--- ray/src/rt/raytrace.c	1989/02/02 10:41:34	1.1
+++ ray/src/rt/raytrace.c	1993/01/26 09:28:00	2.3
@@ -1,4 +1,4 @@
-/* Copyright (c) 1986 Regents of the University of California */
+/* Copyright (c) 1991 Regents of the University of California */
 
 #ifndef lint
 static char SCCSid[] = "$SunId$ LBL";
@@ -16,14 +16,26 @@ static char SCCSid[] = "$SunId$ LBL";
 
 #include  "otypes.h"
 
+#include  "otspecial.h"
+
+#define  MAXCSET	((MAXSET+1)*2-1)	/* maximum check set size */
+
 extern CUBE  thescene;			/* our scene */
 extern int  maxdepth;			/* maximum recursion depth */
 extern double  minweight;		/* minimum ray weight */
+extern int  do_irrad;			/* compute irradiance? */
 
-long  nrays = 0L;			/* number of rays traced */
+long  raynum = 0L;			/* next unique ray number */
+long  nrays = 0L;			/* number of calls to localhit */
 
-#define  MAXLOOP	32		/* modifier loop detection */
+static FLOAT  Lambfa[5] = {PI, PI, PI, 0.0, 0.0};
+OBJREC  Lamb = {
+	OVOID, MAT_PLASTIC, "Lambertian",
+	{0, 5, NULL, Lambfa}, NULL,
+};					/* a Lambertian surface */
 
+#define  MAXLOOP	128		/* modifier loop detection */
+
 #define  RAYHIT		(-1)		/* return value for intercepted ray */
 
 
@@ -38,6 +50,7 @@ double  rw;
 		r->crtype = r->rtype = rt;
 		r->rsrc = -1;
 		r->clipset = NULL;
+		r->revf = raytrace;
 	} else {				/* spawned ray */
 		r->rlvl = ro->rlvl;
 		if (rt & RAYREFL) {
@@ -48,32 +61,37 @@ double  rw;
 			r->rsrc = ro->rsrc;
 			r->clipset = ro->newcset;
 		}
+		r->revf = ro->revf;
 		r->rweight = ro->rweight * rw;
 		r->crtype = ro->crtype | (r->rtype = rt);
 		VCOPY(r->rorg, ro->rop);
 	}
-	r->rno = nrays;
+	rayclear(r);
+	return(r->rlvl <= maxdepth && r->rweight >= minweight ? 0 : -1);
+}
+
+
+rayclear(r)			/* clear a ray for (re)evaluation */
+register RAY  *r;
+{
+	r->rno = raynum++;
 	r->newcset = r->clipset;
 	r->ro = NULL;
 	r->rot = FHUGE;
-	r->ros = 1.0; setident4(r->rox);
 	r->pert[0] = r->pert[1] = r->pert[2] = 0.0;
 	setcolor(r->pcol, 1.0, 1.0, 1.0);
 	setcolor(r->rcol, 0.0, 0.0, 0.0);
-	return(r->rlvl <= maxdepth && r->rweight >= minweight ? 0 : -1);
+	r->rt = 0.0;
 }
 
 
-rayvalue(r)			/* compute a ray's value */
-register RAY  *r;
+raytrace(r)			/* trace a ray and compute its value */
+RAY  *r;
 {
 	extern int  (*trace)();
 
 	if (localhit(r, &thescene))
-		if (r->clipset != NULL && inset(r->clipset, r->ro->omod))
-			raytrans(r);		/* object is clipped */
-		else
-			rayshade(r, r->ro->omod);
+		raycont(r);
 	else if (sourcehit(r))
 		rayshade(r, r->ro->omod);
 
@@ -82,8 +100,18 @@ register RAY  *r;
 }
 
 
+raycont(r)			/* check for clipped object and continue */
+register RAY  *r;
+{
+	if (r->clipset != NULL && inset(r->clipset, r->ro->omod))
+		raytrans(r);
+	else
+		rayshade(r, r->ro->omod);
+}
+
+
 raytrans(r)			/* transmit ray as is */
-RAY  *r;
+register RAY  *r;
 {
 	RAY  tr;
 
@@ -91,6 +119,7 @@ RAY  *r;
 		VCOPY(tr.rdir, r->rdir);
 		rayvalue(&tr);
 		copycolor(r->rcol, tr.rcol);
+		r->rt = r->rot + tr.rt;
 	}
 }
 
@@ -103,15 +132,27 @@ int  mod;
 	register OBJREC  *m;
 					/* check for infinite loop */
 	if (depth++ >= MAXLOOP)
