First version of the SOurce SDK 2013

1 files changed, 1783 insertions, 0 deletions

diff --git a/mp/src/utils/vrad/vraddisps.cpp b/mp/src/utils/vrad/vraddisps.cpp
new file mode 100644
index 00000000..1e8d2606
--- /dev/null
+++ b/mp/src/utils/vrad/vraddisps.cpp
@@ -0,0 +1,1783 @@
+//========= Copyright Valve Corporation, All rights reserved. ============//

+//

+// Purpose: 

+//

+// $NoKeywords: $

+//=============================================================================//

+

+#include "vrad.h"

+#include "utlvector.h"

+#include "cmodel.h"

+#include "BSPTreeData.h"

+#include "VRAD_DispColl.h"

+#include "CollisionUtils.h"

+#include "lightmap.h"

+#include "Radial.h"

+#include "CollisionUtils.h"

+#include "mathlib/bumpvects.h"

+#include "utlrbtree.h"

+#include "tier0/fasttimer.h"

+#include "disp_vrad.h"

+

+class CBSPDispRayDistanceEnumerator;

+

+//=============================================================================

+//

+// Displacement/Face List

+//

+class CBSPDispFaceListEnumerator : public ISpatialLeafEnumerator, public IBSPTreeDataEnumerator

+{

+public:

+

+	//=========================================================================

+	//

+	// Construction/Deconstruction

+	//

+	CBSPDispFaceListEnumerator() {};

+	virtual ~CBSPDispFaceListEnumerator()

+	{

+		m_DispList.Purge();

+		m_FaceList.Purge();

+	}

+

+	// ISpatialLeafEnumerator

+	bool EnumerateLeaf( int ndxLeaf, int context ); 

+

+	// IBSPTreeDataEnumerator

+	bool FASTCALL EnumerateElement( int userId, int context );

+

+public:

+

+	CUtlVector<CVRADDispColl*>	m_DispList;

+	CUtlVector<int>				m_FaceList;

+};

+

+

+//=============================================================================

+//

+// RayEnumerator

+//

+class CBSPDispRayEnumerator : public ISpatialLeafEnumerator, public IBSPTreeDataEnumerator

+{

+public:

+	// ISpatialLeafEnumerator

+	bool EnumerateLeaf( int ndxLeaf, int context );

+

+	// IBSPTreeDataEnumerator

+	bool FASTCALL EnumerateElement( int userId, int context );

+};

+

+//=============================================================================

+//

+// VRad Displacement Manager

+//

+class CVRadDispMgr : public IVRadDispMgr

+{

+public:

+

+	//=========================================================================

+	//

+	// Construction/Deconstruction

+	//

+	CVRadDispMgr();

+	virtual ~CVRadDispMgr();

+

+	// creation/destruction

+	void Init( void );

+	void Shutdown( void );

+

+	// "CalcPoints"

+	bool BuildDispSamples( lightinfo_t *pLightInfo, facelight_t *pFaceLight, int ndxFace );

+	bool BuildDispLuxels( lightinfo_t *pLightInfo, facelight_t *pFaceLight, int ndxFace );

+	bool BuildDispSamplesAndLuxels_DoFast( lightinfo_t *pLightInfo, facelight_t *pFaceLight, int ndxFace );

+

+	// patching functions

+	void MakePatches( void );

+	void SubdividePatch( int iPatch );

+

+	// pre "FinalLightFace"

+	void InsertSamplesDataIntoHashTable( void );

+	void InsertPatchSampleDataIntoHashTable( void );

+

+	// "FinalLightFace"

+	radial_t *BuildLuxelRadial( int ndxFace, int ndxStyle, bool bBump );

+	bool SampleRadial( int ndxFace, radial_t *pRadial, Vector const &vPos, int ndxLxl, LightingValue_t *pLightSample, int sampleCount, bool bPatch );

+	radial_t *BuildPatchRadial( int ndxFace, bool bBump );

+

+	// utility

+	void GetDispSurfNormal( int ndxFace, Vector &pt, Vector &ptNormal, bool bInside );

+	void GetDispSurf( int ndxFace, CVRADDispColl **ppDispTree );

+

+	// bsp tree functions

+	bool ClipRayToDisp( DispTested_t &dispTested, Ray_t const &ray );

+	bool ClipRayToDispInLeaf( DispTested_t &dispTested, Ray_t const &ray, int ndxLeaf );

+	void ClipRayToDispInLeaf( DispTested_t &dispTested, Ray_t const &ray, int ndxLeaf,  

+					float& dist, dface_t*& pFace, Vector2D& luxelCoord );

+	void ClipRayToDispInLeaf( DispTested_t &dispTested, Ray_t const &ray, 

+		int ndxLeaf, float& dist, Vector *pNormal );

+

+	void StartRayTest( DispTested_t &dispTested );

+	void AddPolysForRayTrace( void );

+

+	// general timing -- should be moved!!

+	void StartTimer( const char *name );

+	void EndTimer( void );

+

+	//=========================================================================

+	//

+	// Enumeration Methods

+	//

+	bool DispRay_EnumerateLeaf( int ndxLeaf, int context );

+	bool DispRay_EnumerateElement( int userId, int context );

+	bool DispRayDistance_EnumerateElement( int userId, CBSPDispRayDistanceEnumerator* pEnum );

+

+	bool DispFaceList_EnumerateLeaf( int ndxLeaf, int context );

+	bool DispFaceList_EnumerateElement( int userId, int context );

+

+private:

+

+	//=========================================================================

+	//

+	// BSP Tree Helpers

+	//

+	void InsertDispIntoTree( int ndxDisp );

+	void RemoveDispFromTree( int ndxDisp );

+

+	//=========================================================================

+	//

+	// Displacement Data Loader (from .bsp)

+	//

+	void UnserializeDisps( void );

+	void DispBuilderInit( CCoreDispInfo *pBuilderDisp, dface_t *pFace, int ndxFace );

+

+	//=========================================================================

+	//

+	//  Sampling Helpers

+	//

+	void RadialLuxelBuild( CVRADDispColl *pDispTree, radial_t *pRadial, int ndxStyle, bool bBump );

+	void RadialLuxelAddSamples( int ndxFace, Vector const &luxelPt, Vector const &luxelNormal, float radius,

+                                radial_t *pRadial, int ndxRadial, bool bBump, int lightStyle );

+

+	void RadialPatchBuild( CVRADDispColl *pDispTree, radial_t *pRadial, bool bBump );

+	void RadialLuxelAddPatch( int ndxFace, Vector const &luxelPt, 

+											Vector const &luxelNormal,  float radius, 

+											radial_t *pRadial, int ndxRadial, bool bBump,

+											CUtlVector<CPatch*> &interestingPatches );

+

+	bool IsNeighbor( int iDispFace, int iNeighborFace );

+

+	void GetInterestingPatchesForLuxels( 

+		int ndxFace,

+		CUtlVector<CPatch*> &interestingPatches,

+		float patchSampleRadius );

+

+private:

+

+	struct DispCollTree_t

+	{

+		CVRADDispColl			*m_pDispTree;

+		BSPTreeDataHandle_t		m_Handle;

+	};

+

+	struct EnumContext_t

+	{

+		DispTested_t	*m_pDispTested;

+		Ray_t const		*m_pRay;

+	};

+

+	CUtlVector<DispCollTree_t>	m_DispTrees;

+

+	IBSPTreeData				*m_pBSPTreeData;

+

+	CBSPDispRayEnumerator		m_EnumDispRay;

+	CBSPDispFaceListEnumerator	m_EnumDispFaceList;

+

+	int							sampleCount;

+	Vector						*m_pSamplePos;

+

+	CFastTimer					m_Timer;

+};

+

+//-----------------------------------------------------------------------------

+// Purpose: expose IVRadDispMgr to vrad

+//-----------------------------------------------------------------------------

+

+static CVRadDispMgr	s_DispMgr;

+

+IVRadDispMgr *StaticDispMgr( void )

+{

+	return &s_DispMgr;

+}

+

+

+//=============================================================================

+//

+// Displacement/Face List

+//

+// ISpatialLeafEnumerator

+bool CBSPDispFaceListEnumerator::EnumerateLeaf( int ndxLeaf, int context ) 

+{ 

+	return s_DispMgr.DispFaceList_EnumerateLeaf( ndxLeaf, context );

+}

+

+// IBSPTreeDataEnumerator

+bool FASTCALL CBSPDispFaceListEnumerator::EnumerateElement( int userId, int context )

+{

+	return s_DispMgr.DispFaceList_EnumerateElement( userId, context );

+}

+

+

+//=============================================================================

+//

+// RayEnumerator

+//

+bool CBSPDispRayEnumerator::EnumerateLeaf( int ndxLeaf, int context )

+{

+	return s_DispMgr.DispRay_EnumerateLeaf( ndxLeaf, context );

+}

+

