www.pudn.com > zfxcengine-0.1.0.zip > cePolygon.cpp

// $Id: cePolygon.cpp,v 1.10 2005/08/24 02:32:36 andreaskohn Exp $ 
#include  
#include "Math/ceMath.h" 
 
namespace ZFXCE 
{ 
	//////////////////////////////////////////////////////////////////////////////// 
	cePolygon::cePolygon() 
	{	 
		m_pPoints = NULL; 
		m_puiIndices = NULL; 
		m_uiNumOfPoints = 0; 
		m_uiNumOfIndices = 0; 
		memset(&m_AABB, 0, sizeof(ceAABB) ); 
		memset(&m_Plane, 0, sizeof(cePlane)); 
	} 
	//////////////////////////////////////////////////////////////////////////////// 
	cePolygon::~cePolygon() 
	{ 
		delete[] m_pPoints; 
		m_pPoints = 0; 
 
		delete[] m_puiIndices; 
		m_puiIndices = 0; 
 
		m_uiNumOfIndices = m_uiNumOfPoints = 0; 
 
		memset(&m_AABB, 0, sizeof(ceAABB) ); 
		memset(&m_Plane, 0, sizeof(cePlane)); 
	} 
	//////////////////////////////////////////////////////////////////////////////// 
	void cePolygon::Set(const ceVec3f* pPoints, UINT uiNumOfPoints,  
				const WORD* pIndices, UINT uiNumOfIndices) 
	{ 
		// Wenn noch alte Daten da, dann erstmal löschen 
		if (m_pPoints) 
			delete[] m_pPoints; 
		 
		m_pPoints = 0; 
 
		if (m_puiIndices) 
			delete [] m_puiIndices; 
		 
		m_puiIndices = 0; 
 
		m_pPoints = new ceVec3f[uiNumOfPoints]; 
		memset(&m_pPoints[0], 0, sizeof(ceVec3f) * uiNumOfPoints); 
 
		m_puiIndices = new WORD[uiNumOfIndices]; 
		memset(&m_puiIndices, 0, sizeof(WORD) * uiNumOfIndices); 
 
		m_uiNumOfIndices = uiNumOfIndices; 
		m_uiNumOfPoints = uiNumOfPoints; 
 
		// Daten nun komplett kopieren 
		memcpy(&m_pPoints[0], &pPoints[0], sizeof(ceVec3f) * uiNumOfPoints); 
		memcpy(&m_puiIndices[0], &pIndices[0], sizeof(WORD) * uiNumOfIndices); 
 
		// Die Ebene dieses Polygons berechnen, dazu brauchen wir erstmal einen Punkt... 
		ceVec3f vEdge0 = m_pPoints[ m_puiIndices[1] ] - m_pPoints[ m_puiIndices[0] ]; 
 
		bool bFoundPlane = false; 
		ceVec3f vEdge1; 
		vEdge0.Normalize(); 
		for(UINT i=0;bFoundPlane = FALSE; i++) 
		{ 
			if ( i+1 >= m_uiNumOfIndices) 
				break; 
 
			vEdge1 = m_pPoints[ m_puiIndices[i] ] - m_pPoints[ m_puiIndices[0] ]; 
			vEdge1.Normalize(); 
			if (vEdge0.AngleWith(vEdge1) < 0.000001f) { 
				bFoundPlane = true; 
			} 
		} 
 
		m_Plane.m_vNormal.Cross(vEdge0, vEdge1); 
		m_Plane.m_vNormal.Normalize(); 
		m_Plane.m_fDistance = -(m_Plane.m_vNormal * m_pPoints[0]); 
		m_Plane.m_vPointOnPlane = m_pPoints[0]; 
 
		CalcBoundingBox(); 
	} 
	//////////////////////////////////////////////////////////////////////////////// 
	void cePolygon::CalcBoundingBox() 
	{ 
		PUSH_FUNCTION; 
 
		ceVec3f vMax, vMin; 
 
		// Set a randomize point as start of search 
		vMax = vMin = m_pPoints[0]; 
 
		// Iterate sequenciell over all nodes to find limitations 
		for (size_t i=0; i < m_uiNumOfPoints; ++i) { 
			if (m_pPoints[i].x > vMax.x) 
				vMax.x = m_pPoints[i].x; 
			else if (m_pPoints[i].x < vMin.x) 
				vMin.x = m_pPoints[i].x; 
			if (m_pPoints[i].y > vMax.y) 
				vMax.y = m_pPoints[i].y; 
			else if (m_pPoints[i].y < vMin.y) 
				vMin.y = m_pPoints[i].y; 
			if (m_pPoints[i].z > vMax.z) 
				vMax.z = m_pPoints[i].z; 
			else if (m_pPoints[i].z < vMin.z) 
				vMin.z = m_pPoints[i].z; 
		} 
 
		// Set found limitations 
		m_AABB.m_vMax = vMax; 
		m_AABB.m_vMin = vMin; 
		m_AABB.m_vCenter = (vMax + vMin) * 0.5f; 
	} 
	//////////////////////////////////////////////////////////////////////////////// 
	void cePolygon::Clip(const cePlane& Plane, cePolygon* pFront,  
				cePolygon* pBack) const 
	{ 
		PUSH_FUNCTION; 
 
		if (NULL == pFront && NULL == pBack) 
			return; 
 
		UINT uiNumInFront=0, uiNumInBack=0; 
 
		ceVec3f *pInFront = NULL; 
		ceVec3f *pInBack  = NULL; 
		const size_t size = m_uiNumOfPoints*3; 
		pInFront = new ceVec3f[size]; 
		pInBack = new ceVec3f[size]; 
		ce_assert(NULL != pInFront && NULL != pInBack); 
		 
		// Classify first point of pointlist  
		switch (Plane.Classify(m_pPoints[0])){ 
		case ceFront: 
			pInFront[uiNumInFront++] = m_pPoints[0]; 
			break; 
		 
		case ceBack: 
			pInBack[uiNumInBack++] = m_pPoints[0]; 
			break; 
		 
		case cePlanar: 
			pInFront[uiNumInFront++] = m_pPoints[0]; 
			pInBack[uiNumInBack++] = m_pPoints[0]; 
			break; 
		default: 
			return; 
		} 
 
		// Der erste Index ist 1, da wir ja oben schon das erste Element setzen 
		for (UINT uiLoop=1; uiLoop < (m_uiNumOfPoints+1); uiLoop++) 
		{ 
			UINT uiCurrent = uiLoop; 
			if(uiLoop == m_uiNumOfPoints) 
				uiCurrent = 0; 
 
			// 2 benachbarte Punkte 
			const ceVec3f vA = m_pPoints[uiLoop-1]; 
			const ceVec3f vB = m_pPoints[uiCurrent]; 
 
			const INT uiClassA = Plane.Classify(vA); 
			//const UINT uiClassB = Plane.Classify(vB); 
 
			// Wenn planar, dann in beide Liste hinzufügen 
			if (uiClassA == cePlanar) 
			{ 
				pInFront[uiNumInFront++] = m_pPoints[uiCurrent]; 
				pInBack[uiNumInBack++] = m_pPoints[uiCurrent]; 
			} 
			else // Schneidet dieser Punkt die Ebene? 
			{ 
				ceRay Ray; 
				Ray.m_vOrigin = vA; 
				Ray.m_vDir = vB - vA; 
 
				FLOAT fLength = Ray.m_vDir.GetLength(); 
 
				if (0.0f != fLength) 
					Ray.m_vDir /= fLength; 
 
				ceVec3f vHit; 
				if( Ray.Intersects(Plane, FALSE, fLength, 0, &vHit) && uiClassA != cePlanar) 
				{ 
					pInBack[uiNumInBack++] = vHit; 
					uiNumInFront++; 
					pInFront[uiNumInFront] = vHit; 
 
					if(uiClassA == ceFront) 
					{ 
						if (0 != uiCurrent) 
							pInFront[uiNumInFront++] = m_pPoints[uiCurrent]; 
					} 
					else if (uiClassA == ceBack) 
					{ 
						if (0 != uiCurrent) { 
							uiNumInBack++; 
							pInBack[uiNumInBack] = m_pPoints[uiCurrent]; 
						}	 
					} 
				} 
				else 
				{ 
					if (0 == uiCurrent) 
						continue; 
 
					if (uiClassA == ceFront) 
						pInFront[uiNumInFront++] = m_pPoints[uiCurrent]; 
					else if (uiClassA == ceBack) 
						pInBack[uiNumInBack++] = m_pPoints[uiCurrent]; 
					else 
						return; 
				} 
			} 
		} 
 
		// Wir haben jetzt die beiden Polygone, fehlen noch die Indices 
		WORD usIndex0, usIndex1, usIndex2; 
	 
		WORD* pusFront = 0; 
		WORD* pusBack = 0; 
 
		if( uiNumInFront > 2) 
		{ 
			pusFront = new WORD[ (uiNumInFront-2) * 3]; 
 
			usIndex0 = 0; 
			usIndex1 = 1; 
			usIndex2 = 2; 
			for(UINT uiLoop=0; uiLoop < (uiNumInFront-2); uiLoop++) 
			{ 
				if (0 != uiLoop) 
				{ 
					usIndex1 = usIndex2; 
					usIndex2++; 
				} 
 
				pusFront[ uiLoop * 3] = usIndex0; 
				pusFront[ uiLoop * 3 + 1] = usIndex1; 
				pusFront[ uiLoop * 3 + 2] = usIndex2; 
			} 
		} 
		if (uiNumInBack > 2) 
		{ 
			pusBack = new WORD[ (uiNumInBack-2) * 3]; 
 
			usIndex0 = 0; 
			usIndex1 = 1; 
			usIndex2 = 2; 
			for (UINT uiLoop=0; uiLoop < (uiNumInBack-2); uiLoop++) 
			{ 
				if (0 != uiLoop) 
				{ 
					usIndex1 = usIndex2; 
					usIndex2++; 
				} 
 
				pusBack[ uiLoop * 3] = usIndex0; 
				pusBack[ uiLoop * 3 + 1] = usIndex1; 
				pusBack[ uiLoop * 3 + 2] = usIndex2; 
			} 
		} 
 
		if (0 != pFront && 0 != pusFront) 
		{ 
			pFront->Set(pInFront, uiNumInFront, pusFront, (uiNumInFront-2) * 3); 
 
			// Orientierung richten 
			if (pFront->GetPlane().m_vNormal * m_Plane.m_vNormal < 0.0f) 
				pFront->SwapFaces(); 
		} 
 
		if (0 != pBack && 0 != pusBack) 
		{ 
			pBack->Set(pInBack, uiNumInBack, pusBack, (uiNumInBack-2) * 3); 
 
			// Orientierung richten 
			if (pBack->GetPlane().m_vNormal * m_Plane.m_vNormal < 0.0f) 
				pBack->SwapFaces(); 
		} 
 
		// Release allocated memory 
		delete[] pInBack; 
		pInBack = 0; 
		delete[] pInFront; 
		pInFront = 0; 
		delete[] pusBack; 
		pusBack = 0; 
		delete[] pusFront; 
		pusFront = 0; 
	}	 
	//////////////////////////////////////////////////////////////////////////////// 
	void cePolygon::Clip(const ceAABB& AABB) 
	{ 
		cePolygon BackPolygon, ClippedPolygon; 
		cePlane Planes[6]; 
		BOOL bClipped=FALSE; 
 
		// Die Ebenen der Box berechnen, die Normalen zeigen nach außen 
		AABB.GetPlanes(Planes); 
 
		ClippedPolygon.CopyFrom( *this); 
 
		// Nun das Polygon gegen die Ebenen der Box clippen 
		for(UINT i=0; i < 6; i++) 
		{ 
			if(Planes[i].Classify(ClippedPolygon) == ceClipped) 
			{ 
				ClippedPolygon.Clip(Planes[i], 0, &BackPolygon); 
				ClippedPolygon.CopyFrom( BackPolygon); 
				bClipped = TRUE; 
			} 
		} 
		// Wenn das Polygon geändert wurde, dann kopieren wir es in dieses Objekt 
		// XXX: Das ist gefaehrlich, wenn das Verhalten nicht dokumentiert wird. Die andere Clip() 
		//      Methode tut das nicht. 
		if (bClipped) 
			this->CopyFrom(ClippedPolygon); 
	} 
	//////////////////////////////////////////////////////////////////////////////// 
	INT cePolygon::Cull(const ceAABB& AABB) const 
	{ 
		cePlane Planes[6]; 
		AABB.GetPlanes(Planes); 
 
		// Schneidet das Polygon die Box überhaupt 
		if(m_AABB.Intersects(AABB) == FALSE) 
			return ceCulled; 
 
		// Das Polygon KÖNNTE die Box nun schneiden, muss aber nicht 
		BOOL bFirst = TRUE; 
		UINT uiInside = 0; 
		for(UINT i=0; i < 6; i++) 
		{ 
			if(bFirst) 
			{ 
				for(UINT p=0; p < m_uiNumOfPoints; p++) 
				{ 
					if( AABB.Intersects( m_pPoints[i] ) ) 
						uiInside++; 
				} 
				bFirst = FALSE; 
 
				if(uiInside == m_uiNumOfPoints) 
					return ceVisible; 
			} 
 
			UINT uiCurrent = 0; 
			for (UINT uiLoop=1; uiLoop < (m_uiNumOfPoints+1); uiLoop++) 
			{ 
				if(uiLoop == m_uiNumOfPoints) 
					uiCurrent = 0; 
				else 
					uiCurrent = uiLoop; 
 
				ceRay Ray; 
				Ray.m_vOrigin = m_pPoints[uiLoop-1]; 
				Ray.m_vDir = m_pPoints[uiCurrent] - m_pPoints[uiLoop-1]; 
			 
				const FLOAT fLength = Ray.m_vDir.GetLength(); 
 
				if (fLength != 0.0f) 
					Ray.m_vDir /= fLength; 
 
				if(Ray.Intersects(Planes[i], FALSE, fLength, 0, 0) ) 
					return ceClipped; 
			} 
		} 
 
		return ceCulled; 
	} 
	//////////////////////////////////////////////////////////////////////////////// 
	void cePolygon::CopyFrom(const cePolygon& Polygon) 
	{ 
		Set(Polygon.m_pPoints, Polygon.m_uiNumOfPoints, Polygon.m_puiIndices, Polygon.m_uiNumOfIndices); 
	} 
	//////////////////////////////////////////////////////////////////////////////// 
	void cePolygon::SwapFaces() 
	{ 
		WORD* pusIndices = new WORD[m_uiNumOfIndices]; 
 
		for (UINT i=0; i < m_uiNumOfIndices; i++) 
			pusIndices[m_uiNumOfIndices-i-1] = m_puiIndices[i]; 
 
		m_Plane.m_vNormal *= -1.0f; 
		m_Plane.m_fDistance *= -1.0f; 
 
		delete[] m_puiIndices; 
		m_puiIndices = pusIndices; 
	} 
	//////////////////////////////////////////////////////////////////////////////// 
	bool cePolygon::Intersects(const ceRay& Ray, BOOL bCull, FLOAT* pF) const 
	{ 
		ceRay* pRay = (ceRay*) &Ray; 
 
		for (UINT i=0; i < m_uiNumOfIndices; i+=3) { 
			if (pRay->Intersects(m_pPoints[ m_puiIndices[i] ], 
								m_pPoints[ m_puiIndices[i+1] ], 
								m_pPoints[ m_puiIndices[i+2] ], 
								FALSE, pF) ) { 
				return true; 
			} 
			if (!bCull) { 
				if( pRay->Intersects(m_pPoints[ m_puiIndices[i+2] ], 
									m_pPoints[ m_puiIndices[i+1] ], 
									m_pPoints[ m_puiIndices[i] ], 
									FALSE, pF) ) { 
					return true; 
				} 
			} 
		} 
	 
		return false; 
	} 
	//////////////////////////////////////////////////////////////////////////////// 
	bool cePolygon::Intersects(const ceRay& Ray, BOOL bCull, FLOAT fL,  
				FLOAT* pF) const 
	{ 
		ceRay* pRay = (ceRay*) &Ray; 
 
		for (UINT i=0; i < m_uiNumOfIndices; i+=3) { 
			if( pRay->Intersects(m_pPoints[ m_puiIndices[i] ], 
								m_pPoints[ m_puiIndices[i+1] ], 
								m_pPoints[ m_puiIndices[i+2] ], 
								FALSE, fL, pF) ) { 
				return true; 
			} 
			if (!bCull) { 
				if( pRay->Intersects(m_pPoints[ m_puiIndices[i+2] ], 
									m_pPoints[ m_puiIndices[i+1] ], 
									m_pPoints[ m_puiIndices[i] ], 
									FALSE, fL, pF) ) { 
					return true; 
				} 
			} 
		} 
 
		return false; 
	} 
 
} // Namespace ZFXCE