A HIGH SPEED RAY TRACING ALGORITHM

Abstract

Computer graphics (CG) involves the generation, representation, manipulation, processing, or evaluation of graphic objects by a computer as well as the association of graphic object with related nongraphic information residing in computer files. Graphic objects my be photographic images, or they may be created with the aid of a computer in the form of alphanumeric characters, special symbols, line drawings, or gray—shaded areas. Such artificially created objects may be rendered in black and white or in color. We can classify computer graphics into subareas, dividing it into three main categories: 1. Generative Graphics 2. Image Analysis 3. Cognitive Graphics Generative graphics involves artificially created graphics objects. The main tasks of generative graphics are: 1. Model (object) construction and picture generation. 2. Model and picture transformation. 3. Object identification and information retrieval. There are two different methods to draw a graphics image: a: Line drawing method b: Shade drawing method In line drawing method a picture is drawn by the help of drawing the contour lines of the object faces. In shade drawing method a picture Is made of shades. On the other word this is a pixel wise method because any pixel is considered independently. By giving different intensities, shadow and shades are generated. Ray tracing is one instance of shade drawing method. Since its output images are very realistic, it is used in wide range to produce artistic pictures. But its speed is notoriously slow. In this thesis I have tried to increase the speed of the ray tracing 4 method. I have proposed and applied eight techniques to increase the speed. As a result, my package is able to produce a full screen image in almost 17 minutes as opposed to more the two hours with classical Ray Tracing method. In appendix C you can see the specification of my package. Chapter one gives a brief description about the ray tracing method. Chapter two explains the experimental work.In this package a picture is generated in three phases: Phase one: The basic date of 3D object is created. Phase two: The image is rotated, scaled and transferred in this phase. Phase three; The final image is generated in this phase. In chapter three the data structure which have been chosen for the primitives will be explained. Chapter four is about the . applied geometry of computer graphics. Almost all algorithms of computer graphics packages are based the geometrical rules. The rules of points (XYZ coordinates) lines planes and vectors will be considered here. Chapter 5 mentions some important test$. These test are used for the following purposes: a: Increasing the speed b: Saving the computer memory c: Taking the next decision The containment test, face visibility test and Max—Min. test are some of the typical tests. In all test I have tried to select the fastest algorithm. Chapter six discusses the eight proposed techniques to save the computer time and memory. A full screen image by ray tracing method was produced in more than two and half hours. But this package only needs less than 20 minutes to generate the same (In PC AT 80386). Shading coloring and shadow generation is explained in chapter seven. I developed an advanced half toning method to produce an acceptable rang of intensities. I produced ' 27 different intensities for each color. This range of intensity is earned in price of reduction in. screen resolution. This problem will disturb the elegancy of the picture. I compensated this deficiency and now the image is as precise as the real object. And finally the thesis concludes the scope of future work.