+bool FASTCALL CBSPDispRayEnumerator::EnumerateElement( int userId, int context )

+{

+	return s_DispMgr.DispRay_EnumerateElement( userId, context );

+}

+

+

+//-----------------------------------------------------------------------------

+// Here's an enumerator that we use for testing against disps in a leaf...

+//-----------------------------------------------------------------------------

+

+class CBSPDispRayDistanceEnumerator : public IBSPTreeDataEnumerator

+{

+public:

+	CBSPDispRayDistanceEnumerator() : m_Distance(1.0f), m_pSurface(0) {}

+

+	// IBSPTreeDataEnumerator

+	bool FASTCALL EnumerateElement( int userId, int context )

+	{

+		return s_DispMgr.DispRayDistance_EnumerateElement( userId, this );

+	}

+

+	float m_Distance;

+	dface_t* m_pSurface;

+	DispTested_t	*m_pDispTested;

+	Ray_t const		*m_pRay;

+	Vector2D		m_LuxelCoord;

+	Vector			m_Normal;

+};

+

+

+//-----------------------------------------------------------------------------

+//-----------------------------------------------------------------------------

+CVRadDispMgr::CVRadDispMgr()

+{

+	m_pBSPTreeData = CreateBSPTreeData();

+}

+

+

+//-----------------------------------------------------------------------------

+//-----------------------------------------------------------------------------

+CVRadDispMgr::~CVRadDispMgr()

+{

+	DestroyBSPTreeData( m_pBSPTreeData );

+}

+

+

+//-----------------------------------------------------------------------------

+// Insert a displacement into the tree for collision

+//-----------------------------------------------------------------------------

+void CVRadDispMgr::InsertDispIntoTree( int ndxDisp )

+{

+	DispCollTree_t &dispTree = m_DispTrees[ndxDisp];

+	CDispCollTree *pDispTree = dispTree.m_pDispTree;

+

+	// get the bounding box of the tree

+	Vector boxMin, boxMax;

+	pDispTree->GetBounds( boxMin, boxMax );

+

+	// add the displacement to the tree so we will collide against it

+	dispTree.m_Handle = m_pBSPTreeData->Insert( ndxDisp, boxMin, boxMax );

+}

+

+	

+//-----------------------------------------------------------------------------

+// Remove a displacement from the tree for collision

+//-----------------------------------------------------------------------------

+void CVRadDispMgr::RemoveDispFromTree( int ndxDisp )

+{

+	// release the tree handle

+	if( m_DispTrees[ndxDisp].m_Handle != TREEDATA_INVALID_HANDLE )

+	{

+		m_pBSPTreeData->Remove( m_DispTrees[ndxDisp].m_Handle );

+		m_DispTrees[ndxDisp].m_Handle = TREEDATA_INVALID_HANDLE;

+	}

+}

+

+

+//-----------------------------------------------------------------------------

+//-----------------------------------------------------------------------------

+void CVRadDispMgr::Init( void )

+{

+	// initialize the bsp tree

+	m_pBSPTreeData->Init( ToolBSPTree() );

+

+	// read in displacements that have been compiled into the bsp file

+	UnserializeDisps();

+}

+

+

+//-----------------------------------------------------------------------------

+//-----------------------------------------------------------------------------

+void CVRadDispMgr::Shutdown( void )

+{

+	// remove all displacements from the tree

+	for( int ndxDisp = m_DispTrees.Size(); ndxDisp >= 0; ndxDisp-- )

+	{

+		RemoveDispFromTree( ndxDisp );

+	}

+

+	// shutdown the bsp tree

+	m_pBSPTreeData->Shutdown();

+

+	// purge the displacement collision tree list

+	m_DispTrees.Purge();

+}

+

+

+//-----------------------------------------------------------------------------

+//-----------------------------------------------------------------------------

+void CVRadDispMgr::DispBuilderInit( CCoreDispInfo *pBuilderDisp, dface_t *pFace, int ndxFace )

+{

+	// get the .bsp displacement

+	ddispinfo_t *pDisp = &g_dispinfo[pFace->dispinfo];

+	if( !pDisp )

+		return;

+

+	//

+	// initlialize the displacement base surface

+	//

+	CCoreDispSurface *pSurf = pBuilderDisp->GetSurface();

+	pSurf->SetPointCount( 4 );

+	pSurf->SetHandle( ndxFace );

+	pSurf->SetContents( pDisp->contents ); 

+

+	Vector pt[4];

+	int ndxPt;

+	for( ndxPt = 0; ndxPt < 4; ndxPt++ )

+	{

+		int eIndex = dsurfedges[pFace->firstedge+ndxPt];

+		if( eIndex < 0 )

+		{

+			pSurf->SetPoint( ndxPt, dvertexes[dedges[-eIndex].v[1]].point );

+		}

+		else

+		{

+			pSurf->SetPoint( ndxPt, dvertexes[dedges[eIndex].v[0]].point );

+		}

+

+		VectorCopy( pSurf->GetPoint(ndxPt), pt[ndxPt] );

+	}

+

+	//

+	// calculate the displacement surface normal

+	//

+	Vector vFaceNormal;

+	pSurf->GetNormal( vFaceNormal );

+	for( ndxPt = 0; ndxPt < 4; ndxPt++ )

+	{

+		pSurf->SetPointNormal( ndxPt, vFaceNormal );

+	}

+

+	// set the surface initial point info

+	pSurf->SetPointStart( pDisp->startPosition );

+	pSurf->FindSurfPointStartIndex();

+	pSurf->AdjustSurfPointData();

+

+	Vector vecTmp( texinfo[pFace->texinfo].lightmapVecsLuxelsPerWorldUnits[0][0],

+				   texinfo[pFace->texinfo].lightmapVecsLuxelsPerWorldUnits[0][1],

+				   texinfo[pFace->texinfo].lightmapVecsLuxelsPerWorldUnits[0][2] );

+	int nLuxelsPerWorldUnit = static_cast<int>( 1.0f / VectorLength( vecTmp ) );

+	Vector vecU( texinfo[pFace->texinfo].lightmapVecsLuxelsPerWorldUnits[0][0],

+		texinfo[pFace->texinfo].lightmapVecsLuxelsPerWorldUnits[0][1],

+		texinfo[pFace->texinfo].lightmapVecsLuxelsPerWorldUnits[0][2] );

+	Vector vecV( texinfo[pFace->texinfo].lightmapVecsLuxelsPerWorldUnits[1][0],

+		texinfo[pFace->texinfo].lightmapVecsLuxelsPerWorldUnits[1][1],

+		texinfo[pFace->texinfo].lightmapVecsLuxelsPerWorldUnits[1][2] );

+	pSurf->CalcLuxelCoords( nLuxelsPerWorldUnit, false, vecU, vecV );

+

+	pBuilderDisp->SetNeighborData( pDisp->m_EdgeNeighbors, pDisp->m_CornerNeighbors );

+	

+	CDispVert *pVerts = &g_DispVerts[ pDisp->m_iDispVertStart ];

+	CDispTri *pTris = &g_DispTris[pDisp->m_iDispTriStart];

+

+	//

+	// initialize the displacement data

+	//

+	pBuilderDisp->InitDispInfo( 

+		pDisp->power, 

+		pDisp->minTess, 

+		pDisp->smoothingAngle,

+		pVerts,

+		pTris );

+}

+

+

+//-----------------------------------------------------------------------------

+//-----------------------------------------------------------------------------

+void CVRadDispMgr::UnserializeDisps( void ) 

+{

+	// temporarily create the "builder" displacements

+	CUtlVector<CCoreDispInfo*> builderDisps;

+	for ( int iDisp = 0; iDisp < g_dispinfo.Count(); ++iDisp )

+	{

+		CCoreDispInfo *pDisp = new CCoreDispInfo;

+		if ( !pDisp )

+		{

+			builderDisps.Purge();

+			return;

+		}

+

+		int nIndex = builderDisps.AddToTail();

+		pDisp->SetListIndex( nIndex );

+		builderDisps[nIndex] = pDisp;

+	}

+

+	// Set them up as CDispUtilsHelpers.

+	for ( int iDisp = 0; iDisp < g_dispinfo.Count(); ++iDisp )

+	{

+		builderDisps[iDisp]->SetDispUtilsHelperInfo( builderDisps.Base(), g_dispinfo.Count() );

+	}

+

+	//

+	// find all faces with displacement data and initialize

+	//

+	for( int ndxFace = 0; ndxFace < numfaces; ndxFace++ )

+	{

+		dface_t *pFace = &g_pFaces[ndxFace];

+		if( ValidDispFace( pFace ) )

+		{

+			DispBuilderInit( builderDisps[pFace->dispinfo], pFace, ndxFace );

+		}

+	}

+

+	// generate the displacement surfaces

+	for( int iDisp = 0; iDisp < g_dispinfo.Count(); ++iDisp )

+	{

+		builderDisps[iDisp]->Create();

+	}

+

+	// smooth edge normals

+	SmoothNeighboringDispSurfNormals( builderDisps.Base(), g_dispinfo.Count() );

+

+	//

+	// create the displacement collision tree and add it to the bsp tree

+	//

+	CVRADDispColl *pDispTrees = new CVRADDispColl[g_dispinfo.Count()];

+	if( !pDispTrees )

+		return;

+

+	m_DispTrees.AddMultipleToTail( g_dispinfo.Count() );

+

+	for( int iDisp = 0; iDisp < g_dispinfo.Count(); iDisp++ )

+	{

+		pDispTrees[iDisp].Create( builderDisps[iDisp] );

+

+		m_DispTrees[iDisp].m_pDispTree = &pDispTrees[iDisp];

+		m_DispTrees[iDisp].m_Handle = TREEDATA_INVALID_HANDLE;

+

+		InsertDispIntoTree( iDisp );

+	}

+

+	// free "builder" disps

+	builderDisps.Purge();

+}

