mesh.h

游戏编程精粹2第四章源码

/* Copyright (C) Tom Forsyth, 2001. 
 * All rights reserved worldwide.
 *
 * This software is provided "as is" without express or implied
 * warranties. You may freely copy and compile this source into
 * applications you distribute provided that the copyright text
 * below is included in the resulting source code, for example:
 * "Portions Copyright (C) Tom Forsyth, 2001"
 */
// Helper routines for manipulating large complex meshes.
// Pretty memory-hungry, but good for cross-referencing between
// edges, points and triangles.


#include "tomslib.h"


// Before including this file, #define the following:
//
// MESHPT_APP_DEFINED
// MESHTRI_APP_DEFINED
// MESHEDGE_APP_DEFINED
//
// These declarations are included in the declarations of the relevant
// classes. They may be defined to be nothing of course.
//
// For efficiency, also define some of the following according to use:
//
// MESHCTRL_EDGES_ALWAYS_ADDED_BEFORE_TRIS:
//		Set to 1 to enforce/assume that when adding a tri, all three edges
//		will exist. So all tris must have all three edge entries filled.
//		This is a speedup, and an error check, if that's what your app does.
//		The exception is if autocreation of edges is done for the MeshTri creator.
//		Similarly, before deleteing edges, make sure you have deleted all the
//		tris that use them
// MESHCTRL_PTS_ALWAYS_ADDED_BEFORE_TRIS:
//		Ditto, but for pts.
// MESHCTRL_PTS_ALWAYS_ADDED_BEFORE_EDGES:
//		Ditto, but pts must be added before edges are created.


#ifndef MESHCTRL_EDGES_ALWAYS_ADDED_BEFORE_TRIS
#error Please define MESHCTRL_EDGES_ALWAYS_ADDED_BEFORE_TRIS to 0 or 1
#endif
#ifndef MESHCTRL_PTS_ALWAYS_ADDED_BEFORE_TRIS
#error Please define MESHCTRL_PTS_ALWAYS_ADDED_BEFORE_TRIS to 0 or 1
#endif
#ifndef MESHCTRL_PTS_ALWAYS_ADDED_BEFORE_EDGES
#error Please define MESHCTRL_PTS_ALWAYS_ADDED_BEFORE_EDGES to 0 or 1
#endif
#ifndef MESHCTRL_PTS_ALWAYS_ADDED_BEFORE_EDGES
#error Please define MESHCTRL_PTS_ALWAYS_ADDED_BEFORE_EDGES to 0 or 1
#endif



class MeshPt;
class MeshEdge;
class MeshTri;



class MeshTri
{
	friend class MeshPt;
	friend class MeshEdge;

private:
	DlinkDefine(MeshTri,List);
	DWORD		dwListId;	// For use when doing consistency checks.

	void InternalDelete ( BOOL bBinUnusedEdges );

public:
	MeshPt		*pPt1;		// Points.
	MeshPt		*pPt2;
	MeshPt		*pPt3;
	MeshEdge	*pEdge12;	// Edges between point numbers.
	MeshEdge	*pEdge23;
	MeshEdge	*pEdge31;

	DlinkMethods(MeshTri,List);

	MESHTRI_APP_DEFINED		// App-defined data.

