Merge remote-tracking branch 'upstream/master'

4 files changed, 1430 insertions, 1430 deletions

diff --git a/mp/src/raytrace/raytrace.cpp b/mp/src/raytrace/raytrace.cpp
index 142220e2..7b951dfb 100644
--- a/mp/src/raytrace/raytrace.cpp
+++ b/mp/src/raytrace/raytrace.cpp
@@ -1,901 +1,901 @@
-//========= Copyright Valve Corporation, All rights reserved. ============//

-// $Id$

-

-#include "raytrace.h"

-#include <filesystem_tools.h>

-#include <cmdlib.h>

-#include <stdio.h>

-

-static bool SameSign(float a, float b)

-{

-	int32 aa=*((int *) &a);

-	int32 bb=*((int *) &b);

-	return ((aa^bb)&0x80000000)==0;

-}

-

-int FourRays::CalculateDirectionSignMask(void) const

-{

-	// this code treats the floats as integers since all it cares about is the sign bit and

-	// floating point compares suck.

-

-	int ret;

-	int ormask;

-	int andmask;

-	int32 const *treat_as_int=((int32 const *) (&direction));

-

-	ormask=andmask=*(treat_as_int++);

-	ormask|=*treat_as_int;

-	andmask&=*(treat_as_int++);

-	ormask|=*(treat_as_int);

-	andmask&=*(treat_as_int++);

-	ormask|=*(treat_as_int);

-	andmask&=*(treat_as_int++);

-	if (ormask>=0)

-		ret=0;

-	else

-	{

-		if (andmask<0)

-			ret=1;

-		else return -1;

-	}

-	ormask=andmask=*(treat_as_int++);

-	ormask|=*treat_as_int;

-	andmask&=*(treat_as_int++);

-	ormask|=*(treat_as_int);

-	andmask&=*(treat_as_int++);

-	ormask|=*(treat_as_int);

-	andmask&=*(treat_as_int++);

-	if (ormask<0)

-	{

-		if (andmask<0)

-			ret|=2;

-		else return -1;

-	}

-	ormask=andmask=*(treat_as_int++);

-	ormask|=*treat_as_int;

-	andmask&=*(treat_as_int++);

-	ormask|=*(treat_as_int);

-	andmask&=*(treat_as_int++);

-	ormask|=*(treat_as_int);

-	andmask&=*(treat_as_int++);

-	if (ormask<0)

-	{

-		if (andmask<0)

-			ret|=4;

-		else return -1;

-	}

-	return ret;

-}

-

-

-

-

-void RayTracingEnvironment::MakeRoomForTriangles( int ntris )

-{

-	//OptimizedTriangleList.EnsureCapacity( ntris );

-	if (! (Flags & RTE_FLAGS_DONT_STORE_TRIANGLE_COLORS))

-		TriangleColors.EnsureCapacity( ntris );

-}

-

-

-void RayTracingEnvironment::AddTriangle(int32 id, const Vector &v1,

-										const Vector &v2, const Vector &v3,

-										const Vector &color)

-{

-	AddTriangle( id, v1, v2, v3, color, 0, 0 );

-}

-

-void RayTracingEnvironment::AddTriangle(int32 id, const Vector &v1,

-										const Vector &v2, const Vector &v3,

-										const Vector &color, uint16 flags, int32 materialIndex)

-{

-	CacheOptimizedTriangle tmptri;

-	tmptri.m_Data.m_GeometryData.m_nTriangleID = id;

-	tmptri.Vertex( 0 ) = v1;

-	tmptri.Vertex( 1 ) = v2;

-	tmptri.Vertex( 2 ) = v3;

-	tmptri.m_Data.m_GeometryData.m_nFlags = flags;

-	OptimizedTriangleList.AddToTail(tmptri);

-	if (! ( Flags & RTE_FLAGS_DONT_STORE_TRIANGLE_COLORS) )

-		TriangleColors.AddToTail(color);

-	if ( !( Flags & RTE_FLAGS_DONT_STORE_TRIANGLE_MATERIALS) )

-		TriangleMaterials.AddToTail(materialIndex);

-// 	printf("add triange from (%f %f %f),(%f %f %f),(%f %f %f) id %d\n",

-// 		   XYZ(v1),XYZ(v2),XYZ(v3),id);

-}

-

-void RayTracingEnvironment::AddQuad(

-	int32 id, const Vector &v1, const Vector &v2, const Vector &v3,

-	const Vector &v4,							// specify vertices in cw or ccw order

-	const Vector &color)

-{

-	AddTriangle(id,v1,v2,v3,color);

-	AddTriangle(id+1,v1,v3,v4,color);

-}

-

-

-void RayTracingEnvironment::AddAxisAlignedRectangularSolid(int id,Vector minc, Vector maxc,

-														   const Vector &color)

-{

-

-	// "far" face

-	AddQuad(id,

-			Vector(minc.x,maxc.y,maxc.z),

-			Vector(maxc.x,maxc.y,maxc.z),Vector(maxc.x,minc.y,maxc.z),

-			Vector(minc.x,minc.y,maxc.z),color);

-	// "near" face

-	AddQuad(id,

-			Vector(minc.x,maxc.y,minc.z),

-			Vector(maxc.x,maxc.y,minc.z),Vector(maxc.x,minc.y,minc.z),

-			Vector(minc.x,minc.y,minc.z),color);

-

-	// "left" face

-	AddQuad(id,

-			Vector(minc.x,maxc.y,maxc.z),

-			Vector(minc.x,maxc.y,minc.z),

-			Vector(minc.x,minc.y,minc.z),

-			Vector(minc.x,minc.y,maxc.z),color);

-	// "right" face

-	AddQuad(id,

-			Vector(maxc.x,maxc.y,maxc.z),

-			Vector(maxc.x,maxc.y,minc.z),

-			Vector(maxc.x,minc.y,minc.z),

-			Vector(maxc.x,minc.y,maxc.z),color);

-	

-	// "top" face

-	AddQuad(id,

-			Vector(minc.x,maxc.y,maxc.z),

-			Vector(maxc.x,maxc.y,maxc.z),

-			Vector(maxc.x,maxc.y,minc.z),

-			Vector(minc.x,maxc.y,minc.z),color);

-	// "bot" face

-	AddQuad(id,

-			Vector(minc.x,minc.y,maxc.z),

-			Vector(maxc.x,minc.y,maxc.z),

-			Vector(maxc.x,minc.y,minc.z),

-			Vector(minc.x,minc.y,minc.z),color);

-}

-

-

-

-static Vector GetEdgeEquation(Vector p1, Vector p2, int c1, int c2, Vector InsidePoint)

-{

-	float nx=p1[c2]-p2[c2];

-	float ny=p2[c1]-p1[c1];

-	float d=-(nx*p1[c1]+ny*p1[c2]);

-// 	assert(fabs(nx*p1[c1]+ny*p1[c2]+d)<0.01);

-// 	assert(fabs(nx*p2[c1]+ny*p2[c2]+d)<0.01);

-

-	// use the convention that negative is "outside"

-	float trial_dist=InsidePoint[c1]*nx+InsidePoint[c2]*ny+d;

-	if (trial_dist<0)

-	{

-		nx = -nx;

-		ny = -ny;

-		d = -d;

-		trial_dist = -trial_dist;

-	}

-	nx /= trial_dist;										// scale so that it will be =1.0 at the oppositve vertex

-	ny /= trial_dist;

-	d /= trial_dist;

-

-	return Vector(nx,ny,d);

-}

-

-void CacheOptimizedTriangle::ChangeIntoIntersectionFormat(void)

-{

-	// lose the vertices and use edge equations instead

-

-	// grab the whole original triangle to we don't overwrite it

-	TriGeometryData_t srcTri = m_Data.m_GeometryData;

-

-	m_Data.m_IntersectData.m_nFlags = srcTri.m_nFlags;

-	m_Data.m_IntersectData.m_nTriangleID = srcTri.m_nTriangleID;

-

-	Vector p1 = srcTri.Vertex( 0 );

-	Vector p2 = srcTri.Vertex( 1 );

-	Vector p3 = srcTri.Vertex( 2 );

-

-	Vector e1 = p2 - p1;

-	Vector e2 = p3 - p1;

-

-	Vector N = e1.Cross( e2 );

-	N.NormalizeInPlace();

-	// now, determine which axis to drop

-	int drop_axis = 0;

-	for(int c=1 ; c<3 ; c++)

-		if ( fabs(N[c]) > fabs( N[drop_axis] ) )

-			drop_axis = c;

-

-	m_Data.m_IntersectData.m_flD = N.Dot( p1 );

-	m_Data.m_IntersectData.m_flNx = N.x;

-	m_Data.m_IntersectData.m_flNy = N.y;

-	m_Data.m_IntersectData.m_flNz = N.z;

-

-	// decide which axes to keep

-	int nCoordSelect0 = ( drop_axis + 1 ) % 3;

-	int nCoordSelect1 = ( drop_axis + 2 ) % 3;

-

-	m_Data.m_IntersectData.m_nCoordSelect0 = nCoordSelect0;

-	m_Data.m_IntersectData.m_nCoordSelect1 = nCoordSelect1;

-

-

-	Vector edge1 = GetEdgeEquation( p1, p2, nCoordSelect0, nCoordSelect1, p3 );

-	m_Data.m_IntersectData.m_ProjectedEdgeEquations[0] = edge1.x;

-	m_Data.m_IntersectData.m_ProjectedEdgeEquations[1] = edge1.y;

-	m_Data.m_IntersectData.m_ProjectedEdgeEquations[2] = edge1.z;

-

-	Vector edge2 = GetEdgeEquation( p2, p3, nCoordSelect0, nCoordSelect1, p1 );

-	m_Data.m_IntersectData.m_ProjectedEdgeEquations[3] = edge2.x;

-	m_Data.m_IntersectData.m_ProjectedEdgeEquations[4] = edge2.y;

-	m_Data.m_IntersectData.m_ProjectedEdgeEquations[5] = edge2.z;

-

-

-}

-

-int n_intersection_calculations=0;

-

-int CacheOptimizedTriangle::ClassifyAgainstAxisSplit(int split_plane, float split_value)

-{

-	// classify a triangle against an axis-aligned plane

-	float minc=Vertex(0)[split_plane];

-	float maxc=minc;

-	for(int v=1;v<3;v++)

-	{

-		minc=min(minc,Vertex(v)[split_plane]);

-		maxc=max(maxc,Vertex(v)[split_plane]);

-	}

-

-	if (minc>=split_value)

-		return PLANECHECK_POSITIVE;

-	if (maxc<=split_value)

-		return PLANECHECK_NEGATIVE;

-	if (minc==maxc)

-		return PLANECHECK_POSITIVE;

-	return PLANECHECK_STRADDLING;

-}

-

-#define MAILBOX_HASH_SIZE 256

-#define MAX_TREE_DEPTH 21

-#define MAX_NODE_STACK_LEN (40*MAX_TREE_DEPTH)

-

-struct NodeToVisit {

-	CacheOptimizedKDNode const *node;

-	fltx4 TMin;

-	fltx4 TMax;

-};

-

-

-static fltx4 FourEpsilons={1.0e-10,1.0e-10,1.0e-10,1.0e-10};

-static fltx4 FourZeros={1.0e-10,1.0e-10,1.0e-10,1.0e-10};

-static fltx4 FourNegativeEpsilons={-1.0e-10,-1.0e-10,-1.0e-10,-1.0e-10};

-

-static float BoxSurfaceArea(Vector const &boxmin, Vector const &boxmax)

-{

-	Vector boxdim=boxmax-boxmin;

-	return 2.0*((boxdim[0]*boxdim[2])+(boxdim[0]*boxdim[1])+(boxdim[1]*boxdim[2]));

-}

-

-void RayTracingEnvironment::Trace4Rays(const FourRays &rays, fltx4 TMin, fltx4 TMax,

-									   RayTracingResult *rslt_out,

-									   int32 skip_id, ITransparentTriangleCallback *pCallback)

-{

-	int msk=rays.CalculateDirectionSignMask();

-	if (msk!=-1)

-		Trace4Rays(rays,TMin,TMax,msk,rslt_out,skip_id, pCallback);

-	else

-	{

-		// sucky case - can't trace 4 rays at once. in the worst case, need to trace all 4

-		// separately, but usually we will still get 2x, Since our tracer only does 4 at a

-		// time, we will have to cover up the undesired rays with the desired ray

-

-		//!! speed!! there is room for some sse-ization here

-		FourRays tmprays;

-		tmprays.origin=rays.origin;

-

-		uint8 need_trace[4]={1,1,1,1};

-		for(int try_trace=0;try_trace<4;try_trace++)

-		{

-			if (need_trace[try_trace])

-			{

-				need_trace[try_trace]=2;			// going to trace it

-				// replicate the ray being traced into all 4 rays

-				tmprays.direction.x=ReplicateX4(rays.direction.X(try_trace));

-				tmprays.direction.y=ReplicateX4(rays.direction.Y(try_trace));

-				tmprays.direction.z=ReplicateX4(rays.direction.Z(try_trace));

-				// now, see if any of the other remaining rays can be handled at the same time.

-				for(int try2=try_trace+1;try2<4;try2++)

-					if (need_trace[try2])

-					{

-						if (

-							SameSign(rays.direction.X(try2),

-									 rays.direction.X(try_trace)) &&

-							SameSign(rays.direction.Y(try2),

-									 rays.direction.Y(try_trace)) &&

-							SameSign(rays.direction.Z(try2),

-									 rays.direction.Z(try_trace)))

-						{

-							need_trace[try2]=2;

-							tmprays.direction.X(try2) = rays.direction.X(try2);

-							tmprays.direction.Y(try2) = rays.direction.Y(try2);

-							tmprays.direction.Z(try2) = rays.direction.Z(try2);

-						}

-					}

-				// ok, now trace between 1 and 3 rays, and output the results

-				RayTracingResult tmpresults;

-				msk=tmprays.CalculateDirectionSignMask();

-				assert(msk!=-1);

-				Trace4Rays(tmprays,TMin,TMax,msk,&tmpresults,skip_id, pCallback);

-				// now, move results to proper place

-				for(int i=0;i<4;i++)

-					if (need_trace[i]==2)

-					{

-						need_trace[i]=0;

-						rslt_out->HitIds[i]=tmpresults.HitIds[i];

-						SubFloat(rslt_out->HitDistance, i) = SubFloat(tmpresults.HitDistance, i);

-						rslt_out->surface_normal.X(i) = tmpresults.surface_normal.X(i);

-						rslt_out->surface_normal.Y(i) = tmpresults.surface_normal.Y(i);

-						rslt_out->surface_normal.Z(i) = tmpresults.surface_normal.Z(i);

-					}

-				

-			}

-		}

-	}

-}

-

-

-void RayTracingEnvironment::Trace4Rays(const FourRays &rays, fltx4 TMin, fltx4 TMax,

-									   int DirectionSignMask, RayTracingResult *rslt_out,

-									   int32 skip_id, ITransparentTriangleCallback *pCallback)

