New User Special Price Expires in

Let's log you in.

Sign in with Facebook


Don't have a StudySoup account? Create one here!


Create a StudySoup account

Be part of our community, it's free to join!

Sign up with Facebook


Create your account
By creating an account you agree to StudySoup's terms and conditions and privacy policy

Already have a StudySoup account? Login here


by: Dr. Garrison Mohr


Dr. Garrison Mohr
GPA 3.87


Almost Ready


These notes were just uploaded, and will be ready to view shortly.

Purchase these notes here, or revisit this page.

Either way, we'll remind you when they're ready :)

Preview These Notes for FREE

Get a free preview of these Notes, just enter your email below.

Unlock Preview
Unlock Preview

Preview these materials now for free

Why put in your email? Get access to more of this material and other relevant free materials for your school

View Preview

About this Document

Class Notes
25 ?




Popular in Course

Popular in ComputerScienence

This 122 page Class Notes was uploaded by Dr. Garrison Mohr on Saturday September 26, 2015. The Class Notes belongs to CP SC 102 at Clemson University taught by Staff in Fall. Since its upload, it has received 11 views. For similar materials see /class/214266/cp-sc-102-clemson-university in ComputerScienence at Clemson University.

Similar to CP SC 102 at Clemson

Popular in ComputerScienence




Report this Material


What is Karma?


Karma is the currency of StudySoup.

You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!

