minray.post

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

31 17 8
17 9 4
17 9 4
17 9 4
17 9 4
17 9 4
5 5 5
5 5 5
5 5 5
3 5 5
3 5 5
3 5 4
3 4 4
3 4 4
3 4 4
4 12 14
5 12 14
5 13 15
5 13 15
5 13 15
5 13 15
4 12 14
4 11 13
17 9 4
22 12 6
27 15 7
28 16 7
29 16 7
29 16 7
28 16 7
27 15 7
25 14 6
22 12 6
17 9 4
17 9 4
17 9 4
17 9 4
17 9 4
5 5 5
5 5 5
5 5 5
3 5 5
3 5 4
3 5 4
3 4 4
3 4 4
4 7 8
4 8 9
4 9 10
4 9 11
4 10 11
4 10 11
4 9 10
4 8 9
4 7 7
5 5 5
17 9 4
17 9 4
18 9 4
19 10 5
19 10 5
19 10 5
18 9 4
17 9 4
17 9 4
17 9 4
17 9 4
17 9 4
17 9 4
5 5 5
5 5 5
5 5 5
5 5 5
5 5 5
3 5 4
3 5 4
3 4 4
3 4 4
3 4 4
3 5 5
3 5 5
3 6 6
4 6 6
3 6 6
3 5 5
3 4 4
3 4 4
5 5 5
5 5 5
17 9 4
17 9 4
17 9 4
17 9 4
17 9 4
17 9 4
17 9 4
17 9 4
17 9 4
17 9 4
17 9 4
5 5 5
5 5 5
5 5 5
5 5 5
5 5 5
5 5 5
5 5 5
3 4 4
3 4 4
3 4 4
3 4 4
3 4 4
3 4 4
3 4 4
3 4 4
3 4 4
3 4 4
3 4 4
5 5 5
5 5 5
5 5 5
5 5 5
5 5 5
17 9 4
17 9 4
17 9 4
17 9 4
17 9 4
17 9 4
17 9 4
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
3 4 4
3 4 4
3 4 4
3 4 4
3 4 4
3 4 4
3 4 4
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
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
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
5 5 5
5 5 5
5 5 5
5 5 5
EOF15386
exit


Path: pixar!ph
From: [e-mail] (Paul Heckbert)
Newsgroups: comp.graphics
Subject: Winners of Minimal Ray Tracer Contest
Date: 20 Jun 87 06:03:25 GMT
Organization: Pixar -- Marin County, California

WINNERS OF THE MINIMAL RAY TRACER PROGRAMMING CONTEST
*****************************************************

The contest:
    The goal: write the shortest Whitted-style ray tracing program in C.
    Briefly, the rules were as follows: 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.  Deadline was 15 June 87.

    
I received entries from five people, some of whom sent two versions.
The entries I received all passed my validation tests and they were all
quite clever.  Joe Cychosz of Purdue won first place with an incredibly
minimal program of just 916 tokens.

PLACE   #TOKENS		AUTHOR				NOTES

	    *** GENUINE ENTRIES ***
  1	 916		Joe Cychosz, Purdue  		(compiler-dependent)
   1a	 932		Joe Cychosz, Purdue		(portable)
  2	 956		Darwyn Peachey, Saskatchewan	(portable)
  3	 981		Michel Burgess, Montreal	(portable)
  4	1003		Greg Ward, Berkeley		(portable)

	    *** HONORABLE MENTIONS ***
 c1	  10		Tony Apodaca, Pixar		(cheater)
 c2	  66		Greg Ward, Berkeley		(cheater)

Interestingly, the entries had nearly identical modularization into six
subroutines: main, trace, intersect-sphere, vector-normalize, vector-add,
and dot-product.  One person, Greg Ward, cleverly exploited a loophole in my
rules which allowed arbitrarily long character strings to count as a single
token, and submitted a program which writes a source file, compiles it, and
runs it!  Tony Apodaca used a different cheat: hiding the real program in an
unused part of the source file and compiling and running that program with
a single call to system().  His program is about as minimal as you can get:
10 tokens.  Programs from each of the entrants are included below.


So what did we learn from all this?

The first thing I learned is that there are a lot more dilettantes in
comp.graphics than real hackers.  Various people offered thoughts on why
the turnout was sparse:

    "The unwashed might think that the task is too difficult
    and the cognoscenti might think `I know I could do it, but it's
    too much trouble just for a contest.'"

    "We're all busy with previous hacking commitments."

    "Now if you had a `Get a job at Pixar Ray Tracer Contest', then
    I might be motivated to enter."
    
But one person obviously missed the spirit of the contest (and perhaps
of life itself):

    "For an up-front payment of $5000 and a 12% royalty on any sales of the
    product, I will consider submitting an entry.  My lawyers are Hughes,
    Gumaer, Bedolla and Diener of Santa Clara; please have your lawyers contact
    them regarding contractual terms."