+

+//-----------------------------------------------------------------------------

+// Purpose: create a set of patches for each displacement surface to transfer

+//          bounced light around with

+//-----------------------------------------------------------------------------

+void CVRadDispMgr::MakePatches( void )

+{

+	// Collect stats - keep track of the total displacement surface area.

+	float flTotalArea = 0.0f;

+

+	// Create patches for all of the displacements.

+	int nTreeCount = m_DispTrees.Size();

+	for( int iTree = 0; iTree < nTreeCount; ++iTree )

+	{

+		// Get the current displacement collision tree.

+		CVRADDispColl *pDispTree = m_DispTrees[iTree].m_pDispTree;

+		if( !pDispTree )

+			continue;

+

+		flTotalArea += pDispTree->CreateParentPatches();

+	}

+

+	// Print stats.

+	qprintf( "%i Displacements\n", nTreeCount );

+	qprintf( "%i Square Feet [%.2f Square Inches]\n", ( int )( flTotalArea / 144.0f ), flTotalArea );

+}

+//-----------------------------------------------------------------------------

+//-----------------------------------------------------------------------------

+void CVRadDispMgr::SubdividePatch( int iPatch )

+{

+	// Get the current patch to subdivide.

+	CPatch *pPatch = &g_Patches[iPatch];

+	if ( !pPatch )

+		return;

+

+	// Create children patches.

+	DispCollTree_t &dispTree = m_DispTrees[g_pFaces[pPatch->faceNumber].dispinfo];

+    CVRADDispColl *pTree = dispTree.m_pDispTree;	

+	if( pTree )

+	{

+		pTree->CreateChildPatches( iPatch, 0 );

+	}

+}

+

+//-----------------------------------------------------------------------------

+//-----------------------------------------------------------------------------

+void CVRadDispMgr::StartRayTest( DispTested_t &dispTested )

+{

+	if( m_DispTrees.Size() > 0 )

+	{

+		if( dispTested.m_pTested == 0 )

+		{

+			dispTested.m_pTested = new int[m_DispTrees.Size()];

+			memset( dispTested.m_pTested, 0, m_DispTrees.Size() * sizeof( int ) );

+			dispTested.m_Enum = 0;

+		}

+		++dispTested.m_Enum;

+	}

+}

+

+

+//-----------------------------------------------------------------------------

+//-----------------------------------------------------------------------------

+bool CVRadDispMgr::ClipRayToDisp( DispTested_t &dispTested, Ray_t const &ray )

+{

+	StartRayTest( dispTested );

+

+	EnumContext_t ctx;

+	ctx.m_pRay = &ray;

+	ctx.m_pDispTested = &dispTested;

+

+	// If it got through without a hit, it returns true

+	return !m_pBSPTreeData->EnumerateLeavesAlongRay( ray, &m_EnumDispRay, ( int )&ctx );

+}

+

+

+//-----------------------------------------------------------------------------

+//-----------------------------------------------------------------------------

+bool CVRadDispMgr::ClipRayToDispInLeaf( DispTested_t &dispTested, Ray_t const &ray, 

+										int ndxLeaf )

+{

+	EnumContext_t ctx;

+	ctx.m_pRay = &ray;

+	ctx.m_pDispTested = &dispTested;

+

+	return !m_pBSPTreeData->EnumerateElementsInLeaf( ndxLeaf, &m_EnumDispRay, ( int )&ctx );

+}

+

+//-----------------------------------------------------------------------------

+//-----------------------------------------------------------------------------

+void CVRadDispMgr::ClipRayToDispInLeaf( DispTested_t &dispTested, Ray_t const &ray, 

+			int ndxLeaf, float& dist, dface_t*& pFace, Vector2D& luxelCoord )

+{

+	CBSPDispRayDistanceEnumerator rayTestEnum;

+	rayTestEnum.m_pRay = &ray;

+	rayTestEnum.m_pDispTested = &dispTested;

+

+	m_pBSPTreeData->EnumerateElementsInLeaf( ndxLeaf, &rayTestEnum, 0 );

+

+	dist = rayTestEnum.m_Distance;

+	pFace = rayTestEnum.m_pSurface;

+	if (pFace)

+	{

+		Vector2DCopy( rayTestEnum.m_LuxelCoord, luxelCoord );

+	}

+}

+

+void CVRadDispMgr::ClipRayToDispInLeaf( DispTested_t &dispTested, Ray_t const &ray, 

+						 int ndxLeaf, float& dist, Vector *pNormal )

+{

+	CBSPDispRayDistanceEnumerator rayTestEnum;

+	rayTestEnum.m_pRay = &ray;

+	rayTestEnum.m_pDispTested = &dispTested;

+

+	m_pBSPTreeData->EnumerateElementsInLeaf( ndxLeaf, &rayTestEnum, 0 );

+	dist = rayTestEnum.m_Distance;

+	if ( rayTestEnum.m_pSurface )

+	{

+		*pNormal = rayTestEnum.m_Normal;

+	}

+}

+

+void CVRadDispMgr::AddPolysForRayTrace( void )

+{

+	int nTreeCount = m_DispTrees.Size();

+	for( int iTree = 0; iTree < nTreeCount; ++iTree )

+	{

+		// Get the current displacement collision tree.

+		CVRADDispColl *pDispTree = m_DispTrees[iTree].m_pDispTree;

+

+		// Add the triangles of the tree to the RT environment

+		pDispTree->AddPolysForRayTrace();

+	}

+}

+

+

+//-----------------------------------------------------------------------------

+//-----------------------------------------------------------------------------

+void CVRadDispMgr::GetDispSurfNormal( int ndxFace, Vector &pt, Vector &ptNormal,

+									  bool bInside )

+{

+	// get the displacement surface data

+	DispCollTree_t &dispTree = m_DispTrees[g_pFaces[ndxFace].dispinfo];

+	CVRADDispColl *pDispTree = dispTree.m_pDispTree;

+	

+	// find the parameterized displacement indices

+	Vector2D uv;

+	pDispTree->BaseFacePlaneToDispUV( pt, uv );

+

+	if( bInside )

+	{

+		if( uv[0] < 0.0f || uv[0] > 1.0f ) { Msg( "Disp UV (%f) outside bounds!\n", uv[0] ); }

+		if( uv[1] < 0.0f || uv[1] > 1.0f ) { Msg( "Disp UV (%f) outside bounds!\n", uv[1] ); }

+	}

+

+	if( uv[0] < 0.0f ) { uv[0] = 0.0f; }

+	if( uv[0] > 1.0f ) { uv[0] = 1.0f; }

+	if( uv[1] < 0.0f ) { uv[1] = 0.0f; }

+	if( uv[1] > 1.0f ) { uv[1] = 1.0f; }

+

+	// get the normal at "pt"

+	pDispTree->DispUVToSurfNormal( uv, ptNormal );

+

+	// get the new "pt"

+	pDispTree->DispUVToSurfPoint( uv, pt, 1.0f );

+}

+

+

+//-----------------------------------------------------------------------------

+//-----------------------------------------------------------------------------

+void CVRadDispMgr::GetDispSurf( int ndxFace, CVRADDispColl **ppDispTree )

+{

+	DispCollTree_t &dispTree = m_DispTrees[g_pFaces[ndxFace].dispinfo];

+    *ppDispTree = dispTree.m_pDispTree;

+}

+

+

+//-----------------------------------------------------------------------------

+//-----------------------------------------------------------------------------

+bool CVRadDispMgr::DispRay_EnumerateLeaf( int ndxLeaf, int context )

+{

+	return m_pBSPTreeData->EnumerateElementsInLeaf( ndxLeaf, &m_EnumDispRay, context );

+}

+

+

+//-----------------------------------------------------------------------------

+//-----------------------------------------------------------------------------

+bool CVRadDispMgr::DispRay_EnumerateElement( int userId, int context )