-{

-	rays.Check();

-

-	memset(rslt_out->HitIds,0xff,sizeof(rslt_out->HitIds));

-

-	rslt_out->HitDistance=ReplicateX4(1.0e23);

-

-	rslt_out->surface_normal.DuplicateVector(Vector(0.,0.,0.));

-	FourVectors OneOverRayDir=rays.direction;

-	OneOverRayDir.MakeReciprocalSaturate();

-	

-	// now, clip rays against bounding box

-	for(int c=0;c<3;c++)

-	{

-		fltx4 isect_min_t=

-			MulSIMD(SubSIMD(ReplicateX4(m_MinBound[c]),rays.origin[c]),OneOverRayDir[c]);

-		fltx4 isect_max_t=

-			MulSIMD(SubSIMD(ReplicateX4(m_MaxBound[c]),rays.origin[c]),OneOverRayDir[c]);

-		TMin=MaxSIMD(TMin,MinSIMD(isect_min_t,isect_max_t));

-		TMax=MinSIMD(TMax,MaxSIMD(isect_min_t,isect_max_t));

-	}

-	fltx4 active=CmpLeSIMD(TMin,TMax);					// mask of which rays are active

-	if (! IsAnyNegative(active) )

-		return;												// missed bounding box

-

-	int32 mailboxids[MAILBOX_HASH_SIZE];					// used to avoid redundant triangle tests

-	memset(mailboxids,0xff,sizeof(mailboxids));				// !!speed!! keep around?

-

-	int front_idx[3],back_idx[3];							// based on ray direction, whether to

-															// visit left or right node first

-

-	if (DirectionSignMask & 1)

-	{

-		back_idx[0]=0;

-		front_idx[0]=1;

-	}

-		else

-	{

-		back_idx[0]=1;

-		front_idx[0]=0;

-	}

-	if (DirectionSignMask & 2)

-	{

-		back_idx[1]=0;

-		front_idx[1]=1;

-	}

-	else

-	{

-		back_idx[1]=1;

-		front_idx[1]=0;

-	}

-	if (DirectionSignMask & 4)

-	{

-		back_idx[2]=0;

-		front_idx[2]=1;

-	}

-	else

-	{

-		back_idx[2]=1;

-		front_idx[2]=0;

-	}

-		

-	NodeToVisit NodeQueue[MAX_NODE_STACK_LEN];

-	CacheOptimizedKDNode const *CurNode=&(OptimizedKDTree[0]);

-	NodeToVisit *stack_ptr=&NodeQueue[MAX_NODE_STACK_LEN];

-	while(1)

-	{

-		while (CurNode->NodeType() != KDNODE_STATE_LEAF)		// traverse until next leaf

-		{	   

-			int split_plane_number=CurNode->NodeType();

-			CacheOptimizedKDNode const *FrontChild=&(OptimizedKDTree[CurNode->LeftChild()]);

-			

-			fltx4 dist_to_sep_plane=						// dist=(split-org)/dir

-				MulSIMD(

-					SubSIMD(ReplicateX4(CurNode->SplittingPlaneValue),

-							   rays.origin[split_plane_number]),OneOverRayDir[split_plane_number]);

-			fltx4 active=CmpLeSIMD(TMin,TMax);			// mask of which rays are active

-

-			// now, decide how to traverse children. can either do front,back, or do front and push

-			// back.

-			fltx4 hits_front=AndSIMD(active,CmpGeSIMD(dist_to_sep_plane,TMin));

-			if (! IsAnyNegative(hits_front))

-			{

-				// missed the front. only traverse back

-				//printf("only visit back %d\n",CurNode->LeftChild()+back_idx[split_plane_number]);

-				CurNode=FrontChild+back_idx[split_plane_number];

-				TMin=MaxSIMD(TMin, dist_to_sep_plane);

-

-			}

-			else

-			{

-				fltx4 hits_back=AndSIMD(active,CmpLeSIMD(dist_to_sep_plane,TMax));

-				if (! IsAnyNegative(hits_back) )

-				{

-					// missed the back - only need to traverse front node

-					//printf("only visit front %d\n",CurNode->LeftChild()+front_idx[split_plane_number]);

-					CurNode=FrontChild+front_idx[split_plane_number];

-					TMax=MinSIMD(TMax, dist_to_sep_plane);

-				}

-				else

-				{

-					// at least some rays hit both nodes.

-					// must push far, traverse near

- 					//printf("visit %d,%d\n",CurNode->LeftChild()+front_idx[split_plane_number],

- 					//	   CurNode->LeftChild()+back_idx[split_plane_number]);

-					assert(stack_ptr>NodeQueue);

-					--stack_ptr;

-					stack_ptr->node=FrontChild+back_idx[split_plane_number];

-					stack_ptr->TMin=MaxSIMD(TMin,dist_to_sep_plane);

-					stack_ptr->TMax=TMax;

-					CurNode=FrontChild+front_idx[split_plane_number];

-					TMax=MinSIMD(TMax,dist_to_sep_plane);

-				}

-			}

-		}

-		// hit a leaf! must do intersection check

-		int ntris=CurNode->NumberOfTrianglesInLeaf();

-		if (ntris)

-		{

-			int32 const *tlist=&(TriangleIndexList[CurNode->TriangleIndexStart()]);

-			do

-			{

-				int tnum=*(tlist++);

-				//printf("try tri %d\n",tnum);

-				// check mailbox

-				int mbox_slot=tnum & (MAILBOX_HASH_SIZE-1);

-				TriIntersectData_t const *tri = &( OptimizedTriangleList[tnum].m_Data.m_IntersectData );

-				if ( ( mailboxids[mbox_slot] != tnum ) && ( tri->m_nTriangleID != skip_id ) )

-				{

-					n_intersection_calculations++;

-					mailboxids[mbox_slot] = tnum;

-					// compute plane intersection

-

-

-					FourVectors N;

-					N.x = ReplicateX4( tri->m_flNx );

-					N.y = ReplicateX4( tri->m_flNy );

-					N.z = ReplicateX4( tri->m_flNz );

-

-					fltx4 DDotN = rays.direction * N;

-					// mask off zero or near zero (ray parallel to surface)

-					fltx4 did_hit = OrSIMD( CmpGtSIMD( DDotN,FourEpsilons ),

-											CmpLtSIMD( DDotN, FourNegativeEpsilons ) );

-

-					fltx4 numerator=SubSIMD( ReplicateX4( tri->m_flD ), rays.origin * N );

-

-					fltx4 isect_t=DivSIMD( numerator,DDotN );

-					// now, we have the distance to the plane. lets update our mask

-					did_hit = AndSIMD( did_hit, CmpGtSIMD( isect_t, FourZeros ) );

-					//did_hit=AndSIMD(did_hit,CmpLtSIMD(isect_t,TMax));

-					did_hit = AndSIMD( did_hit, CmpLtSIMD( isect_t, rslt_out->HitDistance ) );

-

-					if ( ! IsAnyNegative( did_hit ) )

-						continue;

-

-					// now, check 3 edges

-					fltx4 hitc1 = AddSIMD( rays.origin[tri->m_nCoordSelect0],

-										MulSIMD( isect_t, rays.direction[ tri->m_nCoordSelect0] ) );

-					fltx4 hitc2 = AddSIMD( rays.origin[tri->m_nCoordSelect1],

-										   MulSIMD( isect_t, rays.direction[tri->m_nCoordSelect1] ) );

-					

-					// do barycentric coordinate check

-					fltx4 B0 = MulSIMD( ReplicateX4( tri->m_ProjectedEdgeEquations[0] ), hitc1 );

-

-					B0 = AddSIMD(

-						B0,

-						MulSIMD( ReplicateX4( tri->m_ProjectedEdgeEquations[1] ), hitc2 ) );

-					B0 = AddSIMD(

-						B0, ReplicateX4( tri->m_ProjectedEdgeEquations[2] ) );

-

-					did_hit = AndSIMD( did_hit, CmpGeSIMD( B0, FourZeros ) );

-

-					fltx4 B1 = MulSIMD( ReplicateX4( tri->m_ProjectedEdgeEquations[3] ), hitc1 );

-					B1 = AddSIMD(

-						B1,

-						MulSIMD( ReplicateX4( tri->m_ProjectedEdgeEquations[4]), hitc2 ) );

-

-					B1 = AddSIMD(

-						B1, ReplicateX4( tri->m_ProjectedEdgeEquations[5] ) );

-					

-					did_hit = AndSIMD( did_hit, CmpGeSIMD( B1, FourZeros ) );

-

-					fltx4 B2 = AddSIMD( B1, B0 );

-					did_hit = AndSIMD( did_hit, CmpLeSIMD( B2, Four_Ones ) );

-

-					if ( ! IsAnyNegative( did_hit ) )

-						continue;

-

-					// if the triangle is transparent

-					if ( tri->m_nFlags & FCACHETRI_TRANSPARENT )

-					{

-						if ( pCallback )

-						{

-							// assuming a triangle indexed as v0, v1, v2

-							// the projected edge equations are set up such that the vert opposite the first

-							// equation is v2, and the vert opposite the second equation is v0

-							// Therefore we pass them back in 1, 2, 0 order

-							// Also B2 is currently B1 + B0 and needs to be 1 - (B1+B0) in order to be a real

-							// barycentric coordinate.  Compute that now and pass it to the callback

-							fltx4 b2 = SubSIMD( Four_Ones, B2 );

-							if ( pCallback->VisitTriangle_ShouldContinue( *tri, rays, &did_hit, &B1, &b2, &B0, tnum ) )

-							{

-								did_hit = Four_Zeros;

-							}

-						}

-					}

-					// now, set the hit_id and closest_hit fields for any enabled rays

-					fltx4 replicated_n = ReplicateIX4(tnum);

-					StoreAlignedSIMD((float *) rslt_out->HitIds,

-								 OrSIMD(AndSIMD(replicated_n,did_hit),

-										   AndNotSIMD(did_hit,LoadAlignedSIMD(

-															 (float *) rslt_out->HitIds))));

-					rslt_out->HitDistance=OrSIMD(AndSIMD(isect_t,did_hit),

-									 AndNotSIMD(did_hit,rslt_out->HitDistance));

-

-					rslt_out->surface_normal.x=OrSIMD(

-						AndSIMD(N.x,did_hit),

-						AndNotSIMD(did_hit,rslt_out->surface_normal.x));

-					rslt_out->surface_normal.y=OrSIMD(

-						AndSIMD(N.y,did_hit),

-						AndNotSIMD(did_hit,rslt_out->surface_normal.y));

-					rslt_out->surface_normal.z=OrSIMD(

-						AndSIMD(N.z,did_hit),

-						AndNotSIMD(did_hit,rslt_out->surface_normal.z));

-					

-				}

-			} while (--ntris);

-			// now, check if all rays have terminated

-			fltx4 raydone=CmpLeSIMD(TMax,rslt_out->HitDistance);

-			if (! IsAnyNegative(raydone))

-			{

-				return;

-			}

-		}

-		

- 		if (stack_ptr==&NodeQueue[MAX_NODE_STACK_LEN])

-		{

-			return;

-		}

-		// pop stack!

-		CurNode=stack_ptr->node;

-		TMin=stack_ptr->TMin;

-		TMax=stack_ptr->TMax;

-		stack_ptr++;

-	}

-}

-

-

-int RayTracingEnvironment::MakeLeafNode(int first_tri, int last_tri)

-{

-	CacheOptimizedKDNode ret;

-	ret.Children=KDNODE_STATE_LEAF+(TriangleIndexList.Count()<<2);

-	ret.SetNumberOfTrianglesInLeafNode(1+(last_tri-first_tri));

-	for(int tnum=first_tri;tnum<=last_tri;tnum++)

-		TriangleIndexList.AddToTail(tnum);

-	OptimizedKDTree.AddToTail(ret);

-	return OptimizedKDTree.Count()-1;

-}

-

-

-void RayTracingEnvironment::CalculateTriangleListBounds(int32 const *tris,int ntris,

-														Vector &minout, Vector &maxout)

-{

-	minout = Vector( 1.0e23, 1.0e23, 1.0e23);

-	maxout = Vector( -1.0e23, -1.0e23, -1.0e23);

-	for(int i=0; i<ntris; i++)

-	{

-		CacheOptimizedTriangle const &tri=OptimizedTriangleList[tris[i]];

-		for(int v=0; v<3; v++)

-			for(int c=0; c<3; c++)

-			{

-				minout[c]=min(minout[c],tri.Vertex(v)[c]);

-							  maxout[c]=max(maxout[c],tri.Vertex(v)[c]);

-			}

-	}

-}

-

-

-// Both the "quick" and regular kd tree building algorithms here use the "surface area heuristic":

-// the relative probability of hitting the "left" subvolume (Vl) from a split is equal to that

-// subvolume's surface area divided by its parent's surface area (Vp) : P(Vl | V)=SA(Vl)/SA(Vp).

-// The same holds for the right subvolume, Vp. Nl is the number of triangles in the left volume,

-// and Nr in the right volume. if Ct is the cost of traversing one tree node, and Ci is the cost of

-// intersection with the primitive, than the cost of splitting is estimated as:

-//

-//    Ct+Ci*((SA(Vl)/SA(V))*Nl+(SA(Vr)/SA(V)*Nr)).

-// and the cost of not splitting is

-//    Ci*N

-//

-//  This both provides a metric to minimize when computing how and where to split, and also a

-//  termination criterion.

-//

-// the "quick" method just splits down the middle, while the slow method splits at the best

-// discontinuity of the cost formula. The quick method splits along the longest axis ; the 

-// regular algorithm tries all 3 to find which one results in the minimum cost

-// 

-// both methods use the additional optimization of "growing" empty nodes - if the split results in

-// one side being devoid of triangles, the empty side is "grown" as much as possible.

-//

-

-#define COST_OF_TRAVERSAL 75								// approximate #operations

-#define COST_OF_INTERSECTION 167							// approximate #operations

-

-

-float RayTracingEnvironment::CalculateCostsOfSplit(

-	int split_plane,int32 const *tri_list,int ntris,

-	Vector MinBound,Vector MaxBound, float &split_value,

-	int &nleft, int &nright, int &nboth)

-{

-	// determine the costs of splitting on a given axis, and label triangles with respect to

-	// that axis by storing the value in coordselect0. It will also return the number of

-	// tris in the left, right, and nboth groups, in order to facilitate memory

-	nleft=nboth=nright=0;

-	

-	// now, label each triangle. Since we have not converted the triangles into

-	// intersection fromat yet, we can use the CoordSelect0 field of each as a temp.

-	nleft=0;

-	nright=0;

-	nboth=0;

-	float min_coord=1.0e23,max_coord=-1.0e23;

-

-	for(int t=0;t<ntris;t++)

-	{

-		CacheOptimizedTriangle &tri=OptimizedTriangleList[tri_list[t]];

-		// determine max and min coordinate values for later optimization

-		for(int v=0;v<3;v++)

-		{

-			min_coord = min( min_coord, tri.Vertex(v)[split_plane] );

-			max_coord = max( max_coord, tri.Vertex(v)[split_plane] );

-		}

-		switch(tri.ClassifyAgainstAxisSplit(split_plane,split_value))

-		{

-			case PLANECHECK_NEGATIVE:

-				nleft++;

-				tri.m_Data.m_GeometryData.m_nTmpData0 = PLANECHECK_NEGATIVE;

-				break;

-

-			case PLANECHECK_POSITIVE:

-				nright++;

-				tri.m_Data.m_GeometryData.m_nTmpData0 = PLANECHECK_POSITIVE;

-				break;

-

-			case PLANECHECK_STRADDLING:

-				nboth++;

-				tri.m_Data.m_GeometryData.m_nTmpData0 = PLANECHECK_STRADDLING;

-				break;

-		}

-	}

-	// now, if the split resulted in one half being empty, "grow" the empty half

-	if (nleft && (nboth==0) && (nright==0))

-		split_value=max_coord;

-	if (nright && (nboth==0) && (nleft==0))

-		split_value=min_coord;

-

-	// now, perform surface area/cost check to determine whether this split was worth it

-	Vector LeftMins=MinBound;

-	Vector LeftMaxes=MaxBound;

-	Vector RightMins=MinBound;

-	Vector RightMaxes=MaxBound;

-	LeftMaxes[split_plane]=split_value;

-	RightMins[split_plane]=split_value;

-	float SA_L=BoxSurfaceArea(LeftMins,LeftMaxes);

-	float SA_R=BoxSurfaceArea(RightMins,RightMaxes);

-	float ISA=1.0/BoxSurfaceArea(MinBound,MaxBound);

-	float cost_of_split=COST_OF_TRAVERSAL+COST_OF_INTERSECTION*(nboth+

-		(SA_L*ISA*(nleft))+(SA_R*ISA*(nright)));

-	return cost_of_split;

-}