	MeshTri ( void );
	// Set pEdgeListRoot to non-NULL to autocreate edges.
	MeshTri ( MeshPt *pNewPt1, MeshPt *pNewPt2, MeshPt *pNewPt3, MeshTri *pListRoot = NULL, MeshEdge *pEdgeListRoot = NULL );
	~MeshTri ( void );
	// Set bBinUnusedEdges to TRUE to autodestroy edges.
	Delete ( BOOL bBinUnusedEdges = FALSE );
	// Which list is this tri in?
	MeshTri *QueryList ( void );
	// Move this tri to this list.
	void SetList ( MeshTri *pListRoot );
	// Checks that all edges and pts refer back to this tri,
	// and that they're in the respective lists.
	// If the lists are NULL, the check is not made.
	bool ConsistencyCheck ( MeshPt *pPtRoot = NULL, MeshEdge *pEdgeRoot = NULL, MeshTri *pTriRoot = NULL );

#if MESHCTRL_EDGES_ALWAYS_ADDED_BEFORE_TRIS
protected:
#else
public:
#endif
	// Add the edge to this tri.
	void AddEdge ( MeshEdge *pEdge );
	// Remove the edge from this tri.
	void RemoveEdge ( MeshEdge *pEdge );

#if MESHCTRL_PTS_ALWAYS_ADDED_BEFORE_TRIS
protected:
#else
public:
#endif
	// Remove the point from this tri.
	// NOTE! This is probably not a good thing to do.
	void RemovePt ( MeshPt *pPt );

};


class MeshEdge
{
	friend class MeshPt;
	friend class MeshTri;

private:
	DlinkDefine(MeshEdge,List);
	DWORD		dwListId;	// For use when doing consistency checks.

public:
	MeshPt		*pPt1;
	MeshPt		*pPt2;
	MeshTri		*pTri12;		// Tri that numbers pt1, pt2 in that order.
	MeshTri		*pTri21;		// Tri that numbers pt2, pt1 in that order.

	MeshEdge	*pEdgeProx;		// The edge that this is close to, if any.

	DlinkMethods(MeshEdge,List);

	MESHEDGE_APP_DEFINED		// App-defined data.

	BINARY_HEAP_VARS();			// Helper stuff.

	MeshEdge ( void );
	MeshEdge ( MeshPt *pNewPt1, MeshPt *pNewPt2, MeshEdge *pListRoot = NULL );
	~MeshEdge ( void );
	// Find the other triangle that uses this edge.
	MeshTri *OtherTri ( MeshTri *pTri );
	// Find the other point that uses this edge.
	MeshPt *OtherPt ( MeshPt *pPt );
	// Try to merge these two edges. Result is TRUE if it succeeded - note that the other edge will be NOT deleted.
	bool bTryToMergeEdges ( MeshEdge *pedge );
	// Which list is this Edge in?
	MeshEdge *QueryList ( void );
	// Move this Edge to this list.
	void SetList ( MeshEdge *pListRoot );
	// Makes these two edges prox.
	// The point prox data must agree.
	// Returns TRUE on success, or FALSE if it failed.
	bool AddProx ( MeshEdge *pEdge );
	// Find the proximity edge, if any.
	// Relies on the point proximity values having been set up.
	// If one is found, it is returned.
	MeshEdge *DoProxMatch ( void );
	// Removes any edge prox data.
	// Returns TRUE if there was some.
	// The pt prox data can still agree - it is not touched.
	bool RemoveProx ( void );
	// Checks that all pts and tris refer back to this edge,
	// and that they're in the respective lists.
	// If the lists are NULL, the check is not made.
	bool ConsistencyCheck ( MeshPt *pPtRoot = NULL, MeshEdge *pEdgeRoot = NULL, MeshTri *pTriRoot = NULL );

#if MESHCTRL_EDGES_ALWAYS_ADDED_BEFORE_TRIS
protected:
#else
public:
#endif
	// Remove the tri from this edge.
	void RemoveTri ( MeshTri *pTri );
	// Add the tri to this edge.
	void AddTri ( MeshTri *pTri );

#if MESHCTRL_PTS_ALWAYS_ADDED_BEFORE_EDGES
protected:
#else
public:
#endif
	// Remove the pt from this edge.
	// NOTE! This is probably not a good thing to do.
	void RemovePt ( MeshPt *pPt );

};



class MeshPt
{
	friend class MeshEdge;
	friend class MeshTri;

private:
	ArbitraryList<MeshEdge *>	EdgeList;	// The list of edges that use this point (in no order).
	ArbitraryList<MeshTri *>	TriList;	// The list of tris that use this point (in no order).
	ArbitraryList<MeshPt *>		ProxPtList;	// The list of prox pts (in no order).