+{

+	DispCollTree_t &dispTree = m_DispTrees[userId];

+	EnumContext_t *pCtx = ( EnumContext_t* )context;

+

+	// don't test twice (check tested value)

+	if( pCtx->m_pDispTested->m_pTested[userId] == pCtx->m_pDispTested->m_Enum )

+		return true;

+

+	// set the tested value

+	pCtx->m_pDispTested->m_pTested[userId] = pCtx->m_pDispTested->m_Enum;

+

+	// false mean stop iterating -- return false if we hit! (NOTE: opposite return

+	// result of the collision tree's ray test, thus the !)

+	CBaseTrace trace;

+	trace.fraction = 1.0f;

+	return ( !dispTree.m_pDispTree->AABBTree_Ray( *pCtx->m_pRay, pCtx->m_pRay->InvDelta(), &trace, true ) );

+}

+

+//-----------------------------------------------------------------------------

+//-----------------------------------------------------------------------------

+

+bool CVRadDispMgr::DispRayDistance_EnumerateElement( int userId, CBSPDispRayDistanceEnumerator* pCtx )

+{

+	DispCollTree_t &dispTree = m_DispTrees[userId];

+

+	// don't test twice (check tested value)

+	if( pCtx->m_pDispTested->m_pTested[userId] == pCtx->m_pDispTested->m_Enum )

+		return true;

+

+	// set the tested value

+	pCtx->m_pDispTested->m_pTested[userId] = pCtx->m_pDispTested->m_Enum;

+

+	// Test the ray, if it's closer than previous tests, use it!

+	RayDispOutput_t output;

+	output.ndxVerts[0] = -1;

+	output.ndxVerts[1] = -1;

+	output.ndxVerts[2] = -1;

+	output.ndxVerts[3] = -1;

+	output.u = -1.0f;

+	output.v = -1.0f;

+	output.dist = FLT_MAX;

+

+	if (dispTree.m_pDispTree->AABBTree_Ray( *pCtx->m_pRay, output ))

+	{

+		if (output.dist < pCtx->m_Distance)

+		{

+			pCtx->m_Distance = output.dist;

+			pCtx->m_pSurface = &g_pFaces[dispTree.m_pDispTree->GetParentIndex()];

+

+			// Get the luxel coordinate

+			ComputePointFromBarycentric( 

+				dispTree.m_pDispTree->GetLuxelCoord(output.ndxVerts[0]),

+				dispTree.m_pDispTree->GetLuxelCoord(output.ndxVerts[1]),

+				dispTree.m_pDispTree->GetLuxelCoord(output.ndxVerts[2]),

+				output.u, output.v, pCtx->m_LuxelCoord );

+

+			Vector v0,v1,v2;

+			dispTree.m_pDispTree->GetVert( output.ndxVerts[0], v0 );

+			dispTree.m_pDispTree->GetVert( output.ndxVerts[1], v1 );

+			dispTree.m_pDispTree->GetVert( output.ndxVerts[2], v2 );

+			Vector e0 = v1-v0;

+			Vector e1 = v2-v0;

+			pCtx->m_Normal = CrossProduct( e0, e1 );

+			VectorNormalize(pCtx->m_Normal);

+		}

+	}

+

+	return true;

+}

+

+//-----------------------------------------------------------------------------

+// Test a ray against a particular dispinfo

+//-----------------------------------------------------------------------------

+

+/*

+float CVRadDispMgr::ClipRayToDisp( Ray_t const &ray, int dispinfo )

+{

+	assert( m_DispTrees.IsValidIndex(dispinfo) );

+

+	RayDispOutput_t output;

+	if (!m_DispTrees[dispinfo].m_pDispTree->AABBTree_Ray( ray, output ))

+		return 1.0f;

+	return output.dist;

+}

+*/

+

+//-----------------------------------------------------------------------------

+//-----------------------------------------------------------------------------

+bool CVRadDispMgr::DispFaceList_EnumerateLeaf( int ndxLeaf, int context )

+{

+	//

+	// add the faces found in this leaf to the face list

+	//

+	dleaf_t *pLeaf = &dleafs[ndxLeaf];

+	for( int ndxFace = 0; ndxFace < pLeaf->numleaffaces; ndxFace++ )

+	{

+		// get the current face index

+		int ndxLeafFace = pLeaf->firstleafface + ndxFace;

+

+		// check to see if the face already lives in the list

+		int ndx;

+		int size = m_EnumDispFaceList.m_FaceList.Size();

+		for( ndx = 0; ndx < size; ndx++ )

+		{

+			if( m_EnumDispFaceList.m_FaceList[ndx] == ndxLeafFace )

+				break;

+		}

+

+		if( ndx == size )

+		{

+			int ndxList = m_EnumDispFaceList.m_FaceList.AddToTail();

+			m_EnumDispFaceList.m_FaceList[ndxList] = ndxLeafFace;

+		}

+	}

+

+	return m_pBSPTreeData->EnumerateElementsInLeaf( ndxLeaf, &m_EnumDispFaceList, context );

+}

+

+

+//-----------------------------------------------------------------------------

+//-----------------------------------------------------------------------------

+bool CVRadDispMgr::DispFaceList_EnumerateElement( int userId, int context )

+{

+	DispCollTree_t &dispTree = m_DispTrees[userId];

+	CVRADDispColl  *pDispTree = dispTree.m_pDispTree;

+	if( !pDispTree )

+		return false;

+

+	// check to see if the displacement already lives in the list

+	int ndx;

+	int size = m_EnumDispFaceList.m_DispList.Size();

+	for( ndx = 0; ndx < size; ndx++ )

+	{

+		if( m_EnumDispFaceList.m_DispList[ndx] == pDispTree )

+			break;

+	}

+

+	if( ndx == size )

+	{

+		int ndxList = m_EnumDispFaceList.m_DispList.AddToTail();

+		m_EnumDispFaceList.m_DispList[ndxList] = pDispTree;

+	}

+

+	return true;

+}

+

+

+

+//-----------------------------------------------------------------------------

+//-----------------------------------------------------------------------------

+inline void GetSampleLight( facelight_t *pFaceLight, int ndxStyle, bool bBumped, 

+			                int ndxSample, LightingValue_t *pSampleLight )

+{

+//	SampleLight[0].Init( 20.0f, 10.0f, 10.0f );

+//	return;

+

+	// get sample from bumped lighting data

+	if( bBumped )

+	{

+		for( int ndxBump = 0; ndxBump < ( NUM_BUMP_VECTS+1 ); ndxBump++ )

+		{

+			pSampleLight[ndxBump] = pFaceLight->light[ndxStyle][ndxBump][ndxSample];

+		}

+	}

+	// just a generally lit surface

+	else

+	{

+		pSampleLight[0] = pFaceLight->light[ndxStyle][0][ndxSample];

+	}

+}

+

+

+//-----------------------------------------------------------------------------

+//-----------------------------------------------------------------------------

+void AddSampleLightToRadial( Vector const &samplePos, Vector const &sampleNormal,

+							 LightingValue_t *pSampleLight, float sampleRadius2,

+							 Vector const &luxelPos, Vector const &luxelNormal,

+							 radial_t *pRadial, int ndxRadial, bool bBumped, 

+							 bool bNeighborBumped ) 

+{

+	// check normals to see if sample contributes any light at all

+	float angle = sampleNormal.Dot( luxelNormal );

+	if ( angle < 0.15f )

+		return;

+

+	// calculate the light vector

+	Vector vSegment = samplePos - luxelPos;

+

+	// get the distance to the light

+	float dist = vSegment.Length();

+	float dist2 = dist * dist;

+

+	// Check to see if the light is within the influence.

+	float influence = 1.0f - ( dist2 / ( sampleRadius2 ) );

+	if( influence <= 0.0f )

+		return;

+

+	influence *= angle;

+

+	if( bBumped )

+	{

+		if( bNeighborBumped )

+		{

+			for( int ndxBump = 0; ndxBump < ( NUM_BUMP_VECTS+1 ); ndxBump++ )

+			{

+				pRadial->light[ndxBump][ndxRadial].AddWeighted( pSampleLight[ndxBump], influence );

+			}

+			pRadial->weight[ndxRadial] += influence;

+		}

+		else

+		{

+			influence *= 0.05f;

+			for( int ndxBump = 0; ndxBump < ( NUM_BUMP_VECTS+1 ); ndxBump++ )

+			{

+				pRadial->light[ndxBump][ndxRadial].AddWeighted( pSampleLight[0], influence );

+			}

+			pRadial->weight[ndxRadial] += influence;

+		}

+	}

+	else

+	{

+		pRadial->light[0][ndxRadial].AddWeighted( pSampleLight[0], influence );

+		pRadial->weight[ndxRadial] += influence;

+	}

+}

+

+

+//-----------------------------------------------------------------------------

+//-----------------------------------------------------------------------------

+bool CVRadDispMgr::IsNeighbor( int iFace, int iNeighborFace )

