1HEADmaster

1 files changed, 1128 insertions, 0 deletions

diff --git a/hammer/dispsubdiv.cpp b/hammer/dispsubdiv.cpp
new file mode 100644
index 0000000..1a917b3
--- /dev/null
+++ b/hammer/dispsubdiv.cpp
@@ -0,0 +1,1128 @@
+//========= Copyright Valve Corporation, All rights reserved. ============//
+//
+// Purpose: 
+//
+// $NoKeywords: $
+//
+//=============================================================================//
+
+#include <stdafx.h>
+#include "DispSubdiv.h"
+#include "MapDisp.h"
+#include "UtlLinkedList.h"
+#include "utlvector.h"
+#include "GlobalFunctions.h"
+
+// memdbgon must be the last include file in a .cpp file!!!
+#include <tier0/memdbgon.h>
+
+//=============================================================================
+//
+// Editable Displacement Subdivision Mesh Implementation
+//
+class CEditDispSubdivMesh : public IEditDispSubdivMesh
+{
+public: // functions
+
+	void Init( void );
+	void Shutdown( void );
+
+	void AddDispTo( CMapDisp *pDisp  );
+	void GetDispFrom( CMapDisp *pDisp );
+
+	void DoCatmullClarkSubdivision( void );
+
+public: // typedefs, enums, structs
+
+	enum { EDITDISP_QUADSIZE = 4 };			// should be in mapdisp (general define)
+
+private: // typedefs, enums, structs
+
+	typedef int SubdivPointHandle_t;
+	typedef int SubdivEdgeHandle_t;
+	typedef int SubdivQuadHandle_t;
+
+	enum { NUM_SUBDIV_LEVELS = 4 };			// number of subdivision levels
+
+	enum
+	{
+		SUBDIV_DISPPOINTS = 512,
+		SUBDIV_DISPEDGES = 1024,
+		SUBDIV_DISPQUADS = 512
+	};
+
+	enum
+	{
+		SUBDIV_POINTORDINARY = 0,
+		SUBDIV_POINTCORNER = 1,
+		SUBDIV_POINTCREASE = 2
+	};
+
+	struct SubdivPoint_t
+	{
+		Vector				m_vPoint;
+		Vector				m_vNormal;
+		Vector				m_vNewPoint;
+		Vector				m_vNewNormal;
+		unsigned short		m_uType;
+		unsigned short		m_uValence;
+		SubdivEdgeHandle_t	m_EdgeHandles[EDITDISP_QUADSIZE*4];
+	};
+
+	struct SubdivEdge_t
+	{
+		Vector				m_vNewEdgePoint;
+		Vector				m_vNewEdgeNormal;
+		SubdivPointHandle_t	m_PointHandles[2];
+		SubdivQuadHandle_t	m_QuadHandles[2];
+		float				m_flSharpness;
+		bool				m_bActive;
+	};
+
+	struct SubdivQuad_t
+	{
+		// generated
+		Vector				m_vCentroid;						// quad center
+		Vector				m_vNormal;							// quad normal
+		
+		// linkage
+		SubdivQuadHandle_t	m_ndxParent;						// parent quad index
+		SubdivQuadHandle_t	m_ndxChild[EDITDISP_QUADSIZE];		// chilren (4 of them) indices
+		
+		// quad data
+		SubdivPointHandle_t	m_PointHandles[EDITDISP_QUADSIZE];	// point indices - unique list
+		SubdivEdgeHandle_t	m_EdgeHandles[EDITDISP_QUADSIZE];	// edge indices - unique list
+
+		// disp/quad mapping
+		EditDispHandle_t	m_EditDispHandle;
+		short				m_Level;							// level of quad in the hierarchy (tree)
+		short				m_QuadIndices[EDITDISP_QUADSIZE];	// quad indices (in the X x X displacement surface)
+	};
+
+private: // functions
+
+	SubdivPoint_t *GetPoint( SubdivPointHandle_t ptHandle );
+	SubdivEdge_t *GetEdge( SubdivEdgeHandle_t edgeHandle );
+	SubdivQuad_t *GetQuad( SubdivQuadHandle_t quadHandle );
+
+	void Point_Init( SubdivPointHandle_t ptHandle );
+	void Point_CalcNewPoint( SubdivPointHandle_t ptHandle );
+	void Point_PointOrdinary( SubdivPoint_t *pPoint );
+	void Point_PointCorner( SubdivPoint_t *pPoint );
+	void Point_PointCrease( SubdivPoint_t *pPoint );
+
+	void Edge_Init( SubdivEdgeHandle_t edgeHandle );
+	void Edge_CalcNewPoint( SubdivEdgeHandle_t edgeHandle );
+
+	void Quad_Init( SubdivQuadHandle_t quadHandle );
+	void Quad_CalcCentroid( SubdivQuadHandle_t quadHandle );
+	void Quad_CalcNormal( SubdivQuadHandle_t quadHandle );
+
+	bool CompareSubdivPoints( Vector const &pt1, Vector const &pt2, float flTolerance );
+	bool CompareSubdivEdges( SubdivPointHandle_t ptEdge0Handle0, SubdivPointHandle_t ptEdge0Handle1,
+							 SubdivPointHandle_t ptEdge1Handle0, SubdivPointHandle_t ptEdge1Handle1 );
+
+	SubdivPointHandle_t BuildSubdivPoint( Vector const &vPoint, Vector const &vNormal );
+	SubdivEdgeHandle_t BuildSubdivEdge( int ndxEdge, SubdivQuadHandle_t quadHandle,
+										SubdivQuadHandle_t parentHandle, int ndxChild );
+	SubdivQuadHandle_t BuildSubdivQuad( int ndxChild, SubdivQuadHandle_t parentHandle );
+
+	void CatmullClarkSubdivision( void );
+	void UpdateSubdivisionHierarchy( int ndxLevel );
+
+private: // variables
+
+	CUtlLinkedList<SubdivPoint_t, SubdivPointHandle_t>	m_Points;
+	CUtlLinkedList<SubdivEdge_t, SubdivEdgeHandle_t>	m_Edges;
+	CUtlLinkedList<SubdivQuad_t, SubdivQuadHandle_t>	m_Quads;
+};
+
+//-----------------------------------------------------------------------------
+// Purpose:
+//-----------------------------------------------------------------------------
+IEditDispSubdivMesh *CreateEditDispSubdivMesh( void )
+{
+	return new CEditDispSubdivMesh;
+}
+
+
+//-----------------------------------------------------------------------------
+// Purpose:
+//-----------------------------------------------------------------------------
+void DestroyEditDispSubdivMesh( IEditDispSubdivMesh **pSubdivMesh )
+{
+	if ( *pSubdivMesh )
+	{
+		delete *pSubdivMesh;
+		*pSubdivMesh = NULL;
+	}
+}
+
+
+//-----------------------------------------------------------------------------
+// Purpose:
+//-----------------------------------------------------------------------------
+CEditDispSubdivMesh::SubdivPoint_t *CEditDispSubdivMesh::GetPoint( SubdivPointHandle_t ptHandle )
+{
+	if ( !m_Points.IsValidIndex( ptHandle ) )
+		return NULL;
+
+	return &m_Points.Element( ptHandle );
+}
+
+
+//-----------------------------------------------------------------------------
+// Purpose:
+//-----------------------------------------------------------------------------
+CEditDispSubdivMesh::SubdivEdge_t *CEditDispSubdivMesh::GetEdge( SubdivEdgeHandle_t edgeHandle )
+{
+	if ( !m_Edges.IsValidIndex( edgeHandle ) )
+		return NULL;
+
+	return &m_Edges.Element( edgeHandle );
+}
+
+
+//-----------------------------------------------------------------------------
+// Purpose:
+//-----------------------------------------------------------------------------
+CEditDispSubdivMesh::SubdivQuad_t *CEditDispSubdivMesh::GetQuad( SubdivQuadHandle_t quadHandle )
+{
+	if ( !m_Quads.IsValidIndex( quadHandle ) )
+		return NULL;
+
+	return &m_Quads.Element( quadHandle );
+}
+
+
+//=============================================================================
+//
+// Subdivision Edit Displacement Point Functions 
+//
+
+//-----------------------------------------------------------------------------
+// Purpose:
+//-----------------------------------------------------------------------------
+void CEditDispSubdivMesh::Point_Init( SubdivPointHandle_t ptHandle )
+{
+	SubdivPoint_t *pPoint = GetPoint( ptHandle );
+	if ( pPoint )
+	{
+		VectorClear( pPoint->m_vPoint );
+		VectorClear( pPoint->m_vNormal );
+		VectorClear( pPoint->m_vNewPoint );
+		VectorClear( pPoint->m_vNewNormal );
+		
+		pPoint->m_uType = (unsigned short)-1;
+		pPoint->m_uValence = 0;
+
+		for ( int ndxEdge = 0; ndxEdge < ( EDITDISP_QUADSIZE*2 ); ndxEdge++ )
+		{
+			pPoint->m_EdgeHandles[ndxEdge] = m_Edges.InvalidIndex();
+		}			
+	}
+}
+
+
+//-----------------------------------------------------------------------------
+// Purpose:
+//-----------------------------------------------------------------------------
+void CEditDispSubdivMesh::Point_CalcNewPoint( SubdivPointHandle_t ptHandle )
+{
+	// get the point to act on
+	SubdivPoint_t *pPoint = GetPoint( ptHandle );
+	if ( !pPoint )
+		return;
+
+	switch ( pPoint->m_uType )
+	{
+	case SUBDIV_POINTORDINARY: { Point_PointOrdinary( pPoint ); break; }
+	case SUBDIV_POINTCORNER: { Point_PointCorner( pPoint ); break; }
+	case SUBDIV_POINTCREASE: { Point_PointCrease( pPoint ); break; }
+	}
+}
+
+
+//-----------------------------------------------------------------------------
+// Purpose:
+//-----------------------------------------------------------------------------
+void CEditDispSubdivMesh::Point_PointOrdinary( SubdivPoint_t *pPoint )
+{
+	//
+	// accumulate the edge data and multiply by the valence (coincident edge)
+	// ratio (squared)
+	//
+	Vector edgeAccumPoint( 0.0f, 0.0f, 0.0f );
+	Vector edgeAccumNormal( 0.0f, 0.0f, 0.0f );
+	for ( int ndxEdge = 0; ndxEdge < pPoint->m_uValence; ndxEdge++ )
+	{
+		SubdivEdge_t *pEdge = GetEdge( pPoint->m_EdgeHandles[ndxEdge] );
+		if ( pEdge )
+		{
+			VectorAdd( edgeAccumPoint, pEdge->m_vNewEdgePoint, edgeAccumPoint );
+			VectorAdd( edgeAccumNormal, pEdge->m_vNewEdgeNormal, edgeAccumNormal );
+		}
+	}
+
+	float ratio = 1.0f / ( float )( pPoint->m_uValence * pPoint->m_uValence );
+
+	VectorScale( edgeAccumPoint, ratio, edgeAccumPoint );
+	VectorScale( edgeAccumNormal, ratio, edgeAccumNormal );
+
+	//
+	// accumlate the centroid data from all neighboring quads and multiply by
+	// the valence (coincident edge) ratio (squared)
+	//
+	int					quadListCount = 0;
+	SubdivQuadHandle_t	quadList[32];
+
+	for ( int ndxEdge = 0; ndxEdge < pPoint->m_uValence; ndxEdge++ )
+	{
+		SubdivEdge_t *pEdge = GetEdge( pPoint->m_EdgeHandles[ndxEdge] );
+		if ( pEdge )
+		{
+			for ( int ndxQuad = 0; ndxQuad < 2; ndxQuad++ )
+			{
+				if ( pEdge->m_QuadHandles[ndxQuad] != m_Quads.InvalidIndex() )
+				{
+					int ndxList;
+					for ( ndxList = 0; ndxList < quadListCount; ndxList++ )
+					{
+						if( pEdge->m_QuadHandles[ndxQuad] == quadList[ndxList] )
+							break;
+					}
+
+					if( ndxList == quadListCount )
+					{
+						quadList[quadListCount] = pEdge->m_QuadHandles[ndxQuad];
+						quadListCount++;
+					}
+				}
+			}
+		}
+	}
+
+	Vector centroidAccum( 0.0f, 0.0f, 0.0f );
+	for ( int ndxQuad = 0; ndxQuad < quadListCount; ndxQuad++ )
+	{
+		SubdivQuadHandle_t quadHandle = quadList[ndxQuad];
+		Quad_CalcCentroid( quadHandle );
+		SubdivQuad_t *pQuad = GetQuad( quadHandle );
+		VectorAdd( centroidAccum, pQuad->m_vCentroid, centroidAccum );
+	}
+
+	VectorScale( centroidAccum, ratio, centroidAccum );
+
+	//
+	// 
+	//
+	ratio = ( ( float )pPoint->m_uValence - 2.0f ) / ( float )pPoint->m_uValence;
+
+	VectorScale( pPoint->m_vPoint, ratio, pPoint->m_vNewPoint );
+	VectorAdd( pPoint->m_vNewPoint, edgeAccumPoint, pPoint->m_vNewPoint );
+	VectorAdd( pPoint->m_vNewPoint, centroidAccum, pPoint->m_vNewPoint );
+
+	VectorScale( pPoint->m_vNormal, ratio, pPoint->m_vNewNormal );
+	VectorAdd( pPoint->m_vNewNormal, edgeAccumNormal, pPoint->m_vNewNormal );
+	VectorAdd( pPoint->m_vNewNormal, centroidAccum, pPoint->m_vNewNormal );
+}
+
+
+//-----------------------------------------------------------------------------
+// Purpose:
+//-----------------------------------------------------------------------------
+void CEditDispSubdivMesh::Point_PointCorner( SubdivPoint_t *pPoint )
+{
+	VectorCopy( pPoint->m_vPoint, pPoint->m_vNewPoint );
+	VectorCopy( pPoint->m_vNormal, pPoint->m_vNewNormal );
+}
+
+
+//-----------------------------------------------------------------------------
+// Purpose:
+//-----------------------------------------------------------------------------
+void CEditDispSubdivMesh::Point_PointCrease( SubdivPoint_t *pPoint )
+{
+	//
+	// accumulate the edge data and multiply by the valence (coincident edge)
+	// ratio (squared)
+	//
+	Vector edgeAccumPoint( 0.0f, 0.0f, 0.0f );
+	Vector edgeAccumNormal( 0.0f, 0.0f, 0.0f );
+	for ( int ndxEdge = 0; ndxEdge < pPoint->m_uValence; ndxEdge++ )
+	{
+		SubdivEdge_t *pEdge = GetEdge( pPoint->m_EdgeHandles[ndxEdge] );
+		if ( pEdge && ( pEdge->m_flSharpness > 0.0f ) )
+		{
+			VectorAdd( edgeAccumPoint, pEdge->m_vNewEdgePoint, edgeAccumPoint );
+			VectorAdd( edgeAccumNormal, pEdge->m_vNewEdgeNormal, edgeAccumNormal );
+		}
+	}
+
+	//
+	// 
+	//
+	VectorScale( pPoint->m_vPoint, 6.0f, pPoint->m_vNewPoint );
+	VectorAdd( pPoint->m_vNewPoint, edgeAccumPoint, pPoint->m_vNewPoint );
+	VectorScale( pPoint->m_vNewPoint, 0.125f, pPoint->m_vNewPoint );
+
+	VectorScale( pPoint->m_vNormal, 6.0f, pPoint->m_vNewNormal );
+	VectorAdd( pPoint->m_vNewNormal, edgeAccumNormal, pPoint->m_vNewNormal );
+	VectorScale( pPoint->m_vNewNormal, 0.125f, pPoint->m_vNewNormal );
+}
+
+
+//-----------------------------------------------------------------------------
+// Purpose:
+//-----------------------------------------------------------------------------
+void CEditDispSubdivMesh::Edge_Init( SubdivEdgeHandle_t edgeHandle )
+{
+	SubdivEdge_t *pEdge = GetEdge( edgeHandle );
+	if ( pEdge )
+	{
+		VectorClear( pEdge->m_vNewEdgePoint );
+		VectorClear( pEdge->m_vNewEdgeNormal );
+
+		pEdge->m_flSharpness = 1.0f;
+		pEdge->m_bActive = false;
+
+		for ( int ndx = 0; ndx < 2; ndx++ )
+		{
+			pEdge->m_PointHandles[ndx] = m_Points.InvalidIndex();
+			pEdge->m_QuadHandles[ndx] = m_Quads.InvalidIndex();
+		}
+	}
+}
+
+
+//-----------------------------------------------------------------------------
+// Purpose:
+//-----------------------------------------------------------------------------
+void CEditDispSubdivMesh::Edge_CalcNewPoint( SubdivEdgeHandle_t edgeHandle )
+{
+	SubdivEdge_t *pEdge = GetEdge( edgeHandle );
+	if ( !pEdge )
+		return;
+
+	if ( !pEdge->m_bActive )
+		return;
+
+	//
+	// get edge points
+	//
+	SubdivPoint_t *pPoint0 = GetPoint( pEdge->m_PointHandles[0] );
+	SubdivPoint_t *pPoint1 = GetPoint( pEdge->m_PointHandles[1] );
+	if ( !pPoint0 || !pPoint1 )
+		return;
+
+	//
+	// calculate the "sharp" new edge point
+	//
+	Vector vSharpPoint( 0.0f, 0.0f, 0.0f );
+	VectorAdd( pPoint0->m_vPoint, pPoint1->m_vPoint, vSharpPoint );
+	VectorScale( vSharpPoint, 0.5f, vSharpPoint );
+
+	Vector vSharpNormal( 0.0f, 0.0f, 0.0f );
+	VectorAdd( pPoint0->m_vNormal, pPoint1->m_vNormal, vSharpNormal );
+	VectorNormalize( vSharpNormal );
+
+	//
+	// calculate the "smooth" new edge point (if necessary)
+	//
+	Vector vSmoothPoint( 0.0f, 0.0f, 0.0f );
+	Vector vSmoothNormal( 0.0f, 0.0f, 0.0f );
+	if ( ( pEdge->m_QuadHandles[1] != m_Edges.InvalidIndex() ) && ( pEdge->m_flSharpness != 1.0f ) )
+	{
+		Quad_CalcCentroid( pEdge->m_QuadHandles[0] );
+		Quad_CalcCentroid( pEdge->m_QuadHandles[1] );
+		Quad_CalcNormal( pEdge->m_QuadHandles[0] );
+		Quad_CalcNormal( pEdge->m_QuadHandles[1] );
+		SubdivQuad_t *pQuad0 = GetQuad( pEdge->m_QuadHandles[0] );
+		SubdivQuad_t *pQuad1 = GetQuad( pEdge->m_QuadHandles[1] );
+
+		VectorAdd( pPoint0->m_vPoint, pPoint1->m_vPoint, vSmoothPoint );
+		VectorAdd( vSmoothPoint, pQuad0->m_vCentroid, vSmoothPoint );
+		VectorAdd( vSmoothPoint, pQuad1->m_vCentroid, vSmoothPoint );
+		VectorScale( vSmoothPoint, 0.25f, vSmoothPoint );
+
+		VectorAdd( pPoint0->m_vNormal, pPoint1->m_vNormal, vSmoothNormal );
+		VectorAdd( vSmoothNormal, pQuad0->m_vNormal, vSmoothNormal );
+		VectorAdd( vSmoothNormal, pQuad1->m_vNormal, vSmoothNormal );
+		VectorNormalize( vSmoothNormal );
+	}
+	else
+	{
+		pEdge->m_flSharpness = 1.0f;
+		Quad_CalcCentroid( pEdge->m_QuadHandles[0] );
+		Quad_CalcNormal( pEdge->m_QuadHandles[0] );
+	}
+
+	//
+	// calculate the new edge point
+	//
+	// ( 1 - edge(sharpness) ) * vSmooth + edge(sharpness) * vSharp
+	//
+	VectorScale( vSmoothPoint, ( 1.0f - pEdge->m_flSharpness ), vSmoothPoint );
+	VectorScale( vSharpPoint, pEdge->m_flSharpness, vSharpPoint );
+	VectorAdd( vSmoothPoint, vSharpPoint, pEdge->m_vNewEdgePoint );
+
+	VectorScale( vSmoothNormal, ( 1.0f - pEdge->m_flSharpness ), vSmoothNormal );
+	VectorScale( vSharpNormal, pEdge->m_flSharpness, vSharpNormal );
+	VectorAdd( vSmoothNormal, vSharpNormal, pEdge->m_vNewEdgeNormal );
+	VectorNormalize( pEdge->m_vNewEdgeNormal );
+}
+
+
+//-----------------------------------------------------------------------------
+// Purpose:
+//-----------------------------------------------------------------------------
+void CEditDispSubdivMesh::Quad_Init( SubdivQuadHandle_t quadHandle )
+{
+	SubdivQuad_t *pQuad = GetQuad( quadHandle );
+	if ( pQuad )
+	{
+		VectorClear( pQuad->m_vCentroid );
+		VectorClear( pQuad->m_vNormal );
+
+		pQuad->m_ndxParent = m_Quads.InvalidIndex();
+		pQuad->m_EditDispHandle = EDITDISPHANDLE_INVALID;
+		pQuad->m_Level = -1;
+
+		for ( int ndx = 0; ndx < EDITDISP_QUADSIZE; ndx++ )
+		{
+			pQuad->m_ndxChild[ndx] = m_Quads.InvalidIndex();
+			
+			pQuad->m_PointHandles[ndx] = m_Points.InvalidIndex();
+			pQuad->m_EdgeHandles[ndx] = m_Edges.InvalidIndex();
+			pQuad->m_QuadIndices[ndx] = -1;			
+		}
+	}
+}
+
+
+//-----------------------------------------------------------------------------
+// Purpose:
+//-----------------------------------------------------------------------------
+void CEditDispSubdivMesh::Quad_CalcCentroid( SubdivQuadHandle_t quadHandle )
+{
+	SubdivQuad_t *pQuad = GetQuad( quadHandle );
+	if ( pQuad )
+	{
+		VectorClear( pQuad->m_vCentroid );
+		for ( int ndxPt = 0; ndxPt < EDITDISP_QUADSIZE; ndxPt++ )
+		{
+			SubdivPoint_t *pPoint = GetPoint( pQuad->m_PointHandles[ndxPt] );
+			VectorAdd( pQuad->m_vCentroid, pPoint->m_vPoint, pQuad->m_vCentroid );
+		}
+
+		VectorScale( pQuad->m_vCentroid, 0.25f, pQuad->m_vCentroid );
+	}
+}
+
+
+//-----------------------------------------------------------------------------
+// Purpose:
+//-----------------------------------------------------------------------------
+void CEditDispSubdivMesh::Quad_CalcNormal( SubdivQuadHandle_t quadHandle )
+{
+	SubdivQuad_t *pQuad = GetQuad( quadHandle );
+	if ( pQuad )
+	{
+		SubdivPoint_t *pPoints[3];
+		Vector edges[2];
+
+		pPoints[0] = GetPoint( pQuad->m_PointHandles[0] );
+		pPoints[1] = GetPoint( pQuad->m_PointHandles[1] );
+		pPoints[2] = GetPoint( pQuad->m_PointHandles[2] );
+
+		VectorSubtract( pPoints[1]->m_vPoint, pPoints[0]->m_vPoint, edges[0] );
+		VectorSubtract( pPoints[2]->m_vPoint, pPoints[0]->m_vPoint, edges[1] );
+
+		CrossProduct( edges[1], edges[0], pQuad->m_vNormal );
+		VectorNormalize( pQuad->m_vNormal );
+	}
+}
+
+
+//-----------------------------------------------------------------------------
+// Purpose:
+//-----------------------------------------------------------------------------
+bool CEditDispSubdivMesh::CompareSubdivPoints( Vector const &pt1, Vector const &pt2, 
+											   float flTolerance )
+{
+	for ( int axis = 0 ; axis < 3 ; axis++ )
+	{
+		if ( fabs( pt1[axis] - pt2[axis] ) > flTolerance )
+			return false;
+	}
+	
+	return true;
+}
+
+
+//-----------------------------------------------------------------------------
+// Purpose:
+//-----------------------------------------------------------------------------
+bool CEditDispSubdivMesh::CompareSubdivEdges( SubdivPointHandle_t ptEdge0Handle0,
+											  SubdivPointHandle_t ptEdge0Handle1,
+											  SubdivPointHandle_t ptEdge1Handle0,
+											  SubdivPointHandle_t ptEdge1Handle1 )
+{
+	if ( ( ( ptEdge0Handle0 == ptEdge1Handle0 ) && ( ptEdge0Handle1 == ptEdge1Handle1 ) ) ||
+		 ( ( ptEdge0Handle0 == ptEdge1Handle1 ) && ( ptEdge0Handle1 == ptEdge1Handle0 ) ) )
+		return true;
+
+	return false;
+}
+
+
+//-----------------------------------------------------------------------------
+// Purpose:
+//-----------------------------------------------------------------------------
+CEditDispSubdivMesh::SubdivPointHandle_t CEditDispSubdivMesh::BuildSubdivPoint( Vector const &vPoint,
+														                        Vector const &vPointNormal )
+{
+	//
+	// build a "unique" point
+	//
+	SubdivPointHandle_t ptHandle;
+	for ( ptHandle = m_Points.Head(); ptHandle != m_Points.InvalidIndex();
+	      ptHandle = m_Points.Next( ptHandle ) )
+	{
+		SubdivPoint_t *pPoint = GetPoint( ptHandle );
+		if ( pPoint )
+		{
+			// compare (positions)
+			if ( CompareSubdivPoints( vPoint, pPoint->m_vPoint, 0.1f ) )
+				return ptHandle;
+		}
+	}
+
+	ptHandle = m_Points.AddToTail();	
+	Point_Init( ptHandle );
+	SubdivPoint_t *pPoint = GetPoint( ptHandle );
+	VectorCopy( vPoint, pPoint->m_vPoint );
+	VectorCopy( vPointNormal, pPoint->m_vNormal );
+
+	return ptHandle;
+}
+
+
+//-----------------------------------------------------------------------------
+// Purpose:
+//-----------------------------------------------------------------------------
+CEditDispSubdivMesh::SubdivEdgeHandle_t CEditDispSubdivMesh::BuildSubdivEdge( int ndxEdge, SubdivQuadHandle_t quadHandle,
+														                      SubdivQuadHandle_t parentHandle, int ndxChild )
+{
+	// get the quad
+	SubdivQuad_t *pQuad = GetQuad( quadHandle );
+	if ( !pQuad )
+		return m_Edges.InvalidIndex();
+
+	//
+	// define a unique edge (m_PointHandlesX2, m_QuadHandle)
+	//
+	SubdivEdgeHandle_t edgeHandle;
+	for ( edgeHandle = m_Edges.Head(); edgeHandle != m_Edges.InvalidIndex();
+	      edgeHandle = m_Edges.Next( edgeHandle ) )
+	{
+		SubdivEdge_t *pEdge = GetEdge( edgeHandle );
+		if ( pEdge )
+		{
+			// compare (point handles)
+			if ( CompareSubdivEdges( pQuad->m_PointHandles[ndxEdge], pQuad->m_PointHandles[(ndxEdge+1)%4],
+				                     pEdge->m_PointHandles[0], pEdge->m_PointHandles[1] ) )
+			{
+				// check to see if the quad is quad 0 or 1 (or if it needs to be quad 1)
+				if ( ( pEdge->m_QuadHandles[0] != quadHandle ) && 
+				 	 ( pEdge->m_QuadHandles[1] == m_Quads.InvalidIndex() ) )
+				{
+					pEdge->m_QuadHandles[1] = quadHandle;
+					pEdge->m_flSharpness = 0.0f;			// smooth edge (between two subdiv quads)
+				}
+
+				return edgeHandle;
+			}
+		}
+	}
+
+	edgeHandle = m_Edges.AddToTail();
+	Edge_Init( edgeHandle );
+	SubdivEdge_t *pEdge = GetEdge( edgeHandle );
+
+	pEdge->m_PointHandles[0] = pQuad->m_PointHandles[ndxEdge];
+	pEdge->m_PointHandles[1] = pQuad->m_PointHandles[(ndxEdge+1)%4];
+	pEdge->m_QuadHandles[0] = quadHandle;
+	pEdge->m_bActive = true;
+
+	// extra data for children (get edge sharpness from parent or 
+	// it may be an internal edge and its sharpness will be 0)
+	if( ndxChild != -1 )
+	{
+		if ( ( ndxEdge == ndxChild ) || ( ndxEdge == ( (ndxChild+3)%4 ) ) )
+		{
+			SubdivQuad_t *pParentQuad = GetQuad( parentHandle );
+			if ( pParentQuad )
+			{
+				SubdivEdge_t *pParentEdge = GetEdge( pParentQuad->m_EdgeHandles[ndxEdge] );
+				pEdge->m_flSharpness = pParentEdge->m_flSharpness;
+			}
+		}
+		else
+		{
+			pEdge->m_flSharpness = 0.0f;
+		}
+	}
+
+	return edgeHandle;
+}
+
+
+//-----------------------------------------------------------------------------
+// Purpose:
+//-----------------------------------------------------------------------------
+CEditDispSubdivMesh::SubdivQuadHandle_t CEditDispSubdivMesh::BuildSubdivQuad( int ndxChild, 
+																			  SubdivQuadHandle_t parentHandle )
+{
+	// get parent quad
+	SubdivQuad_t *pParentQuad = GetQuad( parentHandle );
+	if( !pParentQuad )
+		return m_Quads.InvalidIndex();
+
+	// allocate a new quad
+	SubdivQuadHandle_t quadHandle = m_Quads.AddToTail();
+	Quad_Init( quadHandle );
+	SubdivQuad_t *pQuad = GetQuad( quadHandle );
+	pQuad->m_ndxParent = parentHandle;
+	pQuad->m_EditDispHandle = pParentQuad->m_EditDispHandle;
+	pQuad->m_Level = pParentQuad->m_Level + 1;
+
+	switch ( ndxChild )
+	{
+	case 0:
+		{
+			// displacement quad indices
+			pQuad->m_QuadIndices[0] = pParentQuad->m_QuadIndices[0];
+			pQuad->m_QuadIndices[1] = ( pParentQuad->m_QuadIndices[0] + pParentQuad->m_QuadIndices[1] ) * 0.5f;
+			pQuad->m_QuadIndices[2] = ( pParentQuad->m_QuadIndices[0] + pParentQuad->m_QuadIndices[2] ) * 0.5f;
+			pQuad->m_QuadIndices[3] = ( pParentQuad->m_QuadIndices[0] + pParentQuad->m_QuadIndices[3] ) * 0.5f;
+
+			// new verts
+			SubdivEdge_t *pEdge0 = GetEdge( pParentQuad->m_EdgeHandles[0] );
+			SubdivEdge_t *pEdge3 = GetEdge( pParentQuad->m_EdgeHandles[3] );
+			if ( pEdge0 && pEdge3 )
+			{
+				pQuad->m_PointHandles[0] = pParentQuad->m_PointHandles[0];
+				pQuad->m_PointHandles[1] = BuildSubdivPoint( pEdge0->m_vNewEdgePoint, pEdge0->m_vNewEdgeNormal );
+				pQuad->m_PointHandles[2] = BuildSubdivPoint( pParentQuad->m_vCentroid, pParentQuad->m_vNormal );
+				pQuad->m_PointHandles[3] = BuildSubdivPoint( pEdge3->m_vNewEdgePoint, pEdge3->m_vNewEdgeNormal );
+			}
+
+			break;
+		}
+	case 1:
+		{
+			// displacement quad indices
+			pQuad->m_QuadIndices[0] = ( pParentQuad->m_QuadIndices[0] + pParentQuad->m_QuadIndices[1] ) * 0.5f;
+			pQuad->m_QuadIndices[1] = pParentQuad->m_QuadIndices[1];
+			pQuad->m_QuadIndices[2] = ( pParentQuad->m_QuadIndices[1] + pParentQuad->m_QuadIndices[2] ) * 0.5f;
+			pQuad->m_QuadIndices[3] = ( pParentQuad->m_QuadIndices[0] + pParentQuad->m_QuadIndices[2] ) * 0.5f;
+
+			// new verts
+			SubdivEdge_t *pEdge0 = GetEdge( pParentQuad->m_EdgeHandles[0] );
+			SubdivEdge_t *pEdge1 = GetEdge( pParentQuad->m_EdgeHandles[1] );
+			if ( pEdge0 && pEdge1 )
+			{
+				pQuad->m_PointHandles[0] = BuildSubdivPoint( pEdge0->m_vNewEdgePoint, pEdge0->m_vNewEdgeNormal );
+				pQuad->m_PointHandles[1] = pParentQuad->m_PointHandles[1];
+				pQuad->m_PointHandles[2] = BuildSubdivPoint( pEdge1->m_vNewEdgePoint, pEdge1->m_vNewEdgeNormal );
+				pQuad->m_PointHandles[3] = BuildSubdivPoint( pParentQuad->m_vCentroid, pParentQuad->m_vNormal );
+			}
+
+			break;
+		}
+	case 2:
+		{
+			// displacement quad indices
+			pQuad->m_QuadIndices[0] = ( pParentQuad->m_QuadIndices[0] + pParentQuad->m_QuadIndices[2] ) * 0.5f;
+			pQuad->m_QuadIndices[1] = ( pParentQuad->m_QuadIndices[1] + pParentQuad->m_QuadIndices[2] ) * 0.5f;
+			pQuad->m_QuadIndices[2] = pParentQuad->m_QuadIndices[2];
+			pQuad->m_QuadIndices[3] = ( pParentQuad->m_QuadIndices[2] + pParentQuad->m_QuadIndices[3] ) * 0.5f;
+
+			// new verts
+			SubdivEdge_t *pEdge1 = GetEdge( pParentQuad->m_EdgeHandles[1] );
+			SubdivEdge_t *pEdge2 = GetEdge( pParentQuad->m_EdgeHandles[2] );
+			if ( pEdge1 && pEdge2 )
+			{
+				pQuad->m_PointHandles[0] = BuildSubdivPoint( pParentQuad->m_vCentroid, pParentQuad->m_vNormal );
+				pQuad->m_PointHandles[1] = BuildSubdivPoint( pEdge1->m_vNewEdgePoint, pEdge1->m_vNewEdgeNormal );
+				pQuad->m_PointHandles[2] = pParentQuad->m_PointHandles[2];
+				pQuad->m_PointHandles[3] = BuildSubdivPoint( pEdge2->m_vNewEdgePoint, pEdge2->m_vNewEdgeNormal );
+			}
+
+			break;
+		}
+	case 3:
+		{
+			// displacement quad indices
+			pQuad->m_QuadIndices[0] = ( pParentQuad->m_QuadIndices[0] + pParentQuad->m_QuadIndices[3] ) * 0.5f;
+			pQuad->m_QuadIndices[1] = ( pParentQuad->m_QuadIndices[0] + pParentQuad->m_QuadIndices[2] ) * 0.5f;
+			pQuad->m_QuadIndices[2] = ( pParentQuad->m_QuadIndices[2] + pParentQuad->m_QuadIndices[3] ) * 0.5f;
+			pQuad->m_QuadIndices[3] = pParentQuad->m_QuadIndices[3];
+
+			// new verts
+			SubdivEdge_t *pEdge2 = GetEdge( pParentQuad->m_EdgeHandles[2] );
+			SubdivEdge_t *pEdge3 = GetEdge( pParentQuad->m_EdgeHandles[3] );
+			if ( pEdge2 && pEdge3 )
+			{
+				pQuad->m_PointHandles[0] = BuildSubdivPoint( pEdge3->m_vNewEdgePoint, pEdge3->m_vNewEdgeNormal );
+				pQuad->m_PointHandles[1] = BuildSubdivPoint( pParentQuad->m_vCentroid, pParentQuad->m_vNormal );
+				pQuad->m_PointHandles[2] = BuildSubdivPoint( pEdge2->m_vNewEdgePoint, pEdge2->m_vNewEdgeNormal );
+				pQuad->m_PointHandles[3] = pParentQuad->m_PointHandles[3];
+			}
+
+			break;
+		}
+	}
+
+	//
+	// buidl new quad edges
+	//
+	for ( int ndxEdge = 0; ndxEdge < 4; ndxEdge++ )
+	{
+		pQuad->m_EdgeHandles[ndxEdge] = BuildSubdivEdge( ndxEdge, quadHandle, parentHandle, ndxChild );
+	}
+
+	return quadHandle;
+}
+
+
+//-----------------------------------------------------------------------------
+// Purpose:
+//-----------------------------------------------------------------------------
+void CEditDispSubdivMesh::Init( void )
+{
+	// ensure capacity on all lists
+	IWorldEditDispMgr *pDispMgr = GetActiveWorldEditDispManager();
+	if( !pDispMgr )
+		return;
+
+	int selectCount = pDispMgr->SelectCount();	
+	m_Points.EnsureCapacity( SUBDIV_DISPPOINTS * selectCount );
+	m_Edges.EnsureCapacity( SUBDIV_DISPEDGES * selectCount );
+	m_Quads.EnsureCapacity( SUBDIV_DISPQUADS * selectCount );
+}
+
+
+//-----------------------------------------------------------------------------
+// Purpose:
+//-----------------------------------------------------------------------------
+void CEditDispSubdivMesh::Shutdown( void )
+{
+	// clear all lists
+	m_Points.Purge();
+	m_Edges.Purge();
+	m_Quads.Purge();
+}
+
+
+//-----------------------------------------------------------------------------
+// Purpose:
+//-----------------------------------------------------------------------------
+void CEditDispSubdivMesh::AddDispTo( CMapDisp *pDisp )
+{
+	// add a quad to the subdivision mesh
+	SubdivQuadHandle_t quadHandle = m_Quads.AddToTail();
+	Quad_Init( quadHandle );
+	SubdivQuad_t *pQuad = &m_Quads.Element( quadHandle );
+
+	// this is the parent!
+	pQuad->m_ndxParent = m_Quads.InvalidIndex();
+	pQuad->m_EditDispHandle = pDisp->GetEditHandle();
+	pQuad->m_Level = 0;
+
+	//
+	// get displacement data
+	//
+	int dispWidth = pDisp->GetWidth();
+	int dispHeight = pDisp->GetHeight();
+
+	//
+	// setup mapping between the displacement size and initial quad indices
+	//
+	pQuad->m_QuadIndices[0] = 0;
+	pQuad->m_QuadIndices[1] = dispWidth * ( dispHeight - 1 );
+	pQuad->m_QuadIndices[2] = ( dispWidth * dispHeight ) - 1;
+	pQuad->m_QuadIndices[3] = ( dispWidth - 1 );
+
+	//
+	// find point normals and neighbors -- "smooth"
+	// NOTE: this is slow -- should write a faster version (is offline process, do later)
+	//
+	IWorldEditDispMgr *pDispMgr = GetActiveWorldEditDispManager();
+	if( !pDispMgr )
+		return;
+
+	Vector vPoints[4];
+	Vector vPointNormals[4];
+	for( int ndxPt = 0; ndxPt < EDITDISP_QUADSIZE; ndxPt++ )
+	{
+		// get the base face normal of all surfaces touching this point!
+		pDisp->GetSurfNormal( vPointNormals[ndxPt] );
+
+		// get the point to compare to neighbors
+		pDisp->GetSurfPoint( ndxPt, vPoints[ndxPt] );
+
+		int count = pDispMgr->SelectCount();
+		for( int ndxSelect = 0; ndxSelect < count; ndxSelect++ )
+		{
+			CMapDisp *pSelectDisp = pDispMgr->GetFromSelect( ndxSelect );
+			if( !pSelectDisp || ( pSelectDisp == pDisp ) )
+				continue;
+
+			for( int ndxPt2 = 0; ndxPt2 < EDITDISP_QUADSIZE; ndxPt2++ )
+			{
+				Vector vPoint;
+				pSelectDisp->GetSurfPoint( ndxPt2, vPoint );
+				
+				if( CompareSubdivPoints( vPoints[ndxPt], vPoint, 0.01f ) )
+				{
+					Vector vNormal;
+					pSelectDisp->GetSurfNormal( vNormal );
+					VectorAdd( vPointNormals[ndxPt], vNormal, vPointNormals[ndxPt] );
+				}
+			}
+		}
+
+		VectorNormalize( vPointNormals[ndxPt] );
+	}
+
+	// build subdivision points
+	for( int ndxPt = 0; ndxPt < EDITDISP_QUADSIZE; ndxPt++ )
+	{
+		pQuad->m_PointHandles[ndxPt] = BuildSubdivPoint( vPoints[ndxPt], vPointNormals[ndxPt] );
+	}
+
+	// build subdivision edges
+	for( int ndxEdge = 0; ndxEdge < EDITDISP_QUADSIZE; ndxEdge++ )
+	{
+		pQuad->m_EdgeHandles[ndxEdge] = BuildSubdivEdge( ndxEdge, quadHandle, m_Quads.InvalidIndex(), -1 );
+	}
+}
+
+
+//-----------------------------------------------------------------------------
+// Purpose:
+//-----------------------------------------------------------------------------
+void CEditDispSubdivMesh::GetDispFrom( CMapDisp *pDisp )
+{
+	//
+	// find the parent quad with the id of the displacement
+	//
+	for ( SubdivQuadHandle_t quadHandle = m_Quads.Head(); quadHandle != m_Quads.InvalidIndex();
+	      quadHandle = m_Quads.Next( quadHandle ) )
+	{
+		SubdivQuad_t *pQuad = GetQuad( quadHandle );
+		if ( pQuad )
+		{
+			// find children quads that "belong" to this displacement
+			if( pQuad->m_EditDispHandle != pDisp->GetEditHandle() )
+				continue;
+
+			// get the data at the appropriate level -- (based on the size of the displacement)
+			if ( pQuad->m_Level != pDisp->GetPower() )
+				continue;
+
+			//
+			// fill in subdivision positions and normals
+			//
+			for ( int ndxPt = 0; ndxPt < 4; ndxPt++ )
+			{
+				SubdivPoint_t *pPoint = GetPoint( pQuad->m_PointHandles[ndxPt] );
+				if ( pPoint )
+				{
+					Vector vFlatVert, vSubVert;
+					pDisp->GetFlatVert( pQuad->m_QuadIndices[ndxPt], vFlatVert );
+					VectorSubtract( pPoint->m_vPoint, vFlatVert, vSubVert );
+					pDisp->UpdateVertPositionForSubdiv( pQuad->m_QuadIndices[ndxPt], vSubVert );
+					pDisp->SetSubdivNormal( pQuad->m_QuadIndices[ndxPt], pPoint->m_vNormal );
+				}
+			}
+		}
+	}
+
+	// tell the dispalcemet to update itself
+	pDisp->UpdateData();
+
+	// reset subdivision/subdivided flags
+	pDisp->SetReSubdivision( false );
+	pDisp->SetSubdivided( true );
+}
+
+
+//-----------------------------------------------------------------------------
+// Purpose:
+//-----------------------------------------------------------------------------
+void CEditDispSubdivMesh::DoCatmullClarkSubdivision( void )
+{
+	for ( int ndxLevel = 0; ndxLevel < NUM_SUBDIV_LEVELS; ndxLevel++ )
+	{
+		// subdivide
+		CatmullClarkSubdivision();
+
+		// update the subdivision hierarchy (tree)
+		UpdateSubdivisionHierarchy( ndxLevel );
+	}
+}
+
+
+//-----------------------------------------------------------------------------
+// Purpose:
+//-----------------------------------------------------------------------------
+void CEditDispSubdivMesh::CatmullClarkSubdivision( void )
+{
+	//
+	// step 1: calculate the "new edge points" for all edges
+	//
+	for ( SubdivEdgeHandle_t edgeHandle = m_Edges.Head(); edgeHandle != m_Edges.InvalidIndex();
+	      edgeHandle = m_Edges.Next( edgeHandle ) )
+	{
+		Edge_CalcNewPoint( edgeHandle );
+	}
+
+	//
+	// step 2: calculate the valence and edge list
+	//
+	for ( SubdivPointHandle_t ptHandle = m_Points.Head(); ptHandle != m_Points.InvalidIndex();
+	      ptHandle = m_Points.Next( ptHandle ) )
+	{
+		for ( SubdivEdgeHandle_t edgeHandle = m_Edges.Head(); edgeHandle != m_Edges.InvalidIndex();
+		      edgeHandle = m_Edges.Next( edgeHandle ) )
+		{
+			SubdivEdge_t *pEdge = GetEdge( edgeHandle );
+			if ( !pEdge->m_bActive )
+				continue;
+
+			if ( ( ptHandle == pEdge->m_PointHandles[0] ) || ( ptHandle == pEdge->m_PointHandles[1] ) )
+			{
+				SubdivPoint_t *pPoint = GetPoint( ptHandle );
+
+				if ( pPoint->m_uValence < ( EDITDISP_QUADSIZE*4 ) )
+				{
+					pPoint->m_EdgeHandles[pPoint->m_uValence] = edgeHandle;
+					pPoint->m_uValence++;
+				}
+			}
+		}
+	}
+
+	//
+	// step 3: determine the point's Type (Oridinary, Corner, Crease)
+	//
+	for ( SubdivPointHandle_t ptHandle = m_Points.Head(); ptHandle != m_Points.InvalidIndex(); ptHandle = m_Points.Next( ptHandle ) )
+	{
+		SubdivPoint_t *pPoint = GetPoint( ptHandle );
+		if ( pPoint )
+		{
+			int sharpCount = 0;
+			int sharpThreshold = pPoint->m_uValence - 1;
+			bool bHasNeighbors = false;
+
+			// initialize as oridinary -- determine otherwise
+			pPoint->m_uType = SUBDIV_POINTORDINARY;
+
+			for ( int ndxEdge = 0; ndxEdge < pPoint->m_uValence; ndxEdge++ )
+			{
+				SubdivEdge_t *pEdge = GetEdge( pPoint->m_EdgeHandles[ndxEdge] );
+				if ( pEdge )
+				{
+					if ( pEdge->m_flSharpness > 0.0f )
+					{
+						sharpCount++;
+					}
+
+					if ( pEdge->m_QuadHandles[1] != m_Quads.InvalidIndex() )
+					{
+						bHasNeighbors = true;
+					}
+				}
+			}
+
+			if ( !bHasNeighbors || ( sharpCount >= sharpThreshold ) )
+			{
+				pPoint->m_uType = SUBDIV_POINTCORNER;
+			}
+			else if( sharpCount > 1 )
+			{
+				pPoint->m_uType = SUBDIV_POINTCREASE;
+			}
+		}
+	}
+
+	//
+	// step 4: calculate the "new points" for all points
+	//
+	for ( SubdivPointHandle_t ptHandle = m_Points.Head(); ptHandle != m_Points.InvalidIndex(); ptHandle = m_Points.Next( ptHandle ) )
+	{
+		Point_CalcNewPoint( ptHandle );
+	}
+
+	//
+	// step 5: copy all "new point" data to point data
+	//
+	for ( SubdivPointHandle_t ptHandle = m_Points.Head(); ptHandle != m_Points.InvalidIndex(); ptHandle = m_Points.Next( ptHandle ) )
+	{
+		SubdivPoint_t *pPoint = GetPoint( ptHandle );
+		VectorCopy( pPoint->m_vNewPoint, pPoint->m_vPoint );
+		VectorCopy( pPoint->m_vNewNormal, pPoint->m_vNewNormal );
+		VectorClear( pPoint->m_vNewPoint );
+		VectorClear( pPoint->m_vNewNormal );
+
+		// reset valence
+		pPoint->m_uValence = 0;
+	}
+}
+
+
+//-----------------------------------------------------------------------------
+// Purpose:
+//-----------------------------------------------------------------------------
+void CEditDispSubdivMesh::UpdateSubdivisionHierarchy( int ndxLevel )
+{
+	int quadCount = m_Quads.Count();
+	SubdivQuadHandle_t quadHandle = m_Quads.Head();
+	int ndxQuad = 0;
+
+	while ( ( quadHandle != m_Quads.InvalidIndex() ) && ( ndxQuad < quadCount ) )
+	{
+		SubdivQuad_t *pQuad = GetQuad( quadHandle );
+		if ( pQuad )
+		{
+			// skip parent quads
+			if ( pQuad->m_ndxChild[0] != m_Quads.InvalidIndex() )
+			{
+				ndxQuad++;
+				quadHandle = m_Quads.Next( quadHandle );
+				continue;
+			}
+
+			for( int ndxChild = 0; ndxChild < 4; ndxChild++ )
+			{
+				pQuad->m_ndxChild[ndxChild] = BuildSubdivQuad( ndxChild, quadHandle );
+			}
+
+			// de-activate all edges (children's edges are active now!)
+			for ( int ndxEdge = 0; ndxEdge < 4; ndxEdge++ )
+			{
+				SubdivEdge_t *pEdge = GetEdge( pQuad->m_EdgeHandles[ndxEdge] );
+				if ( pEdge )
+				{
+					pEdge->m_bActive = false;
+				}
+			}
+		}
+
+		ndxQuad++;
+		quadHandle = m_Quads.Next( quadHandle );
+	}
+}