	int							iCurTriNum;		// Used with First/NextTri.
	int							iCurEdgeNum;	// Used with First/NextEdge.
	int							iCurProxNum;	// Used with First/NextProx.

	DlinkDefine(MeshPt,List);
	DWORD						dwListId;	// For use when doing consistency checks.

public:
	MESHPT_APP_DEFINED						// App-defined data.

	DlinkMethods(MeshPt,List);

	MeshPt ( MeshPt *pListRoot = NULL );
	~MeshPt ( void );
	// Find the edge that uses this pt and the other one given.
	// NOTE! You almost never want to use this - almost always,
	// use FindTriEdge, because edges are typically created on-demand
	// when creating tris, and using this rout means that no two
	// points can have more than two tris use them, which lots of models
	// violate.
	MeshEdge *FindEdge ( MeshPt *pPt );
	// Find the first edge that uses this pt and the other given, and
	// also has a free triangle entry, assuming that the points are
	// used in that clockwise order. This allows two edges that share
	// the same points to exist, e.g. where multiple triangles share
	// the same edge (think of the diagonal of the tris of a back-to-back
	// quad - same edge, four tris.
	// The tri will use the points in the order *this,*pPt.
	MeshEdge *FindTriEdge ( MeshPt *pPt );
	// Find the tri that uses this pt and the other two given.
	// They must be in the order this,pPt1,pPt2 - not the other way round.
	MeshTri *FindTri ( MeshPt *pPt1, MeshPt *pPt2 );

	// Retired - there may be several tris like this - call FirstTri/NextTri.
	// Return the first tri in the list. MUST be called before calling NextTri().
	// If a non-NULL pPt is supplied, only tris using this,pPt in that order
	// are returned, otherwise all tris are returned.
	MeshTri *FirstTri ( MeshPt *pPt = NULL );
	// Return the next tri in the list. 
	// If a non-NULL pPt is supplied, only tris using this,pPt in that order
	// are returned, otherwise all tris are returned.
	MeshTri *NextTri ( MeshPt *pPt = NULL );
	// Terminate the current First/Next loop.
	// No need to call this if NULL was returned from NextTri().
	void EndTri ( void );

	// Return the first Edge in the list. MUST be called before calling NextEdge().
	// If a non-NULL pPt is supplied, only edges using this and pPt
	// are returned, otherwise all edges are returned.
	MeshEdge *FirstEdge ( MeshPt *pPt = NULL );
	// Return the next Edge in the list. 
	// If a non-NULL pPt is supplied, only edges using this and pPt
	// are returned, otherwise all edges are returned.
	MeshEdge *NextEdge ( MeshPt *pPt = NULL );
	// Terminate the current First/Next loop.
	// No need to call this if NULL was returned from NextEdge().
	void EndEdge ( void );

	// Add the given pt to the prox list (and vice versa).
	// If the pt was not already there, returns TRUE;
	// If bProxEdges is set to TRUE (default is FALSE ),
	// the edges that these two pts use are made prox if possible.
	bool AddProx ( MeshPt *pPt, bool bProxEdges = FALSE );
	// Remove the given pt from the prox list (and vice versa).
	// If the pt was there, returns TRUE.
	bool RemoveProx ( MeshPt *pPt );
	// Returns TRUE if the two pts are marked as being in proximity.
	bool CheckProx ( MeshPt *pPt );
	// Return the first prox pt. MUST be called before calling NextProx().
	MeshPt *FirstProx ( void );
	// Return the next prox pt.
	MeshPt *NextProx ( void );
	// Terminate the current First/Next loop.
	// No need to call this if NULL was returned from NextProx().
	void EndProx ( void );

