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 : /*
19 : * Axis-aligned bounding box
20 : */
21 :
22 : #include "precompiled.h"
23 :
24 : #include "BoundingBoxAligned.h"
25 :
26 : #include "maths/BoundingBoxOriented.h"
27 : #include "maths/Brush.h"
28 : #include "maths/Frustum.h"
29 : #include "maths/Matrix3D.h"
30 :
31 : #include <limits>
32 :
33 1 : const CBoundingBoxAligned CBoundingBoxAligned::EMPTY = CBoundingBoxAligned(); // initializes to an empty bound
34 :
35 : ///////////////////////////////////////////////////////////////////////////////
36 : // RayIntersect: intersect ray with this bound; return true
37 : // if ray hits (and store entry and exit times), or false
38 : // otherwise
39 : // note: incoming ray direction must be normalised
40 0 : bool CBoundingBoxAligned::RayIntersect(
41 : const CVector3D& origin, const CVector3D& dir, float& tmin, float& tmax) const
42 : {
43 : float t1, t2;
44 : float tnear, tfar;
45 :
46 0 : if (dir[0] == 0)
47 : {
48 0 : if (origin[0] < m_Data[0][0] || origin[0] > m_Data[1][0])
49 0 : return false;
50 : else
51 : {
52 0 : tnear = -std::numeric_limits<float>::max();
53 0 : tfar = std::numeric_limits<float>::max();
54 : }
55 : }
56 : else
57 : {
58 0 : t1 = (m_Data[0][0] - origin[0]) / dir[0];
59 0 : t2 = (m_Data[1][0] - origin[0]) / dir[0];
60 :
61 0 : if (dir[0] < 0)
62 : {
63 0 : tnear = t2;
64 0 : tfar = t1;
65 : }
66 : else
67 : {
68 0 : tnear = t1;
69 0 : tfar = t2;
70 : }
71 :
72 0 : if (tfar < 0)
73 0 : return false;
74 : }
75 :
76 0 : if (dir[1] == 0 && (origin[1] < m_Data[0][1] || origin[1] > m_Data[1][1]))
77 0 : return false;
78 : else
79 : {
80 0 : t1 = (m_Data[0][1] - origin[1]) / dir[1];
81 0 : t2 = (m_Data[1][1] - origin[1]) / dir[1];
82 :
83 0 : if (dir[1] < 0)
84 : {
85 0 : if (t2 > tnear)
86 0 : tnear = t2;
87 0 : if (t1 < tfar)
88 0 : tfar = t1;
89 : }
90 : else
91 : {
92 0 : if (t1 > tnear)
93 0 : tnear = t1;
94 0 : if (t2 < tfar)
95 0 : tfar = t2;
96 : }
97 :
98 0 : if (tnear > tfar || tfar < 0)
99 0 : return false;
100 : }
101 :
102 0 : if (dir[2] == 0 && (origin[2] < m_Data[0][2] || origin[2] > m_Data[1][2]))
103 0 : return false;
104 : else
105 : {
106 0 : t1 = (m_Data[0][2] - origin[2]) / dir[2];
107 0 : t2 = (m_Data[1][2] - origin[2]) / dir[2];
108 :
109 0 : if (dir[2] < 0)
110 : {
111 0 : if (t2 > tnear)
112 0 : tnear = t2;
113 0 : if (t1 < tfar)
114 0 : tfar = t1;
115 : }
116 : else
117 : {
118 0 : if (t1 > tnear)
119 0 : tnear = t1;
120 0 : if (t2 < tfar)
121 0 : tfar = t2;
122 : }
123 :
124 0 : if (tnear > tfar || tfar < 0)
125 0 : return false;
126 : }
127 :
128 0 : tmin = tnear;
129 0 : tmax = tfar;
130 :
131 0 : return true;
132 : }
133 :
134 : ///////////////////////////////////////////////////////////////////////////////
135 : // SetEmpty: initialise this bound as empty
136 1425 : void CBoundingBoxAligned::SetEmpty()
137 : {
138 1425 : m_Data[0] = CVector3D::Max();
139 1425 : m_Data[1] = CVector3D::Min();
140 1425 : }
141 :
142 : ///////////////////////////////////////////////////////////////////////////////
143 : // IsEmpty: tests whether this bound is empty
144 18 : bool CBoundingBoxAligned::IsEmpty() const
145 : {
146 18 : return m_Data[0] == CVector3D::Max() && m_Data[1] == CVector3D::Min();
147 : }
148 :
149 : ///////////////////////////////////////////////////////////////////////////////
150 : // Transform: transform this bound by given matrix; return transformed bound
151 : // in 'result' parameter - slightly modified version of code in Graphic Gems
152 : // (can't remember which one it was, though)
153 0 : void CBoundingBoxAligned::Transform(const CMatrix3D& m, CBoundingBoxAligned& result) const
154 : {
155 0 : ENSURE(this != &result);
156 :
157 0 : for (int i = 0; i < 3; ++i)
158 : {
159 : // handle translation
160 0 : result[0][i] = result[1][i] = m(i, 3);
161 :
162 : // Now find the extreme points by considering the product of the
163 : // min and max with each component of matrix
164 0 : for (int j = 0; j < 3; ++j)
165 : {
166 0 : float a = m(i, j) * m_Data[0][j];
167 0 : float b = m(i, j) * m_Data[1][j];
168 :
169 0 : if (a >= b)
170 0 : std::swap(a, b);
171 :
172 0 : result[0][i] += a;
173 0 : result[1][i] += b;
174 : }
175 : }
176 0 : }
177 :
178 5 : void CBoundingBoxAligned::Transform(const CMatrix3D& transform, CBoundingBoxOriented& result) const
179 : {
180 5 : const CVector3D& pMin = m_Data[0];
181 5 : const CVector3D& pMax = m_Data[1];
182 :
183 : // the basis vectors of the OBB are the normalized versions of the transformed AABB basis vectors, which
184 : // are the columns of the identity matrix, so the unnormalized OBB basis vectors are the transformation
185 : // matrix columns:
186 5 : CVector3D u(transform._11, transform._21, transform._31);
187 5 : CVector3D v(transform._12, transform._22, transform._32);
188 5 : CVector3D w(transform._13, transform._23, transform._33);
189 :
190 : // the half-sizes are scaled by whatever factor the AABB unit vectors end up scaled by
191 15 : result.m_HalfSizes = CVector3D(
192 5 : (pMax.X - pMin.X) / 2.f * u.Length(),
193 5 : (pMax.Y - pMin.Y) / 2.f * v.Length(),
194 5 : (pMax.Z - pMin.Z) / 2.f * w.Length()
195 : );
196 :
197 5 : u.Normalize();
198 5 : v.Normalize();
199 5 : w.Normalize();
200 :
201 5 : result.m_Basis[0] = u;
202 5 : result.m_Basis[1] = v;
203 5 : result.m_Basis[2] = w;
204 :
205 5 : result.m_Center = transform.Transform((pMax + pMin) * 0.5f);
206 5 : }
207 :
208 : ///////////////////////////////////////////////////////////////////////////////
209 : // Intersect with the given frustum in a conservative manner
210 0 : void CBoundingBoxAligned::IntersectFrustumConservative(const CFrustum& frustum)
211 : {
212 : // if this bound is empty, then the result must be empty (we should not attempt to intersect with
213 : // a brush, may cause crashes due to the numeric representation of empty bounds -- see
214 : // http://trac.wildfiregames.com/ticket/1027)
215 0 : if (IsEmpty())
216 0 : return;
217 :
218 0 : CBrush brush(*this);
219 0 : CBrush buf;
220 :
221 0 : brush.Intersect(frustum, buf);
222 :
223 0 : buf.Bounds(*this);
224 : }
225 :
226 : ///////////////////////////////////////////////////////////////////////////////
227 0 : CFrustum CBoundingBoxAligned::ToFrustum() const
228 : {
229 0 : CFrustum frustum;
230 :
231 0 : frustum.SetNumPlanes(6);
232 :
233 : // get the LEFT plane
234 0 : frustum[0].m_Norm = CVector3D(1, 0, 0);
235 0 : frustum[0].m_Dist = -m_Data[0].X;
236 :
237 : // get the RIGHT plane
238 0 : frustum[1].m_Norm = CVector3D(-1, 0, 0);
239 0 : frustum[1].m_Dist = m_Data[1].X;
240 :
241 : // get the BOTTOM plane
242 0 : frustum[2].m_Norm = CVector3D(0, 1, 0);
243 0 : frustum[2].m_Dist = -m_Data[0].Y;
244 :
245 : // get the TOP plane
246 0 : frustum[3].m_Norm = CVector3D(0, -1, 0);
247 0 : frustum[3].m_Dist = m_Data[1].Y;
248 :
249 : // get the NEAR plane
250 0 : frustum[4].m_Norm = CVector3D(0, 0, 1);
251 0 : frustum[4].m_Dist = -m_Data[0].Z;
252 :
253 : // get the FAR plane
254 0 : frustum[5].m_Norm = CVector3D(0, 0, -1);
255 0 : frustum[5].m_Dist = m_Data[1].Z;
256 :
257 0 : return frustum;
258 : }
259 :
260 : ///////////////////////////////////////////////////////////////////////////////
261 0 : void CBoundingBoxAligned::Expand(float amount)
262 : {
263 0 : m_Data[0] -= CVector3D(amount, amount, amount);
264 0 : m_Data[1] += CVector3D(amount, amount, amount);
265 0 : }
266 :
267 69 : bool CBoundingBoxAligned::IsPointInside(const CVector3D& point) const
268 : {
269 : return
270 176 : m_Data[0].X <= point.X && point.X <= m_Data[1].X &&
271 130 : m_Data[0].Y <= point.Y && point.Y <= m_Data[1].Y &&
272 139 : m_Data[0].Z <= point.Z && point.Z <= m_Data[1].Z;
273 3 : }
|
