// // 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-2019 NVIDIA Corporation. All rights reserved. // Copyright (c) 2004-2008 AGEIA Technologies, Inc. All rights reserved. // Copyright (c) 2001-2004 NovodeX AG. All rights reserved. #include "foundation/PxMemory.h" #include "EdgeList.h" #include "Adjacencies.h" #include "CmRadixSortBuffered.h" #include "GuSerialize.h" #include "PsFoundation.h" using namespace physx; using namespace Gu; /////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// /** * Flips the winding. */ /////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// void AdjTriangle::Flip() { #ifdef MSH_ADJACENCIES_INCLUDE_TOPOLOGY // Call the Triangle method IndexedTriangle::Flip(); #endif // Flip links. We flipped vertex references 1 & 2, i.e. links 0 & 1. physx::shdfnd::swap(mATri[0], mATri[1]); } /////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// /** * Computes the number of boundary edges in a triangle. * \return the number of boundary edges. (0 => 3) */ /////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// PxU32 AdjTriangle::ComputeNbBoundaryEdges() const { // Look for boundary edges PxU32 Nb = 0; if(IS_BOUNDARY(mATri[0])) Nb++; if(IS_BOUNDARY(mATri[1])) Nb++; if(IS_BOUNDARY(mATri[2])) Nb++; return Nb; } /////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// /** * Computes the number of valid neighbors. * \return the number of neighbors. (0 => 3) */ /////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// PxU32 AdjTriangle::ComputeNbNeighbors() const { PxU32 Nb = 0; if(!IS_BOUNDARY(mATri[0])) Nb++; if(!IS_BOUNDARY(mATri[1])) Nb++; if(!IS_BOUNDARY(mATri[2])) Nb++; return Nb; } /////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// /** * Checks whether the triangle has a particular neighbor or not. * \param tref [in] the triangle reference to look for * \param index [out] the corresponding index in the triangle (NULL if not needed) * \return true if the triangle has the given neighbor */ /////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// bool AdjTriangle::HasNeighbor(PxU32 tref, PxU32* index) const { // ### could be optimized if(!IS_BOUNDARY(mATri[0]) && MAKE_ADJ_TRI(mATri[0])==tref) { if(index) *index = 0; return true; } if(!IS_BOUNDARY(mATri[1]) && MAKE_ADJ_TRI(mATri[1])==tref) { if(index) *index = 1; return true; } if(!IS_BOUNDARY(mATri[2]) && MAKE_ADJ_TRI(mATri[2])==tref) { if(index) *index = 2; return true; } return false; } /////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// /** * Constructor. */ /////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// Adjacencies::Adjacencies() : mNbFaces(0), mFaces(NULL) { } /////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// /** * Destructor. */ /////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// Adjacencies::~Adjacencies() { PX_DELETE_ARRAY(mFaces); } /////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// /** * Computes the number of boundary edges. * \return the number of boundary edges. */ /////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// PxU32 Adjacencies::ComputeNbBoundaryEdges() const { // Checking if(!mFaces) return 0; // Look for boundary edges PxU32 Nb = 0; for(PxU32 i=0;iComputeNbBoundaryEdges(); } return Nb; } /////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// /** * Computes the boundary vertices. A boundary vertex is defined as a vertex shared by at least one boundary edge. * \param nb_verts [in] the number of vertices * \param bound_status [out] a user-provided array of bool * \return true if success. The user-array is filled with true or false (boundary vertex / not boundary vertex) */ /////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// #ifdef MSH_ADJACENCIES_INCLUDE_TOPOLOGY bool Adjacencies::GetBoundaryVertices(PxU32 nb_verts, bool* bound_status) const #else bool Adjacencies::GetBoundaryVertices(PxU32 nb_verts, bool* bound_status, const Gu::TriangleT* faces) const #endif { // We need the adjacencies if(!mFaces || !bound_status || !nb_verts) { Ps::getFoundation().error(PxErrorCode::eINVALID_OPERATION, __FILE__, __LINE__, "Adjacencies::GetBoundaryVertices: NULL parameter!"); return false; } #ifndef MSH_ADJACENCIES_INCLUDE_TOPOLOGY if(!faces) { Ps::getFoundation().error(PxErrorCode::eINVALID_OPERATION, __FILE__, __LINE__, "Adjacencies::GetBoundaryVertices: NULL parameter!"); return false; } #endif // Init PxMemZero(bound_status, nb_verts*sizeof(bool)); // Loop through faces for(PxU32 i=0;imATri[0])) { // Two boundary vertices: 0 - 1 #ifdef MSH_ADJACENCIES_INCLUDE_TOPOLOGY PxU32 VRef0 = CurTri->v[0]; if(VRef0>=nb_verts) return false; bound_status[VRef0] = true; PxU32 VRef1 = CurTri->v[1]; if(VRef1>=nb_verts) return false; bound_status[VRef1] = true; #else PxU32 VRef0 = faces[i].v[0]; if(VRef0>=nb_verts) return false; bound_status[VRef0] = true; PxU32 VRef1 = faces[i].v[1]; if(VRef1>=nb_verts) return false; bound_status[VRef1] = true; #endif } if(IS_BOUNDARY(CurTri->mATri[1])) { // Two boundary vertices: 0 - 2 #ifdef MSH_ADJACENCIES_INCLUDE_TOPOLOGY PxU32 VRef0 = CurTri->v[0]; if(VRef0>=nb_verts) return false; bound_status[VRef0] = true; PxU32 VRef1 = CurTri->v[2]; if(VRef1>=nb_verts) return false; bound_status[VRef1] = true; #else PxU32 VRef0 = faces[i].v[0]; if(VRef0>=nb_verts) return false; bound_status[VRef0] = true; PxU32 VRef1 = faces[i].v[2]; if(VRef1>=nb_verts) return false; bound_status[VRef1] = true; #endif } if(IS_BOUNDARY(CurTri->mATri[2])) { // Two boundary vertices: 1 - 2 #ifdef MSH_ADJACENCIES_INCLUDE_TOPOLOGY PxU32 VRef0 = CurTri->v[1]; if(VRef0>=nb_verts) return false; bound_status[VRef0] = true; PxU32 VRef1 = CurTri->v[2]; if(VRef1>=nb_verts) return false; bound_status[VRef1] = true; #else PxU32 VRef0 = faces[i].v[1]; if(VRef0>=nb_verts) return false; bound_status[VRef0] = true; PxU32 VRef1 = faces[i].v[2]; if(VRef1>=nb_verts) return false; bound_status[VRef1] = true; #endif } } return true; } /////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// /** * Assigns a new edge code to the counterpart link of a given link. * \param link [in] the link to modify - shouldn't be a boundary link * \param edge_nb [in] the new edge number */ /////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// void Adjacencies::AssignNewEdgeCode(PxU32 link, PxU8 edge_nb) { if(!IS_BOUNDARY(link)) { PxU32 Id = MAKE_ADJ_TRI(link); // Triangle ID PxU32 Edge = GET_EDGE_NB(link); // Counterpart edge ID AdjTriangle* Tri = &mFaces[Id]; // Adjacent triangle // Get link whose edge code is invalid PxU32 AdjLink = Tri->mATri[Edge]; // Link to ourself (i.e. to 'link') SET_EDGE_NB(AdjLink, edge_nb); // Assign new edge code Tri->mATri[Edge] = AdjLink; // Put link back } } /////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// /** * Modifies the existing database so that reference 'vref' of triangle 'curtri' becomes the last one. * Provided reference must already exist in provided triangle. * \param cur_tri [in] the triangle * \param vref [in] the reference * \return true if success. */ /////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// #ifdef MSH_ADJACENCIES_INCLUDE_TOPOLOGY bool Adjacencies::MakeLastRef(AdjTriangle& cur_tri, PxU32 vref) #else bool Adjacencies::MakeLastRef(AdjTriangle& cur_tri, PxU32 vref, Gu::TriangleT* cur_topo) #endif { #ifndef MSH_ADJACENCIES_INCLUDE_TOPOLOGY // Checkings if(!cur_topo) { Ps::getFoundation().error(PxErrorCode::eINVALID_OPERATION, __FILE__, __LINE__, "Adjacencies::MakeLastRef: NULL parameter!"); return false; } #endif // We want pattern (x y vref) // Edge 0-1 is (x y) // Edge 0-2 is (x vref) // Edge 1-2 is (y vref) // First thing is to scroll the existing references in order for vref to become the last one. Scrolling assures winding order is conserved. // Edge code need fixing as well: // The two MSB for each link encode the counterpart edge in adjacent triangle. We swap the link positions, but adjacent triangles remain the // same. In other words, edge codes are still valid for current triangle since counterpart edges have not been swapped. *BUT* edge codes of // the three possible adjacent triangles *are* now invalid. We need to fix edge codes, but for adjacent triangles... #ifdef MSH_ADJACENCIES_INCLUDE_TOPOLOGY if(cur_tri.v[0]==vref) #else if(cur_topo->v[0]==vref) #endif { // Pattern is (vref x y) // Edge 0-1 is (vref x) // Edge 0-2 is (vref y) // Edge 1-2 is (x y) // Catch original data #ifdef MSH_ADJACENCIES_INCLUDE_TOPOLOGY PxU32 Ref0 = cur_tri.v[0]; PxU32 Link01 = cur_tri.mATri[0]; PxU32 Ref1 = cur_tri.v[1]; PxU32 Link02 = cur_tri.mATri[1]; PxU32 Ref2 = cur_tri.v[2]; PxU32 Link12 = cur_tri.mATri[2]; // Swap cur_tri.v[0] = Ref1; cur_tri.v[1] = Ref2; cur_tri.v[2] = Ref0; #else PxU32 Ref0 = cur_topo->v[0]; PxU32 Link01 = cur_tri.mATri[0]; PxU32 Ref1 = cur_topo->v[1]; PxU32 Link02 = cur_tri.mATri[1]; PxU32 Ref2 = cur_topo->v[2]; PxU32 Link12 = cur_tri.mATri[2]; // Swap cur_topo->v[0] = Ref1; cur_topo->v[1] = Ref2; cur_topo->v[2] = Ref0; #endif cur_tri.mATri[0] = Link12; // Edge 0-1 now encodes Ref1-Ref2, i.e. previous Link12 cur_tri.mATri[1] = Link01; // Edge 0-2 now encodes Ref1-Ref0, i.e. previous Link01 cur_tri.mATri[2] = Link02; // Edge 1-2 now encodes Ref2-Ref0, i.e. previous Link02 // Fix edge codes AssignNewEdgeCode(Link01, 1); AssignNewEdgeCode(Link02, 2); AssignNewEdgeCode(Link12, 0); return true; } #ifdef MSH_ADJACENCIES_INCLUDE_TOPOLOGY else if(cur_tri.v[1]==vref) #else else if(cur_topo->v[1]==vref) #endif { // Pattern is (x vref y) // Edge 0-1 is (x vref) // Edge 0-2 is (x y) // Edge 1-2 is (vref y) // Catch original data #ifdef MSH_ADJACENCIES_INCLUDE_TOPOLOGY PxU32 Ref0 = cur_tri.v[0]; PxU32 Link01 = cur_tri.mATri[0]; PxU32 Ref1 = cur_tri.v[1]; PxU32 Link02 = cur_tri.mATri[1]; PxU32 Ref2 = cur_tri.v[2]; PxU32 Link12 = cur_tri.mATri[2]; // Swap cur_tri.v[0] = Ref2; cur_tri.v[1] = Ref0; cur_tri.v[2] = Ref1; #else PxU32 Ref0 = cur_topo->v[0]; PxU32 Link01 = cur_tri.mATri[0]; PxU32 Ref1 = cur_topo->v[1]; PxU32 Link02 = cur_tri.mATri[1]; PxU32 Ref2 = cur_topo->v[2]; PxU32 Link12 = cur_tri.mATri[2]; // Swap cur_topo->v[0] = Ref2; cur_topo->v[1] = Ref0; cur_topo->v[2] = Ref1; #endif cur_tri.mATri[0] = Link02; // Edge 0-1 now encodes Ref2-Ref0, i.e. previous Link02 cur_tri.mATri[1] = Link12; // Edge 0-2 now encodes Ref2-Ref1, i.e. previous Link12 cur_tri.mATri[2] = Link01; // Edge 1-2 now encodes Ref0-Ref1, i.e. previous Link01 // Fix edge codes AssignNewEdgeCode(Link01, 2); AssignNewEdgeCode(Link02, 0); AssignNewEdgeCode(Link12, 1); return true; } #ifdef MSH_ADJACENCIES_INCLUDE_TOPOLOGY else if(cur_tri.v[2]==vref) #else else if(cur_topo->v[2]==vref) #endif { // Nothing to do, provided reference already is the last one return true; } // Here the provided reference doesn't belong to the provided triangle. return false; } bool Adjacencies::Load(PxInputStream& stream) { // Import header PxU32 Version; bool Mismatch; if(!ReadHeader('A', 'D', 'J', 'A', Version, Mismatch, stream)) return false; // Import adjacencies mNbFaces = readDword(Mismatch, stream); mFaces = PX_NEW(AdjTriangle)[mNbFaces]; stream.read(mFaces, sizeof(AdjTriangle)*mNbFaces); return true; } //#ifdef PX_COOKING //! An edge class used to compute the adjacency structures. class AdjEdge : public Gu::EdgeData, public Ps::UserAllocated { public: //! Constructor PX_INLINE AdjEdge() {} //! Destructor PX_INLINE ~AdjEdge() {} PxU32 mFaceNb; //!< Owner face }; /////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// /** * Adds a new edge to the database. * \param ref0 [in] vertex reference for the new edge * \param ref1 [in] vertex reference for the new edge * \param face [in] owner face */ /////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// static void AddEdge(PxU32 ref0, PxU32 ref1, PxU32 face, PxU32& nb_edges, AdjEdge* edges) { // Store edge data edges[nb_edges].Ref0 = ref0; edges[nb_edges].Ref1 = ref1; edges[nb_edges].mFaceNb = face; nb_edges++; } /////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// /** * Adds a new triangle to the database. * \param ref0 [in] vertex reference for the new triangle * \param ref1 [in] vertex reference for the new triangle * \param ref2 [in] vertex reference for the new triangle * \param id [in] triangle index */ /////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// static void AddTriangle(PxU32 ref0, PxU32 ref1, PxU32 ref2, PxU32 id, AdjTriangle* faces, PxU32& nb_edges, AdjEdge* edges) { #ifdef MSH_ADJACENCIES_INCLUDE_TOPOLOGY // Store vertex-references faces[id].v[0] = ref0; faces[id].v[1] = ref1; faces[id].v[2] = ref2; #endif // Reset links faces[id].mATri[0] = PX_INVALID_U32; faces[id].mATri[1] = PX_INVALID_U32; faces[id].mATri[2] = PX_INVALID_U32; // Add edge 01 to database if(ref0 FirstTri, SecondTri; if(create.DFaces) { FirstTri.v[0] = create.DFaces[first_tri*3+0]; FirstTri.v[1] = create.DFaces[first_tri*3+1]; FirstTri.v[2] = create.DFaces[first_tri*3+2]; SecondTri.v[0] = create.DFaces[second_tri*3+0]; SecondTri.v[1] = create.DFaces[second_tri*3+1]; SecondTri.v[2] = create.DFaces[second_tri*3+2]; } if(create.WFaces) { FirstTri.v[0] = create.WFaces[first_tri*3+0]; FirstTri.v[1] = create.WFaces[first_tri*3+1]; FirstTri.v[2] = create.WFaces[first_tri*3+2]; SecondTri.v[0] = create.WFaces[second_tri*3+0]; SecondTri.v[1] = create.WFaces[second_tri*3+1]; SecondTri.v[2] = create.WFaces[second_tri*3+2]; } // Get the edge IDs. 0xff means input references are wrong. const PxU8 EdgeNb0 = FirstTri.findEdge(ref0, ref1); const PxU8 EdgeNb1 = SecondTri.findEdge(ref0, ref1); if(EdgeNb0==0xff || EdgeNb1==0xff) { Ps::getFoundation().error(PxErrorCode::eINVALID_OPERATION, __FILE__, __LINE__, "Adjacencies::UpdateLink: invalid edge reference"); return false; } // Update links. The two most significant bits contain the counterpart edge's ID. faces[first_tri].mATri[EdgeNb0] = second_tri |(PxU32(EdgeNb1)<<30); faces[second_tri].mATri[EdgeNb1] = first_tri |(PxU32(EdgeNb0)<<30); #endif return true; } /////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// /** * Creates the adjacency structures. * \return true if success. */ /////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// #ifdef MSH_ADJACENCIES_INCLUDE_TOPOLOGY static bool CreateDatabase(AdjTriangle* faces, PxU32 nb_edges, const AdjEdge* edges) #else static bool CreateDatabase(AdjTriangle* faces, PxU32 nb_edges, const AdjEdge* edges, const ADJACENCIESCREATE& create) #endif { Cm::RadixSortBuffered Core; { // Multiple sorts - this rewritten version uses less ram // PT: TTP 2994: the mesh has 343000+ edges, so yeah, sure, allocating more than 1mb on the stack causes overflow... PxU32* VRefs = PX_NEW_TEMP(PxU32)[nb_edges]; // Sort according to mRef0, then mRef1 PxU32 i; for(i=0;i edge is a boundary edge: it belongs to a single triangle. // Hence there's no need to update a link to an adjacent triangle. #ifdef MSH_ADJACENCIES_INCLUDE_TOPOLOGY if(!UpdateLink(TmpBuffer[0], TmpBuffer[1], LastRef0, LastRef1, faces)) return false; #else if(!UpdateLink(TmpBuffer[0], TmpBuffer[1], LastRef0, LastRef1, faces, create)) return false; #endif } // Reset for next edge Count = 0; TmpBuffer[Count++] = Face; LastRef0 = Ref0; LastRef1 = Ref1; } } bool Status = true; #ifdef MSH_ADJACENCIES_INCLUDE_TOPOLOGY if(Count==2) Status = UpdateLink(TmpBuffer[0], TmpBuffer[1], LastRef0, LastRef1, faces); #else if(Count==2) Status = UpdateLink(TmpBuffer[0], TmpBuffer[1], LastRef0, LastRef1, faces, create); #endif return Status; } AdjacenciesBuilder::AdjacenciesBuilder() { } AdjacenciesBuilder::~AdjacenciesBuilder() { } /////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// /** * Initializes the component. * \param create [in] the creation structure * \return true if success. */ /////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// bool AdjacenciesBuilder::Init(const ADJACENCIESCREATE& create) { // Checkings if(!create.NbFaces) return false; // Get some bytes mNbFaces = create.NbFaces; mFaces = PX_NEW(AdjTriangle)[mNbFaces]; AdjEdge* Edges = PX_NEW_TEMP(AdjEdge)[mNbFaces*3]; PxU32 NbEdges=0; // Feed me with triangles..... for(PxU32 i=0;i