minray.post

[Game.Programming].Academic - Graphics Gems (6 books source code)

Path: pixar!ph
From: [e-mail] (Paul Heckbert)
Newsgroups: comp.graphics
Subject: Announcing: MINIMAL RAY TRACER PROGRAMMING CONTEST
Date: 4 May 87 21:52:33 GMT
Organization: Pixar -- Marin County, California

# to unpack, cut here and run the following through sh
# shell archive of: rules squeeze.c ntok.csh ray.h test1.ap
#
cat <<'EOF15382' >rules

**************************************
MINIMAL RAY TRACER PROGRAMMING CONTEST
**************************************

The goal: write the shortest Whitted-style ray tracing program in C.
Countless people have written basic sphere ray tracers and made pictures of
glass and chrome balls, so isn't it time we found out just how short such a
program can be?

The algorithms required are described in the classic article:
	
    Turner Whitted
    "An Improved Illumination Model for Shaded Display"
    Communications of the ACM, June 1980, pp. 343-349

Given Kernighan&Ritchie, Whitted's article, and a basic knowledge of 3-D
graphics, anyone should be able to enter this contest.  Winning the
contest will require intimate knowledge of C and considerable ingenuity,
however.

Briefly, the rules are as follows: you mail me C source to a ray tracer which
renders spheres with specular and transmitted rays and hard shadows but
no antialiasing.  The scene is compiled in, and the picture is
output to stdout.  Speed is no object.  The winner will be the shortest
C program which produces the "correct" output, where shortest is measured by
the number of tokens after the C preprocessor.  The deadline is 15 June 1987.

Files in this shell archive are:
    rules    - contest announcement and rules
    squeeze.c   - program for token counting
    ntok.csh - C shell alias for token counting
    ray.h    - sphere list for a test scene
    test1.ap - a correct image of that scene, for reference


**** CONTEST RULES ****

