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 : }
|