+{

+	if ( iFace == iNeighborFace )

+		return true;

+

+	faceneighbor_t *pFaceNeighbor = &faceneighbor[iFace];

+	for ( int iNeighbor = 0; iNeighbor < pFaceNeighbor->numneighbors; iNeighbor++ )

+	{

+		if ( pFaceNeighbor->neighbor[iNeighbor] == iNeighborFace )

+			return true;

+	}

+

+	return false;

+}

+

+

+//-----------------------------------------------------------------------------

+//-----------------------------------------------------------------------------

+void CVRadDispMgr::RadialLuxelAddSamples( int ndxFace, Vector const &luxelPt, Vector const &luxelNormal, float radius,

+									      radial_t *pRadial, int ndxRadial, bool bBump, int lightStyle )

+{

+	// calculate one over the voxel size

+	float ooVoxelSize = 1.0f / SAMPLEHASH_VOXEL_SIZE;

+

+	//

+	// find voxel info

+	//

+	int voxelMin[3], voxelMax[3];

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

+	{

+		voxelMin[axis] = ( int )( ( luxelPt[axis] - radius ) * ooVoxelSize );

+		voxelMax[axis] = ( int )( ( luxelPt[axis] + radius ) * ooVoxelSize ) + 1;

+	}

+

+	SampleData_t sampleData;	

+	for( int ndxZ = voxelMin[2]; ndxZ < voxelMax[2] + 1; ndxZ++ )

+	{

+		for( int ndxY = voxelMin[1]; ndxY < voxelMax[1] + 1; ndxY++ )

+		{

+			for( int ndxX = voxelMin[0]; ndxX < voxelMax[0] + 1; ndxX++ )

+			{

+				sampleData.x = ndxX * 100;

+				sampleData.y = ndxY * 10;

+				sampleData.z = ndxZ;

+				

+				UtlHashHandle_t handle = g_SampleHashTable.Find( sampleData );

+				if( handle != g_SampleHashTable.InvalidHandle() )

+				{

+					SampleData_t *pSampleData = &g_SampleHashTable.Element( handle );

+					int count = pSampleData->m_Samples.Count();

+					for( int ndx = 0; ndx < count; ndx++ )

+					{

+						SampleHandle_t sampleHandle = pSampleData->m_Samples.Element( ndx );

+						int ndxSample = ( sampleHandle & 0x0000ffff );

+						int ndxFaceLight = ( ( sampleHandle >> 16 ) & 0x0000ffff );

+

+						facelight_t *pFaceLight = &facelight[ndxFaceLight];

+						if( pFaceLight && IsNeighbor( ndxFace, ndxFaceLight ) )

+						{

+							//

+							// check for similar lightstyles

+							//

+							dface_t	*pFace = &g_pFaces[ndxFaceLight];

+							if( pFace )

+							{

+								int ndxNeighborStyle = -1;

+								for( int ndxLightStyle = 0; ndxLightStyle < MAXLIGHTMAPS; ndxLightStyle++ )

+								{

+									if( pFace->styles[ndxLightStyle] == lightStyle )

+									{

+										ndxNeighborStyle = ndxLightStyle;

+										break;

+									}

+								}

+								if( ndxNeighborStyle == -1 )

+									continue;

+								

+								// is this surface bumped???

+								bool bNeighborBump = texinfo[pFace->texinfo].flags & SURF_BUMPLIGHT ? true : false;

+								

+								LightingValue_t sampleLight[NUM_BUMP_VECTS+1];

+								GetSampleLight( pFaceLight, ndxNeighborStyle, bNeighborBump, ndxSample, sampleLight );

+								AddSampleLightToRadial( pFaceLight->sample[ndxSample].pos, pFaceLight->sample[ndxSample].normal,

+									                    sampleLight, radius*radius, luxelPt, luxelNormal, pRadial, ndxRadial,

+									                    bBump, bNeighborBump );

+							}

+						}

+					}

+				}

+			}

+		}

+	}

+}

+

+

+//-----------------------------------------------------------------------------

+//-----------------------------------------------------------------------------

+void CVRadDispMgr::RadialLuxelBuild( CVRADDispColl *pDispTree, radial_t *pRadial,

+								     int ndxStyle, bool bBump )

+{

+	//

+	// get data lighting data

+	//

+	int ndxFace = pDispTree->GetParentIndex();

+

+	dface_t *pFace = &g_pFaces[ndxFace];

+	facelight_t *pFaceLight = &facelight[ndxFace];

+

+	// get the influence radius

+	float radius2 = pDispTree->GetSampleRadius2();

+	float radius = ( float )sqrt( radius2 );

+

+	int radialSize = pRadial->w * pRadial->h;

+	for( int ndxRadial = 0; ndxRadial < radialSize; ndxRadial++ )

+	{

+		RadialLuxelAddSamples( ndxFace, pFaceLight->luxel[ndxRadial], pFaceLight->luxelNormals[ndxRadial],

+						       radius, pRadial, ndxRadial, bBump, pFace->styles[ndxStyle] );

+	}

+}

+

+

+//-----------------------------------------------------------------------------

+//-----------------------------------------------------------------------------

+radial_t *CVRadDispMgr::BuildLuxelRadial( int ndxFace, int ndxStyle, bool bBump )

+{

+	// allocate the radial

+	radial_t *pRadial = AllocateRadial( ndxFace );

+	if( !pRadial )

+		return NULL;

+

+	//

+	// step 1: get the displacement surface to be lit

+	//

+	DispCollTree_t &dispTree = m_DispTrees[g_pFaces[ndxFace].dispinfo];

+	CVRADDispColl *pDispTree = dispTree.m_pDispTree;

+	if( !pDispTree )

+		return NULL;

+

+	// step 2: build radial luxels

+	RadialLuxelBuild( pDispTree, pRadial, ndxStyle, bBump );

+

+	// step 3: return the built radial

+	return pRadial;

+}

+

+

+//-----------------------------------------------------------------------------

+//-----------------------------------------------------------------------------

+bool CVRadDispMgr::SampleRadial( int ndxFace, radial_t *pRadial, Vector const &vPos, int ndxLxl,

+								 LightingValue_t *pLightSample, int sampleCount, bool bPatch )

+{

+	bool bGoodSample = true;

+	for ( int count = 0; count < sampleCount; count++ )

+	{

+		pLightSample[count].Zero();

+

+		if ( pRadial->weight[ndxLxl] > 0.0f )

+		{

+			pLightSample[count].AddWeighted( pRadial->light[count][ndxLxl], ( 1.0f / pRadial->weight[ndxLxl] ) );

+		}

+		else

+		{

+			// error, luxel has no samples (not for patches)

+			if ( !bPatch )

+			{

+				// Yes, 2550 is correct!

+				// pLightSample[count].Init( 2550.0f, 0.0f, 2550.0f );

+				if( count == 0 )

+					bGoodSample = false;

+			}

+		}

+	}

+

+	return bGoodSample;

+}

+

+

+//-----------------------------------------------------------------------------

+//-----------------------------------------------------------------------------

+void GetPatchLight( CPatch *pPatch, bool bBump, Vector *pPatchLight )

+{

+	VectorCopy( pPatch->totallight.light[0], pPatchLight[0] );

+

+	if( bBump )

+	{

+		for( int ndxBump = 1; ndxBump < ( NUM_BUMP_VECTS + 1 ); ndxBump++ )

+		{

+			VectorCopy( pPatch->totallight.light[ndxBump], pPatchLight[ndxBump] );

+		}

+	}

+}

+

+extern void GetBumpNormals( const float* sVect, const float* tVect, const Vector& flatNormal, 

+					 const Vector& phongNormal, Vector bumpNormals[NUM_BUMP_VECTS] );

+extern void PreGetBumpNormalsForDisp( texinfo_t *pTexinfo, Vector &vecU, Vector &vecV, Vector &vecNormal );

+

+//-----------------------------------------------------------------------------

+//-----------------------------------------------------------------------------

+void AddPatchLightToRadial( Vector const &patchOrigin, Vector const &patchNormal,

+							Vector *pPatchLight, float patchRadius2,

+							Vector const &luxelPos, Vector const &luxelNormal,

+							radial_t *pRadial, int ndxRadial, bool bBump, 

+							bool bNeighborBump ) 

