1 /* Copyright (C) 2021 Wildfire Games.
2 * This file is part of 0 A.D.
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.
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.
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/>.
18 #include "precompiled.h"
22 #include "maths/BoundingBoxAligned.h"
23 #include "maths/Frustum.h"
25 CBrush::CBrush() = default;
27 ///////////////////////////////////////////////////////////////////////////////
28 // Convert the given bounds into a brush
29 CBrush::CBrush(const CBoundingBoxAligned
& bounds
)
33 for(size_t i
= 0; i
< 8; ++i
)
35 m_Vertices
[i
][0] = bounds
[(i
& 1) ? 1 : 0][0]; // X
36 m_Vertices
[i
][1] = bounds
[(i
& 2) ? 1 : 0][1]; // Y
37 m_Vertices
[i
][2] = bounds
[(i
& 4) ? 1 : 0][2]; // Z
40 // construct cube face indices, 5 vertex indices per face (start vertex included twice)
44 m_Faces
[0] = 0; m_Faces
[1] = 1; m_Faces
[2] = 3; m_Faces
[3] = 2; m_Faces
[4] = 0; // Z = min
45 m_Faces
[5] = 4; m_Faces
[6] = 5; m_Faces
[7] = 7; m_Faces
[8] = 6; m_Faces
[9] = 4; // Z = max
47 m_Faces
[10] = 0; m_Faces
[11] = 2; m_Faces
[12] = 6; m_Faces
[13] = 4; m_Faces
[14] = 0; // X = min
48 m_Faces
[15] = 1; m_Faces
[16] = 3; m_Faces
[17] = 7; m_Faces
[18] = 5; m_Faces
[19] = 1; // X = max
50 m_Faces
[20] = 0; m_Faces
[21] = 1; m_Faces
[22] = 5; m_Faces
[23] = 4; m_Faces
[24] = 0; // Y = min
51 m_Faces
[25] = 2; m_Faces
[26] = 3; m_Faces
[27] = 7; m_Faces
[28] = 6; m_Faces
[29] = 2; // Y = max
55 ///////////////////////////////////////////////////////////////////////////////
56 // Calculate bounds of this brush
57 void CBrush::Bounds(CBoundingBoxAligned
& result
) const
61 for(size_t i
= 0; i
< m_Vertices
.size(); ++i
)
62 result
+= m_Vertices
[i
];
66 ///////////////////////////////////////////////////////////////////////////////
67 // Cut the brush according to a given plane
69 /// Holds information about what happens to a single vertex in a brush during a slicing operation.
70 struct SliceOpVertexInfo
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)
76 /// Holds information about a newly introduced vertex on an edge in a brush as the result of a slicing operation.
77 struct SliceOpNewVertexInfo
79 /// Indices of adjacent edge vertices in original brush
80 size_t edgeIdx1
, edgeIdx2
;
81 /// Index of newly introduced vertex in resulting brush
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).
89 size_t neighbIdx1
, neighbIdx2
;
92 /// Holds support information during a CBrush/CPlane slicing operation.
96 const CBrush
* original
;
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.
102 std::vector
<SliceOpVertexInfo
> ovInfo
;
104 /// Holds information about newly inserted vertices during a slice operation.
105 std::vector
<SliceOpNewVertexInfo
> nvInfo
;
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
112 size_t thisFaceNewVertexIdx
;
115 struct CBrush::Helper
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.
121 static size_t SliceNewVertex(SliceOpInfo
& sliceInfo
, size_t v1
, size_t v2
);
124 size_t CBrush::Helper::SliceNewVertex(SliceOpInfo
& sliceOp
, size_t edgeIdx1
, size_t edgeIdx2
)
126 // check if a new vertex has already been inserted on this edge
128 for(idx
= 0; idx
< sliceOp
.nvInfo
.size(); ++idx
)
130 if ((sliceOp
.nvInfo
[idx
].edgeIdx1
== edgeIdx1
&& sliceOp
.nvInfo
[idx
].edgeIdx2
== edgeIdx2
) ||
131 (sliceOp
.nvInfo
[idx
].edgeIdx1
== edgeIdx2
&& sliceOp
.nvInfo
[idx
].edgeIdx2
== edgeIdx1
))
135 if (idx
>= sliceOp
.nvInfo
.size())
137 // no previously inserted new vertex found on this edge; insert a new one
138 SliceOpNewVertexInfo nvi
;
141 // interpolate between the two vertices based on their distance from the plane
142 float inv
= 1.0 / (sliceOp
.ovInfo
[edgeIdx1
].planeDist
- sliceOp
.ovInfo
[edgeIdx2
].planeDist
);
143 newPos
= sliceOp
.original
->m_Vertices
[edgeIdx2
] * ( sliceOp
.ovInfo
[edgeIdx1
].planeDist
* inv
) +
144 sliceOp
.original
->m_Vertices
[edgeIdx1
] * (-sliceOp
.ovInfo
[edgeIdx2
].planeDist
* inv
);
146 nvi
.edgeIdx1
= edgeIdx1
;
147 nvi
.edgeIdx2
= edgeIdx2
;
148 nvi
.resIdx
= sliceOp
.result
->m_Vertices
.size();
149 nvi
.neighbIdx1
= NO_VERTEX
;
150 nvi
.neighbIdx2
= NO_VERTEX
;
152 sliceOp
.result
->m_Vertices
.push_back(newPos
);
153 sliceOp
.nvInfo
.push_back(nvi
);
156 // at this point, 'idx' is the index into nvInfo of the vertex inserted onto the edge
158 if (sliceOp
.thisFaceNewVertexIdx
!= NO_VERTEX
)
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)
163 if (sliceOp
.nvInfo
[sliceOp
.thisFaceNewVertexIdx
].neighbIdx1
== NO_VERTEX
)
164 sliceOp
.nvInfo
[sliceOp
.thisFaceNewVertexIdx
].neighbIdx1
= idx
;
166 sliceOp
.nvInfo
[sliceOp
.thisFaceNewVertexIdx
].neighbIdx2
= idx
;
168 if (sliceOp
.nvInfo
[idx
].neighbIdx1
== NO_VERTEX
)
169 sliceOp
.nvInfo
[idx
].neighbIdx1
= sliceOp
.thisFaceNewVertexIdx
;
171 sliceOp
.nvInfo
[idx
].neighbIdx2
= sliceOp
.thisFaceNewVertexIdx
;
173 // a plane should slice a face only in two locations, so reset for the next face
174 sliceOp
.thisFaceNewVertexIdx
= NO_VERTEX
;
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 sliceOp
.thisFaceNewVertexIdx
= idx
;
183 return sliceOp
.nvInfo
[idx
].resIdx
;
186 void CBrush::Slice(const CPlane
& plane
, CBrush
& result
) const
188 ENSURE(&result
!= this);
192 sliceOp
.original
= this;
193 sliceOp
.result
= &result
;
194 sliceOp
.thisFaceNewVertexIdx
= NO_VERTEX
;
195 sliceOp
.ovInfo
.resize(m_Vertices
.size());
196 sliceOp
.nvInfo
.reserve(m_Vertices
.size() / 2);
198 result
.m_Vertices
.resize(0); // clear any left-overs
199 result
.m_Faces
.resize(0);
200 result
.m_Vertices
.reserve(m_Vertices
.size() + 2);
201 result
.m_Faces
.reserve(m_Faces
.size() + 5);
203 // Copy vertices that weren't sliced away by the plane to the resulting brush.
204 for(size_t i
= 0; i
< m_Vertices
.size(); ++i
)
206 const CVector3D
& vtx
= m_Vertices
[i
]; // current vertex
207 SliceOpVertexInfo
& vtxInfo
= sliceOp
.ovInfo
[i
]; // slicing operation info about current vertex
209 vtxInfo
.planeDist
= plane
.DistanceToPlane(vtx
);
210 if (vtxInfo
.planeDist
>= 0.0)
212 // positive side of the plane; not sliced away
213 vtxInfo
.resIdx
= result
.m_Vertices
.size();
214 result
.m_Vertices
.push_back(vtx
);
218 // other side of the plane; sliced away
219 vtxInfo
.resIdx
= NO_VERTEX
;
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.
228 size_t currentFaceStartIdx
= NO_VERTEX
; // index of the first vertex of the current face in the original brush
229 size_t resultFaceStartIdx
= NO_VERTEX
; // index of the first vertex of the current face in the resulting brush
231 for(size_t i
= 0; i
< m_Faces
.size(); ++i
)
233 if (currentFaceStartIdx
== NO_VERTEX
)
235 // starting a new face
236 ENSURE(sliceOp
.thisFaceNewVertexIdx
== NO_VERTEX
);
238 currentFaceStartIdx
= m_Faces
[i
];
239 resultFaceStartIdx
= result
.m_Faces
.size();
243 size_t prevIdx
= m_Faces
[i
-1]; // index of previous vertex in this face list
244 size_t curIdx
= m_Faces
[i
]; // index of current vertex in this face list
246 if (sliceOp
.ovInfo
[prevIdx
].resIdx
== NO_VERTEX
)
248 // previous face vertex got sliced away by the plane; see if the edge (prev,current) crosses the slicing plane
249 if (sliceOp
.ovInfo
[curIdx
].resIdx
!= NO_VERTEX
)
251 // re-entering the front side of the plane; insert vertex on intersection of plane and (prev,current) edge
252 result
.m_Faces
.push_back(Helper::SliceNewVertex(sliceOp
, prevIdx
, curIdx
));
253 result
.m_Faces
.push_back(sliceOp
.ovInfo
[curIdx
].resIdx
);
258 // previous face vertex didn't get sliced away; see if the edge (prev,current) crosses the slicing plane
259 if (sliceOp
.ovInfo
[curIdx
].resIdx
!= NO_VERTEX
)
261 // perfectly normal edge; doesn't cross the plane
262 result
.m_Faces
.push_back(sliceOp
.ovInfo
[curIdx
].resIdx
);
266 // leaving the front side of the plane; insert vertex on intersection of plane and edge (prev, current)
267 result
.m_Faces
.push_back(Helper::SliceNewVertex(sliceOp
, prevIdx
, curIdx
));
271 // if we're back at the first vertex of the current face, then we've completed the face
272 if (curIdx
== currentFaceStartIdx
)
274 // close the index loop
275 if (result
.m_Faces
.size() > resultFaceStartIdx
)
276 result
.m_Faces
.push_back(result
.m_Faces
[resultFaceStartIdx
]);
278 currentFaceStartIdx
= NO_VERTEX
; // start a new face
282 ENSURE(currentFaceStartIdx
== NO_VERTEX
);
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).
288 if (sliceOp
.nvInfo
.size())
290 // push the starting vertex
291 result
.m_Faces
.push_back(sliceOp
.nvInfo
[0].resIdx
);
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.
301 idx
= sliceOp
.nvInfo
[0].neighbIdx2
; // pick arbitrary starting direction
302 sliceOp
.nvInfo
[0].neighbIdx2
= NO_VERTEX
;
306 ENSURE(idx
< sliceOp
.nvInfo
.size());
307 if (idx
>= sliceOp
.nvInfo
.size())
310 if (sliceOp
.nvInfo
[idx
].neighbIdx1
== prev
)
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 sliceOp
.nvInfo
[idx
].neighbIdx1
= sliceOp
.nvInfo
[idx
].neighbIdx2
;
315 sliceOp
.nvInfo
[idx
].neighbIdx2
= NO_VERTEX
;
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 ENSURE(sliceOp
.nvInfo
[idx
].neighbIdx2
== prev
);
322 sliceOp
.nvInfo
[idx
].neighbIdx2
= NO_VERTEX
;
325 result
.m_Faces
.push_back(sliceOp
.nvInfo
[idx
].resIdx
);
327 // move to next vertex; neighb1 has been normalized to point onward
329 idx
= sliceOp
.nvInfo
[idx
].neighbIdx1
;
330 sliceOp
.nvInfo
[prev
].neighbIdx1
= NO_VERTEX
; // no longer needed, we've moved on
333 // push starting vertex again to close the shape
334 result
.m_Faces
.push_back(sliceOp
.nvInfo
[0].resIdx
);
340 ///////////////////////////////////////////////////////////////////////////////
341 // Intersect with frustum by repeated slicing
342 void CBrush::Intersect(const CFrustum
& frustum
, CBrush
& result
) const
344 ENSURE(&result
!= this);
346 if (!frustum
.GetNumPlanes())
353 const CBrush
* prev
= this;
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'.
359 if (frustum
.GetNumPlanes() & 1)
364 for(size_t i
= 0; i
< frustum
.GetNumPlanes(); ++i
)
366 prev
->Slice(frustum
[i
], *next
);
374 ENSURE(prev
== &result
);
377 const std::vector
<CVector3D
>& CBrush::GetVertices() const
382 void CBrush::GetFaces(std::vector
<std::vector
<size_t>>& out
) const
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'
388 size_t faceStartIdx
= 0;
389 while (faceStartIdx
< m_Faces
.size())
392 std::vector
<size_t> singleFace
;
393 singleFace
.push_back(m_Faces
[faceStartIdx
]);
395 // step over all the values in the face until we hit the starting value again (which closes the face)
396 size_t j
= faceStartIdx
+ 1;
397 while (j
< m_Faces
.size() && m_Faces
[j
] != m_Faces
[faceStartIdx
])
399 singleFace
.push_back(m_Faces
[j
]);
403 // each face must be closed by the same value that started it
404 ENSURE(m_Faces
[faceStartIdx
] == m_Faces
[j
]);
406 singleFace
.push_back(m_Faces
[j
]);
407 out
.push_back(singleFace
);
409 faceStartIdx
= j
+ 1;