Modified source engine (2017) developed by valve and leaked in 2020. Not for commercial purporses
You can not select more than 25 topics Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
 
 
 
 
 
 

1128 lines
35 KiB

//========= 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 );
}
}