LCOV - code coverage report
Current view: top level - source/simulation2/helpers - Rasterize.cpp (source / functions) Hit Total Coverage
Test: 0 A.D. test coverage report Lines: 0 47 0.0 %
Date: 2023-01-19 00:18:29 Functions: 0 1 0.0 %

          Line data    Source code
       1             : /* Copyright (C) 2015 Wildfire Games.
       2             :  * This file is part of 0 A.D.
       3             :  *
       4             :  * 0 A.D. is free software: you can redistribute it and/or modify
       5             :  * it under the terms of the GNU General Public License as published by
       6             :  * the Free Software Foundation, either version 2 of the License, or
       7             :  * (at your option) any later version.
       8             :  *
       9             :  * 0 A.D. is distributed in the hope that it will be useful,
      10             :  * but WITHOUT ANY WARRANTY; without even the implied warranty of
      11             :  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
      12             :  * GNU General Public License for more details.
      13             :  *
      14             :  * You should have received a copy of the GNU General Public License
      15             :  * along with 0 A.D.  If not, see <http://www.gnu.org/licenses/>.
      16             :  */
      17             : 
      18             : #include "precompiled.h"
      19             : 
      20             : #include "Rasterize.h"
      21             : 
      22             : #include "simulation2/helpers/Geometry.h"
      23             : #include "simulation2/helpers/Pathfinding.h"
      24             : 
      25           0 : void SimRasterize::RasterizeRectWithClearance(Spans& spans,
      26             :     const ICmpObstructionManager::ObstructionSquare& shape,
      27             :     entity_pos_t clearance, entity_pos_t cellSize)
      28             : {
      29             :     // A long-standing issue with the pathfinding has been that the long-range one
      30             :     // uses a AA navcell grid, while the short-range uses an accurate vector representation.
      31             :     // This means we could get paths accepted by one but not both pathfinders.
      32             :     // Since the new pathfinder, the short-range pathfinder's representation was usually
      33             :     // encompassing the rasterisation of the long-range one for a building.
      34             :     // This means that we could never get quite as close as the long-range pathfinder wanted.
      35             :     // This could mean units tried going through impassable paths.
      36             :     // To fix this, we need to make sure that the short-range pathfinder is always mostly
      37             :     // included in the rasterisation. The easiest way is to rasterise more, thus this variable
      38             :     // Since this is a very complicated subject, check out logs on 31/10/2015 for more detailled info.
      39             :     // or ask wraitii about it.
      40             :     // If the short-range pathfinder is sufficiently changed, this could become unnecessary and thus removed.
      41             :     // A side effect is that the basic clearance has been set to 0.8, so removing this constant should be done
      42             :     // in parallel with setting clearance back to 1 for the default passability class (though this isn't strictly necessary).
      43             :     // Also: the code detecting foundation obstruction in CcmpObstructionManager had to be changed similarly.
      44           0 :     entity_pos_t rasterClearance = clearance + Pathfinding::CLEARANCE_EXTENSION_RADIUS;
      45             : 
      46             :     // Get the bounds of cells that might possibly be within the shape
      47             :     // (We'll then test each of those cells more precisely)
      48           0 :     CFixedVector2D shapeHalfSize(CFixedVector2D(shape.hw, shape.hh));
      49           0 :     CFixedVector2D halfSize(shape.hw + rasterClearance, shape.hh + rasterClearance);
      50           0 :     CFixedVector2D halfBound = Geometry::GetHalfBoundingBox(shape.u, shape.v, halfSize);
      51           0 :     i16 i0 = ((shape.x - halfBound.X) / cellSize).ToInt_RoundToNegInfinity();
      52           0 :     i16 j0 = ((shape.z - halfBound.Y) / cellSize).ToInt_RoundToNegInfinity();
      53           0 :     i16 i1 = ((shape.x + halfBound.X) / cellSize).ToInt_RoundToInfinity();
      54           0 :     i16 j1 = ((shape.z + halfBound.Y) / cellSize).ToInt_RoundToInfinity();
      55             : 
      56           0 :     if (j1 <= j0)
      57           0 :         return; // empty bounds - this shouldn't happen
      58             : 
      59             : 
      60           0 :     rasterClearance = rasterClearance.Multiply(rasterClearance);
      61             : 
      62           0 :     spans.reserve(j1 - j0);
      63             : 
      64           0 :     for (i16 j = j0; j < j1; ++j)
      65             :     {
      66             :         // Find the min/max range of cells that are strictly inside the square+rasterClearance.
      67             :         // (Since the square+rasterClearance is a convex shape, we can just test each
      68             :         // corner of each cell is inside the shape.)
      69             :         // When looping on i, if the previous cell was inside, no need to check again the left corners.
      70             :         // and we can stop the loop when exiting the shape.
      71             :         // Futhermore if one of the right corners of a cell is outside, no need to check the following cell
      72           0 :         i16 spanI0 = std::numeric_limits<i16>::max();
      73           0 :         i16 spanI1 = std::numeric_limits<i16>::min();
      74           0 :         bool previousInside = false;
      75           0 :         bool skipNextCell = false;
      76           0 :         for (i16 i = i0; i < i1; ++i)
      77             :         {
      78           0 :             if (skipNextCell)
      79             :             {
      80           0 :                 skipNextCell = false;
      81           0 :                 continue;
      82             :             }
      83             : 
      84           0 :             if (Geometry::DistanceToSquareSquared(CFixedVector2D(cellSize*(i+1)-shape.x, cellSize*j-shape.z),
      85           0 :                                     shape.u, shape.v, shapeHalfSize, true) > rasterClearance)
      86             :             {
      87           0 :                 if (previousInside)
      88           0 :                     break;
      89           0 :                 skipNextCell = true;
      90           0 :                 continue;
      91             :             }
      92             : 
      93           0 :             if (Geometry::DistanceToSquareSquared(CFixedVector2D(cellSize*(i+1)-shape.x, cellSize*(j+1)-shape.z),
      94           0 :                                     shape.u, shape.v, shapeHalfSize, true) > rasterClearance)
      95             :             {
      96           0 :                 if (previousInside)
      97           0 :                     break;
      98           0 :                 skipNextCell = true;
      99           0 :                 continue;
     100             :             }
     101             : 
     102           0 :             if (!previousInside)
     103             :             {
     104           0 :                 if (Geometry::DistanceToSquareSquared(CFixedVector2D(cellSize*i-shape.x, cellSize*j-shape.z),
     105           0 :                                     shape.u, shape.v, shapeHalfSize, true) > rasterClearance)
     106           0 :                     continue;
     107             : 
     108           0 :                 if (Geometry::DistanceToSquareSquared(CFixedVector2D(cellSize*i-shape.x, cellSize*(j+1)-shape.z),
     109           0 :                                     shape.u, shape.v, shapeHalfSize, true) > rasterClearance)
     110           0 :                     continue;
     111             : 
     112           0 :                 previousInside = true;
     113           0 :                 spanI0 = i;
     114             :             }
     115             : 
     116           0 :             spanI1 = i+1;
     117             :         }
     118             : 
     119             :         // Add non-empty spans onto the list
     120           0 :         if (spanI0 < spanI1)
     121             :         {
     122           0 :             Span span = { spanI0, spanI1, j };
     123           0 :             spans.push_back(span);
     124             :         }
     125             :     }
     126             : }

Generated by: LCOV version 1.13