From 7115f60b91b5717d90f643fd692010905c7004db Mon Sep 17 00:00:00 2001 From: Bryan Galdrikian Date: Thu, 31 May 2018 11:36:08 -0700 Subject: Blast 1.1.3. See docs/release_notes.txt. --- .../source/NvBlastExtAuthoringTriangulator.cpp | 1186 ++++++++++---------- 1 file changed, 593 insertions(+), 593 deletions(-) mode change 100644 => 100755 sdk/extensions/authoring/source/NvBlastExtAuthoringTriangulator.cpp (limited to 'sdk/extensions/authoring/source/NvBlastExtAuthoringTriangulator.cpp') diff --git a/sdk/extensions/authoring/source/NvBlastExtAuthoringTriangulator.cpp b/sdk/extensions/authoring/source/NvBlastExtAuthoringTriangulator.cpp old mode 100644 new mode 100755 index c4e80f8..89045eb --- a/sdk/extensions/authoring/source/NvBlastExtAuthoringTriangulator.cpp +++ b/sdk/extensions/authoring/source/NvBlastExtAuthoringTriangulator.cpp @@ -1,594 +1,594 @@ -// 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) 2016-2018 NVIDIA Corporation. All rights reserved. - - -// This warning arises when using some stl containers with older versions of VC -// c:\program files (x86)\microsoft visual studio 12.0\vc\include\xtree(1826): warning C4702: unreachable code -#include "NvPreprocessor.h" -#if NV_VC && NV_VC < 14 -#pragma warning(disable : 4702) -#endif -#include "NvBlastExtAuthoringTriangulator.h" -#include "NvBlastExtAuthoringMesh.h" -#include "NvBlastExtAuthoringTypes.h" -#include -#include "NvPreprocessor.h" -#include -#include -#include -#include "NvBlastExtAuthoringBooleanTool.h" -#include -#include - -using physx::PxVec3; -using physx::PxVec2; - -namespace Nv -{ -namespace Blast -{ -NV_FORCE_INLINE bool compareTwoFloats(float a, float b) -{ - return std::abs(b - a) <= FLT_EPSILON * std::abs(b + a); -} -NV_FORCE_INLINE bool compareTwoVertices(const PxVec3& a, const PxVec3& b) -{ - return compareTwoFloats(a.x, b.x) && compareTwoFloats(a.y, b.y) && compareTwoFloats(a.z, b.z); -} -NV_FORCE_INLINE bool compareTwoVertices(const PxVec2& a, const PxVec2& b) -{ - return compareTwoFloats(a.x, b.x) && compareTwoFloats(a.y, b.y); -} - -NV_FORCE_INLINE float getRotation(const PxVec2& a, const PxVec2& b) -{ - return a.x * b.y - a.y * b.x; -} - -NV_FORCE_INLINE bool pointInside(PxVec2 a, PxVec2 b, PxVec2 c, PxVec2 pnt) -{ - if (compareTwoVertices(a, pnt) || compareTwoVertices(b, pnt) || compareTwoVertices(c, pnt)) - { - return false; - } - float v1 = (getRotation((b - a), (pnt - a))); - float v2 = (getRotation((c - b), (pnt - b))); - float v3 = (getRotation((a - c), (pnt - c))); - - return (v1 >= 0.0f && v2 >= 0.0f && v3 >= 0.0f) || - (v1 <= 0.0f && v2 <= 0.0f && v3 <= 0.0f); - -} -void Triangulator::triangulatePolygonWithEarClipping(std::vector& inputPolygon, Vertex* vert, ProjectionDirections dir) -{ - // return; - //for (uint32_t i = 0; i < inputPolygon.size(); ++i) - //{ - // mBaseMeshTriangles.push_back(TriangleIndexed(inputPolygon[i], inputPolygon[i], inputPolygon[(i + 1) % inputPolygon.size()])); - //} - //return; - int32_t vCount = static_cast(inputPolygon.size()); - - if (vCount < 3) - { - return; - } - for (int32_t curr = 0; curr < vCount && vCount > 2; ++curr) - { - int32_t prev = (curr == 0) ? vCount - 1 : curr - 1; - int32_t next = (curr == vCount - 1) ? 0 : curr + 1; - - Vertex cV = vert[inputPolygon[curr]]; - Vertex nV = vert[inputPolygon[prev]]; - Vertex pV = vert[inputPolygon[next]]; - - PxVec2 cVp = getProjectedPoint(cV.p, dir); - PxVec2 nVp = getProjectedPoint(nV.p, dir); - PxVec2 pVp = getProjectedPoint(pV.p, dir); - - // Check wheather curr is ear-tip - float rot = getRotation((pVp - nVp).getNormalized(), (cVp - nVp).getNormalized()); - if (!(dir & OPPOSITE_WINDING)) rot = -rot; - if (rot > 0.0001) - { - bool good = true; - for (int vrt = 0; vrt < vCount; ++vrt) - { - if (vrt == curr || vrt == prev || vrt == next) continue; - if (pointInside(cVp, nVp, pVp, getProjectedPoint(vert[inputPolygon[vrt]].p, dir))) - { - good = false; - break; - } - } - if (good) - { - mBaseMeshTriangles.push_back(TriangleIndexed(inputPolygon[curr], inputPolygon[prev], inputPolygon[next])); - vCount--; - inputPolygon.erase(inputPolygon.begin() + curr); - curr = -1; - } - } - } -} - - - -struct LoopInfo -{ - LoopInfo() - { - used = false; - } - PxVec3 normal; - float area; - int32_t index; - bool used; - bool operator<(const LoopInfo& b) const - { - return area < b.area; - } -}; - -int32_t unitePolygons(std::vector& externalLoop, std::vector& internalLoop, Vertex* vrx, ProjectionDirections dir) -{ - if (externalLoop.size() < 3 || internalLoop.size() < 3) - return 1; - /** - Find point with maximum x-coordinate - */ - float x_max = -MAXIMUM_EXTENT; - int32_t mIndex = -1; - for (uint32_t i = 0; i < internalLoop.size(); ++i) - { - float nx = getProjectedPoint(vrx[internalLoop[i]].p, dir).x; - if (nx > x_max) - { - mIndex = i; - x_max = nx; - } - } - if (mIndex == -1) - { - return 1; - } - - /** - Search for base point on external loop - */ - float minX = MAXIMUM_EXTENT; - int32_t vrtIndex = -1; - bool isFromBuffer = 0; - PxVec2 holePoint = getProjectedPoint(vrx[internalLoop[mIndex]].p, dir); - PxVec2 computedPoint; - for (uint32_t i = 0; i < externalLoop.size(); ++i) - { - int32_t nx = (i + 1) % externalLoop.size(); - PxVec2 pnt1 = getProjectedPoint(vrx[externalLoop[i]].p, dir); - PxVec2 pnt2 = getProjectedPoint(vrx[externalLoop[nx]].p, dir); - if (pnt1.x < x_max && pnt2.x < x_max) - { - continue; - } - PxVec2 vc = pnt2 - pnt1; - if (vc.y == 0 && pnt1.y == holePoint.y) - { - if (pnt1.x < minX && pnt1.x < pnt2.x && pnt1.x > x_max) - { - minX = pnt1.x; - vrtIndex = i; - isFromBuffer = true; - } - if (pnt2.x < minX && pnt2.x < pnt1.x && pnt2.x > x_max) - { - minX = pnt2.x; - vrtIndex = nx; - isFromBuffer = true; - } - } - else - { - float t = (holePoint.y - pnt1.y) / vc.y; - if (t <= 1 && t >= 0) - { - PxVec2 tempPoint = vc * t + pnt1; - if (tempPoint.x < minX && tempPoint.x > x_max) - { - minX = tempPoint.x; - vrtIndex = i; - isFromBuffer = false; - computedPoint = tempPoint; - } - } - } - } - if (vrtIndex == -1) - { - // std::cout << "Triangulation: base vertex for inner loop is not found..." << std::endl; - return 1; - } - int32_t bridgePoint = -1; - float bestAngle = 100; - if (!isFromBuffer) - { - PxVec2 ex1 = getProjectedPoint(vrx[externalLoop[vrtIndex]].p, dir); - PxVec2 ex2 = getProjectedPoint(vrx[externalLoop[(vrtIndex + 1) % externalLoop.size()]].p, dir); - - if (ex1.x > ex2.x) - { - vrtIndex = (vrtIndex + 1) % externalLoop.size(); - ex1 = ex2; - } - /* Check if some point is inside triangle */ - bool notFound = true; - for (int32_t i = 0; i < (int32_t)externalLoop.size(); ++i) - { - PxVec2 tempPoint = getProjectedPoint(vrx[externalLoop[i]].p, dir); - if (pointInside(holePoint, ex1, computedPoint, tempPoint)) - { - notFound = false; - PxVec2 cVp = getProjectedPoint(vrx[externalLoop[i]].p, dir); - PxVec2 pVp = getProjectedPoint(vrx[externalLoop[(i - 1 + externalLoop.size()) % externalLoop.size()]].p, dir); - PxVec2 nVp = getProjectedPoint(vrx[externalLoop[(i + 1) % externalLoop.size()]].p, dir); - float rt = getRotation((cVp - pVp).getNormalized(), (nVp - pVp).getNormalized()); - if ((dir & OPPOSITE_WINDING)) rt = -rt; - if (rt < 0.000001) - continue; - float tempAngle = PxVec2(1, 0).dot((tempPoint - holePoint).getNormalized()); - if (bestAngle < tempAngle) - { - bestAngle = tempAngle; - bridgePoint = i; - } - } - } - if (notFound) - { - bridgePoint = vrtIndex; - } - if (bridgePoint == -1) - { - // std::cout << "Triangulation: bridge vertex for inner loop is not found..." << std::endl; - return 1; - } - } - else - { - bridgePoint = vrtIndex; - } - std::vector temporal; - - for (int32_t i = 0; i <= bridgePoint; ++i) - { - temporal.push_back(externalLoop[i]); - } - temporal.push_back(internalLoop[mIndex]); - for (int32_t i = (mIndex + 1) % internalLoop.size(); i != mIndex; i = (i + 1) % internalLoop.size()) - { - temporal.push_back(internalLoop[i]); - } - temporal.push_back(internalLoop[mIndex]); - for (uint32_t i = bridgePoint; i < externalLoop.size(); ++i) - { - temporal.push_back(externalLoop[i]); - } - externalLoop = temporal; - return 0; -} - -void Triangulator::buildPolygonAndTriangulate(std::vector& edges, Vertex* vertices, int32_t userData, int32_t materialId, int32_t smoothingGroup) -{ - std::vector > serializedLoops; - - std::set visitedVertices; - std::vector used(edges.size(), 0); - uint32_t collected = 0; - - std::vector edgesIds; - /** - Add first edge to polygon - */ - edgesIds.push_back(0); - visitedVertices.insert(edges[0].s); - visitedVertices.insert(edges[0].e); - used[0] = true; - collected = 1; - uint32_t lastEdge = 0; - bool successfullPass = false; - for (; collected < edges.size();) - { - successfullPass = false; - for (uint32_t p = 0; p < edges.size(); ++p) - { - if (used[p] == 0 && edges[p].s == edges[lastEdge].e) - { - successfullPass = true; - collected++; - used[p] = true; - edgesIds.push_back(p); - lastEdge = p; - if (visitedVertices.find(edges[p].e) != visitedVertices.end()) // if we formed loop, detach it and triangulate - { - serializedLoops.push_back(std::vector()); - std::vector& serializedPositions = serializedLoops.back(); - while (edgesIds.size() > 0) - { - serializedPositions.push_back(edges[edgesIds.back()].s); - visitedVertices.erase(edges[edgesIds.back()].s); - if (edges[edgesIds.back()].s == edges[p].e) - { - edgesIds.pop_back(); - break; - } - edgesIds.pop_back(); - } - if (edgesIds.size() > 0) - { - lastEdge = edgesIds.back(); - } - else - { - for (uint32_t t = 0; t < edges.size(); ++t) - { - if (used[t] == 0) - { - edgesIds.push_back(t); - visitedVertices.insert(edges[t].s); - visitedVertices.insert(edges[t].e); - used[t] = true; - collected++; - lastEdge = t; - break; - } - } - } - } - else - { - visitedVertices.insert(edges[p].e); - } - } - } - if (!successfullPass) - { - break; - } - } - - std::vector loopsInfo(serializedLoops.size()); - // Compute normal to whole polygon, and areas of loops - PxVec3 wholeFacetNormal(0, 0, 0); - for (uint32_t loop = 0; loop < serializedLoops.size(); ++loop) - { - PxVec3 loopNormal(0, 0, 0); - std::vector& pos = serializedLoops[loop]; - for (uint32_t vrt = 1; vrt + 1 < serializedLoops[loop].size(); ++vrt) - { - loopNormal += (vertices[pos[vrt]].p - vertices[pos[0]].p).cross(vertices[pos[vrt + 1]].p - vertices[pos[0]].p); - } - loopsInfo[loop].area = loopNormal.magnitude(); - loopsInfo[loop].normal = loopNormal; - loopsInfo[loop].index = loop; - wholeFacetNormal += loopNormal; - } - - // Change areas signs according to winding direction - for (uint32_t loop = 0; loop < serializedLoops.size(); ++loop) - { - if (wholeFacetNormal.dot(loopsInfo[loop].normal) < 0) - { - loopsInfo[loop].area = -loopsInfo[loop].area; - } - } - ProjectionDirections dir = getProjectionDirection(wholeFacetNormal); - std::sort(loopsInfo.begin(), loopsInfo.end()); - - std::vector tempPositions; - int32_t oldSize = static_cast(mBaseMeshTriangles.size()); - for (uint32_t extPoly = 0; extPoly < loopsInfo.size(); ++extPoly) - { - if (loopsInfo[extPoly].area < 0) - { - continue; // Polygon with negative area is hole - } - int32_t baseLoop = loopsInfo[extPoly].index; - for (uint32_t intPoly = 0; intPoly < loopsInfo.size(); ++intPoly) - { - if (loopsInfo[intPoly].area > 0 || loopsInfo[intPoly].used || std::abs(loopsInfo[intPoly].area) > loopsInfo[extPoly].area) - { - continue; - } - int32_t holeLoop = loopsInfo[intPoly].index; - - if (!unitePolygons(serializedLoops[baseLoop], serializedLoops[holeLoop], vertices, dir)) - { - loopsInfo[intPoly].used = true; - }; - } - triangulatePolygonWithEarClipping(serializedLoops[baseLoop],vertices, dir); - } - for (uint32_t i = oldSize; i < mBaseMeshTriangles.size(); ++i) - { - mBaseMeshTriangles[i].userData = userData; - mBaseMeshTriangles[i].materialId = materialId; - mBaseMeshTriangles[i].smoothingGroup = smoothingGroup; - } -} - -NV_FORCE_INLINE int32_t Triangulator::addVerticeIfNotExist(const Vertex& p) -{ - auto it = mVertMap.find(p); - if (it == mVertMap.end()) - { - mVertMap[p] = static_cast(mVertices.size()); - mVertices.push_back(p); - return static_cast(mVertices.size()) - 1; - } - else - { - return it->second; - } -} - -NV_FORCE_INLINE void Triangulator::addEdgeIfValid(EdgeWithParent& ed) -{ - if (ed.s == ed.e) - return; - EdgeWithParent opposite(ed.e, ed.s, ed.parent); - auto it = mEdgeMap.find(opposite); - if (it == mEdgeMap.end()) - { - mEdgeMap[ed] = static_cast(mBaseMeshEdges.size()); - mBaseMeshEdges.push_back(ed); - } - else - { - if (mBaseMeshEdges[it->second].s == NOT_VALID_VERTEX) - { - mBaseMeshEdges[it->second].s = ed.s; - mBaseMeshEdges[it->second].e = ed.e; - } - else - { - mBaseMeshEdges[it->second].s = NOT_VALID_VERTEX; - } - } -} - - - -void Triangulator::prepare(const Mesh* mesh) -{ - const Edge* ed = mesh->getEdges(); - const Vertex* vr = mesh->getVertices(); - mBaseMapping.resize(mesh->getVerticesCount()); - for (uint32_t i = 0; i < mesh->getFacetCount(); ++i) - { - const Facet* fc = mesh->getFacet(i); - for (uint32_t j = fc->firstEdgeNumber; j < fc->firstEdgeNumber + fc->edgesCount; ++j) - { - int32_t a = addVerticeIfNotExist(vr[ed[j].s]); - int32_t b = addVerticeIfNotExist(vr[ed[j].e]); - mBaseMapping[ed[j].s] = a; - mBaseMapping[ed[j].e] = b; - EdgeWithParent e(a, b, i); - addEdgeIfValid(e); - } - } - std::vector temp; - temp.reserve(mBaseMeshEdges.size()); - for (uint32_t i = 0; i < mBaseMeshEdges.size(); ++i) - { - if (mBaseMeshEdges[i].s != NOT_VALID_VERTEX) - { - temp.push_back(mBaseMeshEdges[i]); - } - } - mBaseMeshEdges = temp; -} - -void Triangulator::reset() -{ - mVertices.clear(); - mBaseMeshEdges.clear(); - mVertMap.clear(); - mEdgeMap.clear(); - mBaseMeshTriangles.clear(); - mBaseMeshResultTriangles.clear(); -} - -void Triangulator::triangulate(const Mesh* mesh) -{ - reset(); - if (mesh == nullptr || !mesh->isValid()) - { - return; - } - prepare(mesh); - if (mBaseMeshEdges.empty()) - { - return; - } - std::vector temp; - int32_t fP = mBaseMeshEdges[0].parent; - for (uint32_t i = 0; i < mBaseMeshEdges.size(); ++i) - { - if (fP != mBaseMeshEdges[i].parent) - { - if (temp.empty() == false) - { - buildPolygonAndTriangulate(temp, mVertices.data(), mesh->getFacet(fP)->userData, mesh->getFacet(fP)->materialId, mesh->getFacet(fP)->smoothingGroup); - } - temp.clear(); - fP = mBaseMeshEdges[i].parent; - } - temp.push_back(Edge(mBaseMeshEdges[i].s, mBaseMeshEdges[i].e)); - } - buildPolygonAndTriangulate(temp, mVertices.data(), mesh->getFacet(fP)->userData, mesh->getFacet(fP)->materialId, mesh->getFacet(fP)->smoothingGroup); - - /* Build final triangles */ - mBaseMeshResultTriangles.clear(); - for (uint32_t i = 0; i < mBaseMeshTriangles.size(); ++i) - { - if (mBaseMeshTriangles[i].ea == NOT_VALID_VERTEX) - { - continue; - } - mBaseMeshResultTriangles.push_back(Triangle(mVertices[mBaseMeshTriangles[i].ea], mVertices[mBaseMeshTriangles[i].eb], mVertices[mBaseMeshTriangles[i].ec])); - mBaseMeshResultTriangles.back().userData = mBaseMeshTriangles[i].userData; - mBaseMeshResultTriangles.back().materialId = mBaseMeshTriangles[i].materialId; - mBaseMeshResultTriangles.back().smoothingGroup = mBaseMeshTriangles[i].smoothingGroup; - - } - mBaseMeshUVFittedTriangles = mBaseMeshResultTriangles; // Uvs will be fitted later, in FractureTool. - computePositionedMapping(); -} - -void Triangulator::computePositionedMapping() -{ - std::map mPosMap; - mPositionMappedVrt.clear(); - mPositionMappedVrt.resize(mVertices.size()); - - for (uint32_t i = 0; i < mVertices.size(); ++i) - { - auto it = mPosMap.find(mVertices[i].p); - - if (it == mPosMap.end()) - { - mPosMap[mVertices[i].p] = i; - mPositionMappedVrt[i] = i; - } - else - { - mPositionMappedVrt[i] = it->second; - } - } -} - -} // namespace Blast +// 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) 2016-2018 NVIDIA Corporation. All rights reserved. + + +// This warning arises when using some stl containers with older versions of VC +// c:\program files (x86)\microsoft visual studio 12.0\vc\include\xtree(1826): warning C4702: unreachable code +#include "NvPreprocessor.h" +#if NV_VC && NV_VC < 14 +#pragma warning(disable : 4702) +#endif +#include "NvBlastExtAuthoringTriangulator.h" +#include "NvBlastExtAuthoringMesh.h" +#include "NvBlastExtAuthoringTypes.h" +#include +#include "NvPreprocessor.h" +#include +#include +#include +#include "NvBlastExtAuthoringBooleanTool.h" +#include +#include + +using physx::PxVec3; +using physx::PxVec2; + +namespace Nv +{ +namespace Blast +{ +NV_FORCE_INLINE bool compareTwoFloats(float a, float b) +{ + return std::abs(b - a) <= FLT_EPSILON * std::abs(b + a); +} +NV_FORCE_INLINE bool compareTwoVertices(const PxVec3& a, const PxVec3& b) +{ + return compareTwoFloats(a.x, b.x) && compareTwoFloats(a.y, b.y) && compareTwoFloats(a.z, b.z); +} +NV_FORCE_INLINE bool compareTwoVertices(const PxVec2& a, const PxVec2& b) +{ + return compareTwoFloats(a.x, b.x) && compareTwoFloats(a.y, b.y); +} + +NV_FORCE_INLINE float getRotation(const PxVec2& a, const PxVec2& b) +{ + return a.x * b.y - a.y * b.x; +} + +NV_FORCE_INLINE bool pointInside(PxVec2 a, PxVec2 b, PxVec2 c, PxVec2 pnt) +{ + if (compareTwoVertices(a, pnt) || compareTwoVertices(b, pnt) || compareTwoVertices(c, pnt)) + { + return false; + } + float v1 = (getRotation((b - a), (pnt - a))); + float v2 = (getRotation((c - b), (pnt - b))); + float v3 = (getRotation((a - c), (pnt - c))); + + return (v1 >= 0.0f && v2 >= 0.0f && v3 >= 0.0f) || + (v1 <= 0.0f && v2 <= 0.0f && v3 <= 0.0f); + +} +void Triangulator::triangulatePolygonWithEarClipping(std::vector& inputPolygon, Vertex* vert, ProjectionDirections dir) +{ + // return; + //for (uint32_t i = 0; i < inputPolygon.size(); ++i) + //{ + // mBaseMeshTriangles.push_back(TriangleIndexed(inputPolygon[i], inputPolygon[i], inputPolygon[(i + 1) % inputPolygon.size()])); + //} + //return; + int32_t vCount = static_cast(inputPolygon.size()); + + if (vCount < 3) + { + return; + } + for (int32_t curr = 0; curr < vCount && vCount > 2; ++curr) + { + int32_t prev = (curr == 0) ? vCount - 1 : curr - 1; + int32_t next = (curr == vCount - 1) ? 0 : curr + 1; + + Vertex cV = vert[inputPolygon[curr]]; + Vertex nV = vert[inputPolygon[prev]]; + Vertex pV = vert[inputPolygon[next]]; + + PxVec2 cVp = getProjectedPoint(cV.p, dir); + PxVec2 nVp = getProjectedPoint(nV.p, dir); + PxVec2 pVp = getProjectedPoint(pV.p, dir); + + // Check wheather curr is ear-tip + float rot = getRotation((pVp - nVp).getNormalized(), (cVp - nVp).getNormalized()); + if (!(dir & OPPOSITE_WINDING)) rot = -rot; + if (rot > 0.0001) + { + bool good = true; + for (int vrt = 0; vrt < vCount; ++vrt) + { + if (vrt == curr || vrt == prev || vrt == next) continue; + if (pointInside(cVp, nVp, pVp, getProjectedPoint(vert[inputPolygon[vrt]].p, dir))) + { + good = false; + break; + } + } + if (good) + { + mBaseMeshTriangles.push_back(TriangleIndexed(inputPolygon[curr], inputPolygon[prev], inputPolygon[next])); + vCount--; + inputPolygon.erase(inputPolygon.begin() + curr); + curr = -1; + } + } + } +} + + + +struct LoopInfo +{ + LoopInfo() + { + used = false; + } + PxVec3 normal; + float area; + int32_t index; + bool used; + bool operator<(const LoopInfo& b) const + { + return area < b.area; + } +}; + +int32_t unitePolygons(std::vector& externalLoop, std::vector& internalLoop, Vertex* vrx, ProjectionDirections dir) +{ + if (externalLoop.size() < 3 || internalLoop.size() < 3) + return 1; + /** + Find point with maximum x-coordinate + */ + float x_max = -MAXIMUM_EXTENT; + int32_t mIndex = -1; + for (uint32_t i = 0; i < internalLoop.size(); ++i) + { + float nx = getProjectedPoint(vrx[internalLoop[i]].p, dir).x; + if (nx > x_max) + { + mIndex = i; + x_max = nx; + } + } + if (mIndex == -1) + { + return 1; + } + + /** + Search for base point on external loop + */ + float minX = MAXIMUM_EXTENT; + int32_t vrtIndex = -1; + bool isFromBuffer = 0; + PxVec2 holePoint = getProjectedPoint(vrx[internalLoop[mIndex]].p, dir); + PxVec2 computedPoint; + for (uint32_t i = 0; i < externalLoop.size(); ++i) + { + int32_t nx = (i + 1) % externalLoop.size(); + PxVec2 pnt1 = getProjectedPoint(vrx[externalLoop[i]].p, dir); + PxVec2 pnt2 = getProjectedPoint(vrx[externalLoop[nx]].p, dir); + if (pnt1.x < x_max && pnt2.x < x_max) + { + continue; + } + PxVec2 vc = pnt2 - pnt1; + if (vc.y == 0 && pnt1.y == holePoint.y) + { + if (pnt1.x < minX && pnt1.x < pnt2.x && pnt1.x > x_max) + { + minX = pnt1.x; + vrtIndex = i; + isFromBuffer = true; + } + if (pnt2.x < minX && pnt2.x < pnt1.x && pnt2.x > x_max) + { + minX = pnt2.x; + vrtIndex = nx; + isFromBuffer = true; + } + } + else + { + float t = (holePoint.y - pnt1.y) / vc.y; + if (t <= 1 && t >= 0) + { + PxVec2 tempPoint = vc * t + pnt1; + if (tempPoint.x < minX && tempPoint.x > x_max) + { + minX = tempPoint.x; + vrtIndex = i; + isFromBuffer = false; + computedPoint = tempPoint; + } + } + } + } + if (vrtIndex == -1) + { + // std::cout << "Triangulation: base vertex for inner loop is not found..." << std::endl; + return 1; + } + int32_t bridgePoint = -1; + float bestAngle = 100; + if (!isFromBuffer) + { + PxVec2 ex1 = getProjectedPoint(vrx[externalLoop[vrtIndex]].p, dir); + PxVec2 ex2 = getProjectedPoint(vrx[externalLoop[(vrtIndex + 1) % externalLoop.size()]].p, dir); + + if (ex1.x > ex2.x) + { + vrtIndex = (vrtIndex + 1) % externalLoop.size(); + ex1 = ex2; + } + /* Check if some point is inside triangle */ + bool notFound = true; + for (int32_t i = 0; i < (int32_t)externalLoop.size(); ++i) + { + PxVec2 tempPoint = getProjectedPoint(vrx[externalLoop[i]].p, dir); + if (pointInside(holePoint, ex1, computedPoint, tempPoint)) + { + notFound = false; + PxVec2 cVp = getProjectedPoint(vrx[externalLoop[i]].p, dir); + PxVec2 pVp = getProjectedPoint(vrx[externalLoop[(i - 1 + externalLoop.size()) % externalLoop.size()]].p, dir); + PxVec2 nVp = getProjectedPoint(vrx[externalLoop[(i + 1) % externalLoop.size()]].p, dir); + float rt = getRotation((cVp - pVp).getNormalized(), (nVp - pVp).getNormalized()); + if ((dir & OPPOSITE_WINDING)) rt = -rt; + if (rt < 0.000001) + continue; + float tempAngle = PxVec2(1, 0).dot((tempPoint - holePoint).getNormalized()); + if (bestAngle < tempAngle) + { + bestAngle = tempAngle; + bridgePoint = i; + } + } + } + if (notFound) + { + bridgePoint = vrtIndex; + } + if (bridgePoint == -1) + { + // std::cout << "Triangulation: bridge vertex for inner loop is not found..." << std::endl; + return 1; + } + } + else + { + bridgePoint = vrtIndex; + } + std::vector temporal; + + for (int32_t i = 0; i <= bridgePoint; ++i) + { + temporal.push_back(externalLoop[i]); + } + temporal.push_back(internalLoop[mIndex]); + for (int32_t i = (mIndex + 1) % internalLoop.size(); i != mIndex; i = (i + 1) % internalLoop.size()) + { + temporal.push_back(internalLoop[i]); + } + temporal.push_back(internalLoop[mIndex]); + for (uint32_t i = bridgePoint; i < externalLoop.size(); ++i) + { + temporal.push_back(externalLoop[i]); + } + externalLoop = temporal; + return 0; +} + +void Triangulator::buildPolygonAndTriangulate(std::vector& edges, Vertex* vertices, int32_t userData, int32_t materialId, int32_t smoothingGroup) +{ + std::vector > serializedLoops; + + std::set visitedVertices; + std::vector used(edges.size(), 0); + uint32_t collected = 0; + + std::vector edgesIds; + /** + Add first edge to polygon + */ + edgesIds.push_back(0); + visitedVertices.insert(edges[0].s); + visitedVertices.insert(edges[0].e); + used[0] = true; + collected = 1; + uint32_t lastEdge = 0; + bool successfullPass = false; + for (; collected < edges.size();) + { + successfullPass = false; + for (uint32_t p = 0; p < edges.size(); ++p) + { + if (used[p] == 0 && edges[p].s == edges[lastEdge].e) + { + successfullPass = true; + collected++; + used[p] = true; + edgesIds.push_back(p); + lastEdge = p; + if (visitedVertices.find(edges[p].e) != visitedVertices.end()) // if we formed loop, detach it and triangulate + { + serializedLoops.push_back(std::vector()); + std::vector& serializedPositions = serializedLoops.back(); + while (edgesIds.size() > 0) + { + serializedPositions.push_back(edges[edgesIds.back()].s); + visitedVertices.erase(edges[edgesIds.back()].s); + if (edges[edgesIds.back()].s == edges[p].e) + { + edgesIds.pop_back(); + break; + } + edgesIds.pop_back(); + } + if (edgesIds.size() > 0) + { + lastEdge = edgesIds.back(); + } + else + { + for (uint32_t t = 0; t < edges.size(); ++t) + { + if (used[t] == 0) + { + edgesIds.push_back(t); + visitedVertices.insert(edges[t].s); + visitedVertices.insert(edges[t].e); + used[t] = true; + collected++; + lastEdge = t; + break; + } + } + } + } + else + { + visitedVertices.insert(edges[p].e); + } + } + } + if (!successfullPass) + { + break; + } + } + + std::vector loopsInfo(serializedLoops.size()); + // Compute normal to whole polygon, and areas of loops + PxVec3 wholeFacetNormal(0, 0, 0); + for (uint32_t loop = 0; loop < serializedLoops.size(); ++loop) + { + PxVec3 loopNormal(0, 0, 0); + std::vector& pos = serializedLoops[loop]; + for (uint32_t vrt = 1; vrt + 1 < serializedLoops[loop].size(); ++vrt) + { + loopNormal += (vertices[pos[vrt]].p - vertices[pos[0]].p).cross(vertices[pos[vrt + 1]].p - vertices[pos[0]].p); + } + loopsInfo[loop].area = loopNormal.magnitude(); + loopsInfo[loop].normal = loopNormal; + loopsInfo[loop].index = loop; + wholeFacetNormal += loopNormal; + } + + // Change areas signs according to winding direction + for (uint32_t loop = 0; loop < serializedLoops.size(); ++loop) + { + if (wholeFacetNormal.dot(loopsInfo[loop].normal) < 0) + { + loopsInfo[loop].area = -loopsInfo[loop].area; + } + } + ProjectionDirections dir = getProjectionDirection(wholeFacetNormal); + std::sort(loopsInfo.begin(), loopsInfo.end()); + + std::vector tempPositions; + int32_t oldSize = static_cast(mBaseMeshTriangles.size()); + for (uint32_t extPoly = 0; extPoly < loopsInfo.size(); ++extPoly) + { + if (loopsInfo[extPoly].area < 0) + { + continue; // Polygon with negative area is hole + } + int32_t baseLoop = loopsInfo[extPoly].index; + for (uint32_t intPoly = 0; intPoly < loopsInfo.size(); ++intPoly) + { + if (loopsInfo[intPoly].area > 0 || loopsInfo[intPoly].used || std::abs(loopsInfo[intPoly].area) > loopsInfo[extPoly].area) + { + continue; + } + int32_t holeLoop = loopsInfo[intPoly].index; + + if (!unitePolygons(serializedLoops[baseLoop], serializedLoops[holeLoop], vertices, dir)) + { + loopsInfo[intPoly].used = true; + }; + } + triangulatePolygonWithEarClipping(serializedLoops[baseLoop],vertices, dir); + } + for (uint32_t i = oldSize; i < mBaseMeshTriangles.size(); ++i) + { + mBaseMeshTriangles[i].userData = userData; + mBaseMeshTriangles[i].materialId = materialId; + mBaseMeshTriangles[i].smoothingGroup = smoothingGroup; + } +} + +NV_FORCE_INLINE int32_t Triangulator::addVerticeIfNotExist(const Vertex& p) +{ + auto it = mVertMap.find(p); + if (it == mVertMap.end()) + { + mVertMap[p] = static_cast(mVertices.size()); + mVertices.push_back(p); + return static_cast(mVertices.size()) - 1; + } + else + { + return it->second; + } +} + +NV_FORCE_INLINE void Triangulator::addEdgeIfValid(EdgeWithParent& ed) +{ + if (ed.s == ed.e) + return; + EdgeWithParent opposite(ed.e, ed.s, ed.parent); + auto it = mEdgeMap.find(opposite); + if (it == mEdgeMap.end()) + { + mEdgeMap[ed] = static_cast(mBaseMeshEdges.size()); + mBaseMeshEdges.push_back(ed); + } + else + { + if (mBaseMeshEdges[it->second].s == NOT_VALID_VERTEX) + { + mBaseMeshEdges[it->second].s = ed.s; + mBaseMeshEdges[it->second].e = ed.e; + } + else + { + mBaseMeshEdges[it->second].s = NOT_VALID_VERTEX; + } + } +} + + + +void Triangulator::prepare(const Mesh* mesh) +{ + const Edge* ed = mesh->getEdges(); + const Vertex* vr = mesh->getVertices(); + mBaseMapping.resize(mesh->getVerticesCount()); + for (uint32_t i = 0; i < mesh->getFacetCount(); ++i) + { + const Facet* fc = mesh->getFacet(i); + for (uint32_t j = fc->firstEdgeNumber; j < fc->firstEdgeNumber + fc->edgesCount; ++j) + { + int32_t a = addVerticeIfNotExist(vr[ed[j].s]); + int32_t b = addVerticeIfNotExist(vr[ed[j].e]); + mBaseMapping[ed[j].s] = a; + mBaseMapping[ed[j].e] = b; + EdgeWithParent e(a, b, i); + addEdgeIfValid(e); + } + } + std::vector temp; + temp.reserve(mBaseMeshEdges.size()); + for (uint32_t i = 0; i < mBaseMeshEdges.size(); ++i) + { + if (mBaseMeshEdges[i].s != NOT_VALID_VERTEX) + { + temp.push_back(mBaseMeshEdges[i]); + } + } + mBaseMeshEdges = temp; +} + +void Triangulator::reset() +{ + mVertices.clear(); + mBaseMeshEdges.clear(); + mVertMap.clear(); + mEdgeMap.clear(); + mBaseMeshTriangles.clear(); + mBaseMeshResultTriangles.clear(); +} + +void Triangulator::triangulate(const Mesh* mesh) +{ + reset(); + if (mesh == nullptr || !mesh->isValid()) + { + return; + } + prepare(mesh); + if (mBaseMeshEdges.empty()) + { + return; + } + std::vector temp; + int32_t fP = mBaseMeshEdges[0].parent; + for (uint32_t i = 0; i < mBaseMeshEdges.size(); ++i) + { + if (fP != mBaseMeshEdges[i].parent) + { + if (temp.empty() == false) + { + buildPolygonAndTriangulate(temp, mVertices.data(), mesh->getFacet(fP)->userData, mesh->getFacet(fP)->materialId, mesh->getFacet(fP)->smoothingGroup); + } + temp.clear(); + fP = mBaseMeshEdges[i].parent; + } + temp.push_back(Edge(mBaseMeshEdges[i].s, mBaseMeshEdges[i].e)); + } + buildPolygonAndTriangulate(temp, mVertices.data(), mesh->getFacet(fP)->userData, mesh->getFacet(fP)->materialId, mesh->getFacet(fP)->smoothingGroup); + + /* Build final triangles */ + mBaseMeshResultTriangles.clear(); + for (uint32_t i = 0; i < mBaseMeshTriangles.size(); ++i) + { + if (mBaseMeshTriangles[i].ea == NOT_VALID_VERTEX) + { + continue; + } + mBaseMeshResultTriangles.push_back(Triangle(mVertices[mBaseMeshTriangles[i].ea], mVertices[mBaseMeshTriangles[i].eb], mVertices[mBaseMeshTriangles[i].ec])); + mBaseMeshResultTriangles.back().userData = mBaseMeshTriangles[i].userData; + mBaseMeshResultTriangles.back().materialId = mBaseMeshTriangles[i].materialId; + mBaseMeshResultTriangles.back().smoothingGroup = mBaseMeshTriangles[i].smoothingGroup; + + } + mBaseMeshUVFittedTriangles = mBaseMeshResultTriangles; // Uvs will be fitted later, in FractureTool. + computePositionedMapping(); +} + +void Triangulator::computePositionedMapping() +{ + std::map mPosMap; + mPositionMappedVrt.clear(); + mPositionMappedVrt.resize(mVertices.size()); + + for (uint32_t i = 0; i < mVertices.size(); ++i) + { + auto it = mPosMap.find(mVertices[i].p); + + if (it == mPosMap.end()) + { + mPosMap[mVertices[i].p] = i; + mPositionMappedVrt[i] = i; + } + else + { + mPositionMappedVrt[i] = it->second; + } + } +} + +} // namespace Blast } // namespace Nv \ No newline at end of file -- cgit v1.2.3