-		objerror(r->ro, USER, "material loop");
+		objerror(r->ro, USER, "possible modifier loop");
+	r->rt = r->rot;			/* set effective ray length */
 	for ( ; mod != OVOID; mod = m->omod) {
 		m = objptr(mod);
+		/****** unnecessary test since modifier() is always called
 		if (!ismodifier(m->otype)) {
 			sprintf(errmsg, "illegal modifier \"%s\"", m->oname);
 			error(USER, errmsg);
 		}
+		******/
+					/* hack for irradiance calculation */
+		if (do_irrad && !(r->crtype & ~(PRIMARY|TRANS))) {
+			if (irr_ignore(m->otype)) {
+				depth--;
+				raytrans(r);
+				return;
+			}
+			if (!islight(m->otype))
+				m = &Lamb;
+		}
 		(*ofun[m->otype].funp)(m, r);	/* execute function */
-		m->lastrno = r->rno;
 		if (ismaterial(m->otype)) {	/* materials call raytexture */
 			depth--;
 			return;		/* we're done */
@@ -138,7 +179,6 @@ int  mod;
 			error(USER, errmsg);
 		}
 		(*ofun[m->otype].funp)(m, r);
-		m->lastrno = r->rno;
 	}
 	depth--;			/* end here */
 }
@@ -204,7 +244,7 @@ register RAY  *r;
 	 *  still fraught with problems since reflected rays and similar
 	 *  directions calculated from the surface normal may spawn rays behind
 	 *  the surface.  The only solution is to curb textures at high
-	 *  incidence (Rdot << 1).
+	 *  incidence (namely, keep DOT(rdir,pert) < Rdot).
 	 */
 
 	for (i = 0; i < 3; i++)
@@ -225,6 +265,42 @@ register RAY  *r;
 }
 
 