An entry is considered valid if it meets all of the following conditions:

    1. program consists of a single C source file (called ray.c, say)

    2. compiles with no errors or warnings on 4.3bsd on my VAX 780
	with a command of the form "cc -o ray ray.c -lm"
	(sorry, but this is the only way I can verify entries consistently)
	Thus, "modern" C features such as structure passing and enum are legal.

    3. ray traces a list of spheres using Whitted's recursive shading
	model for the specular and transmitted (refracted) components.

    4. the sphere list, camera, and other parameters
	(listed below) are compiled into the program from a header file 
	with '#include "ray.h"'.  The program must work for any set of such
	parameters, except where noted below (each entry will be compiled
	and tested with several different header files).

	the following are specified in the header file:

	a sphere has at least the following attributes
	    center point (x,y,z)
	    color (r,g,b) with 0<=r,g,b<=1
	    radius
	    diffuse, specular, transmitted, and luminosity coefficients
		call them kd, ks, kt, kl respectively
	    index of refraction ir

	and the following constants are #defined:
	    DEPTH		maximum ray tree depth
				    depth=0 means return black (0,0,0)
				    depth=1 means shade only primary rays
				    depth=2 means primary and secondary, etc.
	    SIZE		resolution of picture in pixels (it's square)
	    AOV			total angle of view in degrees
	    NSPHERE		number of spheres in scene

	The sphere list and ambient color are initialized in ray.h using
	the identifiers "SPHERE" and "AMBIENT", which you will need to
	#define before #including that file.  SPHERE and AMBIENT can be
	arrays of doubles, structures, or whatever you like.
	For example:
	
		#define SPHERE	struct sphere sph[NSPHERE]
		
	Your program should compile with the enclosed ray.h.
    
    5. uses the following shading model:

	if a ray intersects sphere i, then the color returned along that ray is:

	    C = kd[i]*SURFCOLOR[i]*
		    (AMBIENT + sum(j){lit(j)*kl[j]*SURFCOLOR[j]*max(0,N.L)}) +
		ks[i]*CS + kt[i]*CT + kl[i]*SURFCOLOR[i]

	if a ray misses all spheres, then the color returned is:

	    C = AMBIENT

	where
	    capitals denote 3-vectors (xyz or rgb)
		geometric (xyz) vectors N and L should be normalized
	    sum(j){x} is the sum of x over all lights j
	    lights are modeled as luminous spheres within the scene
	    any sphere with kl!=0 is considered a light
	    lit(j)=0 if the surface point is in shadow with respect to light j,
		else lit(j)=1.  A surface point is "in shadow" if a ray from
		that point toward the center of the light intersects any spheres
		before it reaches the light

	    (SURFCOLOR, kd, ks, kt, kl)[i] are attributes of the sphere hit
	    kl[j] and SURFCOLOR[j] are intensity and color of light being tested
	    L is the vector from the surface point to light j
	    the normal vector N points in if the ray strikes the surface
		from within the sphere, else N points out
	    AMBIENT is the ambient light color
	    CS and CT are the recursive specular and transmitted colors

	notes:
	    air has index of refraction of 1
	    you may assume all spheres have a positive index of refraction
	    you may assume that no two transparent spheres intersect
	    use CT=0 when refraction causes total internal reflection
	    shading formula needs no highlight term because lights are in scene

    6. uses the following perspective camera model:
	spheres are specified in right-handed world space
	eye is at (0,0,0) looking in +y direction of world space
	screen space x points right, y points down
	pixels are square
	the pixel at screen space (x,y) has world space ray direction
	    dx = x-SIZE/2
	    dy = (SIZE/2)/tan(AOV/2)	(where tan takes degrees)
	    dz = SIZE/2-y

    7. the picture is output to stdout in ascii in the format:
	A header of two integers, the xsize and ysize,
	followed by xsize*ysize rgb INTEGER triplets in scanline
	(row-major) order.  These pixel values should be 255 times the
	intensities computed with the above shading model.
	It is acceptable for values to exceed 255.
	Enclosed is test1.ap, an ascii picture file conforming to this format.

    8. output of your program must match my pixel values within + or - 10.
	(Please run your program with the enclosed ray.h and compare your
	output to test1.ap; only submit if your pixel values nearly match)

    9. entries must be postmarked before 15 June 1987

not needed:
    1. antialiasing
    2. any geometric primitives besides spheres
    3. CSG
    4. any probabilistic ray tracing effects, such as
	penumbras or the rendering equation
    5. program doesn't have to pass lint
    6. speed

goal:
    The winner will be the valid entry with the minimum number of tokens
    after running the source through the C preprocessor.
    (This is a better measure of program length than number of lines or object
    code size, since it is machine-independent and more hacker-resistant.)
    Use the enclosed program, squeeze.c, and the ntok alias in ntok.csh to
    count tokens.

Send entries and questions via e-mail to me at

    UUCP: {sun,ucbvax}!pixar!minray
    ARPA: [e-mail]

Please put your name, address (electronic and otherwise), number of years of
programming, and any remarks about your minimization tricks in a comment
at the top of your source file.  Note that my token counter ignores comments
and unused ifdefs, so such a comment won't penalize you.

At any time before the deadline you can mail me and I'll tell you the token
count of the current leader.

The winning entries will be posted to comp.graphics.

		- Paul Heckbert
		  3 May 87
EOF15382
cat <<'EOF15383' >squeeze.c
/*
 * SQUEEZE - Squeeze a C program.
 * Breaks a C program into indivisible tokens and packs as many tokens per
 * line as possible, eliminating comments and unnecessary whitespace.
 * One way to save paper, screen space, and disk space.
 * "squeeze -1 | wc -l" will count tokens.
 *
 * Paul Heckbert	21 May 81
 */

#include <stdio.h>
#define bs BUFSIZ
#define siz 300000	/* change this if you ain't got that much memory */

#define space 1
#define punc 2
#define label 3
#define comment 4
#define eof 5

static char *usage = "\
Usage: squeeze [<file>] [-<linelength>]\n\
Reads from standard input if no filename given.	 Output to standard output.\n\
";

static char buf[siz+1];
static char label_chars[] =
    "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ_";
static char *combo[] =
    {">=","<=","!=","==","||","&&","->","++","--",">>","<<",0};
static char *nd;

main(ac,av)
int ac;
char **av;
{
    char *i0,*j0,*i1,*j1,*i2,*j2,q;
    int count,t0,t1,t2,fill,linel,k,fd,n;

    if (ac>3 || ac==2 && av[1][0]=='-' && av[1][1]==0) {
	fprintf(stderr,usage);
	exit(1);
    }

    fd = 0;
    linel = 79;
    for (k=1; k<ac; k++)
	if (av[k][0]=='-') linel = atoi(av[k]+1);
	else if ((fd = open(av[k],0))==-1)
	    {printf("Can't get %s\n",av[k]); exit(1);}

    for (i1=buf, n=0; n+bs<=siz && (count = read(fd,i1,bs))>0;
	n+=count, i1+=count);
    if (count>0) {printf("file too big to squeeze!\n"); return;}
    buf[n] = 0;				/* sentinel */
    nd = buf+n;
    t0 = punc;				/* pretend */
    i1 = j0 = i0 = buf;
    count = 0;
    fill = 1;
    t1 = get_token(i1,&j1);		/* first token */

    for (i2=j1; t1!=eof; i1=i2,j1=j2,t1=t2, i2=j1) {
	t2 = get_token(i2,&j2);
	if (t1==punc && j1-i1==1 && *i1=='#') { /* preprocessor line */
	    if (count) {putchar('\n'); count = 0;}
	    fill = 0;
	}

	if (!fill && t1==space && index(i1,"\n")<j1-i1) {
					/* CR at end of preprocessor line */
	    putchar('\n');
	    count = 0;
	    fill = 1;
	}
	else if (t1==comment || t1==space && (t0!=label || t2!=label) &&
			    /* eliminate space unless it's between two labels */
	    (fill || t0!=label) &&	/* macros are sensitive to spaces */
	    (j0-i0!=1 || *i0!='=' || j2-i2!=1 ||
		*i2!='-' && *i2!='*' && *i2!='&')) continue;
					/* also, don't make =- or =* or =& */
	else if (t1==space)
	    if (fill && count+1+j2-i2>linel && count)
		{putchar('\n'); count = 0;}
					/* replace space with CR */
	    else {putchar(' '); count++;}
	else if (fill && count+j1-i1>linel && count) {
					/* we've run over, time for a CR */
	    putchar('\n');
	    count = put(i1,j1);
	}
	else count += put(i1,j1);
	i0 = i1; j0 = j1; t0 = t1;
    }
    if (count>0) putchar('\n');
}

static get_token(i1,j1)	/* find token starting at i1, set end j1, return type */
char *i1,**j1;
{
    char *i,str[2];
    int k, number, type;

    if (i1>=nd) {			/* hit end of file */
	*j1 = i1;
	return(eof);
    }
    str[1] = 0;
    number = *i1>='0' && *i1<='9'  ||  *i1=='.' && i1[1]>='0' && i1[1]<='9';
    for (i=i1; i<nd; i++) {		/* is this a label char? */
	str[0] = *i;
	if (index(label_chars,str)<0 && (!number || *i!='.') &&
	    (!number || i[-1]!='e' && i[-1]!='E' || index("+-",str)<0)) break;
    }
    if (i>i1) {				/* a label */
	*j1 = i;
	return(label);
    }
    type = punc;
    for (i=i1; i<nd && (*i==' ' || *i=='\t' || *i=='\n'); i++);
    if (i>i1) {i--; type = space;}
    if (*i1=='"' || *i1=='\'')		/* quote */
	for (i=i1+1; i<nd && *i!=*i1; i++) if (*i=='\\') i++;
    for (k=0; combo[k] && !prefix(combo[k],i1); k++);
    if (combo[k]) i = i1+strlen(combo[k])-1;
			    /* a 2 or 3-char combination (don't split) */
    if (prefix("/*",i1)) {i = index(i1+2,"*/")+i1+3; type = comment;}
    *j1 = i+1;
    return(type);
}

static index(A0,B)		/* find first occurence of string B within A */
char *A0,*B;
{
    char *a,*b,*A;

    if (*B==0) return(-1);
    for (A=A0; *A; A++)
	if (*A==*B) {			/* see if we have a match */
	    for (a=A+1, b=B+1; *b && *a==*b; a++, b++);
	    if (*b==0) return(A-A0);
	}
    return(-1);
}

static prefix(a,b)			/* is a a prefix of b? */
char *a,*b;
{
    while (*a && *a==*b) {a++; b++;}
    return(!*a);
}

static put(i,j)
char *i,*j;
{
    int k;

    k = j-i;
    while (i<j) putchar(*i++);
    return(k);
}
EOF15383
cat <<'EOF15384' >ntok.csh
# run "source ntok.csh" to add this alias to your C shell
# then run "ntok ray.c", for example, to count tokens
#
alias ntok "/lib/cpp \!:1 | sed '/^#/d' | squeeze -1 | wc -l"
alias tokf "/lib/cpp \!:1 | sed '/^#/d' | squeeze -1 | lam - -s \	 - -s \	 - -s \	 - -s \	 - > \!:1.tokf"
EOF15384
cat <<'EOF15385' >ray.h
/* ray.h for test1, first test scene */
#define DEPTH 3		/* max ray tree depth */
#define SIZE 32		/* resolution of picture in x and y */
#define AOV 25		/* total angle of view in degrees */
#define NSPHERE 5	/* number of spheres */

AMBIENT = {.02, .02, .02};	/* ambient light color */

/* sphere: x y z  r g b  rad  kd ks kt kl  ir */
SPHERE = {
     0., 6., .5,    1., 1., 1.,   .9,   .05, .2, .85, 0.,  1.7,
    -1., 8., -.5,   1., .5, .2,   1.,   .7, .3, 0., .05,   1.2,
     1., 8., -.5,   .1, .8, .8,   1.,   .3, .7, 0., 0.,    1.2,
     3., -6., 15.,  1., .8, 1.,   7.,   0., 0., 0., .6,    1.5,
    -3., -3., 12.,  .8, 1., 1.,   5.,   0., 0., 0., .5,    1.5,
};
EOF15385
cat <<'EOF15386' >test1.ap
32 32
5 5 5
5 5 5
5 5 5
5 5 5
5 5 5
5 5 5
5 5 5
5 5 5
5 5 5
5 5 5
5 5 5
5 5 5
13 14 15
13 14 15
14 15 16
14 15 16
17 17 19
25 19 17
25 19 17
25 19 17
24 18 16
5 5 5
5 5 5
5 5 5
5 5 5
5 5 5
5 5 5
5 5 5
5 5 5
5 5 5
5 5 5
5 5 5
5 5 5
5 5 5
5 5 5
5 5 5
5 5 5
5 5 5
5 5 5
5 5 5
5 5 5
5 5 5
11 12 13
12 13 14
15 26 31
15 25 29
16 38 41
16 32 34
17 17 18
75 41 27
94 51 32
49 34 23
54 36 24
57 38 24
23 17 15
5 5 5
5 5 5
5 5 5
5 5 5
5 5 5
5 5 5
5 5 5
5 5 5
5 5 5
5 5 5
5 5 5
5 5 5
5 5 5
5 5 5
5 5 5
5 5 5
5 5 5
5 5 5
13 29 34
14 28 33
16 46 50
16 43 47
16 39 42
15 33 36
17 17 18
17 17 18
17 16 18
81 44 28
98 53 32
110 59 35
120 63 36
60 40 24
63 41 24
5 5 5
5 5 5
5 5 5
5 5 5
5 5 5
5 5 5
5 5 5
5 5 5
5 5 5
5 5 5
5 5 5
5 5 5
5 5 5
5 5 5
5 5 5
5 5 5
13 29 35
13 28 33
16 47 51
16 43 48
15 39 43
15 33 36
36 40 42
36 41 42
36 41 42
46 39 47
46 39 47
83 45 28
101 54 32
114 60 35
124 65 37
62 41 24
65 42 24
5 5 5
5 5 5
5 5 5
5 5 5
5 5 5
5 5 5
5 5 5
5 5 5
5 5 5
5 5 5
5 5 5
5 5 5
5 5 5
5 5 5
12 29 35
15 50 55
15 47 52
15 44 48
15 40 43
14 33 36
35 40 41
35 40 41
35 40 41
35 40 41
45 39 46
45 39 46
45 39 46
83 45 28
104 55 32
118 62 35
129 67 37
138 71 38
68 43 23
5 5 5
5 5 5
5 5 5
5 5 5
5 5 5
5 5 5
5 5 5
5 5 5
5 5 5
5 5 5
5 5 5
5 5 5
5 5 5
14 51 57
14 48 54
14 45 49
14 40 44
13 33 36
15 15 16
34 39 40
34 39 41
34 39 41
34 39 41
45 38 46
45 38 46
45 38 45
15 14 16
85 46 28
108 57 32
122 64 35
134 69 37
144 74 39
5 5 5
5 5 5
5 5 5
5 5 5
5 5 5
5 5 5
5 5 5
5 5 5
5 5 5
5 5 5
5 5 5
5 5 5
12 46 52
13 50 55
13 46 51
13 41 46
13 33 37
14 14 15
14 14 15
14 14 15
34 39 40
34 39 40
44 38 45
44 38 45
44 38 45
14 14 15
14 14 15