v21i014: A ray tracing program, Part07/08
Rich Salz
rsalz at uunet.uu.net
Thu Feb 8 07:50:54 AEST 1990
Submitted-by: Craig Kolb <craig at weedeater.math.yale.edu>
Posting-number: Volume 21, Issue 14
Archive-name: rayshade/part07
#! /bin/sh
# This is a shell archive. Remove anything before this line, then unpack
# it by saving it into a file and typing "sh file". To overwrite existing
# files, type "sh file -c". You can also feed this as standard input via
# unshar, or by typing "sh <file", e.g.. If this archive is complete, you
# will see the following message at the end:
# "End of archive 7 (of 8)."
# Contents: doc/primitive.ms
PATH=/bin:/usr/bin:/usr/ucb ; export PATH
if test -f 'doc/primitive.ms' -a "${1}" != "-c" ; then
echo shar: Will not clobber existing file \"'doc/primitive.ms'\"
else
echo shar: Extracting \"'doc/primitive.ms'\" \(20923 characters\)
sed "s/^X//" >'doc/primitive.ms' <<'END_OF_FILE'
X
X.\"
X.\" Brief tutorial on adding new primitives to rayshade.
X.\" Craig Kolb 10/89
X.\"
X.\" $Id: primitive.ms,v 3.0 89/10/24 18:07:30 craig Exp $
X.\"
X.\" $Log: primitive.ms,v $
X.\" Revision 3.0 89/10/24 18:07:30 craig
X.\" Baseline for first official release.
X.\"
X.de D(
X.DS
X.nr PS 8
X.ps 8
X.nr VS 12p
X.vs 12p
X.cs 1 20
X..
X.de D)
X.DE
X.nr PS 10
X.ps 10
X.nr VS 18p
X.vs 18p
X.cs 1
X..
X.DS
X.ND October, 1989
X.RP
X.de ]H
X.nr PS 10
X.ps 10
X'sp |0.5i-1
X.tl 'Rayshade Primitive Tutorial'-%-'Draft'
X.ps
X.ft
X'sp |1.0i
X.ns
X..
X.wh0 ]H
X.pn 2
X.LP
X.TL
XAdding Primitives to Rayshade
X.TL
X\fR\fIDraft\fR
X.AU
XCraig Kolb
X.AI
XDepartment of Mathematics
XYale University
XNew Haven, CT 06520
X.sp .5i
X.nr VS 18pts
X.PP
XThis tutorial describes the process of adding new primitives to
Xrayshade. Although the hooks for adding primitives are relatively
Xstraight-forward, it is difficult to see the "big picture" by
Xstudying the source code. While this tutorial is primarily
Xmeant for those interested getting their hands dirty, it
Xprovides a overview of the design of at least one portion
Xof rayshade and thus may be of interest even if you are not
Xplanning on making modifications.
X.LP
XAdding a new primitive involves modifying at least six source
Xfiles and creating at least one new file:
X.NH
Xprimobj.h
X.LP
XA datatype for the new primitive is added, and a pointer for
Xthe new type is added to the Primitive type.
X.NH
Xconstants.h
X.LP
XA numerical type is reserved for the primitive.
X.NH
Xintersect.c
X.LP
XVarious arrays of pointers to functions are modified to include
Xnew functions which will be written for the new primitive.
XThe name of the new primitive is added to a list of names,
Xand an array of flags is modified to reflect the addition of
Xthe new primitive.
X.NH
Xfuncdefs.h
X.LP
XThe ray-primitive intersection function, primitive creation
Xfunction, normal calculation function, and bounding-box
Xcalculation function are declared.
X.NH
X<primitive-type>.c
X.LP
XThis file contains
Xall of the code needed to perform
Xray-primitive intersection tests, find normals, and compute
Xbounding boxes for the new primitive type.
X.NH
Xinput_lex.l
X.LP
XThe keyword used to identify the new primitive is added to
Xthe list of recognized keywords.
X.NH
Xinput_yacc.y
X.LP
XThe new primitive is added to the list of primitives recognized by
Xthe yacc grammar. The added code will call the routine
Xwhich creates and returns a reference to the primitive
Xwhich was defined in <primitive-type>.c
X.LP
XIn addition, the Makefile must be updated to reflect the existence of the
Xnew source file.
X.sp 1
X.LP
XIn this tutorial, a new primitive
X.I disc,
Xis added to rayshade. A disc is specified by its center, radius,
Xand normal.
X.br
X.NR PS 12
X.ps 12
X.sp .5
X\fBThe Primitive type\fR
X.nr PS 10
X.ps 10
X.sp .5
X.LP
XAll Primitives in rayshade are referenced using a single Primitive structure.
XThis structure is defined as:
X.D(
Xtypedef struct Primitive {
X char type; /* object type */
X struct Surface *surf; /* default surface */
X union {
X Sphere *p_sphere;
X Box *p_box;
X Triangle *p_triangle;
X Superq *p_superq;
X Plane *p_plane;
X Cylinder *p_cylinder;
X Polygon *p_poly;
X Cone *p_cone;
X Hf *p_hf;
X } objpnt; /* Pointer to primitive */
X} Primitive;
X.D)
X.LP
XThe
X.I type
Xfield is used by various routines in intersect.c to determine
Xwhich elements in a number of arrays should be used when dealing with
Xa given Primitive structure.
XThe
X.I surf
Xfield points to the surface associated with the primitive.
XThe
X.I objpnt
Xfield is a union of pointers to different primitive types.
XThe
X.I type
Xof the Primitive is used to determine which pointer to
Xdereference.
X.NH 0
XModifying primobj.h
X.LP
XPrimobj contains structures describing each primitive type. For example,
Xa sphere is defined as:
X.D(
Xtypedef struct {
X double r; /* radius */
X double x, y, z; /* position */
X} Sphere;
X.D)
XWe must define a similar structure for the disc primitive. After the
Xdefinition of the Hf type, we add:
X.D(
X/*
X * Disc
X */
Xtypedef struct {
X Vector center, /* Center of the disc */
X normal; /* Normal to disc */
X double d, /* Plane constant */
X radius; /* Radius of disc */
X} Disc;
X.D)
X.LP
XWe must also add a pointer for the Disc type to the Primitive type.
XSo, we add a line to the \fIobjpnt\fR union in the Primitive definition,
Xgiving us:
X.D(
Xtypedef struct Primitive {
X char type; /* object type */
X struct Surface *surf; /* default surface */
X union {
X Sphere *p_sphere;
X Box *p_box;
X Triangle *p_triangle;
X Superq *p_superq;
X Plane *p_plane;
X Cylinder *p_cylinder;
X Polygon *p_poly;
X Cone *p_cone;
X Hf *p_hf;
X Disc *p_disc;
X } objpnt; /* Pointer to primitive */
X} Primitive;
X.D)
X.NH
XModifying constants.h
X.LP
XIn constants.h, there are a series of lines resemblin:
X.D(
X#define SPHERE 0
X#define BOX 1
X#define TRIANGLE 2
X#define SUPERQ 3
X#define PLANE 4
X#define CYL 5
X#define POLY 6
X#define PHONGTRI 7
X#define CONE 8
X#define HF 9
X#define LIST 10
X#define GRID 11
X.D)
X.LP
XThese lines define the values assigned to the 'type' field in each
XPrimitive and Object. (Actually, a Primitive can never be of type
XLIST or GRID, but an Object may be.) We must add a similar line for
Xthe new primitive.
X.LP
XWhen adding new values, we
X.I must
Xadd the primitive
X.I before
Xthe
Xlines defining the types for LIST and GRID. This is due to the way
Xarrays are indexed in intersect.c So, below the HF type, we add a line
Xfor the Disc type and increment the LIST and GRID types:
X.D(
X#define CONE 8
X#define HF 9
X#define DISC 10
X#define LIST 11
X#define GRID 12
X.D)
XWe must also increment PRIMTYPES, the total number of primitives types:
X.D(
X#define PRIMTYPES 11
X.D)
X.NH
XModifying intersect.c
X.LP
XIn intersect.c, several arrays are declared and initialized which are indexed
Xby Primitive or Object type. We must modify these array declarations
Xto reflect the addition of the new primitive type. The first array to
Xbe modified is :
X.D(
Xdouble (*objint[])() = {intsph, intbox, inttri, intsup, intplane, intcyl,
X intpoly, inttri, intcone, inthf};
X.D)
XThis array of pointers to functions contains the names of the functions
Xwhich perform ray/primitive intersection tests. Here,
X.I intsph,
Xthe
X0th element in the array, is the name of the intersection routine
Xfor the Sphere primitive, which is declared as type 0 in constants.h.
XSimilarly,
X.I intplane
Xis the 4th element in the array, and the Plane
Xprimitive is defined to be type 4. This is due to the fact that a
XPrimitive's type field is used as an index into this array.
X.LP
XSo, we must add the name of the new ray/disc intersection test, which
Xwe will name "intdisc", to the objint[] array:
X.D(
Xdouble (*objint[])() = {intsph, intbox, inttri, intsup, intplane, intcyl,
X intpoly, inttri, intcone, inthf, intdisc};
X.D)
XSimilarly, we must modify the objnrm[] and objextent[] arrays to contain
Xthe names of the functions that compute a specific disc's normal and
Xbounding box:
X.D(
Xint (*objnrm[])() = {nrmsph, nrmbox, nrmtri, nrmsup, nrmplane, nrmcyl,
X nrmpoly, nrmtri, nrmcone, nrmhf, nrmdisc};
X
Xint (*objextent[])() = {sphextent, boxextent, triextent, supextent,
X planeextent, cylextent, polyextent, triextent,
X coneextent, hfextent, discextent};
X.D)
X.LP
XIn addition, there is an array of Primitive names which is used when
Xprinting statistics. Again, we need to modify the array to include
Xthe name of the Disc primitive:
X.D(
Xchar *primnames[PRIMTYPES] = { "Sphere", "Box", "Triangle", "Superq", "Plane",
X "Cylinder", "Polygon", "Phongtri", "Cone",
X "Heightfield", "Disc"};
X.D)
X.LP
XLastly, there is an array of flags named CheckBounds[] which is indexed
Xby Object type. This array is used by intersect() to determine if
Xa ray/bounding-box intersection test should be performed before a ray/Object
Xintersection test. If the element in CheckBounds[] corresponding to
Xan Object's type is TRUE, a ray/Object intersection test will only occur
Xif a ray/bounding-box intersection test succeeds. (Even if ray/bounding-box
Xtests are not performed for a given primitive, the bounding box is still
Xused to determine the extent of the object when it is included in compound
XObjects.)
X.LP
XWe will set the flag corresponding to the Disc primitive to be TRUE. Note
Xthat the CheckBounds array is indexed by \fIObject\fR type, so we add the
Xentry for the Disc type before the final two entries in the array:
X.D(
Xchar CheckBounds[] = {TRUE, FALSE, TRUE, FALSE, FALSE, TRUE, TRUE, TRUE,
X TRUE, FALSE, TRUE, FALSE, FALSE};
X.D)
X.NH
XModifying funcdefs.h
X.LP
XThe file funcdefs.h contains a number of function declarations. We must add
Xdeclarations for the four new functions to be written. Firstly,
Xwe add the declaration of "nrmdisc" to the normal-finding functions:
X.D(
Xint nrmsph(), nrmbox(), nrmtri(), nrmsup(),nrmplane(), nrmcyl(),
X nrmpoly(), nrmcone(), nrmhf(), nrmdisc();
X.D)
X.LP
XNext, we declare "intdisc" with the other ray/primitive intersection
Xtest functions:
X.D(
X/*
X * Intersection routines
X */
Xdouble intsph(), intbox(), inttri(), intsup(),intplane(), crossp(), intcyl(),
X intpoly(), intcone(), inthf(), intdisc();
X.D)
XAnd the bounding-box routine:
X.D(
X/*
X * Extent-box finding routines
X */
Xint sphextent(),boxextent(),triextent(),supextent(),planeextent(),
X cylextent(), polyextent(), coneextent(), hfextent(),
X discextent();
X.D)
X.LP
XAnd lastly, we add "makdisc", the routine which will create a reference
Xto a particular disc, to the list of object creation functions:
X.D(
X/*
X * Object creation routines
X */
XObject *maksph(), *makbox(), *maktri(), *maksup(), *makplane(), *makcyl(),
X *makpoly(), *makcone(), *makhf(), *makdisc(), *new_object()
X.D)
X.NH
XWriting disc.c
X.LP
XAnd now we must write the four functions makdisc(), intdisc(), nrmdisc()
Xand discextent(). The first thing you should do is copy
Xthe Copyright
Xtemplate to the top of disc.c.
X.LP
XNext, we need to #include the necessary header files. In addition to math.h
Xand stdio.h, you will need "constants.h" (which includes the definition
Xof DISC), "typedefs.h" (which includes all sorts of useful structure
Xdefinitions), and "funcdefs.h" (which includes all sorts of useful
Xfunction declarations).
X.NH 2
Xmakdisc()
X.LP
XEvery primitive-creation function must take a least one argument -- the
Xname of the surface to be associated with the primitive. Besides this
Xargument, these functions will be passed any parameters needed to define
Xa particular primitive. For us, this means two vectors (the center of
Xthe disc and its normal) and one double (the radius of the disc).
X.LP
XThe makdisc() routine will do several things. In addition to creating a new
XDisc, it must allocate a Primitive structure and set its fields
Xappropriately -- it must point to the new Disc, have its "type" field
Xset correctly, and it must point to the surface associated with the
Xprimitive. In addition, an Object which points to this new Primitive
Xmust be created and initialized properly. It is this Object structure
Xwhich is returned by makdisc().
X.LP
XSo, we write:
X.D(
XObject *
Xmakdisc(surf, center, radius, norm)
Xchar *surf;
XVector center, norm;
Xdouble radius;
X{
X Disc *disc; /* Pointer to new disc. */
X Primitive *prim; /* Pointer to new Primitive */
X Object *newobj; /* Pointer to new Object */
X Vector tmpnorm; /* normalized normal */
X extern int Quiet; /* True if we shouldn't complain */
X extern int yylineno; /* Current line # in input file. */
X
X if (radius < EPSILON) {
X if (!Quiet)
X fprintf(stderr,"Degenerate disc (line %d).\\n",
X yylineno);
X /*
X * Don't create this primitive.
X */
X return (Object *)0;
X }
X
X tmpnorm = norm;
X if (normalize(&tmpnorm) == 0.) {
X if (!Quiet)
X fprintf(stderr,"Degenerate disc normal (line %d).\\n",
X yylineno);
X return (Object *)0;
X }
X /*
X * Allocate new Disc.
X */
X disc = (Disc *)Malloc(sizeof(Disc));
X /*
X * Initialize new disc.
X * We store the square of the radius to save us a sqrt().
X */
X disc->radius = radius*radius;
X disc->center = center;
X disc->normal = tmpnorm;
X /*
X * Compute plane constant.
X */
X disc->d = dotp(¢er, &tmpnorm);
X /*
X * Allocate new Primitive
X */
X prim = mallocprim();
X /*
X * Set Primitive type and pointer to new Disc.
X */
X prim->type = DISC;
X prim->objpnt.p_disc = disc;
X /*
X * Search for named surface in list of defined surfaces.
X * find_surface() will exit if the surface is not found.
X */
X prim->surf = find_surface(surf);
X /*
X * Create and return new object with NULL name, of type DISC,
X * which points to the new Primitive and has no transformation
X * associated with it.
X */
X return new_object(NULL, DISC, (char *)prim, (Trans *)NULL);
X}
X.D)
X.LP
XIn this case, our primitive creation function is straight-forward. In
Xsome cases, in order to facilitate ray-primitive intersection tests,
Xa more general version of the primitive is created, and a transformation
Xmatrix is computed to transform the generic primitive to the specific
Xprimitive requested by the user. Then, one need only perform
Xintersection tests against the generic version of the primitive. Examples
Xof these types of primitives are the cone and cylinder. The generic
Xversions of both of these primitives have their main axes coincident
Xwith the Z axis and their base at the origin. Transformations are
Xcomputed in makcyl() and makcone() to transform the generic case to
Xthe specific case. See "cone.c", "cylinder.c" and "input_yacc.y" for
Xdetails.
X.NH 2
Xintdisc()
X.LP
XEach primitive/ray intersection routine is passed three values:
Xa pointer to a Primitive, the origin of the ray, and the direction of
Xthe ray. Each intersection function must do two things. Firstly,
Xit must increment an element in the primtests[] array to reflect the
Xfact that a ray/primitive intersection test has occurred. Most importantly,
Xeach function must return the distance from the ray origin along the
Xray direction to the closest point of ray/primitive intersection. This
Xdistance must be greater than EPSILON. If it is less than EPSILON, it is
Xassumed that no intersection occurs between the ray and the given primitive.
XIf not valid intersection exists, 0 is returned.
X.LP
XSo, we write:
X.D(
Xdouble
Xintdisc(pos, ray, obj)
XVector *pos, *ray;
XPrimitive *obj;
X{
X Disc *disc;
X Vector hit;
X double denom, dist;
X extern unsigned long primtests[];
X
X primtests[DISC]++;
X disc = obj->objpnt.p_disc;
X
X denom = dotp(&disc->normal, ray);
X if (denom == 0.)
X return 0.;
X dist = (disc->d - dotp(&disc->normal, pos)) / denom;
X if (dist > FAR_AWAY || dist < EPSILON)
X return 0.;
X /*
X * Find difference between point of intersection and center of disc.
X */
X vecsub(addscaledvec(*pos, dist, *ray), disc->center, &hit);
X /*
X * If hit point is <= disc->radius from center, we've hit the disc.
X */
X if (dotp(&hit, &hit) <= disc->radius)
X return dist;
X return 0.;
X}
X.D)
X.NH 2
Xnrmdisc()
X.LP
XEach primitive normal routine is passed a location to a primitive, a pointer
Xto a point on the surface of the primitive, and a pointer to a vector
Xwhich must be set to the normal to the primitive at the point of intersection.
XFor the disc, this is very simple, as the disc is planar:
X.D(
XVector
Xnrmdisc(pos, prim, nrm)
XVector *pos, *nrm;
XPrimitive *prim;
X{
X *nrm = prim->objpnt.p_disc->normal;
X}
X.D)
X.NH 2
Xdiscextent()
X.LP
XThe discextent() routine is passed a pointer to a disc Primitive as well
Xas a bounding
Xbox stored as a 2 by 3 array of doubles. The routine computes the extent
Xof the disc along each axis and fills the bounding box array appropriately.
X.LP
XNote that the bounding box of all primitives should be at least
X2*EPSILON along each axis to avoid problems with roundoff error.
XFortunately, primextent(),
Xroutine which calls the primitive bounding box functions, will check
Xfor and "widen" degenerate bounding boxes.
XThus, the
Xbounding box volumes are allowed to compute degenerate boxes.
XAlso, if a primitive is unbounded (e.g., a plane),
Xthe maximum X extent should be set to be less than the minimum X extent.
X.LP
XSo, discextent is written as:
X.D(
Xdiscextent(prim, bounds)
XPrimitive *prim;
Xdouble bounds[2][3];
X{
X Disc *disc;
X double extent, rad;
X
X disc = prim->objpnt.p_disc;
X
X rad = sqrt(disc->radius);
X /*
X * Project disc along each of X, Y and Z axes.
X */
X extent = 1. - disc->normal.x * disc->normal.x;
X extent *= rad;
X bounds[LOW][X] = disc->center.x - extent;
X bounds[HIGH][X] = disc->center.x + extent;
X extent = 1. - disc->normal.y * disc->normal.y;
X extent *= rad;
X bounds[LOW][Y] = disc->center.y - extent;
X bounds[HIGH][Y] = disc->center.y + extent;
X extent = 1. - disc->normal.z * disc->normal.z;
X extent *= rad;
X bounds[LOW][Z] = disc->center.z - extent;
X bounds[HIGH][Z] = disc->center.z + extent;
X}
X.D)
X.NH
Xinput_lex.l
X.LP
XAmong other things, input_lex.l contains a list of all the keywords
Xrecognized by rayshade. To this list we must add the keyword for
Xthe new primitive type. Following the example of other keywords,
Xwe add:
X.D(
Xdisc {return(tDISC);}
X.D)
X.NH
Xinput_yacc.y
X.LP
XNear the top of input_yacc.y are the declarations for the tokens
Xreturned by lex. We must add the new token, tDISC, to this list:
X.D(
X%token tBACKGROUND tBLOTCH tBOX tBUMP tCONE tCYL tDIRECTIONAL tDISC
X.D)
XFinally, we need to add the production to the yacc grammar which will
Xcall makdisc(). We first modify the Primtype production to include
Xa new production named Disc:
X.D(
XPrimtype : Plane
X | Sphere
X | Box
X | Triangle
X | Cylinder
X | Cone
X | Superq
X | Poly
X | HeightField
X | Disc
X ;
X.D)
X.LP
XNext, near the productions for the other primitives, we add:
X.D(
XDisc : tDISC tSTRING Vector Fnumber Vector
X {
X /*
X * disc surfname center.x center.y center.z
X * radius norm.x norm.y norm.z
X */
X LastObj = maksph($2, $3, $4, $5);
X }
X ;
X.D)
X.NH
XTesting
X.LP
XOnce you add "disc.o" to the OBJS list in the Makefile, you should be
Xable to re-compile rayshade. A good input file for testing the disc
Xprimitive might be:
X.D(
X/*
X * Demo picture of a textured ground plane with a sphere, cone
X * and disc. The disc is situated on the top of the cone and faces
X * up and towards the viewer.
X */
Xeyep 0. 25. 7.
Xscreen 256 256
Xlight 1.4 point -15. 20. 15.
Xsurface red .02 0 0 .5 0 0 .2 .2 .2 32. 0.0 0 0
Xsurface blacktile 0.01 0.015 0.01 0.02 0.03 0.02 0.3 0.35 0.3 30 0. 0 0
Xsurface white .02 .02 .008 .5 .5 .25 0.8 0.8 0.8 18 0. 0 0
Xsurface glass 0.02 0.02 0.02 0. 0. 0. 0.8 0.8 0.8 25 0. 0. 1.15
X
Xdisc white -5. 3. 4. 3. 0. 1. 1.
Xsphere red 4. 3 0 0
X/*
X * Cone actually sticks through ground plane. This solves problems
X * that arise when the bottom of the cone and the plane are coincident.
X */
Xcone glass -5. 3 -4.1 -5. 3. 4. 4. 0.
X
X
Xplane white 0. 0. 1. 0. 0. -4.
X texture marble scale 4. 4. 4.
X texture checker blacktile translate 0. 0. 0.3 scale 4. 4. 4.
X.D)
END_OF_FILE
if test 20923 -ne `wc -c <'doc/primitive.ms'`; then
echo shar: \"'doc/primitive.ms'\" unpacked with wrong size!
fi
# end of 'doc/primitive.ms'
fi
echo shar: End of archive 7 \(of 8\).
cp /dev/null ark7isdone
MISSING=""
for I in 1 2 3 4 5 6 7 8 ; do
if test ! -f ark${I}isdone ; then
MISSING="${MISSING} ${I}"
fi
done
if test "${MISSING}" = "" ; then
echo You have unpacked all 8 archives.
rm -f ark[1-9]isdone
else
echo You still need to unpack the following archives:
echo " " ${MISSING}
fi
## End of shell archive.
exit 0
--
Please send comp.sources.unix-related mail to rsalz at uunet.uu.net.
Use a domain-based address or give alternate paths, or you may lose out.
More information about the Comp.sources.unix
mailing list