Stars of Shareware: Raytrace & Morphing/SOS-RAYTRACE.ISO/programm/source/rayce27s/tech.doc

Text File | 1994-01-20 | 13.5 KB | 453 lines

-*-text-*-

Hi There!

This is supposed to be a more detailed doc file about the technicalities
of Rayce. It is under construction (as is everything in Rayce :-)


    ABOUT THE SOURCES

I've tried to continue the Ray-tradition: I've commented the sources
to my best ability, and I hope I didn't obfuscate the sources too
much. All sources have been formatted with GNU indent (see the file
cformat).  I have always use 132 x 43 screen resolution, so some of
the source will not be very readable in 80x25....  Get yourself a
serious VGA card :)


    COMPILING

Remember these if you attempt at compiling Rayce:

0. Get a ANSI compliant compiler. I don't know wether it will compile
on non ANSI compilers, but it will undoubtedly give problems.

1. I've tried to keep all device/compiler dependent stuff in a
separate file.  generic version of this file is in dvi.c; it provides
only the stubs for the functions.

If you want to port Rayce, then make a new Makefile and a replacement
for the systemfile. look at ibmtcc.c or linux.c to see which functions
it should have, and what they should do.  It would be nice if you sent
me a copy of the source, and the makefile.  If you are very lazy, you
can use dvi.c. The linux.c file only uses ANSI standard routines, so
you should be able to use linux.c for most OSes which have signals.

These files are provided:

  - makefile.tcc, ibmtcc.c: for Turbo/Borland-C++
  - Makefile, linux.c: for Linux
  - makefile.dj, djgcc.c: for DJGCC (the port was done by Shawn
  McHorse <[e-mail]>)


2. Although I tried to avoid system dependent code outside the
systemfiles, there are some exceptions:

- the naming of MS Dos is somewhat braindead, so in token.c, there is
a bit of conditional compilation for including "rayparse.h" instead of
"rayparse.tab.h" under MSDOS.

- in rayparse.y it says

    #ifdef __TURBOC__
    #define alloca allocaa
    #endif

3. Make sure that Rayce has enough memory.  In MSDOS this means: a
reasonable stack size, and a large memory model.  Turbo C's 4k stack
is definitely too small, but 16k suffices.

4. Get some variant of Yacc. I use Bison, but any other Yacc will
probably also work. If you use Bison, and your compiler has no
alloca() function, you'd better define alloca to be allocaa in
rayparse.y.  Turbo C doesn't have alloca(), so I made a fix: memory
obtained allocaa() is freed after yyparse() has exited.

5. If you use Linux, it is very easy, just type

    make srayce

for a speedy version of Rayce.


    SOURCE DESCRIPTION

*    ray.h

typedefs and important #defines  for rayce.
The most important ones:

object: This is the main structure. It holds shape data, textures,
boundingshapes. It has a "next" field, so it can easily be linked into
a linked list.

struct ray: this is (of course the ray.) it is a line, starting at
ray.pos, headed for ray.dir.

A few important notes:

If you want to study the sources of Rayce, you'd better start reading
here.

A function or variabele that is local to a file is called PRIVATE.  A
function or variabele that can be accessed from the whole program is
called PUBLIC.

The vector as well as the color are structs, not arrays, so they must
be passed by pointer, if function wants to change them. But the
advantage is, they can be returned from a function.

*    object.h

struct xxxx_data: a structure which holds info on shapes, textures,
etc. eg. sphere_data contains a radius and a center.

*    proto.h

function prototypes, to avoid the compilers' weird ideas about
default prototyping. Modifying its contents usually is harmless, so
the makefile just ignores it.

*    extern.h

Global variables.  Because this header is included more than once, all
variables have been declared as EXTERN, which is defined as extern.  In
initialize.c, EXTERN is undef'ed, and included again.  So storage for
global variables is only allocated once. Important ones: commandline
options, statistics.

*    parse.h

for communication between rayparse and token.

*    rayparse*.h

This one is generated by bison.  It contains token codes and the token
types.

*    rayparse.y

The Bison sources for the parser. Bison generates:

*    rayparse.c or rayparse.tab.c

from rayparse.y. I don't distribute the file, because you can generate
it yourself in a few seconds.

*    vector.h

Vector functions. They usually have this form

  vectormacro(output, input1, input2).

Take care: usually a construction like vsub(a,a,b) (equivalent with
a:=a-b) works fine, but you can't do this with vcross.

[Yes. I know, GCC allows inline functions, but I don't want to go
through all the hassle and compiler dependent code.]

