1HEADmaster

1 files changed, 2930 insertions, 0 deletions

diff --git a/engine/spatialpartition.cpp b/engine/spatialpartition.cpp
new file mode 100644
index 0000000..489dd9c
--- /dev/null
+++ b/engine/spatialpartition.cpp
@@ -0,0 +1,2930 @@
+//========= Copyright Valve Corporation, All rights reserved. ============//
+//
+// Purpose: 
+//
+// $NoKeywords: $
+//
+// @TODO: The features and implementation of these class classes require overly
+//		  broad mutexing. Needs to be addressed. (toml 3-20-06)
+//
+//===========================================================================//
+
+#include "mathlib/vector.h"
+#include "utlhash.h"
+#include "utllinkedlist.h"
+#include "utllinkedlist.h"
+#include "ispatialpartitioninternal.h"
+#include "bsptreedata.h"
+#include "worldsize.h"
+#include "cmodel.h"
+#include "sys_dll.h"
+#include "collisionutils.h"
+#include "debugoverlay.h"
+#include "tier0/vprof.h"
+#include "tier1/utlbuffer.h"
+#include "filesystem_engine.h"
+#include "filesystem.h"
+#include "tier1/convar.h"
+#include "tier1/memstack.h"
+#include "enginethreads.h"
+#include "datacache/imdlcache.h"
+#include "tier2/renderutils.h"
+#include "bitvec.h"
+#include "tier1/mempool.h"
+
+// memdbgon must be the last include file in a .cpp file!!!
+#include "tier0/memdbgon.h"
+
+class CVoxelTree;
+class CIntersectSweptBox;
+
+#define SPHASH_LEVEL_SKIP	2
+
+#define SPHASH_VOXEL_SIZE	256			// must power of 2
+#define SPHASH_VOXEL_SHIFT	8			// shift for voxel size
+
+#define SPHASH_VOXEL_LARGE	65536.0f
+
+#define SPHASH_HANDLELIST_BLOCK		256
+#define SPHASH_LEAFLIST_BLOCK		512
+#define SPHASH_ENTITYLIST_BLOCK		256
+#define SPHASH_BUCKET_COUNT			512
+
+#define SPHASH_EPS					0.03125f
+
+enum PartitionTrees_t
+{
+	CLIENT_TREE,
+	SERVER_TREE,
+	NUM_TREES,
+};
+
+class CPartitionVisitor;
+
+#if defined( _X360 )
+#pragma bitfield_order( push, lsb_to_msb )
+#endif
+union Voxel_t
+{
+	struct
+	{
+		unsigned int x:11;
+		unsigned int y:11;
+		unsigned int z:10;
+	} bitsVoxel;
+	unsigned int uiVoxel;  
+};
+#if defined( _X360 )
+#pragma bitfield_order( pop )
+#endif
+
+enum EntityInfoFlags_t
+{
+	ENTITY_HIDDEN	=	( 1 << 0 ),
+	IN_CLIENT_TREE	=	( 1 << 1 ),
+	IN_SERVER_TREE	=	( 1 << 2 ),
+};
+
+
+struct EntityInfo_t
+{
+	Vector						m_vecMin;			// Min/Max of entity
+	Vector						m_vecMax;
+	IHandleEntity *				m_pHandleEntity;	// Entity handle.
+	unsigned short				m_fList;			// Which lists is it in?
+	uint8						m_flags;
+	char						m_nLevel[NUM_TREES];	// Which level voxel tree is it in?
+	unsigned short				m_nVisitBit[NUM_TREES];
+	int							m_iLeafList[NUM_TREES];	// Index into the leaf pool - leaf list for entity (m_aLeafList).
+};
+
+
+struct LeafListData_t
+{
+	UtlHashFastHandle_t		m_hVoxel;	// Voxel handle the entity is in.
+	int						m_iEntity;	// Entity list index for voxel
+};
+
+typedef CUtlFixedLinkedList<LeafListData_t>	CLeafList;
+
+typedef CVarBitVec CPartitionVisits;
+
+//-----------------------------------------------------------------------------
+// Used when rendering the various levels of the voxel hash
+//-----------------------------------------------------------------------------
+static Color s_pVoxelColor[9] = 
+{
+	Color( 255, 0, 0, 255 ),
+	Color( 0, 255, 0, 255 ),
+	Color( 0, 0, 255, 255 ),
+	Color( 255, 0, 255, 255 ),
+	Color( 255, 255, 0, 255 ),
+	Color( 0, 255, 255, 255 ),
+	Color( 255, 255, 255, 255 ),
+	Color( 192, 192, 0, 255 ),
+	Color( 128, 128, 128, 255 ),
+};
+
+
+// bounds of the spatial partition
+static Vector s_PartitionMin( MIN_COORD_FLOAT, MIN_COORD_FLOAT, MIN_COORD_FLOAT );
+static Vector s_PartitionMax( MAX_COORD_FLOAT, MAX_COORD_FLOAT, MAX_COORD_FLOAT );
+
+//-----------------------------------------------------------------------------
+// Divide voxel coordinates by 2
+//-----------------------------------------------------------------------------
+inline Voxel_t ConvertToNextLevel( Voxel_t v )
+{
+	// Just need to divide by 2 and eliminate the low bits of y and z that shifted
+	// into the x and y fields
+	Voxel_t res;
+	res.uiVoxel = ( ( v.uiVoxel >> SPHASH_LEVEL_SKIP ) & 0xFFCFF9FF );
+	return res;
+}
+
+
+//-----------------------------------------------------------------------------
+// A single voxel hash
+//-----------------------------------------------------------------------------
+class CVoxelHash
+{
+public:
+	// Constructor, destructor
+	CVoxelHash();
+	~CVoxelHash();
+
+	// Call this to clear out the spatial partition and to re-initialize it given a particular world size (ISpatialPartitionInternal)
+	void Init( CVoxelTree *pPartition, const Vector& worldmin, const Vector& worldmax, int nLevel );
+	void Shutdown();
+
+	// Gets all entities in a particular volume...
+	// returns false if the enumerator broke early
+	bool EnumerateElementsInBox( SpatialPartitionListMask_t listMask, Voxel_t vmin, Voxel_t vmax, const Vector& mins, const Vector& maxs, IPartitionEnumerator* pIterator );
+	bool EnumerateElementsAlongRay( SpatialPartitionListMask_t listMask, const Ray_t& ray, const Vector &vecInvDelta, const Vector &vecEnd, IPartitionEnumerator* pIterator );
+	bool EnumerateElementsAtPoint( SpatialPartitionListMask_t listMask, Voxel_t v, const Vector& pt, IPartitionEnumerator* pIterator );
+	
+	// Inserts/Removes a handle from the tree.
+	void InsertIntoTree( SpatialPartitionHandle_t hPartition, const Vector &vecMin, const Vector &vecMax );
+	void RemoveFromTree( SpatialPartitionHandle_t hPartition );
+
+	// Debug!
+	void RenderAllObjectsInTree( float flTime );
+	void RenderObjectsInPlayerLeafs( const Vector &vecPlayerMin, const Vector &vecPlayerMax, float flTime );
+	void RenderVoxel( Voxel_t voxel, float flTime );
+	void RenderObjectInVoxel( SpatialPartitionHandle_t hPartition, CPartitionVisitor *pVisitor, float flTime );
+	void RenderObjectsInVoxel( Voxel_t voxel, CPartitionVisitor *pVisitor, bool bRenderVoxel, float flTime );
+
+	// Computes the voxel count in 1 dimension at a particular level of the tree
+	static int ComputeVoxelCountAtLevel( int nLevel );
+
+	// Gets the voxel size for this hash
+	int VoxelSize( ) const;
+
+	int EntityCount();
+
+	// Rendering methods
+	void RenderGrid();
+
+	// Converts point into voxel index
+	inline Voxel_t VoxelIndexFromPoint( const Vector &vecWorldPoint );
+	inline void VoxelIndexFromPoint( const Vector &vecWorldPoint, int pPoint[3] );
+
+	// Setup ray for iteration
+	void LeafListRaySetup( const Ray_t &ray, const Vector &vecEnd, const Vector &vecInvDelta, Voxel_t voxel, int *pStep, float *pMax, float *pDelta );
+	void LeafListExtrudedRaySetup( const Ray_t &ray, const Vector &vecInvDelta, const Vector &vecMin, const Vector &vecMax, int iVoxelMin[3], int iVoxelMax[3], int *pStep, float *pMin, float *pMax, float *pDelta );
+
+	// Main enumeration method
+	template <class T> bool EnumerateElementsInVoxel( Voxel_t voxel, const T &intersectTest, SpatialPartitionListMask_t listMask, IPartitionEnumerator* pIterator );
+
+	// Enumeration method when only 1 voxel is ever visited
+	template <class T> bool EnumerateElementsInSingleVoxel( Voxel_t voxel, const T &intersectTest, SpatialPartitionListMask_t listMask, IPartitionEnumerator* pIterator );
+
+	bool EnumerateElementsAlongRay_ExtrudedRaySlice( SpatialPartitionListMask_t listMask, IPartitionEnumerator *pIterator, const CIntersectSweptBox &intersectSweptBox,	int voxelMin[3], int voxelMax[3], int iAxis, int *pStep );
+private:
+	bool EnumerateElementsAlongRay_Ray( SpatialPartitionListMask_t listMask, const Ray_t &ray, const Vector &vecInvDelta, const Vector &vecEnd, IPartitionEnumerator* pIterator );
+	bool EnumerateElementsAlongRay_ExtrudedRay( SpatialPartitionListMask_t listMask, const Ray_t &ray, const Vector &vecInvDelta, const Vector &vecEnd, IPartitionEnumerator* pIterator );
+
+	inline void PackVoxel( int iX, int iY, int iZ, Voxel_t &voxel );
+
+	typedef CUtlHashFixed<int, SPHASH_BUCKET_COUNT, CUtlHashFixedGenericHash<SPHASH_BUCKET_COUNT> > CHashTable;
+
+	Vector											m_vecVoxelOrigin;	// Voxel space (hash) origin.
+	CHashTable										m_aVoxelHash;		// Voxel tree (hash) - data = entity list head handle (m_aEntityList)
+	int												m_nVoxelDelta[3];	// Voxel world - width(Dx), height(Dy), depth(Dz)
+	CUtlFixedLinkedList<SpatialPartitionHandle_t>	m_aEntityList;	// Pool - Linked list(multilist) of entities per leaf.
+	CVoxelTree										*m_pTree;
+	int												m_nLevel;
+};
+
+class CSpatialPartition;
+
+//-----------------------------------------------------------------------------
+// 
+//-----------------------------------------------------------------------------
+
+class CVoxelTree
+{
+public:
+	// constructor, destructor
+	CVoxelTree();
+	virtual ~CVoxelTree();
+
+	// Inherited from ISpatialPartition
+	virtual void Init(  CSpatialPartition *pOwner, int iTree, const Vector& worldmin, const Vector& worldmax );
+
+	virtual void ElementMoved( SpatialPartitionHandle_t handle, const Vector& mins, const Vector& maxs );
+	virtual void EnumerateElementsInBox( SpatialPartitionListMask_t listMask, const Vector& mins, const Vector& maxs, bool coarseTest, IPartitionEnumerator* pIterator );
+	virtual void EnumerateElementsInSphere( SpatialPartitionListMask_t listMask, const Vector& origin, float radius, bool coarseTest, IPartitionEnumerator* pIterator );
+	virtual void EnumerateElementsAlongRay( SpatialPartitionListMask_t listMask, const Ray_t& ray, bool coarseTest, IPartitionEnumerator* pIterator );
+	virtual void EnumerateElementsAtPoint( SpatialPartitionListMask_t listMask, const Vector& pt, bool coarseTest, IPartitionEnumerator* pIterator );
+
+	virtual void RenderAllObjectsInTree( float flTime );
+	virtual void RenderObjectsInPlayerLeafs( const Vector &vecPlayerMin, const Vector &vecPlayerMax, float flTime );
+
+	virtual void ReportStats( const char *pFileName );
+	virtual void DrawDebugOverlays();
+
+	EntityInfo_t &EntityInfo( SpatialPartitionHandle_t hPartition );
+	CLeafList &LeafList();
+
+	int GetTreeId() const;
+
+	CPartitionVisits *BeginVisit();
+	CPartitionVisits *GetVisits();
+	void EndVisit( CPartitionVisits * );
+
+	// Shut down the allocated memory
+	void Shutdown( void );
+
+	// Insert into the appropriate tree
+	void InsertIntoTree( SpatialPartitionHandle_t hPartition, const Vector& mins, const Vector& maxs );
+
+	// Remove from appropriate tree
+	void RemoveFromTree( SpatialPartitionHandle_t hPartition );
+
+	void LockForWrite()		{ m_lock.LockForWrite(); }
+	void UnlockWrite()		{ m_lock.UnlockWrite(); }
+
+	void LockForRead()		{ m_lock.LockForRead(); }
+	void UnlockRead()		{ m_lock.UnlockRead(); }
+
+	// Ray casting
+	bool EnumerateElementsAlongRay_Ray( SpatialPartitionListMask_t listMask, const Ray_t &ray, const Vector &vecInvDelta, const Vector &vecEnd, IPartitionEnumerator *pIterator );
+	bool EnumerateElementsAlongRay_ExtrudedRay( SpatialPartitionListMask_t listMask, 
+		const Ray_t &ray, const Vector &vecInvDelta, const Vector &vecEnd, IPartitionEnumerator *pIterator );
+
+	// Purpose:
+	void ComputeSweptRayBounds( const Ray_t &ray, const Vector &vecStartMin, const Vector &vecStartMax, Vector *pVecMin, Vector *pVecMax );
+
+private:
+
+	int									m_nLevelCount;
+	CVoxelHash*							m_pVoxelHash;
+	CLeafList							m_aLeafList;								// Pool - Linked list(multilist) of leaves per entity.
+	int									m_TreeId;
+	CThreadLocalPtr<CPartitionVisits>	m_pVisits;
+	CSpatialPartition *					m_pOwner;
+	CUtlVector<unsigned short>			m_AvailableVisitBits;
+	unsigned short						m_nNextVisitBit;
+#if TEST_TRACE_POOL
+	CTSPool<CPartitionVisits>			m_FreeVisits;
+#else
+	CObjectPool<CPartitionVisits, 2>	m_FreeVisits;
+#endif
+	CThreadSpinRWLock					m_lock;
+};
+
+//-----------------------------------------------------------------------------
+// The spatial partition
+//-----------------------------------------------------------------------------
+
+class CSpatialPartition : public ISpatialPartitionInternal
+{
+public:
+	CSpatialPartition();
+	~CSpatialPartition();
+
+	enum 
+	{ 
+		MAX_QUERY_CALLBACK = 3 
+	};
+
+	// Inherited from ISpatialPartition
+	virtual void Init( const Vector& worldmin, const Vector& worldmax );
+	void Shutdown( void );
+
+	virtual SpatialPartitionHandle_t CreateHandle( IHandleEntity *pHandleEntity );
+	virtual SpatialPartitionHandle_t CreateHandle( IHandleEntity *pHandleEntity, SpatialPartitionListMask_t listMask, const Vector& mins, const Vector& maxs ); 
+	virtual void DestroyHandle( SpatialPartitionHandle_t handle );
+
+	virtual void Insert( SpatialPartitionListMask_t listMask, SpatialPartitionHandle_t handle );
+	virtual void Remove( SpatialPartitionListMask_t listMask, SpatialPartitionHandle_t handle );
+	virtual void RemoveAndInsert( SpatialPartitionListMask_t removeMask, SpatialPartitionListMask_t insertMask, SpatialPartitionHandle_t handle );
+	virtual void Remove( SpatialPartitionHandle_t handle );
+
+	virtual SpatialTempHandle_t HideElement( SpatialPartitionHandle_t handle );
+	virtual void UnhideElement( SpatialPartitionHandle_t handle, SpatialTempHandle_t tempHandle );
+
+	virtual void InstallQueryCallback( IPartitionQueryCallback *pCallback );
+	virtual void InstallQueryCallback_V1( IPartitionQueryCallback *pCallback );
+	virtual void RemoveQueryCallback( IPartitionQueryCallback *pCallback );
+
+	virtual void SuppressLists( SpatialPartitionListMask_t nListMask, bool bSuppress );
+	virtual SpatialPartitionListMask_t GetSuppressedLists( void );
+
+	virtual void RenderLeafsForRayTraceStart( float flTime )	{ }
+	virtual void RenderLeafsForRayTraceEnd( void )				{ }
+	virtual void RenderLeafsForHullTraceStart( float flTime )	{ }
+	virtual void RenderLeafsForHullTraceEnd( void )				{ }
+	virtual void RenderLeafsForBoxStart( float flTime )			{ }
+	virtual void RenderLeafsForBoxEnd( void )					{ }
+	virtual void RenderLeafsForSphereStart( float flTime )		{ }
+	virtual void RenderLeafsForSphereEnd( void )				{ }
+
+	virtual void RenderObjectsInBox( const Vector &vecMin, const Vector &vecMax, float flTime );
+	virtual void RenderObjectsInSphere( const Vector &vecCenter, float flRadius, float flTime );
+	virtual void RenderObjectsAlongRay( const Ray_t& ray, float flTime );
+
+	virtual void ElementMoved( SpatialPartitionHandle_t handle, const Vector& mins, const Vector& maxs );
+	virtual void EnumerateElementsInBox( SpatialPartitionListMask_t listMask, const Vector& mins, const Vector& maxs, bool coarseTest, IPartitionEnumerator* pIterator );
+	virtual void EnumerateElementsInSphere( SpatialPartitionListMask_t listMask, const Vector& origin, float radius, bool coarseTest, IPartitionEnumerator* pIterator );
+	virtual void EnumerateElementsAlongRay( SpatialPartitionListMask_t listMask, const Ray_t& ray, bool coarseTest, IPartitionEnumerator* pIterator );
+	virtual void EnumerateElementsAtPoint( SpatialPartitionListMask_t listMask, const Vector& pt, bool coarseTest, IPartitionEnumerator* pIterator );
+
+	virtual void RenderAllObjectsInTree( float flTime );
+	virtual void RenderObjectsInPlayerLeafs( const Vector &vecPlayerMin, const Vector &vecPlayerMax, float flTime );
+	virtual void ReportStats( const char *pFileName );
+	virtual void DrawDebugOverlays();
+
+	// Gets entity info (for enumerations).
+	EntityInfo_t &EntityInfo( SpatialPartitionHandle_t hPartition );
+
+	virtual void InsertIntoTree( SpatialPartitionHandle_t hPartition, const Vector& mins, const Vector& maxs );
+	virtual void RemoveFromTree( SpatialPartitionHandle_t hPartition );
+
+	CVoxelTree * VoxelTree( SpatialPartitionListMask_t listMask );
+	CVoxelTree * VoxelTreeForHandle( SpatialPartitionHandle_t handle );
+
+protected:
+	// Invokes the pre-query callbacks.
+	void InvokeQueryCallbacks( SpatialPartitionListMask_t listMask, bool = false );
+
+	typedef CUtlLinkedList<EntityInfo_t, SpatialPartitionHandle_t, false, SpatialPartitionHandle_t, CUtlMemoryStack<UtlLinkedListElem_t< EntityInfo_t, SpatialPartitionHandle_t >, SpatialPartitionHandle_t, 0xffff, 1024> > CHandleList;
+
+private:
+	CHandleList												m_aHandles;  								// Stores all unique elements (1 per entity in tree).
+	CThreadFastMutex										m_HandlesMutex;
+
+	CVoxelTree												m_VoxelTrees[NUM_TREES];
+
+	IPartitionQueryCallback									*m_pQueryCallback[MAX_QUERY_CALLBACK];		// Query callbacks.
+	bool													m_bUseOldQueryCallback[MAX_QUERY_CALLBACK];
+	int														m_nQueryCallbackCount;						// Number of query callbacks.
+
+	// Debug!
+	SpatialPartitionListMask_t								m_nSuppressedListMask;
+};
+
+//-----------------------------------------------------------------------------
+// Spatial partition inline methods
+//-----------------------------------------------------------------------------
+// Gets entity info (for enumerations).
+inline EntityInfo_t &CSpatialPartition::EntityInfo( SpatialPartitionHandle_t hPartition )		
+{ 
+	return m_aHandles[hPartition]; 
+}
+
+inline EntityInfo_t &CVoxelTree::EntityInfo( SpatialPartitionHandle_t hPartition )
+{
+	return m_pOwner->EntityInfo( hPartition );
+}
+
+inline CLeafList &CVoxelTree::LeafList() 
+{ 
+	return m_aLeafList; 
+}
+
+inline int CVoxelTree::GetTreeId() const
+{
+	return m_TreeId;
+}
+
+inline CPartitionVisits *CVoxelTree::GetVisits()
+{
+	return m_pVisits;
+}
+
+inline CPartitionVisits *CVoxelTree::BeginVisit()
+{
+	CPartitionVisits *pPrev = m_pVisits;
+	CPartitionVisits *pVisits = m_FreeVisits.GetObject();
+	pVisits->Resize( m_nNextVisitBit, true );
+	m_pVisits = pVisits;
+	return pPrev;
+}
+
+inline void CVoxelTree::EndVisit( CPartitionVisits *pPrev )
+{
+	m_FreeVisits.PutObject( m_pVisits );
+	m_pVisits = pPrev;
+}
+
+inline CVoxelTree *CSpatialPartition::VoxelTree( SpatialPartitionListMask_t listMask )
+{
+	int iTree = ( ( listMask & PARTITION_ALL_CLIENT_EDICTS ) == 0 ) ? SERVER_TREE : CLIENT_TREE;
+	return &m_VoxelTrees[iTree];
+}
+
+inline CVoxelTree *CSpatialPartition::VoxelTreeForHandle( SpatialPartitionHandle_t handle )
+{
+	return VoxelTree( m_aHandles[handle].m_fList );
+}
+
+
+	
+//-----------------------------------------------------------------------------
+// Constructor, destructor
+//-----------------------------------------------------------------------------
+CVoxelHash::CVoxelHash( )
+{
+}
+
+CVoxelHash::~CVoxelHash()
+{
+	Shutdown();
+}
+
+
+//-----------------------------------------------------------------------------
+// Purpose: Create a voxel index from a world point - is the hash key.
+//   Input: vecWorldPoint - world point to get voxel index for
+//  Output: voxel index
+//-----------------------------------------------------------------------------
+inline void CVoxelHash::VoxelIndexFromPoint( const Vector &vecWorldPoint, int pPoint[3] )
+{
+	pPoint[0] = static_cast<int>( vecWorldPoint.x - m_vecVoxelOrigin.x ) >> ( SPHASH_VOXEL_SHIFT + SPHASH_LEVEL_SKIP * m_nLevel );
+	pPoint[1] = static_cast<int>( vecWorldPoint.y - m_vecVoxelOrigin.y ) >> ( SPHASH_VOXEL_SHIFT + SPHASH_LEVEL_SKIP * m_nLevel );
+	pPoint[2] = static_cast<int>( vecWorldPoint.z - m_vecVoxelOrigin.z ) >> ( SPHASH_VOXEL_SHIFT + SPHASH_LEVEL_SKIP * m_nLevel );
+}
+
+inline void CVoxelHash::PackVoxel( int iX, int iY, int iZ, Voxel_t &voxel )
+{
+	Assert( ( iX >= -( 1 << 10 ) ) && ( iX <= ( 1 << 10 ) ) );
+	Assert( ( iY >= -( 1 << 10 ) ) && ( iY <= ( 1 << 10 ) ) );
+	Assert( ( iZ >= -( 1 << 9 ) ) && ( iZ <= ( 1 << 9 ) ) );
+	voxel.bitsVoxel.x = iX;
+	voxel.bitsVoxel.y = iY;
+	voxel.bitsVoxel.z = iZ;
+}
+
+inline Voxel_t CVoxelHash::VoxelIndexFromPoint( const Vector &vecWorldPoint )
+{
+	Voxel_t voxel;
+
+	voxel.bitsVoxel.x = static_cast<int>( vecWorldPoint.x - m_vecVoxelOrigin.x ) >> ( SPHASH_VOXEL_SHIFT + SPHASH_LEVEL_SKIP * m_nLevel );
+	voxel.bitsVoxel.y = static_cast<int>( vecWorldPoint.y - m_vecVoxelOrigin.y ) >> ( SPHASH_VOXEL_SHIFT + SPHASH_LEVEL_SKIP * m_nLevel );
+	voxel.bitsVoxel.z = static_cast<int>( vecWorldPoint.z - m_vecVoxelOrigin.z ) >> ( SPHASH_VOXEL_SHIFT + SPHASH_LEVEL_SKIP * m_nLevel );
+
+	return voxel;
+}
+
+
+//-----------------------------------------------------------------------------
+// Purpose:	Computes the voxel count at a particular level of the tree
+//-----------------------------------------------------------------------------
+int CVoxelHash::ComputeVoxelCountAtLevel( int nLevel )
+{
+	int nVoxelCount = COORD_EXTENT >> SPHASH_VOXEL_SHIFT;
+	nVoxelCount >>= ( SPHASH_LEVEL_SKIP * nLevel ); 
+	return ( nVoxelCount > 0 ) ? nVoxelCount : 1;
+}
+
+
+//-----------------------------------------------------------------------------
+// Gets the voxel size for this hash
+//-----------------------------------------------------------------------------
+inline int CVoxelHash::VoxelSize( ) const
+{
+	return SPHASH_VOXEL_SIZE << ( SPHASH_LEVEL_SKIP * m_nLevel );
+}
+
+
+//-----------------------------------------------------------------------------
+// Purpose:
+//   Input: worldmin - 
+//          worldmax - 
+//-----------------------------------------------------------------------------
+void CVoxelHash::Init( CVoxelTree *pPartition, const Vector &worldmin, const Vector &worldmax, int nLevel )
+{
+	m_pTree = pPartition;
+	m_nLevel = nLevel;
+
+	// Setup the hash.
+	MEM_ALLOC_CREDIT();
+
+	int nVoxelCount = ComputeVoxelCountAtLevel( nLevel );
+	m_vecVoxelOrigin.Init( MIN_COORD_FLOAT, MIN_COORD_FLOAT, MIN_COORD_FLOAT );
+	int nHashBucketCount = SPHASH_BUCKET_COUNT >> nLevel;
+	if ( nHashBucketCount < 16 )
+	{
+		nHashBucketCount = 16;
+	}
+	m_nVoxelDelta[0] = nVoxelCount;
+	m_nVoxelDelta[1] = nVoxelCount;
+	m_nVoxelDelta[2] = nVoxelCount;
+	Assert( ( m_nVoxelDelta[0] >= 0 ) && ( m_nVoxelDelta[0] <= ( 1 << 10 ) ) );
+	Assert( ( m_nVoxelDelta[1] >= 0 ) && ( m_nVoxelDelta[1] <= ( 1 << 10 ) ) );
+	Assert( ( m_nVoxelDelta[2] >= 0 ) && ( m_nVoxelDelta[2] <= ( 1 << 9 ) ) );
+
+	m_aVoxelHash.RemoveAll();
+
+	// Setup the entity list pool.
+	int nGrowSize = SPHASH_ENTITYLIST_BLOCK >> nLevel;
+	if ( nGrowSize < 16 )
+	{
+		nGrowSize = 16;
+	}
+	m_aEntityList.Purge();
+	m_aEntityList.SetGrowSize( nGrowSize );
+}
+
+
+//-----------------------------------------------------------------------------
+// Shutdown
+//-----------------------------------------------------------------------------
+void CVoxelHash::Shutdown( void )
+{
+	m_aEntityList.Purge();
+	m_aVoxelHash.Purge();
+}
+
+
+//-----------------------------------------------------------------------------
+// Purpose: Insert the object into the voxel hash.
+//-----------------------------------------------------------------------------
+void CVoxelHash::InsertIntoTree( SpatialPartitionHandle_t hPartition, const Vector &vecMin, const Vector &vecMax )
+{
+	EntityInfo_t &info = m_pTree->EntityInfo( hPartition );
+	CLeafList &leafList = m_pTree->LeafList();
+	int treeId = m_pTree->GetTreeId();
+
+	// Set the entity bounding box.
+	info.m_vecMin = vecMin;
+	info.m_vecMax = vecMax;
+
+	// Set the voxel level
+	info.m_nLevel[m_pTree->GetTreeId()] = m_nLevel;
+
+	// Add the object to the tree.
+	Voxel_t voxelMin, voxelMax;
+	voxelMin = VoxelIndexFromPoint( vecMin );
+	voxelMax = VoxelIndexFromPoint( vecMax );
+	Assert( (m_nLevel == 4) ||
+			( (voxelMax.bitsVoxel.x - voxelMin.bitsVoxel.x <= 1) && 
+			(voxelMax.bitsVoxel.y - voxelMin.bitsVoxel.y <= 1) && 
+			(voxelMax.bitsVoxel.z - voxelMin.bitsVoxel.z <= 1) ) );
+
+	// Add the object to all the voxels it intersects.
+	Voxel_t voxel;
+	unsigned int iX, iY, iZ;
+	for ( iX = voxelMin.bitsVoxel.x; iX <= voxelMax.bitsVoxel.x; ++iX )
+	{
+		voxel.bitsVoxel.x = iX;
+		for ( iY = voxelMin.bitsVoxel.y; iY <= voxelMax.bitsVoxel.y; ++iY )
+		{
+			voxel.bitsVoxel.y = iY;
+			for ( iZ = voxelMin.bitsVoxel.z; iZ <= voxelMax.bitsVoxel.z; ++iZ )
+			{
+				voxel.bitsVoxel.z = iZ;
+
+#if 0
+				// Debug!
+				RenderVoxel( voxel );
+#endif
+
+				// Entity list.
+				int iEntity = m_aEntityList.Alloc( true );
+				m_aEntityList[iEntity] = hPartition;
+				
+				UtlHashFastHandle_t hHash = m_aVoxelHash.Find( voxel.uiVoxel );
+				if ( hHash == m_aVoxelHash.InvalidHandle() )
+				{
+					// Add voxel(leaf) to hash.
+					hHash = m_aVoxelHash.FastInsert( voxel.uiVoxel, iEntity );
+				}
+				else
+				{
+					int iHead = m_aVoxelHash.Element( hHash );
+					m_aEntityList.LinkBefore( iHead, iEntity );
+					m_aVoxelHash[hHash] = iEntity;
+				}
+				
+				// Leaf list.
+				int iLeafList = leafList.Alloc( true );
+				leafList[iLeafList].m_hVoxel = hHash;
+				leafList[iLeafList].m_iEntity = iEntity;
+				
+				if ( info.m_iLeafList[treeId] == leafList.InvalidIndex() )
+				{
+					info.m_iLeafList[treeId] = iLeafList;
+				}
+				else
+				{
+					int iHead = info.m_iLeafList[treeId];
+					leafList.LinkBefore( iHead, iLeafList );
+					info.m_iLeafList[treeId] = iLeafList;
+				}
+			}
+		}
+	}
+}
+
+
+//-----------------------------------------------------------------------------
+// Purpose: Removes the object into the voxel hash.
+//-----------------------------------------------------------------------------
+void CVoxelHash::RemoveFromTree( SpatialPartitionHandle_t hPartition )
+{
+	EntityInfo_t &data = m_pTree->EntityInfo( hPartition );
+	CLeafList &leafList = m_pTree->LeafList();
+	int treeId = m_pTree->GetTreeId();
+
+	int iLeaf = data.m_iLeafList[treeId];
+	int iNext;
+	while ( iLeaf != leafList.InvalidIndex() )
+	{
+		// Get the next voxel - if any.
+		iNext = leafList.Next( iLeaf );
+
+		UtlHashFastHandle_t hHash = leafList[iLeaf].m_hVoxel;
+		if ( hHash == m_aVoxelHash.InvalidHandle() )
+		{
+			iLeaf = iNext;
+			continue;
+		}
+
+		// Get the head of the entity list for the voxel.
+		int iEntity = leafList[iLeaf].m_iEntity;
+		int iEntityHead = m_aVoxelHash[hHash];
+
+		if ( iEntityHead == iEntity )
+		{
+			int iEntityNext = m_aEntityList.Next( iEntityHead );
+			if ( iEntityNext == m_aEntityList.InvalidIndex() )
+			{
+				m_aVoxelHash.Remove( hHash );
+			}
+			else
+			{
+				m_aVoxelHash[hHash] = iEntityNext;
+			}
+		}
+		
+		// Remove the entity from the entity list for the voxel.
+		m_aEntityList.Remove( iEntity );
+
+		// Remove from the leaf list.
+		leafList.Remove( iLeaf );		
+		iLeaf = iNext;
+	}
+	
+	data.m_iLeafList[treeId] = leafList.InvalidIndex();
+}
+
+
+//-----------------------------------------------------------------------------
+// Purpose:
+//-----------------------------------------------------------------------------
+inline void ClampStartPoint( Ray_t &ray, const Vector &vecEnd )
+{
+	float flDistStart, flT;
+	for ( int iAxis = 0; iAxis < 3; ++iAxis )
+	{
+		if ( fabs(ray.m_Delta[iAxis]) < 1e-10 )
+			continue;
+
+		if ( ray.m_Delta[iAxis] > 0.0f )
+		{
+			if ( ray.m_Start[iAxis] < MIN_COORD_FLOAT )
+			{
+				// Add some bloat inward.
+				flDistStart = ( MIN_COORD_FLOAT + 5.0f ) - ray.m_Start[iAxis];
+				flT = flDistStart / ray.m_Delta[iAxis];
+				VectorMA( ray.m_Start, flT, ray.m_Delta, ray.m_Start );
+			}
+		}
+		else
+		{
+			if ( ray.m_Start[iAxis] > MAX_COORD_FLOAT )
+			{
+				// Add some bloat inward.
+				flDistStart = ray.m_Start[iAxis] - ( MAX_COORD_FLOAT - 5.0f );
+				flT = flDistStart / -ray.m_Delta[iAxis];
+				VectorMA( ray.m_Start, flT, ray.m_Delta, ray.m_Start );
+			}
+		}
+	}
+
+	VectorSubtract( vecEnd, ray.m_Start, ray.m_Delta );
+}
+
+
+//-----------------------------------------------------------------------------
+// Purpose:
+//-----------------------------------------------------------------------------
+inline void ClampEndPoint( Ray_t &ray, Vector &vecEnd )
+{
+	float flDistStart, flT;
+	for ( int iAxis = 0; iAxis < 3; ++iAxis )
+	{
+		if ( fabs(ray.m_Delta[iAxis]) < 1e-10 )
+			continue;
+
+		if ( ray.m_Delta[iAxis] < 0.0f )
+		{
+			if ( vecEnd[iAxis] < MIN_COORD_FLOAT )
+			{
+				// Add some bloat inward.
+				flDistStart = ray.m_Start[iAxis] - ( MIN_COORD_FLOAT + 5.0f );
+				flT = flDistStart / -ray.m_Delta[iAxis];
+				VectorMA( ray.m_Start, flT, ray.m_Delta, vecEnd );
+			}
+		}
+		else
+		{
+			if ( vecEnd[iAxis] > MAX_COORD_FLOAT )
+			{
+				// Add some bloat inward.
+				flDistStart = ray.m_Start[iAxis] - ( -MAX_COORD_FLOAT + 5.0f );
+				flT = flDistStart / ray.m_Delta[iAxis];
+				VectorMA( ray.m_Start, flT, ray.m_Delta, vecEnd );
+			}
+		}
+	}
+
+	VectorSubtract( vecEnd, ray.m_Start, ray.m_Delta );
+}
+
+
+//-----------------------------------------------------------------------------
+// Intersection classes
+//-----------------------------------------------------------------------------
+class CPartitionVisitor
+{
+public:
+	CPartitionVisitor( CVoxelTree *pPartition )
+	{
+		m_pVisits = pPartition->GetVisits();
+		m_iTree = pPartition->GetTreeId();
+	}
+
+	~CPartitionVisitor()
+	{
+	}
+
+	bool Visit( SpatialPartitionHandle_t hPartition, EntityInfo_t &hInfo ) const
+	{
+		int nVisitBit = hInfo.m_nVisitBit[m_iTree];
+		if ( m_pVisits->IsBitSet( nVisitBit ) )
+		{
+			return false;
+		}
+
+		m_pVisits->Set( nVisitBit );
+		return true;
+	}
+
+private:
+	CPartitionVisits *m_pVisits;
+	int m_iTree;
+};
+
+
+class CIntersectPoint : public CPartitionVisitor
+{
+public:
+	CIntersectPoint( CVoxelTree *pPartition, const Vector &pt ) : CPartitionVisitor( pPartition ), m_vecPoint( pt )
+	{
+	}
+
+	bool Intersects( const Vector &vecMins, const Vector &vecMaxs ) const
+	{
+		// Ray intersection test
+		Assert( vecMins.x <= vecMaxs.x );
+		Assert( vecMins.y <= vecMaxs.y );
+		Assert( vecMins.z <= vecMaxs.z );
+
+		// Does the ray intersect the box?
+		return IsPointInBox( m_vecPoint, vecMins, vecMaxs );
+	}
+	 
+private:
+	const Vector &m_vecPoint;
+};
+
+
+class CIntersectBox : public CPartitionVisitor
+{
+public:
+	CIntersectBox( CVoxelTree *pPartition, const Vector &vecMins, const Vector &vecMaxs ) : CPartitionVisitor( pPartition ), m_vecMins( vecMins ), m_vecMaxs( vecMaxs )
+	{
+	}
+
+	bool Intersects( const Vector &vecMins, const Vector &vecMaxs ) const
+	{
+		// Box intersection test
+		Assert( vecMins.x <= vecMaxs.x );
+		Assert( vecMins.y <= vecMaxs.y );
+		Assert( vecMins.z <= vecMaxs.z );
+
+		return ( vecMins.x <= m_vecMaxs.x ) && ( vecMaxs.x >= m_vecMins.x ) &&
+				( vecMins.y <= m_vecMaxs.y ) && ( vecMaxs.y >= m_vecMins.y ) &&
+				( vecMins.z <= m_vecMaxs.z ) && ( vecMaxs.z >= m_vecMins.z );
+	}
+	 
+private:
+	const Vector &m_vecMins;
+	const Vector &m_vecMaxs;
+};
+
+class CIntersectRay : public CPartitionVisitor
+{
+public:
+	CIntersectRay( CVoxelTree *pPartition, const Ray_t &ray, const Vector &vecInvDelta ) : CPartitionVisitor( pPartition ), m_Ray( ray ), m_vecInvDelta( vecInvDelta )
+	{
+	}
+
+	bool Intersects( const Vector &vecMins, const Vector &vecMaxs ) const
+	{
+		// Ray intersection test
+		Assert( vecMins.x <= vecMaxs.x );
+		Assert( vecMins.y <= vecMaxs.y );
+		Assert( vecMins.z <= vecMaxs.z );
+
+		// Does the ray intersect the box?
+		return IsBoxIntersectingRay( vecMins, vecMaxs, m_Ray.m_Start, m_Ray.m_Delta, m_vecInvDelta );
+	}
+	 
+private:
+	const Ray_t &m_Ray;
+	const Vector &m_vecInvDelta;
+};
+
+
+class CIntersectSweptBox : public CPartitionVisitor
+{
+public:
+	CIntersectSweptBox( CVoxelTree *pPartition, const Ray_t &ray, const Vector &vecInvDelta ) : CPartitionVisitor( pPartition ), m_Ray( ray ), m_vecInvDelta( vecInvDelta )
+	{
+	}
+
+	bool Intersects( const Vector &vecMins, const Vector &vecMaxs ) const
+	{
+		// Swept box intersection test
+		Assert( vecMins.x <= vecMaxs.x );
+		Assert( vecMins.y <= vecMaxs.y );
+		Assert( vecMins.z <= vecMaxs.z );
+
+		Vector vecTestMin, vecTestMax;
+		VectorSubtract( vecMins, m_Ray.m_Extents, vecTestMin );
+		VectorAdd( vecMaxs, m_Ray.m_Extents, vecTestMax );
+
+		// Does the ray intersect the box?
+		return IsBoxIntersectingRay( vecTestMin, vecTestMax, m_Ray.m_Start, m_Ray.m_Delta, m_vecInvDelta );
+	}
+	 
+private:
+	const Ray_t &m_Ray;
+	const Vector &m_vecInvDelta;
+};
+
+
+//-----------------------------------------------------------------------------
+// Purpose:
+//-----------------------------------------------------------------------------
+template <class T> 
+bool CVoxelHash::EnumerateElementsInVoxel( Voxel_t voxel, const T &intersectTest, SpatialPartitionListMask_t listMask, IPartitionEnumerator* pIterator )
+{
+	// If the voxel doesn't exist, nothing to iterate over
+	UtlHashFastHandle_t hHash = m_aVoxelHash.Find( voxel.uiVoxel );
+	if ( hHash == m_aVoxelHash.InvalidHandle() )
+		return true;
+
+	SpatialPartitionHandle_t hPartition;
+	for ( int i = m_aVoxelHash.Element( hHash ); i != m_aEntityList.InvalidIndex(); i = m_aEntityList.Next(i) )
+	{
+		hPartition = m_aEntityList[i];
+		if ( hPartition == PARTITION_INVALID_HANDLE )
+			continue;
+
+		EntityInfo_t &hInfo = m_pTree->EntityInfo( hPartition );
+
+		// Keep going if this dude isn't in the list
+		if ( !( listMask & hInfo.m_fList ) )
+			continue;
+
+		if ( hInfo.m_flags & ENTITY_HIDDEN )
+			continue;
+
+		// Has this handle already been visited?
+		if ( !intersectTest.Visit( hPartition, hInfo ) )
+			continue;
+
+		// Intersection test
+		if ( !intersectTest.Intersects( hInfo.m_vecMin, hInfo.m_vecMax ) )
+			continue;
+
+		// Okay, this one is good...
+		if ( pIterator->EnumElement( hInfo.m_pHandleEntity ) == ITERATION_STOP )
+			return false;
+	}
+
+	return true;
+}
+
+
+//-----------------------------------------------------------------------------
+// Enumeration method when only 1 voxel is ever visited
+//-----------------------------------------------------------------------------
+template <class T> 
+bool CVoxelHash::EnumerateElementsInSingleVoxel( Voxel_t voxel, const T &intersectTest, 
+	SpatialPartitionListMask_t listMask, IPartitionEnumerator* pIterator )
+{
+	// NOTE: We don't have to do the enum id checking, nor do we have to up the
+	// nesting level, since this only visits 1 voxel.
+	int iEntityList;
+	UtlHashFastHandle_t hHash = m_aVoxelHash.Find( voxel.uiVoxel );
+	if ( hHash != m_aVoxelHash.InvalidHandle() )
+	{
+		iEntityList = m_aVoxelHash.Element( hHash );
+		while ( iEntityList != m_aEntityList.InvalidIndex() )
+		{
+			SpatialPartitionHandle_t hPartition = m_aEntityList[iEntityList];
+			iEntityList = m_aEntityList.Next( iEntityList );
+			if ( hPartition == PARTITION_INVALID_HANDLE )
+				continue;
+
+			EntityInfo_t &hInfo = m_pTree->EntityInfo( hPartition );
+
+			// Keep going if this dude isn't in the list
+			if ( !( listMask & hInfo.m_fList ) )
+				continue;
+
+			if ( hInfo.m_flags & ENTITY_HIDDEN )
+				continue;
+
+			// Keep going if there's no collision
+			if ( !intersectTest.Intersects( hInfo.m_vecMin, hInfo.m_vecMax ) )
+				continue;
+
+			// Okay, this one is good...
+			if ( pIterator->EnumElement( hInfo.m_pHandleEntity ) == ITERATION_STOP )
+				return false;
+		}
+	}
+	return true;
+}
+
+	
+//-----------------------------------------------------------------------------
+// Purpose:
+//-----------------------------------------------------------------------------
+bool CVoxelHash::EnumerateElementsInBox( SpatialPartitionListMask_t listMask, 
+	Voxel_t vmin, Voxel_t vmax, const Vector& mins, const Vector& maxs, IPartitionEnumerator* pIterator )
+{
+	VPROF( "BoxTest/SphereTest" );
+
+	Assert( mins.x <= maxs.x );
+	Assert( mins.y <= maxs.y );
+	Assert( mins.z <= maxs.z );
+	
+	// Create the intersection object
+	bool bSingleVoxel = ( vmin.uiVoxel == vmax.uiVoxel );
+	CIntersectBox rect( m_pTree, mins, maxs );
+
+	// In the same voxel
+	if ( bSingleVoxel )
+		return EnumerateElementsInSingleVoxel( vmin, rect, listMask, pIterator );
+
+	// Iterate over all voxels
+	Voxel_t vdelta;
+	vdelta.uiVoxel = vmax.uiVoxel - vmin.uiVoxel;
+	int cx = vdelta.bitsVoxel.x;
+	int cy = vdelta.bitsVoxel.y;
+	int cz = vdelta.bitsVoxel.z;
+
+	Voxel_t voxel;
+	voxel.bitsVoxel.x = vmin.bitsVoxel.x;
+	for ( int iX = 0; iX <= cx; ++iX, ++voxel.bitsVoxel.x )
+	{
+		voxel.bitsVoxel.y = vmin.bitsVoxel.y;
+		for ( int iY = 0; iY <= cy; ++iY, ++voxel.bitsVoxel.y )
+		{
+			voxel.bitsVoxel.z = vmin.bitsVoxel.z;
+			for ( int iZ = 0; iZ <= cz; ++iZ, ++voxel.bitsVoxel.z )
+			{
+				if ( !EnumerateElementsInVoxel( voxel, rect, listMask, pIterator ) )
+					return false;
+			}
+		}
+	}
+	return true;
+}
+
+
+//-----------------------------------------------------------------------------
+// Purpose:
+//-----------------------------------------------------------------------------
+bool CVoxelHash::EnumerateElementsAlongRay( SpatialPartitionListMask_t listMask, 
+	const Ray_t &ray, const Vector &vecInvDelta, const Vector &vecEnd, IPartitionEnumerator *pIterator )
+{
+	Assert( ray.m_IsSwept );
+
+	// Two different methods
+	if ( ray.m_IsRay )
+		return EnumerateElementsAlongRay_Ray( listMask, ray, vecInvDelta, vecEnd, pIterator );
+	return EnumerateElementsAlongRay_ExtrudedRay( listMask, ray, vecInvDelta, vecEnd, pIterator );
+}
+
+
+//-----------------------------------------------------------------------------
+// Purpose:
+//-----------------------------------------------------------------------------
+bool CVoxelHash::EnumerateElementsAlongRay_Ray( SpatialPartitionListMask_t listMask, 
+	const Ray_t &ray, const Vector &vecInvDelta, const Vector &vecEnd, IPartitionEnumerator *pIterator )
+{
+#ifdef _DEBUG
+	// For drawing debug objects.
+	static int nRenderRayEnumId = 4;
+#endif
+	
+	// Find the voxel start + end
+	Voxel_t voxelStart = VoxelIndexFromPoint( ray.m_Start );
+	Voxel_t voxelEnd = VoxelIndexFromPoint( vecEnd );
+
+	bool bSingleVoxel = ( voxelStart.uiVoxel == voxelEnd.uiVoxel );
+	CIntersectRay intersectRay( m_pTree, ray, vecInvDelta );
+
+	// Optimization: Look for single voxel rays
+	if ( bSingleVoxel )
+		return EnumerateElementsInSingleVoxel( voxelStart, intersectRay, listMask, pIterator );
+
+	Voxel_t voxelCurrent;
+	voxelCurrent.uiVoxel = voxelStart.uiVoxel;
+	
+	// Setup.
+	int nStep[3];
+	float tMax[3];
+	float tDelta[3];
+	LeafListRaySetup( ray, vecEnd, vecInvDelta, voxelStart, nStep, tMax, tDelta );
+
+	// Walk the voxels and visit all elements in each voxel
+	while ( 1 )
+	{
+		if ( !EnumerateElementsInVoxel( voxelCurrent, intersectRay, listMask, pIterator ) )
+			return false;
+
+		if ( tMax[0] >= 1.0f && tMax[1] >= 1.0f && tMax[2] >= 1.0f )
+			break;
+		
+		if ( tMax[0] < tMax[1] )
+		{
+			if ( tMax[0] < tMax[2] )
+			{
+				voxelCurrent.bitsVoxel.x += nStep[0];
+				tMax[0] += tDelta[0];
+			}
+			else
+			{
+				voxelCurrent.bitsVoxel.z += nStep[2];
+				tMax[2] += tDelta[2];
+			}
+		}
+		else
+		{
+			if ( tMax[1] < tMax[2] )
+			{
+				voxelCurrent.bitsVoxel.y += nStep[1];
+				tMax[1] += tDelta[1];
+			}
+			else
+			{
+				voxelCurrent.bitsVoxel.z += nStep[2];
+				tMax[2] += tDelta[2];
+			}
+		}
+	}
+
+	return true;
+}
+
+
+//-----------------------------------------------------------------------------
+// Purpose:
+//-----------------------------------------------------------------------------
+void CVoxelHash::LeafListRaySetup( const Ray_t &ray, const Vector &vecEnd, 
+	const Vector &vecInvDelta, Voxel_t voxel, int *pStep, float *pMax, float *pDelta )
+{
+	int iVoxel[3];
+	iVoxel[0] = voxel.bitsVoxel.x;
+	iVoxel[1] = voxel.bitsVoxel.y;
+	iVoxel[2] = voxel.bitsVoxel.z;
+
+	// Setup.
+	float flDist, flDistStart, flDistEnd, flRecipDist;
+	Vector vecVoxelStart, vecVoxelEnd;
+	VectorSubtract( ray.m_Start, m_vecVoxelOrigin, vecVoxelStart );
+	VectorSubtract( vecEnd, m_vecVoxelOrigin, vecVoxelEnd );
+
+	for ( int iAxis = 0; iAxis < 3; ++iAxis )
+	{
+		if ( vecVoxelStart[iAxis] == vecVoxelEnd[iAxis] )
+		{
+			pStep[iAxis] = 0;
+			pMax[iAxis] = SPHASH_VOXEL_LARGE;
+			pDelta[iAxis] = SPHASH_VOXEL_LARGE;
+			continue;
+		}
+
+		if ( ray.m_Delta[iAxis] < 0.0f )
+		{
+			pStep[iAxis] = -1;
+			flDist = ( iVoxel[iAxis] ) * VoxelSize();
+			flDistStart = vecVoxelStart[iAxis] - flDist;
+			flDistEnd = vecVoxelEnd[iAxis] - flDist;
+			flRecipDist = -vecInvDelta[iAxis];
+		}
+		else
+		{
+			pStep[iAxis] = 1;
+			flDist = ( iVoxel[iAxis] + 1 ) * -VoxelSize();
+			flDistStart = -vecVoxelStart[iAxis] - flDist;
+			flDistEnd = -vecVoxelEnd[iAxis] - flDist;
+			flRecipDist = vecInvDelta[iAxis];
+		}
+
+		if ( ( flDistStart > 0.0f ) && ( flDistEnd > 0.0f ) )
+		{
+			pMax[iAxis] = SPHASH_VOXEL_LARGE;
+			pDelta[iAxis] = SPHASH_VOXEL_LARGE;
+		}
+		else
+		{
+			pMax[iAxis] = flDistStart * flRecipDist;
+			pDelta[iAxis] = VoxelSize() * flRecipDist;
+		}
+	}
+}
+
+
+//-----------------------------------------------------------------------------
+// Computes the min index of 3 numbers
+//-----------------------------------------------------------------------------
+inline int MinIndex( float v1, float v2, float v3 )
+{
+	if ( v1 < v2 )
+		return ( v1 < v3 ) ? 0 : 2;
+	return ( v2 < v3 ) ? 1 : 2;
+}
+
+
+//-----------------------------------------------------------------------------
+// Purpose:
+//-----------------------------------------------------------------------------
+bool CVoxelHash::EnumerateElementsAlongRay_ExtrudedRay( SpatialPartitionListMask_t listMask, 
+	const Ray_t &ray, const Vector &vecInvDelta, const Vector &vecEnd, IPartitionEnumerator *pIterator )
+{
+	// Check the starting position, then proceed with the sweep.
+	Vector vecMin, vecMax;
+	VectorSubtract( ray.m_Start, ray.m_Extents, vecMin );
+	VectorAdd( ray.m_Start, ray.m_Extents, vecMax );
+
+	// Visit each voxel in the box and enumerate its elements.
+	int voxelMin[3], voxelMax[3];
+	VoxelIndexFromPoint( vecMin, voxelMin );
+	VoxelIndexFromPoint( vecMax, voxelMax );
+
+	CIntersectSweptBox intersectSweptBox( m_pTree, ray, vecInvDelta );
+
+	// Iterate over all voxels that intersect the box around the starting ray point
+	Voxel_t voxel;
+	int iX, iY, iZ;
+	for ( iX = voxelMin[0]; iX <= voxelMax[0]; ++iX )
+	{
+		voxel.bitsVoxel.x = iX;
+		for ( iY = voxelMin[1]; iY <= voxelMax[1]; ++iY )
+		{
+			voxel.bitsVoxel.y = iY;
+			for ( iZ = voxelMin[2]; iZ <= voxelMax[2]; ++iZ )
+			{
+				voxel.bitsVoxel.z = iZ;
+				if ( !EnumerateElementsInVoxel( voxel, intersectSweptBox, listMask, pIterator ) )
+					return false;
+			}
+		}
+	}
+
+	// Early out: Check to see if the range of voxels at the endpoint
+	// is the same as the range at the start point. If so, we're done.
+	Vector vecEndMin, vecEndMax;
+	VectorSubtract( vecEnd, ray.m_Extents, vecEndMin );
+	VectorAdd( vecEnd, ray.m_Extents, vecEndMax );
+
+	int endVoxelMin[3], endVoxelMax[3];
+	VoxelIndexFromPoint( vecEndMin, endVoxelMin );
+	VoxelIndexFromPoint( vecEndMax, endVoxelMax );
+	if ( (endVoxelMin[0] >= voxelMin[0]) && (endVoxelMin[1] >= voxelMin[1]) && (endVoxelMin[2] >= voxelMin[2]) &&
+		 (endVoxelMax[0] <= voxelMax[0]) && (endVoxelMax[1] <= voxelMax[1]) && (endVoxelMax[2] <= voxelMax[2]) )
+		 return true;
+	 
+	// Setup.
+	int nStep[3];
+	float tMax[3];	// amount of change in t along ray until we hit the next new voxel
+	float tMin[3];	// amount of change in t along ray until we leave the last voxel
+	float tDelta[3];
+	LeafListExtrudedRaySetup( ray, vecInvDelta, vecMin, vecMax, voxelMin, voxelMax, nStep, tMin, tMax, tDelta );
+
+	// Walk the voxels and create the leaf list.
+	int iAxis, iMinAxis;
+	while ( tMax[0] < 1.0f || tMax[1] < 1.0f || tMax[2] < 1.0f )
+	{
+		iAxis = MinIndex( tMax[0], tMax[1], tMax[2] );
+		iMinAxis = MinIndex( tMin[0], tMin[1], tMin[2] );
+
+		if ( tMin[iMinAxis] < tMax[iAxis] )
+		{
+			tMin[iMinAxis] += tDelta[iMinAxis];
+			if ( nStep[iMinAxis] > 0 )
+			{
+				voxelMin[iMinAxis] += nStep[iMinAxis];
+			}
+			else
+			{
+				voxelMax[iMinAxis] += nStep[iMinAxis];
+			}
+		}
+		else
+		{
+			tMax[iAxis] += tDelta[iAxis];
+			if ( nStep[iAxis] > 0 )
+			{
+				voxelMax[iAxis] += nStep[iAxis];
+			}
+			else
+			{
+				voxelMin[iAxis] += nStep[iAxis];
+			}
+			
+			if ( !EnumerateElementsAlongRay_ExtrudedRaySlice( listMask, pIterator, intersectSweptBox, voxelMin, voxelMax, iAxis, nStep ) )
+				return false;
+		}
+	}
+	return true;
+}
+
+
+//-----------------------------------------------------------------------------
+// Purpose:
+//-----------------------------------------------------------------------------
+void CVoxelHash::LeafListExtrudedRaySetup( const Ray_t &ray, const Vector &vecInvDelta,
+											const Vector &vecMin, const Vector &vecMax,
+											int iVoxelMin[3], int iVoxelMax[3],													 
+											int *pStep, float *pMin, float *pMax, float *pDelta )
+{
+	float flDist, flDistStart, flRecipDist, flDistMinStart;
+
+	Vector vecVoxelMin, vecVoxelMax;
+	VectorSubtract( vecMin, m_vecVoxelOrigin, vecVoxelMin );
+	VectorSubtract( vecMax, m_vecVoxelOrigin, vecVoxelMax );
+
+	for ( int iAxis = 0; iAxis < 3; ++iAxis )
+	{
+		if ( ray.m_Delta[iAxis] == 0.0f )
+		{
+			pMax[iAxis] = SPHASH_VOXEL_LARGE;
+			pMin[iAxis] = SPHASH_VOXEL_LARGE;
+			pDelta[iAxis] = SPHASH_VOXEL_LARGE;
+			continue;
+		}
+
+		if ( ray.m_Delta[iAxis] < 0.0f )
+		{
+			pStep[iAxis] = -1;
+			flDistStart = vecVoxelMin[iAxis] - ( ( iVoxelMin[iAxis] ) * VoxelSize() );
+			flDistMinStart = vecVoxelMax[iAxis] - ( ( iVoxelMax[iAxis] ) * VoxelSize() );
+			flDist = -ray.m_Delta[iAxis];
+			flRecipDist = -vecInvDelta[iAxis];
+		}
+		else
+		{
+			pStep[iAxis] = 1;
+			flDistStart = -vecVoxelMax[iAxis] - ( ( iVoxelMax[iAxis] + 1 ) * -VoxelSize() );
+			flDistMinStart = -vecVoxelMin[iAxis] - ( ( iVoxelMin[iAxis] + 1 ) * -VoxelSize() );
+			flDist = ray.m_Delta[iAxis];
+			flRecipDist = vecInvDelta[iAxis];
+		}
+
+		if ( flDistStart > flDist )
+		{
+			pMax[iAxis] = SPHASH_VOXEL_LARGE;
+			pDelta[iAxis] = SPHASH_VOXEL_LARGE;
+		}
+		else
+		{
+			pMax[iAxis] = flDistStart * flRecipDist;
+			pDelta[iAxis] = VoxelSize() * flRecipDist;
+		}
+
+		if ( flDistMinStart > flDist )
+		{
+			pMin[iAxis] = SPHASH_VOXEL_LARGE;
+		}
+		else
+		{
+			pMin[iAxis] = flDistMinStart * flRecipDist;
+		}
+	}
+}
+
+
+//-----------------------------------------------------------------------------
+// Purpose:
+//-----------------------------------------------------------------------------
+bool CVoxelHash::EnumerateElementsAlongRay_ExtrudedRaySlice( SpatialPartitionListMask_t listMask,
+	IPartitionEnumerator *pIterator, const CIntersectSweptBox &intersectSweptBox,
+	int voxelMin[3], int voxelMax[3], int iAxis, int *pStep )
+{
+	int mins[3] = { voxelMin[0], voxelMin[1], voxelMin[2] };
+	int maxs[3] = { voxelMax[0], voxelMax[1], voxelMax[2] };
+	if ( pStep[iAxis] < 0.0f )
+	{
+		maxs[iAxis] = mins[iAxis];
+	}
+	else
+	{
+		mins[iAxis] = maxs[iAxis];
+	}
+
+	// Create leaf cache.
+	Voxel_t voxel;
+	int iX, iY, iZ;
+	for ( iX = mins[0]; iX <= maxs[0]; ++iX )
+	{
+		voxel.bitsVoxel.x = iX;
+		for ( iY = mins[1]; iY <= maxs[1]; ++iY )
+		{
+			voxel.bitsVoxel.y = iY;
+			for ( iZ = mins[2]; iZ <= maxs[2]; ++iZ )
+			{
+				voxel.bitsVoxel.z = iZ;
+				if ( !EnumerateElementsInVoxel( voxel, intersectSweptBox, listMask, pIterator ) )
+					return false;
+			}
+		}
+	}
+	return true;
+}
+
+
+//-----------------------------------------------------------------------------
+// Purpose:
+//-----------------------------------------------------------------------------
+bool CVoxelHash::EnumerateElementsAtPoint( SpatialPartitionListMask_t listMask,
+	Voxel_t v, const Vector& pt, IPartitionEnumerator* pIterator )
+{
+	// NOTE: We don't have to do the enum id checking, nor do we have to up the
+	// nesting level, since this only visits 1 voxel.
+	int iEntityList;
+	UtlHashFastHandle_t hHash = m_aVoxelHash.Find( v.uiVoxel );
+	if ( hHash != m_aVoxelHash.InvalidHandle() )
+	{
+		iEntityList = m_aVoxelHash.Element( hHash );
+		while ( iEntityList != m_aEntityList.InvalidIndex() )
+		{
+			SpatialPartitionHandle_t hPartition = m_aEntityList[iEntityList];
+			iEntityList = m_aEntityList.Next( iEntityList );
+			if ( hPartition == PARTITION_INVALID_HANDLE )
+				continue;
+
+			EntityInfo_t &hInfo = m_pTree->EntityInfo( hPartition );
+
+			// Keep going if this dude isn't in the list
+			if ( !( listMask & hInfo.m_fList ) )
+				continue;
+
+			if ( hInfo.m_flags & ENTITY_HIDDEN )
+				continue;
+
+			// Keep going if there's no collision
+			if ( !IsPointInBox( pt, hInfo.m_vecMin, hInfo.m_vecMax ) )
+				continue;
+
+			// Okay, this one is good...
+			if ( pIterator->EnumElement( hInfo.m_pHandleEntity ) == ITERATION_STOP )
+				return false;
+		}
+	}
+	return true;
+}
+
+
+//-----------------------------------------------------------------------------
+// Purpose: Debug! Render a voxel - blue.
+//-----------------------------------------------------------------------------
+void CVoxelHash::RenderVoxel( Voxel_t voxel, float flTime )
+{
+#ifndef SWDS
+	Vector vecMin, vecMax;
+	vecMin.x = ( voxel.bitsVoxel.x * VoxelSize() ) + m_vecVoxelOrigin.x;
+	vecMin.y = ( voxel.bitsVoxel.y * VoxelSize() ) + m_vecVoxelOrigin.y;
+	vecMin.z = ( voxel.bitsVoxel.z * VoxelSize() ) + m_vecVoxelOrigin.z;
+
+	vecMax.x = ( ( voxel.bitsVoxel.x + 1 ) * VoxelSize() ) + m_vecVoxelOrigin.x;
+	vecMax.y = ( ( voxel.bitsVoxel.y + 1 ) * VoxelSize() ) + m_vecVoxelOrigin.y;
+	vecMax.z = ( ( voxel.bitsVoxel.z + 1 ) * VoxelSize() ) + m_vecVoxelOrigin.z;
+
+	CDebugOverlay::AddBoxOverlay( vec3_origin, vecMin, vecMax, vec3_angle, s_pVoxelColor[m_nLevel][0], s_pVoxelColor[m_nLevel][1], s_pVoxelColor[m_nLevel][2], 30, flTime );
+
+	// Add outline.
+	Vector vecPoints[8];
+	vecPoints[0].Init( vecMin.x, vecMin.y, vecMin.z );
+	vecPoints[1].Init( vecMin.x, vecMax.y, vecMin.z );
+	vecPoints[2].Init( vecMax.x, vecMax.y, vecMin.z );
+	vecPoints[3].Init( vecMax.x, vecMin.y, vecMin.z );
+	vecPoints[4].Init( vecMin.x, vecMin.y, vecMax.z );
+	vecPoints[5].Init( vecMin.x, vecMax.y, vecMax.z );
+	vecPoints[6].Init( vecMax.x, vecMax.y, vecMax.z );
+	vecPoints[7].Init( vecMax.x, vecMin.y, vecMax.z );
+
+	CDebugOverlay::AddLineOverlay( vecPoints[0], vecPoints[1], s_pVoxelColor[m_nLevel][0], s_pVoxelColor[m_nLevel][1], s_pVoxelColor[m_nLevel][2], 255, true, flTime );
+	CDebugOverlay::AddLineOverlay( vecPoints[1], vecPoints[2], s_pVoxelColor[m_nLevel][0], s_pVoxelColor[m_nLevel][1], s_pVoxelColor[m_nLevel][2], 255, true, flTime );
+	CDebugOverlay::AddLineOverlay( vecPoints[2], vecPoints[3], s_pVoxelColor[m_nLevel][0], s_pVoxelColor[m_nLevel][1], s_pVoxelColor[m_nLevel][2], 255, true, flTime );
+	CDebugOverlay::AddLineOverlay( vecPoints[3], vecPoints[0], s_pVoxelColor[m_nLevel][0], s_pVoxelColor[m_nLevel][1], s_pVoxelColor[m_nLevel][2], 255, true, flTime );
+
+	CDebugOverlay::AddLineOverlay( vecPoints[4], vecPoints[5], s_pVoxelColor[m_nLevel][0], s_pVoxelColor[m_nLevel][1], s_pVoxelColor[m_nLevel][2], 255, true, flTime );
+	CDebugOverlay::AddLineOverlay( vecPoints[5], vecPoints[6], s_pVoxelColor[m_nLevel][0], s_pVoxelColor[m_nLevel][1], s_pVoxelColor[m_nLevel][2], 255, true, flTime );
+	CDebugOverlay::AddLineOverlay( vecPoints[6], vecPoints[7], s_pVoxelColor[m_nLevel][0], s_pVoxelColor[m_nLevel][1], s_pVoxelColor[m_nLevel][2], 255, true, flTime );
+	CDebugOverlay::AddLineOverlay( vecPoints[7], vecPoints[4], s_pVoxelColor[m_nLevel][0], s_pVoxelColor[m_nLevel][1], s_pVoxelColor[m_nLevel][2], 255, true, flTime );
+
+	CDebugOverlay::AddLineOverlay( vecPoints[0], vecPoints[4], s_pVoxelColor[m_nLevel][0], s_pVoxelColor[m_nLevel][1], s_pVoxelColor[m_nLevel][2], 255, true, flTime );
+	CDebugOverlay::AddLineOverlay( vecPoints[3], vecPoints[7], s_pVoxelColor[m_nLevel][0], s_pVoxelColor[m_nLevel][1], s_pVoxelColor[m_nLevel][2], 255, true, flTime );
+	CDebugOverlay::AddLineOverlay( vecPoints[1], vecPoints[5], s_pVoxelColor[m_nLevel][0], s_pVoxelColor[m_nLevel][1], s_pVoxelColor[m_nLevel][2], 255, true, flTime );
+	CDebugOverlay::AddLineOverlay( vecPoints[2], vecPoints[6], s_pVoxelColor[m_nLevel][0], s_pVoxelColor[m_nLevel][1], s_pVoxelColor[m_nLevel][2], 255, true, flTime );
+#endif
+}
+
+
+//-----------------------------------------------------------------------------
+// Purpose: Debug! Render an object in a voxel - green.
+//-----------------------------------------------------------------------------
+void CVoxelHash::RenderObjectInVoxel( SpatialPartitionHandle_t hPartition, CPartitionVisitor *pVisitor, float flTime )
+{
+#ifndef SWDS
+	// Add outline.
+	if ( hPartition == PARTITION_INVALID_HANDLE )
+		return;
+
+	EntityInfo_t &info = m_pTree->EntityInfo( hPartition );
+	if ( !pVisitor->Visit( hPartition, info ) )
+	{
+		return;
+	}
+
+	CDebugOverlay::AddBoxOverlay( vec3_origin, info.m_vecMin, info.m_vecMax, vec3_angle, s_pVoxelColor[m_nLevel][0], s_pVoxelColor[m_nLevel][1], s_pVoxelColor[m_nLevel][2], 75, flTime );
+
+	// Add outline.
+	Vector vecMin, vecMax;
+	vecMin = info.m_vecMin;
+	vecMax = info.m_vecMax;
+
+	Vector vecPoints[8];
+	vecPoints[0].Init( vecMin.x, vecMin.y, vecMin.z );
+	vecPoints[1].Init( vecMin.x, vecMax.y, vecMin.z );
+	vecPoints[2].Init( vecMax.x, vecMax.y, vecMin.z );
+	vecPoints[3].Init( vecMax.x, vecMin.y, vecMin.z );
+	vecPoints[4].Init( vecMin.x, vecMin.y, vecMax.z );
+	vecPoints[5].Init( vecMin.x, vecMax.y, vecMax.z );
+	vecPoints[6].Init( vecMax.x, vecMax.y, vecMax.z );
+	vecPoints[7].Init( vecMax.x, vecMin.y, vecMax.z );
+	
+	CDebugOverlay::AddLineOverlay( vecPoints[0], vecPoints[1], s_pVoxelColor[m_nLevel][0], s_pVoxelColor[m_nLevel][1], s_pVoxelColor[m_nLevel][2], 255, true, flTime );
+	CDebugOverlay::AddLineOverlay( vecPoints[1], vecPoints[2], s_pVoxelColor[m_nLevel][0], s_pVoxelColor[m_nLevel][1], s_pVoxelColor[m_nLevel][2], 255, true, flTime );
+	CDebugOverlay::AddLineOverlay( vecPoints[2], vecPoints[3], s_pVoxelColor[m_nLevel][0], s_pVoxelColor[m_nLevel][1], s_pVoxelColor[m_nLevel][2], 255, true, flTime );
+	CDebugOverlay::AddLineOverlay( vecPoints[3], vecPoints[0], s_pVoxelColor[m_nLevel][0], s_pVoxelColor[m_nLevel][1], s_pVoxelColor[m_nLevel][2], 255, true, flTime );
+	
+	CDebugOverlay::AddLineOverlay( vecPoints[4], vecPoints[5], s_pVoxelColor[m_nLevel][0], s_pVoxelColor[m_nLevel][1], s_pVoxelColor[m_nLevel][2], 255, true, flTime );
+	CDebugOverlay::AddLineOverlay( vecPoints[5], vecPoints[6], s_pVoxelColor[m_nLevel][0], s_pVoxelColor[m_nLevel][1], s_pVoxelColor[m_nLevel][2], 255, true, flTime );
+	CDebugOverlay::AddLineOverlay( vecPoints[6], vecPoints[7], s_pVoxelColor[m_nLevel][0], s_pVoxelColor[m_nLevel][1], s_pVoxelColor[m_nLevel][2], 255, true, flTime );
+	CDebugOverlay::AddLineOverlay( vecPoints[7], vecPoints[4], s_pVoxelColor[m_nLevel][0], s_pVoxelColor[m_nLevel][1], s_pVoxelColor[m_nLevel][2], 255, true, flTime );
+	
+	CDebugOverlay::AddLineOverlay( vecPoints[0], vecPoints[4], s_pVoxelColor[m_nLevel][0], s_pVoxelColor[m_nLevel][1], s_pVoxelColor[m_nLevel][2], 255, true, flTime );
+	CDebugOverlay::AddLineOverlay( vecPoints[3], vecPoints[7], s_pVoxelColor[m_nLevel][0], s_pVoxelColor[m_nLevel][1], s_pVoxelColor[m_nLevel][2], 255, true, flTime );
+	CDebugOverlay::AddLineOverlay( vecPoints[1], vecPoints[5], s_pVoxelColor[m_nLevel][0], s_pVoxelColor[m_nLevel][1], s_pVoxelColor[m_nLevel][2], 255, true, flTime );
+	CDebugOverlay::AddLineOverlay( vecPoints[2], vecPoints[6], s_pVoxelColor[m_nLevel][0], s_pVoxelColor[m_nLevel][1], s_pVoxelColor[m_nLevel][2], 255, true, flTime );
+#endif
+}
+
+//-----------------------------------------------------------------------------
+// Purpose: Debug! Render the objects in a voxel (optionally, render the voxel!).
+//-----------------------------------------------------------------------------
+void CVoxelHash::RenderObjectsInVoxel( Voxel_t voxel, CPartitionVisitor *pVisitor, bool bRenderVoxel, float flTime )
+{
+	UtlHashFastHandle_t hHash = m_aVoxelHash.Find( voxel.uiVoxel );
+	if ( hHash == m_aVoxelHash.InvalidHandle() )
+		return;
+
+	int iEntityList = m_aVoxelHash.Element( hHash );
+	while ( iEntityList != m_aEntityList.InvalidIndex() )
+	{
+		SpatialPartitionHandle_t hPartition = m_aEntityList[iEntityList];
+		RenderObjectInVoxel( hPartition, pVisitor, flTime );					
+		iEntityList = m_aEntityList.Next( iEntityList );
+	}
+
+	if ( bRenderVoxel )
+	{
+		RenderVoxel( voxel, flTime );
+	}
+}
+
+
+//-----------------------------------------------------------------------------
+// Returns number of entities in the hash
+//-----------------------------------------------------------------------------
+int CVoxelHash::EntityCount()
+{
+	int nCount = 0;
+	int nBucketCount = SPHASH_BUCKET_COUNT;
+	for ( int iBucket = 0; iBucket < nBucketCount; ++iBucket )
+	{
+		if ( m_aVoxelHash.m_aBuckets[iBucket].Count() == 0 )
+			continue;
+
+		UtlPtrLinkedListIndex_t hHash = m_aVoxelHash.m_aBuckets[iBucket].Head();
+	
+		while ( hHash != m_aVoxelHash.m_aBuckets[iBucket].InvalidIndex() )
+		{
+			int iEntity = m_aVoxelHash.m_aBuckets[iBucket][hHash].m_Data;
+			while ( iEntity!= m_aEntityList.InvalidIndex() )
+			{
+				++nCount;
+				iEntity = m_aEntityList.Next( iEntity );
+			}
+
+			hHash = m_aVoxelHash.m_aBuckets[iBucket].Next( hHash );
+		}
+	}
+	return nCount;
+}
+
+
+//-----------------------------------------------------------------------------
+// Rendering methods
+//-----------------------------------------------------------------------------
+void CVoxelHash::RenderGrid()
+{
+#ifndef SWDS
+	Vector vecStart, vecEnd;
+	for ( int i = 0; i < m_nVoxelDelta[0]; ++i )
+	{
+		vecStart.x = vecEnd.x = i * VoxelSize() + m_vecVoxelOrigin.x;
+		for ( int j = 0; j < m_nVoxelDelta[1]; ++j )
+		{
+			vecStart.y = vecEnd.y = j * VoxelSize() + m_vecVoxelOrigin.y;
+			vecStart.z = m_vecVoxelOrigin.z;
+			vecEnd.z = m_nVoxelDelta[2] * VoxelSize() + m_vecVoxelOrigin.z;
+
+			RenderLine( vecStart, vecEnd, s_pVoxelColor[m_nLevel], true );
+		}
+	}
+
+	for ( int i = 0; i < m_nVoxelDelta[0]; ++i )
+	{
+		vecStart.x = vecEnd.x = i * VoxelSize() + m_vecVoxelOrigin.x;
+		for ( int j = 0; j < m_nVoxelDelta[2]; ++j )
+		{
+			vecStart.z = vecEnd.z = j * VoxelSize() + m_vecVoxelOrigin.z;
+			vecStart.y = m_vecVoxelOrigin.y;
+			vecEnd.y = m_nVoxelDelta[2] * VoxelSize() + m_vecVoxelOrigin.y;
+
+			RenderLine( vecStart, vecEnd, s_pVoxelColor[m_nLevel], true );
+		}
+	}
+
+	for ( int i = 0; i < m_nVoxelDelta[1]; ++i )
+	{
+		vecStart.y = vecEnd.y = i * VoxelSize() + m_vecVoxelOrigin.y;
+		for ( int j = 0; j < m_nVoxelDelta[2]; ++j )
+		{
+			vecStart.z = vecEnd.z = j * VoxelSize() + m_vecVoxelOrigin.z;
+			vecStart.x = m_vecVoxelOrigin.z;
+			vecEnd.x = m_nVoxelDelta[2] * VoxelSize() + m_vecVoxelOrigin.x;
+
+			RenderLine( vecStart, vecEnd, s_pVoxelColor[m_nLevel], true );
+		}
+	}
+#endif
+}
+
+//-----------------------------------------------------------------------------
+// Purpose: Debug! Render boxes around objects in tree.
+//-----------------------------------------------------------------------------
+void CVoxelHash::RenderAllObjectsInTree( float flTime )
+{
+	int nBucketCount = SPHASH_BUCKET_COUNT;
+
+	CPartitionVisits *pPrevVisits = m_pTree->BeginVisit();
+	CPartitionVisitor visitor( m_pTree );
+
+	for ( int iBucket = 0; iBucket < nBucketCount; ++iBucket )
+	{
+		if ( m_aVoxelHash.m_aBuckets[iBucket].Count() == 0 )
+			continue;
+
+		UtlPtrLinkedListIndex_t hHash = m_aVoxelHash.m_aBuckets[iBucket].Head();
+
+		while ( hHash != m_aVoxelHash.m_aBuckets[iBucket].InvalidIndex() )
+		{
+			int iEntity = m_aVoxelHash.m_aBuckets[iBucket][hHash].m_Data;
+			while ( iEntity!= m_aEntityList.InvalidIndex() )
+			{
+				SpatialPartitionHandle_t hPartition = m_aEntityList[iEntity];
+				RenderObjectInVoxel( hPartition, &visitor, flTime );
+				iEntity = m_aEntityList.Next( iEntity );
+			}
+
+			hHash = m_aVoxelHash.m_aBuckets[iBucket].Next( hHash );
+		}
+	}
+
+	m_pTree->EndVisit( pPrevVisits );
+}
+
+
+//-----------------------------------------------------------------------------
+// Purpose:
+//-----------------------------------------------------------------------------
+void CVoxelHash::RenderObjectsInPlayerLeafs( const Vector &vecPlayerMin, const Vector &vecPlayerMax, float flTime )
+{
+	// Visit each voxel in the box and enumerate its elements.
+	Voxel_t voxelMin, voxelMax;
+	voxelMin = VoxelIndexFromPoint( vecPlayerMin );
+	voxelMax = VoxelIndexFromPoint( vecPlayerMax );
+	
+	CPartitionVisits *pPrevVisits = m_pTree->BeginVisit();
+
+	// Create leaf cache.
+	Voxel_t voxel;
+	unsigned int iX, iY, iZ;
+	CPartitionVisitor visitor( m_pTree );
+	for ( iX = voxelMin.bitsVoxel.x; iX <= voxelMax.bitsVoxel.x; ++iX )
+	{
+		for ( iY = voxelMin.bitsVoxel.y; iY <= voxelMax.bitsVoxel.y; ++iY )
+		{
+			for ( iZ = voxelMin.bitsVoxel.z; iZ <= voxelMax.bitsVoxel.z; ++iZ )
+			{
+				voxel.bitsVoxel.x = iX;
+				voxel.bitsVoxel.y = iY;
+				voxel.bitsVoxel.z = iZ;
+				RenderObjectsInVoxel( voxel, &visitor, false, flTime );
+			}
+		}
+	}
+
+	m_pTree->EndVisit( pPrevVisits );
+}
+
+//-----------------------------------------------------------------------------
+// Purpose: Constructor
+//-----------------------------------------------------------------------------
+
+CVoxelTree::CVoxelTree() : m_pVoxelHash( NULL ), m_pOwner( NULL ), m_nNextVisitBit( 0 )
+{
+	// Compute max number of levels
+	m_nLevelCount = 0;
+	while ( CVoxelHash::ComputeVoxelCountAtLevel( m_nLevelCount ) > 2 )
+	{
+		++m_nLevelCount;
+	}
+	++m_nLevelCount;	// Account for the level where count = 2;
+
+	// Various optimizations I've made require 4 levels
+	Assert( m_nLevelCount == 4 );
+
+	m_pVoxelHash = new CVoxelHash[m_nLevelCount]; 
+
+	m_AvailableVisitBits.EnsureCapacity( 2048 );
+}
+
+//-----------------------------------------------------------------------------
+// 
+//-----------------------------------------------------------------------------
+CVoxelTree::~CVoxelTree()
+{
+	delete[] m_pVoxelHash;
+}
+
+
+void ClampVector( Vector &out, const Vector &mins, const Vector &maxs )
+{
+	for ( int i = 0; i < 3; i++ )
+	{
+		out[i] = clamp(out[i], mins[i], maxs[i]);
+	}
+}
+
+//-----------------------------------------------------------------------------
+// Purpose:
+//   Input: worldmin - 
+//          worldmax - 
+//-----------------------------------------------------------------------------
+void CVoxelTree::Init( CSpatialPartition *pOwner, int iTree, const Vector &worldmin, const Vector &worldmax )
+{
+	m_pOwner = pOwner;
+	m_TreeId = iTree;
+
+	// Reset the enumeration id.
+	m_pVisits = NULL;
+
+	for ( int i = 0; i < m_nLevelCount; ++i )
+	{
+		m_pVoxelHash[i].Init( this, worldmin, worldmax, i );
+	}
+
+	// Setup the leaf list pool.
+	m_aLeafList.Purge();
+	m_aLeafList.SetGrowSize( SPHASH_LEAFLIST_BLOCK );
+}
+
+
+//-----------------------------------------------------------------------------
+// Purpose:
+//-----------------------------------------------------------------------------
+void CVoxelTree::Shutdown( void )
+{
+	m_aLeafList.Purge();
+	for ( int i = 0; i < m_nLevelCount; ++i )
+	{
+		m_pVoxelHash[i].Shutdown();
+	}
+}
+
+
+//-----------------------------------------------------------------------------
+// Insert into the appropriate tree
+//-----------------------------------------------------------------------------
+void CVoxelTree::InsertIntoTree( SpatialPartitionHandle_t hPartition, const Vector& mins, const Vector& maxs )
+{
+	bool bWasReading = ( m_pVisits != NULL );
+	if ( bWasReading )
+	{
+		// If we're recursing in this thread, need to release our read lock to allow ourselves to write
+		UnlockRead();
+	}
+
+	m_lock.LockForWrite();
+	Assert( hPartition != PARTITION_INVALID_HANDLE );
+
+	EntityInfo_t &info = EntityInfo( hPartition );
+	if ( m_AvailableVisitBits.Count() )
+	{
+		info.m_nVisitBit[m_TreeId] = m_AvailableVisitBits.Tail();
+		m_AvailableVisitBits.Remove( m_AvailableVisitBits.Count() - 1 );
+	}
+	else
+	{
+		info.m_nVisitBit[m_TreeId] = m_nNextVisitBit++;
+	}
+
+	// Bloat by an eps before inserting the object into the tree.
+	Vector vecMin( mins.x - SPHASH_EPS, mins.y - SPHASH_EPS, mins.z - SPHASH_EPS );
+	Vector vecMax( maxs.x + SPHASH_EPS, maxs.y + SPHASH_EPS, maxs.z + SPHASH_EPS );
+
+	ClampVector(vecMin, s_PartitionMin, s_PartitionMax);
+	ClampVector(vecMax, s_PartitionMin, s_PartitionMax);
+	Vector vecSize;
+	VectorSubtract( vecMax, vecMin, vecSize );
+
+	int nLevel;
+	for ( nLevel = 0; nLevel < m_nLevelCount - 1; ++nLevel )
+	{
+		int nVoxelSize = m_pVoxelHash[nLevel].VoxelSize();
+		if ( (nVoxelSize > vecSize.x) && (nVoxelSize > vecSize.y) && (nVoxelSize > vecSize.z) )
+			break;
+	}
+	m_pVoxelHash[nLevel].InsertIntoTree( hPartition, vecMin, vecMax );
+	m_lock.UnlockWrite();
+
+	if ( bWasReading )
+	{
+		LockForRead();
+	}
+}
+
+
+//-----------------------------------------------------------------------------
+// Remove from appropriate tree
+//-----------------------------------------------------------------------------
+void CVoxelTree::RemoveFromTree( SpatialPartitionHandle_t hPartition )
+{
+	Assert( hPartition != PARTITION_INVALID_HANDLE );
+	EntityInfo_t &info = EntityInfo( hPartition );
+	int nLevel = info.m_nLevel[GetTreeId()];
+	if ( nLevel >= 0 )
+	{
+		bool bWasReading = ( m_pVisits != NULL );
+		if ( bWasReading )
+		{
+			// If we're recursing in this thread, need to release our read lock to allow ourselves to write
+			UnlockRead();
+		}
+
+		m_lock.LockForWrite();
+		m_pVoxelHash[nLevel].RemoveFromTree( hPartition );
+		m_AvailableVisitBits.AddToTail( info.m_nVisitBit[m_TreeId] );
+		info.m_nVisitBit[m_TreeId] = (unsigned short)-1;
+		m_lock.UnlockWrite();
+
+		if ( bWasReading )
+		{
+			LockForRead();
+		}
+	}
+}
+
+
+//-----------------------------------------------------------------------------
+// Called when an element moves
+//-----------------------------------------------------------------------------
+void CVoxelTree::ElementMoved( SpatialPartitionHandle_t hPartition, const Vector& mins, const Vector& maxs )
+{
+	if ( hPartition != PARTITION_INVALID_HANDLE )
+	{
+		// If it doesn't already exist in the tree - add it.
+		EntityInfo_t &info = EntityInfo( hPartition );
+		if ( info.m_iLeafList[GetTreeId()] == CLeafList::InvalidIndex() )
+		{
+			InsertIntoTree( hPartition, mins, maxs );
+			return;
+		} 
+
+		// Bloat by an eps before inserting the object into the tree.
+		// Need to do this here to get the test to work
+		Vector vecEpsMin( mins.x - SPHASH_EPS, mins.y - SPHASH_EPS, mins.z - SPHASH_EPS );
+		Vector vecEpsMax( maxs.x + SPHASH_EPS, maxs.y + SPHASH_EPS, maxs.z + SPHASH_EPS );
+
+		if ( (info.m_vecMin == vecEpsMin) && (info.m_vecMax == vecEpsMax) )
+		{
+			return;
+		}
+
+		// Remove entity from voxel hash.
+		RemoveFromTree( hPartition );
+
+		// Re-insert entity into voxel hash.
+		InsertIntoTree( hPartition, mins, maxs );
+	}
+}
+
+
+//-----------------------------------------------------------------------------
+// Purpose:
+//-----------------------------------------------------------------------------
+void CVoxelTree::EnumerateElementsInBox( SpatialPartitionListMask_t listMask, 
+										const Vector& vecMins, const Vector& vecMaxs, 
+										bool coarseTest, IPartitionEnumerator* pIterator )
+{
+	VPROF( "BoxTest/SphereTest" );
+
+	// If this assertion fails, you're using a list at a point where the spatial partition elements aren't set up!
+	//	Assert( ( listMask & m_nSuppressedListMask ) == 0 );
+
+	// Early-out.
+	if ( listMask == 0 )
+		return;
+
+	// Clamp bounds to extant space
+	Vector mins, maxs;
+	VectorMax( vecMins, s_PartitionMin, mins );
+	VectorMin( mins, s_PartitionMax, mins );
+
+	VectorMax( vecMaxs, s_PartitionMin, maxs );
+	VectorMin( maxs, s_PartitionMax, maxs );
+
+	// Callbacks.
+	CPartitionVisits *pPrevVisits = BeginVisit();
+
+	m_lock.LockForRead();
+	Voxel_t vs = m_pVoxelHash[0].VoxelIndexFromPoint( mins );
+	Voxel_t ve = m_pVoxelHash[0].VoxelIndexFromPoint( maxs );
+	if ( !m_pVoxelHash[0].EnumerateElementsInBox( listMask, vs, ve, mins, maxs, pIterator ) )
+	{
+		m_lock.UnlockRead();
+		EndVisit( pPrevVisits );
+		return;
+	}
+
+	vs = ConvertToNextLevel( vs );
+	ve = ConvertToNextLevel( ve );
+	if ( !m_pVoxelHash[1].EnumerateElementsInBox( listMask, vs, ve, mins, maxs, pIterator ) )
+	{
+		m_lock.UnlockRead();
+		EndVisit( pPrevVisits );
+		return;
+	}
+
+	vs = ConvertToNextLevel( vs );
+	ve = ConvertToNextLevel( ve );
+	if ( !m_pVoxelHash[2].EnumerateElementsInBox( listMask, vs, ve, mins, maxs, pIterator ) )
+	{
+		m_lock.UnlockRead();
+		EndVisit( pPrevVisits );
+		return;
+	}
+
+	vs = ConvertToNextLevel( vs );
+	ve = ConvertToNextLevel( ve );
+	m_pVoxelHash[3].EnumerateElementsInBox( listMask, vs, ve, mins, maxs, pIterator );
+
+	m_lock.UnlockRead();
+	EndVisit( pPrevVisits );
+}
+
+
+//-----------------------------------------------------------------------------
+// Purpose:
+//-----------------------------------------------------------------------------
+void CVoxelTree::EnumerateElementsInSphere( SpatialPartitionListMask_t listMask, 
+										   const Vector& origin, float radius, bool coarseTest, IPartitionEnumerator* pIterator )
+{
+	// Otherwise they might as well just walk the entire ent list!!!
+	Assert( radius <= MAX_COORD_FLOAT );
+
+	// If the box test is fast enough - forget about the sphere test?
+	Vector vecMin( origin.x - radius, origin.y - radius, origin.z - radius );
+	Vector vecMax( origin.x + radius, origin.y + radius, origin.z + radius );
+	return EnumerateElementsInBox( listMask, vecMin, vecMax, coarseTest, pIterator );
+}
+
+
+//-----------------------------------------------------------------------------
+// Purpose:
+//-----------------------------------------------------------------------------
+bool CVoxelTree::EnumerateElementsAlongRay_Ray( SpatialPartitionListMask_t listMask, 
+											   const Ray_t &ray, const Vector &vecInvDelta, const Vector &vecEnd, IPartitionEnumerator *pIterator )
+{
+	// Find the voxel start + end
+	Voxel_t voxelStart = m_pVoxelHash[0].VoxelIndexFromPoint( ray.m_Start );
+	Voxel_t voxelEnd = m_pVoxelHash[0].VoxelIndexFromPoint( vecEnd );
+
+	bool bSingleVoxel = ( voxelStart.uiVoxel == voxelEnd.uiVoxel );
+	CIntersectRay intersectRay( this, ray, vecInvDelta );
+
+	// Optimization: Look for single voxel rays
+	if ( bSingleVoxel )
+	{
+		if ( !m_pVoxelHash[0].EnumerateElementsInSingleVoxel( voxelStart, intersectRay, listMask, pIterator ) )
+			return false;
+		voxelStart = ConvertToNextLevel( voxelStart );
+		if ( !m_pVoxelHash[1].EnumerateElementsInSingleVoxel( voxelStart, intersectRay, listMask, pIterator ) )
+			return false;
+		voxelStart = ConvertToNextLevel( voxelStart );
+		if ( !m_pVoxelHash[2].EnumerateElementsInSingleVoxel( voxelStart, intersectRay, listMask, pIterator ) )
+			return false;
+		voxelStart = ConvertToNextLevel( voxelStart );
+		return m_pVoxelHash[3].EnumerateElementsInSingleVoxel( voxelStart, intersectRay, listMask, pIterator );
+	}
+
+	Voxel_t voxelCurrent;
+	voxelCurrent.uiVoxel = voxelStart.uiVoxel;
+
+	// Setup.
+	int nStep[3];
+	float tMax[3];
+	float tDelta[3];
+	m_pVoxelHash[0].LeafListRaySetup( ray, vecEnd, vecInvDelta, voxelStart, nStep, tMax, tDelta );
+
+	// Walk the voxels and visit all elements in each voxel
+
+	// Deal with all levels
+	Voxel_t ov1, ov2, ov3;
+	ov1.uiVoxel = ov2.uiVoxel = ov3.uiVoxel = 0xFFFFFFFF;
+
+	Voxel_t v1 = ConvertToNextLevel( voxelCurrent );
+	Voxel_t v2 = ConvertToNextLevel( v1 );
+	Voxel_t v3 = ConvertToNextLevel( v2 );
+
+	while ( 1 )
+	{
+		if ( !m_pVoxelHash[0].EnumerateElementsInVoxel( voxelCurrent, intersectRay, listMask, pIterator ) )
+			return false;
+
+		if ( v1.uiVoxel != ov1.uiVoxel )
+		{
+			if ( !m_pVoxelHash[1].EnumerateElementsInVoxel( v1, intersectRay, listMask, pIterator ) )
+				return false;
+		}
+		if ( v2.uiVoxel != ov2.uiVoxel )
+		{
+			if ( !m_pVoxelHash[2].EnumerateElementsInVoxel( v2, intersectRay, listMask, pIterator ) )
+				return false;
+		}
+		if ( v3.uiVoxel != ov3.uiVoxel )
+		{
+			if ( !m_pVoxelHash[3].EnumerateElementsInVoxel( v3, intersectRay, listMask, pIterator ) )
+				return false;
+		}
+
+		if ( tMax[0] >= 1.0f && tMax[1] >= 1.0f && tMax[2] >= 1.0f )
+			break;
+
+		if ( tMax[0] < tMax[1] )
+		{
+			if ( tMax[0] < tMax[2] )
+			{
+				voxelCurrent.bitsVoxel.x += nStep[0];
+				tMax[0] += tDelta[0];
+			}
+			else
+			{
+				voxelCurrent.bitsVoxel.z += nStep[2];
+				tMax[2] += tDelta[2];
+			}
+		}
+		else
+		{
+			if ( tMax[1] < tMax[2] )
+			{
+				voxelCurrent.bitsVoxel.y += nStep[1];
+				tMax[1] += tDelta[1];
+			}
+			else
+			{
+				voxelCurrent.bitsVoxel.z += nStep[2];
+				tMax[2] += tDelta[2];
+			}
+		}
+
+		ov1 = v1; ov2 = v2; ov3 = v3;
+		v1 = ConvertToNextLevel( voxelCurrent );
+		v2 = ConvertToNextLevel( v1 );
+		v3 = ConvertToNextLevel( v2 );
+	}
+
+	return true;
+}
+
+
+//-----------------------------------------------------------------------------
+// Purpose:
+//-----------------------------------------------------------------------------
+void CVoxelTree::ComputeSweptRayBounds( const Ray_t &ray, const Vector &vecStartMin, const Vector &vecStartMax, Vector *pVecMin, Vector *pVecMax )
+{
+	if ( ray.m_Delta.x < 0 )
+	{
+		pVecMin->x = vecStartMin.x + ray.m_Delta.x;
+		pVecMax->x = vecStartMax.x;
+	}
+	else
+	{
+		pVecMin->x = vecStartMin.x;
+		pVecMax->x = vecStartMax.x + ray.m_Delta.x;
+	}
+
+	if ( ray.m_Delta.y < 0 )
+	{
+		pVecMin->y = vecStartMin.y + ray.m_Delta.y;
+		pVecMax->y = vecStartMax.y;
+	}
+	else
+	{
+		pVecMin->y = vecStartMin.y;
+		pVecMax->y = vecStartMax.y + ray.m_Delta.y;
+	}
+
+	if ( ray.m_Delta.z < 0 )
+	{
+		pVecMin->z = vecStartMin.z + ray.m_Delta.z;
+		pVecMax->z = vecStartMax.z;
+	}
+	else
+	{
+		pVecMin->z = vecStartMin.z;
+		pVecMax->z = vecStartMax.z + ray.m_Delta.z;
+	}
+}
+
+
+//-----------------------------------------------------------------------------
+// Purpose:
+//-----------------------------------------------------------------------------
+bool CVoxelTree::EnumerateElementsAlongRay_ExtrudedRay( SpatialPartitionListMask_t listMask, 
+													   const Ray_t &ray, const Vector &vecInvDelta, const Vector &vecEnd, IPartitionEnumerator *pIterator )
+{
+	// Check the starting position, then proceed with the sweep.
+	Vector vecMin, vecMax;
+	VectorSubtract( ray.m_Start, ray.m_Extents, vecMin );
+	VectorAdd( ray.m_Start, ray.m_Extents, vecMax );
+
+	// Visit each voxel in the box and enumerate its elements.
+	// Indexed as voxelBounds[level][min/max][x/y/z]
+	int voxelBounds[4][2][3];
+	m_pVoxelHash[0].VoxelIndexFromPoint( vecMin, voxelBounds[0][0] );
+	m_pVoxelHash[0].VoxelIndexFromPoint( vecMax, voxelBounds[0][1] );
+
+	CIntersectSweptBox intersectSweptBox( this, ray, vecInvDelta );
+
+	// Iterate over all voxels that intersect the box around the starting ray point
+	for ( int i = 0; i < m_nLevelCount; ++i )
+	{
+		voxelBounds[i][0][0] = voxelBounds[0][0][0] >> ( i * SPHASH_LEVEL_SKIP );
+		voxelBounds[i][0][1] = voxelBounds[0][0][1] >> ( i * SPHASH_LEVEL_SKIP );
+		voxelBounds[i][0][2] = voxelBounds[0][0][2] >> ( i * SPHASH_LEVEL_SKIP );
+
+		voxelBounds[i][1][0] = voxelBounds[0][1][0] >> ( i * SPHASH_LEVEL_SKIP );
+		voxelBounds[i][1][1] = voxelBounds[0][1][1] >> ( i * SPHASH_LEVEL_SKIP );
+		voxelBounds[i][1][2] = voxelBounds[0][1][2] >> ( i * SPHASH_LEVEL_SKIP );
+
+		Voxel_t voxel;
+		int iX, iY, iZ;
+		for ( iX = voxelBounds[i][0][0]; iX <= voxelBounds[i][1][0]; ++iX )
+		{
+			voxel.bitsVoxel.x = iX;
+			for ( iY = voxelBounds[i][0][1]; iY <= voxelBounds[i][1][1]; ++iY )
+			{
+				voxel.bitsVoxel.y = iY;
+				for ( iZ = voxelBounds[i][0][2]; iZ <= voxelBounds[i][1][2]; ++iZ )
+				{
+					voxel.bitsVoxel.z = iZ;
+					if ( !m_pVoxelHash[i].EnumerateElementsInVoxel( voxel, intersectSweptBox, listMask, pIterator ) )
+						return false;
+				}
+			}
+		}
+	}
+
+	// Early out: Check to see if the range of voxels at the endpoint
+	// is the same as the range at the start point. If so, we're done.
+	Vector vecEndMin, vecEndMax;
+	VectorSubtract( vecEnd, ray.m_Extents, vecEndMin );
+	VectorAdd( vecEnd, ray.m_Extents, vecEndMax );
+
+	int endVoxelMin[3], endVoxelMax[3];
+	m_pVoxelHash[0].VoxelIndexFromPoint( vecEndMin, endVoxelMin );
+	m_pVoxelHash[0].VoxelIndexFromPoint( vecEndMax, endVoxelMax );
+	if ( (endVoxelMin[0] >= voxelBounds[0][0][0]) && (endVoxelMin[1] >= voxelBounds[0][0][1]) && (endVoxelMin[2] >= voxelBounds[0][0][2]) &&
+		(endVoxelMax[0] <= voxelBounds[0][1][0]) && (endVoxelMax[1] <= voxelBounds[0][1][1]) && (endVoxelMax[2] <= voxelBounds[0][1][2]) )
+		return true;
+
+	// Setup.
+	int nStep[3];
+	float tMax[3];	// amount of change in t along ray until we hit the next new voxel
+	float tMin[3];	// amount of change in t along ray until we leave the last voxel
+	float tDelta[3];
+	m_pVoxelHash[0].LeafListExtrudedRaySetup( ray, vecInvDelta, vecMin, vecMax, voxelBounds[0][0], voxelBounds[0][1], nStep, tMin, tMax, tDelta );
+
+	int nLastVoxel1[3];
+	int nLastVoxel2[3];
+	int nLastVoxel3[3];
+	for ( int i = 0; i < 3; ++i )
+	{
+		int nIndex = ( nStep[i] > 0 ) ? 1 : 0;
+		nLastVoxel1[i] = voxelBounds[1][nIndex][i];
+		nLastVoxel2[i] = voxelBounds[2][nIndex][i];
+		nLastVoxel3[i] = voxelBounds[3][nIndex][i];
+	}
+
+	// Walk the voxels and create the leaf list.
+	int iAxis, iMinAxis;
+	while ( tMax[0] < 1.0f || tMax[1] < 1.0f || tMax[2] < 1.0f )
+	{
+		iAxis = MinIndex( tMax[0], tMax[1], tMax[2] );
+		iMinAxis = MinIndex( tMin[0], tMin[1], tMin[2] );
+
+		if ( tMin[iMinAxis] < tMax[iAxis] )
+		{
+			tMin[iMinAxis] += tDelta[iMinAxis];
+			int nIndex = ( nStep[iMinAxis] > 0 ) ? 0 : 1;
+			voxelBounds[0][nIndex][iMinAxis] += nStep[iMinAxis];
+			voxelBounds[1][nIndex][iMinAxis] = voxelBounds[0][nIndex][iMinAxis] >> SPHASH_LEVEL_SKIP;
+			voxelBounds[2][nIndex][iMinAxis] = voxelBounds[0][nIndex][iMinAxis] >> (2 * SPHASH_LEVEL_SKIP);
+			voxelBounds[3][nIndex][iMinAxis] = voxelBounds[0][nIndex][iMinAxis] >> (3 * SPHASH_LEVEL_SKIP);
+		}
+		else
+		{
+			tMax[iAxis] += tDelta[iAxis];
+			int nIndex = ( nStep[iAxis] > 0 ) ? 1 : 0;
+			voxelBounds[0][nIndex][iAxis] += nStep[iAxis];
+			voxelBounds[1][nIndex][iAxis] = voxelBounds[0][nIndex][iAxis] >> SPHASH_LEVEL_SKIP;
+			voxelBounds[2][nIndex][iAxis] = voxelBounds[0][nIndex][iAxis] >> (2 * SPHASH_LEVEL_SKIP);
+			voxelBounds[3][nIndex][iAxis] = voxelBounds[0][nIndex][iAxis] >> (3 * SPHASH_LEVEL_SKIP);
+
+			if ( !m_pVoxelHash[0].EnumerateElementsAlongRay_ExtrudedRaySlice( listMask, pIterator, intersectSweptBox, voxelBounds[0][0], voxelBounds[0][1], iAxis, nStep ) )
+				return false;
+
+			if ( nLastVoxel1[iAxis] != voxelBounds[1][nIndex][iAxis] )
+			{
+				nLastVoxel1[iAxis] = voxelBounds[1][nIndex][iAxis];
+				if ( !m_pVoxelHash[1].EnumerateElementsAlongRay_ExtrudedRaySlice( listMask, pIterator, intersectSweptBox, voxelBounds[1][0], voxelBounds[1][1], iAxis, nStep ) )
+					return false;
+			}
+
+			if ( nLastVoxel2[iAxis] != voxelBounds[2][nIndex][iAxis] )
+			{
+				nLastVoxel2[iAxis] = voxelBounds[2][nIndex][iAxis];
+				if ( !m_pVoxelHash[2].EnumerateElementsAlongRay_ExtrudedRaySlice( listMask, pIterator, intersectSweptBox, voxelBounds[2][0], voxelBounds[2][1], iAxis, nStep ) )
+					return false;
+			}
+
+			if ( nLastVoxel3[iAxis] != voxelBounds[3][nIndex][iAxis] )
+			{
+				nLastVoxel3[iAxis] = voxelBounds[3][nIndex][iAxis];
+				if ( !m_pVoxelHash[3].EnumerateElementsAlongRay_ExtrudedRaySlice( listMask, pIterator, intersectSweptBox, voxelBounds[3][0], voxelBounds[3][1], iAxis, nStep ) )
+					return false;
+			}
+		}
+	}
+	return true;
+}
+
+
+//-----------------------------------------------------------------------------
+// Purpose:
+//-----------------------------------------------------------------------------
+
+void CVoxelTree::EnumerateElementsAlongRay( SpatialPartitionListMask_t listMask, 
+										   const Ray_t &ray, bool coarseTest, IPartitionEnumerator *pIterator )
+{
+	VPROF("EnumerateElementsAlongRay");
+
+	if ( !ray.m_IsSwept )
+	{
+		Vector vecMin, vecMax;
+		VectorSubtract( ray.m_Start, ray.m_Extents, vecMin );
+		VectorAdd( ray.m_Start, ray.m_Extents, vecMax );
+		return EnumerateElementsInBox( listMask, vecMin, vecMax, coarseTest, pIterator );
+	}
+
+	// If this assertion fails, you're using a list at a point where the spatial partition elements aren't set up!
+	//	Assert( ( listMask & m_nSuppressedListMask ) == 0 );
+
+	// Early-out.
+	if ( listMask == 0 )
+		return;
+
+	// Calculate the end of the ray
+	Vector vecEnd;
+	Vector vecInvDelta;
+	Ray_t clippedRay = ray;
+	VectorAdd( clippedRay.m_Start, clippedRay.m_Delta, vecEnd );
+
+	bool bStartIn = IsPointInBox( ray.m_Start, s_PartitionMin, s_PartitionMax );
+	bool bEndIn = IsPointInBox( vecEnd, s_PartitionMin, s_PartitionMax );
+	if ( !bStartIn && !bEndIn )
+		return;
+
+	// Callbacks.
+	if ( !bStartIn )
+	{
+		ClampStartPoint( clippedRay, vecEnd );
+	}
+	else if ( !bEndIn )
+	{
+		ClampEndPoint( clippedRay, vecEnd );
+	}
+
+	vecInvDelta[0] = ( clippedRay.m_Delta[0] != 0.0f ) ? 1.0f / clippedRay.m_Delta[0] : FLT_MAX;
+	vecInvDelta[1] = ( clippedRay.m_Delta[1] != 0.0f ) ? 1.0f / clippedRay.m_Delta[1] : FLT_MAX;
+	vecInvDelta[2] = ( clippedRay.m_Delta[2] != 0.0f ) ? 1.0f / clippedRay.m_Delta[2] : FLT_MAX;
+
+	CPartitionVisits *pPrevVisits = BeginVisit();
+
+	m_lock.LockForRead();
+	if ( ray.m_IsRay )
+	{
+		EnumerateElementsAlongRay_Ray( listMask, clippedRay, vecInvDelta, vecEnd, pIterator );
+	}
+	else
+	{
+		EnumerateElementsAlongRay_ExtrudedRay( listMask, clippedRay, vecInvDelta, vecEnd, pIterator );
+	}
+
+	m_lock.UnlockRead();
+	EndVisit( pPrevVisits );
+}
+
+
+//-----------------------------------------------------------------------------
+// Purpose:
+//-----------------------------------------------------------------------------
+void CVoxelTree::EnumerateElementsAtPoint( SpatialPartitionListMask_t listMask, 
+										  const Vector& pt, bool coarseTest, IPartitionEnumerator* pIterator )
+{
+	// If this assertion fails, you're using a list at a point where the spatial partition elements aren't set up!
+	//	Assert( ( listMask & m_nSuppressedListMask ) == 0 );
+
+	// Early-out.
+	if ( listMask == 0 )
+		return;
+
+	m_lock.LockForRead();
+	// Callbacks.
+	Voxel_t v = m_pVoxelHash[0].VoxelIndexFromPoint( pt );
+	if ( !m_pVoxelHash[0].EnumerateElementsAtPoint( listMask, v, pt, pIterator ) )
+	{
+		m_lock.UnlockRead();
+		return;
+	}
+
+	v = ConvertToNextLevel( v );
+	if ( !m_pVoxelHash[1].EnumerateElementsAtPoint( listMask, v, pt, pIterator ) )
+	{
+		m_lock.UnlockRead();
+		return;
+	}
+
+	v = ConvertToNextLevel( v );
+	if ( !m_pVoxelHash[2].EnumerateElementsAtPoint( listMask, v, pt, pIterator ) )
+	{
+		m_lock.UnlockRead();
+		return;
+	}
+
+	v = ConvertToNextLevel( v );
+	m_pVoxelHash[3].EnumerateElementsAtPoint( listMask, v, pt, pIterator );
+	m_lock.UnlockRead();
+}
+
+
+//-----------------------------------------------------------------------------
+// Purpose: Debug! Render boxes around objects in tree.
+//-----------------------------------------------------------------------------
+void CVoxelTree::RenderAllObjectsInTree( float flTime )
+{
+	MDLCACHE_CRITICAL_SECTION_(g_pMDLCache);
+	m_lock.LockForRead();
+	for ( int i = 0; i < m_nLevelCount; ++i )
+	{
+		m_pVoxelHash[i].RenderAllObjectsInTree( flTime );
+	}
+	m_lock.UnlockRead();
+}
+
+
+
+//-----------------------------------------------------------------------------
+// Purpose:
+//-----------------------------------------------------------------------------
+void CVoxelTree::RenderObjectsInPlayerLeafs( const Vector &vecPlayerMin, const Vector &vecPlayerMax, float flTime )
+{
+	MDLCACHE_CRITICAL_SECTION_(g_pMDLCache);
+	m_lock.LockForRead();
+	for ( int i = 0; i < m_nLevelCount; ++i )
+	{
+		m_pVoxelHash[i].RenderObjectsInPlayerLeafs( vecPlayerMin, vecPlayerMax, flTime );
+	}
+	m_lock.UnlockRead();
+}
+
+
+//-----------------------------------------------------------------------------
+// Expose CSpatialPartition to the game + client DLL.
+//-----------------------------------------------------------------------------
+static CSpatialPartition	g_SpatialPartition;
+EXPOSE_SINGLE_INTERFACE_GLOBALVAR( CSpatialPartition, ISpatialPartition, INTERFACEVERSION_SPATIALPARTITION, g_SpatialPartition );
+
+//-----------------------------------------------------------------------------
+// Expose ISpatialPartitionInternal to the engine.
+//-----------------------------------------------------------------------------
+ISpatialPartitionInternal *SpatialPartition()
+{
+	return &g_SpatialPartition;
+}
+
+
+//-----------------------------------------------------------------------------
+// Purpose: Constructor
+//-----------------------------------------------------------------------------
+CSpatialPartition::CSpatialPartition()
+{
+	m_nQueryCallbackCount = 0;
+}
+
+
+CSpatialPartition::~CSpatialPartition()
+{
+	Shutdown();
+}
+
+//-----------------------------------------------------------------------------
+// Purpose:
+//   Input: worldmin - 
+//          worldmax - 
+//-----------------------------------------------------------------------------
+void CSpatialPartition::Init( const Vector &worldmin, const Vector &worldmax )
+{
+	// Clear the handle list and ensure some new memory.
+	m_aHandles.Purge();
+	m_aHandles.EnsureCapacity( SPHASH_HANDLELIST_BLOCK );
+
+	for ( int i = 0; i < NUM_TREES; i++ )
+	{
+		m_VoxelTrees[i].Init( this, i, worldmin, worldmax );
+	}
+}
+
+//-----------------------------------------------------------------------------
+// Purpose:
+//-----------------------------------------------------------------------------
+void CSpatialPartition::Shutdown( void )
+{
+	for ( int i = 0; i < NUM_TREES; i++ )
+	{
+		m_VoxelTrees[i].Shutdown();
+	}
+	m_aHandles.Purge();
+}
+
+
+//-----------------------------------------------------------------------------
+// Purpose: Add a callback to the query callback list.  Functions get called 
+//          right before a query occurs.
+//   Input: pCallback - pointer to the callback function to add
+//-----------------------------------------------------------------------------
+void CSpatialPartition::InstallQueryCallback( IPartitionQueryCallback *pCallback )
+{
+	// Verify data.
+	Assert( pCallback && m_nQueryCallbackCount < MAX_QUERY_CALLBACK );
+	if ( !pCallback || ( m_nQueryCallbackCount >= MAX_QUERY_CALLBACK ) )
+		return;
+
+	m_pQueryCallback[m_nQueryCallbackCount] = pCallback;
+	m_bUseOldQueryCallback[m_nQueryCallbackCount] = false;
+	++m_nQueryCallbackCount;
+}
+
+//-----------------------------------------------------------------------------
+// Purpose: Add a callback to the query callback list.  Functions get called 
+//          right before a query occurs.
+//   Input: pCallback - pointer to the callback function to add
+//-----------------------------------------------------------------------------
+void CSpatialPartition::InstallQueryCallback_V1( IPartitionQueryCallback *pCallback )
+{
+	// Verify data.
+	Assert( pCallback && m_nQueryCallbackCount < MAX_QUERY_CALLBACK );
+	if ( !pCallback || ( m_nQueryCallbackCount >= MAX_QUERY_CALLBACK ) )
+		return;
+
+	// NOTE: the query callbacks are not mutexed. Only add and remove when threads are joined
+
+	m_pQueryCallback[m_nQueryCallbackCount] = pCallback;
+	m_bUseOldQueryCallback[m_nQueryCallbackCount] = true;
+	++m_nQueryCallbackCount;
+}
+
+
+//-----------------------------------------------------------------------------
+// Purpose: Remove a callback from the query callback list.
+//   Input: pCallback - pointer to the callback function to remove
+//-----------------------------------------------------------------------------
+void CSpatialPartition::RemoveQueryCallback( IPartitionQueryCallback *pCallback )
+{
+	// Verify data.
+	if ( !pCallback )
+		return;
+
+	for ( int iQuery = m_nQueryCallbackCount; --iQuery >= 0;  )
+	{
+		if ( m_pQueryCallback[iQuery] == pCallback )
+		{
+			--m_nQueryCallbackCount;
+			m_pQueryCallback[iQuery] = m_pQueryCallback[m_nQueryCallbackCount];
+			return;
+		}
+	}
+}
+
+
+//-----------------------------------------------------------------------------
+// Purpose: Invokes the pre-query callbacks.
+//-----------------------------------------------------------------------------
+void CSpatialPartition::InvokeQueryCallbacks( SpatialPartitionListMask_t listMask, bool bDone )
+{
+	for ( int iQuery = 0; iQuery < m_nQueryCallbackCount; ++iQuery )
+	{
+		if ( !bDone )
+		{
+			if ( m_bUseOldQueryCallback[iQuery] )
+			{
+				m_pQueryCallback[iQuery]->OnPreQuery_V1();
+			}
+			else
+			{
+				m_pQueryCallback[iQuery]->OnPreQuery( listMask );
+			}
+		}
+		else
+		{
+			if ( !m_bUseOldQueryCallback[iQuery] )
+			{
+				m_pQueryCallback[iQuery]->OnPostQuery( listMask );
+			}
+		}
+	}
+}
+
+//-----------------------------------------------------------------------------
+// Purpose: Create spatial partition object handle.
+//   Input: pHandleEntity - entity handle of the object to create a spatial partition handle for
+//-----------------------------------------------------------------------------
+SpatialPartitionHandle_t CSpatialPartition::CreateHandle( IHandleEntity *pHandleEntity )
+{
+	m_HandlesMutex.Lock();
+	SpatialPartitionHandle_t hPartition = m_aHandles.AddToTail();
+	m_HandlesMutex.Unlock();
+	m_aHandles[hPartition].m_pHandleEntity = pHandleEntity;
+	m_aHandles[hPartition].m_vecMin.Init( FLT_MAX, FLT_MAX, FLT_MAX );
+	m_aHandles[hPartition].m_vecMax.Init( FLT_MIN, FLT_MIN, FLT_MIN );
+	m_aHandles[hPartition].m_fList = 0;
+	m_aHandles[hPartition].m_flags = 0;
+
+	for ( int i = 0; i < NUM_TREES; i++ )
+	{
+		m_aHandles[hPartition].m_nVisitBit[i] = 0xffff;
+		m_aHandles[hPartition].m_nLevel[i] = (uint8)-1;
+		m_aHandles[hPartition].m_iLeafList[i] = CLeafList::InvalidIndex();
+	}
+	
+	return hPartition;
+}
+
+
+//-----------------------------------------------------------------------------
+// Purpose: Destroy spatial partition object handle.
+//   Input: handle - handle of the spatial partition object handle to destroy
+//-----------------------------------------------------------------------------
+void CSpatialPartition::DestroyHandle( SpatialPartitionHandle_t hPartition )
+{
+	if ( hPartition != PARTITION_INVALID_HANDLE )
+	{
+		RemoveFromTree( hPartition );
+		m_HandlesMutex.Lock();
+//		memset( &m_aHandles[hPartition], 0xcd, sizeof(EntityInfo_t) );
+		m_aHandles.Remove( hPartition );
+		m_HandlesMutex.Unlock();
+	}
+}
+
+//-----------------------------------------------------------------------------
+// Purpose: Create spatial partition object handle and insert it into the tree.
+//   Input: pHandleEntity - entity handle of the object to create a spatial partition handle for
+//          listMask -
+//          mins - 
+//          maxs -
+//-----------------------------------------------------------------------------
+SpatialPartitionHandle_t CSpatialPartition::CreateHandle( IHandleEntity *pHandleEntity, 
+															  SpatialPartitionListMask_t listMask, 
+														      const Vector &mins, const Vector &maxs )
+{
+//	CDebugOverlay::AddBoxOverlay( vec3_origin, mins, maxs, vec3_angle, 0, 255, 0, 75, 3600 );
+
+	SpatialPartitionHandle_t hPartition = CreateHandle( pHandleEntity );
+	Insert( listMask, hPartition );
+	InsertIntoTree( hPartition, mins, maxs );
+
+	return hPartition;
+}
+
+//-----------------------------------------------------------------------------
+// Purpose: Insert object handle into group(s).
+//   Input: listId - list(s) to insert the object handle into
+//          handle - object handle to be inserted into list
+//-----------------------------------------------------------------------------
+void CSpatialPartition::Insert( SpatialPartitionListMask_t listId, SpatialPartitionHandle_t handle )
+{
+	Assert( m_aHandles.IsValidIndex( handle ) );
+	Assert( listId <= USHRT_MAX );
+	m_aHandles[handle].m_fList |= listId;
+}
+
+//-----------------------------------------------------------------------------
+// Purpose: Remove object handle from group(s).
+//   Input: listId - list(s) to remove the object handle from
+//          handle - object handle to be removed from list
+//-----------------------------------------------------------------------------
+void CSpatialPartition::Remove( SpatialPartitionListMask_t listId, SpatialPartitionHandle_t handle )
+{
+	Assert( m_aHandles.IsValidIndex( handle ) );
+	Assert( listId <= USHRT_MAX );
+	m_aHandles[handle].m_fList &= ~listId;
+}
+
+//-----------------------------------------------------------------------------
+// Purpose:
+//-----------------------------------------------------------------------------
+void CSpatialPartition::RemoveAndInsert( SpatialPartitionListMask_t removeMask, SpatialPartitionListMask_t insertMask, 
+											 SpatialPartitionHandle_t handle )
+{
+	Assert( m_aHandles.IsValidIndex( handle ) );
+	Assert( removeMask <= USHRT_MAX );
+	Assert( insertMask <= USHRT_MAX );
+	m_aHandles[handle].m_fList &= ~removeMask;
+	m_aHandles[handle].m_fList |= insertMask;
+}
+
+//-----------------------------------------------------------------------------
+// Purpose: Remove object handle from all groups.
+//   Input: handle - object handle to be removed from all lists
+//-----------------------------------------------------------------------------
+void CSpatialPartition::Remove( SpatialPartitionHandle_t handle )
+{
+	Assert( m_aHandles.IsValidIndex( handle ) );
+	m_aHandles[handle].m_fList = 0;
+}
+
+//-----------------------------------------------------------------------------
+// Purpose: Fast way to re-add (set) a group that was removed (and saved) via the
+//          HideElement call.
+//-----------------------------------------------------------------------------
+void CSpatialPartition::UnhideElement( SpatialPartitionHandle_t handle, SpatialTempHandle_t tempHandle )
+{
+	Assert( m_aHandles.IsValidIndex( handle ) );
+
+	m_HandlesMutex.Lock();
+	m_aHandles[handle].m_flags &= ~ENTITY_HIDDEN;
+	m_HandlesMutex.Unlock();
+}
+
+
+//-----------------------------------------------------------------------------
+// Purpose: Remove handle quickly saving the old list data, to be restored later
+//          via the UnhideElement call.
+//-----------------------------------------------------------------------------
+SpatialTempHandle_t CSpatialPartition::HideElement( SpatialPartitionHandle_t handle )
+{
+	Assert( m_aHandles.IsValidIndex( handle ) );
+	m_HandlesMutex.Lock();
+	m_aHandles[handle].m_flags |= ENTITY_HIDDEN;
+	m_HandlesMutex.Unlock();
+
+	return 1;
+}
+
+//-----------------------------------------------------------------------------
+// Purpose: (Debugging) Suppress queries on particular lists.
+//   Input: nListMask - lists to suppress/unsuppress
+//          bSuppress - (true/false) suppress/unsuppress
+//-----------------------------------------------------------------------------
+void CSpatialPartition::SuppressLists( SpatialPartitionListMask_t nListMask, bool bSuppress )
+{
+	if ( bSuppress )
+	{
+		m_nSuppressedListMask |= nListMask;
+	}
+	else
+	{
+		m_nSuppressedListMask &= ~nListMask;
+	}
+}
+
+//-----------------------------------------------------------------------------
+// Purpose: (Debugging) Get the suppression list.
+//  Output: spatial partition suppression list
+//-----------------------------------------------------------------------------
+SpatialPartitionListMask_t CSpatialPartition::GetSuppressedLists( void )
+{
+	return m_nSuppressedListMask;
+}
+
+//-----------------------------------------------------------------------------
+// Purpose:
+//-----------------------------------------------------------------------------
+void CSpatialPartition::ElementMoved( SpatialPartitionHandle_t handle, const Vector& mins, const Vector& maxs )
+{
+	EntityInfo_t &entityInfo = EntityInfo( handle );
+	SpatialPartitionListMask_t listMask = entityInfo.m_fList;
+
+
+	if ( CLIENT_TREE != SERVER_TREE )
+	{
+		if ( listMask & PARTITION_ALL_CLIENT_EDICTS )
+		{
+			m_VoxelTrees[CLIENT_TREE].ElementMoved( handle, mins, maxs );
+			entityInfo.m_flags |= IN_CLIENT_TREE;
+		}
+
+		if ( listMask & ~PARTITION_ALL_CLIENT_EDICTS )
+		{
+			m_VoxelTrees[SERVER_TREE].ElementMoved( handle, mins, maxs );
+			entityInfo.m_flags |= IN_SERVER_TREE;
+		}
+	}
+	else
+	{
+		m_VoxelTrees[CLIENT_TREE].ElementMoved( handle, mins, maxs );
+		entityInfo.m_flags |= IN_CLIENT_TREE;
+	}
+}
+
+//-----------------------------------------------------------------------------
+// Purpose:
+//-----------------------------------------------------------------------------
+void CSpatialPartition::EnumerateElementsInBox( SpatialPartitionListMask_t listMask, const Vector& mins, const Vector& maxs, bool coarseTest, IPartitionEnumerator* pIterator )
+{
+	MDLCACHE_CRITICAL_SECTION_(g_pMDLCache);
+	CVoxelTree *pTree = VoxelTree( listMask );
+	InvokeQueryCallbacks( listMask );
+	pTree->EnumerateElementsInBox( listMask, mins, maxs, coarseTest, pIterator );
+	InvokeQueryCallbacks( listMask, true );
+}
+
+//-----------------------------------------------------------------------------
+// Purpose:
+//-----------------------------------------------------------------------------
+void CSpatialPartition::EnumerateElementsInSphere( SpatialPartitionListMask_t listMask, const Vector& origin, float radius, bool coarseTest, IPartitionEnumerator* pIterator )
+{
+	MDLCACHE_CRITICAL_SECTION_(g_pMDLCache);
+	CVoxelTree *pTree = VoxelTree( listMask );
+	InvokeQueryCallbacks( listMask );
+	pTree->EnumerateElementsInSphere( listMask, origin, radius, coarseTest, pIterator );
+	InvokeQueryCallbacks( listMask, true );
+}
+
+//-----------------------------------------------------------------------------
+// Purpose:
+//-----------------------------------------------------------------------------
+void CSpatialPartition::EnumerateElementsAlongRay( SpatialPartitionListMask_t listMask, const Ray_t& ray, bool coarseTest, IPartitionEnumerator* pIterator )
+{
+	MDLCACHE_CRITICAL_SECTION_(g_pMDLCache);
+	CVoxelTree *pTree = VoxelTree( listMask );
+	InvokeQueryCallbacks( listMask );
+	pTree->EnumerateElementsAlongRay( listMask, ray, coarseTest, pIterator );
+	InvokeQueryCallbacks( listMask, true );
+}
+
+//-----------------------------------------------------------------------------
+// Purpose:
+//-----------------------------------------------------------------------------
+void CSpatialPartition::EnumerateElementsAtPoint( SpatialPartitionListMask_t listMask, const Vector& pt, bool coarseTest, IPartitionEnumerator* pIterator )
+{
+	MDLCACHE_CRITICAL_SECTION_(g_pMDLCache);
+	CVoxelTree *pTree = VoxelTree( listMask );
+	InvokeQueryCallbacks( listMask );
+	pTree->EnumerateElementsAtPoint( listMask, pt, coarseTest, pIterator );
+	InvokeQueryCallbacks( listMask, true );
+}
+
+
+//-----------------------------------------------------------------------------
+// Purpose:
+//-----------------------------------------------------------------------------
+void CSpatialPartition::InsertIntoTree( SpatialPartitionHandle_t hPartition, const Vector& mins, const Vector& maxs ) 
+{
+	EntityInfo_t &entityInfo = EntityInfo( hPartition );
+	SpatialPartitionListMask_t listMask = entityInfo.m_fList;
+
+	if ( CLIENT_TREE != SERVER_TREE )
+	{
+		if ( ( listMask & PARTITION_ALL_CLIENT_EDICTS ) && !( entityInfo.m_flags & IN_CLIENT_TREE ) )
+		{
+			m_VoxelTrees[CLIENT_TREE].InsertIntoTree( hPartition, mins, maxs );
+			entityInfo.m_flags |= IN_CLIENT_TREE;
+		}
+
+		if ( ( listMask & ~PARTITION_ALL_CLIENT_EDICTS ) && !( entityInfo.m_flags & IN_SERVER_TREE ) )
+		{
+			m_VoxelTrees[SERVER_TREE].InsertIntoTree( hPartition, mins, maxs );
+			entityInfo.m_flags |= IN_SERVER_TREE;
+		}
+	}
+	else if ( !( entityInfo.m_flags & IN_CLIENT_TREE ) )
+	{
+		m_VoxelTrees[CLIENT_TREE].InsertIntoTree( hPartition, mins, maxs );
+		entityInfo.m_flags |= IN_CLIENT_TREE;
+	}
+}
+
+//-----------------------------------------------------------------------------
+// Purpose:
+//-----------------------------------------------------------------------------
+void CSpatialPartition::RemoveFromTree( SpatialPartitionHandle_t hPartition ) 
+{ 
+	EntityInfo_t &entityInfo = EntityInfo( hPartition );
+
+	if ( entityInfo.m_flags & IN_CLIENT_TREE )
+	{
+		m_VoxelTrees[CLIENT_TREE].RemoveFromTree( hPartition ); 
+		entityInfo.m_flags &= ~IN_CLIENT_TREE;
+	}
+
+	if ( entityInfo.m_flags & IN_SERVER_TREE )
+	{
+		m_VoxelTrees[SERVER_TREE].RemoveFromTree( hPartition ); 
+		entityInfo.m_flags &= ~IN_SERVER_TREE;
+	}
+}
+
+//-----------------------------------------------------------------------------
+// Purpose:
+//-----------------------------------------------------------------------------
+void CSpatialPartition::RenderObjectsInBox( const Vector &vecMin, const Vector &vecMax, float flTime )
+{
+}
+
+
+//-----------------------------------------------------------------------------
+// Purpose:
+//-----------------------------------------------------------------------------
+void CSpatialPartition::RenderObjectsInSphere( const Vector &vecCenter, float flRadius, float flTime )
+{
+}
+
+
+void CSpatialPartition::RenderObjectsAlongRay( const Ray_t& ray, float flTime )
+{
+}
+
+	
+//-----------------------------------------------------------------------------
+// Report stats
+//-----------------------------------------------------------------------------
+void CSpatialPartition::RenderAllObjectsInTree( float flTime )
+{
+	for ( int i = 0; i < NUM_TREES; i++ )
+	{
+		m_VoxelTrees[i].RenderAllObjectsInTree( flTime );
+	}
+}
+
+void CSpatialPartition::RenderObjectsInPlayerLeafs( const Vector &vecPlayerMin, const Vector &vecPlayerMax, float flTime )
+{
+	for ( int i = 0; i < NUM_TREES; i++ )
+	{
+		m_VoxelTrees[i].RenderObjectsInPlayerLeafs( vecPlayerMin, vecPlayerMax, flTime );
+	}
+}
+
+//-----------------------------------------------------------------------------
+// Report stats
+//-----------------------------------------------------------------------------
+void CVoxelTree::ReportStats( const char *pFileName )
+{
+	Msg( "Histogram : Entities per level\n" );
+	for ( int i = 0; i < m_nLevelCount; ++i )
+	{
+		Msg( "\t%d - %d\n", i, m_pVoxelHash[i].EntityCount() );
+	}
+}
+
+void CSpatialPartition::ReportStats( const char *pFileName )
+{
+	Msg( "Handle Count %d (%llu bytes)\n", m_aHandles.Count(), (uint64)( m_aHandles.Count() * ( sizeof(EntityInfo_t) + 2 * sizeof(SpatialPartitionHandle_t) ) ) );
+	for ( int i = 0; i < NUM_TREES; i++ )
+	{
+		m_VoxelTrees[i].ReportStats( pFileName );
+	}
+}
+
+static ConVar r_partition_level( "r_partition_level", "-1", FCVAR_CHEAT, "Displays a particular level of the spatial partition system. Use -1 to disable it." );
+
+void CVoxelTree::DrawDebugOverlays()
+{
+	int nLevel = r_partition_level.GetInt();
+	if ( nLevel < 0 )
+		return;
+
+	m_lock.LockForRead();
+	for ( int i = 0; i < m_nLevelCount; ++i )
+	{
+		if ( ( nLevel >= 0 ) && ( nLevel != i ) )
+			continue;
+
+		m_pVoxelHash[i].RenderGrid();
+		m_pVoxelHash[i].RenderAllObjectsInTree( 0.01f );
+	}
+	m_lock.UnlockRead();
+}
+
+void CSpatialPartition::DrawDebugOverlays()
+{
+	for ( int i = 0; i < NUM_TREES; i++ )
+	{
+		m_VoxelTrees[i].DrawDebugOverlays();
+	}
+}
+
+//=============================================================================
+ISpatialPartition *CreateSpatialPartition( const Vector& worldmin, const Vector& worldmax )
+{
+	CSpatialPartition *pResult = new CSpatialPartition;
+	pResult->Init( worldmin, worldmax );
+	return pResult;
+}
+
+void DestroySpatialPartition( ISpatialPartition *pPartition )
+{
+	Assert( pPartition != (ISpatialPartition*)&g_SpatialPartition );
+	delete pPartition;
+}
+
+