+{

+	// calculate the light vector

+	Vector vSegment = patchOrigin - luxelPos;

+

+	// get the distance to the light

+	float dist = vSegment.Length();

+	float dist2 = dist * dist;

+

+	// Check to see if the light is within the sample influence.

+	float influence = 1.0f - ( dist2 / ( patchRadius2 ) );

+	if ( influence <= 0.0f )

+		return;

+

+	if( bBump )

+	{

+		Vector normals[NUM_BUMP_VECTS+1];

+		normals[0] = luxelNormal;

+		texinfo_t *pTexinfo = &texinfo[g_pFaces[pRadial->facenum].texinfo];

+		Vector vecTexU, vecTexV;

+		PreGetBumpNormalsForDisp( pTexinfo, vecTexU, vecTexV, normals[0] );

+		GetBumpNormals( vecTexU, vecTexV, normals[0], normals[0], &normals[1] ); 

+

+		if( bNeighborBump )

+		{

+			float flScale = patchNormal.Dot( normals[0] );

+			flScale = clamp( flScale, 0.0f, flScale );

+			float flBumpInfluence = influence * flScale;

+

+			for( int ndxBump = 0; ndxBump < ( NUM_BUMP_VECTS+1 ); ndxBump++ )

+			{

+				pRadial->light[ndxBump][ndxRadial].AddWeighted( pPatchLight[ndxBump], flBumpInfluence );

+			}

+

+			pRadial->weight[ndxRadial] += flBumpInfluence;

+		}

+		else

+		{

+			float flScale = patchNormal.Dot( normals[0] );

+			flScale = clamp( flScale, 0.0f, flScale );

+			float flBumpInfluence = influence * flScale * 0.05f;

+

+			for( int ndxBump = 0; ndxBump < ( NUM_BUMP_VECTS+1 ); ndxBump++ )

+			{

+				pRadial->light[ndxBump][ndxRadial].AddWeighted( pPatchLight[0], flBumpInfluence );

+			}

+

+			pRadial->weight[ndxRadial] += flBumpInfluence;

+		}

+	}

+	else

+	{

+		float flScale = patchNormal.Dot( luxelNormal );

+		flScale = clamp( flScale, 0.0f, flScale );

+		influence *= flScale;

+		pRadial->light[0][ndxRadial].AddWeighted( pPatchLight[0], influence );

+

+		// add the weight value

+		pRadial->weight[ndxRadial] += influence;

+	}

+}

+

+//-----------------------------------------------------------------------------

+//-----------------------------------------------------------------------------

+void CVRadDispMgr::RadialLuxelAddPatch( int ndxFace, Vector const &luxelPt, 

+									    Vector const &luxelNormal,  float radius, 

+									    radial_t *pRadial, int ndxRadial, bool bBump,

+									    CUtlVector<CPatch*> &interestingPatches )

+{

+#ifdef SAMPLEHASH_QUERY_ONCE

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

+	{

+		CPatch *pPatch = interestingPatches[i];	

+		bool bNeighborBump = texinfo[g_pFaces[pPatch->faceNumber].texinfo].flags & SURF_BUMPLIGHT ? true : false;

+		

+		Vector patchLight[NUM_BUMP_VECTS+1];

+		GetPatchLight( pPatch, bBump, patchLight );

+		AddPatchLightToRadial( pPatch->origin, pPatch->normal, patchLight, radius*radius,

+								luxelPt, luxelNormal, pRadial, ndxRadial, bBump, bNeighborBump );

+	}

+#else

+	// calculate one over the voxel size

+	float ooVoxelSize = 1.0f / SAMPLEHASH_VOXEL_SIZE;

+

+	//

+	// find voxel info

+	//

+	int voxelMin[3], voxelMax[3];

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

+	{

+		voxelMin[axis] = ( int )( ( luxelPt[axis] - radius ) * ooVoxelSize );

+		voxelMax[axis] = ( int )( ( luxelPt[axis] + radius ) * ooVoxelSize ) + 1;

+	}

+

+	unsigned short curIterationKey = IncrementPatchIterationKey();

+	PatchSampleData_t patchData;	

+	for ( int ndxZ = voxelMin[2]; ndxZ < voxelMax[2] + 1; ndxZ++ )

+	{

+		for ( int ndxY = voxelMin[1]; ndxY < voxelMax[1] + 1; ndxY++ )

+		{

+			for ( int ndxX = voxelMin[0]; ndxX < voxelMax[0] + 1; ndxX++ )

+			{

+				patchData.x = ndxX * 100;

+				patchData.y = ndxY * 10;

+				patchData.z = ndxZ;

+				

+				UtlHashHandle_t handle = g_PatchSampleHashTable.Find( patchData );

+				if ( handle != g_PatchSampleHashTable.InvalidHandle() )

+				{

+					PatchSampleData_t *pPatchData = &g_PatchSampleHashTable.Element( handle );

+					int count = pPatchData->m_ndxPatches.Count();

+					for ( int ndx = 0; ndx < count; ndx++ )

+					{

+						int ndxPatch = pPatchData->m_ndxPatches.Element( ndx );

+						CPatch *pPatch = &g_Patches.Element( ndxPatch );

+						if ( pPatch && pPatch->m_IterationKey != curIterationKey )

+						{

+							pPatch->m_IterationKey = curIterationKey;

+							

+							if ( IsNeighbor( ndxFace, pPatch->faceNumber ) )

+							{									

+								bool bNeighborBump = texinfo[g_pFaces[pPatch->faceNumber].texinfo].flags & SURF_BUMPLIGHT ? true : false;

+								

+								Vector patchLight[NUM_BUMP_VECTS+1];

+								GetPatchLight( pPatch, bBump, patchLight );

+								AddPatchLightToRadial( pPatch->origin, pPatch->normal, patchLight, radius*radius,

+									                   luxelPt, luxelNormal, pRadial, ndxRadial, bBump, bNeighborBump );

+							}

+						}

+					}

+				}

+			}

+		}

+	}

+#endif

+}

+

+

+void CVRadDispMgr::GetInterestingPatchesForLuxels( 

+	int ndxFace,

+	CUtlVector<CPatch*> &interestingPatches,

+	float patchSampleRadius )

+{

+	facelight_t *pFaceLight = &facelight[ndxFace]; 

+

+	// Get the max bounds of all voxels that these luxels touch.

+	Vector vLuxelMin( FLT_MAX, FLT_MAX, FLT_MAX );

+	Vector vLuxelMax( -FLT_MAX, -FLT_MAX, -FLT_MAX );

+	for ( int i=0; i < pFaceLight->numluxels; i++ )

+	{

+		VectorMin( pFaceLight->luxel[i], vLuxelMin, vLuxelMin );

+		VectorMax( pFaceLight->luxel[i], vLuxelMax, vLuxelMax );

+	}

+		

+	int allVoxelMin[3], allVoxelMax[3];

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

+	{

+		allVoxelMin[axis] = ( int )( ( vLuxelMin[axis] - patchSampleRadius ) / SAMPLEHASH_VOXEL_SIZE );

+		allVoxelMax[axis] = ( int )( ( vLuxelMax[axis] + patchSampleRadius ) / SAMPLEHASH_VOXEL_SIZE ) + 1;

+	}

+	int allVoxelSize[3] = { allVoxelMax[0] - allVoxelMin[0], allVoxelMax[1] - allVoxelMin[1], allVoxelMax[2] - allVoxelMin[2] };

+

+

+	// Now figure out exactly which voxels these luxels touch.

+	CUtlVector<unsigned char> voxelBits;

+	voxelBits.SetSize( ((allVoxelSize[0] * allVoxelSize[1] * allVoxelSize[2]) + 7) / 8 );

+	memset( voxelBits.Base(), 0, voxelBits.Count() );

+	

+	for ( int i=0; i < pFaceLight->numluxels; i++ )

+	{

+		int voxelMin[3], voxelMax[3];

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

+		{

+			voxelMin[axis] = ( int )( ( pFaceLight->luxel[i][axis] - patchSampleRadius ) / SAMPLEHASH_VOXEL_SIZE );

+			voxelMax[axis] = ( int )( ( pFaceLight->luxel[i][axis] + patchSampleRadius ) / SAMPLEHASH_VOXEL_SIZE ) + 1;

+		}

+

+		for ( int x=voxelMin[0]; x < voxelMax[0]; x++ )

+		{

+			for	( int y=voxelMin[1]; y < voxelMax[1]; y++ )

+			{

+				for ( int z=voxelMin[2]; z < voxelMax[2]; z++ )

+				{

+					int iBit = (z - allVoxelMin[2])*(allVoxelSize[0]*allVoxelSize[1]) + 

+						(y-allVoxelMin[1])*allVoxelSize[0] + 

+						(x-allVoxelMin[0]);

+					voxelBits[iBit>>3] |= (1 << (iBit & 7));

+				}

+			}

+		}

+	}

+	

+	

+	// Now get the list of patches that touch those voxels.	

+	unsigned short curIterationKey = IncrementPatchIterationKey();

+

+	for ( int x=0; x < allVoxelSize[0]; x++ )

+	{

+		for ( int y=0; y < allVoxelSize[1]; y++ )

+		{

+			for ( int z=0; z < allVoxelSize[2]; z++ )

+			{

+				// Make sure this voxel has any luxels that care about it.

+				int iBit = z*(allVoxelSize[0]*allVoxelSize[1]) + y*allVoxelSize[0] + x;

+				unsigned char val = voxelBits[iBit>>3] & (1 << (iBit & 7));

+				if ( !val )

+					continue;

+				

+				PatchSampleData_t patchData;	

+				patchData.x = (x + allVoxelMin[0]) * 100;

+				patchData.y = (y + allVoxelMin[1]) * 10;

+				patchData.z = (z + allVoxelMin[2]);

+				

+				UtlHashHandle_t handle = g_PatchSampleHashTable.Find( patchData );

+				if ( handle != g_PatchSampleHashTable.InvalidHandle() )

+				{

+					PatchSampleData_t *pPatchData = &g_PatchSampleHashTable.Element( handle );

+					

+					// For all patches that touch this hash table element..

+					for ( int ndx = 0; ndx < pPatchData->m_ndxPatches.Count(); ndx++ )

+					{

+						int ndxPatch = pPatchData->m_ndxPatches.Element( ndx );

+						CPatch *pPatch = &g_Patches.Element( ndxPatch );

+						

+						// If we haven't touched the patch already and it's a valid neighbor, then we want to use it.

+						if ( pPatch && pPatch->m_IterationKey != curIterationKey )

+						{

+							pPatch->m_IterationKey = curIterationKey;

+							

+							if ( IsNeighbor( ndxFace, pPatch->faceNumber ) )

+							{

+								interestingPatches.AddToTail( pPatch );

+							}

+						}

+					}

+				}

+			}

+		}

+	}

+}