*    macro.h

Other useful macros.

If you want to add code, and you want to pull the brakes somewhere.
(for instance a default of a switch(){} that should not occur), then
call thunk().  It prints a neat errormsg, with the file and linenumber
where the error occurred.

*    token.c

Tokenizer, it contains errormsg(), warning(), it handles includes and
allocation of declares.  The most important function is yylex(). The
rest are little bits. If you add keywords to the syntax, then add it
into the big table in this file. I hardly look at it these days.

*    rayparse.y

The Yacc/Bison file.  Run "bison -d rayparse.y" to get rayparse_tab.c and
rayparse_tab.h.  On MSDOS systems these names will be truncated to
rayparse.c and rayparse.h.

*    raymath.c

Linear algebra and simple mathematics:  vector math, matrix math, random
generators.

*    ibmtcc.c
    linux.c
    djgcc.c
    dvi.c

Compiler/system specific parts: timing, handlers, abort checks.
Although they are still pretty portable, you could substitute dvi.c
for this one, if your compiler has complaints. If you would like to
code display routines, this is where you should add them. I myself
don't like device dependent stuff in a program which is supposed to be
highly portable.

*    main.c

The file containing main(), it scans the command line, prints notices,
calls the parser and starts the tracing process. (somebody told, I
wasn't careful with scanning the command line, and that it would cause
problems on Atari/Amiga computers. Anybody? )

*    trace.c

Sets up the tracer, walks all the pixels, and calls trace() for each
pixel.  Ray sampling is done here, and stat printing is done here too.

*    intersect.c

Small file with main intersection routine:  it does the intersection
with the whole scene, and then fills in the details such as intersection
points, normals. The shadow test is a seperate routine, because it has
to deal with shadow caching, early exit for blocking objects, etc.

*    initialize.c

Initialization and stuff which I can't put somewhere else. Global
storage allocation.

*    bg.c

Compute a background color, maybe too small to be a separate file, and
too fancy.  Who needs gradient background?

*    poly.c

Manipulations of polynomials in one variabel: addition,
multiplication, negation, power, etc. Used by solve.c and algebraic.c.
NB. If you want to do q(x) := q(x) - t(x), then poly_sub(q, q, t) is
OK. But poly_multiply(q,q,t) for q := q*t is not!

*    solve.c

Solve polynomial equations of arbitrary order.  NB.  The sturm
sequence code isn't fully tested.  It's main entry point is the
function solve_rt_poly() which finds positive roots of a polynomial,
and puts them sorted in an array. If possible, solve_rt_poly uses fast
root finders for 3rd and 4th order equations. If you want to have
accurate results, use sturm_solve_rt_poly().

The code was done by the collective Eric H Echidna (who have written a
nice raytracer called Art). I also added bits of myself and Graphics
Gems.

*    shade.c

Compute the color of a ray using textures, light_sources etc.  This
used to be the best preserved part of the original Ray raytracer.
But Shawn McHorse revised it completely to allow TIR, microfacets, etc.
This file recursively calls trace().

*    imagemap.c

Stuff for imagemaps:  reading TGAs, mapping planes onto various shapes,
and (of course) standard methods.

*    gif.c

A file snatched from a Linux Gif viewer. It was created by Harm
Hanemaayer <[e-mail]>, and it was based on posting in
rec.games.programmer in spring of 1993.

*    queue.c

This implements a simple depth queue for keeping intersection
information. Who knows how to do priority queues? I would like some
books/articles on the subject.

*    texture.c

Texture manipulations. This one will be the focus for the next release.

*    camera.c

Routines for manipulating cameras. Not very useful, tho. It is being
reworked right now.

-----------------------------------------------------------------------

