351 lines
13 KiB
C++
351 lines
13 KiB
C++
//========= Copyright Valve Corporation, All rights reserved. ============//
|
|
// $Id:$
|
|
|
|
#ifndef RAYTRACE_H
|
|
#define RAYTRACE_H
|
|
|
|
#include <assert.h>
|
|
#include <bspfile.h>
|
|
#include <mathlib/lightdesc.h>
|
|
#include <mathlib/mathlib.h>
|
|
#include <mathlib/ssemath.h>
|
|
#include <mathlib/vector.h>
|
|
#include <tier0/platform.h>
|
|
#include <tier1/utlvector.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
|