BVB Source Codes

CRYENGINE Show CTriangulator.cpp Source code

Return Download CRYENGINE: download CTriangulator.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 "CTriangulator.h"
  5. #include "AILog.h"
  6. #include <math.h>
  7. #include <algorithm>
  8. #include <limits>
  9. #include <CrySystem/ISystem.h>
  10.  
  11. #ifdef AI_FP_FAST
  12.         #pragma float_control(precise, on)
  13.         #pragma fenv_access(on)
  14. //#else
  15. //#error "!!!AISystem FP optimizations turned off - if you do want this, remove this #error from CTriangulator.cpp"
  16. #endif
  17.  
  18. //====================================================================
  19. // CTriangulator
  20. //====================================================================
  21. CTriangulator::CTriangulator()
  22. {
  23.         m_vtxBBoxMin.x = 3000;
  24.         m_vtxBBoxMin.y = 3000;
  25.         m_vtxBBoxMin.z = 0;
  26.  
  27.         m_vtxBBoxMax.x = 0;
  28.         m_vtxBBoxMax.y = 0;
  29.         m_vtxBBoxMax.z = 0;
  30.  
  31.         m_curCutIdx = 0;
  32. }
  33.  
  34. //====================================================================
  35. // CTriangulator
  36. //====================================================================
  37. CTriangulator::~CTriangulator()
  38. {
  39. }
  40.  
  41. //====================================================================
  42. // DoesVertexExist2D
  43. //====================================================================
  44. bool CTriangulator::DoesVertexExist2D(real x, real y, real tol) const
  45. {
  46.         VARRAY::const_iterator i;
  47.         for (i = m_vVertices.begin(); i != m_vVertices.end(); ++i)
  48.         {
  49.                 const Vtx& v = *i;
  50.                 if ((fabs(x - v.x) < tol) && (fabs(y - v.y) < tol))
  51.                         return true;
  52.         }
  53.         return false;
  54. }
  55.  
  56. //====================================================================
  57. // AddVertex
  58. //====================================================================
  59. int CTriangulator::AddVertex(real x, real y, real z, bool bCollidable, bool bHideable)
  60. {
  61.         Vtx newvertex;
  62.         newvertex.x = x;
  63.         newvertex.y = y;
  64.         newvertex.z = z;
  65.         newvertex.bCollidable = bCollidable;
  66.         newvertex.bHideable = bHideable;
  67.  
  68.         if (newvertex.x < m_vtxBBoxMin.x)
  69.                 m_vtxBBoxMin.x = newvertex.x;
  70.         if (newvertex.x > m_vtxBBoxMax.x)
  71.                 m_vtxBBoxMax.x = newvertex.x;
  72.  
  73.         if (newvertex.y < m_vtxBBoxMin.y)
  74.                 m_vtxBBoxMin.y = newvertex.y;
  75.         if (newvertex.y > m_vtxBBoxMax.y)
  76.                 m_vtxBBoxMax.y = newvertex.y;
  77.  
  78.         VARRAY::iterator i;
  79.         i = std::find(m_vVertices.begin(), m_vVertices.end(), newvertex);
  80.  
  81.         if (i != m_vVertices.end())
  82.                 return -1;
  83.  
  84.         m_vVertices.push_back(newvertex);
  85.  
  86.         return (m_vVertices.size() - 1);
  87. }
  88.  
  89. //====================================================================
  90. // AddSegment
  91. //====================================================================
  92. void CTriangulator::AddSegment(const Vec3r& p1, const Vec3r& p2)
  93. {
  94.         m_cuts.push_back(SSegment(p1, p2));
  95.         m_curCutIdx = 0;
  96. }
  97.  
  98. //====================================================================
  99. // GetSegment
  100. //====================================================================
  101. bool CTriangulator::GetSegment(Vec3r& p1, Vec3r& p2)
  102. {
  103.         if (m_curCutIdx >= m_cuts.size())
  104.                 return false;
  105.         p1 = m_cuts[m_curCutIdx].m_p1;
  106.         p2 = m_cuts[m_curCutIdx].m_p2;
  107.         ++m_curCutIdx;
  108.         return true;
  109. }
  110.  
  111. //====================================================================
  112. // Triangulate
  113. //====================================================================
  114. bool CTriangulator::Triangulate()
  115. {
  116.  
  117.         if (m_vVertices.empty()) return true;
  118.  
  119.         // init supertriangle and structures
  120.         if (!PrepForTriangulation())
  121.                 return false;
  122.  
  123.         // perform triangulation on any new vertices
  124.         if (!TriangulateNew())
  125.                 return false;
  126.  
  127.         return true;
  128. }
  129.  
  130. //====================================================================
  131. // GetVertices
  132. //====================================================================
  133. VARRAY CTriangulator::GetVertices()
  134. {
  135.         return m_vProcessed;
  136. }
  137.  
  138. //====================================================================
  139. // GetTriangles
  140. //====================================================================
  141. TARRAY CTriangulator::GetTriangles()
  142. {
  143.         return m_vTriangles;
  144. }
  145.  
  146. //====================================================================
  147. // PushUnique
  148. //====================================================================
  149. void CTriangulator::PushUnique(int a, int b)
  150. {
  151.         MYPOINT newpoint, oldpoint;
  152.         newpoint.x = a;
  153.         newpoint.y = b;
  154.         oldpoint.x = b;
  155.         oldpoint.y = a;
  156.  
  157.         tUniquePts::iterator i = std::find(m_uniquePts.begin(), m_uniquePts.end(), oldpoint);
  158.         if (i == m_uniquePts.end())
  159.                 m_uniquePts.push_back(newpoint);
  160.         else
  161.                 m_uniquePts.erase(i);
  162. }
  163.  
  164. //====================================================================
  165. // IsAntiClockwise
  166. //====================================================================
  167. bool CTriangulator::IsAntiClockwise(Tri* who)
  168. {
  169.         Vtx v1, v2, v3;
  170.  
  171.         v1 = m_vProcessed[who->v[0]];
  172.         v2 = m_vProcessed[who->v[1]];
  173.         v3 = m_vProcessed[who->v[2]];
  174.  
  175.         Vtx vec1, vec2;
  176.  
  177.         vec1.x = v1.x - v2.x;
  178.         vec1.y = v1.y - v2.y;
  179.  
  180.         vec2.x = v3.x - v2.x;
  181.         vec2.y = v3.y - v2.y;
  182.  
  183.         real f = vec1.x * vec2.y - vec2.x * vec1.y;
  184.  
  185.         if (f > 0) return true;
  186.  
  187.         return false;
  188. }
  189.  
  190. //====================================================================
  191. // Calculate
  192. //====================================================================
  193. bool CTriangulator::Calculate(Tri* pTri)
  194. {
  195.         const Vtx& v1 = m_vProcessed[pTri->v[0]];
  196.         const Vtx& v2 = m_vProcessed[pTri->v[1]];
  197.         const Vtx& v3 = m_vProcessed[pTri->v[2]];
  198.  
  199.         if (!IsPerpendicular(v1, v2, v3))
  200.                 CalcCircle(v1, v2, v3, pTri);
  201.         else if (!IsPerpendicular(v1, v3, v2))
  202.                 CalcCircle(v1, v3, v2, pTri);
  203.         else if (!IsPerpendicular(v2, v1, v3))
  204.                 CalcCircle(v2, v1, v3, pTri);
  205.         else if (!IsPerpendicular(v2, v3, v1))
  206.                 CalcCircle(v2, v3, v1, pTri);
  207.         else if (!IsPerpendicular(v3, v2, v1))
  208.                 CalcCircle(v3, v2, v1, pTri);
  209.         else if (!IsPerpendicular(v3, v1, v2))
  210.                 CalcCircle(v3, v1, v2, pTri);
  211.         else
  212.         {
  213.                 // should not get here. However, we do sometimes... but by setting the radius to very
  214.                 // large this "triangle" can still get broken down and hopefully triangulated better.
  215.                 // Don't issue a warning because there's nothing the level designer can do, and
  216.                 // this case can occur a lot.
  217.                 //              AIWarning("These points are colinear: (%.2f,%.2f,%.2f) - (%.2f,%.2f,%.2f) - (%.2f,%.2f,%.2f)",v1.x,v1.y,v1.z,v2.x,v2.y,v2.z,v3.x,v3.y,v3.z);
  218.                 pTri->radiusSq = std::numeric_limits<real>::max();
  219.                 return true;
  220.         }
  221.         return true;
  222. }
  223.  
  224. //====================================================================
  225. // IsPerpendicular
  226. //====================================================================
  227. bool CTriangulator::IsPerpendicular(const Vtx& v1, const Vtx& v2, const Vtx& v3)
  228. {
  229.  
  230.         double yDelta_a = v2.y - v1.y;
  231.         double xDelta_a = v2.x - v1.x;
  232.         double yDelta_b = v3.y - v2.y;
  233.         double xDelta_b = v3.x - v2.x;
  234.  
  235.         // checking whether the line of the two pts are vertical
  236.         if (fabs(xDelta_a) <= 0.000000001 && fabs(yDelta_b) <= 0.000000001)
  237.                 return false;
  238.  
  239.         if (fabs(yDelta_a) <= 0.0000001)
  240.                 return true;
  241.         else if (fabs(yDelta_b) <= 0.0000001)
  242.                 return true;
  243.         else if (fabs(xDelta_a) <= 0.000000001)
  244.                 return true;
  245.         else if (fabs(xDelta_b) <= 0.000000001)
  246.                 return true;
  247.         else
  248.                 return false;
  249.  
  250. }
  251.  
  252. //====================================================================
  253. // CalcCircle
  254. //====================================================================
  255. void CTriangulator::CalcCircle(const Vtx& v1, const Vtx& v2, const Vtx& v3, Tri* pTri)
  256. {
  257.         double yDelta_a = v2.y - v1.y;
  258.         double xDelta_a = v2.x - v1.x;
  259.         double yDelta_b = v3.y - v2.y;
  260.         double xDelta_b = v3.x - v2.x;
  261.  
  262.         if (fabs(xDelta_a) <= 0.000000001 && fabs(yDelta_b) <= 0.000000001)
  263.         {
  264.  
  265.                 pTri->center.x = 0.5f * (v2.x + v3.x);
  266.                 pTri->center.y = 0.5f * (v1.y + v2.y);
  267.                 pTri->center.z = v1.z;
  268.                 pTri->radiusSq = square(pTri->center.x - v1.x) + square(pTri->center.y - v1.y);
  269.                 return;
  270.         }
  271.  
  272.         // IsPerpendicular() assure that xDelta(s) are not zero
  273.         AIAssert(xDelta_a != 0.0);
  274.         AIAssert(xDelta_b != 0.0);
  275.         double aSlope = yDelta_a / xDelta_a; //
  276.         double bSlope = yDelta_b / xDelta_b;
  277.         if (fabs(aSlope - bSlope) <= 0.000000001)
  278.         {
  279.                 // checking whether the given points are colinear.
  280.                 /*              char which[1024];
  281.                    cry_sprintf(which,"vertices (%.2f,%.2f,%.2f),(%.2f,%.2f,%.2f),(%.2f,%.2f,%.2f) caused assert \n",v1.x,v1.y,v1.z,v2.x,v2.y,v2.z,v3.x,v3.y,v3.z);
  282.                    OutputDebugString(&which[0]);
  283.                    DEBUG_BREAK; // we should never get here!!!
  284.                  */
  285.                 AIError("CTriangulator::CalcCircle vertices (%.2f,%.2f,%.2f),(%.2f,%.2f,%.2f),(%.2f,%.2f,%.2f) caused problems [Code bug]", v1.x, v1.y, v1.z, v2.x, v2.y, v2.z, v3.x, v3.y, v3.z);
  286.                 return;
  287.         }
  288.  
  289.         // calc center
  290.         AIAssert(2.f * (bSlope - aSlope) != 0);
  291.         pTri->center.x = (real) ((aSlope * bSlope * (v1.y - v3.y) + bSlope * (v1.x + v2.x) - aSlope * (v2.x + v3.x)) / (2.f * (bSlope - aSlope)));
  292.         AIAssert(aSlope != 0);
  293.         pTri->center.y = (real) (-(pTri->center.x - (v1.x + v2.x) / 2.f) / aSlope + (v1.y + v2.y) / 2.f);
  294.         pTri->center.z = v1.z;
  295.  
  296.         pTri->radiusSq = square(pTri->center.x - v1.x) + square(pTri->center.y - v1.y);
  297. }
  298.  
  299. //====================================================================
  300. // PrepForTriangulation
  301. //====================================================================
  302. bool CTriangulator::PrepForTriangulation(void)
  303. {
  304.         m_vProcessed.clear();
  305.         m_vProcessed.reserve(m_vVertices.size());
  306.  
  307.         // calculate super-triangle
  308.         VARRAY::iterator i;
  309.         Vec3r min(100000, 100000, 0);
  310.         Vec3r max(-100000, -100000, 0);
  311.  
  312.         // bounding rectangle
  313.         for (i = m_vVertices.begin(); i != m_vVertices.end(); ++i)
  314.         {
  315.                 const Vtx& current = (*i);
  316.                 if (current.x < min.x) min.x = current.x;
  317.                 if (current.y < min.y) min.y = current.y;
  318.                 if (current.x > max.x) max.x = current.x;
  319.                 if (current.y > max.y) max.y = current.y;
  320.         }
  321.  
  322.         // Add 4 corner points that are a little bit outside min/max - then
  323.         // generate 2 triangles to cover this
  324.         Vec3r offset(10, 10, 0);
  325.  
  326.         Vtx v00(min - offset);
  327.         Vtx v11(max + offset);
  328.         Vtx v10(v11.x, v00.y, 0);
  329.         Vtx v01(v00.x, v11.y, 0);
  330.  
  331.         m_vProcessed.push_back(v00);
  332.         m_vProcessed.push_back(v10);
  333.         m_vProcessed.push_back(v11);
  334.         m_vProcessed.push_back(v01);
  335.  
  336.         Tri* tri0 = new Tri(0, 1, 3);
  337.         Tri* tri1 = new Tri(1, 2, 3);
  338.  
  339.         m_vTriangles.push_back(tri0);
  340.         m_vTriangles.push_back(tri1);
  341.  
  342.         if (!Calculate(tri0))
  343.                 return false;
  344.         if (!Calculate(tri1))
  345.                 return false;
  346.  
  347.         return true;
  348. }
  349.  
  350. //====================================================================
  351. // VertSorter
  352. // Can use this in TriangulateNew. Sorting reduces the number of flops, but
  353. // doesn't generally speed up much.
  354. //====================================================================
  355. inline bool VertSorter(const Vtx& v1, const Vtx& v2)
  356. {
  357.         if (v1.x < v2.x)
  358.                 return true;
  359.         else if (v1.x == v2.x)
  360.                 return v1.y < v2.y;
  361.         else
  362.                 return false;
  363. }
  364.  
  365. //====================================================================
  366. // TriangulateNew
  367. //====================================================================
  368. bool CTriangulator::TriangulateNew(void)
  369. {
  370.         // triangulation goes bad (very slow) if the vertices aren't added
  371.         // in approximate order, apart from the first 4 which define the area
  372.         VARRAY::iterator i = m_vVertices.begin();
  373.         //  if (m_vVertices.size() > 4)
  374.         //  {
  375.         //    i += 4;
  376.         //    std::sort(i, m_vVertices.end(), VertSorter);
  377.         //  }
  378.  
  379.         int vertCounter = 0;
  380.         // for every vertex
  381.         for (i = m_vVertices.begin(); i != m_vVertices.end(); ++i, ++vertCounter)
  382.         {
  383.                 const Vtx& current = (*i);
  384.  
  385.                 if (0 == (vertCounter % 500))
  386.                 {
  387.                         AILogAlways("Now on vertex %d of %" PRISIZE_T " (%5.2f percent)\n",
  388.                                     vertCounter, m_vVertices.size(), 100.0f * vertCounter / m_vVertices.size());
  389.                 }
  390.  
  391.                 m_uniquePts.resize(0);
  392.                 // find enclosing circles
  393.                 TARRAY::iterator ti;
  394.  
  395.                 for (ti = m_vTriangles.begin(); ti != m_vTriangles.end(); )
  396.                 {
  397.                         Tri* triangle = (*ti);
  398.  
  399.                         real distSq = square(current.x - triangle->center.x) + square(current.y - triangle->center.y);
  400.  
  401.                         if (distSq <= triangle->radiusSq)
  402.                         {
  403.                                 PushUnique(triangle->v[0], triangle->v[1]);
  404.                                 PushUnique(triangle->v[1], triangle->v[2]);
  405.                                 PushUnique(triangle->v[2], triangle->v[0]);
  406.                                 m_vTriangles.erase(ti++);
  407.                                 delete triangle;
  408.                         }
  409.                         else
  410.                         {
  411.                                 ++ti;
  412.                         }
  413.                 }
  414.  
  415.                 // add new triangles
  416.                 int pos = m_vProcessed.size();
  417.                 m_vProcessed.push_back(current);
  418.  
  419.                 tUniquePts::iterator ui;
  420.  
  421.                 for (ui = m_uniquePts.begin(); ui != m_uniquePts.end(); ++ui)
  422.                 {
  423.                         MYPOINT curr = *ui;
  424.  
  425.                         Tri* newone = new Tri;
  426.                         newone->v[0] = curr.x;
  427.                         newone->v[1] = curr.y;
  428.                         newone->v[2] = pos;
  429.  
  430.                         if (!IsAntiClockwise(newone))
  431.                         {
  432.                                 newone->v[0] = curr.y;
  433.                                 newone->v[1] = curr.x;
  434.                         }
  435.  
  436.                         if (!Calculate(newone))
  437.                                 return false;
  438.  
  439.                         m_vTriangles.push_back(newone);
  440.                 }
  441.         }
  442.         m_vVertices.clear();
  443.  
  444.         return true;
  445. }
  446.  
  447. #ifdef AI_FP_FAST
  448.         #pragma fenv_access(off)
  449.         #pragma float_control(precise, off)
  450. #endif
  451.  
downloadCTriangulator.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