-

-

-#define NEVER_SPLIT 0

-

-void RayTracingEnvironment::RefineNode(int node_number,int32 const *tri_list,int ntris,

-									   Vector MinBound,Vector MaxBound, int depth)

-{

-	if (ntris<3)											// never split empty lists

-	{

-		// no point in continuing

-		OptimizedKDTree[node_number].Children=KDNODE_STATE_LEAF+(TriangleIndexList.Count()<<2);

-		OptimizedKDTree[node_number].SetNumberOfTrianglesInLeafNode(ntris);

-

-#ifdef DEBUG_RAYTRACE

-		OptimizedKDTree[node_number].vecMins = MinBound;

-		OptimizedKDTree[node_number].vecMaxs = MaxBound;

-#endif

-

-		for(int t=0;t<ntris;t++)

-			TriangleIndexList.AddToTail(tri_list[t]);

-		return;

-	}

-

-	float best_cost=1.0e23;

-	int best_nleft=0,best_nright=0,best_nboth=0;

-	float best_splitvalue=0;

-	int split_plane=0;

-

-	int tri_skip=1+(ntris/10);								// don't try all trinagles as split

-															// points when there are a lot of them

-	for(int axis=0;axis<3;axis++)

-	{

-		for(int ts=-1;ts<ntris;ts+=tri_skip)

-		{

-			for(int tv=0;tv<3;tv++)

-			{

-				int trial_nleft,trial_nright,trial_nboth;

-				float trial_splitvalue;

-				if (ts==-1)

-					trial_splitvalue=0.5*(MinBound[axis]+MaxBound[axis]);

-				else

-				{

-					// else, split at the triangle vertex if possible

-					CacheOptimizedTriangle &tri=OptimizedTriangleList[tri_list[ts]];

-					trial_splitvalue = tri.Vertex(tv)[axis];

-					if ((trial_splitvalue>MaxBound[axis]) || (trial_splitvalue<MinBound[axis]))

-						continue;							// don't try this vertex - not inside

-					

-				}

-//				printf("ts=%d tv=%d tp=%f\n",ts,tv,trial_splitvalue);

-				float trial_cost=

-					CalculateCostsOfSplit(axis,tri_list,ntris,MinBound,MaxBound,trial_splitvalue,

-										  trial_nleft,trial_nright, trial_nboth);

-// 				printf("try %d cost=%f nl=%d nr=%d nb=%d sp=%f\n",axis,trial_cost,trial_nleft,trial_nright, trial_nboth,

-// 					   trial_splitvalue);

-				if (trial_cost<best_cost)

-				{

-					split_plane=axis;

-					best_cost=trial_cost;

-					best_nleft=trial_nleft;

-					best_nright=trial_nright;

-					best_nboth=trial_nboth;

-					best_splitvalue=trial_splitvalue;

-					// save away the axis classification of each triangle

-					for(int t=0 ; t < ntris; t++)

-					{

-						CacheOptimizedTriangle &tri=OptimizedTriangleList[tri_list[t]];

-						tri.m_Data.m_GeometryData.m_nTmpData1 = tri.m_Data.m_GeometryData.m_nTmpData0;

-					}

-				}

-				if (ts==-1)

-					break;

-			}

-		}

-

-	}

-	float cost_of_no_split=COST_OF_INTERSECTION*ntris;

-	if ( (cost_of_no_split<=best_cost) || NEVER_SPLIT || (depth>MAX_TREE_DEPTH))

-	{

-		// no benefit to splitting. just make this a leaf node

-		OptimizedKDTree[node_number].Children=KDNODE_STATE_LEAF+(TriangleIndexList.Count()<<2);

-		OptimizedKDTree[node_number].SetNumberOfTrianglesInLeafNode(ntris);

-#ifdef DEBUG_RAYTRACE

-		OptimizedKDTree[node_number].vecMins = MinBound;

-		OptimizedKDTree[node_number].vecMaxs = MaxBound;

-#endif

-		for(int t=0;t<ntris;t++)

-			TriangleIndexList.AddToTail(tri_list[t]);

-	}

-	else

-	{

-// 		printf("best split was %d at %f (mid=%f,n=%d, sk=%d)\n",split_plane,best_splitvalue,

-// 			   0.5*(MinBound[split_plane]+MaxBound[split_plane]),ntris,tri_skip);

-		// its worth splitting!

-		// we will achieve the splitting without sorting by using a selection algorithm.

-		int32 *new_triangle_list;

-		new_triangle_list=new int32[ntris];

-

-		// now, perform surface area/cost check to determine whether this split was worth it

-		Vector LeftMins=MinBound;

-		Vector LeftMaxes=MaxBound;

-		Vector RightMins=MinBound;

-		Vector RightMaxes=MaxBound;

-		LeftMaxes[split_plane]=best_splitvalue;

-		RightMins[split_plane]=best_splitvalue;

-		

-		int n_left_output=0;

-		int n_both_output=0;

-		int n_right_output=0;

-		for(int t=0;t<ntris;t++)

-		{

-			CacheOptimizedTriangle &tri=OptimizedTriangleList[tri_list[t]];

-			switch( tri.m_Data.m_GeometryData.m_nTmpData1 )

-			{

-				case PLANECHECK_NEGATIVE:

-//					printf("%d goes left\n",t);

-					new_triangle_list[n_left_output++]=tri_list[t];

-					break;

-				case PLANECHECK_POSITIVE:

-					n_right_output++;

-//					printf("%d goes right\n",t);

-					new_triangle_list[ntris-n_right_output]=tri_list[t];

-					break;

-				case PLANECHECK_STRADDLING:

-//					printf("%d goes both\n",t);

-					new_triangle_list[best_nleft+n_both_output]=tri_list[t];

-					n_both_output++;

-					break;

-

-					

-			}

-		}

-		int left_child=OptimizedKDTree.Count();

-		int right_child=left_child+1;

-// 		printf("node %d split on axis %d at %f, nl=%d nr=%d nb=%d lc=%d rc=%d\n",node_number,

-// 			   split_plane,best_splitvalue,best_nleft,best_nright,best_nboth,

-// 			   left_child,right_child);

-		OptimizedKDTree[node_number].Children=split_plane+(left_child<<2);

-		OptimizedKDTree[node_number].SplittingPlaneValue=best_splitvalue;

-#ifdef DEBUG_RAYTRACE

-		OptimizedKDTree[node_number].vecMins = MinBound;

-		OptimizedKDTree[node_number].vecMaxs = MaxBound;

-#endif

-		CacheOptimizedKDNode newnode;

-		OptimizedKDTree.AddToTail(newnode);

-		OptimizedKDTree.AddToTail(newnode);

-		// now, recurse!

-		if ( (ntris<20) && ((best_nleft==0) || (best_nright==0)) )

-			depth+=100;

-		RefineNode(left_child,new_triangle_list,best_nleft+best_nboth,LeftMins,LeftMaxes,depth+1);

-		RefineNode(right_child,new_triangle_list+best_nleft,best_nright+best_nboth,

-				   RightMins,RightMaxes,depth+1);

-		delete[] new_triangle_list;

-	}	

-}

-

-

-void RayTracingEnvironment::SetupAccelerationStructure(void)

-{

-	CacheOptimizedKDNode root;

-	OptimizedKDTree.AddToTail(root);

-	int32 *root_triangle_list=new int32[OptimizedTriangleList.Count()];

-	for(int t=0;t<OptimizedTriangleList.Count();t++)

-		root_triangle_list[t]=t;

-	CalculateTriangleListBounds(root_triangle_list,OptimizedTriangleList.Count(),m_MinBound,

-								m_MaxBound);

-	RefineNode(0,root_triangle_list,OptimizedTriangleList.Count(),m_MinBound,m_MaxBound,0);

-	delete[] root_triangle_list;

-

-	// now, convert all triangles to "intersection format"

-	for(int i=0;i<OptimizedTriangleList.Count();i++)

-		OptimizedTriangleList[i].ChangeIntoIntersectionFormat();

-}

-

-

-

-void RayTracingEnvironment::AddInfinitePointLight(Vector position, Vector intensity)

-{

-	LightDesc_t mylight(position,intensity);

-	LightList.AddToTail(mylight);

-	

-}

-

-