Date Created: 09/26/15
Basic elements of 3D coordinate systems and linear algebra Coordinatate systems are used to assign numeric values to locations with respect to a particular frame of reference commonly referred to as the origin The number of dimensions in the coordinate system is equal to the number of perpendicular orthgonal axes and is also the number values needed to specify a location with respect to the origin One dimension the line I A x I V x 00 4 5 Two dimensions the plane O 45 2 x 0 0 Three dimensions the universe as we perceive it A right handed coordinate system is shown In a left handed system the direction of the positive z axis is reversed 37 45 2 3 X Z Points in 3D space The location of a point P in 3 D Euclidean space is given by a triple px py pz The x y and z coordinates specify the distance you must travel in directions parallel to the the x y and z axes starting from the origin 0 0 0 to arrive at the point p x py pz Vectors in 3D space A vector in 3 D space is sometimes called a directed distance because it represents both o a direction and o a magnitude or distance In this context the triple pl py 17 can also be considered to represent o the direction from the origin 0 0 0 to pl py pz and o its length sqrtpx2 pyz pzz is the Euclidean straight line distance from the origin to pl 17 pz Points and vectors Two points in 3 D space implicitly determine a vector pointing from one to the other Given two points P and Q in 3 D Euclidean space the vector RP39QPx39qxPyQy19z39Qz represents the direction from Q to P Its length as defined above is the distance between P and Q Note that the direction is a signed quantity The direction from P to Q is the negative of the direction from Q to P However the distance from P to Q is always the same as the distance from Q to P Example Let V 8 6 5 and P 3 2 0 Then the vector direction from VtoPis 3 8 2 6 0 5 5 4 5 The vector direction from P to Vis 5 4 5 The distance between V and Pis sqrt25 16 25 sqrt66 812 The geometric interpretation of vector arithmetic Here we work With 2 dimensional vectors to simplify the Visual interpretation but in 3 d the principles are the same P 5 1 gt 5 in the x direction and then 1 in the y direction Q 2 4 gt 2 in the x direction and 4 in the y direction R P Q 7 5 PR QRQ Useful operations on vectors We define the sum of two vectors P and Q as the componentwise sums RPQpxqu pyqyy pzqz 3 4 5 I 2 6 4 6 II The difference of two vectors is computed as the componentwise differences RzP39Qpx39qu py39q pz39qz 3 4 5 I 2 6 2 2 I We also define multiplication or scaling of a vector by a scalar number a S aP apx apy arm 3 gtl 1 2 3 3 6 9 The length of a vector P is a scalar whose value is denoted 2 2 2 H P H sqr px py 179z 3 4 5 II sqrt9 16 25 sqrt50 A unit vector is a vector whose length is 1 Therefore an arbitrary vector P may be converted to a unit vector by scaling it by 1 its own length Here U is a unit vector in the same direction as P UIPP The inner product or dot product of two vectors P and Q is a scalar number It is computed by taking the sum of the componentwise products of the two vectors xPdOIQprxquw pzqz 234d0t32I664I6 Thus II P H sqrtP dot P If U and Vore unit vectors and q is the angle beween them then cos q UdotV Vdot U Representing vectors in C There are at least two easy ways to represent a vector Array based representation Use a three elernent double precision array double vec 3 Where it is understood that vec0 is the X cornponent coordinate vec1 is the y component vec2 is the z cornponent Structure based representation Define a structured type in which the elements are explicitly named typede f struct vectype double x double y double 2 vect vect vec In this representation it is explicit that vecx is the X component vecy is the y component vecz is the z component Religious wars have been fought over which is correct We Will refuse to engage in the war but we will use the structure based approach in this course Because elements of a structure are guaranteed to be packed into adjacent memory elements its possible to cheat and use either array or structure notation vect v 10 20 30 double w double ampv printfquot1f lf lfr1quot vx vy vz printfquot1f lf lfr1quot w0 wl W2 I 1000000 2000000 3000000 1000000 2000000 3000000 A library for 3D vector operations Since the above operations Will be commonly required in the raytracer you Will build a library of functions Which we Will call vector to perform them Here are the function prototypes that must be employed Because the functions are called many times we Will use the inline mechanism of gcc to improve performance The static qualifier is used to avoid duplicate definition errors at link time when functions are included in h files Scale a 3d vector static inline void vecscale double fact Scale factor vect vl Input vector vect v2 Output vector Return length of a 3d vector static inline double veclen vect vl Vector whose length is desired Compute the difference of two vectors v3 v2 vl static inline void vecdiff vect vl subtrahend vect v2 minuend vect v3 result Compute the sum of two vectors static inline void vecsum vect vl addend vect v2 addend vect v3 result Return the inner product of two input vectors static inline double vecdot vect vl Input vector 1 vect v2 Input vector 2 Copy one vector to another static inline void veccopy vect vl input vector vect v2 output vector Construct a unit vector in direction of input static inline void vecunit vect vl Input vector vect v2 output unit vec Read in values of vector from file static inline void vecload FILE in vect vl Print values of vector to file static inline void vecprn FILE out output file char label label string vect vl vector to print Warning regarding aliased parameters When parameters are passed using pointers a potentially destructive phenomenon known as aliasing may occur Here the caller of vecunit is requesting that a vector be converted to a unit vector in place vecunit v1 v1 Now suppose the implementation of vecunit is as follows static inline void vecunit vect vin vect vout vout gtx Vin gtx veclenvin vout gty Vin gty veclenvin vout gtz Vin gtz veclenvin This looks correct and assuming veclen is working properly it will work correctly as long as the parameters vin and vout point to different vectors However if they point to the same vector incorrect computation will result If vin and vout point to the same vector the assignment vout gtx vin gtx veclen Vin also changes vingtx Therefore in the subsequent steps of the computation vout gty Vin gty veclenvin vout gtz Vin gtz veclenvin veclen will generally but not always return a di erent value than in the preceding step For the computation to work correctly veclen must always return the original length of the input vector A correct version of vecunit The function can be written correctly and more efficiently as static inline void vecunit vect vin vect vout double scale 10 veclenvin vecscalescale Vin vout ALL vector functions must work correctly With aliased parameters A sample test driver for vectorh p33c include include include include vect Vl vect V2 ltmathhgt ltstdiohgt ltstd1ibhgt quotvectorhquot 30 40 50 40 10 20 main vect V3 vect V4 double V vecprnstdout vecprnstdout quotV2quot ampV2 vecdiffampVl ampV2 ampV3 vecprnstdout quotV2 Vl quot quotv1quot ampv1 ampV3 V vecdotampVl ampV2 printfquotVl dot V2 is 831f nquot V V vec1enampVl printfquotLength of V1 is 831f nquot V vecsca1el V ampV1 ampV3 vecprnstdout quotV1 scaled by its 1 lengthzquot ampV3 vecunitampVl ampV4 vecprnstdout quotunit vector in V1 directionzquot ampV4 V1 3000 4000 5000 V2 4000 1000 2000 V2 V1 1000 5000 3000 Vl dot V2 is 18000 Length of V1 is 7071 Vl scaled by its 1 length 0424 0566 0707 unit vector in V1 direction 0424 0566 0707 Representing rgb data In the raytracer we will work with three types of rgb data re ective materials emissive lights pixels We will use rgb data for all three but will use different models for the interaction of lights with materials than for the pixmap itself As in CPSC 101 for the pixmap data used in the ppm file we use an unsigned character representation where 0 means black and 255 means maximal brightness typedef struct irgbtype unsigned char r unsigned char g unsigned char b irgbt For representing lights re ective materials and their interactions we use typedef struct drgbtype double r double g double b drgbt In this representation 00 means black and 10 means maximal brightness It is possible to produce values gt 10 and as in CPSC 101 these must be clamped before converting to irgbt Ray tracing introduction The objective of a ray tracing program is to render a photo realistic image of a virtual scene in 3 dimensional space There are two major components in the process The virtual camera 1 The viewpoint This is the location in 3d space at which the viewer of the scene is located 2 The screen This defines a virtual window through which the viewer observes the scene The window can be viewed as a discrete 2 D pixel array pixmap The roytrocing procedure computes the color of each pixel When all pixels have been computed the pixmap is written out as a ppm file The scene to be viewed 3 materials One or more material definitions may be associated with each object The material definition describes how the object interacts with a light Among other things the material definition defines the color of the object 4 light sources Lights themselves are not visible but they do illuminate objects and may be subject to shadowing Lights may be white or colored 5 7 visible objects Re ective objects that are illuminated by the light sources light light I obj viewpt obj obj obj SC reen Camera Scene World and window coordinate systems Two coordinate systems will be involved and it will be necessary to map between them 1 Window coordinates the coordinates of individual pixels in the virtual window These are two dimensional x y interger numbers For example if a 400 col x 300 row image is being created the window x coordinates range from 0 to 399 and the window y coordinates range from 0 to 299 In the raytracing algorithm a ray will be red through each pixel in the window The color of the pixel will be determined by the color of the objects the ray hits 2 World coordinates the natural coordinates of the scene measured in feetmeters etc Since world coordinates describe the entire scene these coordinates are three dimensional x y z oating point numbers For the sake of simplicity we will assume that the screen lies in the z 00 plane the lower left comer of the window has world coordinates 00 00 00 the lower left comer of the window has window pixel coordinates 0 0 the location of the viewpoint has a positive z coordinate all objects have negative z coordinates lights may be located in either positive or negative z space Translating from pixel to world coordinates Problem Suppose the window is 640 pixels wide x 480 pixels high and that the dimension of the window in world coordinates is 8 feet wide by 6 feet high Find the world coordinates of the pixel at column 100 row 40 Possible Solution Compute the fraction or percentage of the complete x size that must be traversed to reach column 100 This value is 100640 2 10 64 meaning column 100 is 1064 of the way across the window The x world coordinate of this location is therefore 10 64 of the total world distance across the window or 10648 10 8 125 Similarly the world y coordinate is 40 480 6 1 12 6 05 A general formula for the procedure is thus worldx worldsizex winx winsizex Thus the desired world coordinate is 125 05 00 Recall the screen lies in the z 0 plane Therefore the z world coordinate of every point in the window is 00 WARNING Pixel dimensions are stored as integers You must ensure that the divisions shown above are done in oating point An alternative world View If the above approach is used then the pixel with x coordinate 0 clearly maps to world coordinate 0 as it apparently should But if we are constructing a 640 pixel image the maximum pixel coordinate is thus 639 And thus the corresponding world coordinate is 8 639 640 7988 instead of 8 We can fix that by changing worldx worldsizex winx winsizex I In this way pixel coordinate 0 maps to world coordinate 0 and pixel coordinate 639 maps to world coordinate 8 But then nice pixel coordinates such as 40 and 100 now map to really ugly numbers slightly larger than 125 and 05 Furthermore the image has no center pixel that maps to world coordinate 40 30 00 We can get back our nice numbers and our center pixel by using the above strategy but always making the image size 1 more than a nice size eg 801 x 601 Since the computer doesn39t really care whether a number is ugly or nice we will use this formulation worldx worldsizex winx winsizex 1 world y worldsizey winy winsizey I Computing the direction of a ray Problem Suppose the viewpoint is at location 4 3 6 in world coordinates Compute a unit length vector from the viewpoint through the pixel at column 100 row 40 Solution We saw above that the world coordinates of the pixel is 125 05 0 From page three we know that two points in 3 D space implicitly determine a vector pointing from one to the other Given two points P and Q in 3 D Euclidean space the vector RP39QPx39QxPyQyPz Qz represents the direction from Q to P Therefore the vector from the viewpoint to the point on the window is point viewpoint or 125 05 0 436 125 4 05 3 0 6 275 250 600 The length of this vector is 706 and so a unit length vector in this direction is 039 035 085 If you have computed the direction correctly the z component of the vector will always be negative A good plan is therefore to include the line assertdirection gtz lt O The assert facility will abort your program if the condition is FALSE and will print the module and line number where the problem happened You might be tempted to also do assert veclendirection 10 but because oating point arithmetic is imprecise that would not be a good idea The raytracing algorithm The complete algorithm for the first version of the raytracer is summarized below Phase I Initialization acquire camera data from the stdin and allocate malloc pixmap data bu er dump camera data to the stderr load material object and light descriptions from the stdin dump material object and light descriptions to the stderr Phase 2 The raytracing procedure for building the pixmap for each pixel in the window 1 initialize the color of the pixel to 00 00 00 compute the direction in 3d space of a ray from the viewpoint through the pixel identify the rst closest object hit by the ray make a copy of the ambient color of the material associated with the object scale the copy of the ambient color by 10 distancefromviewpt to hitpt add the scaled value to the color of the pixel convert the drgb pixel to irgb and store it in the pixmap Phase 3 Writing out the pixmap as a ppm le write ppm header to stdout write the image to stdout Example input le and image famera Cami camera material and plane are cam green and leftwall are pixel dim 6 4 O 4 8 0 type names analogous to int instance names analogous to worlddim 8 6 char oat Only de ned type va able names in C Any name VleWpOlnt 4 3 6 names are legal in this context may be used here material green Re ectivity ie color of objects is specified as double r g b ambient O 5 O values Values must be chosen in an ad hack manner material yellow d1 f fus e 4 4 0 Our lighting model assumes 3 ambient 5 4 0 types of re ectivy ambient specular l l l diffuse and specular Initially only ambient Will be implemented plane leftwall material green normal 3 O l Plane definitions must contain the three attributes point 0 O O shown Materials must be defined before they are referenced The value of point is the X yz plane rightwall coordinates of any point on the plane The value of normal is a vector perpendicular to the plane in the material yellow normal 3 O 1 point 8 O O direction of the viewpoint material gray ambient 2 2 2 plane floor material gray normal 0 l 0 point 0 O2 O 20 The output image near the greenrgmy boundary counesy ofJPEG compression LHKWVDH the object the edges ofthe wages component onne normal from 1 to 111 when we do this the ooxmangle becomes larger and the mtexsecuon onhe two ploms becomes mdlsunct plane leftwall materlal green normal 3 0 01 polnt o o 0 plane rlghtwall materlal yellow normal 73 0 01 polnt E The camera data structure The typedef facility can be used to create an identifier for a user defined type The following example creates a new type name camt which is 100 equivalent to struct cameratype You may either use or not use typedef as you see fit A structure of the following type can be used to hold the view point and coordinate mapping data that defines the projection onto the virtual window define NAMELEN 16 define CAMCOOKIE 23987237 typedef struct cameratype int cookie ID s this as a camera char nameNAMELEN User selected camera name int pixeldim2 Projection screen size in pix double worlddim2 Screen size in world coords vect Viewpoint Viewpt Loc in world coords irgbt pixmap Build image here camt The CAMCO0KIE value is a completely arbitrary quasi random identifier that can be used in conjunction with the assert mechanism to detect a defective camt pointers o camt structures that have been corrupted via other pointer errors When a camera structure is created the cookie should be initialized o camgtcookie CAMCO0KIE When a function is passed an alleged pointer to a camt it should be verified o assertcamgtcookie 2 CAMCO0KIE If the value of the expression passed to assert is false the program is aborted and a message issued which provides the module name and line number at which the error was detected 23 Parsing the input le Parsing is a process in which an input file containing sentences written in some language is a read in from a file a tokenized o analyzed The semantics of the language determine the actions that are taken during the analysis Some languages eg the C programming language are quite complex and some formal mechanisms are needed to process them Our input language is simple enough that informal ad hoc methods suffice A token is a wor in the language In this input camera caml pixeldim 800 6 OO worlddim 8 6 viewpoint 4 4 4 camera am 1 pixeldim 800 600 etc are tokens The individual letters making up the words and the digits making up the numbers are not If and only if the language is structured rigidly enough that the position in a sentence in which string values and numeric values can be known in advance then fscan can be used as a combination readertokenizer o s token is a string of 1 or more characters o d token is an integer value c lf token is a double precision value This Will be the case for the raytracer 24 Model description language Each quotsentencequot in our language begins with an an entitytype identifier Our entitytypes will include camera material light plane sphere etc The entitytype is followed by user defined and arbitrary entityname entitytypes are analogous to data types in C int oat double entitynames are analogous to variable names in C max min pixel The entityname is followed by a collection of entityattributes enclosed in Each entityattribute consists of an attributetype specifier followed by attribute values The entitytypes and attributetypes are prede ned keywords and will always be spelled as shown The attribute values will always follow the attribute type The number of values of a particular attribute will never vary The attributes of any entity may appear in any order Attribute values map to the data structure associated with a particular entity type in an obvious way camera caml pixeldim worlddim 800 600 8 6 viewpoint 4 4 6 The attribute values map to the camt structure in the obvious way int pixeldim2 Projection screen size in pix double worlddim2 Screen size in world coords vect Viewpoint Viewpt Loc in world coords 25 In summary our model description language looks informally like enti ty type enti ty name attribute type attribute values attribute type attribute values entity type entity name attribute type attribute values etc That is o the attribute list of each entity definition is terminated by the 1 token and o the complete model definition is terminated by endof le 26 Constructors and parsing In object oriented languages each object type has an associated constructor function that is called each time a new instance of the object type is created Therefore if a raytracing model contains two planes the plane constructor will be invoked twice Each entitytype will provide a constructor function that will know about the attributes that apply to the entity will and be responsible for parsing them Entity constructors should use the as sert mechanism to abort the program whenever c an unknown attribute type is encountered o the proper number of attribute values cannot be read in o required attributes are missing We will constrain to some degree the order in which attributetypes may appear 27 An example parser Suppose a gaming system contains objects of type aircraft define ACCOOKIE 12345932 ids an aircraftt define ACMASK 7 required item bitmask typedef struct aircrafttype int cookie must have value ACCOOKIE int attrmask attribs found char nameNAMELEN name of this aircraft vect position current location vect direction direction of travel double speed speed in knots aircraftt A similar input language is used so that the input looks like aircraft FlB l position 20000 30000 300000 direction 1 O 1 speed 720 28 Creating and initializing a new aircraft structure A new structure of type aircraftt might be created and initialized as follows this function is invoked when the parser driver reads an entity type which has the value quotaircraftquot It then calls the aircraftinit constructor to create an instance of the aircraftt stucture and to load the attributes of this aircraft aircraftt aircraftinit FILE in char buf256 int count Create new aircraft structure aircraftt aircraft mallocsizeofaircraftt assertaircraft 1 NULL memsetaircraft O sizeofaircraftt aircraft gtcookie ACCOOKIE The word quotaircraftquot has already been read so here we acquire the name of the aircraft le l fscanfin quotsquot aircraft gtname consume the quotquot and verify we found it IIS ll fscanfin buf assertbuf0 39 29 Loa nga bums Now the attributes are loaded They may be specified in arbitrary order The alleged attribute name is read here but is processed in aircra attrload load required attributes buf buf0 1 fscanfin count count while quot065quot ampamp aircraftattrloadin aircraft buf buf 0 count fscanfin quotsquot buf verify the closing assertbuf0 39 Verify all required attributes loaded assertaircraft gtattrmask returnaircraft ACMASK Attribute processing The sanest way to process attributes that may appear in arbitrary order is to make it somewhat table driven This generic approach is straightforward to transfer to other object types such as cameras Here we build a table of 3 pointers Each pointer is initalized to point to a string which is the name of one of the legal attributes It is important to understand that this is a table of pointers not a table of strings Table of legit attributes static char acattrs quotpositionquot Current location of aircraft quotdirectionquot Direction of travel quotspeedquot Speed in NMhr define NU39MATTRS sizeof acattrs sizeof acattrs O The following lookup function can be used to identify which if any attribute is found in the input It should return the index in the attribute table of the string passed in target This should go in rayfunsh static inline int tablelookup char attrs Table of attribute names int count Number of attribute names char target name from input int code 1 int i for i O i lt count i if strcmptarget attrsi 0 returni returncode Processing a single attribute This function is called as each attribute name is read The index of the attribute name is looked up in the table and the index is used to determine which loader to call static inline void aircraftattrload FILE in aircraftt aircraft char attr char buf18 int ndx verify structure pointer assertaircraft gtcookie ACCOOKIE Perform table lookup and ensure it worked ndx tablelookupacattrs NUMATTRS attr assertndx gt 0 Remember which attribute was found aircraft gtattrmask 1 ltlt ndx if ndx 0 aircraftloadpositionin aircraft else if ndx 1 aircraftloaddirectionin aircraft else aircraftloadspeedin aircraft Obtaining the values of a single attribute This approach is fairly code intensive requiring a small blob of code for each an every element of each and every structure An advantage is that it is straightforward and easy to understand but a more clever fully table driven approach could be constructed that would avoid ad hoc functions such as this one entirely static inline void aircraftloadposition FILE in aircraftt ac int count assertac gtcookie ACCOOKIE count fscanfin quotlf lf lfquot ampac gtpositionx ampac gtpositiony ampac gtpositionz x ensure that the required number of values were found assertcoun 3 Ray tracer data structures the rayh header le A common technique in building large programs is to consolidate all required header files into a single header file that can be conveniently included by all source modules The file my will contain most of the important data structures of the ray tracer and will also include the header files needed by all of the modules comprising the system rayh include ltstdiohgt include ltstdlibhgt include ltmathhgt include ltstringhgt include ltmemoryhgt include ltasserthgt define NAMELEN l6 max len of entityattr names define OBJCOOKIE 14555678 quasi random cookie values define MATCOOKIE 32434323 used to verify that struct define LGTCOOKIE 30434344 pointers are what they define CAMCOOKIE 49324423 pretend to be define MODCOOKIE 34321564 include quotvectorhquot vect and vector functions typedef struct cameratype int cookie char nameNAMELEN vect Viewpoint Viewpt Loc in world coords int pixeldim2 Projection screen size in pix double worlddim2 Screen size in world coords irgbt pixmap Build image here camt listt objectt materialt lightt drgbt irgbt etc MUST COME LAST include quotrayfunshquot generic inline functions include quotrayhdrshquot prototypes for intermodule calls An alternative approach rayh include ltstdiohgt include ltstdlibhgt include ltmathhgt include ltstringhgt include ltmemoryhgt include ltasserthgt define NAMELEN l6 max len of entityattr names define OBJCOOKIE 12345678 quasi random cookie values define MATCOOKIE 32456123 used to verify that struct define LGTCOOKIE 30492344 pointers are what they define CAMCOOKIE 49495923 pretend to be include quotvectorhquot vect and vector functions include quotlisthquot include quotcamerahquot include quotobjecthquot include quotplanehquot Still have to come last 111 include quotrayfunshquot generic inline functions include quotcamhdrshquot prototypes for intermodule calls include quotlisthdrshquot prototypes for intermodule calls include quotobjhdrshquot prototypes for intermodule calls Neither way is right or wrong Factors that in uence the choice would be the size of the team working on the program and the personal preference of the programmer I use the approach shown on the previous page because it makes it easy to look at all of my data structures all at one time but you are free to do it any way you wish The one approach lD0 NOT recommend is including a giant list of header files in every source module That just makes for unnecessary work when you need to change the list The m0delt data structure This structure is a container used to reduce the number of parameters that must be passed through the raytracing system It lives in myfz typedef struct modeltype camt listt listt listt modelt cam mats objs lgts The The The The camera structure head of the material list head of the visible obj list head of the light list Data structures the big picture struct modelitype listit objects listit lights listit materials camit cam struct listitype linkit tail 39 The data structures shown below Will all be defined in my WARNING Some elements of the definitions have been have been abbreviated and or assume the use of the typedef construct See the examples on other pages for these details struct cameraitype int pixeldim2 vecit viewipoint double worldidim2 struct linkitype f linkit head linkit next void item struct objectitype a void piiv J struct planeitype vecit normal vecit point void priv V struct linkitype linkit next void item struct objectitype void priv l J struct sphereit vecit center double radius void priv List management functions The characteristics of the lists used by the raytracer include the following 1 Newly created objects are always added to the end of the list 2 Objects are never deleted from the list 3 Lists are always processed sequentially from beginning to end 4 There is a need for three lists rnaterials Visible objects and lights 5 We want a single generic structure that can manage lists of the three different types The two structures shown below are sufficient There is a single instance of the listt structure for each list There is a single instance of the linkt structure for each element in each list typedef struct linktype linkt next next link in the list void item the item objectt lightt that this link owns linkt typedef struct listtype linkt head pointer to first object in list linkt tail pointer to last object in list listt List management functions For now our list management module to be constructed in lab will include three functions The listinit function is the constructor that used to create a new list Its mission is to 1 mallod a new listt structure 2 set the head and tail elements of the structure to NULL 3 return a pointer to the listt to the caller listt listinit void The listadd function must add the element pointed to by new to the list structure pointed to by list Its mission is to 1 mallod a new instance of linkt 2 add it to the tail of the list 3 ensure the next pointer of the new link is NULL and 4 ensure the next pointer of the linkt that used to be at the end of the list points to the new link t Two cases must be distinguished 1 the list is empty listgt head 2 NULL 2 the list is not empty listgt head I NULL void listadd l i s tt l i s t vo i d new 40 Deleting a list The listdel function This function should process the entire list For each link in the list it should 1 invoke the free function to free the item the link owns and then 2 it should free the linkt Care must be taken not to reference a linkt after it has been freed When all links and items are free the list header itself should be freed void listdel listt list 41 Processing a list This code segment shows a how to define an arbitrary structure that might be managed by the list a how to ask list init to create a new list a how to process the list from head to tail typedef struct entitytype char enamel6 int eid et listt elist linkt elink elist listinit Load the list loadmylistelist Now traverse the list printing attibutes of the elements elink elist gthead while elink 1 NULL eloc et elink gtitem printfquots d nquot eloc gtename eloc gteid elink elink gtnext 42 The main function A properly designed and constructed program is necessarily modular in nature Modularity is somewhat automatically enforced in 0 0 languages but new C programmers often revert to an ugly pack it all into one main function approach To discourage this in the raytracing program deductions Will be made for 1 Functions that are too long greater than 30 lines 2 Nesting of code greater than 2 deep NO nested loops 3 Exception to 2 Its OK to have an if inside a loop 4 Lines that are too long greater than 72 characters 43 The main function Here is the main function for the nal version of the ray tracer mainc include quotray hquot int main int argc char argv camt cam modelt model Load and dump the model model modelinitstdin modeldumpstderr model Raytrace the image imagecreatemodel return0 44 The generic object structure Even though C is technically not an Object Oriented language it is possible to employ mechanisms that emulate both the inheritence and polymorphism found in true Object Oriented languages The objectt structure serves as the generic base class from which the esoteric objects such as planes or spheres are derived As such it carries only the attributes that are common to the all derived objects Esoteric attributes of a plane are carried by a planet structure Esoteric attributes of a sphere are carried by a spheret structure The priv pointer of the objectt provides a link to the planet or spheret and is thus declared as void Polymorphic behavior is achieved by the use of function pointers embedded in the objectt or its subordinate esoterics These can be initialized to point to functions that provide a default behavior but may be overridden as needed When an esoteric object such as a tiled plane must substitute its own method Fields shown in blue are required for the first version of the ray tracer typedef struct objecttype int cookie char objnameNAMELEN leftwall centersphere char objtypeNAMELEN plane sphere double hitsvect base vect dir struct objecttype Finds ifwhere ray hits object void dumperFILE struct objecttype Prints object attributes Surface reflectivity data materialt mat Primary color of the object void priv Pointer to type dependent data vect hitloc Last hit point vect normal Normal at last hit point objectt 45 Declaration of derived object types The esoteric characteristics of specific object types must be canied by structures that are specific to the object type being described The pn v pointer of the base class objectt is used to connect the generic instance to the esoteric instance This connection is automatic and invisible in a true 00 language but is manual and visible in C Notice that the process of refinement or specialization can continue over multiple levels The priv pointer of the plane structure may point to an fplane bounded rectangular plane structure This structure carries the attributes of an infinite unbounded plane typedef struct planetype vect normal vector perpendicular to plane vect point point on the plane double ndotq dot product of normal and point void priv Data for specialized types planet Sphere typedef struct spheretype vect center double radius spheret 46 Loading the model description Forthescenespec icauon material object and light data may be intermixed the camera definition may appear anywhere materials must be defined before being referenced in an object definition attributes may appear in any order missing attributes must be set to zero camera caml pixeldim 640 480 worlddim 8 6 viewpoint 4 3 6 material green diffuse O l O ambient O 5 O plane leftwall normal 3 O 02 point 0 O 0 material green plane rightwall material green point 8 O 0 normal 3 O 02 47 The m0delinit function This function be contained in the source module modelc It controls the loading of camera material object and light definitions When it completes the cam pointer must point to a complete camit structure and material object and light definitions specified in the input file will have been read and for each material object or light definition in the file a new structure of type materialt objectt or lightt must reside on the appropriate list If the input file contains the definition of three planes three 0bjectt s must be on the objs list typedef struct modeltype camt cam The camera structure listt mats The head of the material list listt objs The head of the visible obj list listt lgts The head of the light list modelt 48 Implementing the m0delinitfuncti0n Specifically it must malloc the modelt structure and set it to zero call listinit three times to set up the material object and light lists call an internal modelload function to load the model data and then return the address of the modelt structure Init model data modelt modelinit FILE in modelt model mallocsizeofmodelt assert model 1 NULL memset model 0 sizeofmodelt model gtcookie MODCOOKIE Create and initialize material structure list model gtmats listinit assert model gtmats 1 NULL Step one is to create the lists This step READS NO INPUT DATA Create and initialize visible object structure list Step two is to read and store the model data read in the camera materials objects lights modelloadin model return model 49 The design of the model loader The model loader operates in a way similar to but not exactly like the CPSC 101 parser In fact the model loader itself is simpler than the CPSC 101 parser because it depends upon entity speci c constructors to create camera object light and material structures and read and store attribute data The model loader like the CPSC 101 parser relies upon a table lookup strategy in which the lookup table is defined as shown below static char entities quotcameraquot quotmaterialquot quotplanequot I quotspherequot ll II I quotspotlightquot define NU39MENTITIES sizeof entities sizeof entities O The m0delload function static void modelload FILE in modelt model char entitynameNAMELEN int count memsetentityname O sizeofentityname Here entityname should be one of quotmaterialquot quotlightquot quotplanequot quotcameraquot etc count quotsquot entityname fscanfin while count 1 lookup entity name in entities table invoke entity specific initializer camerainit materialinit planeinit lightinit sphereinit count fscanfin quot0 u as entityname The modeldump function This function just drives the process of producing a nicely formatted version of the contents of the material list the object list and the light list The entity type specific functions shown are responsible for the details dump model data void modeldump FILE out modelt model cameradumpout model gtcam materialdumpout model objectdumpout model lightdumpout model Material de nitions Each generic object must be associated with one mterialtype which defines the way the surface of the object interacts with light in the scene At the simplest level the material definition can be thought of as specifying the color of the object in drgbt r g 17 units typedef st ruct materialtype int char drgbt drgbt drgbt cookie ID of a materialt nameNAMELEN lightblue for example ambient Reflectivity for materials diffuse specular materialt There are three components to the light interaction model ambient specificies how the object re ects light that is present in the scene but is not emanating from any particular light source dif tse specifies how the object re ects light that does emanate from specific light sources specular 7 specifies the degree to Which the object acts like a mirror incoming light is precisely re ected instead of being diffused with the angle of incidence being equal to the angle of re ection It is possible to create models that are physically unrealizable We can define an object that re ects ambient light as red and diffuse light as green But no physical object exists that operates in such a way Creating a new material entity Material definitions define the re ectivity and hence the color of Visible objects Create a new material description void materialinit FILE in modelt model int attrmax materialt mat char attrnameNAMELEN int count malloc and initialize a material structure read material name lightblue etc read and verify read attribute name while attribute read successfully and attrname0 is not materialattrloadin mat attrname read attribute name verify was found add the material structure to the material list Loading material attributes Legal attribute names are ambient di use and specular At least one attribute must be specified Each attribute has three values the red green and blue re ectivity static int materialattrload FILE in materialt mat material to be filled in char attrname int ndx ndx lookup attrname in attribute name table assertndx gt 0 if ndX 0 read ambient values else if else return 0 The mteriaLsearchO function This function must search the list of materials looking for the color specified in the name parameter materialt materialsearch modelt model char name eg orange materialt mat for each mat in the model gtmats list if mat gtname matches name retummat retumNULL Pointers to functions Pointer variables may also hold the address of a function and be used to invoke the function indirectly class215examples gt gcc p32c class215examples gt cat p32c p32c include ltstdiohgt int adder int a int b returna b int main int ptrfint int declare pointer to function int sum ptrf adder point it to adder note no amp is needed but it doesn t hurt sum ptrf3 4 invoke it printfquotsum d nquot sum returnO class215examples gt aout sum 7 class215examples gt Function pointers as doityourself polymorphism Recall the the objectt structure containes a function pointers typedef struct objecttype int cookie char objnameNAMELEN leftwall centersphere char objtypeNAMELEN plane sphere double hitsvect base vect dir struct objecttype Hits function void dumperFILE struct objecttype void priv sub object planet The hits and dumper pointers must be set in at initialization time The planeinit function must set these pointers as follows These pointers allow the object to behave in a way that is called polymorphically in an 0 0 language obj gthits planehits obj gtdumper planedump All of the hits functions have the same parameters double planehits vect base Start point of ray vect dir MUST be unit vector objectt obj Candidate object Invoking a hits function dist obj gthitsraybase raydir obj Function pointers as a mechanism for simplifying model loading There are a number of possible ways to control the loading of model data The most straightforward way is if strcmpentitytype quotcameraquot 0 camerainitin model 0 else if strcmpentitytype quotmaterialquot 0 materialinitin model 0 else if strcmpentitytype quotplanequot 0 planeinitin model 0 else if or ndx tablelookupentities NUMENTITIES entitytype assert ndx gt 0 switch ndx case 0 camerainitin model 0 break case 1 materialinitin model 0 break case 2 A table driven approach A first cut at an alternative data driven approach might consist of two tables The names of the entities are kept in one Pointers to initialization functions are kept in another Our friend tablelookup is used to search the name table static char items quotcameraquot quotmaterialquot quotplanequot I quotlightquot I quottiledplanequot quotspherequot define NUMITEMS sizeofitems sizeofchar static void loaders FILE in modelt model int max void camerainit materialinit void planeinit void lightinit void tplaneinit void sphereinit static inline void modelitemload FILE in modelt model char itemtype int ndx ndx tablelookupitems NUMITEMS itemtype assertndx gt 0 loadersndx in model 0 return 60 A re nement to the table driven approach Note the the table driven approach works only if the two tables are kept quotin syncquot The address of each entity initializer function must be in the corresponding position to the entity name We can mitigate the problem somewhat by creating a structure that contains both the address of the entity name string and the funcuonthatloadsit typedef st ruct inittype char entityname void loader FILE modelt int initt static initt items quotcameraquot void camerainit quotmaterialquot materialinit quotplanequot void planeinit quotlightquot void lightinit quottiledplanequot void tplaneinit quotspherequot void sphereinit define NUMITEMS sizeof items sizeof items 0 If we do this the indirect invocation mechanism remains more or less the same but note that the newly structured table can no longer be used with the original tablelookup static inline void modelitemload FILE in modelt model char entitytype int ndx ndx tablelookupiitems NUMITEMS entitytype assertndx gt 0 items ndx loader in model 0 return 61 The new tablelookupi function static inline int tablelookupi initt inittab entity initializer table int count number of entities char target candidate entity name int i initt ie inittab int rc l for i O i lt count i if strcmptarget ie gtentityname 0 returni ie 1 returnrc 62 The planeinit function The planeinit function has several responsibilities that are described below In a true object oriented language the planeitype will be a specialization of the objectitype and when a new instance of planeitype is created the constructors for BOTH the plane and object classes will be AUTOMATICALLY invoked in top down order When simulating inheritance with C we must a explictly invoke the constructors or each element in the hierarchy and a link the structures that represent them together In both C and C this will implicitly require that generic attributes appear rst in the model definition obj ectt planeinit FILE in modelt model int attrmax planet pln obj ectt obj invoke objectinit which will malloc the objectit structure and initalize read the the objectiname leftwall Pm esse l 13V process the material attribute Objecumt p Processed by l modeliinit material green nOFmal l O O 39 2 Processed by A pOlnt O O O planeiinlt create a planet structure itself load the specialized attributes of the planeit normal and point set the priv pointer in the objectt to point to the planet initialize the hits and dumper function pointers in the objectt store the object type name plane in the objectt structure 63 The objectinit function objectt objectinit FILE in modelt model objectt obj materialt mat char bufNAMELEN int count Create a new object structure and zero it obj mallocsizeofobjectt assertobj 1 NULL memsetobj O sizeofobjectt obj gtcookie OBJCOOKIE Read the descriptive name of the object leftwall centersphere etc count fscanfin quotsquot obj gtobjname assertcount 1 Consume the delimiter v First attribute must be material count fscanfin buf V squot assertbuf0 I count fscanfin quotsquot buf assertcount count strcmpbuf quotmaterialquot assertcount 0 count fscanfin quotsquot buf assertcount mat materialsearchmodel buf assertmat 1 NULL obj gtmat mat listaddmodel gtobjs void obj returnobj 64 Producing a formatted dump of the object list void obj ectdump FILE out modelt model For each objectt in the modelgtobjs list print the object39s objtype and objmzme print the word material and the name of the object39s associated material plane rightwall material yellow polymorphically ask the object to print the type specfic attributes For the plane type object objgtdumper will point to the actual function planedump obj gtdumperout obj the planedump function will be responsible for printing the specific attributes of a plane normal 1 O 02 point 0 O O 65 Type speci c dumpers Type specific dumpers know What their own attributes are so they just print attribute names and values void planedump FILE out obj ectt obj planet pln Recover the pln pointer using the priv pointer in the objectt Print attribute names and values normal l 0 point 7 O OO 00 00 ON 66 A general attribute parser After writing parsers for the camera material and plane the typical programmer will find repeatedly rewriting almost the same code tiresome and tedious and will seek a better way It is not bad that the ad hoc approach was used initially The very use of the ad hoc helps the programmer see common aspects of the problem and develop a more general solution As usual we try to make our solution data driven to the extent possible To build a general parser we will build upon the capability of the tablelookup mechanism but replace the old table of attribute names with new tables that contain not only the attribute name but also su icient information to allow the general parser to load the values Specifically for each attribute we need the following information How many values must be loaded eg 2 for pixeldim 3 for viewpoint How many bytes of storage does each value occupy 4 for pixeldim 8 for viewpoint What format string should be used to read a value d for pixeldim lf for viewpoint Where should the first value be stored Here we make use of the fact that we know adjacent array elements and members of a structure such as a vect are stored in adjacent memory locations For the vect if the location of the x component is memory address a and then the y component is at location a8 and the z at location a16 The struct ppanntype Therefore each entity will employ a table in which each attribute is represented by a structure of the following type the parse parameter structure typedef struct pparmtype char attrname Attribute name int numvals Number of attribute values int valsize Size of attribute in bytes char fmtstr Format string to use void loc Where to store lst attr value pparmt 67 Building tables of attribute descriptors The address of where to store the first attribute value must be For the camera entity We build the structure as follows lled in after the camerait is malloc39d static pparmt camparse quotpixeldimquot 2 sizeofint quotdquot O quotworlddimquot 2 sizeof double quot fquot O quotviewpointquot 3 sizeofdouble quotlfquot 0 define NUMATTRS sizeofcamparse sizeof pparmt Items to note camparse is an array of three elements each element is a structure of type pparmt initializers should be enclosed in the location Where the first attribute value should be stored will live in the camt structure that is eventually allocated with mallod These values can39t be set until after the camt is malloc d For the other entitities such as the material entity the structure is analogous static pparmt matparse quotambientquot 3 sizeofdouble quotlfquot 0 quotdiffusequot 3 sizeofdouble quotlfquot 0 define NUMATTRS sizeofmatparse sizeofpparmt 68 The interface to the genera attribute parser This version of camerainit demonstrates how the use of the general parser can reduce your workload void camerainit FILE in modelt model int attrmax malloc the camera structure camt cam mallocsizeofcamt assertcam 1 NULL cam gtcookie CAMCOOKIE Read camera name and quotsquot cam gtname buf Store locations where attribute data should be read fscanfin fscanfin assertbufO o quot68quot ampcam gtpixeldim ampcam gtworlddim ampcam gtviewpoint camparse0loc camparselloc camparse2loc Invoke the parser mask 0 parserin camparse NUMATTRS verify required attributes read assertmas 7 remember address of camera structure model gtcam cam 69 Generalized attribute parser It returns a bit mask in which each possible attribute is represented by a bit on exit the attributes that have been found will have their bit l int parser FILE in pparmt pct parser control table int numattrs number of legal attributes int attrmax Quit after this many attrs if not 0 char attrnameNAMELEN int attrcount O number of attribs loaded int mask O loaded attrib bit mask int ndx ndx of this attrib in pct One trip is made through this loop for every attribute processed Exit from the loop is triggered by or if the maximum number of attributes is set when the maximum number have been processed fscanfin while strlenattrname Process one attribute quotsquot attrname ampamp attrnameO 3939 ndx parserloadattrin pct numattrs attrname mask 1 ltlt ndx attrcount See if its quitting time if attrmax ampamp attrcount attrmax break attrname O fscanfin quotsquot attrname if attrmax l attrcount assertattrnameO returnmask Loading the values of a single attribute static int parserloadattr FILE in pparmt pct parser control table int numattrs number of legal attributes char attrname attribute name pparmt pce Entry corresp to this attribute int count O unsigned char loc where to store value have to double work use unsigned char for pointer int ndx arithmetic to work correctly int i tablelookupp is an updated version of tablelookup that takes parse control table pointer as input ndx tablelookupppct numattrs attrname assertndx gt 0 Point to the proper entry in the table pce pct ndx or pce amppctndx pce gtloc points to where the first value must go loc unsigned char pce gtloc Attributes may have different numbers of attribute values for example the viewpoint has three but the pixeldim only has 2 values Each iteration consumes one value for i O i lt pce gtnumvals i count fscanfin pce gtfmtstr loc work double loc fprintfstderr quots lf nquot pce gtattrname work loc pce gtvalsize point to next spot assertcount pce gtnumvals returnndx Exercise Design a generic tableilookup function Avoiding parsing altogether In building programs it39s often useful to employ temporary skeletal modules that facilitate the building and testing of other components but are ultimately thrown away at the end of the project For example if this were a team project it would be desirable for the ray tracing team to press on in parallel With the parsing team39s activities instead of haVing to wait on a functional parser We can View this exerise as transforming or model specification language to C In fact the C version looks quite similar to the target language modelstatc This module provides a statically defined model that can be used to test the raytracing system include quotrayhquot materialt matl cookie MATCOOKIE name quotgreenquot ambient 0 5 O materialt mat2 cookie MATCOOKIE name quotyellowquot ambient 6 5 O materialt mat3 cookie MATCOOKIE name quotgrayquot ambient 4 4 4 Now we define the plane structures Again the definitions are quite consistent with the target language planet planel normal 3 O 1 point 0 o o planet plane2 normal 3 O 1 point 8 o o planet plane3 normal 0 l 0 point 0 o o The object structure definitions combine elements of the original input language but more re ect the actions of the program objectt objectl cookie OBJCOOKIE objname quotleftwallquot hits planehits priv void ampplanel mat ampmatl objectt object2 cookie OBJCOOKIE objname quotrightwallquot hits planehits priv void ampplane2 mat ampmat2 objectt object3 cookie OBJCOOKIE objname quotfloorquot hits planehits priv void ampplane3 mat ampmat3 Linking the model together The last and ugliest piece of the puzzle is to handcraft the object list and put it in the model structure Note that the material list is not necessary because there is on material dumper and no material find needed linkt linkl next NULL item void ampobject2 linkt link2 next amplinkl item void ampobjectl linkt link3 next amplink2 item void ampobject3 listt listl head amplink3 tail amplinkl modelt model objs amplistl modelt modelinit FILE in returnampmodel Hit functions Given the viewpoint ray direction and a pointer to an objectt the mission of a hit function is to determine if the ray hits the object If it does the hit point and the normal vector at the hitpoint should be stored in the objectt Hit point H Screen Viewpoint V Given V D and an object structure 0 the mission of a hit function is to determine if a ray based at V traveling in direction D hits 0 All points on the ray may be expressed as a function of a single parameter t Where t distance along the ray from the viewpoint The set of all points on the ray is thus VtD br aolttltm DULVHPW mHHVH HVmD Ray direction Distance to hit point Location of hit point Prototype for the hits functions To determine if a ray hits an object you must add a hitsobjtype function to your spherec planec etc modules These modules should also contain the loading and dumping code for the specific object type A sample prototype is shown below double planehits vect base vec t dir objectt obj Pointers to the hits39 function obj gthits the x y z coords of origin of the ray unit vector in the x y z dir of the ray the object to be tested for the hit should be stored in the object structure at the time it is created hitsplane Genera Quadric Surfaces These surfaces are so named because the variables x y and z take on at most the power of two The general equation for the quadric is given below Ax2By2sznyExzFyzGxHyIzJ We will start with two of the simpler ones The sphere x2 yz Z2 r2 The plane Gx Hy Iz J where o the plane normal N is G H I and o J is chosen so that the plane passes through the specified point Q Quadric surfaces are nice in a raytracing environment because the intersection of a ray with the surface may always be found by solVing at worst a quadratic equation Determining if a ray hits a plane This basic strategy will be used in all bits functions 0 Assume that Vrepresents the start of the ray and D is a unit vector in its direction 1 Derive an equation for an arbitrary point P on the surface of the object 2 Recall that all points on the ray are expressed as V D 3 Substitute V D for P in the equation derived in 1 4 Attempt to solve the equation for t 5 If a solution I can be found then H V h D A plane in three dimensional space is defined by two parameters A normal vector N 1 my nz A point Q qx qy qz through which the plane passes A point P px py pz is on the plane if and only if N d0 P Q 0 because if the two points P Q lie in the plane then the vector from one to the other P Q also lies in the plane and thus it is necessarily perpendicular to the plane39s normal We can rearrange this expression to get NdotPNdotQ0 NdotPNd0tQ 1 Note that in this equation N and Q are known attributes of the plane and P is the unknown Recall that the the location of any points on a ray based at V with direction D is given by VtD Therefore we may replace the P in equation 1 by V tD and get Nd0tVtDNd0tQ 2 Some algebraic simplification yields allow us to solve this for t Nd0tV tD Nd0tQ 2 NdotVNd0ttDNd0tQ NdottD Nd0tQNd0tV NdotD NdotQ Nd0t V th NdotQ Nd0tVNd0tD 3 The location of the hitpoint that should be stored in the objectt is thus H V thD The normal at the hitpoint which must also be saved in the objectt is just N Unlike other quadric surfaces there is only a single point at which a ray intercepts a plane Therfore unlike equations we will see later this one is not quadratic There are some special cases we must consider 1 N d0l D 0 In this case the direction of the ray is perpendicular to the normal to the plane This means the ray is parallel to the plane Either the ray lies in the plane or misses the plane entirely We will always consider this case a miss and return 1 Attempting to diVide by 0 will cause your program to either fault and die or return a meaningless value 2 h lt 0 In this case the hit lies behind the Viewpoint rather than in the direction of the screen This should also be considered a miss and I should be returned 3 The hit lies on the View point side of the screen H h hy hz if hz gt 0 the hit is on the wrong side and 1 should be returned Determining if a ray hits a sphere Assume the following V viewpoint or start of the ray D a unit vector in the direction the ray is traveling C 2 center of the sphere I radius of the sphere The arithmetic is much simpler if the center of the sphere is at the origin So we start by moving it there To do so we must make a compensating adjustment to the base of the ray C C C 0 0 0 new center ofsphere V V C new base ofray D does not change A point P on the sphere whose center is 0 0 0 necessarily satisfies the following equation px2py2pz2 r2 1 All points on the ray may be expressed in the form PV tDv xtdx v ytdyl v ztdz 2 where t is the Euclidean distance from V to P Thus we need to find a value of t which yields a point that satisfies the two equations To do that we take the x y z coordinates from equation 2 and plug them into equation 1 We will show that this leads to a quadratic equation in t which can be solved via the quadratic formula v tsz v39y dyf v dzf r2 Expanding this expression by squaring the three binomials yields vs 2mm 12 d5 v32 2w dy df l x l x x l l 2 2 2 2 fv z 2tv z dz t dz r Next we collect the terms associatedWith common powers of t 2 A 5 vx vy vz 2tvxdx v ydy v zdz 2dxjj dy2 df r2 Now we reorder terms as decreasing power represent dot products r f k D szDz2 2 V dotD z V39dotV r2 0 l I i We now make the notational changes of t and note that all three of the parenthesized tri nomials I v a D dotD quot I b 2 V dot D c V dot V r2 to obtain the following equation atz btc0 whose solution is the standard form of the quadratic formula h b sqrtb2 4ac Recall that quadratic equations may have 0 1 or 2 real roots depending upon whether the discrimant 2 b 4ac is negative zero or positive These three cases have the following physical implications negative gt ray doesn39t hit the sphere zero gt ray is tangent to the sphere hitting it at one point we will consider this a miss positive gt ray does hit the sphere and would pass through its interior this is the only case we consider a hit Furthermore the two values of t are the distances from the base of the ray to the points s of contact with the sphere We always seek the smaller of the two values since we seek to find the entry wound not the exit wound Therefore the hitssphere function should return th b sqrtb2 4ac otherwise Determining the coordinates of the hit point on a sphere The hitssphere function should also fill in the coordinates of the hit in the objt structure The x y z coordinates are computed as follows H V th D Important items to note are The actual base of the ray V and not the translated base V must be used The vector D must be a unit vector in the direction of the ray Determining the surface normal at the hit point The normal at any point P on the surface of a sphere is a vector from the center to the point Thus N P C note thathill be a unit vector ltgt r 1 Therefore a unit normal may be constructed as follows NuHCHC Creating an image We continue to strive to build simple easy to grasp components Obviously this could be done by massively nesting loops and building functions 100 lines long Even some faculty and professional programmers Will do it this way But if you do it my way you avoid the possibility that one day you Will be recreated as a VooDoo doll by those charged With trying to understand and maintain What you wrote This function is the driver for the raytracing procedure void imagecreate modelt model int y camt cam model gtcam Fire rays through each pixel in the window for y O y lt cam gtpixeldiml y Create ppm image makerowmodel y camerawrit eimage mode 1 gt cam Processing a row of pixels The most common way to mess this up is to forget which element of the pixeldim array represents the horizontal size and which represents the vertical size static inline void makerow modelt model int y int x camt cam model gtcam for x O x lt cam gtpixeldim0 x makepixelmodel x y Building a pixel This function is called for each pixel in the image Eventually we will try to minimze the jaggies by building a loop in here in which we randomize the ray direction and average the computed pixel values static inline void makepixel modelt model int x int y vect raydir drgbt dpix 00 00 00 camt cam model gtcam int i This function was written previously cameragetdircam x y ampraydir ifdef DBGPIX fprintfstderr quotnPIX 4d 4d quot y x endif The raytrace function determines the pixel color in drgb units The last two parameters are used ONLY in the case of specular bouncing rays which we are not doing yet raytracemodel ampcam gtviewpoint ampraydir ampdpix 00 NULL This function must convert the pixel value from drgbt 00 10 to irgbt O 255 and to store it in the upside down location in the pixmap camerasetpixcam x y ampdpix return The rayitraceo function This function traces a single ray and returns the composite void raytrace modelt model vect base vect dir drgbt dpix double totaldist objectt lasthit objectt closest double drgbt mindist thisray I location of viewer or previous hit unit vector in direction of object pixel distance ray has traveled so far intensity of the light it encounters return location most recently hit object 00 00 00 Ask findcl0sest0bject t0 set the cl0sest painter If it returns an abject painter ifdef DBGHIT fprintfstderr endif quot 12s HIT5llf 5llf closest gtobjname closest gthitlocx closest gthitlocz capy the abject s ambient reflectivity t0 thisray scale the values 0f thisray by I distance t0 the cl0sest abject add the value 0f thisray t0 pix ifdef DBGDRGB fprintfstderr endif quot 12s DRGB521f 521f 5llfquot closest gthitlocy 521fquot closest gtobjname pix gtr pix gtg pix gtb Additional notes It is useful to add some inline functions for copying scaling and performing component Wise multiplication of drgbt s to rayfunsh The use of thisray may seem unnecessary here That39s because it is unnecessary here But if you don39t use it you Will almost certainly encounter problems in antialiasing Debugging output The raytracer is sufficiently complicated that debugging output may be required for problem resolution The C compiler preprocessor opp permits us to conditionally compile or not compile statements into a program If we include the line de f ine DBGDRGB in the source code then this statement will be compiled and produce debugging output But if we comment it out the debug output will not be produced ifdef DBGDRGB fprintfstderr quot lZs DRGB521f 521f 521fquot closest gtobjname pix gtr pix gtg pix gtb endif Instead of haVing to comment inout the definition the C compiler allows you to define a symbol on the command line gcc c g DDBGDRGB raytracec A make le for a multimodule program The Unix make program is a handy utility that can be used to build things ranging from programs to documents Elements of significance include targets labels that appear in column 1 and are followed by a the character 2 The make command can take a target as an operand as in make ray dependencies are files that are enumerated following the name of the target If any dependency is newer than the target the target will be rebuilt rules are specified in lines following the target and specify the procedure for building the target Rules must start with a tab character In the example below the tab has been expanded as spaces but you may not enter spaces The following make le can be used build the executable ray tracer named ray assuming that it requires only the 0 files enumerated in the command aout mainlo modelo camerao listo materialo planeo objecto sphereo vectorh rayh rayfunsh rayhdrsh gcc Wall g 0 lm co lt gcc c Wall c g lt 2gt oerr cat err The target co is called a su ix rule It is telling make to use the commands that follow whenever it needs to make a 0 file from a c file There are a number of predefined macro based names the current target s full name a list of the target39s changed dependencies lt similar to but identifies a single file dependency and is used only in suffix rules the target file s name without a suffix Another handy macro based facility permits one to change prefixes on the y The macro o err says use the target name but change the o to err The same result effect may be obtained using err as is done in the subsequent cat command Using user written macros in make les The make le on the previous page is actually broken All of the 0 files depend on my and should be recompiled if my changes but this will not happen We could fix this by typing in a collection of other dependencies but the macro facility simplifies that Make macros are similar in spirit to Unix environment variables In fact environment variables can be accessed in make files via macro calls However it is typically the case that the macros are defined Within the make le Here is a makefile that is used to build a complete raytracer A macro is defined by using the syntax MACRO NAME macro value Many people use the convention of making names all capital but that is not required All of the 0 files necessary to build in are defined using the macro name RAYOBJ S The character at the end of all but the last line is the standard Unix contuation character The character at the start of a line turns the line into a comment A macro is invoked using the syntax MACRO NAME The result of the invocation is that the string MACRO NAME is replaced by the current value of the macro RAYOBJS mainlo modelo camerao listo materialo planeo objecto sphereo RAYHDRS vector h ray h rayfuns h rayhdrs h aout RAYOBJS gcc Wall g 0 lm RAYOBJS RAYHDRS makefile co lt gcc c Wall c g lt 2gt oerr cat err De nining debug control symbols in the make le Use the CFLAGS macro to enable precisely those debug aids that you need CFLAGS DDBGPIX DDBGHIT ray RAYOBJS gcc Wall 0 ray g RAYOBJS lm RAYOBJS INCLUDE makefile co lt gcc c Wall CFLAGS c g lt 2gt oerr cat err This code is in the make pixel function ifdef DBGPIX fprintfstderr quotnPIX 4d 4d quot y x endif This code is in the raytrace function ifdef DBGHIT fprintfstderr quot lZs HIT5llf 5llf 5llfquot closest gtobjname closest gthitlocx closest gthitlocy closest gthitlocz endif Because of how the n characters are used in the format string they work together to produce this useful output PIX 21 16 leftwall PIX 22 16 leftwall PIX 23 16 leftwall PIX 24 16 leftwall PIX 25 16 leftwall PIX 26 16 leftwall PIX 27 16 leftwall PIX 28 16 leftwall PIX 29 16 floor PIX 3O 16 floor PIX 31 16 floor PIX 32 16 floor PIX 33 16 floor PIX 34 16 floor PIX 35 16 rightwall PIX 36 16 rightwall PIX 37 16 rightwall PIX 38 16 rightwall PIX 39 16 rightwall PIX 4O 16 rightwall IIIIIIII 00O U IU IIJgtIJgtIJgt I 00 IIIIIII U IO 100000000 I U I ONONONU1U1U1U1HgtHgtWWWNNNNHHHH Ibwoooo xwoo xwoopboqpbwoooo xmw I OOOOOOOOOOOOOOI I I I l 30030313gtlOOOOOOIJgtO QOUJIJgt I 00 I oo mWKOU INOU IU IU IU IU IU IONU IKOWODIbO 5 Additions to the camera module The mission of camerasetpix is to convert a drgbt pixel encoding to an irgbt pixel encoding and store it in the pixmap void camerasetpix camt cam int x int y drgbt pix int row int offset i rgbt maploc assert cam gtcookie CAMCOOKIE scaleandclamp pix convert to range 0 255 ifdef DBGIRGB fprintf stderr quot IRGB50lf 50lf 50lfquot pix gtr pix gtg pix gtb endif Now it is necessary to set the pointer maploc Recall from CPSC 101 that the pixel at location row col in the image had o set 2 row numcols col 1 in the pixmap That obviously remains true here ifdef DBGOFFSET fprintf stderr quotOFF 7dquot offset endif It is also true that it corresponds to col Unfortunately y doesn39t exactly correspond to row If you simply assume that it does your image Will come out upside down This occurs because in our coordinate system y 0 corresponds to the bottom row of the screen In a ppm file the first row of pixels in the file appears as the top row of the image Thus if y 0 the value of row should be camgtpixeldim1 I the last row of the pixmap and if y camgtpixeldim1 I the top row of the screen row should be 0 the first row of the pixmap Creating the image Some of the code from the write ppmimage from you 101 project can be recycled here void camerawriteimage camt cam assertcam gtcookie CAMCOOKIE Write the ppm header file remember width befare height Write the entire binary pixmap t0 stdaut with a single call tafwrite Polymorphism II We have already discussed how the hits and dumper functions provide polymorphic bahavior in the object quotclassquot Each specialization plane sphere must provide its own characteristic function There is no quotdefaultquot hits function A failure to provide a hits function will cause an instant segfault When the object is to be tested for a ray intersection This bad behavior could be avoided by creating a function double obj ecthits vect base the x y z coords of origin of the ray vect dir unit vector in the x y z dir of the ray objectt obj the object to be tested for the hit return l in objectc and in the objectinit funciton setting the object39s hits function pointer to point to this default function Then planeinits could override the default behavior by storing an pointer to planehits in objgthits But an object that quotforgotquot to override wouldn39t crash the raytracer but it would be invisible The getamb function In other cases most specializations may want to use the default function This will be the case with the material color retrieval function getambO Recall that in the ambient only raytracer the last steps of the operation are add mindist to totaldist set intensity to the ambient re ectivity of closest object divide intensity by totaldist The first inclination is to implement the small amount of code in step 2 in the obvious way this pixr closestgtmat gtambient r this pixg closestgtmatgtambient g this pixb closestgtmatgtambientb or pixcopyampclosestgtmat gtambient ampthispix However that approach would make it not easy to override the default behavior Thus a better approach is to replace the three lines above by closestgtgetamb obj ampthispixy During the objectinit object constructor sets the getambO function pointer to the default getamb function which contains the three lines of code we just replaced While this adds a slight bit of run time overhead it also provides us with an easy hook with which we may override the default getamb with a custom routine We will see an example of this with the tiled plane object 100 Modi cations to the 0bjectt structure The getamb element of the objt structure is a pointer to a void function which is passed pointers to the object structure and the intensity vector typedef struct objecttype int cookie char objnameNAMELEN leftwall centersphere char objtypeNAMELEN plane sphere double hitsvect basevect dir struct objecttype Hits function void dumperFILE struct objecttype Optional plugins for procedural reflectivity void getamb struct objecttype drgbt void getdiff struct objecttype drgbt void getspec struct objecttype drgbt Modi cations to 0bjectinit In the objectinit function it is necessary to initialize the pointers so that the desired default behavior will be provided obj gtgetamb materialgetamb obj gtgetdiff materialgetdiff obj gtgetspec materialgetspec 101 Implementation of the default getter functions It is then necessary to implement the default functions in the materia1c module This material getamb and material getspec are analogous void materialgetamb objectt obj drgbt dest materialt mat obj gtmat assertobj gtcookie OBJCOOKIE assertmat gtcookie MATCOOKIE pixcopyampmatambient dest 102 Tiled planes The tiled plane object is commonly found in ray tracing models Wewilluseit 39 39 quot 39 39 39 39 l quot39 39 JJInObject Oriented mrminology the objectj erucmre is called a base ch55 The base class is at the top or root of a class hierarchy The plane and sphere are specialimt39wns of the object and are called derived ohms 39 L quotJquot l l H39 laieiuuhei 39 39 Lhe pkmeit object plane sphere rplanej ppmth 103 The tilediplane model object description The tiled plane requires two attributes beyond those of the regular plane The dimensions specify the size of the tiling in world coordinates The altmaten al specifies the color of the alternate tiles tiledplane floor P m wdbv objeC11nit material white normal 0 1 o Processedby point 0 0 0 dlmen81or1 20 3 O Processed by altmaterlal green wane mi A specialization always requires that some aspect of the behavior of the parent class be modified If no modifications at all were required we could just use the base class A specialization never requires that that all aspects of the parent39s behaVior be overridden In that case it would be appropriate to create a new class When a new tiled plane is created three structures must be allocated and linked together The objectiinitO function is called by planeiinitO lt mallocs the objectit The planeiinitO function is called by tplaneiinitO It mallocs the planet and sets the priv pointer in the objectit tplane t The tplaneiinitO function is called by the model loader It mallocs the tplanet and sets the priv pointer in the planeit 104 The tplanet structure and the tplanejnito function The structure is shown below and it must be filled in by tplanejni from the input data Tiled plane descendant of plane typedef struct tplanetype char matname NAMELEN materialt background background color double dimension2 dimension of tiles tplanet The dimension parameter specifies the X Z dimensions of a single tile in world coordinates The altmaterial is the name of the material used in alternate tiles The tplaneinit function must ask nuzteriaLsearchO to lookup the corresponding materialit tiledplane floor material white normal 0 1 0 I Processedby point 0 0 0 dimension 20 30 I Processedby altmaterial green mkmq m 105 The tplaneinit function obj ectt tplaneinit FILE in modelt model The function is called from the model loaders Its missions are to invoke planeinit to create the planet and objectt structures malloc a tplanet and set the priv pointer in the planet structure parse the parameter data set the getamb pointer in the objectt to point to the tpkmeamb function set the dumper pointer in the objectt to point to tplanedump set objtype field in the objectt to quottiled planequot The tpkmeinit function need not override the hits function provided planeinit The tplanedump function static void tpdump FILE out obj ectt obj o invoke the planedump function a dump the tplane attributes 106 The tplaneamb function This is the function that actually gives the tplane its characteristic behavior void tplaneamb obj ectt obj drgbt value int foreground tplaneforegroundobj if foreground material getamb obj value else copy ambient re ectivity from background material 107 The tplaneforegroundo function void tplaneforeground obj ectt obj Compute xndx tile index of the hitpoint in the x direction Compute zndx tile index of the hitpoint in the z direction 13796de zndx is an even number returnI else return0 A tile index is computed by adding 10000 to the X or z coordinate of the hitpoint and dividing by the X or z dimension of the tile 108 Procedural mow the location of the hit point on the sumoe of the object There are 39 39 39 39 fox incorporating pmoedumlly shaded surfaces into my moed images Implementation of procedural shaders Construction of such shaders is facilitated by the use of both inheritance and polymorphism within a C language framework The procedurally shaded plane is an lightweight refinement of the planet typedef struct pplanetype int shader pplanet The distinction between a standard plane and a procedurally shaded plane is made at object initialization time by the pplaneinit function when it establishes a single function pointer for ambient only images that provides the polymorphic behavior That function pointer is taken from a table of pointers to programmer provided functions are contained in the module pplanec and perform the procedural shading These procedural shading functions are passed pointers to the objectt structure and to the dgrbt intensity vector whose ng 17 components are filled in procedurally Here is an example in which there are three possible shaders static void pplaneshaders objectt obj drgbt value ppl ane Oamb ppl ane lamb pplane2amb define NUMSHADERS sizeof pplaneshaders sizeof void Note that 1 The number of elements in the array is not explicitly specified 2 The value N UMSHADERS can be computed by dividing the size of the table by the size of a single pointer 110 The index of the shader to be used is supplied in the model description as shown below pplane floor material gray normal 0 l 0 point 0 O 8 shader O pplane backwall material gray normal 0 O 1 point 4 3 8 shader 1 H1 The pplaneinit function As shown below the pplaneinit function simply invokes the planeinit function to construct the object and then overrides the default getamb function replacing it With the shader function Whose index is provided in the model description files obj ectt pplaneinit FILE in modelt model int attrmax pplanet ppln planet pln obj ectt obj The mysterious attrmaX l inkt l ink parameter nally gets to do int mask something planeinitin model 2 Somewhat crude mechanism for 1 ink mOde 1 gt019 S gtta l 1 retrieving the objectit pointer obj objectt link gtitem pln obj gtpriv ppln pplanet mallocsizeofpplanet pln gtpriv ppln pplaneparse0 loc ampppln gtshader mask parserin pplaneparse l attrmax assertmask strcpyobj gtobjtype quotpplanequot obj gtgetamb pplaneshaders ppln gtshader obj gtdumper pplanedump 112 Tiled shading T J 39 39 uoor 39 4v 4 39m a mmion of L J quot 39 39 H II I Fora haekwau ii for a sidewall it would be y and z void pplane07amb obj ectit obj drgb t Value The factor of 2 controls the width of the tiles The largerthe factor the smaller the tile The value of 1000 is known as Wesmll s hack for preventing an ugly double wide strip atthe origin 1000 gtambient value test for odd or even sum make pixel cyan int ix int iz ix 2 objegthitlocx 1000 iz 2 obj egthitlocz pixicopymobj egtmate if iz ix amp1 valueegtr 00 else valueegtb 00 make pixel yellow 113 Continuously modulated shading The image shown below is produced by a procedural shader that continously modulates the ambient re ectivity The modulation function is shown below A vector Vin the direction from the point de ning the plane location to the hitpoint is computed first Then the angle that the vector makes with the positiveX axis is computed Finally the red green and blue components are modulated using the function 1 cosw t f where the angular frequency w is 2 for all three colors and phase angles f are 0 2p 3 and 4p 3 respectively Different effects may be obmined by using different frequencies and phase angles for each color and itis also possible to combine continuous modulation with striping or tiling vecidi ff Sip gtpoint ampobj 7 gthitloc ampVec V1 vecx sqrtvecx vecx vecy vecy t1 acos V1 if vecy lt O tl2 NLPI 7 t1 1 cos2 t1 1 COS2 tl 2 MiPI 3 l COS2 tl 4 MiPI 3 valueigtr 7 7 7 lt m C a l v 0 H mom 114 Procedural sphera quot 39 a Hereisonefora sphere assert Obj rgtcook1e OBJJZOOKIE sph sphere objrgtpr1V7 Vecicopyampobjrgth1tloc accord Vecidlffampsphrgtcenter ampcoord accord Veciscale05 sphrgtrad1us accord amp rd v1 c ord oordx sqrtcoordx c o x coordy coordy 1 t1 1f coordy lt 30 1 2 r M PI 7 t1 destrgtr 1 1 cos2 t1 destrgtg 1 1 cos2 t1 2 MiPI 3 destrgtb 1 1 cos2 t1 4 MiPI 3 The cross product of two vectors Given two linearly independent not parallel vectors V vx vy vz W w w w The cross product sometimes called outer product is a vector which is orthogonal perpendicular to both of the original vectors VXWvyWZvzwy VZWXVXWZ VXWyvywx Notes The vector 0 1 0 is the negative y axis Therefore any vector that is perpendicular to it must lie in the y 0 plane The projection of the vector 1 1 1 onto the y 0 plane is the vector 1 0 1 The vector 1 0 1 is then perpendicular to this vector and lies in the y0 plane In a righthanded coordinate system XXYZ YXZX ZXXY Right thumb X forefinger 2 middle finger 116 The veccross function You Will add the following function to your vector collection Compute the outer product of two input vectors static inline void veccross vect vl Left input vector vect v2 Right input vector vect v3 Output vector 117 Projection Assume that Vand N are unit vectors The projection Q of Von N is shown in red It is a vector in the same direction as N but having length cosq Therefore QNd0tVN Now assume that N is a normal to a plane shown as a yellow line The projection P of Vonto the plane is shown in magenta and is given by V G where G is the vector shown in green Since G and Q have clearly have the same length but point in opposite directions G Q Therefore the projection of a vector V onto a plane with normal N is given by P VNdotVN or possibly vecdy vecscalevecd0tl V N V P In building your new linear algebra routines it is desirable to build upon existing ones where possible but extreme levels of nesting of function calls as shown here can complicate debugging project a vector onto a plane static inline void vecproj ect vect n plane normal vect v input vector vect w projected vector 118 Re ection Basic physics says The angle of incidence the angle the incoming ray makes With the normal at the hitpoint is equal to the angle of re ection vecreflect vect unitin unit vector in incoming direction of the ray vect unitnorm outward surface normal vect unitout unit vector in outgoing direction ray 5 N cos T N V N N dot U Let U Lmitin N unimorm Then U V 2 N cos T where Tis the angle between U andN cosT U dotN so UV2NUd0tN and V2NUd0tNU 119 Matrices Matrix operations are useful in transforming three dimensional coordinate systems in ways that make it easier to determine if and where an object is hit by a ray There are alternative approaches to creating a 3 x 3 matrix Probably the most obvious is double matrix 3 3 but we will build upon our vector type as follows typede f matrixtype vect row3 matt matt matrix To set the the element in the 3 d column of the middle row to fifteen do matrixrow 1 z 150 To add two rows of a matrix vect sum vecsumampmatrixrowl ampmatrixrow2 ampsum Suppose V and W are vectors and a is a scalar value A function F that maps three dimensional space to three dimensional space is a linear transformation if and only if FaV W aFV W forany choice ofa V andW Furthermore any linear transformation may be represented by multiplication of a vector by a matrix 120 Multiplication of a matrix times a vector The product of a 3 x 3 matrix with a 3 d column vector is a 3 d vector The multiplication rule is as follows product the dot product of the ith row of the matrix With the vector 10 10 00 10 10 10 10 00 X 00 10 00 00 10 20 20 The vecxformo function should multiply a vector by a matrix static inline void vecxform matt m input matrix vect vl vector to be transformed vect v2 output vector vect v3 avoid aliasing problems Perform the transform veccopyampv3 v2 121


