diff options
Diffstat (limited to 'APEX_1.4/shared/general/meshutils')
4 files changed, 1591 insertions, 0 deletions
diff --git a/APEX_1.4/shared/general/meshutils/include/MeshIslandGeneration.h b/APEX_1.4/shared/general/meshutils/include/MeshIslandGeneration.h new file mode 100644 index 00000000..013c4049 --- /dev/null +++ b/APEX_1.4/shared/general/meshutils/include/MeshIslandGeneration.h @@ -0,0 +1,69 @@ +// This code contains NVIDIA Confidential Information and is disclosed to you +// under a form of NVIDIA software license agreement provided separately to you. +// +// Notice +// NVIDIA Corporation and its licensors retain all intellectual property and +// proprietary rights in and to this software and related documentation and +// any modifications thereto. Any use, reproduction, disclosure, or +// distribution of this software and related documentation without an express +// license agreement from NVIDIA Corporation is strictly prohibited. +// +// ALL NVIDIA DESIGN SPECIFICATIONS, CODE ARE PROVIDED "AS IS.". NVIDIA MAKES +// NO WARRANTIES, EXPRESSED, IMPLIED, STATUTORY, OR OTHERWISE WITH RESPECT TO +// THE MATERIALS, AND EXPRESSLY DISCLAIMS ALL IMPLIED WARRANTIES OF NONINFRINGEMENT, +// MERCHANTABILITY, AND FITNESS FOR A PARTICULAR PURPOSE. +// +// Information and code furnished is believed to be accurate and reliable. +// However, NVIDIA Corporation assumes no responsibility for the consequences of use of such +// information or for any infringement of patents or other rights of third parties that may +// result from its use. No license is granted by implication or otherwise under any patent +// or patent rights of NVIDIA Corporation. Details are subject to change without notice. +// This code supersedes and replaces all information previously supplied. +// NVIDIA Corporation products are not authorized for use as critical +// components in life support devices or systems without express written approval of +// NVIDIA Corporation. +// +// Copyright (c) 2008-2013 NVIDIA Corporation. All rights reserved. + +#ifndef MESH_ISLAND_GENERATION_H + +#define MESH_ISLAND_GENERATION_H + +#include "Ps.h" +#include "foundation/PxSimpleTypes.h" +#include "PsUserAllocated.h" + +namespace physx +{ + namespace general_meshutils2 + { + +class MeshIslandGeneration +{ +public: + + virtual PxU32 islandGenerate(PxU32 tcount,const PxU32 *indices,const PxF32 *vertices) = 0; + virtual PxU32 islandGenerate(PxU32 tcount,const PxU32 *indices,const PxF64 *vertices) = 0; + + // sometimes island generation can produce co-planar islands. Slivers if you will. If you are passing these islands into a geometric system + // that wants to turn them into physical objects, they may not be acceptable. In this case it may be preferable to merge the co-planar islands with + // other islands that it 'touches'. + virtual PxU32 mergeCoplanarIslands(const PxF32 *vertices) = 0; + virtual PxU32 mergeCoplanarIslands(const PxF64 *vertices) = 0; + + virtual PxU32 mergeTouchingIslands(const PxF32 *vertices) = 0; + virtual PxU32 mergeTouchingIslands(const PxF64 *vertices) = 0; + + virtual PxU32 * getIsland(PxU32 index,PxU32 &tcount) = 0; + + +}; + +MeshIslandGeneration * createMeshIslandGeneration(void); +void releaseMeshIslandGeneration(MeshIslandGeneration *cm); + +}; // end of namespace + using namespace general_meshutils2; +}; + +#endif diff --git a/APEX_1.4/shared/general/meshutils/include/RemoveTjunctions.h b/APEX_1.4/shared/general/meshutils/include/RemoveTjunctions.h new file mode 100644 index 00000000..0550f13c --- /dev/null +++ b/APEX_1.4/shared/general/meshutils/include/RemoveTjunctions.h @@ -0,0 +1,87 @@ +// This code contains NVIDIA Confidential Information and is disclosed to you +// under a form of NVIDIA software license agreement provided separately to you. +// +// Notice +// NVIDIA Corporation and its licensors retain all intellectual property and +// proprietary rights in and to this software and related documentation and +// any modifications thereto. Any use, reproduction, disclosure, or +// distribution of this software and related documentation without an express +// license agreement from NVIDIA Corporation is strictly prohibited. +// +// ALL NVIDIA DESIGN SPECIFICATIONS, CODE ARE PROVIDED "AS IS.". NVIDIA MAKES +// NO WARRANTIES, EXPRESSED, IMPLIED, STATUTORY, OR OTHERWISE WITH RESPECT TO +// THE MATERIALS, AND EXPRESSLY DISCLAIMS ALL IMPLIED WARRANTIES OF NONINFRINGEMENT, +// MERCHANTABILITY, AND FITNESS FOR A PARTICULAR PURPOSE. +// +// Information and code furnished is believed to be accurate and reliable. +// However, NVIDIA Corporation assumes no responsibility for the consequences of use of such +// information or for any infringement of patents or other rights of third parties that may +// result from its use. No license is granted by implication or otherwise under any patent +// or patent rights of NVIDIA Corporation. Details are subject to change without notice. +// This code supersedes and replaces all information previously supplied. +// NVIDIA Corporation products are not authorized for use as critical +// components in life support devices or systems without express written approval of +// NVIDIA Corporation. +// +// Copyright (c) 2008-2013 NVIDIA Corporation. All rights reserved. + +#ifndef REMOVE_TJUNCTIONS_H + +#define REMOVE_TJUNCTIONS_H + +#include "Ps.h" +#include "foundation/PxSimpleTypes.h" + +namespace physx +{ + namespace general_meshutils2 + { + +class RemoveTjunctionsDesc +{ +public: + RemoveTjunctionsDesc(void) + { + mVcount = 0; + mVertices = 0; + mTcount = 0; + mIndices = 0; + mIds = 0; + mTcountOut = 0; + mIndicesOut = 0; + mIdsOut = 0; + mEpsilon = 0.00000001f; + } + +// input + PxF32 mEpsilon; + PxF32 mDistanceEpsilon; + PxU32 mVcount; // input vertice count. + const PxF32 *mVertices; // input vertices as PxF32s or... + PxU32 mTcount; // number of input triangles. + const PxU32 *mIndices; // triangle indices. + const PxU32 *mIds; // optional triangle Id numbers. +// output.. + PxU32 mTcountOut; // number of output triangles. + const PxU32 *mIndicesOut; // output triangle indices + const PxU32 *mIdsOut; // output retained id numbers. +}; + +// Removes t-junctions from an input mesh. Does not generate any new data points, but may possible produce additional triangles and new indices. +class RemoveTjunctions +{ +public: + + virtual PxU32 removeTjunctions(RemoveTjunctionsDesc &desc) =0; // returns number of triangles output and the descriptor is filled with the appropriate results. + + +}; + +RemoveTjunctions * createRemoveTjunctions(void); +void releaseRemoveTjunctions(RemoveTjunctions *tj); + + }; + using namespace general_meshutils2; +}; + +#endif diff --git a/APEX_1.4/shared/general/meshutils/src/MeshIslandGeneration.cpp b/APEX_1.4/shared/general/meshutils/src/MeshIslandGeneration.cpp new file mode 100644 index 00000000..a6594d35 --- /dev/null +++ b/APEX_1.4/shared/general/meshutils/src/MeshIslandGeneration.cpp @@ -0,0 +1,764 @@ +// This code contains NVIDIA Confidential Information and is disclosed to you +// under a form of NVIDIA software license agreement provided separately to you. +// +// Notice +// NVIDIA Corporation and its licensors retain all intellectual property and +// proprietary rights in and to this software and related documentation and +// any modifications thereto. Any use, reproduction, disclosure, or +// distribution of this software and related documentation without an express +// license agreement from NVIDIA Corporation is strictly prohibited. +// +// ALL NVIDIA DESIGN SPECIFICATIONS, CODE ARE PROVIDED "AS IS.". NVIDIA MAKES +// NO WARRANTIES, EXPRESSED, IMPLIED, STATUTORY, OR OTHERWISE WITH RESPECT TO +// THE MATERIALS, AND EXPRESSLY DISCLAIMS ALL IMPLIED WARRANTIES OF NONINFRINGEMENT, +// MERCHANTABILITY, AND FITNESS FOR A PARTICULAR PURPOSE. +// +// Information and code furnished is believed to be accurate and reliable. +// However, NVIDIA Corporation assumes no responsibility for the consequences of use of such +// information or for any infringement of patents or other rights of third parties that may +// result from its use. No license is granted by implication or otherwise under any patent +// or patent rights of NVIDIA Corporation. Details are subject to change without notice. +// This code supersedes and replaces all information previously supplied. +// NVIDIA Corporation products are not authorized for use as critical +// components in life support devices or systems without express written approval of +// NVIDIA Corporation. +// +// Copyright (c) 2008-2013 NVIDIA Corporation. All rights reserved. + +#include "PsShare.h" +#include "foundation/PxAssert.h" +#include "foundation/PxSimpleTypes.h" +#include "PsUserAllocated.h" + +#include "MeshIslandGeneration.h" +#include "FloatMath.h" +#include "PsArray.h" +#include "PsHashMap.h" + +#pragma warning(disable:4100) + +namespace physx +{ + namespace general_meshutils2 + { + +typedef physx::Array< PxU32 > PxU32Vector; + +class Edge; +class Island; + +class AABB : public physx::UserAllocated +{ +public: + PxF32 mMin[3]; + PxF32 mMax[3]; +}; + +class Triangle : public physx::UserAllocated +{ +public: + Triangle(void) + { + mConsumed = false; + mIsland = 0; + mHandle = 0; + mId = 0; + } + + void minmax(const PxF32 *p,AABB &box) + { + if ( p[0] < box.mMin[0] ) box.mMin[0] = p[0]; + if ( p[1] < box.mMin[1] ) box.mMin[1] = p[1]; + if ( p[2] < box.mMin[2] ) box.mMin[2] = p[2]; + + if ( p[0] > box.mMax[0] ) box.mMax[0] = p[0]; + if ( p[1] > box.mMax[1] ) box.mMax[1] = p[1]; + if ( p[2] > box.mMax[2] ) box.mMax[2] = p[2]; + } + + void minmax(const PxF64 *p,AABB &box) + { + if ( (PxF32)p[0] < box.mMin[0] ) box.mMin[0] = (PxF32)p[0]; + if ( (PxF32)p[1] < box.mMin[1] ) box.mMin[1] = (PxF32)p[1]; + if ( (PxF32)p[2] < box.mMin[2] ) box.mMin[2] = (PxF32)p[2]; + if ( (PxF32)p[0] > box.mMax[0] ) box.mMax[0] = (PxF32)p[0]; + if ( (PxF32)p[1] > box.mMax[1] ) box.mMax[1] = (PxF32)p[1]; + if ( (PxF32)p[2] > box.mMax[2] ) box.mMax[2] = (PxF32)p[2]; + } + + void buildBox(const PxF32 *vertices_f,const PxF64 *vertices_d,PxU32 id); + + void render(PxU32 /*color*/) + { +// gRenderDebug->DebugBound(&mBox.mMin[0],&mBox.mMax[0],color,60.0f); + } + + void getTriangle(PxF32 *tri,const PxF32 *vertices_f,const PxF64 *vertices_d); + + PxU32 mHandle; + bool mConsumed; + Edge *mEdges[3]; + Island *mIsland; // identifies which island it is a member of + unsigned short mId; + AABB mBox; +}; + + +class Edge : public physx::UserAllocated +{ +public: + Edge(void) + { + mI1 = 0; + mI2 = 0; + mHash = 0; + mNext = 0; + mPrevious = 0; + mParent = 0; + mNextTriangleEdge = 0; + } + + void init(PxU32 i1,PxU32 i2,Triangle *parent) + { + PX_ASSERT( i1 < 65536 ); + PX_ASSERT( i2 < 65536 ); + + mI1 = i1; + mI2 = i2; + mHash = (i2<<16)|i1; + mReverseHash = (i1<<16)|i2; + mNext = 0; + mPrevious = 0; + mParent = parent; + } + + PxU32 mI1; + PxU32 mI2; + PxU32 mHash; + PxU32 mReverseHash; + + Edge *mNext; + Edge *mPrevious; + Edge *mNextTriangleEdge; + Triangle *mParent; +}; + +typedef physx::HashMap< PxU32, Edge * > EdgeHashMap; +typedef physx::Array< Triangle * > TriangleVector; + +class EdgeCheck //: public physx::UserAllocated +{ +public: + EdgeCheck(Triangle *t,Edge *e) + { + mTriangle = t; + mEdge = e; + } + + Triangle *mTriangle; + Edge *mEdge; +}; + +typedef physx::Array< EdgeCheck > EdgeCheckQueue; + +class Island : public physx::UserAllocated +{ +public: + Island(Triangle *t,Triangle * /*root*/) + { + mVerticesFloat = 0; + mVerticesDouble = 0; + t->mIsland = this; + mTriangles.pushBack(t); + mCoplanar = false; + physx::fm_initMinMax(mMin,mMax); + } + + void add(Triangle *t,Triangle * /*root*/) + { + t->mIsland = this; + mTriangles.pushBack(t); + } + + void merge(Island &isl) + { + TriangleVector::Iterator i; + for (i=isl.mTriangles.begin(); i!=isl.mTriangles.end(); ++i) + { + Triangle *t = (*i); + mTriangles.pushBack(t); + } + isl.mTriangles.clear(); + } + + bool isTouching(Island *isl,const PxF32 *vertices_f,const PxF64 *vertices_d) + { + bool ret = false; + + mVerticesFloat = vertices_f; + mVerticesDouble = vertices_d; + + if ( physx::fm_intersectAABB(mMin,mMax,isl->mMin,isl->mMax) ) // if the two islands has an intersecting AABB + { + // todo.. + } + + + return ret; + } + + + void SAP_DeletePair(const void* /*object0*/, const void* /*object1*/, void* /*user_data*/, void* /*pair_user_data*/) + { + } + + void render(PxU32 color) + { +// gRenderDebug->DebugBound(mMin,mMax,color,60.0f); + TriangleVector::Iterator i; + for (i=mTriangles.begin(); i!=mTriangles.end(); ++i) + { + Triangle *t = (*i); + t->render(color); + } + } + + + const PxF64 *mVerticesDouble; + const PxF32 *mVerticesFloat; + + PxF32 mMin[3]; + PxF32 mMax[3]; + bool mCoplanar; // marked as co-planar.. + TriangleVector mTriangles; +}; + + +void Triangle::getTriangle(PxF32 *tri,const PxF32 *vertices_f,const PxF64 *vertices_d) +{ + PxU32 i1 = mEdges[0]->mI1; + PxU32 i2 = mEdges[1]->mI1; + PxU32 i3 = mEdges[2]->mI1; + if ( vertices_f ) + { + const PxF32 *p1 = &vertices_f[i1*3]; + const PxF32 *p2 = &vertices_f[i2*3]; + const PxF32 *p3 = &vertices_f[i3*3]; + physx::fm_copy3(p1,tri); + physx::fm_copy3(p2,tri+3); + physx::fm_copy3(p3,tri+6); + } + else + { + const PxF64 *p1 = &vertices_d[i1*3]; + const PxF64 *p2 = &vertices_d[i2*3]; + const PxF64 *p3 = &vertices_d[i3*3]; + physx::fm_doubleToFloat3(p1,tri); + physx::fm_doubleToFloat3(p2,tri+3); + physx::fm_doubleToFloat3(p3,tri+6); + } +} + +void Triangle::buildBox(const PxF32 *vertices_f,const PxF64 *vertices_d,PxU32 id) +{ + mId = (unsigned short)id; + PxU32 i1 = mEdges[0]->mI1; + PxU32 i2 = mEdges[1]->mI1; + PxU32 i3 = mEdges[2]->mI1; + + if ( vertices_f ) + { + const PxF32 *p1 = &vertices_f[i1*3]; + const PxF32 *p2 = &vertices_f[i2*3]; + const PxF32 *p3 = &vertices_f[i3*3]; + mBox.mMin[0] = p1[0]; + mBox.mMin[1] = p1[1]; + mBox.mMin[2] = p1[2]; + mBox.mMax[0] = p1[0]; + mBox.mMax[1] = p1[1]; + mBox.mMax[2] = p1[2]; + minmax(p2,mBox); + minmax(p3,mBox); + } + else + { + const PxF64 *p1 = &vertices_d[i1*3]; + const PxF64 *p2 = &vertices_d[i2*3]; + const PxF64 *p3 = &vertices_d[i3*3]; + mBox.mMin[0] = (PxF32)p1[0]; + mBox.mMin[1] = (PxF32)p1[1]; + mBox.mMin[2] = (PxF32)p1[2]; + mBox.mMax[0] = (PxF32)p1[0]; + mBox.mMax[1] = (PxF32)p1[1]; + mBox.mMax[2] = (PxF32)p1[2]; + minmax(p2,mBox); + minmax(p3,mBox); + } + + PX_ASSERT(mIsland); + if ( mIsland ) + { + if ( mBox.mMin[0] < mIsland->mMin[0] ) mIsland->mMin[0] = mBox.mMin[0]; + if ( mBox.mMin[1] < mIsland->mMin[1] ) mIsland->mMin[1] = mBox.mMin[1]; + if ( mBox.mMin[2] < mIsland->mMin[2] ) mIsland->mMin[2] = mBox.mMin[2]; + + if ( mBox.mMax[0] > mIsland->mMax[0] ) mIsland->mMax[0] = mBox.mMax[0]; + if ( mBox.mMax[1] > mIsland->mMax[1] ) mIsland->mMax[1] = mBox.mMax[1]; + if ( mBox.mMax[2] > mIsland->mMax[2] ) mIsland->mMax[2] = mBox.mMax[2]; + } + +} + + +typedef physx::Array< Island * > IslandVector; + +class MyMeshIslandGeneration : public MeshIslandGeneration, public physx::UserAllocated +{ +public: + MyMeshIslandGeneration(void) + { + mTriangles = 0; + mEdges = 0; + mVerticesDouble = 0; + mVerticesFloat = 0; + } + + virtual ~MyMeshIslandGeneration(void) + { + reset(); + } + + void reset(void) + { + delete []mTriangles; + delete []mEdges; + mTriangles = 0; + mEdges = 0; + mTriangleEdges.clear(); + IslandVector::Iterator i; + for (i=mIslands.begin(); i!=mIslands.end(); ++i) + { + Island *_i = (*i); + delete _i; + } + mIslands.clear(); + } + + PxU32 islandGenerate(PxU32 tcount,const PxU32 *indices,const PxF64 *vertices) + { + mVerticesDouble = vertices; + mVerticesFloat = 0; + return islandGenerate(tcount,indices); + } + + PxU32 islandGenerate(PxU32 tcount,const PxU32 *indices,const PxF32 *vertices) + { + mVerticesDouble = 0; + mVerticesFloat = vertices; + return islandGenerate(tcount,indices); + } + + PxU32 islandGenerate(PxU32 tcount,const PxU32 *indices) + { + PxU32 ret = 0; + + reset(); + + mTcount = tcount; + mTriangles = PX_NEW(Triangle)[tcount]; + mEdges = PX_NEW(Edge)[tcount*3]; + Edge *e = mEdges; + + for (PxU32 i=0; i<tcount; i++) + { + Triangle &t = mTriangles[i]; + + PxU32 i1 = *indices++; + PxU32 i2 = *indices++; + PxU32 i3 = *indices++; + + t.mEdges[0] = e; + t.mEdges[1] = e+1; + t.mEdges[2] = e+2; + + e = addEdge(e,&t,i1,i2); + e = addEdge(e,&t,i2,i3); + e = addEdge(e,&t,i3,i1); + + } + + // while there are still edges to process... + while ( mTriangleEdges.size() != 0 ) + { + + EdgeHashMap::Iterator iter = mTriangleEdges.getIterator(); + + Triangle *t = iter->second->mParent; + + Island *i = PX_NEW(Island)(t,mTriangles); // the initial triangle... + removeTriangle(t); // remove this triangle from the triangle-edges hashmap + + mIslands.pushBack(i); + + // now keep adding to this island until we can no longer walk any shared edges.. + addEdgeCheck(t,t->mEdges[0]); + addEdgeCheck(t,t->mEdges[1]); + addEdgeCheck(t,t->mEdges[2]); + + while ( !mEdgeCheckQueue.empty() ) + { + + EdgeCheck e = mEdgeCheckQueue.popBack(); + + // Process all triangles which share this edge + Edge *edge = locateSharedEdge(e.mEdge); + + while ( edge ) + { + Triangle *t = edge->mParent; + PX_ASSERT(!t->mConsumed); + i->add(t,mTriangles); + removeTriangle(t); // remove this triangle from the triangle-edges hashmap + + // now keep adding to this island until we can no longer walk any shared edges.. + + if ( edge != t->mEdges[0] ) + { + addEdgeCheck(t,t->mEdges[0]); + } + + if ( edge != t->mEdges[1] ) + { + addEdgeCheck(t,t->mEdges[1]); + } + + if ( edge != t->mEdges[2] ) + { + addEdgeCheck(t,t->mEdges[2]); + } + + edge = locateSharedEdge(e.mEdge); // keep going until all shared edges have been processed! + } + + } + } + + ret = (PxU32)mIslands.size(); + + return ret; + } + + PxU32 * getIsland(PxU32 index,PxU32 &otcount) + { + PxU32 *ret = 0; + + mIndices.clear(); + if ( index < mIslands.size() ) + { + Island *i = mIslands[index]; + otcount = (PxU32)i->mTriangles.size(); + TriangleVector::Iterator j; + for (j=i->mTriangles.begin(); j!=i->mTriangles.end(); ++j) + { + Triangle *t = (*j); + mIndices.pushBack(t->mEdges[0]->mI1); + mIndices.pushBack(t->mEdges[1]->mI1); + mIndices.pushBack(t->mEdges[2]->mI1); + } + ret = &mIndices[0]; + } + + return ret; + } + +private: + + void removeTriangle(Triangle *t) + { + t->mConsumed = true; + + removeEdge(t->mEdges[0]); + removeEdge(t->mEdges[1]); + removeEdge(t->mEdges[2]); + + } + + + Edge * locateSharedEdge(Edge *e) + { + Edge *ret = 0; + + const EdgeHashMap::Entry *found = mTriangleEdges.find( e->mReverseHash ); + if ( found != NULL ) + { + ret = (*found).second; + PX_ASSERT( ret->mHash == e->mReverseHash ); + } + return ret; + } + + void removeEdge(Edge *e) + { + const EdgeHashMap::Entry *found = mTriangleEdges.find( e->mHash ); + + if ( found != NULL ) + { + Edge *prev = 0; + Edge *scan = (*found).second; + while ( scan && scan != e ) + { + prev = scan; + scan = scan->mNextTriangleEdge; + } + + if ( scan ) + { + if ( prev == 0 ) + { + if ( scan->mNextTriangleEdge ) + { + mTriangleEdges.erase(e->mHash); + mTriangleEdges[e->mHash] = scan->mNextTriangleEdge; + } + else + { + mTriangleEdges.erase(e->mHash); // no more polygons have an edge here + } + } + else + { + prev->mNextTriangleEdge = scan->mNextTriangleEdge; + } + } + else + { + PX_ASSERT(0); + } + } + else + { + PX_ASSERT(0); // impossible! + } + } + + + Edge * addEdge(Edge *e,Triangle *t,PxU32 i1,PxU32 i2) + { + + e->init(i1,i2,t); + + const EdgeHashMap::Entry *found = mTriangleEdges.find(e->mHash); + if ( found == NULL ) + { + mTriangleEdges[ e->mHash ] = e; + } + else + { + Edge *pn = (*found).second; + e->mNextTriangleEdge = pn; + mTriangleEdges.erase(e->mHash); + mTriangleEdges[e->mHash] = e; + } + + e++; + + return e; + } + + void addEdgeCheck(Triangle *t,Edge *e) + { + EdgeCheck ec(t,e); + mEdgeCheckQueue.pushBack(ec); + } + + PxU32 mergeCoplanarIslands(const PxF32 *vertices) + { + mVerticesFloat = vertices; + mVerticesDouble = 0; + return mergeCoplanarIslands(); + } + + PxU32 mergeCoplanarIslands(const PxF64 *vertices) + { + mVerticesDouble = vertices; + mVerticesFloat = 0; + return mergeCoplanarIslands(); + } + + // this island needs to be merged + void mergeTouching(Island * /*isl*/) + { +/* Island *touching = 0; + + IslandVector::Iterator i; + for (i=mIslands.begin(); i!=mIslands.end(); ++i) + { + Island *_i = (*i); + if ( !_i->mCoplanar ) // can't merge with coplanar islands! + { + if ( _i->isTouching(isl,mVerticesFloat,mVerticesDouble) ) + { + touching = _i; + } + } + }*/ + } + + PxU32 mergeCoplanarIslands(void) + { + PxU32 ret = 0; + + if ( !mIslands.empty() ) + { + + + PxU32 cp_count = 0; + PxU32 npc_count = 0; + + PxU32 count = (PxU32)mIslands.size(); + + for (PxU32 i=0; i<count; i++) + { + + PxU32 otcount; + const PxU32 *oindices = getIsland(i,otcount); + + if ( otcount ) + { + + bool isCoplanar; + + if ( mVerticesFloat ) + isCoplanar = physx::fm_isMeshCoplanar(otcount, oindices, mVerticesFloat, true); + else + isCoplanar = physx::fm_isMeshCoplanar(otcount, oindices, mVerticesDouble, true); + + if ( isCoplanar ) + { + Island *isl = mIslands[i]; + isl->mCoplanar = true; + cp_count++; + } + else + { + npc_count++; + } + } + else + { + PX_ASSERT(0); + } + } + + if ( cp_count ) + { + if ( npc_count == 0 ) // all islands are co-planar! + { + IslandVector temp = mIslands; + mIslands.clear(); + Island *isl = mIslands[0]; + mIslands.pushBack(isl); + for (PxU32 i=1; i<cp_count; i++) + { + Island *_i = mIslands[i]; + isl->merge(*_i); + delete _i; + } + } + else + { + + + Triangle *t = mTriangles; + for (PxU32 i=0; i<mTcount; i++) + { + t->buildBox(mVerticesFloat,mVerticesDouble,i); + t++; + } + + IslandVector::Iterator i; + for (i=mIslands.begin(); i!=mIslands.end(); ++i) + { + Island *isl = (*i); + + PxU32 color = 0x00FF00; + + if ( isl->mCoplanar ) + { + color = 0xFFFF00; + } + + PX_UNUSED(color); // Make compiler happy + + mergeTouching(isl); + + } + + IslandVector temp = mIslands; + mIslands.clear(); + for (i=temp.begin(); i!=temp.end(); i++) + { + Island *isl = (*i); + if ( isl->mCoplanar ) + { + delete isl; // kill it + } + else + { + mIslands.pushBack(isl); + } + } + ret = (PxU32)mIslands.size(); + } + } + else + { + ret = npc_count; + } + } + + + return ret; + } + + PxU32 mergeTouchingIslands(const PxF32 * /*vertices*/) + { + PxU32 ret = 0; + + return ret; + } + + PxU32 mergeTouchingIslands(const PxF64 * /*vertices*/) + { + PxU32 ret = 0; + + return ret; + } + + PxU32 mTcount; + Triangle *mTriangles; + Edge *mEdges; + EdgeHashMap mTriangleEdges; + IslandVector mIslands; + EdgeCheckQueue mEdgeCheckQueue; + const PxF64 *mVerticesDouble; + const PxF32 *mVerticesFloat; + PxU32Vector mIndices; +}; + + +MeshIslandGeneration * createMeshIslandGeneration(void) +{ + MyMeshIslandGeneration *mig = PX_NEW(MyMeshIslandGeneration); + return static_cast< MeshIslandGeneration *>(mig); +} + +void releaseMeshIslandGeneration(MeshIslandGeneration *cm) +{ + MyMeshIslandGeneration *mig = static_cast< MyMeshIslandGeneration *>(cm); + delete mig; +} + +}; // end of namespace +}; + diff --git a/APEX_1.4/shared/general/meshutils/src/RemoveTjunctions.cpp b/APEX_1.4/shared/general/meshutils/src/RemoveTjunctions.cpp new file mode 100644 index 00000000..b228ea7a --- /dev/null +++ b/APEX_1.4/shared/general/meshutils/src/RemoveTjunctions.cpp @@ -0,0 +1,671 @@ +// This code contains NVIDIA Confidential Information and is disclosed to you +// under a form of NVIDIA software license agreement provided separately to you. +// +// Notice +// NVIDIA Corporation and its licensors retain all intellectual property and +// proprietary rights in and to this software and related documentation and +// any modifications thereto. Any use, reproduction, disclosure, or +// distribution of this software and related documentation without an express +// license agreement from NVIDIA Corporation is strictly prohibited. +// +// ALL NVIDIA DESIGN SPECIFICATIONS, CODE ARE PROVIDED "AS IS.". NVIDIA MAKES +// NO WARRANTIES, EXPRESSED, IMPLIED, STATUTORY, OR OTHERWISE WITH RESPECT TO +// THE MATERIALS, AND EXPRESSLY DISCLAIMS ALL IMPLIED WARRANTIES OF NONINFRINGEMENT, +// MERCHANTABILITY, AND FITNESS FOR A PARTICULAR PURPOSE. +// +// Information and code furnished is believed to be accurate and reliable. +// However, NVIDIA Corporation assumes no responsibility for the consequences of use of such +// information or for any infringement of patents or other rights of third parties that may +// result from its use. No license is granted by implication or otherwise under any patent +// or patent rights of NVIDIA Corporation. Details are subject to change without notice. +// This code supersedes and replaces all information previously supplied. +// NVIDIA Corporation products are not authorized for use as critical +// components in life support devices or systems without express written approval of +// NVIDIA Corporation. +// +// Copyright (c) 2008-2013 NVIDIA Corporation. All rights reserved. + + +#include "PsShare.h" +#include "foundation/PxSimpleTypes.h" +#include "PsUserAllocated.h" +#include "PsArray.h" +#include "PsHashMap.h" +#include "RemoveTjunctions.h" +#include "FloatMath.h" +#include <limits.h> + +#pragma warning(disable:4189) + +namespace physx +{ + namespace general_meshutils2 + { + +class AABB : public physx::UserAllocated +{ +public: + physx::PxF32 mMin[3]; + physx::PxF32 mMax[3]; +}; + +bool gDebug=false; +PxU32 gCount=0; + +typedef physx::Array< PxU32 > PxU32Vector; + +class Triangle : public physx::UserAllocated +{ +public: + Triangle(void) + { + mPending = false; + mSplit = false; + mI1 = mI2 = mI3 = 0xFFFFFFFF; + mId = 0; + } + + Triangle(PxU32 i1,PxU32 i2,PxU32 i3,const float *vertices,PxU32 id) + { + mPending = false; + init(i1,i2,i3,vertices,id); + mSplit = false; + } + + void init(PxU32 i1,PxU32 i2,PxU32 i3,const float *vertices,PxU32 id) + { + mSplit = false; + mI1 = i1; + mI2 = i2; + mI3 = i3; + mId = id; + + const float *p1 = &vertices[mI1*3]; + const float *p2 = &vertices[mI2*3]; + const float *p3 = &vertices[mI3*3]; + + initMinMax(p1,p2,p3); + } + + void initMinMax(const float *p1,const float *p2,const float *p3) + { + physx::fm_copy3(p1,mBmin); + physx::fm_copy3(p1,mBmax); + physx::fm_minmax(p2,mBmin,mBmax); + physx::fm_minmax(p3,mBmin,mBmax); + } + + void init(const PxU32 *idx,const float *vertices,PxU32 id) + { + mSplit = false; + mI1 = idx[0]; + mI2 = idx[1]; + mI3 = idx[2]; + mId = id; + + const float *p1 = &vertices[mI1*3]; + const float *p2 = &vertices[mI2*3]; + const float *p3 = &vertices[mI3*3]; + + initMinMax(p1,p2,p3); + + } + + bool intersects(const float *pos,const float *p1,const float *p2,float epsilon) const + { + bool ret = false; + + float sect[3]; + physx::LineSegmentType type; + + float dist = fm_distancePointLineSegment(pos,p1,p2,sect,type,epsilon); + + if ( type == physx::LS_MIDDLE && dist < epsilon ) + { + ret = true; + } + + return ret; + } + + bool intersects(PxU32 i,const float *vertices,PxU32 &edge,float epsilon) const + { + bool ret = true; + + const float *pos = &vertices[i*3]; + const float *p1 = &vertices[mI1*3]; + const float *p2 = &vertices[mI2*3]; + const float *p3 = &vertices[mI3*3]; + if ( intersects(pos,p1,p2,epsilon) ) + { + edge = 0; + } + else if ( intersects(pos,p2,p3,epsilon) ) + { + edge = 1; + } + else if ( intersects(pos,p3,p1,epsilon) ) + { + edge = 2; + } + else + { + ret = false; + } + return ret; + } + + bool intersects(const Triangle *t,const float *vertices,PxU32 &intersection_index,PxU32 &edge,float epsilon) + { + bool ret = false; + + if ( physx::fm_intersectAABB(mBmin,mBmax,t->mBmin,t->mBmax) ) // only if the AABB's of the two triangles intersect... + { + + if ( t->intersects(mI1,vertices,edge,epsilon) ) + { + intersection_index = mI1; + ret = true; + } + + if ( t->intersects(mI2,vertices,edge,epsilon) ) + { + intersection_index = mI2; + ret = true; + } + + if ( t->intersects(mI3,vertices,edge,epsilon) ) + { + intersection_index = mI3; + ret = true; + } + + } + + return ret; + } + + bool mSplit:1; + bool mPending:1; + PxU32 mI1; + PxU32 mI2; + PxU32 mI3; + PxU32 mId; + float mBmin[3]; + float mBmax[3]; +}; + +class Edge : public physx::UserAllocated +{ +public: + Edge(void) + { + mNextEdge = 0; + mTriangle = 0; + mHash = 0; + } + + PxU32 init(Triangle *t,PxU32 i1,PxU32 i2) + { + mTriangle = t; + mNextEdge = 0; + PX_ASSERT( i1 < 65536 ); + PX_ASSERT( i2 < 65536 ); + if ( i1 < i2 ) + { + mHash = (i1<<16)|i2; + } + else + { + mHash = (i2<<16)|i1; + } + return mHash; + } + Edge *mNextEdge; + Triangle *mTriangle; + PxU32 mHash; +}; + + +typedef physx::Array< Triangle * > TriangleVector; +typedef physx::HashMap< PxU32, Edge * > EdgeMap; + +class MyRemoveTjunctions : public RemoveTjunctions, public physx::UserAllocated +{ +public: + MyRemoveTjunctions(void) + { + mInputTriangles = 0; + mEdges = 0; + mVcount = 0; + mVertices = 0; + mEdgeCount = 0; + } + virtual ~MyRemoveTjunctions(void) + { + release(); + } + + virtual PxU32 removeTjunctions(RemoveTjunctionsDesc &desc) + { + PxU32 ret = 0; + + mEpsilon = desc.mEpsilon; + + size_t TcountOut; + + desc.mIndicesOut = removeTjunctions(desc.mVcount, desc.mVertices, desc.mTcount, desc.mIndices, TcountOut, desc.mIds); + + PX_ASSERT( TcountOut < UINT_MAX ); + desc.mTcountOut = (PxU32)TcountOut; + + if ( !mIds.empty() ) + { + desc.mIdsOut = &mIds[0]; + } + + ret = desc.mTcountOut; + +#if 0 + bool check = ret != desc.mTcount; + while ( check ) + { + PxU32 tcount = ret; + PxU32 *indices = (PxU32 *)physx::PX_ALLOC(sizeof(PxU32)*tcount*3); + PxU32 *ids = (PxU32 *)physx::PX_ALLOC(sizeof(PxU32)*tcount); + memcpy(indices,desc.mIndicesOut,sizeof(PxU32)*ret*3); + memcpy(ids,desc.mIdsOut,sizeof(PxU32)*ret); + desc.mIndicesOut = removeTjunctions(desc.mVcount, desc.mVertices, tcount, indices, desc.mTcountOut, ids ); + if ( !mIds.empty() ) + { + desc.mIdsOut = &mIds[0]; + } + ret = desc.mTcountOut; + PX_FREE(indices); + PX_FREE(ids); + check = ret != tcount; + } +#endif + return ret; + } + + Edge * addEdge(Triangle *t,Edge *e,PxU32 i1,PxU32 i2) + { + PxU32 hash = e->init(t,i1,i2); + const EdgeMap::Entry *found = mEdgeMap.find(hash); + if ( found == NULL ) + { + mEdgeMap[hash] = e; + } + else + { + Edge *old_edge = (*found).second; + e->mNextEdge = old_edge; + mEdgeMap.erase(hash); + mEdgeMap[hash] = e; + } + e++; + mEdgeCount++; + return e; + } + + Edge * init(Triangle *t,const PxU32 *indices,const float *vertices,Edge *e,PxU32 id) + { + t->init(indices,vertices,id); + e = addEdge(t,e,t->mI1,t->mI2); + e = addEdge(t,e,t->mI2,t->mI3); + e = addEdge(t,e,t->mI3,t->mI1); + return e; + } + + void release(void) + { + mIds.clear(); + mEdgeMap.clear(); + mIndices.clear(); + mSplit.clear(); + delete []mInputTriangles; + delete []mEdges; + mInputTriangles = 0; + mEdges = 0; + mVcount = 0; + mVertices = 0; + mEdgeCount = 0; + + } + + virtual PxU32 * removeTjunctions(PxU32 vcount, + const float *vertices, + size_t tcount, + const PxU32 *indices, + size_t &tcount_out, + const PxU32 * ids) + { + PxU32 *ret = 0; + + release(); + + mVcount = vcount; + mVertices = vertices; + mTcount = (PxU32)tcount; + tcount_out = 0; + + mMaxTcount = (PxU32)tcount*2; + mInputTriangles = PX_NEW(Triangle)[mMaxTcount]; + Triangle *t = mInputTriangles; + + mEdges = PX_NEW(Edge)[mMaxTcount*3]; + mEdgeCount = 0; + + PxU32 id = 0; + + Edge *e = mEdges; + for (PxU32 i=0; i<tcount; i++) + { + if ( ids ) id = *ids++; + e =init(t,indices,vertices,e,id); + indices+=3; + t++; + } + + { + TriangleVector test; + + EdgeMap::Iterator i = mEdgeMap.getIterator(); + for (; !i.done(); ++i) + { + Edge *e = (*i).second; + if ( e->mNextEdge == 0 ) // open edge! + { + Triangle *t = e->mTriangle; + if ( !t->mPending ) + { + test.pushBack(t); + t->mPending = true; + } + } + } + + if ( !test.empty() ) + { + TriangleVector::Iterator i; + for (i=test.begin(); i!=test.end(); ++i) + { + Triangle *t = (*i); + locateIntersection(t); + } + } + + } + + while ( !mSplit.empty() ) + { + TriangleVector scan = mSplit; + mSplit.clear(); + TriangleVector::Iterator i; + for (i=scan.begin(); i!=scan.end(); ++i) + { + Triangle *t = (*i); + locateIntersection(t); + } + } + + + mIndices.clear(); + mIds.clear(); + + t = mInputTriangles; + for (PxU32 i=0; i<mTcount; i++) + { + mIndices.pushBack(t->mI1); + mIndices.pushBack(t->mI2); + mIndices.pushBack(t->mI3); + mIds.pushBack(t->mId); + t++; + } + + + mEdgeMap.clear(); + delete []mEdges; + mEdges = 0; + delete []mInputTriangles; + mInputTriangles = 0; + tcount_out = mIndices.size()/3; + ret = tcount_out ? &mIndices[0] : 0; +#ifdef _DEBUG + if ( ret ) + { + const PxU32 *scan = ret; + for (PxU32 i=0; i<tcount_out; i++) + { + PxU32 i1 = scan[0]; + PxU32 i2 = scan[1]; + PxU32 i3 = scan[2]; + PX_ASSERT( i1 != i2 && i1 != i3 && i2 != i3 ); + scan+=3; + } + } +#endif + return ret; + } + + Triangle * locateIntersection(Triangle *scan,Triangle *t) + { + Triangle *ret = 0; + + PxU32 t1 = (PxU32)(scan-mInputTriangles); + PX_UNUSED(t1); + + PxU32 t2 = (PxU32)(t-mInputTriangles); + PX_UNUSED(t2); + + PX_ASSERT( t1 < mTcount ); + PX_ASSERT( t2 < mTcount ); + + PX_ASSERT( scan->mI1 < mVcount ); + PX_ASSERT( scan->mI2 < mVcount ); + PX_ASSERT( scan->mI3 < mVcount ); + + PX_ASSERT( t->mI1 < mVcount ); + PX_ASSERT( t->mI2 < mVcount ); + PX_ASSERT( t->mI3 < mVcount ); + + + PxU32 intersection_index = 0; + PxU32 edge = 0; + + if ( scan != t && scan->intersects(t,mVertices,intersection_index,edge,mEpsilon) ) + { + + if ( t->mI1 == intersection_index || t->mI2 == intersection_index || t->mI3 == intersection_index ) + { + } + else + { + // here is where it intersects! + PxU32 i1,i2,i3; + PxU32 j1,j2,j3; + PxU32 id = t->mId; + + switch ( edge ) + { + case 0: + i1 = t->mI1; + i2 = intersection_index; + i3 = t->mI3; + j1 = intersection_index; + j2 = t->mI2; + j3 = t->mI3; + break; + case 1: + i1 = t->mI2; + i2 = intersection_index; + i3 = t->mI1; + j1 = intersection_index; + j2 = t->mI3; + j3 = t->mI1; + break; + case 2: + i1 = t->mI3; + i2 = intersection_index; + i3 = t->mI2; + j1 = intersection_index; + j2 = t->mI1; + j3 = t->mI2; + break; + default: + PX_ALWAYS_ASSERT(); + i1 = i2 = i3 = 0; + j1 = j2 = j3 = 0; + break; + } + + if ( mTcount < mMaxTcount ) + { + t->init(i1,i2,i3,mVertices,id); + Triangle *newt = &mInputTriangles[mTcount]; + newt->init(j1,j2,j3,mVertices,id); + mTcount++; + t->mSplit = true; + newt->mSplit = true; + + mSplit.pushBack(t); + mSplit.pushBack(newt); + ret = scan; + } + } + } + return ret; + } + + Triangle * testIntersection(Triangle *scan,Triangle *t) + { + Triangle *ret = 0; + + PxU32 t1 = (PxU32)(scan-mInputTriangles); + PX_UNUSED(t1); + + PxU32 t2 = (PxU32)(t-mInputTriangles); + PX_UNUSED(t2); + + PX_ASSERT( t1 < mTcount ); + PX_ASSERT( t2 < mTcount ); + + PX_ASSERT( scan->mI1 < mVcount ); + PX_ASSERT( scan->mI2 < mVcount ); + PX_ASSERT( scan->mI3 < mVcount ); + + PX_ASSERT( t->mI1 < mVcount ); + PX_ASSERT( t->mI2 < mVcount ); + PX_ASSERT( t->mI3 < mVcount ); + + + PxU32 intersection_index; + PxU32 edge; + + PX_ASSERT( scan != t ); + + if ( scan->intersects(t,mVertices,intersection_index,edge,mEpsilon) ) + { + // here is where it intersects! + PxU32 i1,i2,i3; + PxU32 j1,j2,j3; + PxU32 id = t->mId; + + switch ( edge ) + { + case 0: + i1 = t->mI1; + i2 = intersection_index; + i3 = t->mI3; + j1 = intersection_index; + j2 = t->mI2; + j3 = t->mI3; + break; + case 1: + i1 = t->mI2; + i2 = intersection_index; + i3 = t->mI1; + j1 = intersection_index; + j2 = t->mI3; + j3 = t->mI1; + break; + case 2: + i1 = t->mI3; + i2 = intersection_index; + i3 = t->mI2; + j1 = intersection_index; + j2 = t->mI1; + j3 = t->mI2; + break; + default: + PX_ALWAYS_ASSERT(); + i1 = i2 = i3 = 0; + j1 = j2 = j3 = 0; + break; + } + + if ( mTcount < mMaxTcount ) + { + t->init(i1,i2,i3,mVertices,id); + Triangle *newt = &mInputTriangles[mTcount]; + newt->init(j1,j2,j3,mVertices,id); + mTcount++; + t->mSplit = true; + newt->mSplit = true; + + mSplit.pushBack(t); + mSplit.pushBack(newt); + ret = scan; + } + } + return ret; + } + + Triangle * locateIntersection(Triangle *t) + { + Triangle *ret = 0; + + Triangle *scan = mInputTriangles; + + for (PxU32 i=0; i<mTcount; i++) + { + ret = locateIntersection(scan,t); + if ( ret ) + break; + scan++; + } + return ret; + } + + + Triangle *mInputTriangles; + PxU32 mVcount; + PxU32 mMaxTcount; + PxU32 mTcount; + const float *mVertices; + PxU32Vector mIndices; + PxU32Vector mIds; + TriangleVector mSplit; + PxU32 mEdgeCount; + Edge *mEdges; + EdgeMap mEdgeMap; + PxF32 mEpsilon; +}; + + + +RemoveTjunctions * createRemoveTjunctions(void) +{ + MyRemoveTjunctions *m = PX_NEW(MyRemoveTjunctions); + return static_cast< RemoveTjunctions *>(m); +} + +void releaseRemoveTjunctions(RemoveTjunctions *tj) +{ + MyRemoveTjunctions *m = static_cast< MyRemoveTjunctions *>(tj); + delete m; +} + + }; +};
\ No newline at end of file |