+//========= Copyright Valve Corporation, All rights reserved. ============//
+// $Id$
+
+#include "raytrace.h"
+#include <filesystem_tools.h>
+#include <cmdlib.h>
+#include <stdio.h>
+
+static bool SameSign(float a, float b)
+{
+	int32 aa=*((int *) &a);
+	int32 bb=*((int *) &b);
+	return ((aa^bb)&0x80000000)==0;
+}
+
+int FourRays::CalculateDirectionSignMask(void) const
+{
+	// this code treats the floats as integers since all it cares about is the sign bit and
+	// floating point compares suck.
+
+	int ret;
+	int ormask;
+	int andmask;
+	int32 const *treat_as_int=((int32 const *) (&direction));
+
+	ormask=andmask=*(treat_as_int++);
+	ormask|=*treat_as_int;
+	andmask&=*(treat_as_int++);
+	ormask|=*(treat_as_int);
+	andmask&=*(treat_as_int++);
+	ormask|=*(treat_as_int);
+	andmask&=*(treat_as_int++);
+	if (ormask>=0)
+		ret=0;
+	else
+	{
+		if (andmask<0)
+			ret=1;
+		else return -1;
+	}
+	ormask=andmask=*(treat_as_int++);
+	ormask|=*treat_as_int;
+	andmask&=*(treat_as_int++);
+	ormask|=*(treat_as_int);
+	andmask&=*(treat_as_int++);
+	ormask|=*(treat_as_int);
+	andmask&=*(treat_as_int++);
+	if (ormask<0)
+	{
+		if (andmask<0)
+			ret|=2;
+		else return -1;
+	}
+	ormask=andmask=*(treat_as_int++);
+	ormask|=*treat_as_int;
+	andmask&=*(treat_as_int++);
+	ormask|=*(treat_as_int);
+	andmask&=*(treat_as_int++);
+	ormask|=*(treat_as_int);
+	andmask&=*(treat_as_int++);
+	if (ormask<0)
+	{
+		if (andmask<0)
+			ret|=4;
+		else return -1;
+	}
+	return ret;
+}
+
+
+
+
+void RayTracingEnvironment::MakeRoomForTriangles( int ntris )
+{
+	//OptimizedTriangleList.EnsureCapacity( ntris );
+	if (! (Flags & RTE_FLAGS_DONT_STORE_TRIANGLE_COLORS))
+		TriangleColors.EnsureCapacity( ntris );
+}
+
+
+void RayTracingEnvironment::AddTriangle(int32 id, const Vector &v1,
+										const Vector &v2, const Vector &v3,
+										const Vector &color)
+{
+	AddTriangle( id, v1, v2, v3, color, 0, 0 );
+}
+
+void RayTracingEnvironment::AddTriangle(int32 id, const Vector &v1,
+										const Vector &v2, const Vector &v3,
+										const Vector &color, uint16 flags, int32 materialIndex)
+{
+	CacheOptimizedTriangle tmptri;
+	tmptri.m_Data.m_GeometryData.m_nTriangleID = id;
+	tmptri.Vertex( 0 ) = v1;
+	tmptri.Vertex( 1 ) = v2;
+	tmptri.Vertex( 2 ) = v3;
+	tmptri.m_Data.m_GeometryData.m_nFlags = flags;
+	OptimizedTriangleList.AddToTail(tmptri);
+	if (! ( Flags & RTE_FLAGS_DONT_STORE_TRIANGLE_COLORS) )
+		TriangleColors.AddToTail(color);
+	if ( !( Flags & RTE_FLAGS_DONT_STORE_TRIANGLE_MATERIALS) )
+		TriangleMaterials.AddToTail(materialIndex);
+// 	printf("add triange from (%f %f %f),(%f %f %f),(%f %f %f) id %d\n",
+// 		   XYZ(v1),XYZ(v2),XYZ(v3),id);
+}
+
+void RayTracingEnvironment::AddQuad(
+	int32 id, const Vector &v1, const Vector &v2, const Vector &v3,
+	const Vector &v4,							// specify vertices in cw or ccw order
+	const Vector &color)
+{
+	AddTriangle(id,v1,v2,v3,color);
+	AddTriangle(id+1,v1,v3,v4,color);
+}
+
+
+void RayTracingEnvironment::AddAxisAlignedRectangularSolid(int id,Vector minc, Vector maxc,
+														   const Vector &color)
+{
+
+	// "far" face
+	AddQuad(id,
+			Vector(minc.x,maxc.y,maxc.z),
+			Vector(maxc.x,maxc.y,maxc.z),Vector(maxc.x,minc.y,maxc.z),
+			Vector(minc.x,minc.y,maxc.z),color);
+	// "near" face
+	AddQuad(id,
+			Vector(minc.x,maxc.y,minc.z),
+			Vector(maxc.x,maxc.y,minc.z),Vector(maxc.x,minc.y,minc.z),
+			Vector(minc.x,minc.y,minc.z),color);
+
+	// "left" face
+	AddQuad(id,
+			Vector(minc.x,maxc.y,maxc.z),
+			Vector(minc.x,maxc.y,minc.z),
+			Vector(minc.x,minc.y,minc.z),
+			Vector(minc.x,minc.y,maxc.z),color);
+	// "right" face
+	AddQuad(id,
+			Vector(maxc.x,maxc.y,maxc.z),
+			Vector(maxc.x,maxc.y,minc.z),
+			Vector(maxc.x,minc.y,minc.z),
+			Vector(maxc.x,minc.y,maxc.z),color);
+	
+	// "top" face
+	AddQuad(id,
+			Vector(minc.x,maxc.y,maxc.z),
+			Vector(maxc.x,maxc.y,maxc.z),
+			Vector(maxc.x,maxc.y,minc.z),
+			Vector(minc.x,maxc.y,minc.z),color);
+	// "bot" face
+	AddQuad(id,
+			Vector(minc.x,minc.y,maxc.z),
+			Vector(maxc.x,minc.y,maxc.z),
+			Vector(maxc.x,minc.y,minc.z),
+			Vector(minc.x,minc.y,minc.z),color);
+}
+
+
+
+static Vector GetEdgeEquation(Vector p1, Vector p2, int c1, int c2, Vector InsidePoint)
+{
+	float nx=p1[c2]-p2[c2];
+	float ny=p2[c1]-p1[c1];
+	float d=-(nx*p1[c1]+ny*p1[c2]);
+// 	assert(fabs(nx*p1[c1]+ny*p1[c2]+d)<0.01);
+// 	assert(fabs(nx*p2[c1]+ny*p2[c2]+d)<0.01);
+
+	// use the convention that negative is "outside"
+	float trial_dist=InsidePoint[c1]*nx+InsidePoint[c2]*ny+d;
+	if (trial_dist<0)
+	{
+		nx = -nx;
+		ny = -ny;
+		d = -d;
+		trial_dist = -trial_dist;
+	}
+	nx /= trial_dist;										// scale so that it will be =1.0 at the oppositve vertex
+	ny /= trial_dist;
+	d /= trial_dist;
+
+	return Vector(nx,ny,d);
+}
+
+void CacheOptimizedTriangle::ChangeIntoIntersectionFormat(void)
+{
+	// lose the vertices and use edge equations instead
+
+	// grab the whole original triangle to we don't overwrite it
+	TriGeometryData_t srcTri = m_Data.m_GeometryData;
+
+	m_Data.m_IntersectData.m_nFlags = srcTri.m_nFlags;
+	m_Data.m_IntersectData.m_nTriangleID = srcTri.m_nTriangleID;
+
+	Vector p1 = srcTri.Vertex( 0 );
+	Vector p2 = srcTri.Vertex( 1 );
+	Vector p3 = srcTri.Vertex( 2 );
+
+	Vector e1 = p2 - p1;
+	Vector e2 = p3 - p1;
+
+	Vector N = e1.Cross( e2 );
+	N.NormalizeInPlace();
+	// now, determine which axis to drop
+	int drop_axis = 0;
+	for(int c=1 ; c<3 ; c++)
+		if ( fabs(N[c]) > fabs( N[drop_axis] ) )
+			drop_axis = c;
+
+	m_Data.m_IntersectData.m_flD = N.Dot( p1 );
+	m_Data.m_IntersectData.m_flNx = N.x;
+	m_Data.m_IntersectData.m_flNy = N.y;
+	m_Data.m_IntersectData.m_flNz = N.z;
+
+	// decide which axes to keep
+	int nCoordSelect0 = ( drop_axis + 1 ) % 3;
+	int nCoordSelect1 = ( drop_axis + 2 ) % 3;
+
+	m_Data.m_IntersectData.m_nCoordSelect0 = nCoordSelect0;
+	m_Data.m_IntersectData.m_nCoordSelect1 = nCoordSelect1;
+
+
+	Vector edge1 = GetEdgeEquation( p1, p2, nCoordSelect0, nCoordSelect1, p3 );
+	m_Data.m_IntersectData.m_ProjectedEdgeEquations[0] = edge1.x;
+	m_Data.m_IntersectData.m_ProjectedEdgeEquations[1] = edge1.y;
+	m_Data.m_IntersectData.m_ProjectedEdgeEquations[2] = edge1.z;
+
+	Vector edge2 = GetEdgeEquation( p2, p3, nCoordSelect0, nCoordSelect1, p1 );
+	m_Data.m_IntersectData.m_ProjectedEdgeEquations[3] = edge2.x;
+	m_Data.m_IntersectData.m_ProjectedEdgeEquations[4] = edge2.y;
+	m_Data.m_IntersectData.m_ProjectedEdgeEquations[5] = edge2.z;
+
+
+}
+
+int n_intersection_calculations=0;
+
+int CacheOptimizedTriangle::ClassifyAgainstAxisSplit(int split_plane, float split_value)
+{
+	// classify a triangle against an axis-aligned plane
+	float minc=Vertex(0)[split_plane];
+	float maxc=minc;
+	for(int v=1;v<3;v++)
+	{
+		minc=min(minc,Vertex(v)[split_plane]);
+		maxc=max(maxc,Vertex(v)[split_plane]);
+	}
+
+	if (minc>=split_value)
+		return PLANECHECK_POSITIVE;
+	if (maxc<=split_value)
+		return PLANECHECK_NEGATIVE;
+	if (minc==maxc)
+		return PLANECHECK_POSITIVE;
+	return PLANECHECK_STRADDLING;
+}
+
+#define MAILBOX_HASH_SIZE 256
+#define MAX_TREE_DEPTH 21
+#define MAX_NODE_STACK_LEN (40*MAX_TREE_DEPTH)
+
+struct NodeToVisit {
+	CacheOptimizedKDNode const *node;
+	fltx4 TMin;
+	fltx4 TMax;
+};
+
+
+static fltx4 FourEpsilons={1.0e-10,1.0e-10,1.0e-10,1.0e-10};
+static fltx4 FourZeros={1.0e-10,1.0e-10,1.0e-10,1.0e-10};
+static fltx4 FourNegativeEpsilons={-1.0e-10,-1.0e-10,-1.0e-10,-1.0e-10};
+
+static float BoxSurfaceArea(Vector const &boxmin, Vector const &boxmax)
+{
+	Vector boxdim=boxmax-boxmin;
+	return 2.0*((boxdim[0]*boxdim[2])+(boxdim[0]*boxdim[1])+(boxdim[1]*boxdim[2]));
+}
+
+void RayTracingEnvironment::Trace4Rays(const FourRays &rays, fltx4 TMin, fltx4 TMax,
+									   RayTracingResult *rslt_out,
+									   int32 skip_id, ITransparentTriangleCallback *pCallback)
+{
+	int msk=rays.CalculateDirectionSignMask();
+	if (msk!=-1)
+		Trace4Rays(rays,TMin,TMax,msk,rslt_out,skip_id, pCallback);
+	else
+	{
+		// sucky case - can't trace 4 rays at once. in the worst case, need to trace all 4
+		// separately, but usually we will still get 2x, Since our tracer only does 4 at a
+		// time, we will have to cover up the undesired rays with the desired ray
+
+		//!! speed!! there is room for some sse-ization here
+		FourRays tmprays;
+		tmprays.origin=rays.origin;
+
+		uint8 need_trace[4]={1,1,1,1};
+		for(int try_trace=0;try_trace<4;try_trace++)
+		{
+			if (need_trace[try_trace])
+			{
+				need_trace[try_trace]=2;			// going to trace it
+				// replicate the ray being traced into all 4 rays
+				tmprays.direction.x=ReplicateX4(rays.direction.X(try_trace));
+				tmprays.direction.y=ReplicateX4(rays.direction.Y(try_trace));
+				tmprays.direction.z=ReplicateX4(rays.direction.Z(try_trace));
+				// now, see if any of the other remaining rays can be handled at the same time.
+				for(int try2=try_trace+1;try2<4;try2++)
+					if (need_trace[try2])
+					{
+						if (
+							SameSign(rays.direction.X(try2),
+									 rays.direction.X(try_trace)) &&
+							SameSign(rays.direction.Y(try2),
+									 rays.direction.Y(try_trace)) &&
+							SameSign(rays.direction.Z(try2),
+									 rays.direction.Z(try_trace)))
+						{
+							need_trace[try2]=2;
+							tmprays.direction.X(try2) = rays.direction.X(try2);
+							tmprays.direction.Y(try2) = rays.direction.Y(try2);
+							tmprays.direction.Z(try2) = rays.direction.Z(try2);
+						}
+					}
+				// ok, now trace between 1 and 3 rays, and output the results
+				RayTracingResult tmpresults;
+				msk=tmprays.CalculateDirectionSignMask();
+				assert(msk!=-1);
+				Trace4Rays(tmprays,TMin,TMax,msk,&tmpresults,skip_id, pCallback);
+				// now, move results to proper place
+				for(int i=0;i<4;i++)
+					if (need_trace[i]==2)
+					{
+						need_trace[i]=0;
+						rslt_out->HitIds[i]=tmpresults.HitIds[i];
+						SubFloat(rslt_out->HitDistance, i) = SubFloat(tmpresults.HitDistance, i);
+						rslt_out->surface_normal.X(i) = tmpresults.surface_normal.X(i);
+						rslt_out->surface_normal.Y(i) = tmpresults.surface_normal.Y(i);
+						rslt_out->surface_normal.Z(i) = tmpresults.surface_normal.Z(i);
+					}
+				
+			}
+		}
+	}
+}
+
+
+void RayTracingEnvironment::Trace4Rays(const FourRays &rays, fltx4 TMin, fltx4 TMax,
+									   int DirectionSignMask, RayTracingResult *rslt_out,
+									   int32 skip_id, ITransparentTriangleCallback *pCallback)
+{
+	rays.Check();
+
+	memset(rslt_out->HitIds,0xff,sizeof(rslt_out->HitIds));
+
+	rslt_out->HitDistance=ReplicateX4(1.0e23);
+
+	rslt_out->surface_normal.DuplicateVector(Vector(0.,0.,0.));
+	FourVectors OneOverRayDir=rays.direction;
+	OneOverRayDir.MakeReciprocalSaturate();
+	
+	// now, clip rays against bounding box
+	for(int c=0;c<3;c++)
+	{
+		fltx4 isect_min_t=
+			MulSIMD(SubSIMD(ReplicateX4(m_MinBound[c]),rays.origin[c]),OneOverRayDir[c]);
+		fltx4 isect_max_t=
+			MulSIMD(SubSIMD(ReplicateX4(m_MaxBound[c]),rays.origin[c]),OneOverRayDir[c]);
+		TMin=MaxSIMD(TMin,MinSIMD(isect_min_t,isect_max_t));
+		TMax=MinSIMD(TMax,MaxSIMD(isect_min_t,isect_max_t));
+	}
+	fltx4 active=CmpLeSIMD(TMin,TMax);					// mask of which rays are active
+	if (! IsAnyNegative(active) )
+		return;												// missed bounding box
+
+	int32 mailboxids[MAILBOX_HASH_SIZE];					// used to avoid redundant triangle tests
+	memset(mailboxids,0xff,sizeof(mailboxids));				// !!speed!! keep around?
+
+	int front_idx[3],back_idx[3];							// based on ray direction, whether to
+															// visit left or right node first
+
+	if (DirectionSignMask & 1)
+	{
+		back_idx[0]=0;
+		front_idx[0]=1;
+	}
+		else
+	{
+		back_idx[0]=1;
+		front_idx[0]=0;
+	}
+	if (DirectionSignMask & 2)
+	{
+		back_idx[1]=0;
+		front_idx[1]=1;
+	}
+	else
+	{
+		back_idx[1]=1;
+		front_idx[1]=0;
+	}
+	if (DirectionSignMask & 4)
+	{
+		back_idx[2]=0;
+		front_idx[2]=1;
+	}
+	else
+	{
+		back_idx[2]=1;
+		front_idx[2]=0;
+	}
+		
+	NodeToVisit NodeQueue[MAX_NODE_STACK_LEN];
+	CacheOptimizedKDNode const *CurNode=&(OptimizedKDTree[0]);
+	NodeToVisit *stack_ptr=&NodeQueue[MAX_NODE_STACK_LEN];
+	while(1)
+	{
+		while (CurNode->NodeType() != KDNODE_STATE_LEAF)		// traverse until next leaf
+		{	   
+			int split_plane_number=CurNode->NodeType();
+			CacheOptimizedKDNode const *FrontChild=&(OptimizedKDTree[CurNode->LeftChild()]);
+			
+			fltx4 dist_to_sep_plane=						// dist=(split-org)/dir
+				MulSIMD(
+					SubSIMD(ReplicateX4(CurNode->SplittingPlaneValue),
+							   rays.origin[split_plane_number]),OneOverRayDir[split_plane_number]);
+			fltx4 active=CmpLeSIMD(TMin,TMax);			// mask of which rays are active
+
+			// now, decide how to traverse children. can either do front,back, or do front and push
+			// back.
+			fltx4 hits_front=AndSIMD(active,CmpGeSIMD(dist_to_sep_plane,TMin));
+			if (! IsAnyNegative(hits_front))
+			{
+				// missed the front. only traverse back
+				//printf("only visit back %d\n",CurNode->LeftChild()+back_idx[split_plane_number]);
+				CurNode=FrontChild+back_idx[split_plane_number];
+				TMin=MaxSIMD(TMin, dist_to_sep_plane);
+
+			}
+			else
+			{
+				fltx4 hits_back=AndSIMD(active,CmpLeSIMD(dist_to_sep_plane,TMax));
+				if (! IsAnyNegative(hits_back) )
+				{
+					// missed the back - only need to traverse front node
+					//printf("only visit front %d\n",CurNode->LeftChild()+front_idx[split_plane_number]);
+					CurNode=FrontChild+front_idx[split_plane_number];
+					TMax=MinSIMD(TMax, dist_to_sep_plane);
+				}
+				else
+				{
+					// at least some rays hit both nodes.
+					// must push far, traverse near
+ 					//printf("visit %d,%d\n",CurNode->LeftChild()+front_idx[split_plane_number],
+ 					//	   CurNode->LeftChild()+back_idx[split_plane_number]);
+					assert(stack_ptr>NodeQueue);
+					--stack_ptr;
+					stack_ptr->node=FrontChild+back_idx[split_plane_number];
+					stack_ptr->TMin=MaxSIMD(TMin,dist_to_sep_plane);
+					stack_ptr->TMax=TMax;
+					CurNode=FrontChild+front_idx[split_plane_number];
+					TMax=MinSIMD(TMax,dist_to_sep_plane);
+				}
+			}
+		}
+		// hit a leaf! must do intersection check
+		int ntris=CurNode->NumberOfTrianglesInLeaf();
+		if (ntris)
+		{
+			int32 const *tlist=&(TriangleIndexList[CurNode->TriangleIndexStart()]);
+			do
+			{
+				int tnum=*(tlist++);
+				//printf("try tri %d\n",tnum);
+				// check mailbox
+				int mbox_slot=tnum & (MAILBOX_HASH_SIZE-1);
+				TriIntersectData_t const *tri = &( OptimizedTriangleList[tnum].m_Data.m_IntersectData );
+				if ( ( mailboxids[mbox_slot] != tnum ) && ( tri->m_nTriangleID != skip_id ) )
+				{
+					n_intersection_calculations++;
+					mailboxids[mbox_slot] = tnum;
+					// compute plane intersection
+
+
+					FourVectors N;
+					N.x = ReplicateX4( tri->m_flNx );
+					N.y = ReplicateX4( tri->m_flNy );
+					N.z = ReplicateX4( tri->m_flNz );
+
+					fltx4 DDotN = rays.direction * N;
+					// mask off zero or near zero (ray parallel to surface)
+					fltx4 did_hit = OrSIMD( CmpGtSIMD( DDotN,FourEpsilons ),
+											CmpLtSIMD( DDotN, FourNegativeEpsilons ) );
+
+					fltx4 numerator=SubSIMD( ReplicateX4( tri->m_flD ), rays.origin * N );
+
+					fltx4 isect_t=DivSIMD( numerator,DDotN );
+					// now, we have the distance to the plane. lets update our mask
+					did_hit = AndSIMD( did_hit, CmpGtSIMD( isect_t, FourZeros ) );
+					//did_hit=AndSIMD(did_hit,CmpLtSIMD(isect_t,TMax));
+					did_hit = AndSIMD( did_hit, CmpLtSIMD( isect_t, rslt_out->HitDistance ) );
+
+					if ( ! IsAnyNegative( did_hit ) )
+						continue;
+
+					// now, check 3 edges
+					fltx4 hitc1 = AddSIMD( rays.origin[tri->m_nCoordSelect0],
+										MulSIMD( isect_t, rays.direction[ tri->m_nCoordSelect0] ) );
+					fltx4 hitc2 = AddSIMD( rays.origin[tri->m_nCoordSelect1],
+										   MulSIMD( isect_t, rays.direction[tri->m_nCoordSelect1] ) );
+					
+					// do barycentric coordinate check
+					fltx4 B0 = MulSIMD( ReplicateX4( tri->m_ProjectedEdgeEquations[0] ), hitc1 );
+
+					B0 = AddSIMD(
+						B0,
+						MulSIMD( ReplicateX4( tri->m_ProjectedEdgeEquations[1] ), hitc2 ) );
+					B0 = AddSIMD(
+						B0, ReplicateX4( tri->m_ProjectedEdgeEquations[2] ) );
+
+					did_hit = AndSIMD( did_hit, CmpGeSIMD( B0, FourZeros ) );
+
+					fltx4 B1 = MulSIMD( ReplicateX4( tri->m_ProjectedEdgeEquations[3] ), hitc1 );
+					B1 = AddSIMD(
+						B1,
+						MulSIMD( ReplicateX4( tri->m_ProjectedEdgeEquations[4]), hitc2 ) );
+
+					B1 = AddSIMD(
+						B1, ReplicateX4( tri->m_ProjectedEdgeEquations[5] ) );
+					
+					did_hit = AndSIMD( did_hit, CmpGeSIMD( B1, FourZeros ) );
+
+					fltx4 B2 = AddSIMD( B1, B0 );
+					did_hit = AndSIMD( did_hit, CmpLeSIMD( B2, Four_Ones ) );
+
+					if ( ! IsAnyNegative( did_hit ) )
+						continue;
+
+					// if the triangle is transparent
+					if ( tri->m_nFlags & FCACHETRI_TRANSPARENT )
+					{
+						if ( pCallback )
+						{
+							// assuming a triangle indexed as v0, v1, v2
+							// the projected edge equations are set up such that the vert opposite the first
+							// equation is v2, and the vert opposite the second equation is v0
+							// Therefore we pass them back in 1, 2, 0 order
+							// Also B2 is currently B1 + B0 and needs to be 1 - (B1+B0) in order to be a real
+							// barycentric coordinate.  Compute that now and pass it to the callback
+							fltx4 b2 = SubSIMD( Four_Ones, B2 );
+							if ( pCallback->VisitTriangle_ShouldContinue( *tri, rays, &did_hit, &B1, &b2, &B0, tnum ) )
+							{
+								did_hit = Four_Zeros;
+							}
+						}
+					}
+					// now, set the hit_id and closest_hit fields for any enabled rays
+					fltx4 replicated_n = ReplicateIX4(tnum);
+					StoreAlignedSIMD((float *) rslt_out->HitIds,
+								 OrSIMD(AndSIMD(replicated_n,did_hit),
+										   AndNotSIMD(did_hit,LoadAlignedSIMD(
+															 (float *) rslt_out->HitIds))));
+					rslt_out->HitDistance=OrSIMD(AndSIMD(isect_t,did_hit),
+									 AndNotSIMD(did_hit,rslt_out->HitDistance));
+
+					rslt_out->surface_normal.x=OrSIMD(
+						AndSIMD(N.x,did_hit),
+						AndNotSIMD(did_hit,rslt_out->surface_normal.x));
+					rslt_out->surface_normal.y=OrSIMD(
+						AndSIMD(N.y,did_hit),
+						AndNotSIMD(did_hit,rslt_out->surface_normal.y));
+					rslt_out->surface_normal.z=OrSIMD(
+						AndSIMD(N.z,did_hit),
+						AndNotSIMD(did_hit,rslt_out->surface_normal.z));
+					
+				}
+			} while (--ntris);
+			// now, check if all rays have terminated
+			fltx4 raydone=CmpLeSIMD(TMax,rslt_out->HitDistance);
+			if (! IsAnyNegative(raydone))
+			{
+				return;
+			}
+		}
+		
+ 		if (stack_ptr==&NodeQueue[MAX_NODE_STACK_LEN])
+		{
+			return;
+		}
+		// pop stack!
+		CurNode=stack_ptr->node;
+		TMin=stack_ptr->TMin;
+		TMax=stack_ptr->TMax;
+		stack_ptr++;
+	}
+}
+
+
+int RayTracingEnvironment::MakeLeafNode(int first_tri, int last_tri)
+{
+	CacheOptimizedKDNode ret;
+	ret.Children=KDNODE_STATE_LEAF+(TriangleIndexList.Count()<<2);
+	ret.SetNumberOfTrianglesInLeafNode(1+(last_tri-first_tri));
+	for(int tnum=first_tri;tnum<=last_tri;tnum++)
+		TriangleIndexList.AddToTail(tnum);
+	OptimizedKDTree.AddToTail(ret);
+	return OptimizedKDTree.Count()-1;
+}
+
+
+void RayTracingEnvironment::CalculateTriangleListBounds(int32 const *tris,int ntris,
+														Vector &minout, Vector &maxout)
+{
+	minout = Vector( 1.0e23, 1.0e23, 1.0e23);
+	maxout = Vector( -1.0e23, -1.0e23, -1.0e23);
+	for(int i=0; i<ntris; i++)
+	{
+		CacheOptimizedTriangle const &tri=OptimizedTriangleList[tris[i]];
+		for(int v=0; v<3; v++)
+			for(int c=0; c<3; c++)
+			{
+				minout[c]=min(minout[c],tri.Vertex(v)[c]);
+							  maxout[c]=max(maxout[c],tri.Vertex(v)[c]);
+			}
+	}
+}
+
+
+// Both the "quick" and regular kd tree building algorithms here use the "surface area heuristic":
+// the relative probability of hitting the "left" subvolume (Vl) from a split is equal to that
+// subvolume's surface area divided by its parent's surface area (Vp) : P(Vl | V)=SA(Vl)/SA(Vp).
+// The same holds for the right subvolume, Vp. Nl is the number of triangles in the left volume,
+// and Nr in the right volume. if Ct is the cost of traversing one tree node, and Ci is the cost of
+// intersection with the primitive, than the cost of splitting is estimated as:
+//
+//    Ct+Ci*((SA(Vl)/SA(V))*Nl+(SA(Vr)/SA(V)*Nr)).
+// and the cost of not splitting is
+//    Ci*N
+//
+//  This both provides a metric to minimize when computing how and where to split, and also a
+//  termination criterion.
+//
+// the "quick" method just splits down the middle, while the slow method splits at the best
+// discontinuity of the cost formula. The quick method splits along the longest axis ; the 
+// regular algorithm tries all 3 to find which one results in the minimum cost
+// 
+// both methods use the additional optimization of "growing" empty nodes - if the split results in
+// one side being devoid of triangles, the empty side is "grown" as much as possible.
+//
+
+#define COST_OF_TRAVERSAL 75								// approximate #operations
+#define COST_OF_INTERSECTION 167							// approximate #operations
+
+
+float RayTracingEnvironment::CalculateCostsOfSplit(
+	int split_plane,int32 const *tri_list,int ntris,
+	Vector MinBound,Vector MaxBound, float &split_value,
+	int &nleft, int &nright, int &nboth)
+{
+	// determine the costs of splitting on a given axis, and label triangles with respect to
+	// that axis by storing the value in coordselect0. It will also return the number of
+	// tris in the left, right, and nboth groups, in order to facilitate memory
+	nleft=nboth=nright=0;
+	
+	// now, label each triangle. Since we have not converted the triangles into
+	// intersection fromat yet, we can use the CoordSelect0 field of each as a temp.
+	nleft=0;
+	nright=0;
+	nboth=0;
+	float min_coord=1.0e23,max_coord=-1.0e23;
+
+	for(int t=0;t<ntris;t++)
+	{
+		CacheOptimizedTriangle &tri=OptimizedTriangleList[tri_list[t]];
+		// determine max and min coordinate values for later optimization
+		for(int v=0;v<3;v++)
+		{
+			min_coord = min( min_coord, tri.Vertex(v)[split_plane] );
+			max_coord = max( max_coord, tri.Vertex(v)[split_plane] );
+		}
+		switch(tri.ClassifyAgainstAxisSplit(split_plane,split_value))
+		{
+			case PLANECHECK_NEGATIVE:
+				nleft++;
+				tri.m_Data.m_GeometryData.m_nTmpData0 = PLANECHECK_NEGATIVE;
+				break;
+
+			case PLANECHECK_POSITIVE:
+				nright++;
+				tri.m_Data.m_GeometryData.m_nTmpData0 = PLANECHECK_POSITIVE;
+				break;
+
+			case PLANECHECK_STRADDLING:
+				nboth++;
+				tri.m_Data.m_GeometryData.m_nTmpData0 = PLANECHECK_STRADDLING;
+				break;
+		}
+	}
+	// now, if the split resulted in one half being empty, "grow" the empty half
+	if (nleft && (nboth==0) && (nright==0))
+		split_value=max_coord;
+	if (nright && (nboth==0) && (nleft==0))
+		split_value=min_coord;
+
+	// now, perform surface area/cost check to determine whether this split was worth it
+	Vector LeftMins=MinBound;
+	Vector LeftMaxes=MaxBound;
+	Vector RightMins=MinBound;
+	Vector RightMaxes=MaxBound;
+	LeftMaxes[split_plane]=split_value;
+	RightMins[split_plane]=split_value;
+	float SA_L=BoxSurfaceArea(LeftMins,LeftMaxes);
+	float SA_R=BoxSurfaceArea(RightMins,RightMaxes);
+	float ISA=1.0/BoxSurfaceArea(MinBound,MaxBound);
+	float cost_of_split=COST_OF_TRAVERSAL+COST_OF_INTERSECTION*(nboth+
+		(SA_L*ISA*(nleft))+(SA_R*ISA*(nright)));
+	return cost_of_split;
+}
+
+
+#define NEVER_SPLIT 0
+
+void RayTracingEnvironment::RefineNode(int node_number,int32 const *tri_list,int ntris,
+									   Vector MinBound,Vector MaxBound, int depth)
+{
+	if (ntris<3)											// never split empty lists
+	{
+		// no point in continuing
+		OptimizedKDTree[node_number].Children=KDNODE_STATE_LEAF+(TriangleIndexList.Count()<<2);
+		OptimizedKDTree[node_number].SetNumberOfTrianglesInLeafNode(ntris);
+
+#ifdef DEBUG_RAYTRACE
+		OptimizedKDTree[node_number].vecMins = MinBound;
+		OptimizedKDTree[node_number].vecMaxs = MaxBound;
+#endif
+
+		for(int t=0;t<ntris;t++)
+			TriangleIndexList.AddToTail(tri_list[t]);
+		return;
+	}
+
+	float best_cost=1.0e23;
+	int best_nleft=0,best_nright=0,best_nboth=0;
+	float best_splitvalue=0;
+	int split_plane=0;
+
+	int tri_skip=1+(ntris/10);								// don't try all trinagles as split
+															// points when there are a lot of them
+	for(int axis=0;axis<3;axis++)
+	{
+		for(int ts=-1;ts<ntris;ts+=tri_skip)
+		{
+			for(int tv=0;tv<3;tv++)
+			{
+				int trial_nleft,trial_nright,trial_nboth;
+				float trial_splitvalue;
+				if (ts==-1)
+					trial_splitvalue=0.5*(MinBound[axis]+MaxBound[axis]);
+				else
+				{
+					// else, split at the triangle vertex if possible
+					CacheOptimizedTriangle &tri=OptimizedTriangleList[tri_list[ts]];
+					trial_splitvalue = tri.Vertex(tv)[axis];
+					if ((trial_splitvalue>MaxBound[axis]) || (trial_splitvalue<MinBound[axis]))
+						continue;							// don't try this vertex - not inside
+					
+				}
+//				printf("ts=%d tv=%d tp=%f\n",ts,tv,trial_splitvalue);
+				float trial_cost=
+					CalculateCostsOfSplit(axis,tri_list,ntris,MinBound,MaxBound,trial_splitvalue,
+										  trial_nleft,trial_nright, trial_nboth);
+// 				printf("try %d cost=%f nl=%d nr=%d nb=%d sp=%f\n",axis,trial_cost,trial_nleft,trial_nright, trial_nboth,
+// 					   trial_splitvalue);
+				if (trial_cost<best_cost)
+				{
+					split_plane=axis;
+					best_cost=trial_cost;
+					best_nleft=trial_nleft;
+					best_nright=trial_nright;
+					best_nboth=trial_nboth;
+					best_splitvalue=trial_splitvalue;
+					// save away the axis classification of each triangle
+					for(int t=0 ; t < ntris; t++)
+					{
+						CacheOptimizedTriangle &tri=OptimizedTriangleList[tri_list[t]];
+						tri.m_Data.m_GeometryData.m_nTmpData1 = tri.m_Data.m_GeometryData.m_nTmpData0;
+					}
+				}
+				if (ts==-1)
+					break;
+			}
+		}
+
+	}
+	float cost_of_no_split=COST_OF_INTERSECTION*ntris;
+	if ( (cost_of_no_split<=best_cost) || NEVER_SPLIT || (depth>MAX_TREE_DEPTH))
+	{
+		// no benefit to splitting. just make this a leaf node
+		OptimizedKDTree[node_number].Children=KDNODE_STATE_LEAF+(TriangleIndexList.Count()<<2);
+		OptimizedKDTree[node_number].SetNumberOfTrianglesInLeafNode(ntris);
+#ifdef DEBUG_RAYTRACE
+		OptimizedKDTree[node_number].vecMins = MinBound;
+		OptimizedKDTree[node_number].vecMaxs = MaxBound;
+#endif
+		for(int t=0;t<ntris;t++)
+			TriangleIndexList.AddToTail(tri_list[t]);
+	}
+	else
+	{
+// 		printf("best split was %d at %f (mid=%f,n=%d, sk=%d)\n",split_plane,best_splitvalue,
+// 			   0.5*(MinBound[split_plane]+MaxBound[split_plane]),ntris,tri_skip);
+		// its worth splitting!
+		// we will achieve the splitting without sorting by using a selection algorithm.
+		int32 *new_triangle_list;
+		new_triangle_list=new int32[ntris];
+
+		// now, perform surface area/cost check to determine whether this split was worth it
+		Vector LeftMins=MinBound;
+		Vector LeftMaxes=MaxBound;
+		Vector RightMins=MinBound;
+		Vector RightMaxes=MaxBound;
+		LeftMaxes[split_plane]=best_splitvalue;
+		RightMins[split_plane]=best_splitvalue;
+		
+		int n_left_output=0;
+		int n_both_output=0;
+		int n_right_output=0;
+		for(int t=0;t<ntris;t++)
+		{
+			CacheOptimizedTriangle &tri=OptimizedTriangleList[tri_list[t]];
+			switch( tri.m_Data.m_GeometryData.m_nTmpData1 )
+			{
+				case PLANECHECK_NEGATIVE:
+//					printf("%d goes left\n",t);
+					new_triangle_list[n_left_output++]=tri_list[t];
+					break;
+				case PLANECHECK_POSITIVE:
+					n_right_output++;
+//					printf("%d goes right\n",t);
+					new_triangle_list[ntris-n_right_output]=tri_list[t];
+					break;
+				case PLANECHECK_STRADDLING:
+//					printf("%d goes both\n",t);
+					new_triangle_list[best_nleft+n_both_output]=tri_list[t];
+					n_both_output++;
+					break;
+
+					
+			}
+		}
+		int left_child=OptimizedKDTree.Count();
+		int right_child=left_child+1;
+// 		printf("node %d split on axis %d at %f, nl=%d nr=%d nb=%d lc=%d rc=%d\n",node_number,
+// 			   split_plane,best_splitvalue,best_nleft,best_nright,best_nboth,
+// 			   left_child,right_child);
+		OptimizedKDTree[node_number].Children=split_plane+(left_child<<2);
+		OptimizedKDTree[node_number].SplittingPlaneValue=best_splitvalue;
+#ifdef DEBUG_RAYTRACE
+		OptimizedKDTree[node_number].vecMins = MinBound;
+		OptimizedKDTree[node_number].vecMaxs = MaxBound;
+#endif
+		CacheOptimizedKDNode newnode;
+		OptimizedKDTree.AddToTail(newnode);
+		OptimizedKDTree.AddToTail(newnode);
+		// now, recurse!
+		if ( (ntris<20) && ((best_nleft==0) || (best_nright==0)) )
+			depth+=100;
+		RefineNode(left_child,new_triangle_list,best_nleft+best_nboth,LeftMins,LeftMaxes,depth+1);
+		RefineNode(right_child,new_triangle_list+best_nleft,best_nright+best_nboth,
+				   RightMins,RightMaxes,depth+1);
+		delete[] new_triangle_list;
+	}	
+}
+
+
+void RayTracingEnvironment::SetupAccelerationStructure(void)
+{
+	CacheOptimizedKDNode root;
+	OptimizedKDTree.AddToTail(root);
+	int32 *root_triangle_list=new int32[OptimizedTriangleList.Count()];
+	for(int t=0;t<OptimizedTriangleList.Count();t++)
+		root_triangle_list[t]=t;
+	CalculateTriangleListBounds(root_triangle_list,OptimizedTriangleList.Count(),m_MinBound,
+								m_MaxBound);
+	RefineNode(0,root_triangle_list,OptimizedTriangleList.Count(),m_MinBound,m_MaxBound,0);
+	delete[] root_triangle_list;
+
+	// now, convert all triangles to "intersection format"
+	for(int i=0;i<OptimizedTriangleList.Count();i++)
+		OptimizedTriangleList[i].ChangeIntoIntersectionFormat();
+}
+
+
+
+void RayTracingEnvironment::AddInfinitePointLight(Vector position, Vector intensity)
+{
+	LightDesc_t mylight(position,intensity);
+	LightList.AddToTail(mylight);
+	
+}
+
+
diff --git a/mp/src/raytrace/raytrace.vpc b/mp/src/raytrace/raytrace.vpc
index d8504ec4..aafd2041 100644
--- a/mp/src/raytrace/raytrace.vpc
+++ b/mp/src/raytrace/raytrace.vpc
@@ -1,26 +1,26 @@
-//-----------------------------------------------------------------------------