+newrayxf(r)			/* get new tranformation matrix for ray */
+RAY  *r;
+{
+	static struct xfn {
+		struct xfn  *next;
+		FULLXF  xf;
+	}  xfseed = { &xfseed }, *xflast = &xfseed;
+	register struct xfn  *xp;
+	register RAY  *rp;
+
+	/*
+	 * Search for transform in circular list that
+	 * has no associated ray in the tree.
+	 */
+	xp = xflast;
+	for (rp = r->parent; rp != NULL; rp = rp->parent)
+		if (rp->rox == &xp->xf) {		/* xp in use */
+			xp = xp->next;			/* move to next */
+			if (xp == xflast) {		/* need new one */
+				xp = (struct xfn *)bmalloc(sizeof(struct xfn));
+				if (xp == NULL)
+					error(SYSTEM,
+						"out of memory in newrayxf");
+							/* insert in list */
+				xp->next = xflast->next;
+				xflast->next = xp;
+				break;			/* we're done */
+			}
+			rp = r;			/* start check over */
+		}
+					/* got it */
+	r->rox = &xp->xf;
+	xflast = xp;
+}
+
+
 flipsurface(r)			/* reverse surface orientation */
 register RAY  *r;
 {
@@ -242,29 +318,31 @@ localhit(r, scene)		/* check for hit in the octree */
 register RAY  *r;
 register CUBE  *scene;
 {
+	OBJECT  cxset[MAXCSET+1];	/* set of checked objects */
 	FVECT  curpos;			/* current cube position */
-	int  mpos, mneg;		/* sign flags */
+	int  sflags;			/* sign flags */
 	double  t, dt;
 	register int  i;
 
 	nrays++;			/* increment trace counter */
-
-	mpos = mneg = 0;
+	sflags = 0;
 	for (i = 0; i < 3; i++) {
 		curpos[i] = r->rorg[i];
 		if (r->rdir[i] > FTINY)
-			mpos |= 1 << i;
+			sflags |= 1 << i;
 		else if (r->rdir[i] < -FTINY)
-			mneg |= 1 << i;
+			sflags |= 0x10 << i;
 	}
+	if (sflags == 0)
+		error(CONSISTENCY, "zero ray direction in localhit");
 	t = 0.0;
 	if (!incube(scene, curpos)) {
 					/* find distance to entry */
 		for (i = 0; i < 3; i++) {
 					/* plane in our direction */
-			if (mpos & 1<<i)
+			if (sflags & 1<<i)
 				dt = scene->cuorg[i];
-			else if (mneg & 1<<i)
+			else if (sflags & 0x10<<i)
 				dt = scene->cuorg[i] + scene->cusize;
 			else
 				continue;
@@ -281,24 +359,25 @@ register CUBE  *scene;
 		if (!incube(scene, curpos))	/* non-intersecting ray */
 			return(0);
 	}
-	return(raymove(curpos, mpos, mneg, r, scene) == RAYHIT);
+	cxset[0] = 0;
+	return(raymove(curpos, cxset, sflags, r, scene) == RAYHIT);
 }
 
 
 static int
-raymove(pos, plus, minus, r, cu)	/* check for hit as we move */
-FVECT  pos;			/* modified */
-int  plus, minus;		/* direction indicators to speed tests */
+raymove(pos, cxs, dirf, r, cu)		/* check for hit as we move */
+FVECT  pos;			/* current position, modified herein */
+OBJECT  *cxs;			/* checked objects, modified by checkhit */
+int  dirf;			/* direction indicators to speed tests */
 register RAY  *r;
 register CUBE  *cu;
 {
 	int  ax;
 	double  dt, t;
-	register int  sgn;
 
 	if (istree(cu->cutree)) {		/* recurse on subcubes */
 		CUBE  cukid;
-		register int  br;
+		register int  br, sgn;
 
 		cukid.cusize = cu->cusize * 0.5;	/* find subcube */
 		VCOPY(cukid.cuorg, cu->cuorg);
@@ -317,45 +396,44 @@ register CUBE  *cu;
 		}
 		for ( ; ; ) {
 			cukid.cutree = octkid(cu->cutree, br);
-			if ((ax = raymove(pos,plus,minus,r,&cukid)) == RAYHIT)
+			if ((ax = raymove(pos,cxs,dirf,r,&cukid)) == RAYHIT)
 				return(RAYHIT);
 			sgn = 1 << ax;
-			if (sgn & minus)		/* negative axis? */
-				if (sgn & br) {
-					cukid.cuorg[ax] -= cukid.cusize;
-					br &= ~sgn;
-				} else
-					return(ax);	/* underflow */
-			else
+			if (sgn & dirf)			/* positive axis? */
 				if (sgn & br)
 					return(ax);	/* overflow */
 				else {
 					cukid.cuorg[ax] += cukid.cusize;
 					br |= sgn;
 				}
+			else
+				if (sgn & br) {
+					cukid.cuorg[ax] -= cukid.cusize;
+					br &= ~sgn;
+				} else
+					return(ax);	/* underflow */
 		}
 		/*NOTREACHED*/
 	}
-	if (isfull(cu->cutree) && checkhit(r, cu))
+	if (isfull(cu->cutree) && checkhit(r, cu, cxs))
 		return(RAYHIT);
 					/* advance to next cube */
-	sgn = plus | minus;
-	if (sgn&1) {
-		dt = plus&1 ? cu->cuorg[0] + cu->cusize : cu->cuorg[0];
+	if (dirf&0x11) {
+		dt = dirf&1 ? cu->cuorg[0] + cu->cusize : cu->cuorg[0];
 		t = (dt - pos[0])/r->rdir[0];
 		ax = 0;
 	} else
 		t = FHUGE;
-	if (sgn&2) {
-		dt = plus&2 ? cu->cuorg[1] + cu->cusize : cu->cuorg[1];
+	if (dirf&0x22) {
+		dt = dirf&2 ? cu->cuorg[1] + cu->cusize : cu->cuorg[1];
 		dt = (dt - pos[1])/r->rdir[1];
 		if (dt < t) {
 			t = dt;
 			ax = 1;
 		}
 	}
-	if (sgn&4) {
-		dt = plus&4 ? cu->cuorg[2] + cu->cusize : cu->cuorg[2];
+	if (dirf&0x44) {
+		dt = dirf&4 ? cu->cuorg[2] + cu->cusize : cu->cuorg[2];
 		dt = (dt - pos[2])/r->rdir[2];
 		if (dt < t) {
 			t = dt;
@@ -370,24 +448,55 @@ register CUBE  *cu;
 
 
 static
-checkhit(r, cu)			/* check for hit in full cube */
+checkhit(r, cu, cxs)		/* check for hit in full cube */
 register RAY  *r;
 CUBE  *cu;
+OBJECT  *cxs;
 {
 	OBJECT  oset[MAXSET+1];
 	register OBJREC  *o;
 	register int  i;
 
 	objset(oset, cu->cutree);
+	checkset(oset, cxs);			/* eliminate double-checking */
 	for (i = oset[0]; i > 0; i--) {
 		o = objptr(oset[i]);
-		if (o->lastrno == r->rno)		/* checked already? */
-			continue;
 		(*ofun[o->otype].funp)(o, r);
-		o->lastrno = r->rno;
 	}
 	if (r->ro == NULL)
 		return(0);			/* no scores yet */
 
 	return(incube(cu, r->rop));		/* hit OK if in current cube */
+}
+
+
+static
+checkset(os, cs)		/* modify checked set and set to check */
+register OBJECT  *os;			/* os' = os - cs */
+register OBJECT  *cs;			/* cs' = cs + os */
+{
+	OBJECT  cset[MAXCSET+MAXSET+1];
+	register int  i, j;
+	int  k;
+					/* copy os in place, cset <- cs */
+	cset[0] = 0;
+	k = 0;
+	for (i = j = 1; i <= os[0]; i++) {
+		while (j <= cs[0] && cs[j] < os[i])
+			cset[++cset[0]] = cs[j++];
+		if (j > cs[0] || os[i] != cs[j]) {	/* object to check */
+			os[++k] = os[i];
+			cset[++cset[0]] = os[i];
+		}
+	}
+	if (!(os[0] = k))		/* new "to check" set size */
+		return;			/* special case */
+	while (j <= cs[0])		/* get the rest of cs */
+		cset[++cset[0]] = cs[j++];
+	if (cset[0] > MAXCSET)		/* truncate "checked" set if nec. */
+		cset[0] = MAXCSET;
+	/* setcopy(cs, cset); */	/* copy cset back to cs */
+	os = cset;
+	for (i = os[0]; i-- >= 0; )
+		*cs++ = *os++;
 }