1HEADmaster

1 files changed, 390 insertions, 0 deletions

diff --git a/public/raytrace.h b/public/raytrace.h
new file mode 100644
index 0000000..9692b8d
--- /dev/null
+++ b/public/raytrace.h
@@ -0,0 +1,390 @@
+//========= Copyright Valve Corporation, All rights reserved. ============//
+// $Id:$
+
+#ifndef RAYTRACE_H
+#define RAYTRACE_H
+
+#include <tier0/platform.h>
+#include <mathlib/vector.h>
+#include <mathlib/ssemath.h>
+#include <mathlib/lightdesc.h>
+#include <assert.h>
+#include <tier1/utlvector.h>
+#include <mathlib/mathlib.h>
+#include <bspfile.h>
+
+// fast SSE-ONLY ray tracing module. Based upon various "real time ray tracing" research.
+//#define DEBUG_RAYTRACE 1
+
+class FourRays
+{
+public:
+	FourVectors origin;
+	FourVectors direction;
+
+	inline void Check(void) const
+	{
+		// in order to be valid to trace as a group, all four rays must have the same signs in all
+		// of their direction components
+#ifndef NDEBUG
+		for(int c=1;c<4;c++)
+		{
+			Assert(direction.X(0)*direction.X(c)>=0);
+			Assert(direction.Y(0)*direction.Y(c)>=0);
+			Assert(direction.Z(0)*direction.Z(c)>=0);
+		}
+#endif
+	}
+	// returns direction sign mask for 4 rays. returns -1 if the rays can not be traced as a
+	// bundle.
+	int CalculateDirectionSignMask(void) const;
+
+};
+
+/// The format a triangle is stored in for intersections. size of this structure is important.
+/// This structure can be in one of two forms. Before the ray tracing environment is set up, the
+/// ProjectedEdgeEquations hold the coordinates of the 3 vertices, for facilitating bounding box
+/// checks needed while building the tree. afterwards, they are changed into the projected ege
+/// equations for intersection purposes.
+enum triangleflags
+{
+	FCACHETRI_TRANSPARENT = 0x01,
+	FCACHETRI_NEGATIVE_NORMAL = 0x02,
+};
+
+
+struct TriIntersectData_t
+{
+	// this structure is 16longs=64 bytes for cache line packing.
+	float m_flNx, m_flNy, m_flNz;							// plane equation
+	float m_flD;
+
+	int32 m_nTriangleID;									// id of the triangle.
+
+	float m_ProjectedEdgeEquations[6];						// A,B,C for each edge equation.  a
+															// point is inside the triangle if
+															// a*c1+b*c2+c is negative for all 3
+															// edges.
+
+	uint8 m_nCoordSelect0,m_nCoordSelect1;					// the triangle is projected onto a 2d
+	                                                        // plane for edge testing. These are
+	                                                        // the indices (0..2) of the
+	                                                        // coordinates preserved in the
+	                                                        // projection
+
+	uint8 m_nFlags;											// triangle flags
+	uint8 m_unused0;										// no longer used
+};
+
+
+struct TriGeometryData_t
+{
+	int32 m_nTriangleID;									// id of the triangle.
+
+	float m_VertexCoordData[9];								// can't use a vector in a union
+
+	uint8 m_nFlags;											// triangle flags
+	signed char m_nTmpData0;								// used by kd-tree builder
+	signed char m_nTmpData1;								// used by kd-tree builder
+
+
+	// accessors to get around union annoyance
+	FORCEINLINE Vector &Vertex(int idx)
+	{
+		return * ( reinterpret_cast<Vector *> (  m_VertexCoordData+3*idx ) );
+	}
+
+};
+
+
+struct CacheOptimizedTriangle
+{
+
+	union
+	{
+		TriIntersectData_t m_IntersectData;
+		TriGeometryData_t m_GeometryData;
+	} m_Data;
+
+	// accessors to get around union annoyance
+	FORCEINLINE Vector &Vertex(int idx)
+	{
+		return * ( reinterpret_cast<Vector *> (m_Data.m_GeometryData.m_VertexCoordData+3*idx ) );
+	}
+
+	FORCEINLINE const Vector &Vertex(int idx) const
+	{
+		return * ( reinterpret_cast<const Vector *> (m_Data.m_GeometryData.m_VertexCoordData+3*idx ) );
+	}
+
+	void ChangeIntoIntersectionFormat(void);				// change information storage format for
+	                                                        // computing intersections.
+
+	int ClassifyAgainstAxisSplit(int split_plane, float split_value); // PLANECHECK_xxx below
+	
+};
+
+#define PLANECHECK_POSITIVE 1
+#define PLANECHECK_NEGATIVE -1
+#define PLANECHECK_STRADDLING 0
+
+#define KDNODE_STATE_XSPLIT 0								// this node is an x split
+#define KDNODE_STATE_YSPLIT 1								// this node is a ysplit
+#define KDNODE_STATE_ZSPLIT 2								// this node is a zsplit
+#define KDNODE_STATE_LEAF 3									// this node is a leaf
+
+struct CacheOptimizedKDNode
+{
+	// this is the cache intensive data structure. "Tricks" are used to fit it into 8 bytes:
+	//
+	// A) the right child is always stored after the left child, which means we only need one
+	// pointer
+	// B) The type of node (KDNODE_xx) is stored in the lower 2 bits of the pointer.
+	// C) for leaf nodes, we store the number of triangles in the leaf in the same place as the floating
+	//    point splitting parameter is stored in a non-leaf node
+
+	int32 Children;											// child idx, or'ed with flags above
+	float SplittingPlaneValue;								// for non-leaf nodes, the nodes on the
+	                                                        // "high" side of the splitting plane
+	                                                        // are on the right
+
+#ifdef DEBUG_RAYTRACE
+	Vector vecMins;
+	Vector vecMaxs;
+#endif
+
+	inline int NodeType(void) const
+
+	{
+		return Children & 3;
+	}
+
+	inline int32 TriangleIndexStart(void) const
+	{
+		assert(NodeType()==KDNODE_STATE_LEAF);
+		return Children>>2;
+	}
+
+	inline int LeftChild(void) const
+	{
+		assert(NodeType()!=KDNODE_STATE_LEAF);
+		return Children>>2;
+	}
+
+	inline int RightChild(void) const
+	{
+		return LeftChild()+1;
+	}
+
+	inline int NumberOfTrianglesInLeaf(void) const
+	{
+		assert(NodeType()==KDNODE_STATE_LEAF);
+		return *((int32 *) &SplittingPlaneValue);
+	}
+
+	inline void SetNumberOfTrianglesInLeafNode(int n)
+	{
+		*((int32 *) &SplittingPlaneValue)=n;
+	}
+
+protected:
+
+
+};
+
+
+struct RayTracingSingleResult
+{
+	Vector surface_normal;									// surface normal at intersection
+	int32 HitID;											// -1=no hit. otherwise, triangle index
+	float HitDistance;										// distance to intersection
+	float ray_length;										// leng of initial ray
+};
+
+struct RayTracingResult
+{
+	FourVectors surface_normal;								// surface normal at intersection
+	ALIGN16 int32 HitIds[4] ALIGN16_POST;								// -1=no hit. otherwise, triangle index
+	fltx4 HitDistance;										// distance to intersection
+};
+
+
+class RayTraceLight
+{
+public:
+	FourVectors Position;
+	FourVectors Intensity;
+};
+
+
+#define RTE_FLAGS_FAST_TREE_GENERATION 1
+#define RTE_FLAGS_DONT_STORE_TRIANGLE_COLORS 2				// saves memory if not needed
+#define RTE_FLAGS_DONT_STORE_TRIANGLE_MATERIALS 4
+
+enum RayTraceLightingMode_t {
+	DIRECT_LIGHTING,										// just dot product lighting
+	DIRECT_LIGHTING_WITH_SHADOWS,						// with shadows
+	GLOBAL_LIGHTING										// global light w/ shadows
+};
+
+
+class RayStream
+{
+	friend class RayTracingEnvironment;
+
+	RayTracingSingleResult *PendingStreamOutputs[8][4];
+	int n_in_stream[8];
+	FourRays PendingRays[8];
+
+public:
+	RayStream(void)
+	{
+		memset(n_in_stream,0,sizeof(n_in_stream));
+	}
+};
+
+// When transparent triangles are in the list, the caller can provide a callback that will get called at each triangle
+// allowing the callback to stop processing if desired.
+// UNDONE: This is not currently SIMD - it really only supports single rays
+// Also for efficiency FourRays really needs some kind of active mask for the cases where rays get unbundled
+class ITransparentTriangleCallback
+{
+public:
+	virtual bool VisitTriangle_ShouldContinue( const TriIntersectData_t &triangle, const FourRays &rays, fltx4 *hitMask, fltx4 *b0, fltx4 *b1, fltx4 *b2, int32 hitID ) = 0;
+};
+
+class RayTracingEnvironment
+{
+public:
+	uint32 Flags;											// RTE_FLAGS_xxx above
+	Vector m_MinBound;
+	Vector m_MaxBound;
+
+	FourVectors BackgroundColor;							//< color where no intersection
+	CUtlVector<CacheOptimizedKDNode> OptimizedKDTree;		//< the packed kdtree. root is 0
+	CUtlBlockVector<CacheOptimizedTriangle> OptimizedTriangleList; //< the packed triangles
+	CUtlVector<int32> TriangleIndexList;					//< the list of triangle indices.
+	CUtlVector<LightDesc_t> LightList;						//< the list of lights
+	CUtlVector<Vector> TriangleColors;						//< color of tries
+	CUtlVector<int32> TriangleMaterials;					//< material index of tries
+
+public:
+	RayTracingEnvironment() : OptimizedTriangleList( 1024 )
+	{
+		BackgroundColor.DuplicateVector(Vector(1,0,0));		// red
+		Flags=0;
+	}
+
+
+	// call AddTriangle to set up the world
+	void AddTriangle(int32 id, const Vector &v1, const Vector &v2, const Vector &v3,
+					 const Vector &color);
+
+	// Adds a triangle with flags & material
+	void AddTriangle(int32 id, const Vector &v1, const Vector &v2, const Vector &v3,
+								const Vector &color, uint16 flags, int32 materialIndex);
+
+
+	void 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);
+
+	// for ease of testing. 
+	void AddAxisAlignedRectangularSolid(int id,Vector mincoord, Vector Maxcoord, 
+										const Vector &color);
+
+
+	// SetupAccelerationStructure to prepare for tracing
+	void SetupAccelerationStructure(void);
+
+
+	// lowest level intersection routine - fire 4 rays through the scene. all 4 rays must pass the
+	// Check() function, and t extents must be initialized. skipid can be set to exclude a
+	// particular id (such as the origin surface). This function finds the closest intersection.
+	void Trace4Rays(const FourRays &rays, fltx4 TMin, fltx4 TMax,int DirectionSignMask,
+					RayTracingResult *rslt_out,
+					int32 skip_id=-1, ITransparentTriangleCallback *pCallback = NULL);
+
+	// higher level intersection routine that handles computing the mask and handling rays which do not match in direciton sign
+	void Trace4Rays(const FourRays &rays, fltx4 TMin, fltx4 TMax,
+					RayTracingResult *rslt_out,
+					int32 skip_id=-1, ITransparentTriangleCallback *pCallback = NULL);
+
+	// compute virtual light sources to model inter-reflection
+	void ComputeVirtualLightSources(void);
+
+
+	// high level interface - pass viewing parameters, rendering flags, and a destination frame
+	// buffer, and get a ray traced scene in 32-bit rgba format
+	void 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 lightmode=DIRECT_LIGHTING);
+
+					 
+	/// raytracing stream - lets you trace an array of rays by feeding them to this function.
+	/// results will not be returned until FinishStream is called. This function handles sorting
+	/// the rays by direction, tracing them 4 at a time, and de-interleaving the results.
+
+	void AddToRayStream(RayStream &s,
+						Vector const &start,Vector const &end,RayTracingSingleResult *rslt_out);
+
+	inline void FlushStreamEntry(RayStream &s,int msk);
+
+	/// call this when you are done. handles all cleanup. After this is called, all rslt ptrs
+	/// previously passed to AddToRaySteam will have been filled in.
+	void FinishRayStream(RayStream &s);
+
+
+	int MakeLeafNode(int first_tri, int last_tri);
+
+
+	float CalculateCostsOfSplit(
+		int split_plane,int32 const *tri_list,int ntris,
+		Vector MinBound,Vector MaxBound, float &split_value,
+		int &nleft, int &nright, int &nboth);
+		
+	void RefineNode(int node_number,int32 const *tri_list,int ntris,
+						 Vector MinBound,Vector MaxBound, int depth);
+	
+	void CalculateTriangleListBounds(int32 const *tris,int ntris,
+									 Vector &minout, Vector &maxout);
+
+	void AddInfinitePointLight(Vector position,				// light center
+							   Vector intensity);			// rgb amount
+
+	// use the global variables set by LoadBSPFile to populated the RayTracingEnvironment with
+	// faces.
+	void InitializeFromLoadedBSP(void);
+
+	void AddBSPFace(int id,dface_t const &face);
+
+	// MakeRoomForTriangles - a hint telling it how many triangles we are going to add so that
+	// the utl vectors used can be pre-allocated
+	void MakeRoomForTriangles( int ntriangles );
+
+	const CacheOptimizedTriangle &GetTriangle( int32 triID )
+	{
+		return OptimizedTriangleList[triID];
+	}
+
+	int32 GetTriangleMaterial( int32 triID )
+	{
+		return TriangleMaterials[triID];
+	}
+	const Vector &GetTriangleColor( int triID )
+	{
+		return TriangleColors[triID];
+	}
+
+};
+
+
+
+#endif