-//	RAYTRACE.VPC

-//

-//	Project Script

-//-----------------------------------------------------------------------------

-

-$Macro SRCDIR		".."

-$Include "$SRCDIR\vpc_scripts\source_lib_base.vpc"

-

-$Configuration

-{

-	$Compiler

-	{

-		$AdditionalIncludeDirectories		"$BASE,$SRCDIR\utils\common"

-	}

-}

-

-$Project "Raytrace"

-{

-	$Folder	"Source Files"

-	{

-		$File	"raytrace.cpp"

-		$File	"trace2.cpp"

-		$File	"trace3.cpp"

-	}

-}

+//-----------------------------------------------------------------------------
+//	RAYTRACE.VPC
+//
+//	Project Script
+//-----------------------------------------------------------------------------
+
+$Macro SRCDIR		".."
+$Include "$SRCDIR\vpc_scripts\source_lib_base.vpc"
+
+$Configuration
+{
+	$Compiler
+	{
+		$AdditionalIncludeDirectories		"$BASE,$SRCDIR\utils\common"
+	}
+}
+
+$Project "Raytrace"
+{
+	$Folder	"Source Files"
+	{
+		$File	"raytrace.cpp"
+		$File	"trace2.cpp"
+		$File	"trace3.cpp"
+	}
+}
diff --git a/mp/src/raytrace/trace2.cpp b/mp/src/raytrace/trace2.cpp
index f7f4ed7e..f419cc76 100644
--- a/mp/src/raytrace/trace2.cpp
+++ b/mp/src/raytrace/trace2.cpp
@@ -1,376 +1,376 @@
-//========= Copyright Valve Corporation, All rights reserved. ============//