The files below are files with object and shape standard_routines. The
file xxx.c usually contains:

    free_xxx()    free a xxx structure (and it's components)
    get_new_xxx_object()    alloc and init a xxx structure (don't alloc
            components)
    rotate_xxx(),
    scale_xxx(),
    translate_xxx()    transform a xxx structure

    all_xxx_intersections()
            intersect a ray with a xxx structure, and put
            some or all intersections into a queue. Give
            info, wether ray.pos is inside shape.

    xxx_normal    the normal to a xxx shape.
    copy_xxx    copy a xxx structure (and it's components)
    inside_xxx    is a point inside an xxx shape?
    precompute_xxx    Compute constants for a certain object before
            tracing has started, but after the parsing
            objects should be automatically bounded here.

These routines are stored in a method structure. With each instance of a
XXX, a pointer to XXX's methods is stored. So a sphere object carries
a pointer to its own special routines. These routines can only be
accessed using this method structure, since the routines are PRIVATE.

If you want to add your own primitive this is what you have to do:

- Make your own routines, and put them into a seperate file.  Take a
look at the implementation of some simple shapes, such as polygon, or
sphere. Use stub.c as a starting point.

- Add the datastructures to objects.h

- define the syntax of your primitive, and please make it PoV like.
Add it to the csg_shape_block or the shape_block. Add the keywords to
token.c and rayparse.y, remember to add support for declarations too.
Here are fragments to get you started:

/* rayparse.y */

/* token declarations */
%type <objectval> XXXX_block    XXXX_body
%token     XXXX_T
%token <dectabptr> XXXX_IDENTIFIER


/* syntax */
XXXX_body: /* how to specify a XXXX */             {
        $$ = get_new_XXXX_object();

        /* no precomputation! */
          }
              | XXXX_IDENTIFIER        {
            $$ = get_new_XXXX_object();
        copy_object($$, (object *) $1->data);
          }
          | XXXX_body TRANSLATE vexp    { translate_object($$, $3); }
          | XXXX_body ROTATE vexp     { matrix rm; make_rotation_matrix(rm,$3);rotate_object($$, rm); }
          | XXXX_body scale_stuff        { scale_object($$, $2); }
          | XXXX_body INVERSE        { $$->inverted = !$$->inverted; }
          | XXXX_body texture_block    { $$->text = $2; }
          ;


XXXX_block: XXXX_T '{' XXXX_body '}'    { $$ = $3; }
        ;

/* declarations */
declare_block:
    /* stuff. .. */
    | DECLARE any_identifier '=' XXXX_block    {
        $2->data = (void*) $4;
        $2->type = XXXX_IDENTIFIER;
    }




/* token.c, keyword table (it's alfabetical) */
{
      :
      :
    XXXX_T, "xxxx",    /* remember! sorted by alphabet */
     :
    :
}

- You're finished! Presto! Test your primitive, and then mail the
modified sources to me.


*    box.c:

Boxes. The algorithm is standard. It also contains a public procedure
intersect_rawbox(), for intersecting a ray with an axis aligned box.
This function is public, because it could be used for bounding shapes.

*    composite.c:

A composite is just a bunch of objects which can be treated as one.
This makes collective scaling, rotating etc. very easy. Note that in
Rayce, this is something different than a csg union.

*    lights.c:

A very simple file with routines for the lights objects. Code to
create a linked list of all the lights in the scene is also here.
This list is needed for efficiently finding the lights in the scene,
in shade.c.

*    plane.c:

Infinite planes.

*    object.c

A uniform interface to the various shapes and object types in Rayce.

*    quadric.c

Code for arbitrary quadrics.

*    sphere.c

Spheres, the most basic thing in raytracing (along with checkered
floors ;-) (gee, I must do checkers, some time)

*      superq.c

Superquadrics. It should work now.

*    torus.c

Toruses. Simple toruses. They can be calculated quite efficiently,
because it is possible to have very tight bounds around them. uses
solve.c to do the equation solving.

*    csg.c

CSG unions and intersections. Since the code for both overlaps, they
are contained in one file. Mathematically speaking, they are even
equivalent!

*    algebraic.c

Arbitrary algebraic surfaces. The general idea is: store the
polynomial in terms of operations (similar to hoc level 4, in The Unix
Programming Environment, by Kernighan & Pike).  Then use a simple
"virtual" stack machine to calculate the resulting polynomial in the
ray parameter t. The normal is calculated in a similar fashion: the
input is vector Loc, and of all operands (which are polynomials p_j),
the polynomial p_j(x1,x2,x3) in Loc is evaluated, and the polynomial
dp_j/dx_i (i = 1..3) is evaluated in Loc. We then get the gradient of
the polynomial Phi(x,y,z) which determines the surface normal

*    polygon.c

Convex flat polygons. Implemented by clipping a plane with the edges
of a polygon. The polygon is projected onto a coordinate plane before
it is clipped.  I should build an extra routine for non-convex polygons.

*    extrusion.c

Extrusions. This takes the intersection of a shape with the XY plane,
and then "thickens" it along the Z axis. I have thought of the
algorithm myself, but it turns out mr. Kajiya already did before me.

*    triangle.c

Smooth and non-smooth triangles. It works by decomposing an
intersection point into barycentric coordinates.

/* eof */