BVB Source Codes

CRYENGINE Show AttachmentVClothPreProcess.cpp Source code

Return Download CRYENGINE: download AttachmentVClothPreProcess.cpp Source code - Download CRYENGINE Source code - Type:.cpp
  1. // Copyright 2001-2016 Crytek GmbH / Crytek Group. All rights reserved.
  2.  
  3. #include "stdafx.h"
  4. #include <CryMath/Cry_Math.h>
  5. #include <CryPhysics/primitives.h>
  6. #include "../CryPhysics/quotient.h"
  7. #include "AttachmentVClothPreProcess.h"
  8.  
  9. // boost is needed here for path finding algorithm over mesh (i.e., dijkstra)
  10. #include <iostream>
  11. #include <fstream>
  12. #include "CryCore/BoostHelpers.h"
  13.  
  14. // suppress warning from boost on MSVC: warning C4172: returning address of local variable or temporary
  15. // warning suppression has to go outside of the function to take effect.
  16. #ifdef CRY_PLATFORM_WINDOWS
  17.         #pragma warning(push)
  18.         #pragma warning(disable: 4172)
  19. #endif
  20. #ifdef CRY_PLATFORM_DURANGO
  21.         #pragma warning(push)
  22.         #pragma warning(disable: 4172)
  23. #endif
  24.  
  25. #include <boost/config.hpp>
  26. #include <boost/graph/graph_traits.hpp>
  27. // !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
  28. // !! the following fixes compiling problems with boost on orbis (i.e. include path problems with <boost/predef/other/endian.h>) :
  29. // !! orbis defines __FreeBSD__, but boost needs __Open_BSD__ defined to include <boost/predef/other/endian.h> within "adjacency_list.hpp" properly
  30. // !! might/SHOULD be removed if boost is updated and has fixed that problem
  31. // !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
  32.  
  33. #if CRY_PLATFORM_ORBIS
  34.         #ifdef __FreeBSD__
  35.                 #undef __FreeBSD__
  36.                 #define __OpenBSD__
  37.                 #define RESET__FreeBSD__
  38.         #endif
  39.         #include <boost/predef/other/endian.h>
  40.         #ifdef RESET__FreeBSD__
  41.                 #define __FreeBSD__
  42.                 #undef __OpenBSD__
  43.                 #undef RESET__FreeBSD__
  44.                 #undef BOOST_OS_BSD_OPEN
  45.                 #undef BOOST_OS_BSD
  46.                 #undef __OPEN_BSD__
  47.         #endif
  48. #endif
  49. #include <boost/graph/adjacency_list.hpp>
  50. #include <boost/graph/dijkstra_shortest_paths.hpp>
  51.  
  52. #ifdef CRY_PLATFORM_WINDOWS
  53.         #pragma warning(pop)
  54. #endif
  55. #ifdef CRY_PLATFORM_DURANGO
  56.         #pragma warning(pop)
  57. #endif
  58. ///////////////////////////////////////////////////////////////////////////////
  59.  
  60. bool AttachmentVClothPreProcess::PreProcess(std::vector<Vec3> const& vtx, std::vector<int> const& idx, std::vector<bool> const& attached)
  61. {
  62.         bool valid = true;
  63.  
  64.         // init data structures
  65.         m_lra.resize(vtx.size());
  66.  
  67.         // preprocess
  68.         LraDijkstra(vtx, idx, attached);
  69.         BendByTriangleAngle(vtx, idx, attached);
  70.         CreateLinks(vtx, idx);
  71.  
  72.         //////////////////////////////////////////////////////////////////////////
  73.  
  74.         // Debug output:
  75.         //CryWarning(VALIDATOR_MODULE_ANIMATION, VALIDATOR_WARNING, "[Cloth] No of Stretch Links %i", m_linksStretch.size());
  76.         //CryWarning(VALIDATOR_MODULE_ANIMATION, VALIDATOR_WARNING, "[Cloth] No of Shear Links %i", m_linksShear.size());
  77.         //CryWarning(VALIDATOR_MODULE_ANIMATION, VALIDATOR_WARNING, "[Cloth] No of bend Links %i", m_linksBend.size());
  78.  
  79.         return valid;
  80. }
  81.  
  82. bool AttachmentVClothPreProcess::LraDijkstra(std::vector<Vec3> const& vtx, std::vector<int> const& idx, std::vector<bool> const& attached)
  83. {
  84.         using namespace boost;
  85.  
  86.         typedef adjacency_list<listS, vecS, undirectedS,
  87.                                boost::property<boost::vertex_index_t, int>, property<edge_weight_t, float>> graph_t;
  88.         typedef graph_traits<graph_t>::vertex_descriptor vertex_descriptor;
  89.         typedef std::pair<int, int>                      Edge;
  90.  
  91.         int nVtx = (int)vtx.size();
  92.         int nTriangles = (int)idx.size() / 3;
  93.         int nEdges = (int)idx.size();
  94.  
  95.         // generate data structure for Dijkstra
  96.  
  97.         // add edges of all triangles
  98.         std::vector<Edge> edgeArray;
  99.         edgeArray.reserve(nEdges);
  100.         const int* tri = &idx[0];
  101.         for (int i = 0; i < nTriangles; i++)
  102.         {
  103.                 int idx = i * 3;
  104.                 edgeArray.push_back(Edge(tri[idx], tri[idx + 1]));
  105.                 edgeArray.push_back(Edge(tri[idx + 1], tri[idx + 2]));
  106.                 edgeArray.push_back(Edge(tri[idx], tri[idx + 2]));
  107.         }
  108.  
  109.         // fill weights with length of edges
  110.         std::vector<float> weights;
  111.         weights.reserve(edgeArray.size());
  112.         for (auto it = edgeArray.begin(); it != edgeArray.end(); ++it)
  113.         {
  114.                 const float distance = (vtx[(*it).first] - vtx[(*it).second]).GetLengthFast();
  115.                 weights.push_back(distance);
  116.         }
  117.  
  118.         // add one special node with weight 0, which is connected to all attached vtx
  119.         // this is later on used as source, thus, multiple sources can be actually handled, which is not possible directly with boost::dijkstra
  120.         for (int i = 0; i < nVtx; i++)
  121.         {
  122.                 if (attached[i])
  123.                 {
  124.                         edgeArray.push_back(Edge(nVtx, i));
  125.                         weights.push_back(0.0f);
  126.                 }
  127.         }
  128.         // update sizes
  129.         nVtx += 1;
  130.         nEdges = (int)edgeArray.size();
  131.  
  132.         // init graph
  133.         {
  134.                 graph_t g(&edgeArray[0], &edgeArray[0] + edgeArray.size(), &weights[0], nVtx);
  135.  
  136.                 // acquire containers for dijkstra-results, i.e. direct-neighbor-parent and distance
  137.                 property_map<graph_t, edge_weight_t>::type weightmap = get(edge_weight, g);
  138.                 std::vector<vertex_descriptor> p(num_vertices(g)); // will take each vtx next parent
  139.                 std::vector<float> d(num_vertices(g));             // will take distance to source
  140.                 int source = nVtx - 1;
  141.                 vertex_descriptor s = vertex(source, g);
  142.  
  143.                 // search shortest paths
  144.                 dijkstra_shortest_paths(g, s,
  145.                                         predecessor_map(boost::make_iterator_property_map(p.begin(), get(boost::vertex_index, g))).
  146.                                         distance_map(boost::make_iterator_property_map(d.begin(), get(boost::vertex_index, g))));
  147.  
  148.                 // store best source & distance to that one
  149.                 {
  150.                         graph_traits<graph_t>::vertex_iterator vi, vend;
  151.                         for (std::tie(vi, vend) = vertices(g); vi != vend; ++vi)
  152.                         {
  153.                                 const int idx = *vi;
  154.  
  155.                                 bool _continue = false;
  156.                                 if (idx < 0) _continue = true;
  157.                                 if (idx >= d.size()) _continue = true;
  158.                                 if (idx >= p.size()) _continue = true;
  159.                                 if (idx >= *vend) _continue = true;
  160.                                 if (idx >= m_lra.size()) _continue = true; // this occurs, since size of m_lra is one less than the others
  161.  
  162.                                 if (_continue)
  163.                                 {
  164.                                         // CryWarning(VALIDATOR_MODULE_ANIMATION, VALIDATOR_WARNING, "[Cloth] LraDijkstra::CONTINUE due to idx out of range:: %i   # %i,%i,%i,%i[d.size,p.size,*vend,m_lra.size()]", idx, d.size(), p.size(), *vend, m_lra.size());
  165.                                         continue;
  166.                                 }
  167.  
  168.                                 assert(idx < *vend);
  169.                                 assert(idx < d.size());
  170.                                 const float distance = d[idx];
  171.                                 const int nextParent = p[idx];
  172.  
  173.                                 m_lra[idx].lraNextParent = -1;
  174.                                 if (idx == source) continue;     // this is the source node, not existing in m_particlesHot, since added for graph traversing reasons, thus, do nothing
  175.                                 if (idx == nextParent) continue; // this is the source node or something went wrong, do nothing
  176.                                 m_lra[idx].lraDist = 0;          // default: no lra, i.e. no path existing / disconnected parts
  177.                                 m_lra[idx].lraIdx = -1;          // default: no lra, i.e. no path existing / disconnected parts
  178.                                 m_lra[idx].lraNextParent = nextParent;
  179.                                 if (distance < 0.001f) continue;         // this is an attached vtx, thus, no lra
  180.                                 if (distance > FLT_MAX * 0.5f) continue; // no path existing, disconnected mesh, thus, no lra
  181.  
  182.                                 // if we are here a path has been found
  183.                                 m_lra[idx].lraDist = distance;
  184.                                 m_lra[idx].lraNextParent = nextParent;
  185.                                 m_lra[idx].lraIdx = 0; // this enables later the search for the closest attached constraint
  186.                         }
  187.                 }
  188.  
  189.                 // all paths are set, thus, search for each particle the closest attached vtx by walking the whole path until next parent equals 'source'
  190.                 nVtx = vtx.size();
  191.                 for (int idx = 0; idx < nVtx; idx++)
  192.                 {
  193.                         if (attached[idx]) continue;
  194.                         if (m_lra[idx].lraIdx == -1) continue; // no path available, (-1 is default value, see above)
  195.                         int actualNode = idx;
  196.                         while (m_lra[actualNode].lraNextParent != source)
  197.                         {
  198.                                 int nextParentNode = m_lra[actualNode].lraNextParent;
  199.                                 assert(nextParentNode >= 0);
  200.                                 assert(nextParentNode < nVtx); // +1 // +1 due to source
  201.                                 actualNode = nextParentNode;
  202.                         }
  203.                         m_lra[idx].lraIdx = actualNode;
  204.                 }
  205.  
  206.                 // free by hand to let boost be faster
  207.                 g.m_edges.clear();
  208.                 g.m_vertices.clear();
  209.                 g.m_edges.resize(0);
  210.                 g.m_vertices.resize(0);
  211.                 g.clear();
  212.                 stl::free_container(p);
  213.                 stl::free_container(d);
  214.         }
  215.  
  216.         // extension: sort by distance
  217.         {
  218.                 // 1. sort not attached particles by distance to attachment
  219.                 struct MyClassSort
  220.                 {
  221.                         int   idx;
  222.                         float dist;
  223.                         MyClassSort(int _idx, float _dist) : idx(_idx), dist(_dist)
  224.                         {
  225.                         }
  226.                 };
  227.                 std::vector<MyClassSort> myClassSortList;
  228.                 myClassSortList.reserve(nVtx);
  229.                 for (int i = 0; i < nVtx; i++)
  230.                 {
  231.                         if (attached[i]) continue;
  232.                         myClassSortList.push_back(MyClassSort(i, m_lra[i].lraDist));
  233.                 }
  234.                 std::sort(myClassSortList.begin(), myClassSortList.end(), [](const MyClassSort& a, const MyClassSort& b) { return a.dist < b.dist; });
  235.                 // copy list of indices to m_lraNotAttachedOrderedIdx
  236.                 m_lraNotAttachedOrderedIdx.clear();
  237.                 m_lraNotAttachedOrderedIdx.reserve(myClassSortList.size());
  238.                 for (auto it = myClassSortList.begin(); it != myClassSortList.end(); ++it)
  239.                 {
  240.                         m_lraNotAttachedOrderedIdx.push_back((*it).idx);
  241.                 }
  242.  
  243.                 stl::free_container(myClassSortList); // assist VC memory management
  244.         }
  245.  
  246.         stl::free_container(edgeArray); // assist VC memory management
  247.         stl::free_container(weights);   // assist VC memory management
  248.  
  249.         return true;
  250. }
  251.  
  252. //////////////////////////////////////////////////////////////////////////
  253. //////////////////////////////////////////////////////////////////////////
  254.  
  255. namespace VClothPreProcessUtils
  256. {
  257. static inline void BendEdgeEnsureOrder(std::pair<int, int>& e)
  258. {
  259.         if (e.first > e.second) std::swap(e.first, e.second);
  260. }
  261.  
  262. static inline int AddToMapTriangleIdxToListBendTrianglesIdx(
  263.   std::vector<SBendTriangle>& listBendTriangles,
  264.   std::unordered_map<int, int>& mapTriangleIdxToListBendTrianglesIdx,
  265.   const int* meshIdx,
  266.   const Vec3* meshVtx,
  267.   int idxTriangle
  268.   )
  269. {
  270.         if (mapTriangleIdxToListBendTrianglesIdx.find(idxTriangle) != mapTriangleIdxToListBendTrianglesIdx.end())
  271.         {
  272.                 return mapTriangleIdxToListBendTrianglesIdx[idxTriangle];     // already existing
  273.         }
  274.  
  275.         int idxP0 = meshIdx[idxTriangle * 3 + 0];
  276.         int idxP1 = meshIdx[idxTriangle * 3 + 1];
  277.         int idxP2 = meshIdx[idxTriangle * 3 + 2];
  278.         const Vec3& p0 = meshVtx[idxP0];
  279.         const Vec3& p1 = meshVtx[idxP1];
  280.         const Vec3& p2 = meshVtx[idxP2];
  281.         // check for area, if valid triangle
  282.         float s = 100.0f;                                                                          // fight floating point precision for cross-product & length
  283.         if (((p1 * s - p0 * s).cross(p2 * s - p0 * s)).GetLengthSquared() < 0.0001f) return -1;    // degenerated triangle
  284.  
  285.         // else: add to map
  286.         mapTriangleIdxToListBendTrianglesIdx[idxTriangle] = (int)listBendTriangles.size();
  287.         SBendTriangle bendTriangle(idxP0, idxP1, idxP2);
  288.         listBendTriangles.push_back(bendTriangle);
  289.         return mapTriangleIdxToListBendTrianglesIdx[idxTriangle];
  290. }
  291.  
  292. static inline void AddBendTrianglePair(
  293.   std::vector<SBendTrianglePair>& listBendTrianglePair,
  294.   const int* meshIdx,
  295.   int idxTriangle0,
  296.   int idxTriangle1,
  297.   int idxListBendTriangles0,
  298.   int idxListBendTriangles1
  299.   )
  300. {
  301.         const int* t0 = &meshIdx[idxTriangle0 * 3];
  302.         const int* t1 = &meshIdx[idxTriangle1 * 3];
  303.  
  304.         // find same edge
  305.         bool found;
  306.         int edge0Idx = 0;
  307.         int edge1Idx = 0;
  308.         found = false;
  309.         for (int i = 0; i < 3; i++)
  310.         {
  311.                 for (int j = 0; j < 3; j++)
  312.                 {
  313.  
  314.                         if (!found)
  315.                         {
  316.                                 edge0Idx = i;
  317.                                 found = (t0[i] == t1[j]);
  318.                         }
  319.                 }
  320.         }
  321.         assert(found);
  322.         found = false;
  323.         for (int i = 2; i >= 0; i--)
  324.                 for (int j = 0; j < 3; j++)
  325.                         if (!found)
  326.                         {
  327.                                 edge1Idx = i;
  328.                                 found = (t0[i] == t1[j]);
  329.                         }
  330.         assert(found);
  331.  
  332.         // find vtx of each triangle, not belonging to edge
  333.         int idxP2 = edge0Idx == 1 ? 0 : (edge1Idx == 1 ? 2 : 1);
  334.         int idxP3 = 0;
  335.         found = false;
  336.         for (int i = 0; i < 3; i++)
  337.         {
  338.                 if ((t1[i] != t0[edge0Idx]) && (t1[i] != t0[edge1Idx]))
  339.                 {
  340.                         found = true;
  341.                         idxP3 = i;
  342.                 }
  343.         }
  344.         assert(found);
  345.  
  346.         int idxNormal0 = idxListBendTriangles0;
  347.         int idxNormal1 = idxListBendTriangles1;
  348.  
  349.         SBendTrianglePair bendTrianglePair(t0[edge0Idx], t0[edge1Idx], t0[idxP2], t1[idxP3], idxNormal0, idxNormal1);
  350.         listBendTrianglePair.push_back(bendTrianglePair);
  351. }
  352.  
  353. static inline float BendDetermineAngle(const Vec3& n0, const Vec3& n1, const Vec3 pRef0, const Vec3& pRef3)
  354. {
  355.         float nDotN = n0.dot(n1);
  356.         if (nDotN > 1.0f) nDotN = 1.0f;
  357.         if (nDotN < -1.0f) nDotN = -1.0f;
  358.         float alpha = acos(nDotN);
  359.         float sign = n0.dot(pRef3 - pRef0) > 0.0f ? -1.0f : 1.0f;
  360.         alpha *= sign;
  361.         return alpha;
  362. }
  363. }
  364.  
  365. bool AttachmentVClothPreProcess::BendByTriangleAngle(std::vector<Vec3> const& vtx, std::vector<int> const& idx, std::vector<bool> const& attached)
  366. {
  367.         typedef std::pair<int, int> BendEdge;
  368.         std::unordered_set<BendEdge, boost::hash<std::pair<int, int>>> edgeDone;
  369.         std::unordered_map<int, int> mapTriangleIdxToListBendTrianglesIdx;
  370.         m_listBendTrianglePairs.clear();
  371.         m_listBendTriangles.clear();
  372.  
  373.         int nTriangles = (int)idx.size() / 3;
  374.         int nEdges = (int)idx.size();
  375.         const int* meshIdx = &idx[0];
  376.         const Vec3* meshVtx = &vtx[0];
  377.  
  378.         if (nTriangles <= 1) return false;
  379.  
  380.         // debug
  381.         //int nEdgesWithNeighbor = 0;
  382.         //int nEdgesFromDegeneratedTriangle = 0;
  383.         //int nTriCandidatesGreater1=0;
  384.         //int nTriHasNoNeighbor = 0;
  385.  
  386.         // loop over all edges of all triangles
  387.         for (int i = 0; i < nTriangles - 1; i++)
  388.         {
  389.                 for (int e0 = 0; e0 < 3; e0++) // loop over edges
  390.                 {
  391.                         int idx0 = meshIdx[i * 3 + e0];
  392.                         int idx1 = meshIdx[i * 3 + (e0 + 1) % 3];
  393.                         BendEdge edge0(idx0, idx1);
  394.                         VClothPreProcessUtils::BendEdgeEnsureOrder(edge0);
  395.  
  396.                         if (edgeDone.find(edge0) != edgeDone.end()) continue; // already handled this edge
  397.  
  398.                         // loop over all edges of all following triangles and compare edges
  399.                         int triCandidate = -1;
  400.                         int triCandidateNo = 0;
  401.                         for (int j = i + 1; j < nTriangles; j++)
  402.                         {
  403.                                 for (int e1 = 0; e1 < 3; e1++)
  404.                                 {
  405.                                         int idx0 = meshIdx[j * 3 + e1];
  406.                                         int idx1 = meshIdx[j * 3 + (e1 + 1) % 3];
  407.                                         BendEdge edge1(idx0, idx1);
  408.                                         VClothPreProcessUtils::BendEdgeEnsureOrder(edge1);
  409.                                         if (edge0 == edge1)
  410.                                         {
  411.                                                 triCandidate = j;
  412.                                                 triCandidateNo++;
  413.                                         }
  414.                                 }
  415.                         }
  416.  
  417.                         //if (triCandidateNo > 1) nTriCandidatesGreater1++; // debug
  418.                         //if (triCandidate==-1) nTriHasNoNeighbor++; // debug
  419.  
  420.                         if ((triCandidateNo == 1) && triCandidate >= 0) // found neighbor, since only two triangles are sharing this edge
  421.                         {
  422.                                 int idxListBendTriangles0 = VClothPreProcessUtils::AddToMapTriangleIdxToListBendTrianglesIdx(m_listBendTriangles, mapTriangleIdxToListBendTrianglesIdx, meshIdx, meshVtx, i);
  423.                                 int idxListBendTriangles1 = VClothPreProcessUtils::AddToMapTriangleIdxToListBendTrianglesIdx(m_listBendTriangles, mapTriangleIdxToListBendTrianglesIdx, meshIdx, meshVtx, triCandidate);
  424.  
  425.                                 bool isDegeneratedTriangle = (idxListBendTriangles0 < 0) || (idxListBendTriangles1 < 0);
  426.                                 if (!isDegeneratedTriangle)
  427.                                 {
  428.                                         VClothPreProcessUtils::AddBendTrianglePair(m_listBendTrianglePairs, meshIdx, i, triCandidate, idxListBendTriangles0, idxListBendTriangles1);
  429.                                         //nEdgesWithNeighbor++; // debug
  430.                                 }
  431.                                 //else { // debug
  432.                                 //      nEdgesFromDegeneratedTriangle++;
  433.                                 // }
  434.                         }
  435.  
  436.                         edgeDone.insert(edge0);
  437.                 }
  438.         }
  439.         //CryWarning(VALIDATOR_MODULE_ANIMATION, VALIDATOR_ERROR, "[Cloth] BendByTriangleAngleInit() BendEdges: Found %i edges with neighbors, out of %i edges total. Edge Done: %i", nEdgesWithNeighbor, nEdges,(int)edgeDone.size());
  440.         //CryWarning(VALIDATOR_MODULE_ANIMATION, VALIDATOR_ERROR, "[Cloth] BendByTriangleAngleInit() Degenerated: %i", nEdgesFromDegeneratedTriangle);
  441.         //CryWarning(VALIDATOR_MODULE_ANIMATION, VALIDATOR_ERROR, "[Cloth] BendByTriangleAngleInit() nTriCandidatesGreater1: %i", nTriCandidatesGreater1);
  442.         //CryWarning(VALIDATOR_MODULE_ANIMATION, VALIDATOR_ERROR, "[Cloth] BendByTriangleAngleInit() nTriHasNoNeighbor: %i", nTriHasNoNeighbor);
  443.  
  444.         // determine phi0
  445.         // 1st: determine all normals
  446.         DetermineTriangleNormals(vtx, m_listBendTriangles);
  447.  
  448.         // 2nd: determine angle
  449.         for (auto it = m_listBendTrianglePairs.begin(); it != m_listBendTrianglePairs.end(); it++)
  450.         {
  451.                 Vec3& n0 = m_listBendTriangles[(*it).idxNormal0].normal;
  452.                 Vec3& n1 = m_listBendTriangles[(*it).idxNormal1].normal;
  453.  
  454.                 it->phi0 = VClothPreProcessUtils::BendDetermineAngle(n0, n1, vtx[it->p3], vtx[it->p0]);
  455.         }
  456.  
  457.         return true;
  458. }
  459.  
  460. bool AttachmentVClothPreProcess::DetermineTriangleNormals(std::vector<Vec3> const& vtx, std::vector<SBendTriangle>& tri)
  461. {
  462.         for (auto it = tri.begin(); it != tri.end(); it++)
  463.         {
  464.                 it->normal = ((vtx[it->p1] - vtx[it->p0]).cross(vtx[it->p2] - vtx[it->p0])).GetNormalizedFast();
  465.         }
  466.         return true;
  467. }
  468.  
  469. bool AttachmentVClothPreProcess::DetermineTriangleNormals(int nVertices, strided_pointer<Vec3> const& pVertices, std::vector<SBendTriangle>& tri)
  470. {
  471.         for (auto it = tri.begin(); it != tri.end(); it++)
  472.         {
  473.                 it->normal = ((pVertices[it->p1] - pVertices[it->p0]).cross(pVertices[it->p2] - pVertices[it->p0])).GetNormalizedFast();
  474.         }
  475.         return true;
  476. }
  477.  
  478. bool AttachmentVClothPreProcess::PruneWeldedVertices(std::vector<Vec3>& vtx, std::vector<int>& idx, std::vector<bool>& attached)
  479. {
  480.  
  481.         // look for welded vertices and prune them
  482.         int nWelded = 0;
  483.         std::vector<Vec3> unweldedVerts;
  484.         std::vector<bool> unweldedAttached;
  485.         std::vector<int> weldMap;
  486.  
  487.         // TODO: faster welded vertices detector - this is O(n^2) - see CharacterManager::LoadVClothGeometry
  488.         for (int i = 0; i < vtx.size(); i++)
  489.         {
  490.                 int iMap = -1;
  491.                 for (int j = i - 1; j >= 0; j--)
  492.                 {
  493.                         Vec3 delta = vtx[i] - vtx[j];
  494.                         if (delta.len() < 0.001f)
  495.                         {
  496.                                 iMap = weldMap[j];
  497.                                 nWelded++;
  498.                                 break;
  499.                         }
  500.                 }
  501.                 if (iMap >= 0)
  502.                         weldMap.push_back(iMap);
  503.                 else
  504.                 {
  505.                         weldMap.push_back(unweldedVerts.size());
  506.                         unweldedVerts.push_back(vtx[i]);
  507.                         unweldedAttached.push_back(attached[i]);
  508.                 }
  509.         }
  510.  
  511.         if (nWelded)
  512.         {
  513.                 //CryLog("[Character Cloth] Found %i welded vertices out of %i ", nWelded, (int)vtx.size());
  514.                 //printf("[Character Cloth] Found %i welded vertices out of %i ", nWelded, (int)vtx.size());
  515.         }
  516.  
  517.         // reconstruct indices
  518.         std::vector<int> unweldedIndices;
  519.         for (int i = 0; i < (int)idx.size(); i++)
  520.         {
  521.                 unweldedIndices.push_back(weldMap[idx[i]]);
  522.         }
  523.  
  524.         //////////////////////////////////////////////////////////////////////////
  525.         idx = unweldedIndices;
  526.         vtx = unweldedVerts;
  527.         attached = unweldedAttached;
  528.         //////////////////////////////////////////////////////////////////////////
  529.  
  530.         return true;
  531. }
  532.  
  533. bool AttachmentVClothPreProcess::RemoveDegeneratedTriangles(std::vector<Vec3>& vtx, std::vector<int>& idx, std::vector<bool>& attached)
  534. {
  535.         // remove degenerated triangles, by shifting them to the end and resize - similar to CryPhysics/trimesh.h
  536.         // move degenerate triangles to the end of the list
  537.         int i, j;
  538.         int nTris = (int)idx.size() / 3;
  539.         for (i = 0, j = nTris; i < j; )
  540.         {
  541.                 if (iszero(idx[i * 3] ^ idx[i * 3 + 1]) | iszero(idx[i * 3 + 1] ^ idx[i * 3 + 2]) |
  542.                     iszero(idx[i * 3 + 2] ^ idx[i * 3]))
  543.                 {
  544.                         j--;
  545.                         for (int k = 0; k < 3; k++)
  546.                         {
  547.                                 int itmp = idx[j * 3 + k];
  548.                                 idx[j * 3 + k] = idx[i * 3 + k];
  549.                                 idx[i * 3 + k] = itmp;
  550.                         }
  551.                 }
  552.                 else i++;
  553.         }
  554.         nTris = i;
  555.  
  556.         if (nTris * 3 < idx.size()) idx.resize(nTris * 3);
  557.  
  558.         return true;
  559. }
  560.  
  561. //////////////////////////////////////////////////////////////////////////
  562.  
  563. namespace VClothPreProcessUtils
  564. {
  565. struct STriInfo
  566. {
  567.         index_t ibuddy[3];
  568. };
  569.  
  570. template<class F>
  571. inline int IntersectLists(F* pSrc0, int nSrc0, F* pSrc1, int nSrc1, F* pDst)
  572. {
  573.         int i0, i1, n;
  574.         for (i0 = i1 = n = 0; ((i0 - nSrc0) & (i1 - nSrc1)) < 0; )
  575.         {
  576.                 const F a = pSrc0[i0];
  577.                 const F b = pSrc1[i1];
  578.                 F equal = iszero(a - b);
  579.                 pDst[n] = a;
  580.                 n += equal;
  581.                 i0 += isneg(a - b) + equal;
  582.                 i1 += isneg(b - a) + equal;
  583.         }
  584.         return n;
  585. }
  586. }
  587.  
  588. // on the basis of 'CTriMesh::CalculateTopology()'
  589. // int CalculateTopology(index_t* pIndices, int bCheckOnly = 0);
  590. bool AttachmentVClothPreProcess::CalculateTopology(std::vector<Vec3> const& vtx, std::vector<int> const& idx, std::vector<VClothPreProcessUtils::STriInfo>& pTopology)
  591. {
  592.         int nTris = idx.size() / 3;
  593.         int nVertices = vtx.size();
  594.         int i, j, i1, j1, itri, * pTris, * pVtxTris, * pEdgeTris, nBadEdges[2] = { 0, 0 };
  595.         Vec3 edge, v0, v1;
  596.         float elen2;
  597.         quotientf sina, minsina;
  598.  
  599.         pTopology.resize(nTris);
  600.  
  601.         // strided_pointer<Vec3mem> pVtxMem = strided_pointer<Vec3mem>((Vec3mem*)m_pVertices.data, m_pVertices.iStride);
  602.         const Vec3* pVtxMem = &vtx[0];
  603.  
  604.         memset(pTris = new int[nVertices + 1], 0, (nVertices + 1) * sizeof(int));  // for each used vtx, points to the corresponding tri list start
  605.         pVtxTris = new int[nTris * 4];                                             // holds tri lists for each used vtx
  606.         pEdgeTris = pVtxTris + nTris * 3;
  607.  
  608.         for (i = 0; i < nTris; i++)
  609.         {
  610.                 for (j = 0; j < 3; j++)
  611.                 {
  612.                         pTris[idx[i * 3 + j]]++;
  613.                 }
  614.         }
  615.         for (i = 0; i < nVertices; i++)
  616.         {
  617.                 pTris[i + 1] += pTris[i];
  618.         }
  619.         for (i = nTris - 1; i >= 0; i--)
  620.         {
  621.                 for (j = 0; j < 3; j++)
  622.                 {
  623.                         pVtxTris[--pTris[idx[i * 3 + j]]] = i;
  624.                 }
  625.         }
  626.         for (i = 0; i < nTris; i++)
  627.         {
  628.                 for (j = 0; j < 3; j++)
  629.                 {
  630.                         int nTrisIntersect = VClothPreProcessUtils::IntersectLists(pVtxTris + pTris[idx[i * 3 + j]], pTris[idx[i * 3 + j] + 1] - pTris[idx[i * 3 + j]],
  631.                                                                                    pVtxTris + pTris[idx[i * 3 + inc_mod3[j]]], pTris[idx[i * 3 + inc_mod3[j]] + 1] - pTris[idx[i * 3 + inc_mod3[j]]], pEdgeTris);
  632.                         assert(nTrisIntersect <= nTris);   // check for possible memory corruption in case of degenerative triangles
  633.                         // if (nTris!=2) - the mesh is not manifold
  634.                         if (nTrisIntersect == 2)
  635.                                 pTopology[i].ibuddy[j] = pEdgeTris[iszero(i - pEdgeTris[0])];
  636.                         else
  637.                         {
  638.                                 // among the other triangles sharing this edge, find the one that has it in reverse order
  639.                                 edge = pVtxMem[idx[i * 3 + inc_mod3[j]]] - pVtxMem[idx[i * 3 + j]];
  640.                                 v0 = pVtxMem[idx[i * 3 + dec_mod3[j]]] - pVtxMem[idx[i * 3 + j]];
  641.                                 v0 = v0 * (elen2 = edge.len2()) - edge * (edge * v0);
  642.                                 itri = -1;
  643.                                 minsina.set(3.0f, 1.0f);
  644.                                 for (i1 = 0; i1 < nTrisIntersect; i1++)
  645.                                 {
  646.                                         if (pEdgeTris[i1] != i)
  647.                                                 for (j1 = 0; j1 < 3; j1++)
  648.                                                 {
  649.                                                         if (idx[i * 3 + j] == idx[pEdgeTris[i1] * 3 + inc_mod3[j1]] && idx[i * 3 + inc_mod3[j]] == idx[pEdgeTris[i1] * 3 + j1])
  650.                                                         {
  651.                                                                 v1 = pVtxMem[idx[pEdgeTris[i1] * 3 + dec_mod3[j1]]] - pVtxMem[idx[i * 3 + j]];
  652.                                                                 v1 = v1 * elen2 - edge * (edge * v1);
  653.                                                                 sina.set(sqr_signed((v0 ^ v1) * edge), v0.len2() * v1.len2() * elen2);
  654.                                                                 float denom = isneg(1e10f - sina.y) * 1e-15f;
  655.                                                                 sina.x *= denom;
  656.                                                                 sina.y *= denom;
  657.                                                                 sina += isneg(sina) * 2.0f;
  658.                                                                 if (sina < minsina)
  659.                                                                 {
  660.                                                                         minsina = sina;
  661.                                                                         itri = pEdgeTris[i1];
  662.                                                                 }
  663.                                                         }
  664.                                                 }
  665.  
  666.                                 }
  667.                                 pTopology[i].ibuddy[j] = itri;
  668.                                 nBadEdges[min(nTrisIntersect - 1, 1)]++;
  669.                         }
  670.                 }
  671.         }
  672.  
  673.         delete[] pVtxTris;
  674.         delete[] pTris;
  675.         return (nBadEdges[0] + nBadEdges[1]) == 0;
  676. }
  677.  
  678. struct _SEdgeInfo
  679. {
  680.         int   m_iEdge;
  681.         float m_cost;
  682.         bool  m_skip;
  683.  
  684.         _SEdgeInfo() : m_iEdge(-1), m_cost(1e38f), m_skip(false) {}
  685. };
  686.  
  687. namespace VClothPreProcessUtils
  688. {
  689. // copied form StatObjPhys.cpp
  690. static inline int GetEdgeByBuddy(std::vector<VClothPreProcessUtils::STriInfo> const& pTopology, int itri, int itri_buddy)
  691. {
  692.         int iedge = 0, imask;
  693.         imask = pTopology[itri].ibuddy[1] - itri_buddy;
  694.         imask = (imask - 1) >> 31 ^ imask >> 31;
  695.         iedge = 1 & imask;
  696.         imask = pTopology[itri].ibuddy[2] - itri_buddy;
  697.         imask = (imask - 1) >> 31 ^ imask >> 31;
  698.         iedge = iedge & ~imask | 2 & imask;
  699.         return iedge;
  700. }
  701. }
  702.  
  703. bool AttachmentVClothPreProcess::CreateLinks(std::vector<Vec3> const& vtx, std::vector<int> const& idx)
  704. {
  705.         std::vector<VClothPreProcessUtils::STriInfo> pTopology;
  706.         CalculateTopology(vtx, idx, pTopology);
  707.  
  708.         //////////////////////////////////////////////////////////////////////////
  709.  
  710.         int nTris = idx.size() / 3;
  711.  
  712.         _SEdgeInfo(*pInfo)[3] = new _SEdgeInfo[nTris][3];
  713.         for (int i = 0; i < nTris; i++)
  714.         {
  715.                 for (int j = 0; j < 3; j++)
  716.                 {
  717.                         int i1 = idx[i * 3 + j];
  718.                         int i2 = idx[i * 3 + inc_mod3[j]];
  719.                         const Vec3& v1 = vtx[i1];
  720.                         const Vec3& v2 = vtx[i2];
  721.                         // compute the cost of the edge (squareness of quad)
  722.                         int adjTri = pTopology[i].ibuddy[j];
  723.                         if (adjTri >= 0)
  724.                         {
  725.                                 float cost;
  726.                                 int adjEdge = VClothPreProcessUtils::GetEdgeByBuddy(pTopology, adjTri, i);
  727.                                 int i3 = idx[i * 3 + dec_mod3[j]];
  728.                                 const Vec3& v3 = vtx[i3];
  729.                                 int i4 = idx[adjTri * 3 + dec_mod3[adjEdge]];
  730.                                 const Vec3& v4 = vtx[i4];
  731.                                 cost = fabs((v1 - v2).len() - (v3 - v4).len());         // difference between diagonals
  732.                                 // get the lowest value, although it should be the same
  733.                                 if (pInfo[adjTri][adjEdge].m_cost < cost)
  734.                                         cost = pInfo[adjTri][adjEdge].m_cost;
  735.                                 else
  736.                                         pInfo[adjTri][adjEdge].m_cost = cost;
  737.                                 pInfo[i][j].m_cost = cost;
  738.                         }
  739.                 }
  740.         }
  741.         // count the number of edges - for each tri, mark each edge, unless buddy already did it
  742.         int nEdges = 0;
  743.         for (int i = 0; i < nTris; i++)
  744.         {
  745.                 int bDegen = 0;
  746.                 float len[3];
  747.                 float minCost = 1e37f;
  748.                 int iedge = -1;
  749.                 for (int j = 0; j < 3; j++)
  750.                 {
  751.                         const Vec3& v1 = vtx[idx[i * 3 + j]];
  752.                         const Vec3& v2 = vtx[idx[i * 3 + inc_mod3[j]]];
  753.                         len[j] = (v1 - v2).len2();
  754.                         bDegen |= iszero(len[j]);
  755.                         int adjTri = pTopology[i].ibuddy[j];
  756.                         if (adjTri >= 0)
  757.                         {
  758.                                 int adjEdge = VClothPreProcessUtils::GetEdgeByBuddy(pTopology, adjTri, i);
  759.                                 float cost = pInfo[i][j].m_cost;
  760.                                 if (pInfo[adjTri][adjEdge].m_skip)
  761.                                         cost = -1e36f;
  762.                                 bool otherSkipped = false;
  763.                                 for (int k = 0; k < 3; k++)
  764.                                 {
  765.                                         if (pInfo[adjTri][k].m_skip && k != adjEdge)
  766.                                         {
  767.                                                 otherSkipped = true;
  768.                                                 break;
  769.                                         }
  770.                                 }
  771.                                 if (cost < minCost && !otherSkipped)
  772.                                 {
  773.                                         minCost = cost;
  774.                                         iedge = j;
  775.                                 }
  776.                         }
  777.                 }
  778.  
  779.                 int j = 0;
  780.                 if (iedge >= 0)
  781.                 {
  782.                         j = iedge & - bDegen;
  783.                         pInfo[i][iedge].m_skip = true;
  784.                 }
  785.                 do
  786.                 {
  787.                         if (pInfo[i][j].m_iEdge < 0 && !(j == iedge && !bDegen))
  788.                         {
  789.                                 int adjTri = pTopology[i].ibuddy[j];
  790.                                 if (adjTri >= 0)
  791.                                 {
  792.                                         int adjEdge = VClothPreProcessUtils::GetEdgeByBuddy(pTopology, adjTri, i);
  793.                                         pInfo[adjTri][adjEdge].m_iEdge = nEdges;
  794.                                 }
  795.                                 pInfo[i][j].m_iEdge = nEdges++;
  796.                         }
  797.                 }
  798.                 while (++j < 3 && !bDegen);
  799.         }
  800.         int num = ((nEdges / 2) + 1) * 2;
  801.         m_linksStretch.resize(num);
  802.         int* pVtxEdges = new int[nEdges * 2];
  803.         for (int i = 0; i < nTris; i++)
  804.         {
  805.                 for (int j = 0; j < 3; j++)
  806.                 {
  807.                         int iedge = pInfo[i][j].m_iEdge;
  808.                         if (iedge >= 0)
  809.                         {
  810.                                 int i0 = m_linksStretch[iedge].i1 = idx[i * 3 + j];
  811.                                 int i1 = m_linksStretch[iedge].i2 = idx[i * 3 + inc_mod3[j]];
  812.                                 m_linksStretch[iedge].lenSqr = (vtx[i0] - vtx[i1]).len2();
  813.                         }
  814.                 }
  815.         }
  816.         if (nEdges & 1)
  817.         {
  818.                 m_linksStretch[num - 1].skip = true;
  819.         }
  820.  
  821.         // for each vertex, trace ccw fan around it and store in m_pVtxEdges
  822.         STopology* pTopologyCCW = new STopology[vtx.size()];
  823.         int nVtxEdges = 0;
  824.         for (int i = 0; i < nTris; i++)
  825.         {
  826.                 for (int j = 0; j < 3; j++)
  827.                 {
  828.                         int ivtx = idx[i * 3 + j];
  829.                         if (!pTopologyCCW[ivtx].iSorted)
  830.                         {
  831.                                 int itri = i;
  832.                                 int iedge = j;
  833.                                 pTopologyCCW[ivtx].iStartEdge = nVtxEdges;
  834.                                 pTopologyCCW[ivtx].bFullFan = 1;
  835.                                 int itrinew;
  836.                                 do
  837.                                 {
  838.                                         // first, trace cw fan until we find an open edge (if any)
  839.                                         itrinew = pTopology[itri].ibuddy[iedge];
  840.                                         if (itrinew <= 0)
  841.                                                 break;
  842.                                         iedge = inc_mod3[VClothPreProcessUtils::GetEdgeByBuddy(pTopology, itrinew, itri)];
  843.                                         itri = itrinew;
  844.                                 }
  845.                                 while (itri != i);
  846.                                 int itri0 = itri;
  847.                                 do
  848.                                 {
  849.                                         // now trace ccw fan
  850.                                         assert(itri < nTris);
  851.                                         if (pInfo[itri][iedge].m_iEdge >= 0)
  852.                                                 pVtxEdges[nVtxEdges++] = pInfo[itri][iedge].m_iEdge;
  853.                                         itrinew = pTopology[itri].ibuddy[dec_mod3[iedge]];
  854.                                         if (itrinew < 0)
  855.                                         {
  856.                                                 if (pInfo[itri][dec_mod3[iedge]].m_iEdge >= 0)
  857.                                                         pVtxEdges[nVtxEdges++] = pInfo[itri][dec_mod3[iedge]].m_iEdge;
  858.                                                 pTopologyCCW[ivtx].bFullFan = 0;
  859.                                                 break;
  860.                                         }
  861.                                         iedge = VClothPreProcessUtils::GetEdgeByBuddy(pTopology, itrinew, itri);
  862.                                         itri = itrinew;
  863.                                 }
  864.                                 while (itri != itri0);
  865.                                 pTopologyCCW[ivtx].iEndEdge = nVtxEdges - 1;
  866.                                 pTopologyCCW[ivtx].iSorted = 1;
  867.                         }
  868.                 }
  869.         }
  870.         delete[] pInfo;
  871.  
  872.         // add shear and bending edges
  873.         m_linksShear.clear();
  874.         m_linksBend.clear();
  875.         for (int i = 0; i < nEdges; i++)
  876.         {
  877.                 int i1 = m_linksStretch[i].i1;
  878.                 int i2 = m_linksStretch[i].i2;
  879.                 // first point 1
  880.                 float maxLen = 0;
  881.                 int maxIdx = -1;
  882.                 bool maxAdded = false;
  883.                 for (int j = pTopologyCCW[i1].iStartEdge; j < pTopologyCCW[i1].iEndEdge + pTopologyCCW[i1].bFullFan; j++)
  884.                 {
  885.                         int i3 = m_linksStretch[pVtxEdges[j]].i2 + m_linksStretch[pVtxEdges[j]].i1 - i1;
  886.                         float len = (vtx[i3] - vtx[i2]).len2();
  887.                         bool valid = i3 != i1 && i2 < i3;
  888.                         if (len > maxLen)
  889.                         {
  890.                                 maxLen = len;
  891.                                 maxIdx = m_linksShear.size();
  892.                                 maxAdded = valid;
  893.                         }
  894.                         if (valid)
  895.                         {
  896.                                 SLink link;
  897.                                 link.i1 = i2;
  898.                                 link.i2 = i3;
  899.                                 link.lenSqr = len;
  900.                                 m_linksShear.push_back(link);
  901.                         }
  902.                 }
  903.                 // we make the assumption that the longest edge of all is a bending one
  904.                 if (maxIdx >= 0 && maxAdded && pTopologyCCW[i1].bFullFan)
  905.                 {
  906.                         m_linksBend.push_back(m_linksShear[maxIdx]);
  907.                         m_linksShear.erase(m_linksShear.begin() + maxIdx);
  908.                 }
  909.                 // then point 2
  910.                 maxLen = 0;
  911.                 maxIdx = -1;
  912.                 maxAdded = false;
  913.                 for (int j = pTopologyCCW[i2].iStartEdge; j < pTopologyCCW[i2].iEndEdge + pTopologyCCW[i2].bFullFan; j++)
  914.                 {
  915.                         int i3 = m_linksStretch[pVtxEdges[j]].i2 + m_linksStretch[pVtxEdges[j]].i1 - i2;
  916.                         float len = (vtx[i3] - vtx[i1]).len2();
  917.                         bool valid = i3 != i2 && i1 < i3;
  918.                         if (len > maxLen)
  919.                         {
  920.                                 maxLen = len;
  921.                                 maxIdx = m_linksShear.size();
  922.                                 maxAdded = valid;
  923.                         }
  924.                         if (valid)
  925.                         {
  926.                                 SLink link;
  927.                                 link.i1 = i1;
  928.                                 link.i2 = i3;
  929.                                 link.lenSqr = len;
  930.                                 m_linksShear.push_back(link);
  931.                         }
  932.                 }
  933.                 if (maxIdx >= 0 && maxAdded && pTopologyCCW[i2].bFullFan)
  934.                 {
  935.                         m_linksBend.push_back(m_linksShear[maxIdx]);
  936.                         m_linksShear.erase(m_linksShear.begin() + maxIdx);
  937.                 }
  938.         }
  939.  
  940.         //delete[] pTopology;
  941.         delete[] pVtxEdges;
  942.         m_linksStretch.resize(nEdges);
  943.  
  944.         return true;
  945. }
  946.  
downloadAttachmentVClothPreProcess.cpp Source code - Download CRYENGINE Source code
Related Source Codes/Software:
postal - 2017-06-11
reactide - Reactide is the first dedicated IDE for React web ... 2017-06-11
rkt - rkt is a pod-native container engine for Linux. It... 2017-06-11
uWebSockets - Tiny WebSockets https://for... 2017-06-11
realworld - TodoMVC for the RealWorld - Exemplary fullstack Me... 2017-06-11
CRYENGINE - CRYENGINE is a powerful real-time game development... 2017-06-11
goreplay - GoReplay is an open-source tool for capturing and ... 2017-06-10
pyenv - Simple Python version management 2017-06-10
redux-saga - An alternative side effect model for Redux apps ... 2017-06-10
angular-starter - 2017-06-10

 Back to top