-// $Id$

-#include "raytrace.h"

-#include <mathlib/halton.h>

-

-static uint32 MapDistanceToPixel(float t)

-{

-	if (t<0) return 0xffff0000;

-	if (t>100) return 0xff000000;

-	int a=t*1000; a&=0xff;

-	int b=t*10; b &=0xff;

-	int c=t*.01; c &=0xff;

-	return 0xff000000+(a<<16)+(b<<8)+c;

-}

-

-#define IGAMMA (1.0/2.2)

-

-#define MAGIC_NUMBER (1<<23)

-

-static fltx4 Four_MagicNumbers={ MAGIC_NUMBER, MAGIC_NUMBER, MAGIC_NUMBER, MAGIC_NUMBER };

-static ALIGN16 int32 Four_255s[4]= {0xff,0xff,0xff,0xff};

-#define PIXMASK ( * ( reinterpret_cast< fltx4 *>( &Four_255s ) ) )

-

-void MapLinearIntensities(FourVectors const &intens,uint32 *p1, uint32 *p2, uint32 *p3, uint32 *p4)

-{

-	// convert four pixels worth of sse-style rgb into argb lwords

-	// NOTE the _mm_empty macro is voodoo. do not mess with this routine casually - simply throwing

-	// anything that ends up generating a fpu stack references in here would be bad news.

-	static fltx4 pixscale={255.0,255.0,255.0,255.0};

-	fltx4 r,g,b;

-	r=MinSIMD(pixscale,MulSIMD(pixscale,PowSIMD(intens.x,IGAMMA)));

-	g=MinSIMD(pixscale,MulSIMD(pixscale,PowSIMD(intens.y,IGAMMA)));

-	b=MinSIMD(pixscale,MulSIMD(pixscale,PowSIMD(intens.z,IGAMMA)));

-	// now, convert to integer

-	r=AndSIMD( AddSIMD( r, Four_MagicNumbers ), PIXMASK );

-	g=AndSIMD( AddSIMD( g, Four_MagicNumbers ), PIXMASK );

-	b=AndSIMD( AddSIMD( b, Four_MagicNumbers ), PIXMASK );

-

-	*(p1)=(SubInt(r, 0))|(SubInt(g, 0)<<8)|(SubInt(b, 0)<<16);

-	*(p2)=(SubInt(r, 1))|(SubInt(g, 1)<<8)|(SubInt(b, 1)<<16);

-	*(p3)=(SubInt(r, 2))|(SubInt(g, 2)<<8)|(SubInt(b, 2)<<16);

-	*(p4)=(SubInt(r, 3))|(SubInt(g, 3)<<8)|(SubInt(b, 3)<<16);

-}

-

-static ALIGN16 int32 signmask[4]={0x80000000,0x80000000,0x80000000,0x80000000};

-static ALIGN16 int32 all_ones[4]={-1,-1,-1,-1};

-static fltx4 all_zeros={0,0,0,0};

-static fltx4 TraceLimit={1.0e20,1.0e20,1.0e20,1.0e20};

-

-void RayTracingEnvironment::RenderScene(

-	int width, int height,								   // width and height of desired rendering

-	int stride,											 // actual width in pixels of target buffer

-	uint32 *output_buffer,									// pointer to destination 

-	Vector CameraOrigin,									// eye position

-	Vector ULCorner,										// word space coordinates of upper left

-															// monitor corner

-	Vector URCorner,										// top right corner

-	Vector LLCorner,										// lower left

-	Vector LRCorner,										// lower right

-	RayTraceLightingMode_t lmode)

-{

-	// first, compute deltas

-	Vector dxvector=URCorner;

-	dxvector-=ULCorner;

-	dxvector*=(1.0/width);

-	Vector dxvectortimes2=dxvector;

-	dxvectortimes2+=dxvector;

-

-	Vector dyvector=LLCorner;

-	dyvector-=ULCorner;

-	dyvector*=(1.0/height);

-

-

-	// block_offsets-relative offsets for eahc of the 4 pixels in the block, in sse format

-	FourVectors block_offsets;

-	block_offsets.LoadAndSwizzle(Vector(0,0,0),dxvector,dyvector,dxvector+dyvector);

-	

-	FourRays myrays;

-	myrays.origin.DuplicateVector(CameraOrigin);

-	

-	// tmprays is used fo rthe case when we cannot trace 4 rays at once.

-	FourRays tmprays;

-	tmprays.origin.DuplicateVector(CameraOrigin);

-

-	// now, we will ray trace pixels. we will do the rays in a 2x2 pattern

-	for(int y=0;y<height;y+=2)

-	{

-		Vector SLoc=dyvector;

-		SLoc*=((float) y);

-		SLoc+=ULCorner;

-		uint32 *dest=output_buffer+y*stride;

-		for(int x=0;x<width;x+=2)

-		{

-			myrays.direction.DuplicateVector(SLoc);

-			myrays.direction+=block_offsets;

-			myrays.direction.VectorNormalize();

-			

-			RayTracingResult rslt;

-			Trace4Rays(myrays,all_zeros,TraceLimit, &rslt);

-			if ((rslt.HitIds[0]==-1) && (rslt.HitIds[1]==-1) && 

-				(rslt.HitIds[2]==-1) && (rslt.HitIds[3]==-1))

-				MapLinearIntensities(BackgroundColor,dest,dest+1,dest+stride,dest+stride+1);

-			else

-			{

-				// make sure normal points back towards ray origin

-				fltx4 ndoti=rslt.surface_normal*myrays.direction;

-				fltx4 bad_dirs=AndSIMD(CmpGtSIMD(ndoti,Four_Zeros),

-										   LoadAlignedSIMD((float *) signmask));

-

-				// flip signs of all "wrong" normals

-				rslt.surface_normal.x=XorSIMD(bad_dirs,rslt.surface_normal.x);

-				rslt.surface_normal.y=XorSIMD(bad_dirs,rslt.surface_normal.y);

-				rslt.surface_normal.z=XorSIMD(bad_dirs,rslt.surface_normal.z);

-

-				FourVectors intens;

-				intens.DuplicateVector(Vector(0,0,0));

-				// set up colors

-				FourVectors surf_colors;

-				surf_colors.DuplicateVector(Vector(0,0,0));

-				for(int i=0;i<4;i++)

-				{

-					if (rslt.HitIds[i]>=0)

-					{

-						surf_colors.X(i)=TriangleColors[rslt.HitIds[i]].x;

-						surf_colors.Y(i)=TriangleColors[rslt.HitIds[i]].y;

-						surf_colors.Z(i)=TriangleColors[rslt.HitIds[i]].z;

-					}

-

-				}

-				FourVectors surface_pos=myrays.direction;

-				surface_pos*=rslt.HitDistance;

-				surface_pos+=myrays.origin;

-				

-				switch(lmode)

-				{

-					case DIRECT_LIGHTING:

-					{

-						// light all points

-						for(int l=0;l<LightList.Count();l++)

-						{

-							LightList[l].ComputeLightAtPoints(surface_pos,rslt.surface_normal,

-															  intens);

-						}

-					}

-					break;

-

-					case DIRECT_LIGHTING_WITH_SHADOWS:

-					{

-						// light all points

-						for(int l=0;l<LightList.Count();l++)

-						{

-							FourVectors ldir;

-							ldir.DuplicateVector(LightList[l].m_Position);

-							ldir-=surface_pos;

-							fltx4 MaxT=ldir.length();

-							ldir.VectorNormalizeFast();

-							// now, compute shadow flag

-							FourRays myrays;

-							myrays.origin=surface_pos;

-							FourVectors epsilon=ldir;

-							epsilon*=0.01;

-							myrays.origin+=epsilon;

-							myrays.direction=ldir;

-							RayTracingResult shadowtest;

-							Trace4Rays(myrays,Four_Zeros,MaxT, &shadowtest);

-							fltx4 unshadowed=CmpGtSIMD(shadowtest.HitDistance,MaxT);

-							if (! (IsAllZeros(unshadowed)))

-							{

-								FourVectors tmp;

-								tmp.DuplicateVector(Vector(0,0,0));

-								LightList[l].ComputeLightAtPoints(surface_pos,rslt.surface_normal,

-																  tmp);

-								intens.x=AddSIMD(intens.x,AndSIMD(tmp.x,unshadowed));

-								intens.y=AddSIMD(intens.y,AndSIMD(tmp.y,unshadowed));

-								intens.z=AddSIMD(intens.z,AndSIMD(tmp.z,unshadowed));

-							}

-						}

-					}

-					break;

-				}

-				// now, mask off non-hitting pixels

-				intens.VProduct(surf_colors);

-				fltx4 no_hit_mask=CmpGtSIMD(rslt.HitDistance,TraceLimit);

-				

-				intens.x=OrSIMD(AndSIMD(BackgroundColor.x,no_hit_mask),

-								   AndNotSIMD(no_hit_mask,intens.x));

-				intens.y=OrSIMD(AndSIMD(BackgroundColor.y,no_hit_mask),

-								   AndNotSIMD(no_hit_mask,intens.y));

-				intens.z=OrSIMD(AndSIMD(BackgroundColor.y,no_hit_mask),

-								   AndNotSIMD(no_hit_mask,intens.z));

-

-				MapLinearIntensities(intens,dest,dest+1,dest+stride,dest+stride+1);

-			}

-			dest+=2;

-			SLoc+=dxvectortimes2;

-		}

-	}

-}

-

-

-

-

-#define SQ(x) ((x)*(x))

-

-void RayTracingEnvironment::ComputeVirtualLightSources(void)

-{

-	int start_pos=0;

-	for(int b=0;b<3;b++)

-	{

-		int nl=LightList.Count();

-		int where_to_start=start_pos;

-		start_pos=nl;

-		for(int l=where_to_start;l<nl;l++)

-		{

-			DirectionalSampler_t sample_generator;

-			int n_desired=1*LightList[l].m_Color.Length();

-			if (LightList[l].m_Type==MATERIAL_LIGHT_SPOT)

-				n_desired*=LightList[l].m_Phi/2;

-			for(int try1=0;try1<n_desired;try1++)

-			{

-				LightDesc_t const &li=LightList[l];

-				FourRays myrays;

-				myrays.origin.DuplicateVector(li.m_Position);

-				RayTracingResult rslt;

-				Vector trial_dir=sample_generator.NextValue();

-				if (li.IsDirectionWithinLightCone(trial_dir))

-				{

-					myrays.direction.DuplicateVector(trial_dir);

-					Trace4Rays(myrays,all_zeros,ReplicateX4(1000.0), &rslt);

-					if ((rslt.HitIds[0]!=-1))

-					{

-						// make sure normal points back towards ray origin

-						fltx4 ndoti=rslt.surface_normal*myrays.direction;

-						fltx4 bad_dirs=AndSIMD(CmpGtSIMD(ndoti,Four_Zeros),

-												   LoadAlignedSIMD((float *) signmask));

-						

-						// flip signs of all "wrong" normals

-						rslt.surface_normal.x=XorSIMD(bad_dirs,rslt.surface_normal.x);

-						rslt.surface_normal.y=XorSIMD(bad_dirs,rslt.surface_normal.y);

-						rslt.surface_normal.z=XorSIMD(bad_dirs,rslt.surface_normal.z);

-

-						// a hit! let's make a virtual light source

-

-						// treat the virtual light as a disk with its center at the hit position

-						// and its radius scaled by the amount of the solid angle this probe

-						// represents.

-						float area_of_virtual_light=

-							4.0*M_PI*SQ( SubFloat( rslt.HitDistance, 0 ) )*(1.0/n_desired);

-

-						FourVectors intens;

-						intens.DuplicateVector(Vector(0,0,0));

-

-						FourVectors surface_pos=myrays.direction;

-						surface_pos*=rslt.HitDistance;

-						surface_pos+=myrays.origin;

-						FourVectors delta=rslt.surface_normal;

-						delta*=0.1;

-						surface_pos+=delta;

-						LightList[l].ComputeLightAtPoints(surface_pos,rslt.surface_normal,

-														  intens);

-						FourVectors surf_colors;

-						surf_colors.DuplicateVector(TriangleColors[rslt.HitIds[0]]);

-						intens*=surf_colors;

-						// see if significant

-						LightDesc_t l1;

-						l1.m_Type=MATERIAL_LIGHT_SPOT;

-						l1.m_Position=Vector(surface_pos.X(0),surface_pos.Y(0),surface_pos.Z(0));

-						l1.m_Direction=Vector(rslt.surface_normal.X(0),rslt.surface_normal.Y(0),

-											  rslt.surface_normal.Z(0));

-						l1.m_Color=Vector(intens.X(0),intens.Y(0),intens.Z(0));

-						if (l1.m_Color.Length()>0)

-						{

-							l1.m_Color*=area_of_virtual_light/M_PI;

-							l1.m_Range=0.0;

-							l1.m_Falloff=1.0;

-							l1.m_Attenuation0=1.0;

-							l1.m_Attenuation1=0.0;

-							l1.m_Attenuation2=1.0;			// intens falls off as 1/r^2

-							l1.m_Theta=0;

-							l1.m_Phi=M_PI;

-							l1.RecalculateDerivedValues();

-							LightList.AddToTail(l1);

-						}

-					}

-				}

-			}

-		}

-	}

-}

