BVB Source Codes

CRYENGINE Show TileGenerator.cpp Source code

Return Download CRYENGINE: download TileGenerator.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 "TileGenerator.h"
  5. #include "Voxelizer.h"
  6.  
  7. //#pragma optimize("", off)
  8. //#pragma inline_depth(0)
  9.  
  10. namespace MNM
  11. {
  12. //Code relies on the ordering (specifically we must list l/r/u/d cyclically before corners)
  13. static const int NeighbourOffset_TileGenerator[8][2] =
  14. {
  15.         { 0,  1  },
  16.         { -1, 0  },
  17.         { 1,  0  },
  18.         { 0,  -1 },
  19.         { -1, -1 },
  20.         { 1,  -1 },
  21.         { 1,  1  },
  22.         { -1, 1  },
  23. };
  24.  
  25. /*
  26.    Expanded s_CornerTable, easier to read
  27.  
  28.    Expanded, easier to read
  29.  
  30.    CornerTable[UW][UW][UW] = 0;
  31.    CornerTable[UW][UW][NB] = 0;
  32.    CornerTable[UW][UW][WB] = 1;
  33.    CornerTable[UW][NB][UW] = 0;
  34.    CornerTable[UW][NB][NB] = 0;
  35.    CornerTable[UW][NB][WB] = 0;
  36.    CornerTable[UW][WB][UW] = 1;
  37.    CornerTable[UW][WB][NB] = 1;
  38.    CornerTable[UW][WB][WB] = 1;
  39.  
  40.    CornerTable[NB][UW][UW] = 0;
  41.    CornerTable[NB][UW][NB] = 0;
  42.    CornerTable[NB][UW][WB] = 1;
  43.    CornerTable[NB][NB][UW] = 0;
  44.    CornerTable[NB][NB][NB] = 0;
  45.    CornerTable[NB][NB][WB] = 0;
  46.    CornerTable[NB][WB][UW] = 1;
  47.    CornerTable[NB][WB][NB] = 0;
  48.    CornerTable[NB][WB][WB] = 0;
  49.  
  50.    CornerTable[WB][UW][UW] = 1;
  51.    CornerTable[WB][UW][NB] = 1;
  52.    CornerTable[WB][UW][WB] = 0;
  53.    CornerTable[WB][NB][UW] = 0;
  54.    CornerTable[WB][NB][NB] = 0;
  55.    CornerTable[WB][NB][WB] = 1;
  56.    CornerTable[WB][WB][UW] = 1;
  57.    CornerTable[WB][WB][NB] = 0;
  58.    CornerTable[WB][WB][WB] = 0;
  59.  */
  60.  
  61. // Corner table is used to detect unremovable corner vertices on contours
  62. // using neighbour classes, see NeighbourClassification.
  63. // Indexing order: left, front-left, front.
  64. static uchar s_CornerTable[3][3][3] =
  65. {
  66.         // *INDENT-OFF* - disable uncrustify's indenting, as I want to preserve specific comment formatting.
  67.         {// UW
  68.          // UW, NB, WB
  69.                 { 0, 0, 1 }, // UW
  70.                 { 0, 0, 0 }, // NB
  71.                 { 1, 1, 1 }, // WB
  72.         },
  73.         {// NB
  74.          // UW, NB, WB
  75.                 { 0, 0, 1 }, // UW
  76.                 { 0, 0, 0 }, // NB
  77.                 { 1, 0, 0 }, // WB
  78.         },
  79.         {// WB
  80.          // UW, NB, WB
  81.                 { 1, 1, 0 }, // UW
  82.                 { 0, 0, 1 }, // NB
  83.                 { 1, 0, 0 }, // WB
  84.         },
  85.         // *INDENT-ON* - disable uncrustify's indenting, as I want to preserve specific comment formatting.
  86. };
  87.  
  88. namespace PinchCornerTable
  89. {
  90.  
  91. enum EBitMask : uint8
  92. {
  93.         eExt = BIT(0), //!< pinch point on external contour
  94.         eInt = BIT(1)  //!< pinch point on internal contour
  95. };
  96.  
  97. // Pinch corner table is used to detect unremovable pinch points on external contours
  98. // using neighbour classes.
  99. // Indexing order: left, front-left, front.
  100. // TODO pavloi 2016.03.21: s_CornerTable and s_PinchCornerTable can be merged together (bitmask).
  101. static const uint8 s_PinchCornerTable[3][3][3] =
  102. {
  103.         // *INDENT-OFF* - disable uncrustify's indenting, as I want to preserve specific comment formatting.
  104.         {// UW
  105.          //   UW         , NB  , WB
  106.                 { 0          , 0   , 0    }, // UW
  107.                 { eExt | eInt, 0   , eExt }, // NB
  108.                 { eExt | eInt, eInt, 0    }, // WB
  109.         },
  110.         {// NB
  111.          //   UW         , NB  , WB
  112.                 { 0          , eInt, 0    }, // UW
  113.                 { 0          , 0   , 0    }, // NB
  114.                 { eInt       , eInt, 0    }, // WB
  115.         },
  116.         {// WB
  117.          //   UW         , NB  , WB
  118.                 { 0          , 0   , eExt }, // UW
  119.                 { eExt       , 0   , eExt }, // NB
  120.                 { 0          , 0   , 0    }, // WB
  121.         },
  122.         // *INDENT-ON* - disable uncrustify's indenting, as I want to preserve specific comment formatting.
  123. };
  124.  
  125. }
  126.  
  127. /*static */ size_t CTileGenerator::BorderSizeH(const Params& params)
  128. {
  129.         // TODO pavloi 2016.03.16: inclineTestCount = (height + 1) comes from FilterWalkable
  130.         const size_t inclineTestCount = params.agent.climbableHeight + 1;
  131.  
  132.         return (params.flags & Params::NoBorder) ? 0 : (params.agent.radius + inclineTestCount + 1);
  133. }
  134.  
  135. /*static */ size_t CTileGenerator::BorderSizeV(const Params& params)
  136. {
  137.         // TODO pavloi 2016.03.16: inclineTestCount = (height + 1) comes from FilterWalkable
  138.         const size_t inclineTestCount = params.agent.climbableHeight + 1;
  139.         const size_t maxZDiffInWorstCase = inclineTestCount * params.agent.climbableHeight;
  140.  
  141.         // TODO pavloi 2016.03.16: agent.height is not applied here, because it's usually applied additionally in other places.
  142.         // Or such places just don't care.
  143.         // +1 just in case, I'm not fully tested this formula.
  144.         return (params.flags & Params::NoBorder) ? 0 : (maxZDiffInWorstCase + 1);
  145. }
  146.  
  147. void CTileGenerator::Clear()
  148. {
  149.         m_profiler = ProfilerType();
  150.  
  151.         m_mesh.Clear();
  152.         m_bvtree.clear();
  153.  
  154.         m_spanGrid.Clear();
  155.         m_distances.clear();
  156.         m_labels.clear();
  157.         m_paint.clear();
  158.         m_regions.clear();
  159.         m_polygons.clear();
  160.         m_tracerPaths.clear();
  161.         m_spanGridRaw.Clear();
  162.         m_spanGridFlagged.Clear();
  163. }
  164.  
  165. bool CTileGenerator::Generate(const Params& params, STile& tile, uint32* tileHash)
  166. {
  167.         if ((params.sizeX > MaxTileSizeX) || (params.sizeY > MaxTileSizeY) || (params.sizeZ > MaxTileSizeZ))
  168.                 return false;
  169.  
  170.         const float MinVoxelSize = 0.025f;
  171.         if ((params.voxelSize.x < MinVoxelSize) || (params.voxelSize.y < MinVoxelSize) || (params.voxelSize.z < MinVoxelSize))
  172.                 return false;
  173.  
  174.         Clear();
  175.  
  176.         m_params = params;
  177.         m_profiler = ProfilerType();
  178.  
  179.         const AABB tileAabbWorld(m_params.origin, m_params.origin + Vec3i(m_params.sizeX, m_params.sizeY, m_params.sizeZ));
  180.         AABB aabb = tileAabbWorld;
  181.  
  182.         if (m_params.boundary && !m_params.boundary->Overlaps(aabb))
  183.                 return false;
  184.  
  185.         // TODO pavloi 2016.03.15: this calculation to set aabb z is repeated several times through code under
  186.         // different names (spaceTop in filter walkable, for example).
  187.  
  188.         const size_t border = BorderSizeH(m_params);
  189.         const size_t borderV = BorderSizeV(m_params);
  190.         if (border | borderV)
  191.                 aabb.Expand(Vec3(border * m_params.voxelSize.x, border * m_params.voxelSize.y, borderV * m_params.voxelSize.z));
  192.  
  193.         aabb.max.z += m_params.agent.height * m_params.voxelSize.z;
  194.  
  195.         bool fullyContained = true;
  196.  
  197.         if (m_params.boundary || m_params.exclusionCount)
  198.         {
  199.                 for (size_t e = 0; e < m_params.exclusionCount; ++e)
  200.                 {
  201.                         BoundingVolume::ExtendedOverlap eoverlap = m_params.exclusions[e].Contains(aabb);
  202.  
  203.                         if (eoverlap == BoundingVolume::FullOverlap)
  204.                                 return false;
  205.                         else if (eoverlap == BoundingVolume::PartialOverlap)
  206.                                 fullyContained = false;
  207.                 }
  208.  
  209.                 BoundingVolume::ExtendedOverlap ioverlap =
  210.                   m_params.boundary ? m_params.boundary->Contains(aabb) : BoundingVolume::FullOverlap;
  211.  
  212.                 if (ioverlap == BoundingVolume::NoOverlap)
  213.                         return false;
  214.                 else if (ioverlap == BoundingVolume::PartialOverlap)
  215.                         fullyContained = false;
  216.         }
  217.  
  218.         CompactSpanGrid().Swap(m_spanGrid);
  219.         SpanExtraInfo().swap(m_distances);
  220.         SpanExtraInfo().swap(m_labels);
  221.         Regions().swap(m_regions);
  222.         Polygons().swap(m_polygons);
  223.  
  224.         m_mesh.Clear();
  225.         m_mesh.SetTileAabb(tileAabbWorld);
  226.         BVTree().swap(m_bvtree);
  227.  
  228.         CompactSpanGrid().Swap(m_spanGridRaw);
  229.         CompactSpanGrid().Swap(m_spanGridFlagged);
  230.  
  231.         uint32 hashSeed = 0;
  232.         if (fullyContained)
  233.                 hashSeed = 0xf007b00b;
  234.         else
  235.         {
  236.                 HashComputer hash;
  237.  
  238.                 if (m_params.boundary || m_params.exclusionCount)
  239.                 {
  240.                         for (size_t e = 0; e < m_params.exclusionCount; ++e)
  241.                         {
  242.                                 const BoundingVolume& volume = m_params.exclusions[e];
  243.                                 const size_t vertexCount = volume.vertices.size();
  244.  
  245.                                 for (size_t v = 0; v < vertexCount; ++v)
  246.                                 {
  247.                                         hash.Add(volume.vertices[v]);
  248.                                 }
  249.  
  250.                                 hash.Add(volume.height);
  251.                         }
  252.  
  253.                         if (m_params.boundary)
  254.                         {
  255.                                 const BoundingVolume& volume = *m_params.boundary;
  256.                                 const size_t vertexCount = volume.vertices.size();
  257.  
  258.                                 for (size_t v = 0; v < vertexCount; ++v)
  259.                                 {
  260.                                         hash.Add(volume.vertices[v]);
  261.                                 }
  262.  
  263.                                 hash.Add(volume.height);
  264.                         }
  265.                 }
  266.  
  267.                 hash.Complete();
  268.                 hashSeed = hash.GetValue();
  269.         }
  270.  
  271.         m_mesh.ResetHashSeed(hashSeed);
  272.  
  273.         if (params.pTileGeneratorExtensions)
  274.         {
  275.                 // #MNM_TODO pavloi 2016.07.20: add profiler statistics
  276.                 MNM::TileGenerator::SExtensionParams extensionParams;
  277.                 extensionParams.tileAabbWorld = tileAabbWorld;
  278.                 extensionParams.extendedTileAabbWorld = aabb;
  279.                 extensionParams.navAgentTypeId = params.navAgentTypeId;
  280.  
  281.                 {
  282.                         AUTO_READLOCK(params.pTileGeneratorExtensions->extensionsLock);
  283.                         for (const auto& idExtensionPair : params.pTileGeneratorExtensions->extensions)
  284.                         {
  285.                                 MNM::TileGenerator::IExtension* pExtension = idExtensionPair.second;
  286.                                 const bool bContinue = pExtension->Generate(extensionParams, m_mesh);
  287.                                 if (!bContinue)
  288.                                 {
  289.                                         break;
  290.                                 }
  291.                         }
  292.                 }
  293.         }
  294.  
  295.         hashSeed = m_mesh.CompleteAndGetHashValue();
  296.  
  297.         uint32 hashValue = 0;
  298.         size_t triCount = VoxelizeVolume(aabb, hashSeed, &hashValue);
  299.  
  300.         const uint32 oldHashValueForTest =
  301.           m_params.flags & Params::NoHashTest
  302.           ? 0
  303.           : m_params.hashValue;
  304.  
  305.         if (tileHash)
  306.                 *tileHash = hashValue;
  307.  
  308.         if (!(m_params.flags & Params::NoHashTest) && (oldHashValueForTest == hashValue))
  309.         {
  310.                 // no changes - see GenerateTileJob() in NavigationSystem.cpp
  311.                 return false;
  312.         }
  313.  
  314.         if (triCount)
  315.         {
  316.                 if (m_params.flags & Params::DebugInfo)
  317.                 {
  318.                         m_spanGridRaw = m_spanGrid;
  319.                 }
  320.  
  321.                 GenerateFromVoxelizedVolume(aabb, fullyContained);
  322.         }
  323.  
  324.         if (m_params.flags & Params::BuildBVTree)
  325.                 BuildBVTree();
  326.  
  327.         if (m_mesh.IsEmpty())
  328.                 return false;
  329.  
  330.         tile.SetHashValue(hashValue);
  331.  
  332.         m_mesh.CopyIntoTile(tile);
  333.  
  334.         if (m_params.flags & Params::BuildBVTree)
  335.                 tile.CopyNodes(&m_bvtree.front(), static_cast<uint16>(m_bvtree.size()));
  336.  
  337.         return true;
  338. }
  339.  
  340. const CTileGenerator::ProfilerType& CTileGenerator::GetProfiler() const
  341. {
  342.         return m_profiler;
  343. }
  344.  
  345. size_t CTileGenerator::VoxelizeVolume(const AABB& volume, uint32 hashValueSeed, uint32* hashValue)
  346. {
  347.         m_profiler.StartTimer(Voxelization);
  348.  
  349.         WorldVoxelizer voxelizer;
  350.  
  351.         voxelizer.Start(volume, m_params.voxelSize);
  352.  
  353. #if DEBUG_MNM_ENABLED
  354.         if (m_params.flags & Params::DebugInfo)
  355.         {
  356.                 voxelizer.SetDebugRawGeometryContainer(&m_debugRawGeometry);
  357.                 m_debugVoxelizedVolume = volume;
  358.         }
  359. #endif // DEBUG_MNM_ENABLED
  360.  
  361.         size_t triCount = voxelizer.ProcessGeometry(hashValueSeed,
  362.                                                     m_params.flags & Params::NoHashTest ? 0 : m_params.hashValue, hashValue, m_params.agent.callback);
  363.         voxelizer.CalculateWaterDepth();
  364.  
  365.         m_profiler.AddMemory(DynamicSpanGridMemory, voxelizer.GetSpanGrid().GetMemoryUsage());
  366.  
  367.         m_spanGrid.BuildFrom(voxelizer.GetSpanGrid());
  368.  
  369.         m_profiler.StopTimer(Voxelization);
  370.  
  371.         m_profiler.AddMemory(CompactSpanGridMemory, m_spanGrid.GetMemoryUsage());
  372.         m_profiler.FreeMemory(DynamicSpanGridMemory, voxelizer.GetSpanGrid().GetMemoryUsage());
  373.  
  374.         m_profiler.AddStat(VoxelizationTriCount, triCount);
  375.  
  376.         return triCount;
  377. }
  378.  
  379. struct CTileGenerator::SFilterWalkableParams
  380. {
  381.         SFilterWalkableParams(CompactSpanGrid& grid, const AABB& aabb, const bool fullyContained, const CTileGenerator::Params& params)
  382.                 : spanGrid(grid)
  383.                 , aabb(aabb)
  384.                 , bFullyContained(fullyContained)
  385.                 , gridWidth(spanGrid.GetWidth())
  386.                 , gridHeight(spanGrid.GetHeight())
  387.                 , heightVoxelCount(params.agent.height)
  388.                 , climbableVoxelCount(params.agent.climbableHeight)
  389.                 , border(CTileGenerator::BorderSizeH(params))
  390.                 , climbableInclineGradient(params.climbableInclineGradient)
  391.                 , climbableStepRatio(params.climbableStepRatio)
  392.                 , inclineTestCount(climbableVoxelCount + 1)
  393.                 , climbableInclineGradientLowerBound((size_t)floor(climbableInclineGradient))
  394.                 , climbableInclineGradientSquared(climbableInclineGradient * climbableInclineGradient)
  395.                 // TODO pavloi 2016.03.10: is this formula correct? Maybe there is a better way to get the number from an actual voxelized volume.
  396.                 , spaceTop((2 * CTileGenerator::BorderSizeV(params)) + params.agent.height + CTileGenerator::Top(params))
  397.         {}
  398.  
  399.         CompactSpanGrid& spanGrid;
  400.         const AABB&      aabb;
  401.         const bool       bFullyContained;
  402.  
  403.         const size_t     gridWidth;
  404.         const size_t     gridHeight;
  405.  
  406.         const size_t     heightVoxelCount;
  407.         const size_t     climbableVoxelCount;
  408.         const size_t     border;
  409.         const float      climbableInclineGradient;
  410.         const float      climbableStepRatio; //!< The bigger the step height, the more step width required to be traversable
  411.  
  412.         const size_t     inclineTestCount; //!< Must be bigger that climbable height to correctly resolve valid steps
  413.         const size_t     climbableInclineGradientLowerBound;
  414.         float const      climbableInclineGradientSquared;
  415.         const size_t     spaceTop;
  416. };
  417.  
  418. struct CTileGenerator::SSpanClearance
  419. {
  420.         SSpanClearance(const SSpanCoord& spanCoord, const CompactSpanGrid::Span& span, const CompactSpanGrid::Cell& cell, const CTileGenerator::SFilterWalkableParams& filterParams, const CompactSpanGrid& spanGrid)
  421.         {
  422.                 top = span.bottom + span.height;
  423.                 nextBottom = filterParams.spaceTop;
  424.  
  425.                 if (spanCoord.spanIdx + 1 < cell.count)
  426.                 {
  427.                         const CompactSpanGrid::Span& nextSpan = spanGrid.GetSpan(cell.index + spanCoord.spanIdx + 1);
  428.                         nextBottom = nextSpan.bottom;
  429.                 }
  430.         }
  431.  
  432.         size_t Clearance() const { return nextBottom - top; }
  433.  
  434.         size_t top;
  435.         size_t nextBottom;
  436. };
  437.  
  438. bool CTileGenerator::GenerateFromVoxelizedVolume(const AABB& aabb, const bool fullyContained)
  439. {
  440.         FilterWalkable(aabb, fullyContained);
  441.  
  442.         if (!m_spanGrid.GetSpanCount())
  443.                 return false;
  444.  
  445.         ComputeDistanceTransform();
  446.         //BlurDistanceTransform();
  447.  
  448.         if (!ExtractContours())
  449.                 return false;
  450.  
  451.         FilterBadRegions(m_params.minWalkableArea);
  452.         SimplifyContours();
  453.         Triangulate();
  454.  
  455.         return true;
  456. }
  457.  
  458. void CTileGenerator::FilterWalkable(const AABB& aabb, bool fullyContained)
  459. {
  460.         m_profiler.StartTimer(Filter);
  461.  
  462.         const SFilterWalkableParams filterParams(m_spanGrid, aabb, fullyContained, m_params);
  463.  
  464.         size_t nonWalkableCount = 0;
  465.  
  466.         for (size_t y = 0; y < filterParams.gridHeight; ++y)
  467.         {
  468.                 const size_t ymult = y * filterParams.gridWidth;
  469.  
  470.                 for (size_t x = 0; x < filterParams.gridWidth; ++x)
  471.                 {
  472.                         if (const CompactSpanGrid::Cell cell = m_spanGrid[x + ymult])
  473.                         {
  474.                                 const bool boundaryCell = IsBoundaryCell_Static(x, y, filterParams.border, filterParams.gridWidth, filterParams.gridHeight);
  475.                                 const uint32 boundaryFlag(boundaryCell ? TileBoundary : 0);
  476.  
  477.                                 const size_t count = cell.count;
  478.  
  479.                                 for (size_t s = 0; s < count; ++s)
  480.                                 {
  481.                                         const SSpanCoord spanCoord(x, y, s, cell.index + s);
  482.                                         CompactSpanGrid::Span& span = m_spanGrid.GetSpan(cell.index + s);
  483.  
  484.                                         span.flags |= boundaryFlag;
  485.  
  486.                                         if (FilterWalkable_CheckSpanBackface(span))
  487.                                         {
  488.                                                 span.flags |= NotWalkable;
  489.                                                 ++nonWalkableCount;
  490.                                                 DebugAddNonWalkableReason(spanCoord, "backface");
  491.                                                 continue;
  492.                                         }
  493.  
  494.                                         if (FilterWalkable_CheckSpanWaterDepth(span, m_params))
  495.                                         {
  496.                                                 span.flags |= NotWalkable;
  497.                                                 ++nonWalkableCount;
  498.                                                 DebugAddNonWalkableReason(spanCoord, "water");
  499.                                                 continue;
  500.                                         }
  501.  
  502.                                         const SSpanClearance spanClearance(spanCoord, span, cell, filterParams, m_spanGrid);
  503.                                         if (spanClearance.Clearance() < filterParams.heightVoxelCount)
  504.                                         {
  505.                                                 span.flags |= NotWalkable;
  506.                                                 ++nonWalkableCount;
  507.                                                 DebugAddNonWalkableReason(spanCoord, "clearance");
  508.                                                 continue;
  509.                                         }
  510.  
  511.                                         SNonWalkableNeighbourReason* pNeighbourReason = nullptr;
  512. #if DEBUG_MNM_GATHER_NONWALKABLE_REASONS
  513.                                         SNonWalkableNeighbourReason neighbourReason;
  514.                                         IF_UNLIKELY (m_params.flags & Params::DebugInfo)
  515.                                         {
  516.                                                 pNeighbourReason = &neighbourReason;
  517.                                         }
  518. #endif
  519.  
  520.                                         if (FilterWalkable_CheckNeighbours(spanCoord, spanClearance, filterParams, pNeighbourReason))
  521.                                         {
  522.                                                 span.flags |= NotWalkable;
  523.                                                 ++nonWalkableCount;
  524. #if DEBUG_MNM_GATHER_NONWALKABLE_REASONS
  525.                                                 if (pNeighbourReason)
  526.                                                 {
  527.                                                         m_debugNonWalkableReasonMap[spanCoord] = SNonWalkableReason("neighbour", *pNeighbourReason);
  528.                                                 }
  529. #endif
  530.                                                 continue;
  531.                                         }
  532.                                 } // for s
  533.                         }   // if cell
  534.                 }     // for x
  535.         }       // for y
  536.  
  537.         // apply boundaries
  538.         if (!fullyContained)
  539.         {
  540.                 FilterWalkable_CheckBoundaries(aabb, filterParams.gridWidth, filterParams.gridHeight);
  541.         }
  542.  
  543.         // TODO pavloi 2016.03.10: CheckBoundaries is not adding to nonWalkableCount, so new compact grid will
  544.         // reserve more spans than required.
  545.         CompactSpanGrid compact;
  546.         compact.CompactExcluding(m_spanGrid, NotWalkable, m_spanGrid.GetSpanCount() - nonWalkableCount);
  547.  
  548.         m_profiler.AddMemory(CompactSpanGridMemory, compact.GetMemoryUsage());
  549.  
  550.         // TODO pavloi 2016.03.10: m_spanGrid is used to visualize "Raw voxels", but actually contains
  551.         // only walkable voxels after this point. m_spanGridFlagged contains all (but already flagged) voxels.
  552.         compact.Swap(m_spanGrid);
  553.  
  554.         m_profiler.StopTimer(Filter);
  555.  
  556.         if (m_params.flags & Params::DebugInfo)
  557.                 m_spanGridFlagged.Swap(compact);
  558.         else
  559.                 m_profiler.FreeMemory(CompactSpanGridMemory, compact.GetMemoryUsage());
  560. }
  561.  
  562. /*static*/ bool CTileGenerator::FilterWalkable_CheckSpanBackface(const CompactSpanGrid::Span& span)
  563. {
  564.         return span.backface;
  565. }
  566.  
  567. /*static*/ bool CTileGenerator::FilterWalkable_CheckSpanWaterDepth(const CompactSpanGrid::Span& span, const Params& params)
  568. {
  569.         return span.depth > params.agent.maxWaterDepth;
  570. }
  571.  
  572. /*static*/ bool CTileGenerator::FilterWalkable_CheckNeighbours(const SSpanCoord& spanCoord, const SSpanClearance& spanClearance, const SFilterWalkableParams& filterParams, SNonWalkableNeighbourReason* pOutReason)
  573. {
  574.         const size_t axisNeighbourCount = 4;
  575.  
  576.         bool neighbourTest(true);
  577.  
  578.         float probeInclinationVars[axisNeighbourCount] = { 0.0f };
  579.  
  580.         for (size_t n = 0; n < axisNeighbourCount; ++n)
  581.         {
  582.                 const size_t nx = spanCoord.cellX + NeighbourOffset_TileGenerator[n][0];
  583.                 const size_t ny = spanCoord.cellY + NeighbourOffset_TileGenerator[n][1];
  584.  
  585.                 // Neighbour off grid - pass
  586.                 // NOTE: (0 - 1) will underflow to size_t::max, which is also > gridWidth.
  587.                 if (nx >= filterParams.gridWidth || ny >= filterParams.gridHeight)
  588.                         continue;
  589.  
  590.                 const size_t neighbourCellGridIndex = (ny * filterParams.gridWidth) + nx;
  591.                 const CompactSpanGrid::Cell& ncell = filterParams.spanGrid[neighbourCellGridIndex];
  592.                 if (!ncell)
  593.                 {
  594.                         //Empty neighbour on grid - fail
  595.                         neighbourTest = false;
  596. #if DEBUG_MNM_GATHER_NONWALKABLE_REASONS
  597.                         IF_UNLIKELY (pOutReason)
  598.                         {
  599.                                 pOutReason->szReason = "empty";
  600.                         }
  601. #endif
  602.                         break;
  603.                 }
  604.  
  605.                 const size_t ncount = ncell.count;
  606.                 const size_t nindex = ncell.index;
  607.  
  608.                 size_t ptopLast;
  609.                 size_t pnextBottomLast;
  610.                 size_t dpTopFirst;
  611.                 size_t dpTopLast;
  612.  
  613.                 int sdpTopFirst;
  614.                 int sdpTopLast;
  615.  
  616.                 // Assume this neighbour cell is not valid. Succeed when we find just one valid adjacent span
  617.                 bool nCellValid(false);
  618.  
  619.                 for (size_t ns = 0; ns < ncount; ++ns)
  620.                 {
  621.                         const size_t nsindex = nindex + ns;
  622.                         const CompactSpanGrid::Span& nspan = filterParams.spanGrid.GetSpan(nsindex);
  623.  
  624.                         const SSpanCoord neighbourCoord(nx, ny, ns, nsindex);
  625.                         const SSpanClearance neighbourClearance(neighbourCoord, nspan, ncell, filterParams, filterParams.spanGrid);
  626.  
  627.                         const size_t dTop = (size_t)abs((int)(neighbourClearance.top - spanClearance.top));
  628.  
  629.                         //Test validity
  630.                         if (dTop <= filterParams.climbableVoxelCount
  631.                             && min(spanClearance.nextBottom, neighbourClearance.nextBottom) >= max(spanClearance.top, neighbourClearance.top) + filterParams.heightVoxelCount)
  632.                         {
  633.                                 ptopLast = neighbourClearance.top;
  634.                                 pnextBottomLast = neighbourClearance.nextBottom;
  635.                                 dpTopFirst = dpTopLast = dTop;
  636.  
  637.                                 sdpTopFirst = sdpTopLast = int(neighbourClearance.top) - int(spanClearance.top);
  638.  
  639.                                 nCellValid = true;
  640.  
  641.                                 break;
  642.                         }
  643.                 }
  644.  
  645.                 if (!nCellValid)
  646.                 {
  647.                         neighbourTest = false;
  648. #if DEBUG_MNM_GATHER_NONWALKABLE_REASONS
  649.                         IF_UNLIKELY (pOutReason)
  650.                         {
  651.                                 pOutReason->szReason = "clearance";
  652.                         }
  653. #endif
  654.                         break;
  655.                 }
  656.  
  657.                 if (dpTopFirst > 0)
  658.                 {
  659.                         size_t const stepTestCount((size_t)ceil(dpTopFirst * filterParams.climbableStepRatio));
  660.                         size_t const stepTestTolerance(stepTestCount - 1);
  661.                         bool const isStep(dpTopFirst > (filterParams.climbableInclineGradientLowerBound + 1));
  662.                         bool stepTest(true);
  663.  
  664.                         AIAssert(stepTestCount <= filterParams.inclineTestCount);
  665.  
  666.                         size_t ptopMin(ptopLast);
  667.                         size_t ptopMax(ptopLast);
  668.  
  669.                         size_t pTopOffsMax(dpTopFirst);
  670.  
  671.                         size_t pc(2);
  672.  
  673.                         for (; pc <= filterParams.inclineTestCount; ++pc)
  674.                         {
  675.                                 size_t px = spanCoord.cellX + NeighbourOffset_TileGenerator[n][0] * pc;
  676.                                 size_t py = spanCoord.cellY + NeighbourOffset_TileGenerator[n][1] * pc;
  677.  
  678.                                 const CompactSpanGrid::Cell pcell = filterParams.spanGrid.GetCell(px, py);
  679.  
  680.                                 if (!pcell)
  681.                                 {
  682.                                         //Empty neighbour - stop probe (but no fail)
  683.                                         break;
  684.                                 }
  685.  
  686.                                 const size_t pcount = pcell.count;
  687.                                 const size_t pindex = pcell.index;
  688.  
  689.                                 bool pCellValid(false);
  690.  
  691.                                 for (size_t ps = 0; ps < pcount; ++ps)
  692.                                 {
  693.                                         const size_t psindex = pindex + ps;
  694.                                         const CompactSpanGrid::Span& pspan = filterParams.spanGrid.GetSpan(psindex);
  695.  
  696.                                         const SSpanCoord probeCoord(px, py, ps, psindex);
  697.                                         const SSpanClearance probeClearance(probeCoord, pspan, pcell, filterParams, filterParams.spanGrid);
  698.  
  699.                                         const size_t dpTop = (size_t)abs((int)(probeClearance.top - ptopLast));
  700.  
  701.                                         //Test validity
  702.                                         if (dpTop <= filterParams.climbableVoxelCount
  703.                                             && min(pnextBottomLast, probeClearance.nextBottom) >= max(ptopLast, probeClearance.top) + filterParams.heightVoxelCount)
  704.                                         {
  705.                                                 // Track range of tops in probe
  706.                                                 ptopMin = min(ptopMin, probeClearance.top);
  707.                                                 ptopMax = max(ptopMax, probeClearance.top);
  708.  
  709.                                                 const size_t pTopOffs = (size_t)abs(int(probeClearance.top) - int(spanClearance.top));
  710.                                                 pTopOffsMax = max(pTopOffsMax, pTopOffs);
  711.  
  712.                                                 sdpTopLast = (int)(probeClearance.top - ptopLast);
  713.  
  714.                                                 ptopLast = probeClearance.top;
  715.                                                 pnextBottomLast = probeClearance.nextBottom;
  716.                                                 dpTopLast = dpTop;
  717.  
  718.                                                 nCellValid = true;
  719.  
  720.                                                 break;
  721.                                         }
  722.                                 }
  723.  
  724.                                 if (!nCellValid)
  725.                                 {
  726.                                         break;
  727.                                 }
  728.  
  729.                                 if (isStep)
  730.                                 {
  731.                                         if (pc <= stepTestCount
  732.                                             && pTopOffsMax > stepTestTolerance + dpTopFirst)
  733.                                         {
  734.                                                 stepTest = false;
  735.                                         }
  736.                                 }
  737.                                 else
  738.                                 {
  739.                                         if (sdpTopLast > sdpTopFirst + 1
  740.                                             || sdpTopLast < sdpTopFirst - 1)
  741.                                         {
  742.                                                 // stop probe (but no fail)
  743.                                                 break;
  744.                                         }
  745.  
  746.                                         probeInclinationVars[n] = (float)(ptopMax - ptopMin);
  747.                                 }
  748.                         }
  749.  
  750.                         if (isStep
  751.                             && !stepTest
  752.                             && (pTopOffsMax > filterParams.climbableVoxelCount))
  753.                         {
  754.                                 neighbourTest = false;
  755.  
  756. #if DEBUG_MNM_GATHER_NONWALKABLE_REASONS
  757.                                 IF_UNLIKELY (pOutReason)
  758.                                 {
  759.                                         pOutReason->szReason = "step test";
  760.                                 }
  761. #endif
  762.                         }
  763.                         else
  764.                         {
  765.                                 probeInclinationVars[n] /= pc - 1;
  766.                         }
  767.                 }
  768.         }
  769.  
  770.         if (neighbourTest)
  771.         {
  772.                 float previousProbeGainSquared(probeInclinationVars[axisNeighbourCount - 1] * probeInclinationVars[axisNeighbourCount - 1]);
  773.  
  774.                 // Test for probe pairs at 90degrees giving a net incline above tolerance
  775.  
  776.                 // TODO pavloi 2016.03.10: I do not fully understand the meaning of the metric we have here, but
  777.                 // I think, there may be an error. Neighbours in the NeighbourOffset_TileGenerator are listed in order y, -x, x, -y,
  778.                 // so the compared probe pairs are (y, -y), (-x, y), (x, -x), (-y, x).
  779.                 // I think, expected order is something like (x, y), (y, -x), (-x, -y), (-y, x), so there are never cases,
  780.                 // when we compare (y, -y) and (x, -x).
  781.                 // I don't see any other piece of code, which depends on the order of first four elements of NeighbourOffset_TileGenerator, so
  782.                 // should be save to reorder them.
  783.                 // But still, a comment before NeighbourOffset_TileGenerator states, that this order is really expected. Who to belive?
  784.  
  785.                 // TODO pavloi 2016.03.11: if we perform stepTest for neighbours, then all probeInclinationVars will stay 0 and condition in this loop
  786.                 // will never be true, so neighbourTest will also stay true. This whole loop is not required then.
  787.                 for (size_t n = 0; n < axisNeighbourCount; ++n)
  788.                 {
  789.                         float thisProbeGainSquared(probeInclinationVars[n] * probeInclinationVars[n]);
  790.                         if ((float)(thisProbeGainSquared + previousProbeGainSquared) > filterParams.climbableInclineGradientSquared)
  791.                         {
  792.                                 neighbourTest = false;
  793. #if DEBUG_MNM_GATHER_NONWALKABLE_REASONS
  794.                                 IF_UNLIKELY (pOutReason)
  795.                                 {
  796.                                         pOutReason->szReason = "inclination";
  797.                                 }
  798. #endif
  799.                                 break;
  800.                         }
  801.                         previousProbeGainSquared = thisProbeGainSquared;
  802.                 }
  803.         }
  804.  
  805.         return !neighbourTest;
  806. }
  807.  
  808. void CTileGenerator::FilterWalkable_CheckBoundaries(const AABB& aabb, const size_t gridWidth, const size_t gridHeight)
  809. {
  810.         const float convX = 1.0f / m_params.voxelSize.x;
  811.         const float convY = 1.0f / m_params.voxelSize.y;
  812.         const float convZ = 1.0f / m_params.voxelSize.z;
  813.  
  814.         const Vec3 voxelSize = m_params.voxelSize;
  815.         const Vec3 halfVoxel = m_params.voxelSize * 0.5f;
  816.  
  817.         const Vec3 bmax = aabb.max - aabb.min;
  818.  
  819.         for (size_t e = 0; e < m_params.exclusionCount; ++e)
  820.         {
  821.                 const BoundingVolume& exclusion = m_params.exclusions[e];
  822.  
  823.                 if (exclusion.Overlaps(aabb))
  824.                 {
  825.                         const Vec3 emin = (exclusion.aabb.min - aabb.min);
  826.                         const Vec3 emax = (exclusion.aabb.max - aabb.min);
  827.  
  828.                         uint16 xmin = (uint16)(std::max(0.0f, emin.x) * convX);
  829.                         uint16 xmax = (uint16)(std::min(bmax.x, emax.x) * convX);
  830.  
  831.                         uint16 ymin = (uint16)(std::max(0.0f, emin.y) * convY);
  832.                         uint16 ymax = (uint16)(std::min(bmax.y, emax.y) * convY);
  833.  
  834.                         uint16 zmin = (uint16)(std::max(0.0f, emin.z) * convZ);
  835.                         uint16 zmax = (uint16)(std::min(bmax.z, emax.z) * convZ);
  836.  
  837.                         for (uint16 y = ymin; y <= ymax; ++y)
  838.                         {
  839.                                 const size_t ymult = y * gridWidth;
  840.  
  841.                                 for (uint16 x = xmin; x <= xmax; ++x)
  842.                                 {
  843.                                         if (const CompactSpanGrid::Cell& cell = m_spanGrid[x + ymult])
  844.                                         {
  845.                                                 for (size_t s = 0; s < cell.count; ++s)
  846.                                                 {
  847.                                                         CompactSpanGrid::Span& span = m_spanGrid.GetSpan(cell.index + s);
  848.  
  849.                                                         if (span.flags & NotWalkable)
  850.                                                                 continue;
  851.  
  852.                                                         size_t top = span.bottom + span.height;
  853.  
  854.                                                         if ((top >= zmin) && (top <= zmax))
  855.                                                         {
  856.                                                                 const Vec3 point = aabb.min + halfVoxel + Vec3(x * voxelSize.x, y * voxelSize.y, top * voxelSize.z);
  857.  
  858.                                                                 if (exclusion.Contains(point))
  859.                                                                 {
  860.                                                                         span.flags |= NotWalkable;
  861. #if DEBUG_MNM_GATHER_NONWALKABLE_REASONS
  862.                                                                         IF_UNLIKELY (m_params.flags & Params::DebugInfo)
  863.                                                                         {
  864.                                                                                 m_debugNonWalkableReasonMap[SSpanCoord(x, y, s, cell.index + s)] = SNonWalkableReason("exclusion");
  865.                                                                         }
  866. #endif
  867.                                                                 }
  868.                                                         }
  869.                                                 }
  870.                                         }
  871.                                 }
  872.                         }
  873.                 }
  874.         }
  875.  
  876.         if (m_params.boundary)
  877.         {
  878.                 const BoundingVolume& boundary = *m_params.boundary;
  879.  
  880.                 for (uint16 y = 0; y <= gridHeight; ++y)
  881.                 {
  882.                         const size_t ymult = y * gridWidth;
  883.  
  884.                         for (uint16 x = 0; x <= gridWidth; ++x)
  885.                         {
  886.                                 const CompactSpanGrid::Cell& cell = m_spanGrid[x + ymult];
  887.  
  888.                                 if (cell)
  889.                                 {
  890.                                         for (size_t s = 0; s < cell.count; ++s)
  891.                                         {
  892.                                                 CompactSpanGrid::Span& span = m_spanGrid.GetSpan(cell.index + s);
  893.  
  894.                                                 if (span.flags & NotWalkable)
  895.                                                         continue;
  896.  
  897.                                                 size_t top = span.bottom + span.height;
  898.  
  899.                                                 const Vec3 point = aabb.min + halfVoxel + Vec3(x * voxelSize.x, y * voxelSize.y, top * voxelSize.z);
  900.  
  901.                                                 if (!boundary.Contains(point))
  902.                                                 {
  903.                                                         span.flags |= NotWalkable;
  904. #if DEBUG_MNM_GATHER_NONWALKABLE_REASONS
  905.                                                         IF_UNLIKELY (m_params.flags & Params::DebugInfo)
  906.                                                         {
  907.                                                                 m_debugNonWalkableReasonMap[SSpanCoord(x, y, s, cell.index + s)] = SNonWalkableReason("boundary");
  908.                                                         }
  909. #endif
  910.                                                 }
  911.                                         }
  912.                                 }
  913.                         }
  914.                 }
  915.         }
  916. }
  917.  
  918. inline bool IsBorderLabel(uint16 label)
  919. {
  920.         return (label & (CTileGenerator::BorderLabelH | CTileGenerator::BorderLabelV)) != 0;
  921. }
  922.  
  923. inline bool IsLabelValid(uint16 label)
  924. {
  925.         return (label < CTileGenerator::FirstInvalidLabel);
  926. }
  927.  
  928. /*      inline uint16 ConsolidateLabel(uint16 label)
  929.    {
  930.     if (label < TileGenerator::FirstInvalidLabel)
  931.       return label;
  932.     return TileGenerator::FirstInvalidLabel;
  933.    }*/
  934.  
  935. void CTileGenerator::ComputeDistanceTransform()
  936. {
  937.         m_profiler.StartTimer(DistanceTransform);
  938.  
  939.         const size_t gridWidth = m_spanGrid.GetWidth();
  940.         const size_t gridHeight = m_spanGrid.GetHeight();
  941.         const size_t spanCount = m_spanGrid.GetSpanCount();
  942.  
  943.         const size_t climbableVoxelCount = m_params.agent.climbableHeight;
  944.  
  945.         m_distances.resize(spanCount);
  946.  
  947.         m_profiler.AddMemory(SegmentationMemory, m_distances.size() * sizeof(SpanExtraInfo::value_type));
  948.  
  949.         // TODO pavloi 2016.03.15: why fill with NoLabel which equals to 4095?\
  950.         // Answer: we search for a minimum and 4095 serves as a kind of max distance value.
  951.         // I see no dependency on this particular value and it should be something like uint16::max instead.
  952.         std::fill(m_distances.begin(), m_distances.end(), NoLabel);
  953.  
  954.         const size_t KStraight = 2;
  955.         const size_t KDiagonal = 3;
  956.  
  957.         struct SweepElement
  958.         {
  959.                 int x;
  960.                 int y;
  961.                 int k;
  962.         };
  963.  
  964.         const size_t SweepPixelCount = 4;
  965.  
  966.         const SweepElement downSweep[SweepPixelCount] =
  967.         {
  968.                 { -1, 0,  KStraight },
  969.                 { -1, -1, KDiagonal },
  970.                 { 0,  -1, KStraight },
  971.                 { 1,  -1, KDiagonal },
  972.         };
  973.  
  974.         for (size_t y = 0; y < gridHeight; ++y)
  975.         {
  976.                 for (size_t x = 0; x < gridWidth; ++x)
  977.                 {
  978.                         if (const CompactSpanGrid::Cell cell = m_spanGrid.GetCell(x, y))
  979.                         {
  980.                                 const size_t index = cell.index;
  981.                                 const size_t count = cell.count;
  982.  
  983.                                 for (size_t s = 0; s < count; ++s)
  984.                                 {
  985.                                         const CompactSpanGrid::Span& span = m_spanGrid.GetSpan(index + s);
  986.  
  987.                                         const size_t top = span.bottom + span.height;
  988.                                         const uint16 current = m_distances[index + s];
  989.  
  990.                                         uint16 sweepValues[SweepPixelCount];
  991.  
  992.                                         for (size_t p = 0; p < SweepPixelCount; ++p)
  993.                                         {
  994.                                                 sweepValues[p] = 0;
  995.  
  996.                                                 const size_t nx = x + downSweep[p].x;
  997.                                                 const size_t ny = y + downSweep[p].y;
  998.  
  999.                                                 size_t nindex;
  1000.                                                 if (m_spanGrid.GetSpanAt(nx, ny, top, climbableVoxelCount, nindex))
  1001.                                                         sweepValues[p] = m_distances[nindex] + downSweep[p].k;
  1002.                                         }
  1003.  
  1004.                                         uint16 minimum = sweepValues[0];
  1005.  
  1006.                                         for (size_t p = 1; p < SweepPixelCount; ++p)
  1007.                                         {
  1008.                                                 minimum = std::min<uint16>(minimum, sweepValues[p]);
  1009.                                         }
  1010.  
  1011.                                         if (minimum < current)
  1012.                                                 m_distances[index + s] = minimum;
  1013.                                 }
  1014.                         }
  1015.                 }
  1016.         }
  1017.  
  1018.         const SweepElement upSweep[SweepPixelCount] =
  1019.         {
  1020.                 { 1,  0, KStraight },
  1021.                 { 1,  1, KDiagonal },
  1022.                 { 0,  1, KStraight },
  1023.                 { -1, 1, KDiagonal },
  1024.         };
  1025.  
  1026.         for (size_t y = gridHeight - 1; y; --y)
  1027.         {
  1028.                 // TODO pavloi 2016.03.15: out of bounds read? Shouldn't we start at gridWidth-1. There is a check below in GetCell()
  1029.                 for (size_t x = gridWidth; x; --x)
  1030.                 {
  1031.                         if (const CompactSpanGrid::Cell cell = m_spanGrid.GetCell(x, y))
  1032.                         {
  1033.                                 const size_t index = cell.index;
  1034.                                 const size_t count = cell.count;
  1035.  
  1036.                                 for (size_t s = 0; s < count; ++s)
  1037.                                 {
  1038.                                         const CompactSpanGrid::Span& span = m_spanGrid.GetSpan(index + s);
  1039.  
  1040.                                         const size_t top = span.bottom + span.height;
  1041.                                         const uint16 current = m_distances[index + s];
  1042.  
  1043.                                         uint16 sweepValues[SweepPixelCount];
  1044.  
  1045.                                         for (size_t p = 0; p < SweepPixelCount; ++p)
  1046.                                         {
  1047.                                                 sweepValues[p] = 0;
  1048.  
  1049.                                                 const size_t nx = x + upSweep[p].x;
  1050.                                                 const size_t ny = y + upSweep[p].y;
  1051.  
  1052.                                                 size_t nindex;
  1053.                                                 if (m_spanGrid.GetSpanAt(nx, ny, top, climbableVoxelCount, nindex))
  1054.                                                         sweepValues[p] = m_distances[nindex] + upSweep[p].k;
  1055.                                         }
  1056.  
  1057.                                         uint16 minimum = sweepValues[0];
  1058.  
  1059.                                         for (size_t p = 1; p < SweepPixelCount; ++p)
  1060.                                         {
  1061.                                                 minimum = std::min<uint16>(minimum, sweepValues[p]);
  1062.                                         }
  1063.  
  1064.                                         if (minimum < current)
  1065.                                                 m_distances[index + s] = minimum;
  1066.                                 }
  1067.                         }
  1068.                 }
  1069.         }
  1070.  
  1071.         m_profiler.StopTimer(DistanceTransform);
  1072. }
  1073.  
  1074. void CTileGenerator::BlurDistanceTransform()
  1075. {
  1076.         if (!m_params.blurAmount)
  1077.                 return;
  1078.  
  1079.         m_profiler.StartTimer(Blur);
  1080.  
  1081.         const size_t threshold = 1;
  1082.         const size_t gridWidth = m_spanGrid.GetWidth();
  1083.         const size_t gridHeight = m_spanGrid.GetHeight();
  1084.  
  1085.         const size_t climbableVoxelCount = m_params.agent.climbableHeight;
  1086.  
  1087.         m_labels.resize(m_distances.size());
  1088.  
  1089.         for (size_t i = 0; i < m_params.blurAmount; ++i)
  1090.         {
  1091.                 for (size_t y = 0; y < gridHeight; ++y)
  1092.                 {
  1093.                         for (size_t x = 0; x < gridWidth; ++x)
  1094.                         {
  1095.                                 if (const CompactSpanGrid::Cell cell = m_spanGrid.GetCell(x, y))
  1096.                                 {
  1097.                                         size_t index = cell.index;
  1098.                                         size_t count = cell.count;
  1099.  
  1100.                                         for (size_t s = 0; s < count; ++s)
  1101.                                         {
  1102.                                                 const CompactSpanGrid::Span& span = m_spanGrid.GetSpan(index + s);
  1103.                                                 const uint16 orig = m_distances[index + s];
  1104.  
  1105.                                                 if (orig > threshold)
  1106.                                                 {
  1107.                                                         const size_t top = span.bottom + span.height;
  1108.                                                         size_t accum = orig;
  1109.  
  1110.                                                         for (size_t n = 0; n < 8; ++n)
  1111.                                                         {
  1112.                                                                 const size_t nx = x + NeighbourOffset_TileGenerator[n][0];
  1113.                                                                 const size_t ny = y + NeighbourOffset_TileGenerator[n][1];
  1114.  
  1115.                                                                 size_t nindex;
  1116.                                                                 if (m_spanGrid.GetSpanAt(nx, ny, top, climbableVoxelCount, nindex))
  1117.                                                                         accum += m_distances[nindex];
  1118.                                                                 else
  1119.                                                                         accum += orig;
  1120.                                                         }
  1121.  
  1122.                                                         const uint16 c = static_cast<uint16>((accum + 5) / 9);          // round
  1123.                                                         m_labels[index + s] = c;
  1124.                                                 }
  1125.                                                 else
  1126.                                                         m_labels[index + s] = orig;
  1127.                                         }
  1128.                                 }
  1129.                         }
  1130.                 }
  1131.  
  1132.                 if ((i & 1) == 0)
  1133.                         m_labels.swap(m_distances);
  1134.         }
  1135.  
  1136.         m_profiler.StopTimer(Blur);
  1137. }
  1138.  
  1139. struct StreamElement
  1140. {
  1141.         StreamElement(size_t _x, size_t _y, size_t _span)
  1142.                 : x(static_cast<uint16>(_x))
  1143.                 , y(static_cast<uint16>(_y))
  1144.                 , span(_span)
  1145.         {}
  1146.  
  1147.         uint16 x;
  1148.         uint16 y;
  1149.         size_t span;
  1150.  
  1151.         bool operator==(const StreamElement& other) const
  1152.         {
  1153.                 return (x == other.x) && (y == other.y) && (span == other.span);
  1154.         }
  1155.  
  1156.         bool operator<(const StreamElement& other) const
  1157.         {
  1158.                 if (x == other.x)
  1159.                 {
  1160.                         if (y == other.y)
  1161.                                 return (span < other.span);
  1162.                         return (y < other.y);
  1163.                 }
  1164.  
  1165.                 return x < other.x;
  1166.         }
  1167. };
  1168.  
  1169. typedef std::vector<StreamElement> LinearStream;
  1170.  
  1171. size_t RunStream(const CompactSpanGrid& spanGrid, size_t climbableVoxelCount, LinearStream& unexplored,
  1172.                  const StreamElement& first, LinearStream& stream, const uint16* data, size_t erosion, uint16* labels)
  1173. {
  1174.         stream.clear();
  1175.         stream.push_back(first);
  1176.  
  1177.         unexplored.clear();
  1178.         unexplored.push_back(first);
  1179.  
  1180.         while (!unexplored.empty())
  1181.         {
  1182.                 const StreamElement y = unexplored.back();
  1183.                 unexplored.pop_back();
  1184.  
  1185.                 const size_t yx = y.x;
  1186.                 const size_t yy = y.y;
  1187.  
  1188.                 const CompactSpanGrid::Span& yspan = spanGrid.GetSpan(first.span);
  1189.                 const size_t ytop = yspan.bottom + yspan.height;
  1190.  
  1191.                 size_t minimum = erosion;
  1192.                 bool bfirst = true;
  1193.  
  1194.                 while (bfirst)
  1195.                 {
  1196.                         for (size_t n = 0; n < 4; ++n)
  1197.                         {
  1198.                                 size_t nx = yx + NeighbourOffset_TileGenerator[n][0];
  1199.                                 size_t ny = yy + NeighbourOffset_TileGenerator[n][1];
  1200.  
  1201.                                 size_t nindex;
  1202.                                 if (spanGrid.GetSpanAt(nx, ny, ytop, climbableVoxelCount, nindex))
  1203.                                 {
  1204.                                         uint16 label = labels[nindex];
  1205.  
  1206.                                         if (!IsBorderLabel(label))
  1207.                                         {
  1208.                                                 uint16 ndata = data[nindex];
  1209.                                                 if (ndata > minimum)
  1210.                                                         minimum = ndata;
  1211.                                         }
  1212.                                 }
  1213.                         }
  1214.  
  1215.                         size_t zx = ~0ul;
  1216.                         size_t zy = ~0ul;
  1217.                         size_t zspan = 0;
  1218.  
  1219.                         for (size_t n = 0; n < 4; ++n)
  1220.                         {
  1221.                                 const size_t nx = yx + NeighbourOffset_TileGenerator[n][0];
  1222.                                 const size_t ny = yy + NeighbourOffset_TileGenerator[n][1];
  1223.  
  1224.                                 size_t nindex;
  1225.                                 if (spanGrid.GetSpanAt(nx, ny, ytop, climbableVoxelCount, nindex))
  1226.                                 {
  1227.                                         uint16 label = labels[nindex];
  1228.  
  1229.                                         if (!IsBorderLabel(label))
  1230.                                         {
  1231.                                                 uint16 ndata = data[nindex];
  1232.  
  1233.                                                 if (data[nindex] == minimum)
  1234.                                                 {
  1235.                                                         const StreamElement probe(nx, ny, nindex);
  1236.  
  1237.                                                         if (std::find(stream.begin(), stream.end(), probe) == stream.end())
  1238.                                                         {
  1239.                                                                 zx = nx;
  1240.                                                                 zy = ny;
  1241.                                                                 zspan = nindex;
  1242.                                                                 break;
  1243.                                                         }
  1244.                                                 }
  1245.                                         }
  1246.                                 }
  1247.                         }
  1248.  
  1249.                         if (zx == ~0ul)
  1250.                                 break;
  1251.  
  1252.                         if (IsLabelValid(labels[zspan]))
  1253.                                 return labels[zspan];
  1254.                         else
  1255.                         {
  1256.                                 if (data[zspan] > data[y.span])
  1257.                                 {
  1258.                                         unexplored.clear();
  1259.                                         bfirst = false;
  1260.                                 }
  1261.  
  1262.                                 stream.push_back(StreamElement(zx, zy, zspan));
  1263.                                 unexplored.push_back(StreamElement(zx, zy, zspan));
  1264.                         }
  1265.                 }
  1266.         }
  1267.  
  1268.         return CTileGenerator::NoLabel;
  1269. }
  1270.  
  1271. void CTileGenerator::PaintBorder(uint16* data, size_t borderH, size_t borderV)
  1272. {
  1273.         const size_t width = m_spanGrid.GetWidth();
  1274.         const size_t height = m_spanGrid.GetHeight();
  1275.  
  1276.         if (borderH)
  1277.         {
  1278.                 for (size_t y = 0; y < height; ++y)
  1279.                 {
  1280.                         for (size_t b = 0; b < 2; ++b)
  1281.                         {
  1282.                                 size_t xoffset = b * (width - borderH);
  1283.  
  1284.                                 for (size_t x = 0; x < borderH; ++x)
  1285.                                 {
  1286.                                         if (const CompactSpanGrid::Cell cell = m_spanGrid.GetCell(x + xoffset, y))
  1287.                                         {
  1288.                                                 const size_t index = cell.index;
  1289.                                                 const size_t count = cell.count;
  1290.  
  1291.                                                 for (size_t s = 0; s < count; ++s)
  1292.                                                 {
  1293.                                                         data[index + s] |= BorderLabelH;
  1294.                                                 }
  1295.                                         }
  1296.                                 }
  1297.                         }
  1298.                 }
  1299.  
  1300.                 size_t hwidth = width - borderH;
  1301.  
  1302.                 for (size_t b = 0; b < 2; ++b)
  1303.                 {
  1304.                         const size_t yoffset = b * (height - borderH);
  1305.  
  1306.                         for (size_t y = 0; y < borderH; ++y)
  1307.                         {
  1308.                                 for (size_t x = borderH; x < hwidth; ++x)
  1309.                                 {
  1310.                                         if (const CompactSpanGrid::Cell cell = m_spanGrid.GetCell(x, y + yoffset))
  1311.                                         {
  1312.                                                 const size_t index = cell.index;
  1313.                                                 const size_t count = cell.count;
  1314.  
  1315.                                                 for (size_t s = 0; s < count; ++s)
  1316.                                                 {
  1317.                                                         data[index + s] |= BorderLabelH;
  1318.                                                 }
  1319.                                         }
  1320.                                 }
  1321.                         }
  1322.                 }
  1323.         }
  1324.  
  1325.         if (borderV)
  1326.         {
  1327.                 const size_t maxTop = borderV + Top(m_params);
  1328.  
  1329.                 for (size_t y = 0; y < height; ++y)
  1330.                 {
  1331.                         for (size_t x = 0; x < width; ++x)
  1332.                         {
  1333.                                 if (const CompactSpanGrid::Cell cell = m_spanGrid.GetCell(x, y))
  1334.                                 {
  1335.                                         const size_t index = cell.index;
  1336.                                         const size_t count = cell.count;
  1337.  
  1338.                                         for (size_t s = 0; s < count; ++s)
  1339.                                         {
  1340.                                                 CompactSpanGrid::Span& span = m_spanGrid.GetSpan(index + s);
  1341.                                                 const uint16 top = span.bottom + span.height;
  1342.  
  1343.                                                 // TODO pavloi 2016.03.15: top below borderV is OK. What about top >= maxTop? I suppose maxTop should like gridDepth,
  1344.                                                 // if one would exist, i.e. it is (8meters / voxelSize.z) of normal tile + borderV of extended tile,
  1345.                                                 // an actual size of voxelized volume).
  1346.                                                 // How top of voxel could be above voxelized volume? Isn't it true just for a voxels with top on volume
  1347.                                                 // border? What about voxels between volume top and tile top (upper borderV)? I think, they will not be
  1348.                                                 // marked as BorderLabelV.
  1349.                                                 if ((top < borderV) || (top >= maxTop))
  1350.                                                         data[index + s] |= BorderLabelV;
  1351.                                         }
  1352.                                 }
  1353.                         }
  1354.                 }
  1355.         }
  1356. }
  1357.  
  1358. real_t DistVertexToLineSq(int x, int y, int z, int ax, int ay, int az, int bx, int by, int bz)
  1359. {
  1360.         const Vec3i diff(x - ax, y - ay, z - az);
  1361.         const Vec3i dir(bx - ax, by - ay, bz - az);
  1362.         const int t = diff.dot(dir);
  1363.  
  1364.         if (t > 0)
  1365.         {
  1366.                 const int lenSq = dir.len2();
  1367.  
  1368.                 if (t >= lenSq)
  1369.                 {
  1370.                         const real_t lenSq_t((diff - dir).len2());
  1371.                         return lenSq_t >= 0 ? lenSq_t : real_t::max();
  1372.                 }
  1373.                 else
  1374.                 {
  1375.                         const vector3_t diff_t(diff);
  1376.                         const vector3_t dir_t(dir);
  1377.                         const real_t lenSq_t = (diff_t - (dir_t * real_t::fraction(t, lenSq))).lenSq();
  1378.                         return lenSq_t >= 0 ? lenSq_t : real_t::max();
  1379.                 }
  1380.         }
  1381.  
  1382.         const real_t lenSq_t(diff.len2());
  1383.         return lenSq_t >= 0 ? lenSq_t : real_t::max();
  1384. }
  1385.  
  1386. real_t DistVertexToLineSq(int x, int y, int ax, int ay, int bx, int by)
  1387. {
  1388.         return DistVertexToLineSq(x, y, 0, ax, ay, 0, bx, by, 0);
  1389. }
  1390.  
  1391. const real_t AddContourVertexThreshold(real_t::fraction(15, 1000));
  1392.  
  1393. void CTileGenerator::AddContourVertex(const ContourVertex& contourVertex, Region& region, Contour& contour) const
  1394. {
  1395.         if ((contour.size() < 2) || !ContourVertexRemovable(contour.back()))
  1396.         {
  1397.                 contour.push_back(contourVertex);
  1398.         }
  1399.         else
  1400.         {
  1401.                 ContourVertex& middle = contour.back();
  1402.                 const ContourVertex& left = contour[contour.size() - 2];
  1403.  
  1404.                 real_t distSq = DistVertexToLineSq(middle.x, middle.y, middle.z, left.x, left.y, left.z,
  1405.                                                    contourVertex.x, contourVertex.y, contourVertex.z);
  1406.  
  1407.                 if (distSq <= AddContourVertexThreshold)
  1408.                 {
  1409. #if DEBUG_MNM_GATHER_EXTRA_CONTOUR_VERTEX_INFO
  1410.                         m_debugDiscardedVertices.push_back(middle);
  1411. #endif
  1412.                         middle = contourVertex;
  1413.                 }
  1414.                 else
  1415.                 {
  1416.                         contour.push_back(contourVertex);
  1417.                 }
  1418.         }
  1419.  
  1420.         if (contourVertex.flags & ContourVertex::TileBoundary)
  1421.                 region.flags |= Region::TileBoundary;
  1422.  
  1423.         if (contourVertex.flags & ContourVertex::TileBoundaryV)
  1424.                 region.flags |= Region::TileBoundaryV;
  1425. }
  1426.  
  1427. bool CTileGenerator::GatherSurroundingInfo(const Vec2i& vertex, const Vec2i& direction, const uint16 top,
  1428.                                            const uint16 climbableVoxelCount, size_t& height, SurroundingSpanInfo& left, SurroundingSpanInfo& front,
  1429.                                            SurroundingSpanInfo& frontLeft) const
  1430. {
  1431.         Vec2i external = vertex + direction;
  1432.         bool result = false;
  1433.  
  1434.         height = top;
  1435.  
  1436.         size_t index;
  1437.         if (m_spanGrid.GetSpanAt(external.x, external.y, top, climbableVoxelCount, index))
  1438.         {
  1439.                 const CompactSpanGrid::Span& span = m_spanGrid.GetSpan(index);
  1440.                 maximize<size_t>(height, span.bottom + span.height);
  1441.  
  1442.                 front.label = m_labels[index];
  1443.                 front.flags = span.flags;
  1444.                 front.index = index;
  1445.                 result = true;
  1446.         }
  1447.  
  1448.         external = vertex + direction + direction.rot90ccw();
  1449.         if (m_spanGrid.GetSpanAt(external.x, external.y, top, climbableVoxelCount, index))
  1450.         {
  1451.                 const CompactSpanGrid::Span& span = m_spanGrid.GetSpan(index);
  1452.                 maximize<size_t>(height, span.bottom + span.height);
  1453.  
  1454.                 frontLeft.label = m_labels[index];
  1455.                 frontLeft.flags = span.flags;
  1456.                 frontLeft.index = index;
  1457.  
  1458.                 result = true;
  1459.         }
  1460.  
  1461.         external = vertex + direction.rot90ccw();
  1462.         if (m_spanGrid.GetSpanAt(external.x, external.y, top, climbableVoxelCount, index))
  1463.         {
  1464.                 const CompactSpanGrid::Span& span = m_spanGrid.GetSpan(index);
  1465.                 maximize<size_t>(height, span.bottom + span.height);
  1466.  
  1467.                 left.label = m_labels[index];
  1468.                 left.flags = span.flags;
  1469.                 left.index = index;
  1470.                 result = true;
  1471.         }
  1472.  
  1473.         return result;
  1474. }
  1475.  
  1476. void CTileGenerator::DetermineContourVertex(const Vec2i& vertex, const Vec2i& direction, const uint16 top,
  1477.                                             const uint16 climbableVoxelCount, ContourVertex& contourVertex, const bool bInternalContour, SContourVertexDebugInfo* pDebugInfo) const
  1478. {
  1479.         const size_t xoffs = (direction.x == 1) | (direction.y == -1);
  1480.         const size_t yoffs = (direction.y == 1) | (direction.x == 1);
  1481.  
  1482.         const size_t cx = vertex.x + xoffs;
  1483.         const size_t cy = vertex.y + yoffs;
  1484.         size_t cz = top;
  1485.  
  1486.         bool internalBorderV = false;
  1487.         {
  1488.                 size_t index;
  1489.                 // TODO pavloi 2016.03.15: can't we pass index in this function instead searching for it again?
  1490.  
  1491.                 // TODO pavloi 2016.03.21: how current vertex can ever be BorderLabelV? Any border voxels are unwalkable
  1492.                 // Answer: hole contours are actually walk on unwalkable spans. If hole is close to broderV, then the
  1493.                 // contour can walk into borderV span.
  1494.                 if (m_spanGrid.GetSpanAt(vertex.x, vertex.y, top, climbableVoxelCount, index))
  1495.                         internalBorderV = (m_labels[index] & BorderLabelV) != 0;
  1496.  
  1497.                 assert((internalBorderV && bInternalContour) || !internalBorderV);
  1498.         }
  1499.  
  1500.         // NOTE pavloi 2016.03.15: either we above lower borderV, or we're hitting an upper borderV.
  1501.         // When this assert can be false? If we're below lower borderV, then we should have BorderLabelV anyway. An additional consistency check?
  1502.         assert((top >= BorderSizeV(m_params)) || internalBorderV);
  1503.  
  1504.         SurroundingSpanInfo front(NoLabel, ~0ul, NotWalkable);
  1505.         SurroundingSpanInfo frontLeft(NoLabel, ~0ul, NotWalkable);
  1506.         SurroundingSpanInfo left(NoLabel, ~0ul, NotWalkable);
  1507.  
  1508.         const size_t borderV = BorderSizeV(m_params);
  1509.         // TODO pavloi 2016.03.15: in TraceContour() we alread asses these neighbours. Maybe we can store
  1510.         // their span indices, so we don't have to search for them again. But it will require more memory to store Tracer.
  1511.         GatherSurroundingInfo(vertex, direction, top, climbableVoxelCount, cz, left, front, frontLeft);
  1512.         minimize(cz, borderV + Top(m_params));
  1513.  
  1514.         size_t flags = 0;
  1515.  
  1516.         // TODO pavloi 2016.03.15: erosion code is repeated again
  1517.         const size_t erosion = m_params.flags & Params::NoErosion ? 0 : m_params.agent.radius * 2;
  1518.  
  1519.         // Order of bits (left->frontLeft->front) is important - a clock-wise neighbours. And it's also the same as indexing of corners table.
  1520.         size_t walkableBit = 0;
  1521.         walkableBit |= (size_t)((((left.flags & NotWalkable) == 0) && (m_distances[left.index] >= erosion)) ? 1 : 0) << 0;
  1522.         walkableBit |= (size_t)((((frontLeft.flags & NotWalkable) == 0) && (m_distances[frontLeft.index] >= erosion)) ? 1 : 0) << 1;
  1523.         walkableBit |= (size_t)((((front.flags & NotWalkable) == 0) && (m_distances[front.index] >= erosion)) ? 1 : 0) << 2;
  1524.  
  1525.         size_t borderBitH = 0;
  1526.         borderBitH |= (size_t)((left.label & BorderLabelH) ? 1 : 0) << 0;
  1527.         borderBitH |= (size_t)((frontLeft.label & BorderLabelH) ? 1 : 0) << 1;
  1528.         borderBitH |= (size_t)((front.label & BorderLabelH) ? 1 : 0) << 2;
  1529.  
  1530.         size_t borderBitV = 0;
  1531.         borderBitV |= (size_t)((left.label & BorderLabelV) ? 1 : 0) << 0;
  1532.         borderBitV |= (size_t)((frontLeft.label & BorderLabelV) ? 1 : 0) << 1;
  1533.         borderBitV |= (size_t)((front.label & BorderLabelV) ? 1 : 0) << 2;
  1534.  
  1535.         const size_t borderBit = borderBitH | borderBitV;
  1536.  
  1537.         const NeighbourClassification lclass = ClassifyNeighbour(left, erosion, BorderLabelV | BorderLabelH);
  1538.         const NeighbourClassification flclass = ClassifyNeighbour(frontLeft, erosion, BorderLabelV | BorderLabelH);
  1539.         const NeighbourClassification fclass = ClassifyNeighbour(front, erosion, BorderLabelV | BorderLabelH);
  1540.  
  1541. #if DEBUG_MNM_GATHER_EXTRA_CONTOUR_VERTEX_INFO
  1542.         IF_UNLIKELY (pDebugInfo)
  1543.         {
  1544.                 pDebugInfo->lclass = lclass;
  1545.                 pDebugInfo->flclass = flclass;
  1546.                 pDebugInfo->fclass = fclass;
  1547.                 pDebugInfo->walkableBit = static_cast<uint8>(walkableBit);
  1548.                 pDebugInfo->borderBitH = static_cast<uint8>(borderBitH);
  1549.                 pDebugInfo->borderBitV = static_cast<uint8>(borderBitV);
  1550.                 pDebugInfo->internalBorderV = internalBorderV;
  1551.         }
  1552. #endif
  1553.         // horizontal border
  1554.         {
  1555.                 if (IsCornerVertex(cx, cy))
  1556.                 {
  1557.                         flags |= ContourVertex::TileBoundary;
  1558.                         DebugAddContourVertexUnremovableReason(pDebugInfo, "TileCornerH");
  1559.                 }
  1560.                 else
  1561.                 {
  1562.                         const bool boundary = IsBoundaryVertex(cx, cy);
  1563.  
  1564.                         if (boundary)
  1565.                         {
  1566.                                 const bool frontBoundary = IsBoundaryCell(vertex.x + direction.x, vertex.y + direction.y)
  1567.                                                            || IsBorderCell(vertex.x + direction.x, vertex.y + direction.y);
  1568.                                 const bool connection = (borderBitH == 7) && walkableBit;
  1569.  
  1570.                                 if (frontBoundary && connection)
  1571.                                 {
  1572.                                         flags |= ContourVertex::TileBoundary;
  1573.                                         DebugAddContourVertexUnremovableReason(pDebugInfo, "BndH");
  1574.                                 }
  1575.  
  1576.                                 if (s_CornerTable[lclass][flclass][fclass])
  1577.                                 {
  1578.                                         flags |= ContourVertex::Unremovable;
  1579.                                         DebugAddContourVertexUnremovableReason(pDebugInfo, "BndH CornerTbl");
  1580.                                 }
  1581.                                 else if ((borderBit == 7) && (borderBitH && borderBitV))
  1582.                                 {
  1583.                                         flags |= ContourVertex::Unremovable;
  1584.                                         DebugAddContourVertexUnremovableReason(pDebugInfo, "BndH Border");
  1585.                                 }
  1586.                         }
  1587.                 }
  1588.         }
  1589.  
  1590.         // vertical border
  1591.         {
  1592.                 if (borderBitV || internalBorderV)
  1593.                 {
  1594.                         flags |= ContourVertex::TileBoundaryV;
  1595.                         DebugAddContourVertexUnremovableReason(pDebugInfo, "BndV");
  1596.  
  1597.                         if (!internalBorderV)
  1598.                         {
  1599.                                 if (s_CornerTable[lclass][flclass][fclass])
  1600.                                 {
  1601.                                         flags |= ContourVertex::Unremovable;
  1602.                                         DebugAddContourVertexUnremovableReason(pDebugInfo, "BndV CornerTbl");
  1603.                                 }
  1604.                                 else if ((borderBit == 7) && (borderBitH && borderBitV))
  1605.                                 {
  1606.                                         flags |= ContourVertex::Unremovable;
  1607.                                         DebugAddContourVertexUnremovableReason(pDebugInfo, "BndV Border");
  1608.                                 }
  1609.                                 // If neighbours are are actually belong to different borders.
  1610.                                 else if (borderBitH & ((borderBitV << 1) | (borderBitV >> 1)))
  1611.                                 {
  1612.                                         flags |= ContourVertex::Unremovable;
  1613.                                         DebugAddContourVertexUnremovableReason(pDebugInfo, "BndV BorderChange");
  1614.                                 }
  1615.                         }
  1616.                 }
  1617.  
  1618.                 if (flags & ContourVertex::TileBoundaryV)
  1619.                 {
  1620.                         if (cz < borderV + Top(m_params))
  1621.                                 cz = borderV;
  1622.                 }
  1623.         }
  1624.  
  1625.         const uint8 pinchTableMask = bInternalContour ? PinchCornerTable::eInt : PinchCornerTable::eExt;
  1626.         if (PinchCornerTable::s_PinchCornerTable[lclass][flclass][fclass] & pinchTableMask)
  1627.         {
  1628.                 flags |= ContourVertex::Unremovable;
  1629.                 DebugAddContourVertexUnremovableReason(pDebugInfo, "Pinch");
  1630.         }
  1631.  
  1632.         contourVertex.x = static_cast<uint16>(cx);
  1633.         contourVertex.y = static_cast<uint16>(cy);
  1634.         contourVertex.z = static_cast<uint16>(cz);
  1635.         contourVertex.flags = static_cast<uint16>(flags);
  1636. }
  1637.  
  1638. void CTileGenerator::AssessNeighbour(NeighbourInfo& info, size_t erosion, size_t climbableVoxelCount)
  1639. {
  1640.         // TODO pavloi 2016.03.15: erosion is not used.
  1641.         if (info.isValid = m_spanGrid.GetSpanAt(info.pos.x, info.pos.y, info.top, climbableVoxelCount, info.index))
  1642.         {
  1643.                 const CompactSpanGrid::Span& span = m_spanGrid.GetSpan(info.index);
  1644.                 info.top = (span.bottom + span.height);
  1645.                 info.label = m_labels[info.index];
  1646.                 info.paint = m_paint[info.index];
  1647.         }
  1648. }
  1649.  
  1650. void CTileGenerator::TraceContour(CTileGenerator::TracerPath& path, const Tracer& start, size_t erosion, size_t climbableVoxelCount, const NeighbourInfoRequirements& contourReq)
  1651. {
  1652.         // TODO pavloi 2016.03.15: erosion is not used in AssessNeighbour and so is not used here.
  1653.  
  1654.         Tracer tracer = start;
  1655.         path.steps.clear();
  1656.         path.steps.reserve(2048);
  1657.         path.turns = 0;
  1658.  
  1659.         do
  1660.         {
  1661.                 tracer.bPinchPoint = false;
  1662.  
  1663.                 // Check if the tracer path can turn left(next:front-left), carry on(next:front) else we rotate.
  1664.                 NeighbourInfo left(tracer.GetLeft());
  1665.                 NeighbourInfo frontLeft(tracer.GetFrontLeft());
  1666.                 NeighbourInfo front(tracer.GetFront());
  1667.  
  1668.                 AssessNeighbour(left, erosion, climbableVoxelCount);
  1669.                 AssessNeighbour(frontLeft, erosion, climbableVoxelCount);
  1670.                 AssessNeighbour(front, erosion, climbableVoxelCount);
  1671.  
  1672.                 if (left.Check(contourReq))
  1673.                 {
  1674.                         // Shouldn't ever happen... Sidle over and close you eyes...
  1675.                         // NOTE pavloi 2016.03.15: I suppose it's not possible, because we check grid in positive X direction,
  1676.                         // so every time a start should have an invalid span to the left, or it is already a part of different
  1677.                         // region, so this function was not even called.
  1678.                         CRY_ASSERT(false);
  1679.                         tracer.SetPos(left);
  1680.                         tracer.indexIn = left.index;
  1681.                         tracer.indexOut = left.index;
  1682.                 }
  1683.                 else if (front.Check(contourReq))
  1684.                 {
  1685.                         if (frontLeft.Check(contourReq))
  1686.                         {
  1687.                                 // We can turn left!
  1688.                                 tracer.SetPos(frontLeft);
  1689.                                 tracer.TurnLeft();
  1690.                                 tracer.indexIn = frontLeft.index;
  1691.                                 tracer.indexOut = left.index;
  1692.                                 path.turns--;
  1693.                         }
  1694.                         else
  1695.                         {
  1696.                                 // We can go forward!
  1697.                                 tracer.SetPos(front);
  1698.                                 tracer.indexIn = front.index;
  1699.                                 tracer.indexOut = frontLeft.index;
  1700.                                 // TODO pavloi 2016.03.15:  even if frontLeft is invalid?
  1701.                         }
  1702.                 }
  1703.                 else
  1704.                 {
  1705.                         if (frontLeft.Check(contourReq))
  1706.                         {
  1707.                                 // We could have moved diagonally here...
  1708.                                 // Mark the vert as pinch point.
  1709.                                 tracer.bPinchPoint = true;
  1710.                         }
  1711.  
  1712.                         // Turn right.
  1713.                         tracer.TurnRight();
  1714.                         tracer.indexOut = front.index;
  1715.                         path.turns++;
  1716.  
  1717.                         // TODO pavloi 2016.03.15: even if front is invalid?
  1718.                 }
  1719.  
  1720.                 // Add tracer to the path.
  1721.                 path.steps.push_back(tracer);
  1722.  
  1723.         }
  1724.         while (tracer != start);
  1725. }
  1726.  
  1727. int CTileGenerator::LabelTracerPath(const CTileGenerator::TracerPath& path, size_t climbableVoxelCount, Region& region, Contour& contour, const uint16 internalLabel, const uint16 internalLabelFlags, const uint16 externalLabel)
  1728. {
  1729.         const int numSteps = path.steps.size();
  1730.         contour.reserve(numSteps);
  1731.  
  1732.         for (int i = numSteps - 1, j = 0; j < numSteps; i = j++)
  1733.         {
  1734.                 const Tracer& curr = path.steps[i];
  1735.                 const Tracer& next = path.steps[j];
  1736.  
  1737.                 ContourVertex vertex;
  1738.  
  1739.                 SContourVertexDebugInfo* pDebugInfo = nullptr;
  1740. #if DEBUG_MNM_GATHER_EXTRA_CONTOUR_VERTEX_INFO
  1741.                 IF_UNLIKELY (m_params.flags & Params::DebugInfo)
  1742.                 {
  1743.                         m_debugContourVertexDebugInfos.emplace_back();
  1744.                         SContourVertexDebugInfo& debugInfo = m_debugContourVertexDebugInfos.back();
  1745.                         pDebugInfo = &debugInfo;
  1746.                         vertex.debugInfoIndex = m_debugContourVertexDebugInfos.size() - 1;
  1747.                         debugInfo.tracer = curr;
  1748.                         debugInfo.tracerIndex = i;
  1749.                 }
  1750. #endif
  1751.  
  1752.                 const bool bInternalContour = (internalLabelFlags & InternalContour) != 0;
  1753.  
  1754.                 // Add a vertex at each point.
  1755.                 DetermineContourVertex(Vec2i(curr.pos), curr.GetDir(), curr.pos.z, static_cast<uint16>(climbableVoxelCount), *&vertex, bInternalContour, pDebugInfo);
  1756.  
  1757.                 // Get the paint values for the current neighbour and the next neighbour. If they don't match then we must have a vert.
  1758.                 const bool bImportantVert = (m_paint[curr.indexOut] != m_paint[next.indexOut]);
  1759.                 if (bImportantVert)
  1760.                 {
  1761.                         vertex.flags |= ContourVertex::Unremovable;
  1762.                         DebugAddContourVertexUnremovableReason(pDebugInfo, "Paint change");
  1763.                 }
  1764.                 if (next.bPinchPoint)
  1765.                 {
  1766.                         if (!(vertex.flags & ContourVertex::Unremovable))
  1767.                         {
  1768.                                 // NOTE pavloi 2016.06.15: since pinch contour table works for both external and
  1769.                                 // internal contours, this should never happen. But just in case.
  1770.                                 AIWarning("[MNM] TileGenerator potential issue: removable pinch point, origin (%g,%g,%g), tracer (%d,%d,%d)",
  1771.                                           m_params.origin.x, m_params.origin.y, m_params.origin.z,
  1772.                                           curr.pos.x, curr.pos.y, curr.pos.z);
  1773.  
  1774.                                 vertex.flags |= ContourVertex::Unremovable;
  1775.                                 DebugAddContourVertexUnremovableReason(pDebugInfo, "next pinch");
  1776.                         }
  1777.                 }
  1778.                 AddContourVertex(vertex, region, contour);
  1779.  
  1780.                 // Apply the labels.
  1781.                 if (internalLabel != NoLabel)
  1782.                         m_labels[curr.indexIn] = internalLabel;
  1783.                 m_labels[curr.indexIn] |= internalLabelFlags;
  1784.  
  1785.                 if (externalLabel != NoLabel)
  1786.                 {
  1787.                         // Don't allow already established external contours to be stomped
  1788.                         if ((m_labels[curr.indexOut] & ExternalContour) == 0)
  1789.                                 m_labels[curr.indexOut] = externalLabel;
  1790.                 }
  1791.         }
  1792.  
  1793.         TidyUpContourEnd(contour);
  1794.         return numSteps;
  1795. }
  1796.  
  1797. inline bool IsWalkable(uint16 label, uint16 distance, size_t erosion)
  1798. {
  1799.         if ((label & (CTileGenerator::BorderLabelH | CTileGenerator::BorderLabelV)) != 0)
  1800.                 return false;
  1801.  
  1802.         if (distance < erosion)
  1803.                 return false;
  1804.  
  1805.         return true;
  1806. }
  1807.  
  1808. inline bool IsWalkable(const Vec2i& voxel, size_t& index, uint16& label, size_t top, size_t climbableVoxelCount,
  1809.                        size_t erosion, const CompactSpanGrid& spanGrid, const uint16* distances, const uint16* labels)
  1810. {
  1811.         if (!spanGrid.GetSpanAt(voxel.x, voxel.y, top, climbableVoxelCount, index))
  1812.                 return false;
  1813.  
  1814.         label = labels[index];
  1815.         if ((label & (CTileGenerator::BorderLabelH | CTileGenerator::BorderLabelV)) != 0)
  1816.                 return false;
  1817.  
  1818.         if (distances[index] < erosion)
  1819.                 return false;
  1820.  
  1821.         return true;
  1822. }
  1823.  
  1824. void CTileGenerator::TidyUpContourEnd(Contour& contour)
  1825. {
  1826.         if (contour.size() > 2)
  1827.         {
  1828.                 const ContourVertex& left = contour[contour.size() - 2];
  1829.                 const ContourVertex& middle = contour.back();
  1830.                 const ContourVertex& right = contour.front();
  1831.  
  1832.                 if ((DistVertexToLineSq(middle.x, middle.y, middle.z, left.x, left.y, left.z,
  1833.                                         right.x, right.y, right.z) <= AddContourVertexThreshold) && ContourVertexRemovable(middle))
  1834.                 {
  1835. #if DEBUG_MNM_GATHER_EXTRA_CONTOUR_VERTEX_INFO
  1836.                         m_debugDiscardedVertices.push_back(middle);
  1837. #endif
  1838.                         contour.pop_back();
  1839.                 }
  1840.         }
  1841.  
  1842.         if (contour.size() > 2)
  1843.         {
  1844.                 const ContourVertex& left = contour.back();
  1845.                 ContourVertex& middle = contour.front();
  1846.                 const ContourVertex& right = contour[1];
  1847.  
  1848.                 if ((DistVertexToLineSq(middle.x, middle.y, middle.z, left.x, left.y, left.z,
  1849.                                         right.x, right.y, right.z) <= AddContourVertexThreshold) && ContourVertexRemovable(middle))
  1850.                 {
  1851. #if DEBUG_MNM_GATHER_EXTRA_CONTOUR_VERTEX_INFO
  1852.                         m_debugDiscardedVertices.push_back(middle);
  1853. #endif
  1854.                         middle = left;
  1855.                         contour.pop_back();
  1856.                 }
  1857.         }
  1858. }
  1859.  
  1860. uint16 CTileGenerator::GetPaintVal(size_t x, size_t y, size_t z, size_t index, size_t borderH, size_t borderV, size_t erosion)
  1861. {
  1862.         // TODO pavloi 2016.03.15: there is already a function bool IsWalkable(uint16 label, uint16 distance, size_t erosion)
  1863.         // which returns false exactly when we apply BadPaint here.
  1864.  
  1865.         if (m_distances[index] < erosion)
  1866.                 return BadPaint;
  1867.  
  1868.         // TODO pavloi 2016.03.15: if we suppose, that caller is properly written and never passes coords in borderH zone,
  1869.         // then this check for BorderLabelH should never happen. But BorderLabelV could for upper border zone.
  1870.         if (m_labels[index] & (CTileGenerator::BorderLabelH | CTileGenerator::BorderLabelV))
  1871.                 return BadPaint;
  1872.  
  1873.         return OkPaintStart;
  1874. }
  1875.  
  1876. void CTileGenerator::CalcPaintValues()
  1877. {
  1878.         // Adds the "paint" values to each voxel.
  1879.         // Different paint values represent different walkable regions that should NOT be merged.
  1880.         // We can add surface type filtering in here too.
  1881.  
  1882.         // NOTE pavloi 2016.03.15: this was integrated from HF2 (Christian is reviewer).
  1883.         // m_paint effectively contains BadPaint or OkPaintStart (and some NoPaint in border zones).
  1884.         // My understanding that OkPaintStart supposed to be a starting enum value for all kinds of different markers, but is
  1885.         // not actually used in this version of code. Might have used by HF2.
  1886.  
  1887.         const size_t gridWidth = m_spanGrid.GetWidth();
  1888.         const size_t gridHeight = m_spanGrid.GetHeight();
  1889.  
  1890.         // TODO pavloi 2016.03.15: looks like m_paint is never accounted in memory profiler.
  1891.  
  1892.         m_paint.resize(m_distances.size());
  1893.         std::fill(m_paint.begin(), m_paint.end(), NoPaint);
  1894.  
  1895.         const size_t borderH = BorderSizeH(m_params);
  1896.         const size_t borderV = BorderSizeV(m_params);
  1897.         const size_t erosion = m_params.flags & Params::NoErosion ? 0 : m_params.agent.radius << 1;
  1898.         const size_t climbableVoxelCount = m_params.agent.climbableHeight;
  1899.  
  1900.         for (size_t y = borderH; y < gridHeight - borderH; ++y)
  1901.         {
  1902.                 for (size_t x = borderH; x < gridWidth - borderH; ++x)
  1903.                 {
  1904.                         const size_t spanGridIndex = (y * gridWidth) + x;
  1905.                         const CompactSpanGrid::Cell& cell = m_spanGrid[spanGridIndex];
  1906.                         for (size_t s = 0; s < cell.count; ++s)
  1907.                         {
  1908.                                 const size_t index = cell.index + s;
  1909.                                 const CompactSpanGrid::Span& span = m_spanGrid.GetSpan(index);
  1910.                                 m_paint[index] = GetPaintVal(x, y, span.bottom + span.height, index, borderH, borderV, erosion);
  1911.                         }
  1912.                 }
  1913.         }
  1914. }
  1915.  
  1916. size_t CTileGenerator::ExtractContours()
  1917. {
  1918.         m_profiler.StartTimer(ContourExtraction);
  1919.  
  1920.         const size_t gridWidth = m_spanGrid.GetWidth();
  1921.         const size_t gridHeight = m_spanGrid.GetHeight();
  1922.  
  1923.         m_labels.resize(m_distances.size());
  1924.  
  1925.         m_profiler.AddMemory(SegmentationMemory, m_labels.size() * sizeof(SpanExtraInfo::value_type));
  1926.  
  1927.         const size_t borderH = BorderSizeH(m_params);
  1928.         const size_t borderV = BorderSizeV(m_params);
  1929.  
  1930.         std::fill(m_labels.begin(), m_labels.end(), NoLabel);
  1931.         PaintBorder(&m_labels.front(), borderH, borderV);
  1932.  
  1933.         CalcPaintValues();
  1934.  
  1935.         uint16 regionCount = 0;
  1936.         m_regions.reserve(128);
  1937.  
  1938.         TracerPath path;
  1939.  
  1940.         // TODO pavloi 2016.03.15: same erosion calculated in CalcPaintValues. And it's not even required here - see
  1941.         // comments in AssessNeighbour and TraceContour.
  1942.         // Or it is required, in LabelTracerPath() - DetermineContourVertex(), where it's calcluated again.
  1943.         const size_t erosion = m_params.flags & Params::NoErosion ? 0 : m_params.agent.radius << 1;
  1944.         const size_t climbableVoxelCount = m_params.agent.climbableHeight;
  1945.  
  1946.         for (size_t y = borderH; y < gridHeight - borderH; ++y)
  1947.         {
  1948.                 for (size_t x = borderH; x < gridWidth - borderH; ++x)
  1949.                 {
  1950.                         const size_t spanGridIndex = (y * gridWidth) + x;
  1951.                         const CompactSpanGrid::Cell& cell = m_spanGrid[spanGridIndex];
  1952.                         for (size_t s = 0; s < cell.count; ++s)
  1953.                         {
  1954.                                 const size_t index = cell.index + s;
  1955.                                 const uint16 label = m_labels[index];
  1956.                                 const uint16 labelsafe = label & NoLabel;
  1957.  
  1958.                                 // TODO pavloi 2016.03.15: labels should all be set NoLabel(default value), and some with additional
  1959.                                 // bits BorderLabelH or BorderLabelV (from PaintBorder). How then this check can possibly fail?
  1960.                                 // Answer: TraceContour walks from this span to other spans. Which means, this span was potentially
  1961.                                 // visited before as a part of tracing.
  1962.  
  1963.                                 if (labelsafe != NoLabel)
  1964.                                         continue;
  1965.  
  1966.                                 const uint16 paint = m_paint[index];
  1967.  
  1968.                                 const CompactSpanGrid::Span& span = m_spanGrid.GetSpan(index);
  1969.                                 const size_t top = span.bottom + span.height;
  1970.  
  1971.                                 NeighbourInfo prev(Vec2i(x - 1, y), top);
  1972.                                 AssessNeighbour(*&prev, erosion, climbableVoxelCount);
  1973.  
  1974.                                 const uint16 prevLabelSafe = (prev.label & NoLabel);
  1975.  
  1976.                                 const bool walkable = (paint >= OkPaintStart);
  1977.                                 const bool prevwalkable = (prev.paint >= OkPaintStart);
  1978.                                 const bool bothwalkable = (walkable && prevwalkable);
  1979.                                 const bool paintcontinuation = (paint == prev.paint);
  1980.  
  1981.                                 Tracer startTracer;
  1982.                                 startTracer.pos = Vec3i(x, y, top);
  1983.                                 startTracer.dir = N;
  1984.                                 startTracer.indexIn = index;
  1985.                                 startTracer.indexOut = prev.index;
  1986.                                 startTracer.bPinchPoint = false;
  1987.  
  1988.                                 if (bothwalkable)
  1989.                                 {
  1990.                                         if (paintcontinuation)
  1991.                                         {
  1992.                                                 if (prevLabelSafe < m_regions.size())
  1993.                                                 {
  1994.                                                         // Continuation of previous region. Walk label forward.
  1995.                                                         m_labels[index] = prevLabelSafe;
  1996.                                                         Region& region = m_regions[prevLabelSafe];
  1997.                                                         ++region.spanCount;
  1998.                                                 }
  1999.                                         }
  2000.                                         else
  2001.                                         {
  2002.                                                 // Paint has changed colour. Trace the contour.
  2003.                                                 NeighbourInfoRequirements contourReq;
  2004.                                                 contourReq.paint = paint;
  2005.  
  2006.                                                 TraceContour(path, startTracer, erosion, climbableVoxelCount, contourReq);
  2007.                                                 if (path.turns > 0)
  2008.                                                 {
  2009.                                                         // Store for Debugging.
  2010.                                                         CacheTracerPath(path);
  2011.  
  2012.                                                         // Start of a new Region. Mark the inside with the new label.
  2013.                                                         const uint16 newLabel = regionCount;
  2014.                                                         m_regions.resize(++regionCount);
  2015.  
  2016.                                                         Region& region = m_regions.back();
  2017.  
  2018.                                                         region.spanCount += LabelTracerPath(path, climbableVoxelCount, region, region.contour, newLabel, ExternalContour, NoLabel);
  2019.  
  2020.                                                         // Also trace the hole contour for the previous painted colour.
  2021.                                                         if ((prev.label & ExternalContour) == 0 && (label & InternalContour) == 0)
  2022.                                                         {
  2023.                                                                 Region& holeRegion = m_regions[prevLabelSafe];
  2024.                                                                 holeRegion.holes.reserve(64);
  2025.                                                                 holeRegion.holes.resize(holeRegion.holes.size() + 1);
  2026.  
  2027.                                                                 NeighbourInfoRequirements holeReq;
  2028.                                                                 holeReq.notPaint = prev.paint;
  2029.  
  2030.                                                                 TraceContour(path, startTracer, erosion, climbableVoxelCount, holeReq);
  2031.                                                                 LabelTracerPath(path, climbableVoxelCount, holeRegion, holeRegion.holes.back(), NoLabel, InternalContour, prev.label);
  2032.  
  2033.                                                                 // Store for Debugging.
  2034.                                                                 CacheTracerPath(path);
  2035.                                                         }
  2036.                                                 }
  2037.                                                 else
  2038.                                                 {
  2039.                                                         // This is actually a hole we have discovered before we have entered the "containing" region.
  2040.                                                         // This is most likely when the hole inverts and exits the bounds of the region is within.
  2041.                                                         //CryLogAlways("Ignoring contour!");
  2042.                                                 }
  2043.                                         }
  2044.                                 }
  2045.                                 else if (walkable)
  2046.                                 {
  2047.                                         // Trace the new region
  2048.                                         NeighbourInfoRequirements contourReq;
  2049.                                         contourReq.paint = paint;
  2050.                                         TraceContour(path, startTracer, erosion, climbableVoxelCount, contourReq);
  2051.  
  2052.                                         if (path.turns > 0)
  2053.                                         {
  2054.                                                 // Store for Debugging.
  2055.                                                 CacheTracerPath(path);
  2056.  
  2057.                                                 // Just entered a new painted region. Marking the inside with the new label.
  2058.                                                 const uint16 newLabel = regionCount;
  2059.                                                 m_regions.resize(++regionCount);
  2060.  
  2061.                                                 Region& region = m_regions.back();
  2062.  
  2063.                                                 region.spanCount += LabelTracerPath(path, climbableVoxelCount, region, region.contour, newLabel, ExternalContour, NoLabel);
  2064.                                         }
  2065.                                         else
  2066.                                         {
  2067.                                                 // This is actually a hole we have discovered before we have entered the "containing" region.
  2068.                                                 // This is most likely when the hole inverts and exits the bounds of the region is within.
  2069.                                                 //CryLogAlways("Ignoring contour!");
  2070.                                         }
  2071.                                 }
  2072.                                 else if (prevwalkable)
  2073.                                 {
  2074.                                         if ((prev.label & ExternalContour) == 0 && (label & InternalContour) == 0)
  2075.                                         {
  2076.                                                 if (prevLabelSafe < m_regions.size())
  2077.                                                 {
  2078.                                                         // Just left a painted region for a hole. Trace the outer of the hole with the previous region label.
  2079.                                                         Region& holeRegion = m_regions[prevLabelSafe];
  2080.                                                         holeRegion.holes.reserve(64);
  2081.                                                         holeRegion.holes.resize(holeRegion.holes.size() + 1);
  2082.  
  2083.                                                         NeighbourInfoRequirements holeReq;
  2084.                                                         holeReq.notPaint = prev.paint;
  2085.  
  2086.                                                         TraceContour(path, startTracer, erosion, climbableVoxelCount, holeReq);
  2087.                                                         LabelTracerPath(path, climbableVoxelCount, holeRegion, holeRegion.holes.back(), NoLabel, InternalContour, prev.label);
  2088.  
  2089.                                                         // Store for Debugging.
  2090.                                                         CacheTracerPath(path);
  2091.                                                 }
  2092.                                                 else
  2093.                                                 {
  2094.                                                         //CryLogAlways("Ending unknown section.");
  2095.                                                 }
  2096.                                         }
  2097.                                 }
  2098.                         }
  2099.                 }
  2100.         }
  2101.  
  2102.         m_profiler.StopTimer(ContourExtraction);
  2103.  
  2104.         m_profiler.AddMemory(RegionMemory, m_regions.capacity() * sizeof(Region));
  2105.  
  2106.         for (size_t i = 0; i < m_regions.size(); ++i)
  2107.         {
  2108.                 const Region& region = m_regions[i];
  2109.  
  2110.                 size_t memory = region.contour.capacity() * sizeof(ContourVertex);
  2111.                 memory += region.holes.capacity() * sizeof(Contour);
  2112.  
  2113.                 for (size_t h = 0; h < region.holes.size(); ++h)
  2114.                 {
  2115.                         memory += region.holes[h].capacity() * sizeof(ContourVertex);
  2116.                 }
  2117.  
  2118.                 m_profiler.AddMemory(RegionMemory, memory);
  2119.         }
  2120.  
  2121.         if ((m_params.flags & Params::DebugInfo) == 0)
  2122.         {
  2123.                 SpanExtraInfo().swap(m_labels);
  2124.  
  2125.                 m_profiler.FreeMemory(SegmentationMemory, m_labels.capacity() * sizeof(SpanExtraInfo::value_type));
  2126.  
  2127.                 SpanExtraInfo().swap(m_distances);
  2128.  
  2129.                 m_profiler.FreeMemory(SegmentationMemory, m_distances.capacity() * sizeof(SpanExtraInfo::value_type));
  2130.         }
  2131.  
  2132.         return regionCount;
  2133. }
  2134.  
  2135. size_t CTileGenerator::InsertUniqueVertex(VertexIndexLookUp& lookUp, size_t x, size_t y, size_t z)
  2136. {
  2137.         // #MNM_TODO pavloi 2016.07.21: different vertex index lookUp, not the one from m_mesh.
  2138.         // Might lead to some duplicated vertices. It's not a big problem, just an increased memory use.
  2139.  
  2140.         enum { zmask = (1 << 11) - 1, };
  2141.         enum { xmask = (1 << 10) - 1, };
  2142.         enum { ymask = (1 << 10) - 1, };
  2143.  
  2144.         const uint32 vertexID = ((uint32)(z & zmask) << 20) | ((uint32)(x & xmask) << 10) | (y & ymask);
  2145.  
  2146.         bool inserted;
  2147.         uint16& index = *lookUp.insert(vertexID, 0, &inserted);
  2148.  
  2149.         if (inserted)
  2150.         {
  2151.                 const size_t idx = m_mesh.InsertVertex(Tile::Vertex(
  2152.                                                          Tile::Vertex::value_type(x * m_params.voxelSize.x),
  2153.                                                          Tile::Vertex::value_type(y * m_params.voxelSize.y),
  2154.                                                          Tile::Vertex::value_type(z * m_params.voxelSize.z)));
  2155.  
  2156.                 index = static_cast<uint16>(idx);
  2157.         }
  2158.  
  2159.         return index;
  2160. }
  2161.  
  2162. void CTileGenerator::FilterBadRegions(size_t minSpanCount)
  2163. {
  2164.         for (size_t i = 0; i < m_regions.size(); ++i)
  2165.         {
  2166.                 Region& region = m_regions[i];
  2167.  
  2168.                 if (((region.flags & Region::TileBoundary) == 0)
  2169.                     && ((region.flags & Region::TileBoundaryV) == 0)
  2170.                     && (region.spanCount && (region.spanCount <= minSpanCount)))
  2171.                 {
  2172.                         Region().swap(region);
  2173.                 }
  2174.         }
  2175. }
  2176.  
  2177. bool CTileGenerator::SimplifyContour(const Contour& contour, const real_t& tolerance2DSq, const real_t& tolerance3DSq, PolygonContour& poly)
  2178. {
  2179.         const size_t MaxSimplifiedCount = 2048;
  2180.         uint16 simplified[MaxSimplifiedCount];
  2181.         size_t simplifiedCount = 0;
  2182.         const size_t contourSize = contour.size();
  2183.         bool boundary = (contour.back().flags & ContourVertex::TileBoundaryV) != 0;
  2184.  
  2185.         // TODO pavloi 2016.03.15: contourSize can be bigger then MaxSimplifiedCount
  2186.  
  2187.         for (uint16 i = 0; i < contourSize; ++i)
  2188.         {
  2189.                 const ContourVertex& v = contour[i];
  2190.  
  2191.                 if (v.flags & ContourVertex::TileBoundaryV)
  2192.                 {
  2193.                         if (!boundary || !ContourVertexRemovable(v))
  2194.                                 simplified[simplifiedCount++] = i;
  2195.  
  2196.                         boundary = true;
  2197.                 }
  2198.                 else
  2199.                 {
  2200.                         if (boundary && i && (simplified[simplifiedCount - 1] != (i - 1)))
  2201.                                 simplified[simplifiedCount++] = i - 1;
  2202.  
  2203.                         if (!ContourVertexRemovable(v))
  2204.                                 simplified[simplifiedCount++] = i;
  2205.  
  2206.                         boundary = false;
  2207.                 }
  2208.         }
  2209.  
  2210.         if (simplifiedCount && (simplified[simplifiedCount - 1] != (contourSize - 1)))
  2211.         {
  2212.                 if ((contour.back().flags & ContourVertex::TileBoundaryV)
  2213.                     && ((contour.front().flags & ContourVertex::TileBoundaryV) == 0))
  2214.                 {
  2215.                         simplified[simplifiedCount++] = static_cast<uint16>(contourSize - 1);
  2216.                 }
  2217.         }
  2218.  
  2219.         if (!simplifiedCount)
  2220.         {
  2221.                 Vec3i min(std::numeric_limits<int>::max());
  2222.                 size_t minVertex = 0;
  2223.  
  2224.                 Vec3i max(std::numeric_limits<int>::min());
  2225.                 size_t maxVertex = 0;
  2226.  
  2227.                 for (size_t i = 0; i < contourSize; ++i)
  2228.                 {
  2229.                         const ContourVertex& v = contour[i];
  2230.  
  2231.                         if ((v.x < min.x) || ((v.x == min.x) && (v.y < min.y)))
  2232.                         {
  2233.                                 minVertex = i;
  2234.                                 min = Vec3i(v.x, v.y, v.z);
  2235.                         }
  2236.  
  2237.                         if ((v.x > max.x) || ((v.x == max.x) && (v.y > max.y)))
  2238.                         {
  2239.                                 maxVertex = i;
  2240.                                 max = Vec3i(v.x, v.y, v.z);
  2241.                         }
  2242.                 }
  2243.  
  2244.                 simplified[simplifiedCount++] = static_cast<uint16>(minVertex);
  2245.                 simplified[simplifiedCount++] = static_cast<uint16>(maxVertex);
  2246.         }
  2247.  
  2248.         for (size_t s0 = 0; s0 < simplifiedCount; )
  2249.         {
  2250.                 const size_t s1 = (s0 + 1) % simplifiedCount;
  2251.                 const size_t i0 = simplified[s0];
  2252.                 const size_t i1 = simplified[s1];
  2253.                 const size_t last = (i0 < i1) ? i1 : contourSize + i1;
  2254.  
  2255.                 const ContourVertex& v0 = contour[i0];
  2256.                 const ContourVertex& v1 = contour[i1];
  2257.  
  2258.                 real_t dmax2DSq = real_t::min();
  2259.                 real_t dmax3DSq = real_t::min();
  2260.                 size_t index2D = 0;
  2261.                 size_t index3D = 0;
  2262.  
  2263.                 if (v0 < v1)
  2264.                 {
  2265.                         for (size_t v = i0 + 1; v < last; ++v)
  2266.                         {
  2267.                                 const size_t vi = v % contourSize;
  2268.                                 const ContourVertex& vp = contour[vi];
  2269.                                 const real_t d3DSq = DistVertexToLineSq(vp.x, vp.y, vp.z, v0.x, v0.y, v0.z, v1.x, v1.y, v1.z);
  2270.                                 const real_t d2DSq = DistVertexToLineSq(vp.x, vp.y, v0.x, v0.y, v1.x, v1.y);
  2271.  
  2272.                                 if (d2DSq > dmax2DSq)
  2273.                                 {
  2274.                                         index2D = vi;
  2275.                                         dmax2DSq = d2DSq;
  2276.                                 }
  2277.  
  2278.                                 if (d3DSq > dmax3DSq)
  2279.                                 {
  2280.                                         index3D = vi;
  2281.                                         dmax3DSq = d3DSq;
  2282.                                 }
  2283.                         }
  2284.                 }
  2285.                 else
  2286.                 {
  2287.                         for (size_t v = last - 1; v > i0; --v)
  2288.                         {
  2289.                                 const size_t vi = v % contourSize;
  2290.                                 const ContourVertex& vp = contour[vi];
  2291.                                 const real_t d3DSq = DistVertexToLineSq(vp.x, vp.y, vp.z, v1.x, v1.y, v1.z, v0.x, v0.y, v0.z);
  2292.                                 const real_t d2DSq = DistVertexToLineSq(vp.x, vp.y, v1.x, v1.y, v0.x, v0.y);
  2293.  
  2294.                                 if (d2DSq > dmax2DSq)
  2295.                                 {
  2296.                                         index2D = vi;
  2297.                                         dmax2DSq = d2DSq;
  2298.                                 }
  2299.  
  2300.                                 if (d3DSq > dmax3DSq)
  2301.                                 {
  2302.                                         index3D = vi;
  2303.                                         dmax3DSq = d3DSq;
  2304.                                 }
  2305.                         }
  2306.                 }
  2307.  
  2308.                 size_t index = (dmax3DSq >= tolerance3DSq) ? index3D : ((dmax2DSq >= tolerance2DSq) ? index2D : ~0ul);
  2309.  
  2310.                 if (index != ~0ul)
  2311.                 {
  2312.                         assert(simplifiedCount + 1 < MaxSimplifiedCount);
  2313.                         if (simplifiedCount + 1 == MaxSimplifiedCount)
  2314.                                 break;
  2315.  
  2316.                         for (size_t k = 0, i = s0 + 1; i < simplifiedCount; ++i, ++k)
  2317.                         {
  2318.                                 simplified[simplifiedCount - k] = simplified[simplifiedCount - k - 1];
  2319.                         }
  2320.  
  2321.                         simplified[s0 + 1] = static_cast<uint16>(index);
  2322.                         ++simplifiedCount;
  2323.  
  2324.                         continue;
  2325.                 }
  2326.  
  2327.                 ++s0;
  2328.         }
  2329.  
  2330.         // Remove degenerate verts for [a,b,c] where: a==c or a==b.
  2331.         for (size_t a = (simplifiedCount - 2), b = (simplifiedCount - 1), c = 0; simplifiedCount > 2 && c < simplifiedCount; )
  2332.         {
  2333.                 const uint16 as = simplified[a];
  2334.                 const uint16 bs = simplified[b];
  2335.                 const uint16 cs = simplified[c];
  2336.  
  2337.                 const ContourVertex& av = contour[as];
  2338.                 const ContourVertex& bv = contour[bs];
  2339.                 const ContourVertex& cv = contour[cs];
  2340.  
  2341.                 if (as == bs || ((av.x == bv.x) && (av.y == bv.y) && (av.z == bv.z)))
  2342.                 {
  2343.                         // Remove b
  2344.                         if ((b + 1) < simplifiedCount)
  2345.                         {
  2346.                                 const size_t numShift = simplifiedCount - (b + 1);
  2347.                                 memmove(&simplified[b], &simplified[b + 1], sizeof(simplified[0]) * numShift);
  2348.                         }
  2349.                         simplifiedCount -= 1;
  2350.                         b = ((a + 1) % simplifiedCount);
  2351.                         c = ((a + 2) % simplifiedCount);
  2352.                 }
  2353.                 else if (as == cs || ((av.x == cv.x) && (av.y == cv.y) && (av.z == cv.z)))
  2354.                 {
  2355.                         // Remove b and c
  2356.                         if ((b + 2) < simplifiedCount)
  2357.                         {
  2358.                                 const size_t numShift = simplifiedCount - (b + 2);
  2359.                                 memmove(&simplified[b], &simplified[b + 2], sizeof(simplified[0]) * numShift);
  2360.                         }
  2361.                         simplifiedCount -= 2;
  2362.                         b = ((a + 1) % simplifiedCount);
  2363.                         c = ((a + 2) % simplifiedCount);
  2364.                 }
  2365.                 else
  2366.                 {
  2367.                         a = b;
  2368.                         b = c++;
  2369.                 }
  2370.         }
  2371.  
  2372.         if (simplifiedCount > 2)
  2373.         {
  2374.                 PolygonContour spoly;
  2375.                 spoly.reserve(simplifiedCount);
  2376.  
  2377.                 for (size_t i = 0; i < simplifiedCount; ++i)
  2378.                 {
  2379.                         const ContourVertex& cv = contour[simplified[i]];
  2380.                         spoly.push_back(PolygonVertex(cv.x, cv.y, cv.z));
  2381.                 }
  2382.  
  2383.                 poly.swap(spoly);
  2384.  
  2385.                 return true;
  2386.         }
  2387.  
  2388.         return false;
  2389. }
  2390.  
  2391. void CTileGenerator::SimplifyContours()
  2392. {
  2393.         m_profiler.StartTimer(Simplification);
  2394.  
  2395.         const real_t tolerance2DSq(7);
  2396.         const real_t tolerance3DSq(11);
  2397.  
  2398.         size_t polygonCount = 0;
  2399.  
  2400.         for (size_t r = 0; r < m_regions.size(); ++r)
  2401.         {
  2402.                 const Region& region = m_regions[r];
  2403.                 polygonCount += (region.spanCount > 0);
  2404.         }
  2405.  
  2406.         m_polygons.reserve(polygonCount);
  2407.  
  2408.         for (size_t r = 0; r < m_regions.size(); ++r)
  2409.         {
  2410.                 Region& region = m_regions[r];
  2411.                 const Contour& contour = region.contour;
  2412.  
  2413.                 if (contour.size() < 3)
  2414.                         continue;
  2415.  
  2416.                 m_polygons.resize(m_polygons.size() + 1);
  2417.                 Polygon& poly = m_polygons.back();
  2418.  
  2419.                 if (!SimplifyContour(region.contour, tolerance2DSq, tolerance3DSq, poly.contour))
  2420.                 {
  2421.                         m_polygons.pop_back();
  2422.                         continue;
  2423.                 }
  2424.  
  2425.                 if (region.holes.empty())
  2426.                         continue;
  2427.  
  2428.                 poly.holes.reserve(region.holes.size());
  2429.  
  2430.                 for (size_t h = 0; h < region.holes.size(); ++h)
  2431.                 {
  2432.                         poly.holes.resize(poly.holes.size() + 1);
  2433.                         Hole& hole = poly.holes.back();
  2434.  
  2435.                         if (!SimplifyContour(region.holes[h], tolerance2DSq, tolerance3DSq, hole.verts))
  2436.                         {
  2437.                                 poly.holes.pop_back();
  2438.                         }
  2439.                         else
  2440.                         {
  2441.                                 const size_t holeSize = hole.verts.size();
  2442.                                 Vec2i avg(ZERO);
  2443.                                 for (size_t hvi = 0; hvi < holeSize; ++hvi)
  2444.                                 {
  2445.                                         avg += Vec2i(hole.verts[hvi].x, hole.verts[hvi].y);
  2446.                                 }
  2447.                                 hole.center.x = avg.x / holeSize;
  2448.                                 hole.center.y = avg.y / holeSize;
  2449.                                 hole.rad = 0;
  2450.                                 for (size_t hvi = 0; hvi < holeSize; ++hvi)
  2451.                                 {
  2452.                                         const Vec2i hv(hole.verts[hvi].x, hole.verts[hvi].y);
  2453.                                         const int vertDist = int_ceil(sqrt_tpl((float)((hv - hole.center).GetLength2())));
  2454.                                         hole.rad = max(hole.rad, vertDist);
  2455.                                 }
  2456.                         }
  2457.                 }
  2458.         }
  2459.  
  2460.         m_profiler.StopTimer(Simplification);
  2461.  
  2462.         m_profiler.AddMemory(PolygonMemory, m_polygons.capacity() * sizeof(Polygon));
  2463.  
  2464.         for (size_t i = 0; i < m_polygons.size(); ++i)
  2465.         {
  2466.                 m_profiler.AddMemory(PolygonMemory, m_polygons[i].contour.capacity() * sizeof(PolygonContour::value_type));
  2467.                 m_profiler.AddMemory(PolygonMemory, m_polygons[i].holes.capacity() * sizeof(PolygonHoles::value_type));
  2468.  
  2469.                 for (size_t k = 0; k < m_polygons[i].holes.size(); ++k)
  2470.                 {
  2471.                         m_profiler.AddMemory(PolygonMemory, m_polygons[i].holes[k].verts.capacity() * sizeof(PolygonContour::value_type));
  2472.                 }
  2473.         }
  2474.  
  2475.         if ((m_params.flags & Params::DebugInfo) == 0)
  2476.         {
  2477.                 Regions().swap(m_regions);
  2478.  
  2479.                 m_profiler.FreeMemory(RegionMemory, m_profiler[RegionMemory].used);
  2480.         }
  2481.  
  2482.         m_profiler.AddStat(PolygonCount, m_polygons.size());
  2483. }
  2484.  
  2485. template<typename VertexTy>
  2486. inline bool IsReflex(size_t vertex, const VertexTy* vertices, size_t vertexCount)
  2487. {
  2488.         const uint16 i0 = static_cast<uint16>(vertex ? vertex - 1 : vertexCount - 1);
  2489.         const uint16 i1 = static_cast<uint16>(vertex);
  2490.         const uint16 i2 = static_cast<uint16>((vertex + 1) % vertexCount);
  2491.  
  2492.         const VertexTy& v0 = vertices[i0];
  2493.         const VertexTy& v1 = vertices[i1];
  2494.         const VertexTy& v2 = vertices[i2];
  2495.  
  2496.         int area = ((int)v1.x - (int)v0.x) * ((int)v2.y - (int)v0.y) - ((int)v1.y - (int)v0.y) * ((int)v2.x - (int)v0.x);
  2497.         return area > 0;
  2498. }
  2499.  
  2500. template<typename VertexTy>
  2501. inline bool IsReflex(size_t vertex, const VertexTy* vertices, uint16* indices, size_t indexCount)
  2502. {
  2503.         const uint16 i0 = static_cast<uint16>(vertex ? vertex - 1 : indexCount - 1);
  2504.         const uint16 i1 = static_cast<uint16>(vertex);
  2505.         const uint16 i2 = static_cast<uint16>((vertex + 1) % indexCount);
  2506.  
  2507.         const VertexTy& v0 = vertices[indices[i0]];
  2508.         const VertexTy& v1 = vertices[indices[i1]];
  2509.         const VertexTy& v2 = vertices[indices[i2]];
  2510.  
  2511.         int area = ((int)v1.x - (int)v0.x) * ((int)v2.y - (int)v0.y) - ((int)v1.y - (int)v0.y) * ((int)v2.x - (int)v0.x);
  2512.         return area > 0;
  2513. }
  2514.  
  2515. template<typename VertexTy>
  2516. bool IsEar(size_t vertex, const VertexTy* vertices, size_t vertexCount, size_t agentHeight)
  2517. {
  2518.         const uint16 i0 = static_cast<uint16>(vertex ? vertex - 1 : vertexCount - 1);
  2519.         const uint16 i1 = static_cast<uint16>(vertex);
  2520.         const uint16 i2 = static_cast<uint16>((vertex + 1) % vertexCount);
  2521.  
  2522.         const VertexTy& v0 = vertices[i0];
  2523.         const VertexTy& v1 = vertices[i1];
  2524.         const VertexTy& v2 = vertices[i2];
  2525.  
  2526.         const size_t minZ = std::min<size_t>(std::min<size_t>(v0.z, v1.z), v2.z);
  2527.         const size_t maxZ = std::max<size_t>(std::max<size_t>(v0.z, v1.z), v2.z);
  2528.  
  2529.         // Calc edges
  2530.         const int x01 = ((int)v0.x - (int)v1.x);
  2531.         const int y01 = ((int)v0.y - (int)v1.y);
  2532.         const int x12 = ((int)v1.x - (int)v2.x);
  2533.         const int y12 = ((int)v1.y - (int)v2.y);
  2534.         const int x20 = ((int)v2.x - (int)v0.x);
  2535.         const int y20 = ((int)v2.y - (int)v0.y);
  2536.  
  2537.         // Check for any point existing within the test triangle
  2538.         for (size_t k = 0; k < vertexCount; ++k)
  2539.         {
  2540.                 const VertexTy& cv = vertices[k];
  2541.                 const Vec3i p(cv.x, cv.y, cv.z);
  2542.  
  2543.                 if ((static_cast<size_t>(p.z) > maxZ + agentHeight) || (static_cast<size_t>(p.z) < minZ - 1))
  2544.                         continue;
  2545.  
  2546.                 bool e0 = ((((int)p.x - (int)v0.x) * y01 - ((int)p.y - (int)v0.y) * x01) < 0);
  2547.                 bool e1 = ((((int)p.x - (int)v1.x) * y12 - ((int)p.y - (int)v1.y) * x12) < 0);
  2548.                 bool e2 = ((((int)p.x - (int)v2.x) * y20 - ((int)p.y - (int)v2.y) * x20) < 0);
  2549.  
  2550.                 // A point has been found inside the triangle so, therefore, not an ear.
  2551.                 if (e0 && e1 && e2)
  2552.                         return false;
  2553.         }
  2554.  
  2555.         return true;
  2556. }
  2557.  
  2558. template<typename VertexTy>
  2559. bool IsEar(size_t vertex, const VertexTy* vertices, size_t vertexCount, uint16* indices, size_t indexCount,
  2560.            size_t agentHeight)
  2561. {
  2562.         const uint16 i0 = static_cast<uint16>(vertex ? vertex - 1 : indexCount - 1);
  2563.         const uint16 i1 = static_cast<uint16>(vertex);
  2564.         const uint16 i2 = static_cast<uint16>((vertex + 1) % indexCount);
  2565.  
  2566.         const VertexTy& v0 = vertices[indices[i0]];
  2567.         const VertexTy& v1 = vertices[indices[i1]<