diff options
Diffstat (limited to 'hammer/dispsubdiv.cpp')
| -rw-r--r-- | hammer/dispsubdiv.cpp | 1128 |
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 ); + } +} |