+

+

+//-----------------------------------------------------------------------------

+//-----------------------------------------------------------------------------

+void CVRadDispMgr::RadialPatchBuild( CVRADDispColl *pDispTree, radial_t *pRadial,

+									 bool bBump )

+{

+	//

+	// get data lighting data

+	//

+	int ndxFace = pDispTree->GetParentIndex();

+	facelight_t *pFaceLight = &facelight[ndxFace];

+

+	// get the influence radius

+	float radius2 = pDispTree->GetPatchSampleRadius2();

+	float radius = ( float )sqrt( radius2 );

+

+	CUtlVector<CPatch*> interestingPatches;

+#ifdef SAMPLEHASH_QUERY_ONCE

+	GetInterestingPatchesForLuxels( ndxFace, interestingPatches, radius );

+#endif

+

+	int radialSize = pRadial->w * pRadial->h;

+	for( int ndxRadial = 0; ndxRadial < radialSize; ndxRadial++ )

+	{

+		RadialLuxelAddPatch( 

+			ndxFace, 

+			pFaceLight->luxel[ndxRadial], 

+			pFaceLight->luxelNormals[ndxRadial],

+			radius, 

+			pRadial, 

+			ndxRadial, 

+			bBump,

+			interestingPatches );

+	}

+}

+

+//-----------------------------------------------------------------------------

+//-----------------------------------------------------------------------------

+radial_t *CVRadDispMgr::BuildPatchRadial( int ndxFace, bool bBump )

+{

+	// allocate the radial

+	radial_t *pRadial = AllocateRadial( ndxFace );

+	if( !pRadial )

+		return NULL;

+

+	//

+	// step 1: get the displacement surface to be lit

+	//

+	DispCollTree_t &dispTree = m_DispTrees[g_pFaces[ndxFace].dispinfo];

+	CVRADDispColl *pDispTree = dispTree.m_pDispTree;

+	if( !pDispTree )

+		return NULL;

+

+	// step 2: build radial of patch light

+	RadialPatchBuild( pDispTree, pRadial, bBump );

+

+	// step 3: return the built radial

+	return pRadial;

+}

+

+

+//-----------------------------------------------------------------------------

+//-----------------------------------------------------------------------------

+bool SampleInSolid( sample_t *pSample )

+{

+	int ndxLeaf = PointLeafnum( pSample->pos );

+	return ( dleafs[ndxLeaf].contents == CONTENTS_SOLID );

+}

+

+

+//-----------------------------------------------------------------------------

+//-----------------------------------------------------------------------------

+void CVRadDispMgr::InsertSamplesDataIntoHashTable( void )

+{

+	int totalSamples = 0;

+#if 0

+	int totalSamplesInSolid = 0;

+#endif

+

+	for( int ndxFace = 0; ndxFace < numfaces; ndxFace++ )

+	{

+		dface_t *pFace = &g_pFaces[ndxFace];

+		facelight_t *pFaceLight = &facelight[ndxFace];

+		if( !pFace || !pFaceLight )

+			continue;

+		

+		if( texinfo[pFace->texinfo].flags & TEX_SPECIAL )

+			continue;

+

+#if 0

+		bool bDisp = ( pFace->dispinfo != -1 );

+#endif

+		//

+		// for each sample

+		//

+		for( int ndxSample = 0; ndxSample < pFaceLight->numsamples; ndxSample++ )

+		{

+			sample_t *pSample = &pFaceLight->sample[ndxSample];

+			if( pSample )

+			{

+#if 0

+				if( bDisp )

+				{

+					// test sample to see if the displacement samples resides in solid

+					if( SampleInSolid( pSample ) )

+					{

+						totalSamplesInSolid++;

+						continue;

+					}

+				}

+#endif

+

+				// create the sample handle

+				SampleHandle_t sampleHandle = ndxSample;

+				sampleHandle |= ( ndxFace << 16 );

+				

+				SampleData_AddSample( pSample, sampleHandle );

+			}

+

+		}

+

+		totalSamples += pFaceLight->numsamples;

+	}

+

+#if 0

+	// not implemented yet!!!

+	Msg( "%d samples in solid\n", totalSamplesInSolid );

+#endif

+

+	// log the distribution

+	SampleData_Log();

+}

+

+

+//-----------------------------------------------------------------------------

+//-----------------------------------------------------------------------------

+void CVRadDispMgr::InsertPatchSampleDataIntoHashTable( void )

+{

+	// don't insert patch samples if we are not bouncing light

+	if( numbounce <= 0 )

+		return;

+

+	int totalPatchSamples = 0;

+

+	for( int ndxFace = 0; ndxFace < numfaces; ndxFace++ )

+	{

+		dface_t *pFace = &g_pFaces[ndxFace];

+		facelight_t *pFaceLight = &facelight[ndxFace];

+		if( !pFace || !pFaceLight )

+			continue;

+		

+		if( texinfo[pFace->texinfo].flags & TEX_SPECIAL )

+			continue;

+		

+		//

+		// for each patch

+		//

+		CPatch *pNextPatch = NULL;

+		if( g_FacePatches.Element( ndxFace ) != g_FacePatches.InvalidIndex() )

+		{

+			for( CPatch *pPatch = &g_Patches.Element( g_FacePatches.Element( ndxFace ) ); pPatch; pPatch = pNextPatch )

+			{

+				// next patch

+				pNextPatch = NULL;

+				if( pPatch->ndxNext != g_Patches.InvalidIndex() )

+				{

+					pNextPatch = &g_Patches.Element( pPatch->ndxNext );

+				}

+			

+				// skip patches with children

+				if( pPatch->child1 != g_Patches.InvalidIndex() )

+					continue;

+			

+				int ndxPatch = pPatch - g_Patches.Base();

+				PatchSampleData_AddSample( pPatch, ndxPatch );

+

+				totalPatchSamples++;

+			}

+		}

+	}

+}

+

+

+//-----------------------------------------------------------------------------

+//-----------------------------------------------------------------------------

+void CVRadDispMgr::StartTimer( const char *name )

+{

+	Msg( name );

+	m_Timer.Start();

+}

+

+

+//-----------------------------------------------------------------------------

+//-----------------------------------------------------------------------------

+void CVRadDispMgr::EndTimer( void )

+{

+	m_Timer.End();

+	CCycleCount duration = m_Timer.GetDuration();

+	double seconds = duration.GetSeconds();

+

+	Msg( "Done<%1.4lf sec>\n", seconds );

+}

+

+

+//-----------------------------------------------------------------------------

+//-----------------------------------------------------------------------------

+bool CVRadDispMgr::BuildDispSamples( lightinfo_t *pLightInfo, facelight_t *pFaceLight, int ndxFace )

