Revision control
+ // Redistribution and use in source and binary forms, with or without
+ // modification, are permitted provided that the following conditions
+ // are met:
+ // * Redistributions of source code must retain the above copyright
+ // notice, this list of conditions and the following disclaimer.
+ // * Redistributions in binary form must reproduce the above copyright
+ // notice, this list of conditions and the following disclaimer in the
+ // documentation and/or other materials provided with the distribution.
+ // * Neither the name of NVIDIA CORPORATION nor the names of its
+ // contributors may be used to endorse or promote products derived
+ // from this software without specific prior written permission.
+ //
+ // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS ''AS IS'' AND ANY
+ // EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ // IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
+ // PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR
+ // CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
+ // EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
+ // PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
+ // PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
+ // OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ // (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+ // OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ //
+ // Copyright (c) 2008-2026 NVIDIA Corporation. All rights reserved.
+
+ #include "ExtTetSplitting.h"
+ #include "ExtUtilities.h"
+ #include "foundation/PxBasicTemplates.h"
+
+ using namespace physx;
+ using namespace Ext;
+
+ //Last four bits are used
+ //Last bit set stands for A
+ //Second last bit stands for B
+ //Third last bit stands for C
+ //Fourth last bit stands for D
+
+ typedef PxU32 TetCorner;
+ typedef PxU32 TetEdge;
+
+ static const TetCorner None = 0x00000000;
+ static const TetCorner A = 0x00000001;
+ static const TetCorner B = 0x00000002;
+ static const TetCorner C = 0x00000004;
+ static const TetCorner D = 0x00000008;
+
+ static const TetEdge AB = 0x00000003;
+ static const TetEdge AC = 0x00000005;
+ static const TetEdge AD = 0x00000009;
+ static const TetEdge BC = 0x00000006;
+ static const TetEdge BD = 0x0000000A;
+ static const TetEdge CD = 0x0000000C;
+
+ static const TetCorner tetCorners[4] = { A, B, C, D };
+
+ namespace
+ {
+ //Specifies which edges of a tetrahedron should get a point inserted (=split)
+ struct TetSubdivisionInfo
+ {
+ //If an index has value -1 then this means that this edge won't get split
+ PxI32 ab;
+ PxI32 ac;
+ PxI32 ad;
+
+ PxI32 bc;
+ PxI32 bd;
+
+ PxI32 cd;
+
+ Tetrahedron tet;
+ PxI32 id;
+
+ PX_FORCE_INLINE TetSubdivisionInfo() : ab(-1), ac(-1), ad(-1), bc(-1), bd(-1), cd(-1), tet(Tetrahedron(-1, -1, -1, -1)), id(-1) {}
+
+ PX_FORCE_INLINE TetSubdivisionInfo(Tetrahedron tet_, PxI32 aBPointInsertIndex, PxI32 aCPointInsertIndex, PxI32 aDPointInsertIndex,
+ PxI32 bCPointInsertIndex, PxI32 bDPointInsertIndex, PxI32 cDPointInsertIndex, PxI32 id_ = -1) :
+ ab(aBPointInsertIndex), ac(aCPointInsertIndex), ad(aDPointInsertIndex), bc(bCPointInsertIndex), bd(bDPointInsertIndex), cd(cDPointInsertIndex), tet(tet_), id(id_)
+ { }
+
+ PX_FORCE_INLINE void swapInternal(TetCorner corner1, TetCorner corner2, TetCorner& cornerToProcess)
+ {
+ if (cornerToProcess == corner1)
+ cornerToProcess = corner2;
+ else if (cornerToProcess == corner2)
+ cornerToProcess = corner1;
+ }
+
+ // PT: this function seems unused
+ //Helper method for sorting
+ /*template<typename T>
+ void swap(T& a, T& b)
+ {
+ T tmp = a;
+ a = b;
+ b = tmp;
+ }*/
+
+ //Helper method for sorting
+ bool swap(TetCorner corner1, TetCorner corner2, TetCorner& additionalCornerToProcess1, TetCorner& additionalCornerToProcess2)
+ {
+ swapInternal(corner1, corner2, additionalCornerToProcess1);
+ swapInternal(corner1, corner2, additionalCornerToProcess2);
+ return swap(corner1, corner2);
+ }
+
+ //Helper method for sorting
+ bool swap(TetCorner corner1, TetCorner corner2, TetCorner& additionalCornerToProcess)
+ {
+ swapInternal(corner1, corner2, additionalCornerToProcess);
+ return swap(corner1, corner2);
+ }
+
+ //Helper method for sorting
+ bool swap(TetCorner corner1, TetCorner corner2)
+ {
+ if (corner1 == corner2)
+ return false;
+
+ if (corner1 > corner2)
+ {
+ TetCorner tmp = corner1;
+ corner1 = corner2;
+ corner2 = tmp;
+ }
+
+ if (corner1 == A && corner2 == B)
+ {
+ PxSwap(ad, bd);
+ PxSwap(ac, bc);
+ PxSwap(tet[0], tet[1]);
+ }
+ else if (corner1 == A && corner2 == C)
+ {
+ PxSwap(ad, cd);
+ PxSwap(ab, bc);
+ PxSwap(tet[0], tet[2]);
+ }
+ else if (corner1 == A && corner2 == D)
+ {
+ PxSwap(ac, cd);
+ PxSwap(ab, bd);
+ PxSwap(tet[0], tet[3]);
+ }
+ else if (corner1 == B && corner2 == C)
+ {
+ PxSwap(ac, ab);
+ PxSwap(cd, bd);
+ PxSwap(tet[1], tet[2]);
+ }
+ else if (corner1 == B && corner2 == D)
+ {
+ PxSwap(ab, ad);
+ PxSwap(bc, cd);
+ PxSwap(tet[1], tet[3]);
+ }
+ else if (corner1 == C && corner2 == D)
+ {
+ PxSwap(ac, ad);
+ PxSwap(bc, bd);
+ PxSwap(tet[2], tet[3]);
+ }
+ return true;
+ }
+
+ //Allows to sort the information such that edges of neighboring tets have the same orientation
+ PxI32 sort()
+ {
+ PxI32 counter = 0;
+ if (tet[0] > tet[1]) { swap(A, B); ++counter; }
+ if (tet[0] > tet[2]) { swap(A, C); ++counter; }
+ if (tet[0] > tet[3]) { swap(A, D); ++counter; }
+
+ if (tet[1] > tet[2]) { swap(B, C); ++counter; }
+ if (tet[1] > tet[3]) { swap(B, D); ++counter; }
+ if (tet[2] > tet[3]) { swap(C, D); ++counter; }
+ return counter;
+ }
+ };
+ }
+
+ //Returns true if the edge is adjacent to the specified corner
+ static PX_FORCE_INLINE bool edgeContainsCorner(TetEdge edge, TetCorner corner)
+ {
+ return (edge & corner) != 0;
+ }
+
+ //Returns the common point of two edges, will be None if there is no common point
+ static PX_FORCE_INLINE TetCorner getCommonPoint(TetEdge edge1, TetEdge edge2)
+ {
+ return edge1 & edge2;
+ }
+
+ //Extracts the global indices from a tet given a local edge
+ static Edge getTetEdge(const Tetrahedron& tet, TetEdge edge)
+ {
+ switch (edge)
+ {
+ case AB:
+ return Edge(tet[0], tet[1]);
+ case AC:
+ return Edge(tet[0], tet[2]);
+ case AD:
+ return Edge(tet[0], tet[3]);
+ case BC:
+ return Edge(tet[1], tet[2]);
+ case BD:
+ return Edge(tet[1], tet[3]);
+ case CD:
+ return Edge(tet[2], tet[3]);
+ }
+ return Edge(-1, -1);
+ }
+
+ static TetCorner getStart(TetEdge e)
+ {
+ switch (e)
+ {
+ case AB:
+ return A;
+ case AC:
+ return A;
+ case AD:
+ return A;
+ case BC:
+ return B;
+ case BD:
+ return B;
+ case CD:
+ return C;
+ }
+ return None;
+ }
+
+ static TetCorner getEnd(TetEdge e)
+ {
+ switch (e)
+ {
+ case AB:
+ return B;
+ case AC:
+ return C;
+ case AD:
+ return D;
+ case BC:
+ return C;
+ case BD:
+ return D;
+ case CD:
+ return D;
+ }
+ return None;
+ }
+
+ static PX_FORCE_INLINE TetEdge getOppositeEdge(TetEdge edge)
+ {
+ return 0x0000000F ^ edge;
+ }
+
+ //Finds the index of the first instance of value in list
+ static PxI32 getIndexOfFirstValue(PxI32 list[4], PxI32 value = 0, PxI32 startAt = 0)
+ {
+ for (PxI32 i = startAt; i < 4; ++i)
+ if (list[i] == value)
+ return i;
+
+ PX_ASSERT(false); // we should never reach this line
+ return 0;
+ }
+
+ //Counts how many times every corner is referenced by the specified set of edges - useful for corner classification
+ static void getCornerAccessCounter(TetEdge edges[6], PxI32 edgesLength, PxI32 cornerAccessCounter[4])
+ {
+ for (PxI32 i = 0; i < 4; ++i)
+ cornerAccessCounter[i] = 0;
+
+ for (PxI32 j = 0; j < edgesLength; ++j)
+ {
+ switch (edges[j])
+ {
+ case AB:
+ ++cornerAccessCounter[0];
+ ++cornerAccessCounter[1];
+ break;
+ case AC:
+ ++cornerAccessCounter[0];
+ ++cornerAccessCounter[2];
+ break;
+ case AD:
+ ++cornerAccessCounter[0];
+ ++cornerAccessCounter[3];
+ break;
+ case BC:
+ ++cornerAccessCounter[1];
+ ++cornerAccessCounter[2];
+ break;
+ case BD:
+ ++cornerAccessCounter[1];
+ ++cornerAccessCounter[3];
+ break;
+ case CD:
+ ++cornerAccessCounter[2];
+ ++cornerAccessCounter[3];
+ break;
+ }
+ }
+ }
+
+ // PT: using static exposed the fact that this function was not used. Expected?
+ //Returns the tet's edge that does not contain corner1 and neither corner2
+ /*static Edge getRemainingEdge(const Tetrahedron& tet, PxI32 corner1, PxI32 corner2)
+ {
+ PxI32 indexer = 0;
+ Edge result(-1, -1);
+ for (PxU32 i = 0; i < 4; ++i)
+ {
+ if (tet[i] != corner1 && tet[i] != corner2)
+ {
+ if (indexer == 0)
+ result.first = tet[i];
+ else if (indexer == 1)
+ result.second = tet[i];
+ ++indexer;
+ }
+ }
+ return result;
+ }*/
+
+ static PX_FORCE_INLINE TetCorner getOtherCorner(TetEdge edge, TetCorner corner)
+ {
+ return edge ^ corner;
+ }
+
+ static PX_FORCE_INLINE Tetrahedron flip(bool doFlip, Tetrahedron t)
+ {
+ if (doFlip) PxSwap(t[2], t[3]);
+ return t;
+ }
+
+ //Splits all tets according to the specification in tetSubdivisionInfos. The resulting mesh will be watertight if the tetSubdivisionInfos are specified such
+ //that all tets sharing and edge will get the same point inserted on their corresponding edge
+ static void split(PxArray<Tetrahedron>& tets, const PxArray<PxVec3d>& points, const PxArray<TetSubdivisionInfo>& tetSubdivisionInfos)
+ {
+ PxU32 originalNumTets = tets.size();
+ for (PxU32 i = 0; i < originalNumTets; ++i)
+ {
+ TetSubdivisionInfo info = tetSubdivisionInfos[i];
+ PxI32 counter = info.sort();
+
+ TetEdge splitEdges[6];
+ PxI32 splitEdgesLength = 0;
+ TetEdge nonSplitEdges[6];
+ PxI32 nonSplitEdgesLength = 0;
+ PxI32 insertionIndices[6];
+ PxI32 insertionIndicesLength = 0;
+ if (info.ab >= 0) { splitEdges[splitEdgesLength++] = AB; insertionIndices[insertionIndicesLength++] = info.ab; }
+ else nonSplitEdges[nonSplitEdgesLength++] = AB;
+ if (info.ac >= 0) { splitEdges[splitEdgesLength++] = AC; insertionIndices[insertionIndicesLength++] = info.ac; }
+ else nonSplitEdges[nonSplitEdgesLength++] = AC;
+ if (info.ad >= 0) { splitEdges[splitEdgesLength++] = AD; insertionIndices[insertionIndicesLength++] = info.ad; }
+ else nonSplitEdges[nonSplitEdgesLength++] = AD;
+
+ if (info.bc >= 0) { splitEdges[splitEdgesLength++] = BC; insertionIndices[insertionIndicesLength++] = info.bc; }
+ else nonSplitEdges[nonSplitEdgesLength++] = BC;
+ if (info.bd >= 0) { splitEdges[splitEdgesLength++] = BD; insertionIndices[insertionIndicesLength++] = info.bd; }
+ else nonSplitEdges[nonSplitEdgesLength++] = BD;
+
+ if (info.cd >= 0) { splitEdges[splitEdgesLength++] = CD; insertionIndices[insertionIndicesLength++] = info.cd; }
+ else nonSplitEdges[nonSplitEdgesLength++] = CD;
+
+ //Depending on how many tet edges get a point inserted, a different topology results.
+ //The created topology will make sure all neighboring tet faces will be tessellated identically to keep the mesh watertight
+ switch (splitEdgesLength)
+ {
+ case 0:
+ //Nothing to do here
+ break;
+ case 1:
+ {
+ PxI32 pointIndex = insertionIndices[0];
+ Edge splitEdge = getTetEdge(info.tet, splitEdges[0]);
+
+ Edge oppositeEdge = getTetEdge(info.tet, getOppositeEdge(splitEdges[0]));
+
+ tets[i] = Tetrahedron(oppositeEdge.first, oppositeEdge.second, splitEdge.first, pointIndex);
+ tets.pushBack(Tetrahedron(oppositeEdge.first, oppositeEdge.second, pointIndex, splitEdge.second));
+
+ break;
+ }
+ case 2:
+ {
+ TetCorner corner = getCommonPoint(splitEdges[0], splitEdges[1]);
+ if (corner != None)
+ {
+ //edges have a common point
+ //Rearrange such that common corner is a and first edge is from a to b while second edge is from a to c
+ TetCorner p1 = getOtherCorner(splitEdges[0], corner);
+ TetCorner p2 = getOtherCorner(splitEdges[1], corner);
+ if (info.swap(corner, A, p1, p2)) ++counter;
+ if (info.swap(p1, B, p2)) ++counter;
+ if (info.swap(p2, C)) ++counter;
+
+ if (info.tet[1] > info.tet[2])
+ {
+ if (info.swap(B, C)) ++counter;
+ }
+
+ const bool f = counter % 2 == 1;
+
+ tets[i] = flip(f, Tetrahedron(info.tet[0], info.tet[3], info.ab, info.ac));
+ tets.pushBack(flip(f, Tetrahedron(info.tet[3], info.tet[1], info.ab, info.ac)));
+ tets.pushBack(flip(f, Tetrahedron(info.tet[3], info.tet[2], info.tet[1], info.ac)));
+ }
+ else
+ {
+ //Edges don't have a common point (opposite edges)
+ TetEdge edge1 = splitEdges[0];
+ //TetEdge edge2 = splitEdges[1];
+
+ //Permute the tetrahedron such that edge1 becomes the edge AB
+ if (info.swap(getStart(edge1), A)) ++counter;
+ if (info.swap(getEnd(edge1), B)) ++counter;
+
+ if (info.tet[0] > info.tet[1])
+ {
+ if (info.swap(A, B)) ++counter;
+ }
+ if (info.tet[2] > info.tet[3])
+ {
+ if (info.swap(C, D)) ++counter;
+ }
+
+ const bool f = counter % 2 == 1;
+
+ tets[i] = flip(f, Tetrahedron(info.tet[0], info.ab, info.tet[2], info.cd));
+ tets.pushBack(flip(f, Tetrahedron(info.tet[1], info.ab, info.cd, info.tet[2])));
+
+ tets.pushBack(flip(f, Tetrahedron(info.tet[0], info.ab, info.cd, info.tet[3])));
+ tets.pushBack(flip(f, Tetrahedron(info.tet[1], info.ab, info.tet[3], info.cd)));
+ }
+ break;
+ }
+ case 3:
+ {
+ //There are three sub cases called a, b and c
+ TetCorner commonPoint01 = getCommonPoint(splitEdges[0], splitEdges[1]);
+ TetCorner commonPoint02 = getCommonPoint(splitEdges[0], splitEdges[2]);
+ TetCorner commonPoint12 = getCommonPoint(splitEdges[1], splitEdges[2]);
+ if (commonPoint01 == None || commonPoint02 == None || commonPoint12 == None)
+ {
+ //The three edges form a non closed strip
+ //The strip's end points are connected by a tet edge - map this edge such that it becomes edge AB
+ //Then sort AB
+
+ PxI32 cnt[4];
+ getCornerAccessCounter(splitEdges, splitEdgesLength, cnt);
+
+ PxI32 index = getIndexOfFirstValue(cnt, 1);
+ TetCorner refStart = tetCorners[index];
+ TetCorner refEnd = tetCorners[getIndexOfFirstValue(cnt, 1, index + 1)];
+
+
+ TetCorner cornerToMapOntoC = None;
+ if (edgeContainsCorner(splitEdges[0], refEnd))
+ {
+ cornerToMapOntoC = getOtherCorner(splitEdges[0], refEnd);
+ }
+ else if (edgeContainsCorner(splitEdges[1], refEnd))
+ {
+ cornerToMapOntoC = getOtherCorner(splitEdges[1], refEnd);
+ }
+ else if (edgeContainsCorner(splitEdges[2], refEnd))
+ {
+ cornerToMapOntoC = getOtherCorner(splitEdges[2], refEnd);
+ }
+
+ if (info.swap(refStart, A, refEnd, cornerToMapOntoC)) ++counter;
+ if (info.swap(refEnd, B, cornerToMapOntoC)) ++counter;
+ if (info.swap(cornerToMapOntoC, C)) ++counter;
+
+ if (info.tet[0] > info.tet[1])
+ {
+ if (info.swap(A, B)) ++counter;
+ if (info.swap(C, D)) ++counter;
+ }
+
+ const bool f = counter % 2 == 1;
+
+ tets[i] = flip(f, Tetrahedron(info.tet[0], info.tet[1], info.bc, info.ad));
+
+ if (info.tet[0] > info.tet[2])
+ {
+ tets.pushBack(flip(f, Tetrahedron(info.tet[2], info.cd, info.ad, info.bc)));
+ tets.pushBack(flip(f, Tetrahedron(info.tet[0], info.tet[2], info.ad, info.bc)));
+ }
+ else
+ {
+ tets.pushBack(flip(f, Tetrahedron(info.tet[0], info.tet[2], info.cd, info.bc)));
+ tets.pushBack(flip(f, Tetrahedron(info.tet[0], info.ad, info.bc, info.cd)));
+ }
+
+ if (info.tet[1] > info.tet[3])
+ {
+ tets.pushBack(flip(f, Tetrahedron(info.tet[3], info.bc, info.ad, info.cd)));
+ tets.pushBack(flip(f, Tetrahedron(info.tet[3], info.tet[1], info.ad, info.bc)));
+ }
+ else
+ {
+ tets.pushBack(flip(f, Tetrahedron(info.tet[1], info.tet[3], info.cd, info.ad)));
+ tets.pushBack(flip(f, Tetrahedron(info.tet[1], info.bc, info.ad, info.cd)));
+ }
+ }
+ else if (edgeContainsCorner(splitEdges[2], commonPoint01))
+ {
+ //All three edges share one common point
+ //Permute tetrahedron such that the common tip point is a
+ if (info.swap(commonPoint01, A)) ++counter;
+ //Sort the remaining values
+ if (info.tet[1] > info.tet[2])
+ {
+ if (info.swap(B, C)) ++counter;
+ }
+ if (info.tet[2] > info.tet[3])
+ {
+ if (info.swap(C, D)) ++counter;
+ }
+ if (info.tet[1] > info.tet[2])
+ {
+ if (info.swap(B, C)) ++counter;
+ }
+
+ const bool f = counter % 2 == 1;
+
+ tets[i] = flip(f, Tetrahedron(info.tet[0], info.ab, info.ac, info.ad));
+ tets.pushBack(flip(f, Tetrahedron(info.tet[1], info.ab, info.ad, info.ac)));
+ tets.pushBack(flip(f, Tetrahedron(info.tet[2], info.tet[1], info.ad, info.ac)));
+ tets.pushBack(flip(f, Tetrahedron(info.tet[1], info.tet[2], info.ad, info.tet[3])));
+ }
+ else
+ {
+ //Edges form a triangle
+ //Rearrange such that point opposite of triangle loop is point d
+ //Triangle loop is a, b and c, make sure they're sorted
+
+ if (!(commonPoint01 == A || commonPoint02 == A || commonPoint12 == A))
+ {
+ if (info.swap(A, D)) ++counter;
+ }
+ else if (!(commonPoint01 == B || commonPoint02 == B || commonPoint12 == B))
+ {
+ if (info.swap(B, D)) ++counter;
+ }
+ else if (!(commonPoint01 == C || commonPoint02 == C || commonPoint12 == C))
+ {
+ if (info.swap(C, D)) ++counter;
+ }
+ else if (!(commonPoint01 == D || commonPoint02 == D || commonPoint12 == D))
+ {
+ if (info.swap(D, D)) ++counter;
+ }
+
+ //Sort a,b and c
+ if (info.tet[0] > info.tet[1])
+ if (info.swap(A, B)) ++counter;
+ if (info.tet[1] > info.tet[2])
+ if (info.swap(B, C)) ++counter;
+ if (info.tet[0] > info.tet[1])
+ if (info.swap(A, B)) ++counter;
+
+ const bool f = counter % 2 == 1;
+
+ tets[i] = flip(f, Tetrahedron(info.tet[3], info.ab, info.ac, info.bc));
+ tets.pushBack(flip(f, Tetrahedron(info.tet[3], info.ab, info.ac, info.tet[0])));
+ tets.pushBack(flip(f, Tetrahedron(info.tet[3], info.ab, info.bc, info.tet[1])));
+ tets.pushBack(flip(f, Tetrahedron(info.tet[3], info.ac, info.bc, info.tet[2])));
+ }
+ break;
+ }
+ case 4:
+ {
+ TetCorner commonPoint = getCommonPoint(nonSplitEdges[0], nonSplitEdges[1]);
+
+ if (commonPoint != None)
+ {
+ //Three edges form a triangle and the two edges that are not split share a common point
+ TetCorner p1 = getOtherCorner(nonSplitEdges[0], commonPoint);
+ TetCorner p2 = getOtherCorner(nonSplitEdges[1], commonPoint);
+
+ if (info.swap(commonPoint, A, p1, p2)) ++counter;
+
+ if (info.swap(p1, B, p2)) ++counter;
+ if (info.swap(p2, C)) ++counter;
+
+ if (info.tet[1] > info.tet[2])
+ if (info.swap(B, C)) ++counter;
+
+ const bool f = counter % 2 == 0;
+
+ //Tip
+ tets[i] = flip(f, Tetrahedron(info.tet[3], info.ad, info.bd, info.cd));
+
+ //Center
+ tets.pushBack(flip(f, Tetrahedron(info.bd, info.ad, info.bc, info.cd)));
+
+ if (info.tet[0] < info.tet[1] && info.tet[0] < info.tet[2])
+ {
+ tets.pushBack(flip(f, Tetrahedron(info.tet[0], info.tet[1], info.bd, info.bc)));
+ tets.pushBack(flip(f, Tetrahedron(info.tet[0], info.tet[2], info.bc, info.cd)));
+ tets.pushBack(flip(f, Tetrahedron(info.tet[0], info.bc, info.bd, info.ad)));
+ tets.pushBack(flip(f, Tetrahedron(info.tet[0], info.bc, info.ad, info.cd)));
+ }
+ else if (info.tet[0] > info.tet[1] && info.tet[0] < info.tet[2])
+ {
+ tets.pushBack(flip(f, Tetrahedron(info.tet[0], info.tet[2], info.bc, info.cd)));
+ tets.pushBack(flip(f, Tetrahedron(info.tet[0], info.bc, info.ad, info.cd)));
+ tets.pushBack(flip(f, Tetrahedron(info.tet[0], info.tet[1], info.ad, info.bc)));
+ tets.pushBack(flip(f, Tetrahedron(info.tet[1], info.bc, info.bd, info.ad)));
+ }
+ else
+ {
+ tets.pushBack(flip(f, Tetrahedron(info.tet[0], info.tet[1], info.ad, info.bc)));
+ tets.pushBack(flip(f, Tetrahedron(info.tet[1], info.bc, info.bd, info.ad)));
+ tets.pushBack(flip(f, Tetrahedron(info.tet[2], info.tet[0], info.ad, info.bc)));
+ tets.pushBack(flip(f, Tetrahedron(info.tet[2], info.bc, info.ad, info.cd)));
+ }
+ }
+ else
+ {
+ //All four edges form a loop
+ TetEdge edge1 = nonSplitEdges[0];
+
+ //Permute the tetrahedron such that edge1 becomes the edge AB
+ TetCorner end = getEnd(edge1);
+ if (info.swap(getStart(edge1), A, end)) ++counter;
+ if (info.swap(end, B)) ++counter;
+
+ //Sort
+ if (info.tet[0] > info.tet[1])
+ if (info.swap(A, B)) ++counter;
+ if (info.tet[2] > info.tet[3])
+ if (info.swap(C, D)) ++counter;
+
+ const bool f = counter % 2 == 1;
+
+ tets[i] = flip(f, Tetrahedron(info.tet[0], info.tet[1], info.bc, info.bd));
+ tets.pushBack(flip(f, Tetrahedron(info.tet[2], info.tet[3], info.ad, info.bd)));
+
+ PxF64 dist1 = (points[info.ad] - points[info.bc]).magnitudeSquared();
+ PxF64 dist2 = (points[info.ac] - points[info.bd]).magnitudeSquared();
+
+ if (dist1 < dist2)
+ {
+ //Diagonal from AD to BC
+ tets.pushBack(flip(f, Tetrahedron(info.tet[0], info.ad, info.bc, info.ac)));
+ tets.pushBack(flip(f, Tetrahedron(info.tet[0], info.ad, info.bd, info.bc)));
+ tets.pushBack(flip(f, Tetrahedron(info.tet[2], info.ad, info.ac, info.bc)));
+ tets.pushBack(flip(f, Tetrahedron(info.tet[2], info.ad, info.bc, info.bd)));
+ }
+ else
+ {
+ //Diagonal from AC to BD
+ tets.pushBack(flip(f, Tetrahedron(info.tet[0], info.ad, info.bd, info.ac)));
+ tets.pushBack(flip(f, Tetrahedron(info.tet[0], info.ac, info.bd, info.bc)));
+ tets.pushBack(flip(f, Tetrahedron(info.tet[2], info.bc, info.bd, info.ac)));
+ tets.pushBack(flip(f, Tetrahedron(info.tet[2], info.bd, info.ad, info.ac)));
+ }
+ }
+ break;
+ }
+ case 5:
+ {
+ //There is only one edge that does not get split
+
+ //First create 2 small tetrahedra in every corner that is not an end point of the unsplit edge
+ TetEdge nonSplitEdge;
+ if (info.ab < 0)
+ nonSplitEdge = AB;
+ else if (info.ac < 0)
+ nonSplitEdge = AC;
+ else if (info.ad < 0)
+ nonSplitEdge = AD;
+ else if (info.bc < 0)
+ nonSplitEdge = BC;
+ else if (info.bd < 0)
+ nonSplitEdge = BD;
+ else //if (info.CDPointInsertIndex < 0)
+ nonSplitEdge = CD;
+
+ TetCorner end = getEnd(nonSplitEdge);
+ if (info.swap(getStart(nonSplitEdge), A, end)) ++counter;
+ if (info.swap(end, B)) ++counter;
+
+ if (info.tet[0] > info.tet[1])
+ if (info.swap(A, B)) ++counter;
+ if (info.tet[2] > info.tet[3])
+ if (info.swap(C, D)) ++counter;
+
+ const bool f = counter % 2 == 1;
+
+ //Two corner tets at corner C and corner D
+ tets[i] = flip(f, Tetrahedron(info.tet[2], info.ac, info.bc, info.cd));
+ tets.pushBack(flip(f, Tetrahedron(info.tet[3], info.ad, info.cd, info.bd)));
+
+ tets.pushBack(flip(f, Tetrahedron(info.tet[0], info.tet[1], info.bc, info.bd)));
+
+
+ //There are two possible diagonals -> take the shorter
+ PxF64 dist1 = (points[info.ac] - points[info.bd]).magnitudeSquared();
+ PxF64 dist2 = (points[info.ad] - points[info.bc]).magnitudeSquared();
+ if (dist1 < dist2)
+ {
+ //Diagonal from AC to BD
+ tets.pushBack(flip(f, Tetrahedron(info.tet[0], info.ad, info.bd, info.ac)));
+ tets.pushBack(flip(f, Tetrahedron(info.tet[0], info.ac, info.bd, info.bc)));
+ //Tip pyramid
+ tets.pushBack(flip(f, Tetrahedron(info.cd, info.bc, info.bd, info.ac)));
+ tets.pushBack(flip(f, Tetrahedron(info.cd, info.bd, info.ad, info.ac)));
+ }
+ else
+ {
+ //Diagonal from AD to BC
+ tets.pushBack(flip(f, Tetrahedron(info.tet[0], info.ac, info.ad, info.bc)));
+ tets.pushBack(flip(f, Tetrahedron(info.tet[0], info.bd, info.bc, info.ad)));
+ //Tip pyramid
+ tets.pushBack(flip(f, Tetrahedron(info.cd, info.bc, info.ad, info.ac)));
+ tets.pushBack(flip(f, Tetrahedron(info.cd, info.bd, info.ad, info.bc)));
+ }
+ break;
+ }
+ case 6:
+ {
+ //First create a small tetrahedron in every corner
+ const bool f = counter % 2 == 1;
+ if (f)
+ info.swap(A, B);
+
+ tets[i] = Tetrahedron(info.tet[0], info.ab, info.ac, info.ad);
+ tets.pushBack(Tetrahedron(info.tet[1], info.ab, info.bd, info.bc));
+ tets.pushBack(Tetrahedron(info.tet[2], info.ac, info.bc, info.cd));
+ tets.pushBack(Tetrahedron(info.tet[3], info.ad, info.cd, info.bd));
+
+ //Now fill the remaining octahedron in the middle
+ //An octahedron can be constructed using 4 tetrahedra
+ //There are three diagonal candidates -> pick the shortest diagonal
+ PxF64 dist1 = (points[info.ab] - points[info.cd]).magnitudeSquared();
+ PxF64 dist2 = (points[info.ac] - points[info.bd]).magnitudeSquared();
+ PxF64 dist3 = (points[info.ad] - points[info.bc]).magnitudeSquared();
+
+ if (dist1 <= dist2 && dist1 <= dist3)
+ {
+ tets.pushBack(Tetrahedron(info.ab, info.cd, info.ad, info.bd));
+ tets.pushBack(Tetrahedron(info.ab, info.cd, info.bd, info.bc));
+ tets.pushBack(Tetrahedron(info.ab, info.cd, info.bc, info.ac));
+ tets.pushBack(Tetrahedron(info.ab, info.cd, info.ac, info.ad));
+ }
+ else if (dist2 <= dist1 && dist2 <= dist3)
+ {
+ tets.pushBack(Tetrahedron(info.ac, info.bd, info.cd, info.ad));
+ tets.pushBack(Tetrahedron(info.ac, info.bd, info.ad, info.ab));
+ tets.pushBack(Tetrahedron(info.ac, info.bd, info.ab, info.bc));
+ tets.pushBack(Tetrahedron(info.ac, info.bd, info.bc, info.cd));
+ }
+ else
+ {
+ tets.pushBack(Tetrahedron(info.ad, info.bc, info.bd, info.ab));
+ tets.pushBack(Tetrahedron(info.ad, info.bc, info.cd, info.bd));
+ tets.pushBack(Tetrahedron(info.ad, info.bc, info.ac, info.cd));
+ tets.pushBack(Tetrahedron(info.ad, info.bc, info.ab, info.ac));
+ }
+ break;
+ }
+ }
+ }
+ }
+
+ void physx::Ext::split(PxArray<Tetrahedron>& tets, const PxArray<PxVec3d>& points, const PxHashMap<PxU64, PxI32>& edgesToSplit)
+ {
+ PxArray<TetSubdivisionInfo> subdivisionInfos;
+ subdivisionInfos.resize(tets.size());
+ for (PxU32 i = 0; i < tets.size(); ++i)
+ {
+ const Tetrahedron& tet = tets[i];
+ TetSubdivisionInfo info(tet, -1, -1, -1, -1, -1, -1, i);
+
+ if (const PxPair<const PxU64, PxI32>* ptr = edgesToSplit.find(key(tet[0], tet[1])))
+ info.ab = ptr->second;
+ if (const PxPair<const PxU64, PxI32>* ptr = edgesToSplit.find(key(tet[0], tet[2])))
+ info.ac = ptr->second;
+ if (const PxPair<const PxU64, PxI32>* ptr = edgesToSplit.find(key(tet[0], tet[3])))
+ info.ad = ptr->second;
+
+ if (const PxPair<const PxU64, PxI32>* ptr = edgesToSplit.find(key(tet[1], tet[2])))
+ info.bc = ptr->second;
+ if (const PxPair<const PxU64, PxI32>* ptr = edgesToSplit.find(key(tet[1], tet[3])))
+ info.bd = ptr->second;
+
+ if (const PxPair<const PxU64, PxI32>* ptr = edgesToSplit.find(key(tet[2], tet[3])))
+ info.cd = ptr->second;
+
+ subdivisionInfos[i] = info;
+ }
+
+ ::split(tets, points, subdivisionInfos);
+ }