BVB Source Codes

CRYENGINE Show Shape.cpp Source code

Return Download CRYENGINE: download Shape.cpp Source code - Download CRYENGINE Source code - Type:.cpp
  1. // Copyright 2001-2016 Crytek GmbH / Crytek Group. All rights reserved.
  2.  
  3. /********************************************************************
  4.    -------------------------------------------------------------------------
  5.    File name:   Shape.cpp
  6.    $Id$
  7.    Description: Polygon shapes used for different purposes in the AI system and various shape containers.
  8.  
  9.    The bin sort point-in-polygon check is based on:
  10.    Graphics Gems IV: Point in Polygon Strategies by Eric Haines
  11.    http://tog.acm.org/GraphicsGems/gemsiv/ptpoly_haines/
  12.  
  13.    -------------------------------------------------------------------------
  14.    History:
  15.    - 2007                               : Created by Mikko Mononen
  16.    - 2 Mar 2009 : Evgeny Adamenkov: Replaced IRenderer with CDebugDrawContext
  17.  
  18.  *********************************************************************/
  19.  
  20. #include "StdAfx.h"
  21. #include "Shape.h"
  22. #include "DebugDrawContext.h"
  23.  
  24. static const float BIN_WIDTH = 3.0f;
  25.  
  26. //====================================================================
  27. // DistancePointLinesegSq
  28. //====================================================================
  29. static float DistancePointLinesegSq(const Vec3& p, const Vec3& start, const Vec3& end, float& t)
  30. {
  31.         Vec2 diff(p.x - start.x, p.y - start.y);
  32.         Vec2 dir(end.x - start.x, end.y - start.y);
  33.         t = diff.Dot(dir);
  34.  
  35.         if (t <= 0.0f)
  36.         {
  37.                 t = 0.0f;
  38.         }
  39.         else
  40.         {
  41.                 float sqrLen = dir.GetLength2();
  42.                 if (t >= sqrLen)
  43.                 {
  44.                         t = 1.0f;
  45.                         diff -= dir;
  46.                 }
  47.                 else
  48.                 {
  49.                         t /= sqrLen;
  50.                         diff -= t * dir;
  51.                 }
  52.         }
  53.  
  54.         return diff.GetLength2();
  55. }
  56.  
  57. //====================================================================
  58. // IntersectLinesegLineseg
  59. //====================================================================
  60. static bool IntersectLinesegLineseg(const Vec3& startA, const Vec3& endA,
  61.                                     const Vec3& startB, const Vec3& endB,
  62.                                     float& tA, float& tB)
  63. {
  64.         // used for parallel testing
  65.         static const float epsilon = 0.0000001f;
  66.  
  67.         Vec2 delta(startB.x - startA.x, startB.y - startA.y);
  68.         Vec2 lineADir(endA.x - startA.x, endA.y - startA.y);
  69.         Vec2 lineBDir(endB.x - startB.x, endB.y - startB.y);
  70.         float crossD = lineADir.x * lineBDir.y - lineADir.y * lineBDir.x;
  71.         float crossDelta1 = delta.x * lineBDir.y - delta.y * lineBDir.x;
  72.         float crossDelta2 = delta.x * lineADir.y - delta.y * lineADir.x;
  73.  
  74.         if (fabs(crossD) > epsilon)
  75.         {
  76.                 // intersection
  77.                 tA = crossDelta1 / crossD;
  78.                 tB = crossDelta2 / crossD;
  79.         }
  80.         else
  81.         {
  82.                 // parallel - maybe should really test for lines overlapping each other?
  83.                 tA = tB = 0.5f;
  84.                 return false;
  85.         }
  86.  
  87.         if (tA > 1.0f || tA < 0.0f || tB > 1.0f || tB < 0.0f)
  88.                 return false;
  89.  
  90.         return true;
  91. }
  92.  
  93. //====================================================================
  94. // CAIShape
  95. //====================================================================
  96. CAIShape::CAIShape() :
  97.         m_binSort(0),
  98.         m_aabb(AABB::RESET)
  99. {
  100. }
  101.  
  102. //====================================================================
  103. // ~CAIShape
  104. //====================================================================
  105. CAIShape::~CAIShape()
  106. {
  107.         delete m_binSort;
  108. }
  109.  
  110. //====================================================================
  111. // Duplicate
  112. //====================================================================
  113. CAIShape* CAIShape::DuplicateData()
  114. {
  115.         CAIShape* pShape = new CAIShape;
  116.         pShape->m_name = m_name;
  117.         pShape->m_aabb = m_aabb;
  118.         pShape->m_points = m_points;
  119.         return pShape;
  120. }
  121.  
  122. //====================================================================
  123. // SetPoints
  124. //====================================================================
  125. void CAIShape::SetPoints(const std::vector<Vec3>& points)
  126. {
  127.         m_points.resize(points.size());
  128.         for (unsigned i = 0, ni = points.size(); i < ni; ++i)
  129.                 m_points[i] = points[i];
  130.         BuildAABB();
  131. }
  132.  
  133. //====================================================================
  134. // BuildAABB
  135. //====================================================================
  136. void CAIShape::BuildAABB()
  137. {
  138.         // Build AABB
  139.         m_aabb.Reset();
  140.         for (unsigned i = 0, ni = m_points.size(); i < ni; ++i)
  141.                 m_aabb.Add(m_points[i]);
  142.  
  143.         // add a little to the bounds to ensure everything falls inside area
  144.         const float EPSILON = 0.00001f;
  145.         float rangex = m_aabb.max.x - m_aabb.min.x;
  146.         float rangey = m_aabb.max.y - m_aabb.min.y;
  147.         m_aabb.min.x -= EPSILON * rangex;
  148.         m_aabb.max.x += EPSILON * rangex;
  149.         m_aabb.min.y -= EPSILON * rangey;
  150.         m_aabb.max.y += EPSILON * rangey;
  151. }
  152.  
  153. //====================================================================
  154. // BuildBins
  155. //====================================================================
  156. void CAIShape::BuildBins()
  157. {
  158.         if (m_binSort)
  159.         {
  160.                 delete m_binSort;
  161.                 m_binSort = 0;
  162.         }
  163.  
  164.         // Do not build hte bins if too few points.
  165.         if (m_points.size() < 15)
  166.                 return;
  167.  
  168.         const float minx = m_aabb.min.x;
  169.         const float maxx = m_aabb.max.x;
  170.         const float miny = m_aabb.min.y;
  171.         const float maxy = m_aabb.max.y;
  172.  
  173.         unsigned bins = (unsigned)ceilf((maxy - miny) / BIN_WIDTH);
  174.         if (bins < 2)
  175.                 return;
  176.  
  177.         // Limit the size of bins so that the acceleration structure does not take more memory than the points.
  178.         if (bins > m_points.size() / 2)
  179.                 bins = m_points.size() / 2;
  180.  
  181.         m_binSort = new BinSort;
  182.  
  183.         m_binSort->bins.resize(bins);
  184.  
  185.         m_binSort->ydelta = (maxy - miny) / (float)bins;
  186.         m_binSort->invYdelta = 1.0f / m_binSort->ydelta;
  187.  
  188.         // find how many locations to allocate for each bin
  189.         std::vector<unsigned> binTot(bins);
  190.         for (unsigned i = 0, ni = binTot.size(); i < ni; ++i)
  191.                 binTot[i] = 0;
  192.  
  193.         Vec3* p0 = 0;
  194.         Vec3* p1 = 0;
  195.  
  196.         p0 = &m_points.back();
  197.         for (unsigned i = 0, ni = m_points.size(); i < ni; ++i)
  198.         {
  199.                 p1 = &m_points[i];
  200.  
  201.                 // skip if Y's identical (edge has no effect)
  202.                 if (p0->y != p1->y)
  203.                 {
  204.                         Vec3* pa = p0;
  205.                         Vec3* pb = p1;
  206.                         if (pa->y > pb->y)
  207.                                 std::swap(pa, pb);
  208.  
  209.                         float fba = (pa->y - miny) * m_binSort->invYdelta;
  210.                         int ba = (int)fba;
  211.                         float fbb = (pb->y - miny) * m_binSort->invYdelta;
  212.                         int bb = (int)fbb;
  213.                         // if high vertex ends on a boundary, don't go into next boundary
  214.                         if (fbb == (float)bb)
  215.                                 bb--;
  216.  
  217.                         if (ba < 0) ba = 0;
  218.                         if (bb >= (int)bins) bb = (int)bins - 1;
  219.  
  220.                         //                      AIAssert(ba >= 0 && ba < (int)bins);
  221.                         //                      AIAssert(bb >= 0 && bb < (int)bins);
  222.  
  223.                         // mark the bins with this edge
  224.                         for (int j = ba; j <= bb; j++)
  225.                                 binTot[j]++;
  226.                 }
  227.  
  228.                 p0 = p1;
  229.         }
  230.  
  231.         // allocate the bin contents and fill in some basics
  232.         for (unsigned i = 0, ni = m_binSort->bins.size(); i < ni; ++i)
  233.         {
  234.                 Bin& bin = m_binSort->bins[i];
  235.                 bin.edges.reserve(binTot[i]);
  236.                 // start these off at some awful values; refined below
  237.                 bin.minx = maxx;
  238.                 bin.maxx = minx;
  239.         }
  240.  
  241.         // now go through list yet again, putting edges in bins
  242.         p0 = &m_points.back();
  243.         unsigned short id = (unsigned short)(m_points.size() - 1);
  244.         for (unsigned i = 0, ni = m_points.size(); i < ni; ++i)
  245.         {
  246.                 p1 = &m_points[i];
  247.  
  248.                 // skip if Y's identical (edge has no effect)
  249.                 if (p0->y != p1->y)
  250.                 {
  251.                         Vec3* pa = p0;
  252.                         Vec3* pb = p1;
  253.                         if (pa->y > pb->y)
  254.                                 std::swap(pa, pb);
  255.  
  256.                         float fba = (pa->y - miny) * m_binSort->invYdelta;
  257.                         int ba = (int)fba;
  258.                         float fbb = (pb->y - miny) * m_binSort->invYdelta;
  259.                         int bb = (int)fbb;
  260.                         // if high vertex ends on a boundary, don't go into it
  261.                         if (bb > ba && fbb == (float)bb)
  262.                                 bb--;
  263.  
  264.                         if (ba < 0) ba = 0;
  265.                         if (bb >= (int)bins) bb = (int)bins - 1;
  266.  
  267.                         //                      AIAssert(ba >= 0 && ba < (int)bins);
  268.                         //                      AIAssert(bb >= 0 && bb < (int)bins);
  269.  
  270.                         float vx0 = pa->x;
  271.                         float dy = pb->y - pa->y;
  272.                         float slope = m_binSort->ydelta * (pb->x - pa->x) / dy;
  273.  
  274.                         // set vx1 in case loop is not entered
  275.                         float vx1 = vx0;
  276.                         bool fullCross = false;
  277.                         for (int j = ba; j < bb; j++, vx0 = vx1)
  278.                         {
  279.                                 // could increment vx1, but for greater accuracy recompute it
  280.                                 vx1 = pa->x + ((float)(j + 1) - fba) * slope;
  281.                                 m_binSort->bins[j].AddEdge(vx0, vx1, id, fullCross);
  282.                                 fullCross = true;
  283.                         }
  284.  
  285.                         // at last bin - fill as above, but with vx1 = p1->x
  286.                         vx0 = vx1;
  287.                         vx1 = pb->x;
  288.                         m_binSort->bins[bb].AddEdge(vx0, vx1, id, false); // the last bin is never a full crossing
  289.                 }
  290.  
  291.                 id = (unsigned short)i;
  292.                 p0 = p1;
  293.         }
  294.  
  295.         // finally, sort the bins' contents by minx
  296.         for (unsigned i = 0, ni = m_binSort->bins.size(); i < ni; ++i)
  297.                 std::sort(m_binSort->bins[i].edges.begin(), m_binSort->bins[i].edges.end());
  298. }
  299.  
  300. //====================================================================
  301. // IsPointInsideSlow
  302. //====================================================================
  303. bool CAIShape::IsPointInsideSlow(const Vec3& pt) const
  304. {
  305.         return Overlap::Point_Polygon2D(pt, m_points, &m_aabb);
  306. }
  307.  
  308. //====================================================================
  309. // IsPointInside
  310. //====================================================================
  311. bool CAIShape::IsPointInside(const Vec3& pt) const
  312. {
  313.         if (!m_binSort)
  314.         {
  315.                 return IsPointInsideSlow(pt);
  316.         }
  317.  
  318.         bool insideFlag = false;
  319.  
  320.         // first, is point inside bounding rectangle?
  321.         //      if (!Overlap::Point_AABB2D(pt, m_aabb))
  322.         //              return false;
  323.  
  324.         // what bin are we in?
  325.         int b = (int)((pt.y - m_aabb.min.y) * m_binSort->invYdelta);
  326.  
  327.         // Outside the bin range, outside the shape.
  328.         if (b < 0 || b >= (int)m_binSort->bins.size())
  329.                 return false;
  330.  
  331.         const Bin& bin = m_binSort->bins[b];
  332.         // find if we're inside this bin's bounds
  333.         if (pt.x < bin.minx || pt.x > bin.maxx)
  334.                 return false;
  335.  
  336.         // now search bin for crossings
  337.         const unsigned npts = m_points.size();
  338.         for (unsigned j = 0, nj = bin.edges.size(); j < nj; ++j)
  339.         {
  340.                 const Edge* edge = &bin.edges[j];
  341.                 if (pt.x < edge->minx)
  342.                 {
  343.                         // all remaining edges are to right of point, so test them
  344.                         do
  345.                         {
  346.                                 if (edge->fullCross)
  347.                                 {
  348.                                         insideFlag = !insideFlag;
  349.                                 }
  350.                                 else
  351.                                 {
  352.                                         unsigned id = edge->id;
  353.                                         if ((pt.y <= m_points[id].y) != (pt.y <= m_points[(id + 1) % npts].y))
  354.                                         {
  355.                                                 // point crosses edge in Y, so must cross.
  356.                                                 insideFlag = !insideFlag;
  357.                                         }
  358.                                 }
  359.                                 edge++;
  360.                         }
  361.                         while (++j < nj);
  362.  
  363.                         return insideFlag;
  364.                 }
  365.                 else if (pt.x < edge->maxx)
  366.                 {
  367.                         // edge is overlapping point in X, check it
  368.                         unsigned id = edge->id;
  369.                         const Vec3& vtx0 = m_points[id];
  370.                         const Vec3& vtx1 = m_points[(id + 1) % npts];
  371.  
  372.                         if (edge->fullCross || (pt.y <= vtx0.y) != (pt.y <= vtx1.y))
  373.                         {
  374.                                 // edge crosses in Y, so have to do full crossings test
  375.                                 if ((vtx0.x - (vtx0.y - pt.y) * (vtx1.x - vtx0.x) / (vtx1.y - vtx0.y)) >= pt.x)
  376.                                         insideFlag = !insideFlag;
  377.                         }
  378.                 } // else edge is to left of point, ignore it
  379.         }
  380.  
  381.         return insideFlag;
  382. }
  383.  
  384. //====================================================================
  385. // IsPointOnEdgeSlow
  386. //====================================================================
  387. bool CAIShape::IsPointOnEdgeSlow(const Vec3& pt, float tol, Vec3* outNormal) const
  388. {
  389.         float tolSq = sqr(tol);
  390.  
  391.         unsigned j = m_points.size() - 1;
  392.         for (unsigned i = 0, ni = m_points.size(); i < ni; j = i, ++i)
  393.         {
  394.                 const Vec3& sa = m_points[j];
  395.                 const Vec3& sb = m_points[i];
  396.                 float t;
  397.                 if (DistancePointLinesegSq(pt, sa, sb, t) < tolSq)
  398.                 {
  399.                         Vec3 polySeg = sb - sa;
  400.                         Vec3 intersectionPoint = sa + t * polySeg;
  401.                         Vec3 intSeg = (intersectionPoint - pt);
  402.  
  403.                         Vec3 normal(polySeg.y, -polySeg.x, 0.0f);
  404.                         normal.Normalize();
  405.                         // returns the normal towards the start point of the intersecting segment
  406.                         if ((intSeg.Dot(normal)) > 0.0f)
  407.                         {
  408.                                 normal.x = -normal.x;
  409.                                 normal.y = -normal.y;
  410.                         }
  411.  
  412.                         if (outNormal)
  413.                                 *outNormal = normal;
  414.  
  415.                         return true;
  416.                 }
  417.         }
  418.  
  419.         return false;
  420. }
  421.  
  422. //====================================================================
  423. // IsPointOnEdge
  424. //====================================================================
  425. bool CAIShape::IsPointOnEdge(const Vec3& pt, float tol, Vec3* outNormal) const
  426. {
  427.         if (!Overlap::Sphere_AABB2D(Sphere(pt, tol), m_aabb))
  428.                 return false;
  429.  
  430.         if (!m_binSort)
  431.         {
  432.                 return IsPointOnEdgeSlow(pt, tol, outNormal);
  433.         }
  434.  
  435.         const unsigned bins = m_binSort->bins.size();
  436.  
  437.         // Calculate x and y ranges.
  438.         const float xrmin = pt.x - tol;
  439.         const float xrmax = pt.x + tol;
  440.         const float yrmin = pt.y - tol;
  441.         const float yrmax = pt.y + tol;
  442.  
  443.         // Check all bins that overlap the circle.
  444.         float fba = (yrmin - m_aabb.min.y) * m_binSort->invYdelta;
  445.         int ba = (int)fba;
  446.         float fbb = (yrmax - m_aabb.min.y) * m_binSort->invYdelta;
  447.         int bb = (int)fbb;
  448.         // if high vertex ends on a boundary, don't go into it
  449.         if (bb > ba && fbb == (float)bb)
  450.                 bb--;
  451.  
  452.         // Sanity check for index ranges.
  453.         if (ba < 0) ba = 0;
  454.         if (bb >= (int)bins) bb = (int)bins - 1;
  455.  
  456.         float tolSq = sqr(tol);
  457.  
  458.         for (int i = ba; i <= bb; i++)
  459.         {
  460.                 const Bin& bin = m_binSort->bins[i];
  461.  
  462.                 // Check the bins.
  463.                 const unsigned npts = m_points.size();
  464.                 for (unsigned j = 0, nj = bin.edges.size(); j < nj; ++j)
  465.                 {
  466.                         const Edge* edge = &bin.edges[j];
  467.                         // Skip if the X range does not overlap.
  468.                         if (xrmin > edge->maxx || xrmax < edge->minx)
  469.                                 continue;
  470.  
  471.                         unsigned id = edge->id;
  472.                         const Vec3& sa = m_points[id];
  473.                         const Vec3& sb = m_points[(id + 1) % npts];
  474.  
  475.                         float t;
  476.                         if (DistancePointLinesegSq(pt, sa, sb, t) < tolSq)
  477.                         {
  478.                                 Vec3 polySeg = sb - sa;
  479.                                 Vec3 intersectionPoint = sa + t * polySeg;
  480.                                 Vec3 intSeg = (intersectionPoint - pt);
  481.  
  482.                                 Vec3 normal(polySeg.y, -polySeg.x, 0.0f);
  483.                                 normal.Normalize();
  484.                                 // returns the normal towards the start point of the intersecting segment
  485.                                 if ((intSeg.Dot(normal)) > 0.0f)
  486.                                 {
  487.                                         normal.x = -normal.x;
  488.                                         normal.y = -normal.y;
  489.                                 }
  490.  
  491.                                 if (outNormal)
  492.                                         *outNormal = normal;
  493.  
  494.                                 return true;
  495.                         }
  496.                 }
  497.         }
  498.  
  499.         return false;
  500. }
  501.  
  502. //====================================================================
  503. // IntersectLineSegSlow
  504. //====================================================================
  505. bool CAIShape::IntersectLineSegSlow(const Vec3& start, const Vec3& end, float& tmin,
  506.                                     Vec3* outClosestPoint, Vec3* outNormal, bool bForceNormalOutwards) const
  507. {
  508.         const Vec3* isa = 0;
  509.         const Vec3* isb = 0;
  510.  
  511.         tmin = 1.0f;
  512.         bool intersect = false;
  513.  
  514.         size_t pointCount = m_points.size();
  515.  
  516.         for (size_t i = 1; i <= pointCount; ++i)
  517.         {
  518.                 const Vec3 sa = m_points[i - 1];
  519.                 const Vec3 sb = m_points[i % pointCount];
  520.  
  521.                 float s, t;
  522.                 if (IntersectLinesegLineseg(start, end, sa, sb, s, t))
  523.                 {
  524.                         if (s < 0.00001f || s > 0.99999f || t < 0.00001f || t > 0.99999f)
  525.                                 continue;
  526.  
  527.                         if (s < tmin)
  528.                         {
  529.                                 tmin = s;
  530.                                 intersect = true;
  531.                                 isa = &sa;
  532.                                 isb = &sb;
  533.                         }
  534.                 }
  535.         }
  536.  
  537.         if (intersect && outClosestPoint)
  538.                 *outClosestPoint = start + tmin * (end - start);
  539.  
  540.         if (intersect && outNormal)
  541.         {
  542.                 Vec3 polyseg = *isb - *isa;
  543.                 Vec3 intSeg = end - start;
  544.                 outNormal->x = polyseg.y;
  545.                 outNormal->y = -polyseg.x;
  546.                 outNormal->z = 0;
  547.                 outNormal->Normalize();
  548.                 // returns the normal towards the start point of the intersecting segment (if it's not forced to be outwards)
  549.                 if (!bForceNormalOutwards && intSeg.Dot(*outNormal) > 0)
  550.                 {
  551.                         outNormal->x = -outNormal->x;
  552.                         outNormal->y = -outNormal->y;
  553.                 }
  554.         }
  555.  
  556.         return intersect;
  557. }
  558.  
  559. //====================================================================
  560. // IntersectLineSegBin
  561. //====================================================================
  562. bool CAIShape::IntersectLineSegBin(const Bin& bin, float xrmin, float xrmax,
  563.                                    const Vec3& start, const Vec3& end,
  564.                                    float& tmin, const Vec3*& isa, const Vec3*& isb) const
  565. {
  566.         if (xrmin > xrmax)
  567.                 std::swap(xrmin, xrmax);
  568.  
  569.         const float EPSILON = 0.00001f;
  570.         xrmin -= EPSILON;
  571.         xrmax += EPSILON;
  572.  
  573.         bool intersect = false;
  574.  
  575.         // Check the bins.
  576.         const unsigned npts = m_points.size();
  577.         for (unsigned j = 0, nj = bin.edges.size(); j < nj; ++j)
  578.         {
  579.                 const Edge* edge = &bin.edges[j];
  580.                 // Skip if the X range does not overlap.
  581.                 if (xrmin > edge->maxx || xrmax < edge->minx)
  582.                         continue;
  583.  
  584.                 unsigned id = edge->id;
  585.                 const Vec3& sa = m_points[id];
  586.                 const Vec3& sb = m_points[(id + 1) % npts];
  587.  
  588.                 float s, t;
  589.                 if (IntersectLinesegLineseg(start, end, sa, sb, s, t))
  590.                 {
  591.                         if (s < 0.00001f || s > 0.99999f || t < 0.00001f || t > 0.99999f)
  592.                                 continue;
  593.                         if (s < tmin)
  594.                         {
  595.                                 tmin = s;
  596.                                 intersect = true;
  597.                                 isa = &sa;
  598.                                 isb = &sb;
  599.                         }
  600.                 }
  601.         }
  602.  
  603.         return intersect;
  604. }
  605.  
  606. //====================================================================
  607. // IntersectLineSeg
  608. //====================================================================
  609. bool CAIShape::IntersectLineSeg(const Vec3& start, const Vec3& end, float& tmin,
  610.                                 Vec3* outClosestPoint, Vec3* outNormal, bool bForceNormalOutwards) const
  611. {
  612.         tmin = 1.0f;
  613.         if (!Overlap::Lineseg_AABB2D(Lineseg(start, end), m_aabb))
  614.                 return false;
  615.  
  616.         if (!m_binSort)
  617.         {
  618.                 return IntersectLineSegSlow(start, end, tmin, outClosestPoint, outNormal, bForceNormalOutwards);
  619.         }
  620.  
  621.         const unsigned bins = m_binSort->bins.size();
  622.  
  623.         const Vec3* isa = 0;
  624.         const Vec3* isb = 0;
  625.  
  626.         bool intersect = false;
  627.  
  628.         Vec3 pa(start);
  629.         Vec3 pb(end);
  630.  
  631.         // skip if Y's identical (edge has no effect)
  632.         if (pa.y > pb.y)
  633.                 std::swap(pa, pb);
  634.  
  635.         float fba = (pa.y - m_aabb.min.y) * m_binSort->invYdelta;
  636.         int ba = (int)fba;
  637.         float fbb = (pb.y - m_aabb.min.y) * m_binSort->invYdelta;
  638.         int bb = (int)fbb;
  639.         // if high vertex ends on a boundary, don't go into it
  640.         if (bb > ba && fbb == (float)bb)
  641.                 bb--;
  642.  
  643.         if (ba < 0) ba = 0;
  644.         if (bb >= (int)bins) bb = (int)bins - 1;
  645.  
  646.         float vx0 = pa.x;
  647.         float dy = pb.y - pa.y;
  648.         float slope = dy < 0.000001f ? 0.0f : m_binSort->ydelta * (pb.x - pa.x) / dy;
  649.  
  650.         // set vx1 in case loop is not entered
  651.         float vx1 = vx0;
  652.         for (int i = ba; i < bb; i++, vx0 = vx1)
  653.         {
  654.                 const Bin& bin = m_binSort->bins[i];
  655.  
  656.                 // could increment vx1, but for greater accuracy recompute it
  657.                 vx1 = pa.x + ((float)(i + 1) - fba) * slope;
  658.  
  659.                 if (IntersectLineSegBin(bin, vx0, vx1, start, end, tmin, isa, isb))
  660.                         intersect = true;
  661.         }
  662.  
  663.         // at last bin - fill as above, but with vx1 = p1->x
  664.         if (IntersectLineSegBin(m_binSort->bins[bb], vx1, pb.x, start, end, tmin, isa, isb))
  665.                 intersect = true;
  666.  
  667.         if (intersect && outClosestPoint)
  668.                 *outClosestPoint = start + tmin * (end - start);
  669.  
  670.         if (intersect && outNormal)
  671.         {
  672.                 Vec3 polyseg = *isb - *isa;
  673.                 Vec3 intSeg = end - start;
  674.                 outNormal->x = polyseg.y;
  675.                 outNormal->y = -polyseg.x;
  676.                 outNormal->z = 0;
  677.                 outNormal->Normalize();
  678.                 // returns the normal towards the start point of the intersecting segment (if it's not forced to be outwards)
  679.                 /*                      if (!bForceNormalOutwards && intSeg.Dot(Vec2(outNormal->x, outNormal->y)) > 0)
  680.                    {
  681.                    outNormal->x = -outNormal->x;
  682.                    outNormal->y = -outNormal->y;
  683.                    }*/
  684.         }
  685.  
  686.         return intersect;
  687. }
  688.  
  689. //====================================================================
  690. // IntersectLineSeg
  691. //====================================================================
  692. bool CAIShape::IntersectLineSeg(const Vec3& start, const Vec3& end, float radius) const
  693. {
  694.         AABB aabb(m_aabb);
  695.         aabb.Expand(Vec3(radius));
  696.  
  697.         Lineseg line(start, end);
  698.  
  699.         if (!Overlap::Lineseg_AABB2D(line, aabb))
  700.                 return false;
  701.  
  702.         size_t pointCount = m_points.size();
  703.         float radiusSq = sqr(radius);
  704.  
  705.         for (size_t i = 1; i <= pointCount; ++i)
  706.         {
  707.                 float distanceSq = Distance::Lineseg_Lineseg2DSq<float>(line, Lineseg(m_points[i - 1], m_points[i % pointCount]));
  708.  
  709.                 if (distanceSq <= radiusSq)
  710.                         return true;
  711.         }
  712.  
  713.         return false;
  714. }
  715.  
  716. //====================================================================
  717. // DebugDraw
  718. //====================================================================
  719. bool CAIShape::OverlapAABB(const AABB& aabb) const
  720. {
  721.         if (!Overlap::AABB_AABB2D(aabb, m_aabb))
  722.                 return false;
  723.  
  724.         const ShapePointContainer& pts = m_points;
  725.         const unsigned npts = m_points.size();
  726.  
  727.         // Trivial reject if all points are outside any of the edges of the AABB.
  728.         unsigned cxmin = 0, cxmax = 0, cymin = 0, cymax = 0;
  729.         for (unsigned i = 0; i < npts; ++i)
  730.         {
  731.                 const Vec3& v = pts[i];
  732.                 unsigned inside = 0;
  733.                 if (v.x < aabb.min.x)
  734.                         cxmin++;
  735.                 else if (v.x > aabb.max.x)
  736.                         cxmax++;
  737.                 else
  738.                         inside++;
  739.  
  740.                 if (v.y < aabb.min.y)
  741.                         cymin++;
  742.                 else if (v.y > aabb.max.y)
  743.                         cymax++;
  744.                 else
  745.                         inside++;
  746.  
  747.                 // The vertex is inside the AABB, there is be overlap.
  748.                 if (inside == 2)
  749.                         return true;
  750.         }
  751.         if (cxmin == npts || cxmax == npts || cymin == npts || cymax == npts)
  752.                 return false;
  753.  
  754.         // If any edge intersects the aabb, return true.
  755.         for (unsigned i = 0; i < npts; ++i)
  756.         {
  757.                 unsigned ine = i + 1;
  758.                 if (ine >= npts) ine = 0;
  759.                 if (OverlapLinesegAABB2D(pts[i], pts[ine], aabb))
  760.                         return true;
  761.         }
  762.  
  763.         // If any aabb edge is inside the poly, return true.
  764.         if (IsPointInside(Vec3(aabb.min.x, aabb.min.y, 0)))
  765.                 return true;
  766.         if (IsPointInside(Vec3(aabb.max.x, aabb.min.y, 0)))
  767.                 return true;
  768.         if (IsPointInside(Vec3(aabb.max.x, aabb.max.y, 0)))
  769.                 return true;
  770.         if (IsPointInside(Vec3(aabb.min.x, aabb.max.y, 0)))
  771.                 return true;
  772.  
  773.         return false;
  774. }
  775.  
  776. //====================================================================
  777. // DebugDraw
  778. //====================================================================
  779. void CAIShape::DebugDraw()
  780. {
  781.         CDebugDrawContext dc;
  782.  
  783.         AABB bounds(m_aabb);
  784.  
  785.         // Draw shape
  786.         dc->DrawPolyline(&m_points[0], m_points.size(), true, ColorB(255, 255, 255), 3.0f);
  787.  
  788.         dc->DrawAABB(bounds, false, ColorB(255, 255, 255, 128), eBBD_Faceted);
  789.  
  790.         // Draw bins
  791.         if (m_binSort)
  792.         {
  793.                 AABB aabb;
  794.                 const unsigned npts = m_points.size();
  795.                 for (unsigned i = 0, ni = m_binSort->bins.size(); i < ni; ++i)
  796.                 {
  797.                         const Bin& bin = m_binSort->bins[i];
  798.  
  799.                         float y = bounds.min.y + i * m_binSort->ydelta;
  800.                         dc->DrawLine(Vec3(bin.minx, y, bounds.min.z), ColorB(255, 0, 0, 128),
  801.                                      Vec3(bin.maxx, y, bounds.min.z), ColorB(255, 0, 0, 128));
  802.  
  803.                         aabb.min.y = y;
  804.                         aabb.max.y = y + m_binSort->ydelta;
  805.  
  806.                         // Draw edge aabbs
  807.                         for (unsigned j = 0, nj = bin.edges.size(); j < nj; ++j)
  808.                         {
  809.                                 const Edge& e = bin.edges[j];
  810.                                 const Vec3& va = m_points[e.id];
  811.                                 const Vec3& vb = m_points[(e.id + 1) % npts];
  812.  
  813.                                 aabb.min.x = e.minx;
  814.                                 aabb.min.z = min(va.z, vb.z);
  815.  
  816.                                 aabb.max.x = e.maxx;
  817.                                 aabb.max.z = max(va.z, vb.z);
  818.  
  819.                                 dc->DrawAABB(aabb, true, ColorB(255, 0, 0, 128), eBBD_Faceted);
  820.                         }
  821.                 }
  822.         }
  823. }
  824.  
  825. //====================================================================
  826. // GetDrawZ
  827. //====================================================================
  828. float CAIShape::GetDrawZ(float x, float y)
  829. {
  830.         I3DEngine* pEngine = gEnv->p3DEngine;
  831.         float terrainZ = pEngine->GetTerrainElevation(x, y);
  832.         Vec3 pt(x, y, 0);
  833.         float waterZ = pEngine->GetWaterLevel(&pt);
  834.         return max(terrainZ, waterZ);
  835. }
  836.  
  837. //====================================================================
  838. // MemStats
  839. //====================================================================
  840. size_t CAIShape::MemStats() const
  841. {
  842.         size_t size = sizeof(*this);
  843.         size += m_points.capacity() * sizeof(ShapePointContainer::value_type);
  844.         if (m_binSort)
  845.         {
  846.                 size += sizeof(*m_binSort);
  847.                 size += m_binSort->bins.capacity() * sizeof(Bin);
  848.                 for (unsigned i = 0, ni = m_binSort->bins.size(); i < ni; ++i)
  849.                         size += m_binSort->bins[i].edges.capacity() * sizeof(Edge);
  850.         }
  851.         return size;
  852. }
  853.  
downloadShape.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