+{

+	// get the tree assosciated with the face

+	DispCollTree_t &dispTree = m_DispTrees[g_pFaces[ndxFace].dispinfo];

+	CVRADDispColl *pDispTree = dispTree.m_pDispTree;

+	if( !pDispTree )

+		return false;

+

+	// lightmap size

+	int width = pLightInfo->face->m_LightmapTextureSizeInLuxels[0]+1;

+	int height = pLightInfo->face->m_LightmapTextureSizeInLuxels[1]+1;

+

+	// calculate the steps in uv space

+	float stepU = 1.0f / ( float )width;

+	float stepV = 1.0f / ( float )height;

+	float halfStepU = stepU * 0.5f;

+	float halfStepV = stepV * 0.5f;

+	

+	//

+	// build the winding points (used to generate world space winding and

+	// calculate the area of the "sample")

+	//

+	int ndxU, ndxV;

+

+	// NOTE: These allocations are necessary to avoid stack overflow

+	// FIXME: Solve with storing global per-thread temp buffers if there's

+	// a performance problem with this solution...

+	bool bTempAllocationNecessary = ((height + 1) * (width + 1)) > SINGLE_BRUSH_MAP;

+

+	Vector worldPointBuffer[SINGLE_BRUSH_MAP];

+	sample_t sampleBuffer[SINGLE_BRUSH_MAP*2];

+

+	Vector *pWorldPoints = worldPointBuffer;

+	sample_t *pSamples = sampleBuffer;

+	if (bTempAllocationNecessary)

+	{

+		pWorldPoints = new Vector[ SINGLEMAP ];

+		pSamples = new sample_t[ SINGLEMAP ];

+	}

+

+	for( ndxV = 0; ndxV < ( height + 1 ); ndxV++ )

+	{

+		for( ndxU = 0; ndxU < ( width + 1 ); ndxU++ )

+		{

+			int ndx = ( ndxV * ( width + 1 ) ) + ndxU;

+

+			Vector2D uv( ndxU * stepU, ndxV * stepV );

+			pDispTree->DispUVToSurfPoint( uv, pWorldPoints[ndx], 0.0f );

+		}

+	}

+

+

+	for( ndxV = 0; ndxV < height; ndxV++ )

+	{

+		for( ndxU = 0; ndxU < width; ndxU++ )

+		{

+			// build the winding

+			winding_t *pWinding = AllocWinding( 4 );

+			if( pWinding )

+			{

+				pWinding->numpoints = 4;

+				pWinding->p[0] = pWorldPoints[(ndxV*(width+1))+ndxU];

+				pWinding->p[1] = pWorldPoints[((ndxV+1)*(width+1))+ndxU];

+				pWinding->p[2] = pWorldPoints[((ndxV+1)*(width+1))+(ndxU+1)];

+				pWinding->p[3] = pWorldPoints[(ndxV*(width+1))+(ndxU+1)];

+				

+				// calculate the area

+				float area = WindingArea( pWinding );

+				

+				int ndxSample = ( ndxV * width ) + ndxU;

+				pSamples[ndxSample].w = pWinding;

+				pSamples[ndxSample].area = area;

+			}

+			else

+			{

+				Msg( "BuildDispSamples: WARNING - failed winding allocation\n" );

+			}

+		}

+	}

+

+	//

+	// build the samples points (based on s, t and sampleoffset (center of samples);

+	// generates world space position and normal)

+	//

+	for( ndxV = 0; ndxV < height; ndxV++ )

+	{

+		for( ndxU = 0; ndxU < width; ndxU++ )

+		{

+			int ndxSample = ( ndxV * width ) + ndxU;

+			pSamples[ndxSample].s = ndxU;

+			pSamples[ndxSample].t = ndxV;

+			pSamples[ndxSample].coord[0] = ( ndxU * stepU ) + halfStepU;

+			pSamples[ndxSample].coord[1] = ( ndxV * stepV ) + halfStepV;

+			pDispTree->DispUVToSurfPoint( pSamples[ndxSample].coord, pSamples[ndxSample].pos, 1.0f );

+			pDispTree->DispUVToSurfNormal( pSamples[ndxSample].coord, pSamples[ndxSample].normal );			

+		}

+	}

+

+	//

+	// copy over samples

+	//

+	pFaceLight->numsamples = width * height;

+	pFaceLight->sample = ( sample_t* )calloc( pFaceLight->numsamples, sizeof( *pFaceLight->sample ) );

+	if( !pFaceLight->sample )

+		goto buildDispSamplesError;

+

+	memcpy( pFaceLight->sample, pSamples, pFaceLight->numsamples * sizeof( *pFaceLight->sample ) );

+

+	// statistics - warning?!

+	if( pFaceLight->numsamples == 0 )

+	{

+		Msg( "BuildDispSamples: WARNING - no samples %d\n", pLightInfo->face - g_pFaces );

+	}

+ 

+	if (bTempAllocationNecessary)

+	{

+		delete[] pWorldPoints;

+		delete[] pSamples;

+	}

+

+	return true;

+

+buildDispSamplesError:

+	if (bTempAllocationNecessary)

+	{

+		delete[] pWorldPoints;

+		delete[] pSamples;

+	}

+

+	return false;

+}

+

+

+//-----------------------------------------------------------------------------

+//-----------------------------------------------------------------------------

+bool CVRadDispMgr::BuildDispLuxels( lightinfo_t *pLightInfo, facelight_t *pFaceLight, int ndxFace )

+{

+	// get the tree assosciated with the face

+	DispCollTree_t &dispTree = m_DispTrees[g_pFaces[ndxFace].dispinfo];

+	CVRADDispColl *pDispTree = dispTree.m_pDispTree;

+	if( !pDispTree )

+		return false;

+

+	// lightmap size

+	int width = pLightInfo->face->m_LightmapTextureSizeInLuxels[0]+1;

+	int height = pLightInfo->face->m_LightmapTextureSizeInLuxels[1]+1;

+

+	// calcuate actual luxel points

+	pFaceLight->numluxels = width * height;

+	pFaceLight->luxel = ( Vector* )calloc( pFaceLight->numluxels, sizeof( *pFaceLight->luxel ) );

+	pFaceLight->luxelNormals = ( Vector* )calloc( pFaceLight->numluxels, sizeof( Vector ) );

+	if( !pFaceLight->luxel || !pFaceLight->luxelNormals )

+		return false;

+

+	float stepU = 1.0f / ( float )( width - 1 );

+	float stepV = 1.0f / ( float )( height - 1 );

+

+	for( int ndxV = 0; ndxV < height; ndxV++ )

+	{

+		for( int ndxU = 0; ndxU < width; ndxU++ )

+		{

+			int ndxLuxel = ( ndxV * width ) + ndxU; 

+

+			Vector2D uv( ndxU * stepU, ndxV * stepV );

+			pDispTree->DispUVToSurfPoint( uv, pFaceLight->luxel[ndxLuxel], 1.0f );

+			pDispTree->DispUVToSurfNormal( uv, pFaceLight->luxelNormals[ndxLuxel] );			

+		}

+	}

+

+	return true;

+}

+

+

+//-----------------------------------------------------------------------------

+//-----------------------------------------------------------------------------

+bool CVRadDispMgr::BuildDispSamplesAndLuxels_DoFast( lightinfo_t *pLightInfo, facelight_t *pFaceLight, int ndxFace )

+{

+	// get the tree assosciated with the face

+	DispCollTree_t &dispTree = m_DispTrees[g_pFaces[ndxFace].dispinfo];

+	CVRADDispColl *pDispTree = dispTree.m_pDispTree;

+	if( !pDispTree )

+		return false;

+

+	// lightmap size

+	int width = pLightInfo->face->m_LightmapTextureSizeInLuxels[0]+1;

+	int height = pLightInfo->face->m_LightmapTextureSizeInLuxels[1]+1;

+

+	// calcuate actual luxel points

+	pFaceLight->numsamples = width * height;

+	pFaceLight->sample = ( sample_t* )calloc( pFaceLight->numsamples, sizeof( *pFaceLight->sample ) );

+	if( !pFaceLight->sample )

+		return false;

+

+	pFaceLight->numluxels = width * height;

+	pFaceLight->luxel = ( Vector* )calloc( pFaceLight->numluxels, sizeof( *pFaceLight->luxel ) );

+	pFaceLight->luxelNormals = ( Vector* )calloc( pFaceLight->numluxels, sizeof( Vector ) );

+	if( !pFaceLight->luxel || !pFaceLight->luxelNormals )

+		return false;

+

+	float stepU = 1.0f / ( float )( width - 1 );

+	float stepV = 1.0f / ( float )( height - 1 );

+	float halfStepU = stepU * 0.5f;

+	float halfStepV = stepV * 0.5f;

+

+	for( int ndxV = 0; ndxV < height; ndxV++ )

+	{

+		for( int ndxU = 0; ndxU < width; ndxU++ )

+		{

+			int ndx = ( ndxV * width ) + ndxU;

+

+			pFaceLight->sample[ndx].s = ndxU;

+			pFaceLight->sample[ndx].t = ndxV;

+			pFaceLight->sample[ndx].coord[0] = ( ndxU * stepU ) + halfStepU;

+			pFaceLight->sample[ndx].coord[1] = ( ndxV * stepV ) + halfStepV;

+

+			pDispTree->DispUVToSurfPoint( pFaceLight->sample[ndx].coord, pFaceLight->sample[ndx].pos, 1.0f );

+			pDispTree->DispUVToSurfNormal( pFaceLight->sample[ndx].coord, pFaceLight->sample[ndx].normal );			

+

+			pFaceLight->luxel[ndx] = pFaceLight->sample[ndx].pos;

+			pFaceLight->luxelNormals[ndx] = pFaceLight->sample[ndx].normal;

+		}

+	}

+

+	return true;

+}