-

-

-

-static unsigned int GetSignMask(Vector const &v)

-{

-	unsigned int ret=0;

-	if (v.x<0.0)

-		ret++;

-	if (v.y<0)

-		ret+=2;

-	if (v.z<0)

-		ret+=4;

-	return ret;

-}

-

-

-inline void RayTracingEnvironment::FlushStreamEntry(RayStream &s,int msk)

-{

-	assert(msk>=0);

-	assert(msk<8);

-	fltx4 tmax=s.PendingRays[msk].direction.length();

-	fltx4 scl=ReciprocalSaturateSIMD(tmax);

-	s.PendingRays[msk].direction*=scl;					// normalize

-	RayTracingResult tmpresult;

-	Trace4Rays(s.PendingRays[msk],Four_Zeros,tmax,msk,&tmpresult);

-	// now, write out results

-	for(int r=0;r<4;r++)

-	{

-		RayTracingSingleResult *out=s.PendingStreamOutputs[msk][r];

-		out->ray_length=SubFloat( tmax, r );

-		out->surface_normal.x=tmpresult.surface_normal.X(r);

-		out->surface_normal.y=tmpresult.surface_normal.Y(r);

-		out->surface_normal.z=tmpresult.surface_normal.Z(r);

-		out->HitID=tmpresult.HitIds[r];

-		out->HitDistance=SubFloat( tmpresult.HitDistance, r );

-	}

-	s.n_in_stream[msk]=0;

-}

-

-void RayTracingEnvironment::AddToRayStream(RayStream &s,

-										   Vector const &start,Vector const &end,

-										   RayTracingSingleResult *rslt_out)

-{

-	Vector delta=end;

-	delta-=start;

-	int msk=GetSignMask(delta);

-	assert(msk>=0);

-	assert(msk<8);

-	int pos=s.n_in_stream[msk];

-	assert(pos<4);

-	s.PendingRays[msk].origin.X(pos)=start.x;

-	s.PendingRays[msk].origin.Y(pos)=start.y;

-	s.PendingRays[msk].origin.Z(pos)=start.z;

-	s.PendingRays[msk].direction.X(pos)=delta.x;

-	s.PendingRays[msk].direction.Y(pos)=delta.y;

-	s.PendingRays[msk].direction.Z(pos)=delta.z;

-	s.PendingStreamOutputs[msk][pos]=rslt_out;

-	if (pos==3)

-	{

-		FlushStreamEntry(s,msk);

-	}

-	else

-		s.n_in_stream[msk]++;

-}

-

-void RayTracingEnvironment::FinishRayStream(RayStream &s)

-{

-	for(int msk=0;msk<8;msk++)

-	{

-		int cnt=s.n_in_stream[msk];

-		if (cnt)

-		{

-			// fill in unfilled entries with dups of first

-			for(int c=cnt;c<4;c++)

-			{

-				s.PendingRays[msk].origin.X(c) = s.PendingRays[msk].origin.X(0);

-				s.PendingRays[msk].origin.Y(c) = s.PendingRays[msk].origin.Y(0);

-				s.PendingRays[msk].origin.Z(c) = s.PendingRays[msk].origin.Z(0);

-				s.PendingRays[msk].direction.X(c) = s.PendingRays[msk].direction.X(0);

-				s.PendingRays[msk].direction.Y(c) = s.PendingRays[msk].direction.Y(0);

-				s.PendingRays[msk].direction.Z(c) = s.PendingRays[msk].direction.Z(0);

-				s.PendingStreamOutputs[msk][c]=s.PendingStreamOutputs[msk][0];

-			}

-			FlushStreamEntry(s,msk);

-		}

-	}

-}

+//========= Copyright Valve Corporation, All rights reserved. ============//
+// $Id$
+#include "raytrace.h"
+#include <mathlib/halton.h>
+
+static uint32 MapDistanceToPixel(float t)
+{
+	if (t<0) return 0xffff0000;
+	if (t>100) return 0xff000000;
+	int a=t*1000; a&=0xff;
+	int b=t*10; b &=0xff;
+	int c=t*.01; c &=0xff;
+	return 0xff000000+(a<<16)+(b<<8)+c;
+}
+
+#define IGAMMA (1.0/2.2)
+
+#define MAGIC_NUMBER (1<<23)
+
+static fltx4 Four_MagicNumbers={ MAGIC_NUMBER, MAGIC_NUMBER, MAGIC_NUMBER, MAGIC_NUMBER };
+static ALIGN16 int32 Four_255s[4]= {0xff,0xff,0xff,0xff};
+#define PIXMASK ( * ( reinterpret_cast< fltx4 *>( &Four_255s ) ) )
+
+void MapLinearIntensities(FourVectors const &intens,uint32 *p1, uint32 *p2, uint32 *p3, uint32 *p4)
+{
+	// convert four pixels worth of sse-style rgb into argb lwords
+	// NOTE the _mm_empty macro is voodoo. do not mess with this routine casually - simply throwing
+	// anything that ends up generating a fpu stack references in here would be bad news.
+	static fltx4 pixscale={255.0,255.0,255.0,255.0};
+	fltx4 r,g,b;
+	r=MinSIMD(pixscale,MulSIMD(pixscale,PowSIMD(intens.x,IGAMMA)));
+	g=MinSIMD(pixscale,MulSIMD(pixscale,PowSIMD(intens.y,IGAMMA)));
+	b=MinSIMD(pixscale,MulSIMD(pixscale,PowSIMD(intens.z,IGAMMA)));
+	// now, convert to integer
+	r=AndSIMD( AddSIMD( r, Four_MagicNumbers ), PIXMASK );
+	g=AndSIMD( AddSIMD( g, Four_MagicNumbers ), PIXMASK );
+	b=AndSIMD( AddSIMD( b, Four_MagicNumbers ), PIXMASK );
+
+	*(p1)=(SubInt(r, 0))|(SubInt(g, 0)<<8)|(SubInt(b, 0)<<16);
+	*(p2)=(SubInt(r, 1))|(SubInt(g, 1)<<8)|(SubInt(b, 1)<<16);
+	*(p3)=(SubInt(r, 2))|(SubInt(g, 2)<<8)|(SubInt(b, 2)<<16);
+	*(p4)=(SubInt(r, 3))|(SubInt(g, 3)<<8)|(SubInt(b, 3)<<16);
+}
+
+static ALIGN16 int32 signmask[4]={0x80000000,0x80000000,0x80000000,0x80000000};
+static ALIGN16 int32 all_ones[4]={-1,-1,-1,-1};
+static fltx4 all_zeros={0,0,0,0};
+static fltx4 TraceLimit={1.0e20,1.0e20,1.0e20,1.0e20};
+
+void RayTracingEnvironment::RenderScene(
+	int width, int height,								   // width and height of desired rendering
+	int stride,											 // actual width in pixels of target buffer
+	uint32 *output_buffer,									// pointer to destination 
+	Vector CameraOrigin,									// eye position
+	Vector ULCorner,										// word space coordinates of upper left
+															// monitor corner
+	Vector URCorner,										// top right corner
+	Vector LLCorner,										// lower left
+	Vector LRCorner,										// lower right
+	RayTraceLightingMode_t lmode)
+{
+	// first, compute deltas
+	Vector dxvector=URCorner;
+	dxvector-=ULCorner;
+	dxvector*=(1.0/width);
+	Vector dxvectortimes2=dxvector;
+	dxvectortimes2+=dxvector;
+
+	Vector dyvector=LLCorner;
+	dyvector-=ULCorner;
+	dyvector*=(1.0/height);
+
+
+	// block_offsets-relative offsets for eahc of the 4 pixels in the block, in sse format
+	FourVectors block_offsets;
+	block_offsets.LoadAndSwizzle(Vector(0,0,0),dxvector,dyvector,dxvector+dyvector);
+	
+	FourRays myrays;
+	myrays.origin.DuplicateVector(CameraOrigin);
+	
+	// tmprays is used fo rthe case when we cannot trace 4 rays at once.
+	FourRays tmprays;
+	tmprays.origin.DuplicateVector(CameraOrigin);
+
+	// now, we will ray trace pixels. we will do the rays in a 2x2 pattern
+	for(int y=0;y<height;y+=2)
+	{
+		Vector SLoc=dyvector;
+		SLoc*=((float) y);
+		SLoc+=ULCorner;
+		uint32 *dest=output_buffer+y*stride;
+		for(int x=0;x<width;x+=2)
+		{
+			myrays.direction.DuplicateVector(SLoc);
+			myrays.direction+=block_offsets;
+			myrays.direction.VectorNormalize();
+			
+			RayTracingResult rslt;
+			Trace4Rays(myrays,all_zeros,TraceLimit, &rslt);
+			if ((rslt.HitIds[0]==-1) && (rslt.HitIds[1]==-1) && 
+				(rslt.HitIds[2]==-1) && (rslt.HitIds[3]==-1))
+				MapLinearIntensities(BackgroundColor,dest,dest+1,dest+stride,dest+stride+1);
+			else
+			{
+				// make sure normal points back towards ray origin
+				fltx4 ndoti=rslt.surface_normal*myrays.direction;
+				fltx4 bad_dirs=AndSIMD(CmpGtSIMD(ndoti,Four_Zeros),
+										   LoadAlignedSIMD((float *) signmask));
+
+				// flip signs of all "wrong" normals
+				rslt.surface_normal.x=XorSIMD(bad_dirs,rslt.surface_normal.x);
+				rslt.surface_normal.y=XorSIMD(bad_dirs,rslt.surface_normal.y);
+				rslt.surface_normal.z=XorSIMD(bad_dirs,rslt.surface_normal.z);
+
+				FourVectors intens;
+				intens.DuplicateVector(Vector(0,0,0));
+				// set up colors
+				FourVectors surf_colors;
+				surf_colors.DuplicateVector(Vector(0,0,0));
+				for(int i=0;i<4;i++)
+				{
+					if (rslt.HitIds[i]>=0)
+					{
+						surf_colors.X(i)=TriangleColors[rslt.HitIds[i]].x;
+						surf_colors.Y(i)=TriangleColors[rslt.HitIds[i]].y;
+						surf_colors.Z(i)=TriangleColors[rslt.HitIds[i]].z;
+					}
+
+				}
+				FourVectors surface_pos=myrays.direction;
+				surface_pos*=rslt.HitDistance;
+				surface_pos+=myrays.origin;
+				
+				switch(lmode)
+				{
+					case DIRECT_LIGHTING:
+					{
+						// light all points
+						for(int l=0;l<LightList.Count();l++)
+						{
+							LightList[l].ComputeLightAtPoints(surface_pos,rslt.surface_normal,
+															  intens);
+						}
+					}
+					break;
+
+					case DIRECT_LIGHTING_WITH_SHADOWS:
+					{
+						// light all points
+						for(int l=0;l<LightList.Count();l++)
+						{
+							FourVectors ldir;
+							ldir.DuplicateVector(LightList[l].m_Position);
+							ldir-=surface_pos;
+							fltx4 MaxT=ldir.length();
+							ldir.VectorNormalizeFast();
+							// now, compute shadow flag
+							FourRays myrays;
+							myrays.origin=surface_pos;
+							FourVectors epsilon=ldir;
+							epsilon*=0.01;
+							myrays.origin+=epsilon;
+							myrays.direction=ldir;
+							RayTracingResult shadowtest;
+							Trace4Rays(myrays,Four_Zeros,MaxT, &shadowtest);
+							fltx4 unshadowed=CmpGtSIMD(shadowtest.HitDistance,MaxT);
+							if (! (IsAllZeros(unshadowed)))
+							{
+								FourVectors tmp;
+								tmp.DuplicateVector(Vector(0,0,0));
+								LightList[l].ComputeLightAtPoints(surface_pos,rslt.surface_normal,
+																  tmp);
+								intens.x=AddSIMD(intens.x,AndSIMD(tmp.x,unshadowed));
+								intens.y=AddSIMD(intens.y,AndSIMD(tmp.y,unshadowed));
+								intens.z=AddSIMD(intens.z,AndSIMD(tmp.z,unshadowed));
+							}
+						}
+					}
+					break;
+				}
+				// now, mask off non-hitting pixels
+				intens.VProduct(surf_colors);
+				fltx4 no_hit_mask=CmpGtSIMD(rslt.HitDistance,TraceLimit);
+				
+				intens.x=OrSIMD(AndSIMD(BackgroundColor.x,no_hit_mask),
+								   AndNotSIMD(no_hit_mask,intens.x));
+				intens.y=OrSIMD(AndSIMD(BackgroundColor.y,no_hit_mask),
+								   AndNotSIMD(no_hit_mask,intens.y));
+				intens.z=OrSIMD(AndSIMD(BackgroundColor.y,no_hit_mask),
+								   AndNotSIMD(no_hit_mask,intens.z));
+
+				MapLinearIntensities(intens,dest,dest+1,dest+stride,dest+stride+1);
+			}
+			dest+=2;
+			SLoc+=dxvectortimes2;
+		}
+	}
+}
+
+
+
+
+#define SQ(x) ((x)*(x))
+
+void RayTracingEnvironment::ComputeVirtualLightSources(void)
+{
+	int start_pos=0;
+	for(int b=0;b<3;b++)
+	{
+		int nl=LightList.Count();
+		int where_to_start=start_pos;
+		start_pos=nl;
+		for(int l=where_to_start;l<nl;l++)
+		{
+			DirectionalSampler_t sample_generator;
+			int n_desired=1*LightList[l].m_Color.Length();
+			if (LightList[l].m_Type==MATERIAL_LIGHT_SPOT)
+				n_desired*=LightList[l].m_Phi/2;
+			for(int try1=0;try1<n_desired;try1++)
+			{
+				LightDesc_t const &li=LightList[l];
+				FourRays myrays;
+				myrays.origin.DuplicateVector(li.m_Position);
+				RayTracingResult rslt;
+				Vector trial_dir=sample_generator.NextValue();
+				if (li.IsDirectionWithinLightCone(trial_dir))
+				{
+					myrays.direction.DuplicateVector(trial_dir);
+					Trace4Rays(myrays,all_zeros,ReplicateX4(1000.0), &rslt);
+					if ((rslt.HitIds[0]!=-1))
+					{
+						// make sure normal points back towards ray origin
+						fltx4 ndoti=rslt.surface_normal*myrays.direction;
+						fltx4 bad_dirs=AndSIMD(CmpGtSIMD(ndoti,Four_Zeros),
+												   LoadAlignedSIMD((float *) signmask));
+						
+						// flip signs of all "wrong" normals
+						rslt.surface_normal.x=XorSIMD(bad_dirs,rslt.surface_normal.x);
+						rslt.surface_normal.y=XorSIMD(bad_dirs,rslt.surface_normal.y);
+						rslt.surface_normal.z=XorSIMD(bad_dirs,rslt.surface_normal.z);
+
+						// a hit! let's make a virtual light source
+
+						// treat the virtual light as a disk with its center at the hit position
+						// and its radius scaled by the amount of the solid angle this probe
+						// represents.
+						float area_of_virtual_light=
+							4.0*M_PI*SQ( SubFloat( rslt.HitDistance, 0 ) )*(1.0/n_desired);
+
+						FourVectors intens;
+						intens.DuplicateVector(Vector(0,0,0));
+
+						FourVectors surface_pos=myrays.direction;
+						surface_pos*=rslt.HitDistance;
+						surface_pos+=myrays.origin;
+						FourVectors delta=rslt.surface_normal;
+						delta*=0.1;
+						surface_pos+=delta;
+						LightList[l].ComputeLightAtPoints(surface_pos,rslt.surface_normal,
+														  intens);
+						FourVectors surf_colors;
+						surf_colors.DuplicateVector(TriangleColors[rslt.HitIds[0]]);
+						intens*=surf_colors;
+						// see if significant
+						LightDesc_t l1;
+						l1.m_Type=MATERIAL_LIGHT_SPOT;
+						l1.m_Position=Vector(surface_pos.X(0),surface_pos.Y(0),surface_pos.Z(0));
+						l1.m_Direction=Vector(rslt.surface_normal.X(0),rslt.surface_normal.Y(0),
+											  rslt.surface_normal.Z(0));
+						l1.m_Color=Vector(intens.X(0),intens.Y(0),intens.Z(0));
+						if (l1.m_Color.Length()>0)
+						{
+							l1.m_Color*=area_of_virtual_light/M_PI;
+							l1.m_Range=0.0;
+							l1.m_Falloff=1.0;
+							l1.m_Attenuation0=1.0;
+							l1.m_Attenuation1=0.0;
+							l1.m_Attenuation2=1.0;			// intens falls off as 1/r^2
+							l1.m_Theta=0;
+							l1.m_Phi=M_PI;
+							l1.RecalculateDerivedValues();
+							LightList.AddToTail(l1);
+						}
+					}
+				}
+			}
+		}
+	}
+}
+
+
+
+static unsigned int GetSignMask(Vector const &v)
+{
+	unsigned int ret=0;
+	if (v.x<0.0)
+		ret++;
+	if (v.y<0)
+		ret+=2;
+	if (v.z<0)
+		ret+=4;
+	return ret;
+}
+
+
+inline void RayTracingEnvironment::FlushStreamEntry(RayStream &s,int msk)
+{
+	assert(msk>=0);
+	assert(msk<8);
+	fltx4 tmax=s.PendingRays[msk].direction.length();
+	fltx4 scl=ReciprocalSaturateSIMD(tmax);
+	s.PendingRays[msk].direction*=scl;					// normalize
+	RayTracingResult tmpresult;
+	Trace4Rays(s.PendingRays[msk],Four_Zeros,tmax,msk,&tmpresult);
+	// now, write out results
+	for(int r=0;r<4;r++)
+	{
+		RayTracingSingleResult *out=s.PendingStreamOutputs[msk][r];
+		out->ray_length=SubFloat( tmax, r );
+		out->surface_normal.x=tmpresult.surface_normal.X(r);
+		out->surface_normal.y=tmpresult.surface_normal.Y(r);
+		out->surface_normal.z=tmpresult.surface_normal.Z(r);
+		out->HitID=tmpresult.HitIds[r];
+		out->HitDistance=SubFloat( tmpresult.HitDistance, r );
+	}
+	s.n_in_stream[msk]=0;
+}
+
+void RayTracingEnvironment::AddToRayStream(RayStream &s,
+										   Vector const &start,Vector const &end,
+										   RayTracingSingleResult *rslt_out)
+{
+	Vector delta=end;
+	delta-=start;
+	int msk=GetSignMask(delta);
+	assert(msk>=0);
+	assert(msk<8);
+	int pos=s.n_in_stream[msk];
+	assert(pos<4);
+	s.PendingRays[msk].origin.X(pos)=start.x;
+	s.PendingRays[msk].origin.Y(pos)=start.y;
+	s.PendingRays[msk].origin.Z(pos)=start.z;
+	s.PendingRays[msk].direction.X(pos)=delta.x;
+	s.PendingRays[msk].direction.Y(pos)=delta.y;
+	s.PendingRays[msk].direction.Z(pos)=delta.z;
+	s.PendingStreamOutputs[msk][pos]=rslt_out;
+	if (pos==3)
+	{
+		FlushStreamEntry(s,msk);
+	}
+	else
+		s.n_in_stream[msk]++;
+}
+
+void RayTracingEnvironment::FinishRayStream(RayStream &s)
+{
+	for(int msk=0;msk<8;msk++)
+	{
+		int cnt=s.n_in_stream[msk];
+		if (cnt)
+		{
+			// fill in unfilled entries with dups of first
+			for(int c=cnt;c<4;c++)
+			{
+				s.PendingRays[msk].origin.X(c) = s.PendingRays[msk].origin.X(0);
+				s.PendingRays[msk].origin.Y(c) = s.PendingRays[msk].origin.Y(0);
+				s.PendingRays[msk].origin.Z(c) = s.PendingRays[msk].origin.Z(0);
+				s.PendingRays[msk].direction.X(c) = s.PendingRays[msk].direction.X(0);
+				s.PendingRays[msk].direction.Y(c) = s.PendingRays[msk].direction.Y(0);
+				s.PendingRays[msk].direction.Z(c) = s.PendingRays[msk].direction.Z(0);
+				s.PendingStreamOutputs[msk][c]=s.PendingStreamOutputs[msk][0];
+			}
+			FlushStreamEntry(s,msk);
+		}
+	}
+}
diff --git a/mp/src/raytrace/trace3.cpp b/mp/src/raytrace/trace3.cpp
index d8000c3d..b582347e 100644
--- a/mp/src/raytrace/trace3.cpp
+++ b/mp/src/raytrace/trace3.cpp
@@ -1,127 +1,127 @@
-//========= Copyright Valve Corporation, All rights reserved. ============//

