713 lines
28 KiB
C++
713 lines
28 KiB
C++
//
|
|
// 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;i<mNbFaces;i++)
|
|
{
|
|
AdjTriangle* CurTri = &mFaces[i];
|
|
Nb+=CurTri->ComputeNbBoundaryEdges();
|
|
}
|
|
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<PxU32>* 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;i<mNbFaces;i++)
|
|
{
|
|
AdjTriangle* CurTri = &mFaces[i];
|
|
if(IS_BOUNDARY(CurTri->mATri[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<PxU32>* 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<ref1) AddEdge(ref0, ref1, id, nb_edges, edges);
|
|
else AddEdge(ref1, ref0, id, nb_edges, edges);
|
|
// Add edge 02 to database
|
|
if(ref0<ref2) AddEdge(ref0, ref2, id, nb_edges, edges);
|
|
else AddEdge(ref2, ref0, id, nb_edges, edges);
|
|
// Add edge 12 to database
|
|
if(ref1<ref2) AddEdge(ref1, ref2, id, nb_edges, edges);
|
|
else AddEdge(ref2, ref1, id, nb_edges, edges);
|
|
}
|
|
|
|
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
|
|
/**
|
|
* Updates the links in two adjacent triangles.
|
|
* \param first_tri [in] index of the first triangle
|
|
* \param second_tri [in] index of the second triangle
|
|
* \param ref0 [in] the common edge's first vertex reference
|
|
* \param ref1 [in] the common edge's second vertex reference
|
|
* \return true if success.
|
|
*/
|
|
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
|
|
#ifdef MSH_ADJACENCIES_INCLUDE_TOPOLOGY
|
|
static bool UpdateLink(PxU32 first_tri, PxU32 second_tri, PxU32 ref0, PxU32 ref1, AdjTriangle* faces)
|
|
#else
|
|
static bool UpdateLink(PxU32 first_tri, PxU32 second_tri, PxU32 ref0, PxU32 ref1, AdjTriangle* faces, const ADJACENCIESCREATE& create)
|
|
#endif
|
|
{
|
|
#ifdef MSH_ADJACENCIES_INCLUDE_TOPOLOGY
|
|
AdjTriangle& Tri0 = faces[first_tri]; // Catch the first triangle
|
|
AdjTriangle& Tri1 = faces[second_tri]; // Catch the second triangle
|
|
|
|
// Get the edge IDs. 0xff means input references are wrong.
|
|
PxU8 EdgeNb0 = Tri0.FindEdge(ref0, ref1); if(EdgeNb0==0xff) return SetIceError("Adjacencies::UpdateLink: invalid edge reference in first triangle");
|
|
PxU8 EdgeNb1 = Tri1.FindEdge(ref0, ref1); if(EdgeNb1==0xff) return SetIceError("Adjacencies::UpdateLink: invalid edge reference in second triangle");
|
|
|
|
// Update links. The two most significant bits contain the counterpart edge's ID.
|
|
Tri0.mATri[EdgeNb0] = second_tri |(PxU32(EdgeNb1)<<30);
|
|
Tri1.mATri[EdgeNb1] = first_tri |(PxU32(EdgeNb0)<<30);
|
|
#else
|
|
Gu::TriangleT<PxU32> 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<nb_edges;i++)
|
|
VRefs[i] = edges[i].Ref0;
|
|
Core.Sort(VRefs, nb_edges);
|
|
for(i=0;i<nb_edges;i++)
|
|
VRefs[i] = edges[i].Ref1;
|
|
Core.Sort(VRefs, nb_edges);
|
|
|
|
PX_DELETE_POD(VRefs);
|
|
}
|
|
const PxU32* Sorted = Core.GetRanks();
|
|
|
|
// Read the list in sorted order, look for similar edges
|
|
PxU32 LastRef0 = edges[Sorted[0]].Ref0;
|
|
PxU32 LastRef1 = edges[Sorted[0]].Ref1;
|
|
PxU32 Count = 0;
|
|
PxU32 TmpBuffer[3];
|
|
|
|
while(nb_edges--)
|
|
{
|
|
PxU32 SortedIndex = *Sorted++;
|
|
PxU32 Face = edges[SortedIndex].mFaceNb; // Owner face
|
|
PxU32 Ref0 = edges[SortedIndex].Ref0; // Vertex ref #1
|
|
PxU32 Ref1 = edges[SortedIndex].Ref1; // Vertex ref #2
|
|
if(Ref0==LastRef0 && Ref1==LastRef1)
|
|
{
|
|
// Current edge is the same as last one
|
|
TmpBuffer[Count++] = Face; // Store face number
|
|
// Only works with manifold meshes (i.e. an edge is not shared by more than 2 triangles)
|
|
if(Count==3)
|
|
{
|
|
Ps::getFoundation().error(PxErrorCode::eINVALID_OPERATION, __FILE__, __LINE__, "Adjacencies::CreateDatabase: can't work on non-manifold meshes.");
|
|
return false;
|
|
}
|
|
}
|
|
else
|
|
{
|
|
// Here we have a new edge (LastRef0, LastRef1) shared by Count triangles stored in TmpBuffer
|
|
if(Count==2)
|
|
{
|
|
// if Count==1 => 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<mNbFaces;i++)
|
|
{
|
|
// Get correct vertex references
|
|
const PxU32 Ref0 = create.DFaces ? create.DFaces[i*3+0] : create.WFaces ? create.WFaces[i*3+0] : 0;
|
|
const PxU32 Ref1 = create.DFaces ? create.DFaces[i*3+1] : create.WFaces ? create.WFaces[i*3+1] : 1;
|
|
const PxU32 Ref2 = create.DFaces ? create.DFaces[i*3+2] : create.WFaces ? create.WFaces[i*3+2] : 2;
|
|
|
|
// Add a triangle to the database
|
|
AddTriangle(Ref0, Ref1, Ref2, i, mFaces, NbEdges, Edges);
|
|
}
|
|
|
|
// At this point of the process we have mFaces & Edges filled with input data. That is:
|
|
// - a list of triangles with 3 NULL links (i.e. PX_INVALID_U32)
|
|
// - a list of mNbFaces*3 edges, each edge having 2 vertex references and an owner face.
|
|
|
|
// Here NbEdges should be equal to mNbFaces*3.
|
|
PX_ASSERT(NbEdges==mNbFaces*3);
|
|
|
|
#ifdef MSH_ADJACENCIES_INCLUDE_TOPOLOGY
|
|
bool Status = CreateDatabase(mFaces, NbEdges, Edges);
|
|
#else
|
|
bool Status = CreateDatabase(mFaces, NbEdges, Edges, create);
|
|
#endif
|
|
|
|
// We don't need the edges anymore
|
|
PX_DELETE_ARRAY(Edges);
|
|
|
|
#ifdef MSH_ADJACENCIES_INCLUDE_CONVEX_BITS
|
|
// Now create convex information. This creates coupling between adjacencies & edge-list but in this case it's actually the goal:
|
|
// mixing the two structures to save memory.
|
|
if(Status && create.Verts)
|
|
{
|
|
Gu::EDGELISTCREATE ELC;
|
|
ELC.NbFaces = create.NbFaces;
|
|
ELC.DFaces = create.DFaces; // That's where I like having a unified way to do things... We
|
|
ELC.WFaces = create.WFaces; // can just directly copy the same pointers.
|
|
ELC.FacesToEdges = true;
|
|
ELC.Verts = create.Verts;
|
|
ELC.Epsilon = create.Epsilon;
|
|
|
|
Gu::EdgeListBuilder EL;
|
|
if(EL.init(ELC))
|
|
{
|
|
for(PxU32 i=0;i<mNbFaces;i++)
|
|
{
|
|
const Gu::EdgeTriangleData& ET = EL.getEdgeTriangle(i);
|
|
if(Gu::EdgeTriangleAC::HasActiveEdge01(ET)) mFaces[i].mATri[EDGE01] |= 0x20000000;
|
|
else mFaces[i].mATri[EDGE01] &= ~0x20000000;
|
|
if(Gu::EdgeTriangleAC::HasActiveEdge20(ET)) mFaces[i].mATri[EDGE02] |= 0x20000000;
|
|
else mFaces[i].mATri[EDGE02] &= ~0x20000000;
|
|
if(Gu::EdgeTriangleAC::HasActiveEdge12(ET)) mFaces[i].mATri[EDGE12] |= 0x20000000;
|
|
else mFaces[i].mATri[EDGE12] &= ~0x20000000;
|
|
|
|
PX_ASSERT((Gu::EdgeTriangleAC::HasActiveEdge01(ET) && mFaces[i].HasActiveEdge01()) || (!Gu::EdgeTriangleAC::HasActiveEdge01(ET) && !mFaces[i].HasActiveEdge01()));
|
|
PX_ASSERT((Gu::EdgeTriangleAC::HasActiveEdge20(ET) && mFaces[i].HasActiveEdge20()) || (!Gu::EdgeTriangleAC::HasActiveEdge20(ET) && !mFaces[i].HasActiveEdge20()));
|
|
PX_ASSERT((Gu::EdgeTriangleAC::HasActiveEdge12(ET) && mFaces[i].HasActiveEdge12()) || (!Gu::EdgeTriangleAC::HasActiveEdge12(ET) && !mFaces[i].HasActiveEdge12()));
|
|
}
|
|
}
|
|
}
|
|
#endif
|
|
|
|
return Status;
|
|
}
|
|
/*
|
|
bool AdjacenciesBuilder::Save(Stream& stream) const
|
|
{
|
|
bool PlatformMismatch = PxPlatformMismatch();
|
|
|
|
// Export header
|
|
if(!WriteHeader('A', 'D', 'J', 'A', gVersion, PlatformMismatch, stream))
|
|
return false;
|
|
|
|
// Export adjacencies
|
|
// stream.StoreDword(mNbFaces);
|
|
WriteDword(mNbFaces, PlatformMismatch, stream);
|
|
|
|
// stream.StoreBuffer(mFaces, sizeof(AdjTriangle)*mNbFaces);
|
|
WriteDwordBuffer((const PxU32*)mFaces, mNbFaces*3, PlatformMismatch, stream);
|
|
|
|
return true;
|
|
}*/
|
|
//#endif
|