· 10 years ago · Nov 07, 2015, 04:06 AM
1
2%% bare_conf.tex
3%% V1.3
4%% 2007/01/11
5%% by Michael Shell
6%% See:
7%% http://www.michaelshell.org/
8%% for current contact information.
9%%
10%% This is a skeleton file demonstrating the use of IEEEtran.cls
11%% (requires IEEEtran.cls version 1.7 or later) with an IEEE conference paper.
12%%
13%% Support sites:
14%% http://www.michaelshell.org/tex/ieeetran/
15%% http://www.ctan.org/tex-archive/macros/latex/contrib/IEEEtran/
16%% and
17%% http://www.ieee.org/
18
19%%*************************************************************************
20%% Legal Notice:
21%% This code is offered as-is without any warranty either expressed or
22%% implied; without even the implied warranty of MERCHANTABILITY or
23%% FITNESS FOR A PARTICULAR PURPOSE!
24%% User assumes all risk.
25%% In no event shall IEEE or any contributor to this code be liable for
26%% any damages or losses, including, but not limited to, incidental,
27%% consequential, or any other damages, resulting from the use or misuse
28%% of any information contained here.
29%%
30%% All comments are the opinions of their respective authors and are not
31%% necessarily endorsed by the IEEE.
32%%
33%% This work is distributed under the LaTeX Project Public License (LPPL)
34%% ( http://www.latex-project.org/ ) version 1.3, and may be freely used,
35%% distributed and modified. A copy of the LPPL, version 1.3, is included
36%% in the base LaTeX documentation of all distributions of LaTeX released
37%% 2003/12/01 or later.
38%% Retain all contribution notices and credits.
39%% ** Modified files should be clearly indicated as such, including **
40%% ** renaming them and changing author support contact information. **
41%%
42%% File list of work: IEEEtran.cls, IEEEt ran_HOWTO.pdf, bare_adv.tex,
43%% bare_conf.tex, bare_jrnl.tex, bare_jrnl_compsoc.tex
44%%*************************************************************************
45
46% *** Authors should verify (and, if needed, correct) their LaTeX system ***
47% *** with the testflow diagnostic prior to trusting their LaTeX platform ***
48% *** with production work. IEEE's font choices can trigger bugs that do ***
49% *** not appear when using other class files. ***
50% The testflow support page is at:
51% http://www.michaelshell.org/tex/testflow/
52
53
54
55% Note that the a4paper option is mainly intended so that authors in
56% countries using A4 can easily print to A4 and see how their papers will
57% look in print - the typesetting of the document will not typically be
58% affected with changes in paper size (but the bottom and side margins will).
59% Use the testflow package mentioned above to verify correct handling of
60% both paper sizes by the user's LaTeX system.
61%
62% Also note that the "draftcls" or "draftclsnofoot", not "draft", option
63% should be used if it is desired that the figures are to be displayed in
64% draft mode.
65%
66\documentclass[conference]{IEEEtran}
67\usepackage{blindtext, graphicx}
68\usepackage[T1]{fontenc}
69\usepackage{pgfplots}
70\pgfplotsset{width=8cm,compat=1.9}
71\usepgfplotslibrary{external}
72\tikzexternalize
73\graphicspath{ {images/} }
74\usepackage{amsmath}
75\usepackage{tikz}
76\usepackage{tkz-euclide}
77\usetikzlibrary{patterns}
78\usetkzobj{all}
79\usetikzlibrary{arrows,positioning,shapes.geometric}
80\usepackage{algorithm}
81\usepackage[noend]{algpseudocode}
82\usepackage{pifont}
83\usepackage{gensymb}
84\usepackage{listings}
85\usepackage{subcaption}
86\usepackage{cite}
87\usepackage{color}
88\usepackage[justification=centering]{caption}
89\definecolor{dkgreen}{rgb}{0,0.6,0}
90\definecolor{gray}{rgb}{0.5,0.5,0.5}
91\definecolor{mauve}{rgb}{0.58,0,0.82}
92\usepgflibrary{patterns} % LATEX and plain TEX and pure pgf
93\usepgflibrary[patterns] % ConTEXt and pure pgf
94\usetikzlibrary{patterns} % LATEX and plain TEX when using Tik Z
95\usetikzlibrary[patterns] % ConTEXt when using Tik Z
96\lstset{frame=tb,
97 language=Java,
98 aboveskip=3mm,
99 belowskip=3mm,
100 showstringspaces=false,
101 columns=flexible,
102 basicstyle={\small\ttfamily},
103 numbers=none,
104 mathescape,
105 literate={->}{$\rightarrow$}{2}
106 {ε}{$\varepsilon$}{1},
107 numberstyle=\tiny\color{gray},
108 keywordstyle=\color{blue},
109 commentstyle=\color{dkgreen},
110 stringstyle=\color{mauve},
111 breaklines=true,
112 breakatwhitespace=true,
113 tabsize=3
114}
115
116\usepackage[utf8]{inputenc}
117\usepackage[english]{babel}
118\usepackage{fancyhdr}
119\usepackage{lastpage}
120
121
122\pagestyle{fancy}
123\fancyhf{}
124\tikzstyle{startstop} = [rectangle, rounded corners, minimum width=3cm, minimum height=1cm,text centered, draw=black, fill=red!30]
125
126\tikzstyle{io} = [trapezium, trapezium left angle=70, trapezium right angle=110, minimum width=3cm, minimum height=1cm, text centered, draw=black, fill=blue!30]
127
128\tikzstyle{process} = [rectangle, minimum width=3cm, minimum height=1cm, text centered, draw=black, fill=orange!30]
129\tikzstyle{decision} = [diamond, minimum width=3cm, minimum height=1cm, text centered, draw=black, fill=green!30]
130\tikzstyle{arrow} = [thick,->,>=stealth]
131
132\rfoot{Page \thepage \hspace{1pt} of \pageref{LastPage}}
133% Add the compsoc option for Computer Society conferences.
134%
135% If IEEEtran.cls has not been installed into the LaTeX system files,
136% manually specify the path to it like:
137% \documentclass[conference]{../sty/IEEEtran}
138
139
140
141
142
143% Some very useful LaTeX packages include:
144% (uncomment the ones you want to load)
145
146
147% *** MISC UTILITY PACKAGES ***
148%
149%\usepackage{ifpdf}
150% Heiko Oberdiek's ifpdf.sty is very useful if you need conditional
151% compilation based on whether the output is pdf or dvi.
152% usage:
153% \ifpdf
154% % pdf code
155% \else
156% % dvi code
157% \fi
158% The latest version of ifpdf.sty can be obtained from:
159% http://www.ctan.org/tex-archive/macros/latex/contrib/oberdiek/
160% Also, note that IEEEtran.cls V1.7 and later provides a builtin
161% \ifCLASSINFOpdf conditional that works the same way.
162% When switching from latex to pdflatex and vice-versa, the compiler may
163% have to be run twice to clear warning/error messages.
164
165
166
167
168
169
170% *** CITATION PACKAGES ***
171%
172%\usepackage{cite}
173% cite.sty was written by Donald Arseneau
174% V1.6 and later of IEEEtran pre-defines the format of the cite.sty package
175% \cite{} output to follow that of IEEE. Loading the cite package will
176% result in citation numbers being automatically sorted and properly
177% "compressed/ranged". e.g., [1], [9], [2], [7], [5], [6] without using
178% cite.sty will become [1], [2], [5]--[7], [9] using cite.sty. cite.sty's
179% \cite will automatically add leading space, if needed. Use cite.sty's
180% noadjust option (cite.sty V3.8 and later) if you want to turn this off.
181% cite.sty is already installed on most LaTeX systems. Be sure and use
182% version 4.0 (2003-05-27) and later if using hyperref.sty. cite.sty does
183% not currently provide for hyperlinked citations.
184% The latest version can be obtained at:
185% http://www.ctan.org/tex-archive/macros/latex/contrib/cite/
186% The documentation is contained in the cite.sty file itself.
187
188
189
190
191
192
193% *** GRAPHICS RELATED PACKAGES ***
194%
195\ifCLASSINFOpdf
196 % \usepackage[pdftex]{graphicx}
197 % declare the path(s) where your graphic files are
198 % \graphicspath{{../pdf/}{../jpeg/}}
199 % and their extensions so you won't have to specify these with
200 % every instance of \includegraphics
201 % \DeclareGraphicsExtensions{.pdf,.jpeg,.png}
202\else
203 % or other class option (dvipsone, dvipdf, if not using dvips). graphicx
204 % will default to the driver specified in the system graphics.cfg if no
205 % driver is specified.
206 % \usepackage[dvips]{graphicx}
207 % declare the path(s) where your graphic files are
208 % \graphicspath{{../eps/}}
209 % and their extensions so you won't have to specify these with
210 % every instance of \includegraphics
211 % \DeclareGraphicsExtensions{.eps}
212\fi
213% graphicx was written by David Carlisle and Sebastian Rahtz. It is
214% required if you want graphics, photos, etc. graphicx.sty is already
215% installed on most LaTeX systems. The latest version and documentation can
216% be obtained at:
217% http://www.ctan.org/tex-archive/macros/latex/required/graphics/
218% Another good source of documentation is "Using Imported Graphics in
219% LaTeX2e" by Keith Reckdahl which can be found as epslatex.ps or
220% epslatex.pdf at: http://www.ctan.org/tex-archive/info/
221%
222% latex, and pdflatex in dvi mode, support graphics in encapsulated
223% postscript (.eps) format. pdflatex in pdf mode supports graphics
224% in .pdf, .jpeg, .png and .mps (metapost) formats. Users should ensure
225% that all non-photo figures use a vector format (.eps, .pdf, .mps) and
226% not a bitmapped formats (.jpeg, .png). IEEE frowns on bitmapped formats
227% which can result in "jaggedy"/blurry rendering of lines and letters as
228% well as large increases in file sizes.
229%
230% You can find documentation about the pdfTeX application at:
231% http://www.tug.org/applications/pdftex
232
233
234
235
236
237% *** MATH PACKAGES ***
238%
239%\usepackage[cmex10]{amsmath}
240% A popular package from the American Mathematical Society that provides
241% many useful and powerful commands for dealing with mathematics. If using
242% it, be sure to load this package with the cmex10 option to ensure that
243% only type 1 fonts will utilized at all point sizes. Without this option,
244% it is possible that some math symbols, particularly those within
245% footnotes, will be rendered in bitmap form which will result in a
246% document that can not be IEEE Xplore compliant!
247%
248% Also, note that the amsmath package sets \interdisplaylinepenalty to 10000
249% thus preventing page breaks from occurring within multiline equations. Use:
250%\interdisplaylinepenalty=2500
251% after loading amsmath to restore such page breaks as IEEEtran.cls normally
252% does. amsmath.sty is already installed on most LaTeX systems. The latest
253% version and documentation can be obtained at:
254% http://www.ctan.org/tex-archive/macros/latex/required/amslatex/math/
255
256
257
258
259
260% *** SPECIALIZED LIST PACKAGES ***
261%
262%\usepackage{algorithmic}
263% algorithmic.sty was written by Peter Williams and Rogerio Brito.
264% This package provides an algorithmic environment fo describing algorithms.
265% You can use the algorithmic environment in-text or within a figure
266% environment to provide for a floating algorithm. Do NOT use the algorithm
267% floating environment provided by algorithm.sty (by the same authors) or
268% algorithm2e.sty (by Christophe Fiorio) as IEEE does not use dedicated
269% algorithm float types and packages that provide these will not provide
270% correct IEEE style captions. The latest version and documentation of
271% algorithmic.sty can be obtained at:
272% http://www.ctan.org/tex-archive/macros/latex/contrib/algorithms/
273% There is also a support site at:
274% http://algorithms.berlios.de/index.html
275% Also of interest may be the (relatively newer and more customizable)
276% algorithmicx.sty package by Szasz Janos:
277% http://www.ctan.org/tex-archive/macros/latex/contrib/algorithmicx/
278
279
280
281
282% *** ALIGNMENT PACKAGES ***
283%
284\usepackage{array}
285\newcolumntype{P}[1]{>{\centering\arraybackslash}p{#1}}
286% Frank Mittelbach's and David Carlisle's array.sty patches and improves
287% the standard LaTeX2e array and tabular environments to provide better
288% appearance and additional user controls. As the default LaTeX2e table
289% generation code is lacking to the point of almost being broken with
290% respect to the quality of the end results, all users are strongly
291% advised to use an enhanced (at the very least that provided by array.sty)
292% set of table tools. array.sty is already installed on most systems. The
293% latest version and documentation can be obtained at:
294% http://www.ctan.org/tex-archive/macros/latex/required/tools/
295
296
297%\usepackage{mdwmath}
298%\usepackage{mdwtab}
299% Also highly recommended is Mark Wooding's extremely powerful MDW tools,
300% especially mdwmath.sty and mdwtab.sty which are used to format equations
301% and tables, respectively. The MDWtools set is already installed on most
302% LaTeX systems. The lastest version and documentation is available at:
303% http://www.ctan.org/tex-archive/macros/latex/contrib/mdwtools/
304
305
306% IEEEtran contains the IEEEeqnarray family of commands that can be used to
307% generate multiline equations as well as matrices, tables, etc., of high
308% quality.
309
310
311%\usepackage{eqparbox}
312% Also of notable interest is Scott Pakin's eqparbox package for creating
313% (automatically sized) equal width boxes - aka "natural width parboxes".
314% Available at:
315% http://www.ctan.org/tex-archive/macros/latex/contrib/eqparbox/
316
317
318
319
320
321% *** SUBFIGURE PACKAGES ***
322%\usepackage[tight,footnotesize]{subfigure}
323% subfigure.sty was written by Steven Douglas Cochran. This package makes it
324% easy to put subfigures in your figures. e.g., "Figure 1a and 1b". For IEEE
325% work, it is a good idea to load it with the tight package option to reduce
326% the amount of white space around the subfigures. subfigure.sty is already
327% installed on most LaTeX systems. The latest version and documentation can
328% be obtained at:
329% http://www.ctan.org/tex-archive/obsolete/macros/latex/contrib/subfigure/
330% subfigure.sty has been superceeded by subfig.sty.
331
332
333
334%\usepackage[caption=false]{caption}
335%\usepackage[font=footnotesize]{subfig}
336% subfig.sty, also written by Steven Douglas Cochran, is the modern
337% replacement for subfigure.sty. However, subfig.sty requires and
338% automatically loads Axel Sommerfeldt's caption.sty which will override
339% IEEEtran.cls handling of captions and this will result in nonIEEE style
340% figure/table captions. To prevent this problem, be sure and preload
341% caption.sty with its "caption=false" package option. This is will preserve
342% IEEEtran.cls handing of captions. Version 1.3 (2005/06/28) and later
343% (recommended due to many improvements over 1.2) of subfig.sty supports
344% the caption=false option directly:
345%\usepackage[caption=false,font=footnotesize]{subfig}
346%
347% The latest version and documentation can be obtained at:
348% http://www.ctan.org/tex-archive/macros/latex/contrib/subfig/
349% The latest version and documentation of caption.sty can be obtained at:
350% http://www.ctan.org/tex-archive/macros/latex/contrib/caption/
351
352
353
354
355% *** FLOAT PACKAGES ***
356%
357%\usepackage{fixltx2e}
358% fixltx2e, the successor to the earlier fix2col.sty, was written by
359% Frank Mittelbach and David Carlisle. This package corrects a few problems
360% in the LaTeX2e kernel, the most notable of which is that in current
361% LaTeX2e releases, the ordering of single and double column floats is not
362% guaranteed to be preserved. Thus, an unpatched LaTeX2e can allow a
363% single column figure to be placed prior to an earlier double column
364% figure. The latest version and documentation can be found at:
365% http://www.ctan.org/tex-archive/macros/latex/base/
366
367
368
369%\usepackage{stfloats}
370% stfloats.sty was written by Sigitas Tolusis. This package gives LaTeX2e
371% the ability to do double column floats at the bottom of the page as well
372% as the top. (e.g., "\begin{figure*}[!b]" is not normally possible in
373% LaTeX2e). It also provides a command:
374%\fnbelowfloat
375% to enable the placement of footnotes below bottom floats (the standard
376% LaTeX2e kernel puts them above bottom floats). This is an invasive package
377% which rewrites many portions of the LaTeX2e float routines. It may not work
378% with other packages that modify the LaTeX2e float routines. The latest
379% version and documentation can be obtained at:
380% http://www.ctan.org/tex-archive/macros/latex/contrib/sttools/
381% Documentation is contained in the stfloats.sty comments as well as in the
382% presfull.pdf file. Do not use the stfloats baselinefloat ability as IEEE
383% does not allow \baselineskip to stretch. Authors submitting work to the
384% IEEE should note that IEEE rarely uses double column equations and
385% that authors should try to avoid such use. Do not be tempted to use the
386% cuted.sty or midfloat.sty packages (also by Sigitas Tolusis) as IEEE does
387% not format its papers in such ways.
388
389
390
391
392
393% *** PDF, URL AND HYPERLINK PACKAGES ***
394%
395%\usepackage{url}
396% url.sty was written by Donald Arseneau. It provides better support for
397% handling and breaking URLs. url.sty is already installed on most LaTeX
398% systems. The latest version can be obtained at:
399% http://www.ctan.org/tex-archive/macros/latex/contrib/misc/
400% Read the url.sty source comments for usage information. Basically,
401% \url{my_url_here}.
402
403
404
405
406
407% *** Do not adjust lengths that control margins, column widths, etc. ***
408% *** Do not use packages that alter fonts (such as pslatex). ***
409% There should be no need to do such things with IEEEtran.cls V1.6 and later.
410% (Unless specifically asked to do so by the journal or conference you plan
411% to submit to, of course. )
412\usepackage{algorithm}
413\usepackage{algpseudocode}
414\usepackage{pifont}
415\usepackage[english]{babel}
416\usepackage[utf8]{inputenc}
417\usepackage{multirow}
418\usepackage{mathtools}
419
420\DeclarePairedDelimiter\abs{\lvert}{\rvert}%
421
422% Swap the definition of \abs* and \norm*, so that \abs
423% and \norm resizes the size of the brackets, and the
424% starred version does not.
425
426% correct bad hyphenation here
427\hyphenation{op-tical net-works semi-conduc-tor}
428\usepackage{booktabs}
429\newcommand{\head}[1]{\textnormal{\textbf{#1}}}
430\begin{document}
431%
432% paper title
433% can use linebreaks \\ within to get better formatting as desired
434\title{Accelerated CPU-based Ray Tracer}
435
436
437% author names and affiliations
438% use a multiple column layout for up to three different
439% affiliations
440\author{
441\IEEEauthorblockN{Thejdeep Gudivada}
442\IEEEauthorblockA{
443National Institute of Technology\\
444Karnataka, India 575025\\
445Email: tejdeepg@gmail.com}\\ %<------ Line breaks in the current column
446\IEEEauthorblockN{Shashidhar G Koolagudi}
447\IEEEauthorblockA{National Institute of Technology\\
448Karnataka, India 575025\\
449Email: koolagudi@yahoo.com}
450\and
451\IEEEauthorblockN{Shruthi Puranik}
452\IEEEauthorblockA{National Institute of Technology\\
453Karnataka, India 575025\\
454Email: shruthi3093@gmail.com}\\[0.9cm] %<------- Extra vertical space
455\IEEEauthorblockN{}
456\IEEEauthorblockA{}
457\and
458\IEEEauthorblockN{Shruthi Repally\\}
459\IEEEauthorblockA{National Institute of Technology\\
460Karnataka, India 575025\\
461Email: shrutirepally@gmail.com}\\ %<-----------
462\IEEEauthorblockN{Y. V. Srinivasa Murthy\\}
463\IEEEauthorblockA{National Institute of Technology\\
464Karnataka, India 575025\\
465Email: urvishnu@gmail.com\\}
466}
467
468% conference papers do not typically use \thanks and this command
469% is locked out in conference mode. If really needed, such as for
470% the acknowledgment of grants, issue a \IEEEoverridecommandlockouts
471% after \documentclass
472
473% for over three affiliations, or if they all won't fit within the width
474% of the page, use this alternative format:
475%
476%\author{\IEEEauthorblockN{Michael Shell\IEEEauthorrefmark{1},
477%Homer Simpson\IEEEauthorrefmark{2},
478%James Kirk\IEEEauthorrefmark{3},
479%Montgomery Scott\IEEEauthorrefmark{3} and
480%Eldon Tyrell\IEEEauthorrefmark{4}}
481%\IEEEauthorblockA{\IEEEauthorrefmark{1}School of Electrical and Computer Engineering\\
482%Georgia Institute of Technology,
483%Atlanta, Georgia 30332--0250\\ Email: see http://www.michaelshell.org/contact.html}
484%\IEEEauthorblockA{\IEEEauthorrefmark{2}Twentieth Century Fox, Springfield, USA\\
485%Email: homer@thesimpsons.com}
486%\IEEEauthorblockA{\IEEEauthorrefmark{3}Starfleet Academy, San Francisco, California 96678-2391\\
487%Telephone: (800) 555--1212, Fax: (888) 555--1212}
488%\IEEEauthorblockA{\IEEEauthorrefmark{4}Tyrell Inc., 123 Replicant Street, Los Angeles, California 90210--4321}}
489
490
491
492
493% use for special paper notices
494%\IEEEspecialpapernotice{(Invited Paper)}
495
496
497
498
499% make the title area
500\maketitle
501
502
503\begin{abstract}
504Ray Tracing is one of the most popular methods to achieve global illumination while rendering real world scenes. However its high computational requirements inhibit its usage in real time scenarios. As a result, there always exists a trade-off between the execution time and the quality of the rendered image. In this paper, an effort has been made to address the low computational speeds of the exhaustive ray tracers. One of the techniques used to achieve the speedup is, by controlling the depth of the traversal of the light rays that are emitted from the eye to the objects present in the scene. POSIX threads are used to achieve parallelism while rendering the pixels, which brings down the running time without diminishing the image quality. An efficient algorithm is proposed to find the first intersections of the rays with respect to objects in the scene. In aggregate, the above mentioned heuristics give a hybrid model of what currently exists, in a time efficient manner. Finally, a comparison has been made between the proposed algorithm and the one that exists currently, thereby showing that the proposed algorithm yields a better performance.
505%\boldmath
506
507\end{abstract}
508% IEEEtran.cls defaults to using nonbold math in the Abstract.
509% This preserves the distinction between vectors and scalars. However,
510% if the journal you are submitting to favors bold math in the abstract,
511% then you can use LaTeX's standard command \boldmath at the very start
512% of the abstract to achieve this. Many IEEE journals frown on math
513% in the abstract anyway.
514
515% Note that keywords are not normally used for peerreview papers.
516\begin{IEEEkeywords}
517Ray Tracing, Early ray termination, Illumination, Speedup, Parallel Computation, POSIX threading.
518\end{IEEEkeywords}
519
520
521
522
523
524
525% For peer review papers, you can put extra information on the cover
526% page as needed:
527% \ifCLASSOPTIONpeerreview
528% \begin{center} \bfseries EDICS Category: 3-BBND \end{center}
529% \fi
530%
531% For peerreview papers, this IEEEtran command inserts a page break and
532% creates the second title. It will be ignored for other modes.
533\IEEEpeerreviewmaketitle
534
535
536
537\section{Introduction}
538The conventional process of image rendering involves firing rays from the light sources in all the directions. It finds the points of intersection of the rays with the objects in the scene repeatedly until the rays reach the eye or the camera. Given the number of possible directions for the rays originating from any light source, this process would take a lot of time. Since most of these rays do not reach the eye, there is a scope for improvement. This fact has been exploited by the ray tracers, where the image is rendered by tracing the path of the light rays backwards from the eye or camera to the light source. The interactions of these rays with the objects are simulated in the form of the color of the pixels \cite{2ref}. Hence, in contrast to the conventional image rendering method, ray tracing avoids the unnecessary computations and serves as a better substitute to the typical image rendering methods.\\
539\indent The performance of the ray tracers can be enhanced using appropriate acceleration techniques which lead to better rendering speeds. For a scene containing \mbox{\[\abs{O} \]} number of objects and a resulting image consisting of \mbox{\[\abs{I} \]} pixels, the complexity of ray tracing is equal to $\mbox{\[\abs{O} \]}\times $\mbox{\[\abs{I} \]}. Some of the existing approaches, by which the computational speed of the ray tracer can be improved considerably face bottlenecks in rendering complex scenes as the memory requirements exceed the host system memory \cite{1ref}. Thus, an efficient ray tracer should get an optimized value for the three determinants of images such as the space, the execution time and the image quality. Here, space refers to the amount of working storage needed by the algorithm. The weight assigned to each of these determinants is completely dependent on the resources available and the specific requirements.\\
540\indent Important applications of ray tracing usually focus on adding visual realism and appeal to images \cite{2ref}. This is usually achieved by adding the fancy effects such as reflection and shadowing in animations. These applications along with few others like analysis in theater lighting design, architectural design require us to devise new and efficient methods which attain higher computational speeds \cite{4ref}. Since, the image generation is very expensive in terms of the execution time. The current research in ray tracing concentrates on achieving speedup \cite{3ref}. Following the same lines, in this paper, an effort has been made to reduce the execution time of the ray tracers without diminishing the quality of the image significantly.
541The approaches used to achieve speedup are:
542\begin{itemize}
543\item Early ray termination in the ray intersection tree.
544\item Use of POSIX threading to achieve the parallelism while computing the pixel colors.
545\item An efficient algorithm to compute first object intersections in the scene with the rays shot from the camera (first object intersections).
546\end{itemize}
547
548\indent The remainder of the paper is organised as follows. Section II discusses the various works already done in the area of ray tracing. In section III, a brief introduction to ray tracing from the implementation point of view is given. In section IV, the proposed acceleration strategies to ray tracing are explained. In section V, the results obtained by deploying all the proposed acceleration strategies are presented. Section VI concludes the work done followed by the Appendix which discusses the concept of ray-sphere intersection.
549
550%\subsection{Subsection Heading Here}
551\section{Related Work}
552\label{sec:related}
553As a part of the basic lighting and reflection theory, classical ray tracing and Monte Carlo ray tracing have been discussed here - are the two most popular ray tracing methods.
554
555
556\subsection{Basic Lighting and Reflection Theory}
557A lot of research is being done in understanding the interaction of light with its surroundings \cite{11ref}. For ray tracing, light needs to be studied from the perspective of ray optics \cite{12ref} which describes the propagation of light in terms of rays. The common phenomena of light such as reflection can be understood in a better way with the help of functions such as Bidirectional Reflectance Distribution Function (BRDF) \cite{12ref}. BRDF is a function of four real variables which defines how light is reflected at an opaque surface. The function takes an incoming light direction, an outgoing direction and returns the ratio of reflected radiance along the outgoing direction to the irradiance incident along the incoming direction.
558
559\subsection{Classical Ray Tracing}The ray tracing problem has been dealt by many researchers in the field of computer graphics and computational geometry, started by Whitted et. al \cite{5ref}. An implementation of a simple ray tracer by Thomas Nikodym \cite{6ref} gives a clear idea of the working of a ray tracer in general. Considerable research has been done in finding ways to reduce the ray-object intersections using concepts such as Bounding Volumes, in which each volume encloses a set of objects present in the scene, and bidirectional tracing algorithm for the rays \cite{7ref}\cite{8ref}. Hank et. al \cite{9ref} mentions the concept of Adaptive Depth Control using a mathematical model for building an accelerated ray tracer.}
560
561\subsection{Monte Carlo Ray Tracing}
562The concept of Monte-Carlo ray tracing introduced by Kajiya serves as a substitute to the conventional method of ray tracing \cite{13ref}. Monte Carlo methods rely on repeated random sampling to obtain numerical results. It simulates tracing of the scene by producing many rays instead of just one at the points of intersection of the rays and the objects.
563
564\section{Background}
565There has been a lot of surge towards the field of three dimensional computer graphics over the past few years which can be attributed to the people's fascination for viewing animations. In this section, an overview of the concept of ray tracing is presented along with its working and basic implementation.
566\subsection{Ray Tracing}
567The idea behind image rendering is that the images are composed of light and that light rays coming from a light source traverse around in the scene before hitting the eye or camera. As a result, rendering boils down to finding the intersection of the ray shot from the light source with the objects in the scene and to shading the point of intersection. This is known to produce realistic images of higher degree compared to the scan-line rendering methods \cite{10ref}, but at a greater computational cost. In contrast to this, a ray tracer traces the light rays from the camera to the light source, thereby avoiding unnecessary computations. Figure \ref{fig:ray_image} shows an image which is rendered at 1000 samples per pixel using backward ray tracing techniques.
568
569\subsection{Basic Terminology}
570The most common phenomena in ray optics are reflection and refraction. Reflection is a phenomenon by which light rays bounce off when they strike an object. This is observed either in the form of specular reflection in which the reflected ray travels only in one direction or diffuse reflection in which the reflected rays travel in multiple directions. Refraction of light is the change in the direction of the ray when it travels from one medium to another.
571\begin{figure}[h!]
572 \centering
573 \includegraphics[width=0.4\textwidth]{fig1.png}
574 \caption{The rendered image using Ray Tracing techniques (showing an area of light source)}
575 \label{fig:ray_image}
576\end{figure}
577\subsection{Ray Tracing Algorithm}
578The basic objective of a ray tracer is to determine the intensity of each light ray that falls on the view window before reaching the eye and the rays are traced backwards from the camera to the light source. In other words, only the rays that are certainly going to hit the eye, are to be traced. The ray tracer should consider the presence of both the reflective and refractive objects in a scene. As a result, each ray that hits an object can take two paths, considering reflection and refraction. When each of these two rays hits some other object, two more rays are generated. This process continues until the rays encounter objects which are both opaque and non-reflective. A ray intersection tree is developed as a result of this process which shows the path of each ray. The steps for a simple ray tracer are as follows :
579\begin{itemize}
580\item For each pixel on the view window, construct a ray which connects the eye and the pixel.
581\item Trace the ray as it bounces around various objects in the scene
582\item The final pixel color is depicted by the objects that the ray strikes as it travels around the scene
583\end{itemize}
584
585A simple ray tracer can be implemented using an algorithm discussed by Shirley in \cite{2ref}. \\
586
587
588\section{Proposed Acceleration}
589Since, the conventional ray tracing algorithm follows a rule in which each ray must be checked for intersection against all the objects present in a scene, a naive ray tracer with no speedup techniques performs computations proportional to the number of objects times the number of rays. Each of which requires a pretty big number of floating point operations \cite{4ref}. Although using faster machine to speedup the computations is a solution, it would lead to higher expenditures which is certainly undesirable. A better and more feasible way is needed to reduce the number of ray-object intersections by using certain acceleration techniques. Although, there are enough techniques which achieve the render times much better, they pose a serious problem of the host running out of space while rendering the complex scenes \cite{4ref}. The following techniques do not take much extra space, but still achieve a significant speedup compared to the conventional ray tracing approach. An assumption has been made that all the objects present in the scene are spherical.
590
591\subsection{Controlling the depth of the rays}
592 \indent In most of the typical scenes, the percentage of the objects that are made up of reflective or transparent surfaces is very low. It implies that most of the rays shot from the camera are terminated after a certain number of traversals. Thus, computing the necessary point intersections benefits a lot instead of capturing the reflected and refracted data for every pixel. The main idea behind this is, the reflected or refracted rays are stopped to generate when the depth of the traversed rays go above certain threshold. If the maximum depth is not set, an infinite amount of rays get generated. The first node on the tree contributes 100 percent to the final color of the sample point. The further rays that emerge from the primary ray can be shown to be contributing a fraction of the primary ray's contribution. As a result, intensity of the ray drops since it traverses through the scene \cite{9ref}. The procedure for depth control can be summarized as follows :
593\begin{itemize}
594\item Assign a threshold value
595\item Find the depth of the ray traversed
596\item If the depth is above the threshold, terminate. Else, trace the ray further.
597\end{itemize}
598
599Since, a threshold value is used to control the tree depth, most of the computational time is utilized for determining the first intersections. Ways to efficiently compute the first intersection tests need to be devised \cite{9ref}. This is addressed in section \ref{sec:firstdegree}.
600
601\subsection{Parallelism using Threads}
602Since Ray Tracing is a computationally expensive algorithm, optimal use of hardware is required to make it close to real-time. A close observation reveals that the ray tracing is parallel by nature. Rays can be traced independent of each other and in any random order. The multi-threaded ray tracer is implemented using a master thread and several slave threads. The flow of the process is as follows :
603\begin{itemize}
604\item Master thread asked to render and slave threads are asleep
605\item Master thread prepares tasks
606\item Master awakens slaves and assigns tasks then master goes to sleep
607\item When all the tasks are completed, slaves wake up master
608\item Master finally renders the image
609\end{itemize}
610The parallel implementation of the ray tracer is given in Algorithm \ref{alg:Z-Buffer}.
611
612\begin{algorithm}
613\caption{Parallel Ray Tracer}
614\label{alg:Z-Buffer}
615\begin{algorithmic}[1]
616\State // \textit{Input the Threshold and SPP}
617\State Integer threshold, spp
618\State
619\State // \textit{Initialize and set thread attributes}
620\State Create references to threads
621\State Describe thread attributes
622\State Allocate memory
623\State Initialize the thread attributes object
624\State Create and allocate memory for the parameter variable
625\State
626\State // \textit{Create thread for each row of image}
627\For{i in height}
628 \State Store thread ID
629\State Create thread that calls the render function
630\EndFor
631\State
632\State // \textit{Finally, synchronise each thread for completion}
633\For{i in height}
634\State Join Slave thread with Parent thread
635\EndFor
636\end{algorithmic}
637\end{algorithm}
638
639
640\subsection{Computing First-Degree Intersections}
641\label{sec:firstdegree}
642Figure \ref{fig:inter} shows the method to perform a test for intersection. Consider a sphere with center $C$ on which a ray-intersection test is to be performed. Let $P$ be the position of the camera. A tangent drawn from the point $P$ to the sphere forms an angle $\theta$ with the line joining the point $P$ and the center $C$ of the sphere. Since the tangent forms an angle 90$^{\circ}$ with the radius drawn at the point of intersection, the angle $\theta$ can be determined easily with the help of inverse trigonometric functions. Now, consider any other ray that starts from the camera. If the angle $\phi$ between the ray considered and the line joining the center of the sphere $C$ and the point $P$ is greater than $\theta$, then the ray will certainly not intersect the sphere. If the angle $\phi$ is lesser than or equal to $\theta$, the points of intersection can be determined as shown in Appendix \ref{sec:appe}. \\
643\indent As already mentioned, most of the rendering time would be attributed to the depth of first intersections. Hence, the proposed method is used only for the first depth intersections while the method described in Appendix \ref{sec:appe} is used for the rest.
644\begin{figure}
645\centering
646\begin{tikzpicture}
647\newcommand{\myangle}{120}
648\tkzInit[xmin=-2,xmax=2,xstep=1,ymin=-2,ymax=2,ystep=1]
649\tkzDrawX \tkzDrawY
650\tkzDefPoiFigure nt(0,0){c}
651\tkzDefPoint(1,1){a0}
652\tkzRadius=1 cm
653\tkzDrawCircle[R,thick,color=Cerulean](c,\tkzRadius)
654\tkzDefPointBy[rotation=center c angle \myangle](a0)
655\tkzGetPoint{a}
656\tkzTangent[from with R = a](c,\tkzRadius)
657\tkzGetPoints{e}{f}
658\tkzDrawLine[add = 1 and 2,color=OrangeRed,thick](a,f)
659\draw (-1.5,0)arc[radius=.25cm,start angle=0,end angle=50] node [pos=0.2,below, black, straight] {$\theta$};
660\draw (-1.15,0)arc[radius=.5cm,start angle=0,end angle=75] node [pos=0.2,below, black, straight] {$\phi$};
661\draw (-2,0) -- (0,2) ;
662\draw(0,-2) node[pos=0.1,below right,black,straight] {C}
663\tkzDrawSegment(c,f)
664\tkzDrawPoints[size=3,fill](f,c)
665\node [label=below:P,draw,fill=black,circle,inner sep=0pt,minimum size=2pt] at (-2,0) {};
666\end{tikzpicture}
667\caption{The method to perform faster intersection tests}
668\label{fig:inter}
669\end{figure}
670\\
671\indent A significant speedup is observed with the hybrid model which is designed with the proposed acceleration techniques. Figure \ref{fig:flow} shows the work flow of the overall accelerated ray tracer. The ray tracer begins by taking as input the Samples Per Pixel (SPP) and the threshold level of the ray-intersection tree. The master process spawns slave processes to perform computation in parallel. Each of these slave processes renders each row of the image independently. At each intersection point, the process checks to see if the depth of the tree is greater than the threshold level. If it is found to be greater, the rendering process stops and returns to the master thread. Else, the rendering by the slave process continues.
672
673% needed in second column of first page if using \IEEEpubid
674%\IEEEpubidadjcol
675
676% An example of a floating figure using the graphicx package.
677% Note that \label must occur AFTER (or within) \caption.
678% For figures, \caption should occur after the \includegraphics.
679% Note that IEEEtran v1.7 and later has special internal code that
680% is designed to preserve the operation of \label within \caption
681% even when the captionsoff option is in effect. However, because
682% of issues like this, it may be the safest practice to put all your
683% \label just after \caption rather than within \caption{}.
684%
685% Reminder: the "draftcls" or "draftclsnofoot", not "draft", class
686% option should be used if it is desired that the figures are to be
687% displayed while in draft mode.
688%
689%\begin{figure}[!t]
690%\centering
691%\includegraphics[width=2.5in]{myfigure}
692% where an .eps filename suffix will be assumed under latex,
693% and a .pdf suffix will be assumed for pdflatex; or what has been declared
694% via \DeclareGraphicsExtensions.
695%\caption{Simulation Results}
696%\label{fig_sim}
697%\end{figure}
698
699% Note that IEEE typically puts floats only at the top, even when this
700% results in a large percentage of a column being occupied by floats.
701
702
703% An example of a double column floating figure using two subfigures.
704% (The subfig.sty package must be loaded for this to work.)
705% The subfigure \label commands are set within each subfloat command, the
706% \label for the overall figure must come after \caption.
707% \hfil must be used as a separator to get equal spacing.
708% The subfigure.sty package works much the same way, except \subfigure is
709% used instead of \subfloat.
710%
711%\begin{figure*}[!t]
712%\centerline{\subfloat[Case I]\includegraphics[width=2.5in]{subfigcase1}%
713%\label{fig_first_case}}
714%\hfil
715%\subfloat[Case II]{\includegraphics[width=2.5in]{subfigcase2}%
716%\label{fig_second_case}}}
717%\caption{Simulation results}
718%\label{fig_sim}
719%\end{figure*}
720%
721% Note that often IEEE papers with subfigures do not employ subfigure
722% captions (using the optional argument to \subfloat), but instead will
723% reference/describe all of them (a), (b), etc., within the main caption.
724
725
726% An example of a floating table. Note that, for IEEE style tables, the
727% \caption command should come BEFORE the table. Table text will default to
728% \footnotesize as IEEE normally uses this smaller font for tables.
729% The \label must come after \caption as always.
730%
731%\begin{table}[!t]
732%% increase table row spacing, adjust to taste
733%\renewcommand{\arraystretch}{1.3}
734% if using array.sty, it might be a good idea to tweak the value of
735% \extrarowheight as needed to properly center the text within the cells
736%\caption{An Example of a Table}
737%\label{table_example}
738%\centering
739%% Some packages, such as MDW tools, offer better commands for making tables
740%% than the plain LaTeX2e tabular which is used here.
741%\begin{tabular}{|c||c|}
742%\hline
743%One & Two\\
744%\hline
745%Three & Four\\
746%\hline
747%\end{tabular}
748%\end{table}
749
750
751% Note that IEEE does not put floats in the very first column - or typically
752% anywhere on the first page for that matter. Also, in-text middle ("here")
753% positioning is not used. Most IEEE journals use top floats exclusively.
754% Note that, LaTeX2e, unlike IEEE journals, places footnotes above bottom
755% floats. This can be corrected via the \fnbelowfloat command of the
756% stfloats package.
757\begin{figure}
758 \begin{tikzpicture}[>=latex']
759 \tikzset{block/.style= {draw, rectangle, align=center,minimum width=1cm,minimum height=1cm},
760 rblock/.style={draw, shape=rectangle,rounded corners=0.7em,align=center,minimum width=0.5cm,minimum height=0.2cm},
761 input/.style={ % requires library shapes.geometric
762 draw,
763 trapezium,
764 trapezium left angle=60,
765 trapezium right angle=120,
766 minimum width=0.5cm,
767 maximum width=1cm,
768 align=center,
769 scale=0.8,
770 minimum height=1cm
771 },decision/.style = {diamond, draw,scale=0.8},
772 }
773 \node [rblock] (start) {Start};
774 \node [input, right =1cm of start] (acquire) {Input Threshold\\ and SPP};
775 \node [block, below =1cm of acquire] (rgb2gray) {Master thread};
776 \node [block, left =1cm of rgb2gray] (otsu) {Create slave threads};
777 \node [block, below =1cm of otsu] (gchannel) {Render};
778 \node [block, right =1cm of gchannel] (closing) {Compute closest\\intersection};
779 \node [decision, below=1cm of closing] (decide) {Depth < Threshold ?};
780 \node [rblock, right =1cm of decide] (NN) {Return};
781% Coordinate on left and middle
782
783%% paths
784
785
786 \draw [arrow] (start) -- (acquire);
787 \draw [arrow] (acquire) -- (rgb2gray);
788 \draw [arrow] (rgb2gray) -- (otsu);
789 \draw [arrow] (otsu) -- (gchannel);
790 \draw [arrow] (gchannel) -- (closing);
791 \draw [arrow] (closing) -- (decide);
792 \draw [arrow] (decide) -| node[pos=0.1,above]{yes} (gchannel);
793 \draw [arrow] (decide) -- node[pos=0.1,above]{no} (NN);
794
795
796 \end{tikzpicture}
797 \caption{The work flow of the accelerated ray tracer} \label{fig:flow}
798\end{figure}
799
800\begin{table*}[t]
801\centering
802\begin{tabular}{||P{1.5cm}|P{1.5cm}|P{1.5cm}|P{1.5cm}|P{1.5cm}|P{1.5cm}||}
803\hline
804 & & \multicolumn{4}{P{7cm}|}{Render Time (minutes)}\\
805\cline{3-6}
806 Sl.No&Samples Per Pixel (SPP)&Without Acceleration&Early Ray Termination&Parallelism&Proposed Method\\
807\hline\hline
8081&100&6.815&5.622&3.104&2.521\\
8092&200&13.885&12.017&7.015&5.032\\
8103&300&20.433&17.934&10.591&7.545\\
8114&400&27.292&24.701 &12.791 &10.055\\
812\hline
813\end{tabular}
814\caption{Render times using various techniques}
815\label{table:4}
816\end{table*}
817
818
819
820\section{Results}
821The accelerated ray tracer was executed and the render times were obtained on a machine with a clock speech of 2.5GHz and a physical memory of 4GB. Table \ref{table:4} shows the render times obtained using various acceleration techniques discussed above. It clearly shows that the proposed method yields better render times than the previously available methods. Figure \ref{fig7} shows the images rendered using all the acceleration strategies for varying number of Samples Per Pixel (SPP). It is clearly observable that the quality of the image is enhanced with the increasing SPP. However, the time taken to render the image increases. Figure \ref{fig:graph1} shows a plot of the render times with and without using the proposed speed-up strategy. Although the quality of the image rendered using the proposed method is slightly inferior to the image rendered using the original method, as shown in Figure \ref{fig11}, but the speedup achieved is more than to commensurate for the loss in image quality. Hence, this method is more efficient in performance as compared to the original method.\\
822
823\begin{figure}[ht]
824 \begin{subfigure}[b]{0.5\linewidth}
825 \centering
826 \includegraphics[width=0.75\linewidth]{b100.png}
827 \caption{SPP : 100}
828 \label{fig7:a}
829 \vspace{4ex}
830 \end{subfigure}%%
831 \begin{subfigure}[b]{0.5\linewidth}
832 \centering
833 \includegraphics[width=0.75\linewidth]{w100.png}
834 \caption{SPP : 100}
835 \label{fig7:b}
836 \vspace{4ex}
837 \end{subfigure}
838 \begin{subfigure}[b]{0.5\linewidth}
839 \centering
840 \includegraphics[width=0.75\linewidth]{b200.png}
841 \caption{SPP : 200}
842 \label{fig7:c}
843 \end{subfigure}%%
844 \begin{subfigure}[b]{0.5\linewidth}
845 \centering
846 \includegraphics[width=0.75\linewidth]{w200.png}
847 \caption{SPP : 200}
848 \label{fig7:d}
849 \end{subfigure}
850 \begin{subfigure}[b]{0.5\linewidth}
851 \centering
852 \includegraphics[width=0.75\linewidth]{b300.png}
853 \caption{SPP : 300}
854 \label{fig8:a}
855 \vspace{4ex}
856 \end{subfigure}%%
857 \begin{subfigure}[b]{0.5\linewidth}
858 \centering
859 \includegraphics[width=0.75\linewidth]{w300.png}
860 \caption{SPP : 300}
861 \label{fig8:b}
862 \vspace{4ex}
863 \end{subfigure}
864 \begin{subfigure}[b]{0.5\linewidth}
865 \centering
866 \includegraphics[width=0.75\linewidth]{b400.png}
867 \caption{SPP : 400}
868 \label{fig8:c}
869 \end{subfigure}%%
870 \begin{subfigure}[b]{0.5\linewidth}
871 \centering
872 \includegraphics[width=0.75\linewidth]{w400.png}
873 \caption{SPP : 400}
874 \label{fig8:d}
875 \end{subfigure}
876 \caption{Scenes rendered using varying number of Samples per Pixel}
877 \label{fig7}
878\end{figure}
879
880\begin{figure}[ht]
881 \begin{subfigure}[b]{0.5\linewidth}
882 \centering
883 \includegraphics[width=0.75\linewidth]{original_400.png}
884 \caption{Original Method}
885 \label{fig11:a}
886 \end{subfigure}%%
887 \begin{subfigure}[b]{0.5\linewidth}
888 \centering
889 \includegraphics[width=0.75\linewidth]{proposed_400.png}
890 \caption{Proposed Method}
891 \label{fig11:b}
892 \end{subfigure}
893 \caption{Comparison of rendered image quality of the two approaches}
894 \label{fig11}
895\end{figure}
896
897\begin{figure}
898\begin{tikzpicture}
899\begin{axis}[
900 x tick label style={
901 /pgf/number format/1000 sep=},
902 ylabel=Time to Render (minutes),
903 xlabel=SPP,
904 enlargelimits=0.05,
905 legend style={at={(10.5,0.5)},
906 legend pos = north west,
907 anchor=north west,legend rows=2},
908 ybar interval=0.7,
909]
910\addplot [black,fill=blue,pattern=grid]
911 coordinates {(100,6.815) (200,13.885)
912 (300,20.433) (400,27.292)(500,28)};
913\addplot [black,fill=gray,pattern=northwest lines]
914 coordinates {(100,2.521) (200,5.032)
915 (300,7.545) (400,10.055) (500,11)};
916\legend{Without Acceleration,With Acceleration}
917\end{axis}
918\end{tikzpicture}
919\caption{Rendering speeds using acceleration methods}
920\label{fig:graph1}
921\end{figure}
922
923\section{Conclusion and Future Work}
924In this paper, an approach is presented which has an improvement in the rendering times without consuming high computational space unlike the other approaches such as Bounding Volumes. Although, the speedup may not be as high as the ones using acceleration data structures, a lot of space on the host system is saved when rendering the complex scenes. The conventional ray tracing algorithm is improved using a hybrid model of acceleration techniques such as controlling the depth of light ray traversals, faster ray-object intersection tests and process level parallelism. The results presented also show that the proposed ray tracer performed better against the conventional one, thereby, clearly showing an improvement over the conventional algorithm.\\
925\indent An improvement to the proposed method can be made by supporting parallelism at the instruction level instead of process level. An investigation can be made as to how the concept of early ray termination described in this paper performs together with bounding volumes and hierarchical structures, which makes the use of tree structures for describing the scene. Another possible extension is to re-design the program using the Compute Unified Device Architecture (CUDA) parallel computing platform to make it compatible with graphical processors for achieving a better speedup.
926
927% if have a single appendix:
928%\appendix[Proof of the Zonklar Equations]
929% or
930%\appendix % for no appendix heading
931% do not use \section anymore after \appendix, only \section*
932% is possibly needed
933
934% use appendices with more than one appendix
935% then use \section to start each appendix
936% you must declare a \section before using any
937% \subsection or using \label (\appendices by itself
938% starts a section numbered zero.)
939%
940\medskip
941\bibliographystyle{unsrt}
942\bibliography{sample}
943
944\appendices
945\section{Ray-Sphere Intersection}
946\label{sec:appe}
947Intersecting a ray with a sphere is probably the simplest form of ray-geometry intersection test. It also has the advantage of being quite fast. A technique is described which is often the solution implemented in rendering engines. A ray can be expressed using the equation \ref{eq:1}:
948
949\begin{equation}
950r(t) = o + t * r
951\label{eq:1}
952\end{equation} where o is a point and corresponds to the origin of the ray, r is a vector and corresponds to the direction of the ray, and t is a parameter of the function. \\
953\indent The idea behind solving the ray-sphere intersection test, is that spheres too can be defined algebraically as in equation \ref{eq:2}.\\
954\begin{equation}
955 x^2 + y^2 + z^2 = R^2
956 \label{eq:2}
957\end{equation}
958
959where x, y and z are the coordinates of a Cartesian point and R is the radius of a sphere centred at the origin. Substitute equation \ref{eq:1} in \ref{eq:2} to obtain \ref{eq:3} :
960\begin{equation}
961 |o + r*t|^2 - R^2 = 0
962 \label{eq:3}
963\end{equation}
964
965
966Expanding equation \ref{eq:3}, equation \ref{eq:4} is obtained:
967\begin{equation}
968 |o^2 + (r*t)^2 + 2*o*r*t| - R^2 = 0
969 \label{eq:4}
970\end{equation}
971
972which is a quadratic equation of the form present in equation \ref{eq:5} :
973\begin{equation}
974a*x^2 + b*x + c = 0
975 \label{eq:5}
976\end{equation}
977
978Since a, b and c are known, the roots of the above equation can be computed and the points of intersection of the ray with the sphere can be derived.\\
979\indent This can be extended to considering a sphere whose center does not coincide with the origin. In such a case, equation \ref{eq:3} can be rewritten as :
980\begin{equation}
981 |o + r*t - C|^2 - R^2 = 0
982\end{equation}
983where C is the center of the sphere.
984
985
986
987
988% Can use something like this to put references on a page
989% by themselves when using endfloat and the captionsoff option.
990\ifCLASSOPTIONcaptionsoff
991 \newpage
992\fi
993
994
995
996% trigger a \newpage just before the given reference
997% number - used to balance the columns on the last page
998% adjust value as needed - may need to be readjusted if
999% the document is modified later
1000%\IEEEtriggeratref{8}
1001% The "triggered" command can be changed if desired:
1002%\IEEEtriggercmd{\enlargethispage{-5in}}
1003
1004% references section
1005
1006% can use a bibliography generated by BibTeX as a .bbl file
1007% BibTeX documentation can be easily obtained at:
1008% http://www.ctan.org/tex-archive/biblio/bibtex/contrib/doc/
1009% The IEEEtran BibTeX style support page is at:
1010% http://www.michaelshell.org/tex/ieeetran/bibtex/
1011%\bibliographystyle{IEEEtran}
1012% argument is your BibTeX string definitions and bibliography database(s)
1013%\bibliography{IEEEabrv,../bib/paper}
1014%
1015% <OR> manually copy in the resultant .bbl file
1016% set second argument of \begin to the number of references
1017% (used to reserve space for the reference number labels box)
1018
1019%H.~Kopka and P.~W. Daly, \emph{A Guide to \LaTeX}, 3rd~ed.\hskip 1em plus
1020 % 0.5em minus 0.4em\relax Harlow, England: Addison-Wesley, 1999.
1021
1022
1023
1024% biography section
1025%
1026% If you have an EPS/PDF photo (graphicx package needed) extra braces are
1027% needed around the contents of the optional argument to biography to prevent
1028% the LaTeX parser from getting confused when it sees the complicated
1029% \includegraphics command within an optional argument. (You could create
1030% your own custom macro containing the \includegraphics command to make things
1031% simpler here.)
1032%\begin{biography}[{\includegraphics[width=1in,height=1.25in,clip,keepaspectratio]{mshell}}]{Michael Shell}
1033% or if you just want to reserve a space for a photo:
1034
1035
1036% You can push biographies down or up by placing
1037% a \vfill before or after them. The appropriate
1038% use of \vfill depends on what kind of text is
1039% on the last page and whether or not the columns
1040% are being equalized.
1041
1042%\vfill
1043
1044% Can be used to pull up biographies so that the bottom of the last one
1045% is flush with the other column.
1046%\enlargethispage{-5in}
1047
1048
1049
1050
1051% that's all folks
1052\end{document}