	// Which list is this Pt in?
	MeshPt *QueryList ( void );
	// Move this Pt to this list.
	void SetList ( MeshPt *pListRoot );
	// Checks that all edges and tris refer back to this pt,
	// and that they're in the respective lists.
	// If the lists are NULL, the check is not made.
	bool ConsistencyCheck ( MeshPt *pPtRoot = NULL, MeshEdge *pEdgeRoot = NULL, MeshTri *pTriRoot = NULL );

#if MESHCTRL_PTS_ALWAYS_ADDED_BEFORE_EDGES
protected:
#else
public:
#endif
	// Remove the edge from this point.
	void RemoveEdge ( MeshEdge *pEdge );
	// Add the edge to this point.
	void AddEdge ( MeshEdge *pEdge );

#if MESHCTRL_PTS_ALWAYS_ADDED_BEFORE_TRIS
protected:
#else
public:
#endif
	// Remove the tri from this point.
	void RemoveTri ( MeshTri *pTri );
	// Add the tri to this point.
	void AddTri ( MeshTri *pTri );

};



inline MeshTri::MeshTri ( void )
{
	// Should only be used for list roots.
	pPt1 = NULL;
	pPt2 = NULL;
	pPt3 = NULL;
	pEdge12 = NULL;
	pEdge23 = NULL;
	pEdge31 = NULL;
	ListInit();
}

inline MeshTri::MeshTri ( MeshPt *pNewPt1, MeshPt *pNewPt2, MeshPt *pNewPt3, MeshTri *pListRoot, MeshEdge *pEdgeListRoot )
{
	ASSERT ( pNewPt1 != NULL );
	ASSERT ( pNewPt2 != NULL );
	ASSERT ( pNewPt3 != NULL );
	pPt1 = pNewPt1;
	pPt2 = pNewPt2;
	pPt3 = pNewPt3;
	pEdge12 = NULL;
	pEdge23 = NULL;
	pEdge31 = NULL;

	pPt1->AddTri ( this );
	pPt2->AddTri ( this );
	pPt3->AddTri ( this );

	pEdge12 = pPt1->FindTriEdge ( pPt2 );
	if ( ( pEdge12 == NULL ) && ( pEdgeListRoot != NULL ) )
	{
		// Autocreate the edge.
		pEdge12 = new MeshEdge ( pPt1, pPt2, pEdgeListRoot );
	}
#if MESHCTRL_EDGES_ALWAYS_ADDED_BEFORE_TRIS
	ASSERT ( pEdge12 != NULL );
#else
	if ( pEdge12 != NULL )
#endif
	{
		pEdge12->AddTri ( this );
	}

	pEdge23 = pPt2->FindTriEdge ( pPt3 );
	if ( ( pEdge23 == NULL ) && ( pEdgeListRoot != NULL ) )
	{
		// Autocreate the edge.
		pEdge23 = new MeshEdge ( pPt2, pPt3, pEdgeListRoot );
	}
#if MESHCTRL_EDGES_ALWAYS_ADDED_BEFORE_TRIS
	ASSERT ( pEdge23 != NULL );
#else
	if ( pEdge23 != NULL )
#endif
	{
		pEdge23->AddTri ( this );
	}

	pEdge31 = pPt3->FindTriEdge ( pPt1 );
	if ( ( pEdge31 == NULL ) && ( pEdgeListRoot != NULL ) )
	{
		// Autocreate the edge.
		pEdge31 = new MeshEdge ( pPt3, pPt1, pEdgeListRoot );
	}
#if MESHCTRL_EDGES_ALWAYS_ADDED_BEFORE_TRIS
	ASSERT ( pEdge31 != NULL );
#else
	if ( pEdge31 != NULL )
#endif
	{
		pEdge31->AddTri ( this );
	}

	ListInit();
	if ( pListRoot != NULL )
	{
		ListAddAfter ( pListRoot );
	}
}


