source/maths/BoundingBoxAligned.cpp

   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 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 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         if (dir[0] == 0)
  47         {
  48                 if (origin[0] < m_Data[0][0] || origin[0] > m_Data[1][0])
  49                         return false;
  50                 else
  51                 {
  52                         tnear = -std::numeric_limits<float>::max();
  53                         tfar = std::numeric_limits<float>::max();
  54                 }
  55         }
  56         else
  57         {
  58                 t1 = (m_Data[0][0] - origin[0]) / dir[0];
  59                 t2 = (m_Data[1][0] - origin[0]) / dir[0];
  60
  61                 if (dir[0] < 0)
  62                 {
  63                         tnear = t2;
  64                         tfar = t1;
  65                 }
  66                 else
  67                 {
  68                         tnear = t1;
  69                         tfar = t2;
  70                 }
  71
  72                 if (tfar < 0)
  73                         return false;
  74         }
  75
  76         if (dir[1] == 0 && (origin[1] < m_Data[0][1] || origin[1] > m_Data[1][1]))
  77                 return false;
  78         else
  79         {
  80                 t1 = (m_Data[0][1] - origin[1]) / dir[1];
  81                 t2 = (m_Data[1][1] - origin[1]) / dir[1];
  82
  83                 if (dir[1] < 0)
  84                 {
  85                         if (t2 > tnear)
  86                                 tnear = t2;
  87                         if (t1 < tfar)
  88                                 tfar = t1;
  89                 }
  90                 else
  91                 {
  92                         if (t1 > tnear)
  93                                 tnear = t1;
  94                         if (t2 < tfar)
  95                                 tfar = t2;
  96                 }
  97
  98                 if (tnear > tfar || tfar < 0)
  99                         return false;
 100         }
 101
 102         if (dir[2] == 0 && (origin[2] < m_Data[0][2] || origin[2] > m_Data[1][2]))
 103                 return false;
 104         else
 105         {
 106                 t1 = (m_Data[0][2] - origin[2]) / dir[2];
 107                 t2 = (m_Data[1][2] - origin[2]) / dir[2];
 108
 109                 if (dir[2] < 0)
 110                 {
 111                         if (t2 > tnear)
 112                                 tnear = t2;
 113                         if (t1 < tfar)
 114                                 tfar = t1;
 115                 }
 116                 else
 117                 {
 118                         if (t1 > tnear)
 119                                 tnear = t1;
 120                         if (t2 < tfar)
 121                                 tfar = t2;
 122                 }
 123
 124                 if (tnear > tfar || tfar < 0)
 125                         return false;
 126         }
 127
 128         tmin = tnear;
 129         tmax = tfar;
 130
 131         return true;
 132 }
 133
 134 ///////////////////////////////////////////////////////////////////////////////
 135 // SetEmpty: initialise this bound as empty
 136 void CBoundingBoxAligned::SetEmpty()
 137 {
 138         m_Data[0] = CVector3D::Max();
 139         m_Data[1] = CVector3D::Min();
 140 }
 141
 142 ///////////////////////////////////////////////////////////////////////////////
 143 // IsEmpty: tests whether this bound is empty
 144 bool CBoundingBoxAligned::IsEmpty() const
 145 {
 146         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 void CBoundingBoxAligned::Transform(const CMatrix3D& m, CBoundingBoxAligned& result) const
 154 {
 155         ENSURE(this != &result);
 156
 157         for (int i = 0; i < 3; ++i)
 158         {
 159                 // handle translation
 160                 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                 for (int j = 0; j < 3; ++j)
 165                 {
 166                         float a = m(i, j) * m_Data[0][j];
 167                         float b = m(i, j) * m_Data[1][j];
 168
 169                         if (a >= b)
 170                                 std::swap(a, b);
 171
 172                         result[0][i] += a;
 173                         result[1][i] += b;
 174                 }
 175         }
 176 }
 177
 178 void CBoundingBoxAligned::Transform(const CMatrix3D& transform, CBoundingBoxOriented& result) const
 179 {
 180         const CVector3D& pMin = m_Data[0];
 181         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         CVector3D u(transform._11, transform._21, transform._31);
 187         CVector3D v(transform._12, transform._22, transform._32);
 188         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         result.m_HalfSizes = CVector3D(
 192                 (pMax.X - pMin.X) / 2.f * u.Length(),
 193                 (pMax.Y - pMin.Y) / 2.f * v.Length(),
 194                 (pMax.Z - pMin.Z) / 2.f * w.Length()
 195         );
 196
 197         u.Normalize();
 198         v.Normalize();
 199         w.Normalize();
 200
 201         result.m_Basis[0] = u;
 202         result.m_Basis[1] = v;
 203         result.m_Basis[2] = w;
 204
 205         result.m_Center = transform.Transform((pMax + pMin) * 0.5f);
 206 }
 207
 208 ///////////////////////////////////////////////////////////////////////////////
 209 // Intersect with the given frustum in a conservative manner
 210 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         if (IsEmpty())
 216                 return;
 217
 218         CBrush brush(*this);
 219         CBrush buf;
 220
 221         brush.Intersect(frustum, buf);
 222
 223         buf.Bounds(*this);
 224 }
 225
 226 ///////////////////////////////////////////////////////////////////////////////
 227 CFrustum CBoundingBoxAligned::ToFrustum() const
 228 {
 229         CFrustum frustum;
 230
 231         frustum.SetNumPlanes(6);
 232
 233         // get the LEFT plane
 234         frustum[0].m_Norm = CVector3D(1, 0, 0);
 235         frustum[0].m_Dist = -m_Data[0].X;
 236
 237         // get the RIGHT plane
 238         frustum[1].m_Norm = CVector3D(-1, 0, 0);
 239         frustum[1].m_Dist = m_Data[1].X;
 240
 241         // get the BOTTOM plane
 242         frustum[2].m_Norm = CVector3D(0, 1, 0);
 243         frustum[2].m_Dist = -m_Data[0].Y;
 244
 245         // get the TOP plane
 246         frustum[3].m_Norm = CVector3D(0, -1, 0);
 247         frustum[3].m_Dist = m_Data[1].Y;
 248
 249         // get the NEAR plane
 250         frustum[4].m_Norm = CVector3D(0, 0, 1);
 251         frustum[4].m_Dist = -m_Data[0].Z;
 252
 253         // get the FAR plane
 254         frustum[5].m_Norm = CVector3D(0, 0, -1);
 255         frustum[5].m_Dist = m_Data[1].Z;
 256
 257         return frustum;
 258 }
 259
 260 ///////////////////////////////////////////////////////////////////////////////
 261 void CBoundingBoxAligned::Expand(float amount)
 262 {
 263         m_Data[0] -= CVector3D(amount, amount, amount);
 264         m_Data[1] += CVector3D(amount, amount, amount);
 265 }
 266
 267 bool CBoundingBoxAligned::IsPointInside(const CVector3D& point) const
 268 {
 269         return
 270                 m_Data[0].X <= point.X && point.X <= m_Data[1].X &&
 271                 m_Data[0].Y <= point.Y && point.Y <= m_Data[1].Y &&
 272                 m_Data[0].Z <= point.Z && point.Z <= m_Data[1].Z;
 273 }