// 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-2017 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