inline void MeshTri::InternalDelete ( BOOL bBinUnusedEdges )
{
	// Remove edge references.
	if ( pEdge12 != NULL )
	{
		pEdge12->RemoveTri ( this );
		if ( bBinUnusedEdges && ( pEdge12->pTri12 == NULL ) && ( pEdge12->pTri21 == NULL ) )
		{
			// This edge is no longer in use.
			delete pEdge12;
		}
		pEdge12 = NULL;
	}
#if MESHCTRL_EDGES_ALWAYS_ADDED_BEFORE_TRIS
	else
	{
		// The only good reason is if this is a local var,
		// in which case everything should be NULL.
		ASSERT ( pEdge12 == NULL );
		ASSERT ( pEdge23 == NULL );
		ASSERT ( pEdge31 == NULL );
		ASSERT ( pPt1 == NULL );
		ASSERT ( pPt2 == NULL );
		ASSERT ( pPt3 == NULL );
	}
#endif

	if ( pEdge23 != NULL )
	{
		pEdge23->RemoveTri ( this );
		if ( bBinUnusedEdges && ( pEdge23->pTri12 == NULL ) && ( pEdge23->pTri21 == NULL ) )
		{
			// This edge is no longer in use.
			delete pEdge23;
		}
		pEdge23 = NULL;
	}
#if MESHCTRL_EDGES_ALWAYS_ADDED_BEFORE_TRIS
	else
	{
		// The only good reason is if this is a local var,
		// in which case everything should be NULL.
		ASSERT ( pEdge12 == NULL );
		ASSERT ( pEdge23 == NULL );
		ASSERT ( pEdge31 == NULL );
		ASSERT ( pPt1 == NULL );
		ASSERT ( pPt2 == NULL );
		ASSERT ( pPt3 == NULL );
	}
#endif

	if ( pEdge31 != NULL )
	{
		pEdge31->RemoveTri ( this );
		if ( bBinUnusedEdges && ( pEdge31->pTri12 == NULL ) && ( pEdge31->pTri21 == NULL ) )
		{
			// This edge is no longer in use.
			delete pEdge31;
		}
		pEdge31 = NULL;
	}
#if MESHCTRL_EDGES_ALWAYS_ADDED_BEFORE_TRIS
	else
	{
		// The only good reason is if this is a local var,
		// in which case everything should be NULL.
		ASSERT ( pEdge12 == NULL );
		ASSERT ( pEdge23 == NULL );
		ASSERT ( pEdge31 == NULL );
		ASSERT ( pPt1 == NULL );
		ASSERT ( pPt2 == NULL );
		ASSERT ( pPt3 == NULL );
	}
#endif

	// Remove point references.
	if ( pPt1 != NULL )
	{
		pPt1->RemoveTri ( this );
		pPt1 = NULL;
	}
#if MESHCTRL_PTS_ALWAYS_ADDED_BEFORE_TRIS
	else
	{
		// The only good reason is if this is a local var,
		// in which case everything should be NULL.
		ASSERT ( pEdge12 == NULL );
		ASSERT ( pEdge23 == NULL );
		ASSERT ( pEdge31 == NULL );
		ASSERT ( pPt1 == NULL );
		ASSERT ( pPt2 == NULL );
		ASSERT ( pPt3 == NULL );
	}
#endif

	if ( pPt2 != NULL )
	{
		pPt2->RemoveTri ( this );
		pPt2 = NULL;
	}
#if MESHCTRL_PTS_ALWAYS_ADDED_BEFORE_TRIS
	else
	{
		// The only good reason is if this is a local var,
		// in which case everything should be NULL.
		ASSERT ( pEdge12 == NULL );
		ASSERT ( pEdge23 == NULL );
		ASSERT ( pEdge31 == NULL );
		ASSERT ( pPt1 == NULL );
		ASSERT ( pPt2 == NULL );
		ASSERT ( pPt3 == NULL );
	}
#endif

	if ( pPt3 != NULL )
	{