Those who entered the contest also learned some repulsive C coding tricks:
 *  color = point: "struct {float r, g, b;}" -> "struct {float x, y, z;}"
 *  pass structures (not just pointers to structs) to allow vector expressions
 *  use global variables for return values
 *  no optimizations: trace specular and transmitted rays even if coeff=0!
 *  reuse variables!
 *  "for (i=0; i<n; i++)"  -->  "i = n; while (i--)"
 *  merge x and y loops into one (see joe.c)
 *  assume statics are initialized to 0
 *  "&sph[i]" -> "sph+i"
 *  choose just the right set of utility routines
 *  creative use of commas, e.g.: "if (a) {b;c;}"  -->  "if (a) b,c;"
 *  move assignments into expressions: "b = vdot(D, U = vcomb(-1., P, s->cen))"
cheats (non-portable C):
 *  eliminate semicolons in struct def: "struct {int a;}" -> "struct {int a}"
 *  assume right-to-left argument evaluation order

winner of the most shocking cheat award, a little gem by Joe Cychosz:
 *  "printf("%f %f %f\n", pt.x, pt.y, pt.z);"  -->  "printf("%f %f %f\n", pt);"

Since Joe Cychosz said this was only his second C program(!), I asked him
how he managed to do so well.  Excerpts of his response:

    "My thesis work is `Global Ray Tracing in a Vector Processing Environment.'
    ... My primary program language is FORTRAN and COMPASS (CDC assembly)
    for the CYBER 205 and the CYBER 800s ...
    This is an interesting way to learn C.  I spent the weekend looking
    through Kernighan & Ritchie trying to determine if what I wanted to do
    was legal C ...  Finally, ... Kirk Smith found 12 tokens while we were
    sitting in a bar..."


But if you were expecting a useful ray tracing program out of this, a warning:

As one would expect of any "minimal" program, the winning program is cryptic,
"tense", inefficient, unmaintainable, and nearly useless, except as a source
of C coding tricks.  Remember all the limitations of this contest:
no antialiasing, spheres only, a bizarre shading model, and i/o formats out of
the neanderthal age.  So don't be surprised that the program is slow and the
output contoured and jaggy.  If you want a good ray tracer, start from scratch!


I'd like to thank everyone who participated in the contest, especially
Darwyn Peachey, who helped me debug the rules, and Paul Haeberli, who hatched
this wacky idea with me.  Let's see some more programming contests here, eh?

Paul Heckbert
Pixar				415-499-3600
P.O. Box 13719			UUCP: {sun,ucbvax}!pixar!ph
San Rafael, CA 94913		ARPA: [e-mail]

----
The header files for three test scenes are included below along with five
different ray tracers.  To compile and run one of these entries, run, e.g.:

	cp test1.h ray.h
	cc -o joe joe.c -lm

Please MAIL any minimizations of these programs to me and I'll post to the net.
----

# to unpack, cut here and run the following through sh
# shell archive of joe.c darwyn.c michel.c tony.c greg.c test1.h test2.h test3.h
#
cat <<'EOF27903' >joe.c
/*	ray.c - Minimal ray tracing program.				*/
/*									*/
/*	Joe Cychosz							*/
/*									*/
/*	work:	Purdue University CADLAB /				*/
/*		Control Data Corporation				*/
/*		Potter Engineering Center				*/
/*		W. Lafayette, IN  47907					*/
/*									*/
/*	phone:	[phone]						*/
/*									*/
/*	arpa:	[e-mail]				*/
/*	uucp:	pur-ee!3ksnn64						*/
/*									*/
/*	experience: 13 years programing,				*/
/*		    this is my second C program.			*/
/*									*/
/*	strategy:							*/
/*		1)  Express shading calculations as functions.		*/
/*		2)  All vector expressions are vector triads (a + b*s)	*/
/*		3)  Do a critical path analysis of variables and map to */
/*		    temporarys with #define's.  This keeps the code 	*/
/*		    readable.						*/
/*		4)  Have Kirk Smith find 14 more tokens.		*/
/*		5)  This version is machine/compiler dependent in that	*/
/*		    it assumes function parameters are evaluated from	*/
/*		    right to left.					*/


typedef	struct	{ double x, y, z;
		} vector;

typedef	struct	{ vector center,	/* center coordinate		*/
			 color;		/* surface color		*/
		  double radius,	/* radius			*/
			 kd,		/* diffuse coefficient		*/
			 ks,		/* coefficient of reflection	*/
			 kt,		/* coefficient of transmission	*/
			 kl,		/* light source intensity	*/
			 ir;		/* index of refraction		*/
		} sphere;


#define	SPHERE	sphere spheres[]	/* "The Sceen"			*/
#define AMBIENT	vector ambint		/* ambient light color		*/

#define PINF	100000000.		/* positive infinity		*/
#define PINF2	200000000.		/* second positive infinity	*/
#define EPS	0.001			/* used to detect self-intersect*/


/*	include file defining the sceen and viewing parameters		*/

#include	"ray.h"


/*	global variables		*/

double	sqrt(), tan(),			/* math functions from <math.h>	*/
	dist,				/* distance to closest sphere	*/
	size2 = SIZE/2,			/* SIZE / 2			*/

	s0, s1, s2;			/* temporary scalars		*/

vector	origin,				/* eye location and zeros	*/
	c,				/* direction cosine of pixel ray*/
					/* and pixel color		*/

	v0, v1;				/* temporary vectors		*/

