LCOV - code coverage report
Current view: top level - source/maths - Brush.cpp (source / functions) Hit Total Coverage
Test: 0 A.D. test coverage report Lines: 119 142 83.8 %
Date: 2023-01-19 00:18:29 Functions: 9 11 81.8 %

          Line data    Source code
       1             : /* Copyright (C) 2021 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 "Brush.h"
      21             : 
      22             : #include "maths/BoundingBoxAligned.h"
      23             : #include "maths/Frustum.h"
      24             : 
      25             : CBrush::CBrush() = default;
      26             : 
      27             : ///////////////////////////////////////////////////////////////////////////////
      28             : // Convert the given bounds into a brush
      29           3 : CBrush::CBrush(const CBoundingBoxAligned& bounds)
      30             : {
      31           3 :     m_Vertices.resize(8);
      32             : 
      33          27 :     for(size_t i = 0; i < 8; ++i)
      34             :     {
      35          24 :         m_Vertices[i][0] = bounds[(i & 1) ? 1 : 0][0]; // X
      36          24 :         m_Vertices[i][1] = bounds[(i & 2) ? 1 : 0][1]; // Y
      37          24 :         m_Vertices[i][2] = bounds[(i & 4) ? 1 : 0][2]; // Z
      38             :     }
      39             : 
      40             :     // construct cube face indices, 5 vertex indices per face (start vertex included twice)
      41             : 
      42           3 :     m_Faces.resize(30);
      43             : 
      44           3 :     m_Faces[0] = 0; m_Faces[1] = 1; m_Faces[2] = 3; m_Faces[3] = 2; m_Faces[4] = 0; // Z = min
      45           3 :     m_Faces[5] = 4; m_Faces[6] = 5; m_Faces[7] = 7; m_Faces[8] = 6; m_Faces[9] = 4; // Z = max
      46             : 
      47           3 :     m_Faces[10] = 0; m_Faces[11] = 2; m_Faces[12] = 6; m_Faces[13] = 4; m_Faces[14] = 0; // X = min
      48           3 :     m_Faces[15] = 1; m_Faces[16] = 3; m_Faces[17] = 7; m_Faces[18] = 5; m_Faces[19] = 1; // X = max
      49             : 
      50           3 :     m_Faces[20] = 0; m_Faces[21] = 1; m_Faces[22] = 5; m_Faces[23] = 4; m_Faces[24] = 0; // Y = min
      51           3 :     m_Faces[25] = 2; m_Faces[26] = 3; m_Faces[27] = 7; m_Faces[28] = 6; m_Faces[29] = 2; // Y = max
      52           3 : }
      53             : 
      54             : 
      55             : ///////////////////////////////////////////////////////////////////////////////
      56             : // Calculate bounds of this brush
      57           0 : void CBrush::Bounds(CBoundingBoxAligned& result) const
      58             : {
      59           0 :     result.SetEmpty();
      60             : 
      61           0 :     for(size_t i = 0; i < m_Vertices.size(); ++i)
      62           0 :         result += m_Vertices[i];
      63           0 : }
      64             : 
      65             : 
      66             : ///////////////////////////////////////////////////////////////////////////////
      67             : // Cut the brush according to a given plane
      68             : 
      69             : /// Holds information about what happens to a single vertex in a brush during a slicing operation.
      70             : struct SliceOpVertexInfo
      71             : {
      72             :     float planeDist;    ///< Signed distance from this vertex to the slicing plane.
      73             :     size_t resIdx;      ///< Index of this vertex in the resulting brush (or NO_VERTEX if cut away)
      74             : };
      75             : 
      76             : /// Holds information about a newly introduced vertex on an edge in a brush as the result of a slicing operation.
      77             : struct SliceOpNewVertexInfo
      78             : {
      79             :     /// Indices of adjacent edge vertices in original brush
      80             :     size_t edgeIdx1, edgeIdx2;
      81             :     /// Index of newly introduced vertex in resulting brush
      82             :     size_t resIdx;
      83             : 
      84             :     /**
      85             :      * Index into SliceOpInfo.nvInfo; hold the indices of this new vertex's direct neighbours in the slicing plane face,
      86             :      * with no consistent winding direction around the face for either field (e.g., the neighb1 of X can point back to
      87             :      * X with either its neighb1 or neighb2).
      88             :      */
      89             :     size_t neighbIdx1, neighbIdx2;
      90             : };
      91             : 
      92             : /// Holds support information during a CBrush/CPlane slicing operation.
      93           8 : struct SliceOpInfo
      94             : {
      95             :     CBrush* result;
      96             :     const CBrush* original;
      97             : 
      98             :     /**
      99             :      * Holds information about what happens to each vertex in the original brush after the slice operation.
     100             :      * Same size as m_Vertices of the brush getting sliced.
     101             :      */
     102             :     std::vector<SliceOpVertexInfo> ovInfo;
     103             : 
     104             :     /// Holds information about newly inserted vertices during a slice operation.
     105             :     std::vector<SliceOpNewVertexInfo> nvInfo;
     106             : 
     107             :     /**
     108             :      * Indices into nvInfo; during the execution of the slicing algorithm, holds the previously inserted new vertex on
     109             :      * one of the edges of the face that's currently being evaluated for slice points, or NO_VERTEX if no such vertex
     110             :      * exists.
     111             :      */
     112             :     size_t thisFaceNewVertexIdx;
     113             : };
     114             : 
     115             : struct CBrush::Helper
     116             : {
     117             :     /**
     118             :      * Creates a new vertex between the given two vertices (indexed into the original brush).
     119             :      * Returns the index of the new vertex in the resulting brush.
     120             :      */
     121             :     static size_t SliceNewVertex(SliceOpInfo& sliceInfo, size_t v1, size_t v2);
     122             : };
     123             : 
     124           8 : size_t CBrush::Helper::SliceNewVertex(SliceOpInfo& sliceOp, size_t edgeIdx1, size_t edgeIdx2)
     125             : {
     126             :     // check if a new vertex has already been inserted on this edge
     127             :     size_t idx;
     128          20 :     for(idx = 0; idx < sliceOp.nvInfo.size(); ++idx)
     129             :     {
     130          34 :         if ((sliceOp.nvInfo[idx].edgeIdx1 == edgeIdx1 && sliceOp.nvInfo[idx].edgeIdx2 == edgeIdx2) ||
     131          16 :             (sliceOp.nvInfo[idx].edgeIdx1 == edgeIdx2 && sliceOp.nvInfo[idx].edgeIdx2 == edgeIdx1))
     132           4 :             break;
     133             :     }
     134             : 
     135           8 :     if (idx >= sliceOp.nvInfo.size())
     136             :     {
     137             :         // no previously inserted new vertex found on this edge; insert a new one
     138             :         SliceOpNewVertexInfo nvi;
     139           4 :         CVector3D newPos;
     140             : 
     141             :         // interpolate between the two vertices based on their distance from the plane
     142           4 :         float inv = 1.0 / (sliceOp.ovInfo[edgeIdx1].planeDist - sliceOp.ovInfo[edgeIdx2].planeDist);
     143           4 :         newPos = sliceOp.original->m_Vertices[edgeIdx2] * ( sliceOp.ovInfo[edgeIdx1].planeDist * inv) +
     144           8 :                  sliceOp.original->m_Vertices[edgeIdx1] * (-sliceOp.ovInfo[edgeIdx2].planeDist * inv);
     145             : 
     146           4 :         nvi.edgeIdx1 = edgeIdx1;
     147           4 :         nvi.edgeIdx2 = edgeIdx2;
     148           4 :         nvi.resIdx = sliceOp.result->m_Vertices.size();
     149           4 :         nvi.neighbIdx1 = NO_VERTEX;
     150           4 :         nvi.neighbIdx2 = NO_VERTEX;
     151             : 
     152           4 :         sliceOp.result->m_Vertices.push_back(newPos);
     153           4 :         sliceOp.nvInfo.push_back(nvi);
     154             :     }
     155             : 
     156             :     // at this point, 'idx' is the index into nvInfo of the vertex inserted onto the edge
     157             : 
     158           8 :     if (sliceOp.thisFaceNewVertexIdx != NO_VERTEX)
     159             :     {
     160             :         // a vertex has been previously inserted onto another edge of this face; link them together as neighbours
     161             :         // (using whichever one of the neighbIdx1 or -2 links is still available)
     162             : 
     163           4 :         if (sliceOp.nvInfo[sliceOp.thisFaceNewVertexIdx].neighbIdx1 == NO_VERTEX)
     164           2 :             sliceOp.nvInfo[sliceOp.thisFaceNewVertexIdx].neighbIdx1 = idx;
     165             :         else
     166           2 :             sliceOp.nvInfo[sliceOp.thisFaceNewVertexIdx].neighbIdx2 = idx;
     167             : 
     168           4 :         if (sliceOp.nvInfo[idx].neighbIdx1 == NO_VERTEX)
     169           2 :             sliceOp.nvInfo[idx].neighbIdx1 = sliceOp.thisFaceNewVertexIdx;
     170             :         else
     171           2 :             sliceOp.nvInfo[idx].neighbIdx2 = sliceOp.thisFaceNewVertexIdx;
     172             : 
     173             :         // a plane should slice a face only in two locations, so reset for the next face
     174           4 :         sliceOp.thisFaceNewVertexIdx = NO_VERTEX;
     175             :     }
     176             :     else
     177             :     {
     178             :         // store the index of the inserted vertex on this edge, so that we can retrieve it when the plane slices
     179             :         // this face again in another edge
     180           4 :         sliceOp.thisFaceNewVertexIdx = idx;
     181             :     }
     182             : 
     183           8 :     return sliceOp.nvInfo[idx].resIdx;
     184             : }
     185             : 
     186           4 : void CBrush::Slice(const CPlane& plane, CBrush& result) const
     187             : {
     188           4 :     ENSURE(&result != this);
     189             : 
     190           8 :     SliceOpInfo sliceOp;
     191             : 
     192           4 :     sliceOp.original = this;
     193           4 :     sliceOp.result = &result;
     194           4 :     sliceOp.thisFaceNewVertexIdx = NO_VERTEX;
     195           4 :     sliceOp.ovInfo.resize(m_Vertices.size());
     196           4 :     sliceOp.nvInfo.reserve(m_Vertices.size() / 2);
     197             : 
     198           4 :     result.m_Vertices.resize(0); // clear any left-overs
     199           4 :     result.m_Faces.resize(0);
     200           4 :     result.m_Vertices.reserve(m_Vertices.size() + 2);
     201           4 :     result.m_Faces.reserve(m_Faces.size() + 5);
     202             : 
     203             :     // Copy vertices that weren't sliced away by the plane to the resulting brush.
     204          28 :     for(size_t i = 0; i < m_Vertices.size(); ++i)
     205             :     {
     206          24 :         const CVector3D& vtx = m_Vertices[i];            // current vertex
     207          24 :         SliceOpVertexInfo& vtxInfo = sliceOp.ovInfo[i];  // slicing operation info about current vertex
     208             : 
     209          24 :         vtxInfo.planeDist = plane.DistanceToPlane(vtx);
     210          24 :         if (vtxInfo.planeDist >= 0.0)
     211             :         {
     212             :             // positive side of the plane; not sliced away
     213          12 :             vtxInfo.resIdx = result.m_Vertices.size();
     214          12 :             result.m_Vertices.push_back(vtx);
     215             :         }
     216             :         else
     217             :         {
     218             :             // other side of the plane; sliced away
     219          12 :             vtxInfo.resIdx = NO_VERTEX;
     220             :         }
     221             :     }
     222             : 
     223             :     // Transfer faces. (Recall how faces are specified; see CBrush::m_Faces). The idea is to examine each face separately,
     224             :     // and see where its edges cross the slicing plane (meaning that exactly one of the vertices of that edge was cut away).
     225             :     // On those edges, new vertices are introduced where the edge intersects the plane, and the resulting brush's m_Faces
     226             :     // array is updated to refer to the newly inserted vertices instead of the original one that got cut away.
     227             : 
     228           4 :     size_t currentFaceStartIdx = NO_VERTEX; // index of the first vertex of the current face in the original brush
     229           4 :     size_t resultFaceStartIdx = NO_VERTEX;  // index of the first vertex of the current face in the resulting brush
     230             : 
     231          94 :     for(size_t i = 0; i < m_Faces.size(); ++i)
     232             :     {
     233          90 :         if (currentFaceStartIdx == NO_VERTEX)
     234             :         {
     235             :             // starting a new face
     236          18 :             ENSURE(sliceOp.thisFaceNewVertexIdx == NO_VERTEX);
     237             : 
     238          18 :             currentFaceStartIdx = m_Faces[i];
     239          18 :             resultFaceStartIdx = result.m_Faces.size();
     240          18 :             continue;
     241             :         }
     242             : 
     243          72 :         size_t prevIdx = m_Faces[i-1];  // index of previous vertex in this face list
     244          72 :         size_t curIdx = m_Faces[i];     // index of current vertex in this face list
     245             : 
     246          72 :         if (sliceOp.ovInfo[prevIdx].resIdx == NO_VERTEX)
     247             :         {
     248             :             // previous face vertex got sliced away by the plane; see if the edge (prev,current) crosses the slicing plane
     249          36 :             if (sliceOp.ovInfo[curIdx].resIdx != NO_VERTEX)
     250             :             {
     251             :                 // re-entering the front side of the plane; insert vertex on intersection of plane and (prev,current) edge
     252           4 :                 result.m_Faces.push_back(Helper::SliceNewVertex(sliceOp, prevIdx, curIdx));
     253           4 :                 result.m_Faces.push_back(sliceOp.ovInfo[curIdx].resIdx);
     254             :             }
     255             :         }
     256             :         else
     257             :         {
     258             :             // previous face vertex didn't get sliced away; see if the edge (prev,current) crosses the slicing plane
     259          36 :             if (sliceOp.ovInfo[curIdx].resIdx != NO_VERTEX)
     260             :             {
     261             :                 // perfectly normal edge; doesn't cross the plane
     262          32 :                 result.m_Faces.push_back(sliceOp.ovInfo[curIdx].resIdx);
     263             :             }
     264             :             else
     265             :             {
     266             :                 // leaving the front side of the plane; insert vertex on intersection of plane and edge (prev, current)
     267           4 :                 result.m_Faces.push_back(Helper::SliceNewVertex(sliceOp, prevIdx, curIdx));
     268             :             }
     269             :         }
     270             : 
     271             :         // if we're back at the first vertex of the current face, then we've completed the face
     272          72 :         if (curIdx == currentFaceStartIdx)
     273             :         {
     274             :             // close the index loop
     275          18 :             if (result.m_Faces.size() > resultFaceStartIdx)
     276          11 :                 result.m_Faces.push_back(result.m_Faces[resultFaceStartIdx]);
     277             : 
     278          18 :             currentFaceStartIdx = NO_VERTEX; // start a new face
     279             :         }
     280             :     }
     281             : 
     282           4 :     ENSURE(currentFaceStartIdx == NO_VERTEX);
     283             : 
     284             :     // Create the face that lies in the slicing plane. Remember, all the intersections of the slicing plane with face
     285             :     // edges of the brush have been stored in sliceOp.nvInfo by the SliceNewVertex function, and refer to their direct
     286             :     // neighbours in the slicing plane face using the neighbIdx1 and neighbIdx2 fields (in no consistent winding order).
     287             : 
     288           4 :     if (sliceOp.nvInfo.size())
     289             :     {
     290             :         // push the starting vertex
     291           1 :         result.m_Faces.push_back(sliceOp.nvInfo[0].resIdx);
     292             : 
     293             :         // At this point, there is no consistent winding order in the neighbX fields, so at each vertex we need to figure
     294             :         // out whether neighb1 or neighb2 points 'onwards' along the face, according to an initially chosen winding direction.
     295             :         // (or, equivalently, which one points back to the one we were just at). At each vertex, we then set neighb1 to be the
     296             :         // one to point onwards, deleting any pointers which we no longer need to complete the trace.
     297             : 
     298             :         size_t idx;
     299           1 :         size_t prev = 0;
     300             : 
     301           1 :         idx = sliceOp.nvInfo[0].neighbIdx2; // pick arbitrary starting direction
     302           1 :         sliceOp.nvInfo[0].neighbIdx2 = NO_VERTEX;
     303             : 
     304           7 :         while(idx != 0)
     305             :         {
     306           3 :             ENSURE(idx < sliceOp.nvInfo.size());
     307           3 :             if (idx >= sliceOp.nvInfo.size())
     308           0 :                 break;
     309             : 
     310           3 :             if (sliceOp.nvInfo[idx].neighbIdx1 == prev)
     311             :             {
     312             :                 // neighb1 is pointing the wrong way; we want to normalize it to point onwards in the direction
     313             :                 // we initially chose, so swap it with neighb2 and delete neighb2 (no longer needed)
     314           1 :                 sliceOp.nvInfo[idx].neighbIdx1 = sliceOp.nvInfo[idx].neighbIdx2;
     315           1 :                 sliceOp.nvInfo[idx].neighbIdx2 = NO_VERTEX;
     316             :             }
     317             :             else
     318             :             {
     319             :                 // neighb1 isn't pointing to the previous vertex, so neighb2 must be (otherwise a pair of vertices failed to
     320             :                 // get paired properly during face/plane slicing).
     321           2 :                 ENSURE(sliceOp.nvInfo[idx].neighbIdx2 == prev);
     322           2 :                 sliceOp.nvInfo[idx].neighbIdx2 = NO_VERTEX;
     323             :             }
     324             : 
     325           3 :             result.m_Faces.push_back(sliceOp.nvInfo[idx].resIdx);
     326             : 
     327             :             // move to next vertex; neighb1 has been normalized to point onward
     328           3 :             prev = idx;
     329           3 :             idx = sliceOp.nvInfo[idx].neighbIdx1;
     330           3 :             sliceOp.nvInfo[prev].neighbIdx1 = NO_VERTEX; // no longer needed, we've moved on
     331             :         }
     332             : 
     333             :         // push starting vertex again to close the shape
     334           1 :         result.m_Faces.push_back(sliceOp.nvInfo[0].resIdx);
     335             :     }
     336           4 : }
     337             : 
     338             : 
     339             : 
     340             : ///////////////////////////////////////////////////////////////////////////////
     341             : // Intersect with frustum by repeated slicing
     342           0 : void CBrush::Intersect(const CFrustum& frustum, CBrush& result) const
     343             : {
     344           0 :     ENSURE(&result != this);
     345             : 
     346           0 :     if (!frustum.GetNumPlanes())
     347             :     {
     348           0 :         result = *this;
     349           0 :         return;
     350             :     }
     351             : 
     352           0 :     CBrush buf;
     353           0 :     const CBrush* prev = this;
     354             :     CBrush* next;
     355             : 
     356             :     // Repeatedly slice this brush with each plane of the frustum, alternating between 'result' and 'buf' to
     357             :     // save intermediate results. Set up the starting brush so that the final version always ends up in 'result'.
     358             : 
     359           0 :     if (frustum.GetNumPlanes() & 1)
     360           0 :         next = &result;
     361             :     else
     362           0 :         next = &buf;
     363             : 
     364           0 :     for(size_t i = 0; i < frustum.GetNumPlanes(); ++i)
     365             :     {
     366           0 :         prev->Slice(frustum[i], *next);
     367           0 :         prev = next;
     368           0 :         if (prev == &buf)
     369           0 :             next = &result;
     370             :         else
     371           0 :             next = &buf;
     372             :     }
     373             : 
     374           0 :     ENSURE(prev == &result);
     375             : }
     376             : 
     377          19 : const std::vector<CVector3D>& CBrush::GetVertices() const
     378             : {
     379          19 :     return m_Vertices;
     380             : }
     381             : 
     382          13 : void CBrush::GetFaces(std::vector<std::vector<size_t>>& out) const
     383             : {
     384             :     // split the back-to-back faces into separate face vectors, so that they're in a
     385             :     // user-friendlier format than the back-to-back vertex index array
     386             :     // i.e. split 'x--xy------yz----z' into 'x--x', 'y-------y', 'z---z'
     387             : 
     388          13 :     size_t faceStartIdx = 0;
     389         157 :     while (faceStartIdx < m_Faces.size())
     390             :     {
     391             :         // start new face
     392         144 :         std::vector<size_t> singleFace;
     393          72 :         singleFace.push_back(m_Faces[faceStartIdx]);
     394             : 
     395             :         // step over all the values in the face until we hit the starting value again (which closes the face)
     396          72 :         size_t j = faceStartIdx + 1;
     397         504 :         while (j < m_Faces.size() && m_Faces[j] != m_Faces[faceStartIdx])
     398             :         {
     399         216 :             singleFace.push_back(m_Faces[j]);
     400         216 :             j++;
     401             :         }
     402             : 
     403             :         // each face must be closed by the same value that started it
     404          72 :         ENSURE(m_Faces[faceStartIdx] == m_Faces[j]);
     405             : 
     406          72 :         singleFace.push_back(m_Faces[j]);
     407          72 :         out.push_back(singleFace);
     408             : 
     409          72 :         faceStartIdx = j + 1;
     410             :     }
     411          16 : }

Generated by: LCOV version 1.13