Buy Material

Are you sure you want to buy this material for

25 Karma

Buy Material

BOOM! Enjoy Your Free Notes!

We've added these Notes to your profile, click here to view them now.


You're already Subscribed!

Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'

Why people love StudySoup

Bentley McCaw University of Florida

"I was shooting for a perfect 4.0 GPA this semester. Having StudySoup as a study aid was critical to helping me achieve my goal...and I nailed it!"

Amaris Trozzo George Washington University

"I made $350 in just two days after posting my first study guide."

Steve Martinelli UC Los Angeles

"There's no way I would have passed my Organic Chemistry class this semester without the notes and study guides I got from StudySoup."

Parker Thompson 500 Startups

"It's a great way for students to improve their educational experience and it seemed like a product that everybody wants, so all the people participating are winning."

Become an Elite Notetaker and start selling your notes online!

Refund Policy


All subscriptions to StudySoup are paid in full at the time of subscribing. To change your credit card information or to cancel your subscription, go to "Edit Settings". All credit card information will be available there. If you should decide to cancel your subscription, it will continue to be valid until the next payment period, as all payments for the current period were made in advance. For special circumstances, please email


StudySoup has more than 1 million course-specific study resources to help students study smarter. If you’re having trouble finding what you’re looking for, our customer support team can help you find what you need! Feel free to contact them here:

Recurring Subscriptions: If you have canceled your recurring subscription on the day of renewal and have not downloaded any documents, you may request a refund by submitting an email to

Satisfaction Guarantee: If you’re not satisfied with your subscription, you can contact us for further help. Contact must be made within 3 business days of your subscription purchase and your refund request will be subject for review.

Please Note: Refunds can never be provided more than 30 days after the initial purchase date regardless of your activity on the site.