text: //========= 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 = max( 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 = max( 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 = max( 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;
  
  	CUtlVector<sample_t> samples;
  	samples.SetCount( SINGLEMAP );
  	sample_t *pSamples = samples.Base();
  
  	CUtlVector<Vector> worldPoints;
  	worldPoints.SetCount( SINGLEMAP );
  	Vector *pWorldPoints = worldPoints.Base();
  
  	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 )
  		return false;
  
  	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 );
  	}
  
  	return true;
  }
  
  
  //-----------------------------------------------------------------------------
  //-----------------------------------------------------------------------------
  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;
  }
  