-

-#include "raytrace.h"

-#include <bspfile.h>

-#include "bsplib.h"

-

-static Vector VertCoord(dface_t const &f, int vnum)

-{

-	int eIndex = dsurfedges[f.firstedge+vnum];

-	int point;

-	if( eIndex < 0 )

-	{

-		point = dedges[-eIndex].v[1];

-	}

-	else

-	{

-		point = dedges[eIndex].v[0];

-	}

-	dvertex_t *v=dvertexes+point;

-	return Vector(v->point[0],v->point[1],v->point[2]);

-

-}

-

-Vector colors[]={

-	Vector(0.5,0.5,1),

-	Vector(0.5,1,0.5),

-	Vector(0.5,1,1),

-	Vector(1,0.5,0.5),

-	Vector(1,0.5,1),

-	Vector(1,1,1)};

-

-void RayTracingEnvironment::AddBSPFace(int id,dface_t const &face)

-{

-	if (face.dispinfo!=-1)									// displacements must be dealt with elsewhere

-		return;

-	texinfo_t *tx =(face.texinfo>=0)?&(texinfo[face.texinfo]):0;

-// 	if (tx && (tx->flags & (SURF_SKY|SURF_NODRAW)))

-// 		return;

-	if (tx)

-	{

-		printf("id %d flags=%x\n",id,tx->flags);

-	}

-	printf("side: ");

-	for(int v=0;v<face.numedges;v++)

-	{

-		printf("(%f %f %f) ",XYZ(VertCoord(face,v)));

-	}

-	printf("\n");

-	int ntris=face.numedges-2;

-	for(int tri=0;tri<ntris;tri++)

-	{

-		

-		AddTriangle(id,VertCoord(face,0),VertCoord(face,(tri+1)%face.numedges),

-					VertCoord(face,(tri+2)%face.numedges),Vector(1,1,1)); //colors[id % NELEMS(colors)]);

-	}

-}

-

-void RayTracingEnvironment::InitializeFromLoadedBSP(void)

-{

-// 	CUtlVector<uint8> PlanesToSkip;

-// 	SidesToSkip.EnsureCapacity(numplanes);

-// 	for(int s=0;s<numplanes;s++)

-// 		SidesToSkip.AddToTail(0);

-// 	for(int b=0;b<numbrushes;b++)

-// 		if ((dbrushes[b].contents & MASK_OPAQUE)==0)

-// 		{

-// 			// transparent brush - mark all its sides as "do not process"

-// 			for(int s=0;s<dbrushes[b].numsides;s++)

-// 			{

-// 				PlanesToSkip[s+dbrushes[b].firstside]=1;

-// 			}

-

-// 		}

-// 	// now, add all origfaces, omitting those whose sides are the ones we marked previously

-// 	for(int c=0;c<numorigfaces;c++)

-// 	{

-// 		dface_t const &f=dorigfaces[c];

-// 		if (SidesToSkip[f.AddBSPFace(c,dorigfaces[c]);

-// 	}

-	

-

-

-// 	// ugly - I want to traverse all the faces. but there is no way to get from a face back to it's

-// 	// original brush, and I need to get back to the face to the contents field of the brush.  So I

-// 	// will create a temporary mapping from a "side" to its brush. I can get from the face to it

-// 	// side, which can get me back to its brush.

-	

-// 	CUtlVector<uint8> OrigFaceVisited;

-// 	OrigFaceVisited.EnsureCapacity(numorigfaces);

-// 	int n_added=0;

-

-// 	for(int i=0;i<numorigfaces;i++)

-// 		OrigFaceVisited.AddToTail(0);

-

-// 	for(int l=0;l<numleafs;l++)

-// 	{

-// 		dleaf_t const &lf=dleafs[l];

-// //		if (lf.contents & MASK_OPAQUE)

-// 		{

-// 			for(int f=0;f<lf.numleaffaces;f++);

-// 			{

-// 				dface_t const &face=dfaces[f+lf.firstleafface];

-// 				if (OrigFaceVisited[face.origFace]==0)

-// 				{

-// 					dface_t const &oface=dorigfaces[face.origFace];

-// 					OrigFaceVisited[face.origFace]=1;

-// 					n_added++;

-// 					AddBSPFace(face.origFace,oface);

-// 				}

-// 			}

-// 		}

-// 	}

-// 	printf("added %d of %d\n",n_added,numorigfaces);

-// 	for(int c=0;c<numorigfaces;c++)

-// 	{

-// 		dface_t const &f=dorigfaces[c];

-// 		AddBSPFace(c,dorigfaces[c]);

-// 	}

-	for(int c=0;c<numfaces;c++)

-	{

-//		dface_t const &f=dfaces[c];

-		AddBSPFace(c,dorigfaces[c]);

-	}

-

-//	AddTriangle(1234,Vector(51,145,-700),Vector(71,165,-700),Vector(51,165,-700),colors[5]);

-}

-

+//========= Copyright Valve Corporation, All rights reserved. ============//
+
+#include "raytrace.h"
+#include <bspfile.h>
+#include "bsplib.h"
+
+static Vector VertCoord(dface_t const &f, int vnum)
+{
+	int eIndex = dsurfedges[f.firstedge+vnum];
+	int point;
+	if( eIndex < 0 )
+	{
+		point = dedges[-eIndex].v[1];
+	}
+	else
+	{
+		point = dedges[eIndex].v[0];
+	}
+	dvertex_t *v=dvertexes+point;
+	return Vector(v->point[0],v->point[1],v->point[2]);
+
+}
+
+Vector colors[]={
+	Vector(0.5,0.5,1),
+	Vector(0.5,1,0.5),
+	Vector(0.5,1,1),
+	Vector(1,0.5,0.5),
+	Vector(1,0.5,1),
+	Vector(1,1,1)};
+
+void RayTracingEnvironment::AddBSPFace(int id,dface_t const &face)
+{
+	if (face.dispinfo!=-1)									// displacements must be dealt with elsewhere
+		return;
+	texinfo_t *tx =(face.texinfo>=0)?&(texinfo[face.texinfo]):0;
+// 	if (tx && (tx->flags & (SURF_SKY|SURF_NODRAW)))
+// 		return;
+	if (tx)
+	{
+		printf("id %d flags=%x\n",id,tx->flags);
+	}
+	printf("side: ");
+	for(int v=0;v<face.numedges;v++)
+	{
+		printf("(%f %f %f) ",XYZ(VertCoord(face,v)));
+	}
+	printf("\n");
+	int ntris=face.numedges-2;
+	for(int tri=0;tri<ntris;tri++)
+	{
+		
+		AddTriangle(id,VertCoord(face,0),VertCoord(face,(tri+1)%face.numedges),
+					VertCoord(face,(tri+2)%face.numedges),Vector(1,1,1)); //colors[id % NELEMS(colors)]);
+	}
+}
+
+void RayTracingEnvironment::InitializeFromLoadedBSP(void)
+{
+// 	CUtlVector<uint8> PlanesToSkip;
+// 	SidesToSkip.EnsureCapacity(numplanes);
+// 	for(int s=0;s<numplanes;s++)
+// 		SidesToSkip.AddToTail(0);
+// 	for(int b=0;b<numbrushes;b++)
+// 		if ((dbrushes[b].contents & MASK_OPAQUE)==0)
+// 		{
+// 			// transparent brush - mark all its sides as "do not process"
+// 			for(int s=0;s<dbrushes[b].numsides;s++)
+// 			{
+// 				PlanesToSkip[s+dbrushes[b].firstside]=1;
+// 			}
+
+// 		}
+// 	// now, add all origfaces, omitting those whose sides are the ones we marked previously
+// 	for(int c=0;c<numorigfaces;c++)
+// 	{
+// 		dface_t const &f=dorigfaces[c];
+// 		if (SidesToSkip[f.AddBSPFace(c,dorigfaces[c]);
+// 	}
+	
+
+
+// 	// ugly - I want to traverse all the faces. but there is no way to get from a face back to it's
+// 	// original brush, and I need to get back to the face to the contents field of the brush.  So I
+// 	// will create a temporary mapping from a "side" to its brush. I can get from the face to it
+// 	// side, which can get me back to its brush.
+	
+// 	CUtlVector<uint8> OrigFaceVisited;
+// 	OrigFaceVisited.EnsureCapacity(numorigfaces);
+// 	int n_added=0;
+
+// 	for(int i=0;i<numorigfaces;i++)
+// 		OrigFaceVisited.AddToTail(0);
+
+// 	for(int l=0;l<numleafs;l++)
+// 	{
+// 		dleaf_t const &lf=dleafs[l];
+// //		if (lf.contents & MASK_OPAQUE)
+// 		{
+// 			for(int f=0;f<lf.numleaffaces;f++);
+// 			{
+// 				dface_t const &face=dfaces[f+lf.firstleafface];
+// 				if (OrigFaceVisited[face.origFace]==0)
+// 				{
+// 					dface_t const &oface=dorigfaces[face.origFace];
+// 					OrigFaceVisited[face.origFace]=1;
+// 					n_added++;
+// 					AddBSPFace(face.origFace,oface);
+// 				}
+// 			}
+// 		}
+// 	}
+// 	printf("added %d of %d\n",n_added,numorigfaces);
+// 	for(int c=0;c<numorigfaces;c++)
+// 	{
+// 		dface_t const &f=dorigfaces[c];
+// 		AddBSPFace(c,dorigfaces[c]);
+// 	}
+	for(int c=0;c<numfaces;c++)
+	{
+//		dface_t const &f=dfaces[c];
+		AddBSPFace(c,dorigfaces[c]);
+	}
+
+//	AddTriangle(1234,Vector(51,145,-700),Vector(71,165,-700),Vector(51,165,-700),colors[5]);
+}
+