sphere	*sph,				/* closest sphere, = 0 if null	*/
	*s;				/* intsph - current sphere	*/



/*	basic math routines						*/


double	dot (a,b)		/* compute dot product		(a.b)	*/
vector	a, b;
{
	return  a.x*b.x + a.y*b.y + a.z*b.z ;
}


vector	vaddm (a,b,s)		/* compute vector triad		(a+b*s)	*/
vector	a, b;
double	s;
{
	a.x += b.x * s;
	a.y += b.y * s;
	a.z += b.z * s;
	return a ;
}


vector	unitize (a)		/* normalize vector		(a/|a|)	*/
vector	a;
{
	return  vaddm ( origin, a, 1.0/sqrt(dot(a,a)) ) ;
}


	intsph (base,cosine)
vector	base,			/* base of the ray 			*/
	cosine;			/* direction cosines for the ray	*/
{
#define	d	v0
#define	bsq	s0
#define	disc	s1
#define root	s2		/* distance to intersected sphere	*/

	dist = PINF;		/* closest sphere is at infinity	*/
	sph  = 0;		/* default to no sphere intersected	*/

	for (s = spheres; s < spheres+NSPHERE; s++)

	    bsq  = - dot (d = vaddm(base,s->center,-1.),cosine),
	    disc = bsq*bsq - dot (d,d) + s->radius*s->radius,
	    disc = disc > 0. ? sqrt(disc) : PINF2,
	    root = bsq - disc,
	    root = root < EPS ? bsq + disc : root,
	    dist = root > EPS && root < dist ? sph = s, root : dist
	;
}


vector	shade (base,cosine,depth)
vector	base,			/* base of the ray 			*/
	cosine;			/* directoin cosines for the ray	*/
/*int	depth;			/* depth in the shade tree		*/
{
	sphere	*p,		/* visible sphere for the ray		*/
		*light =	/* current light source for shadow tests*/
		       spheres;
	vector	hitpt,		/* hit point on the visible sphere	*/
		norm,		/* surface normal in direction of ray	*/
		sint;		/* diffuse illumination intensity	*/
	double	n12,		/* relative index of refraction		*/
		costh;
#define a	v0
#define	scos	v1		/* direction cosine for shadow ray	*/
#define	q	s0		/* N.L shading term			*/
#define kf	s1

	if  (!depth) return origin ;

	intsph (base,cosine);

	if  (p = sph) {

	    costh = - dot (cosine,
			   norm = unitize(vaddm(
				  hitpt = vaddm(base,cosine,dist),
				  p->center,-1.))
		          );

	    n12   = 1. / p->ir;

	    if  (costh < 0.) 		/* if ray originates from within*/

		norm = vaddm(origin,norm,-1.), n12 = p->ir, costh = -costh
		;

	    sint  = ambint; 		/* initial intensity = ambient	*/

	    while ( light < spheres+NSPHERE )
	
		intsph (hitpt,
			scos = unitize(vaddm(light->center,hitpt,-1.))
		       ),
		q    = dot (norm,scos),
		sint = vaddm (sint,sph->color,
			      sph == light++ && q > 0. ? sph->kl*q : 0.)
	    ;

	    kf    = 1.0 - n12*n12 *  dot(a,
					 a = vaddm (cosine,norm,costh)
					);

/*	    evaluate the shading function				*/
/*									*/
/*		cs  = shade (hitpt,R,--depth) ;		reflected ray	*/
/*		ct  = shade (hitpt,T,  depth) ;		refracted ray	*/
/*									*/
/*		c = p->kd * p->color * (ambint + shadow) +		*/
/*		    p->ks * cs + p->kt * ct + p->kl * p->color ;	*/

	
	    sint.x *= p->color.x;
	    sint.y *= p->color.y;
	    sint.z *= p->color.z;

	    depth--;

	    return			/* yep folks, it's all here	*/
	        vaddm(vaddm(vaddm(vaddm(
		     origin,sint,
		     p->kd)
		,
		     shade(hitpt,
		           vaddm(cosine,norm,2.*costh),
			   depth),
		     p->ks)
		,
		     kf > 0. ? shade(hitpt,
	    		   vaddm(vaddm(origin,norm,-sqrt(kf)),a,n12),
			   depth) : origin,
		     p->kt)
		,
		p->color,p->kl)
		;
	} else
	    return ambint ;
}


main (argc) 
/*	int	argc;			/* pixel number  		*/
{

	argc  = 0;
	printf ("%d %d\n", SIZE, SIZE);

	while ( argc < SIZE*SIZE )

	    c.x = argc % SIZE - size2,
	    c.y = size2 / tan( AOV / 114.59166 ),
	    c.z = size2 - argc++ / SIZE,

	    c = vaddm (origin,  shade (origin,unitize(c),DEPTH), 255.),

	    printf ("%.0f %.0f %.0f\n", c)

	;
}	/* send laywers, guns, and money, get me out of this...		*/
EOF27903
cat <<'EOF27904' >darwyn.c
/*
 * Short ray tracer written with the goal of minimizing the total number