nel/src/misc/aabbox.cpp

   1 // NeL - MMORPG Framework <http://dev.ryzom.com/projects/nel/>
   2 // Copyright (C) 2010  Winch Gate Property Limited
   3 //
   4 // This program is free software: you can redistribute it and/or modify
   5 // it under the terms of the GNU Affero General Public License as
   6 // published by the Free Software Foundation, either version 3 of the
   7 // License, or (at your option) any later version.
   8 //
   9 // This program 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 Affero General Public License for more details.
  13 //
  14 // You should have received a copy of the GNU Affero General Public License
  15 // along with this program.  If not, see <http://www.gnu.org/licenses/>.
  16
  17 #include "stdmisc.h"
  18
  19 #include "nel/misc/aabbox.h"
  20 #include "nel/misc/polygon.h"
  21 #include "nel/misc/bsphere.h"
  22 #include "nel/misc/matrix.h"
  23
  24 #ifdef DEBUG_NEW
  25         #define new DEBUG_NEW
  26 #endif
  27
  28 namespace NLMISC {
  29
  30
  31 // ***************************************************************************
  32 bool    CAABBox::clipFront(const CPlane &p) const
  33 {
  34         CVector         hswap;
  35
  36         // The bbox is front of the plane if only one of his vertex is in front.
  37         if(p*(Center + HalfSize) > 0)   return true;
  38         if(p*(Center - HalfSize) > 0)   return true;
  39         hswap.set(-HalfSize.x, HalfSize.y, HalfSize.z);
  40         if(p*(Center + hswap) > 0)      return true;
  41         if(p*(Center - hswap) > 0)      return true;
  42         hswap.set(HalfSize.x, -HalfSize.y, HalfSize.z);
  43         if(p*(Center + hswap) > 0)      return true;
  44         if(p*(Center - hswap) > 0)      return true;
  45         hswap.set(HalfSize.x, HalfSize.y, -HalfSize.z);
  46         if(p*(Center + hswap) > 0)      return true;
  47         if(p*(Center - hswap) > 0)      return true;
  48
  49         return false;
  50 }
  51 // ***************************************************************************
  52 bool    CAABBox::clipBack(const CPlane &p) const
  53 {
  54         CVector         hswap;
  55
  56         // The bbox is back of the plane if only one of his vertex is in back.
  57         if(p*(Center + HalfSize) < 0)   return true;
  58         if(p*(Center - HalfSize) < 0)   return true;
  59         hswap.set(-HalfSize.x, HalfSize.y, HalfSize.z);
  60         if(p*(Center + hswap) < 0)      return true;
  61         if(p*(Center - hswap) < 0)      return true;
  62         hswap.set(HalfSize.x, -HalfSize.y, HalfSize.z);
  63         if(p*(Center + hswap) < 0)      return true;
  64         if(p*(Center - hswap) < 0)      return true;
  65         hswap.set(HalfSize.x, HalfSize.y, -HalfSize.z);
  66         if(p*(Center + hswap) < 0)      return true;
  67         if(p*(Center - hswap) < 0)      return true;
  68
  69         return false;
  70 }
  71
  72
  73 // ***************************************************************************
  74 bool                    CAABBox::include(const CVector &a) const
  75 {
  76         if(Center.x+HalfSize.x<a.x)     return false;
  77         if(Center.x-HalfSize.x>a.x)     return false;
  78         if(Center.y+HalfSize.y<a.y)     return false;
  79         if(Center.y-HalfSize.y>a.y)     return false;
  80         if(Center.z+HalfSize.z<a.z)     return false;
  81         if(Center.z-HalfSize.z>a.z)     return false;
  82         return true;
  83 }
  84
  85
  86 // ***************************************************************************
  87 bool                    CAABBox::include(const CAABBox &box) const
  88 {
  89         if(Center.x+HalfSize.x < box.Center.x+box.HalfSize.x)   return false;
  90         if(Center.x-HalfSize.x > box.Center.x-box.HalfSize.x)   return false;
  91         if(Center.y+HalfSize.y < box.Center.y+box.HalfSize.y)   return false;
  92         if(Center.y-HalfSize.y > box.Center.y-box.HalfSize.y)   return false;
  93         if(Center.z+HalfSize.z < box.Center.z+box.HalfSize.z)   return false;
  94         if(Center.z-HalfSize.z > box.Center.z-box.HalfSize.z)   return false;
  95         return true;
  96 }
  97
  98
  99 // ***************************************************************************
 100 bool                    CAABBox::intersect(const CAABBox &box) const
 101 {
 102         CVector mina = getMin(), maxa = getMax(),
 103                         minb = box.getMin(), maxb = box.getMax();
 104
 105         return ! ( mina.x > maxb.x ||
 106                            mina.y > maxb.y ||
 107                            mina.z > maxb.z ||
 108                            minb.x > maxa.x ||
 109                            minb.y > maxa.y ||
 110                            minb.z > maxa.z);
 111 }
 112
 113 // ***************************************************************************
 114 bool                    CAABBox::intersect(const CVector &a, const CVector &b, const CVector &c) const
 115 {
 116         // Trivial test.
 117         if(include(a) || include(b) || include(c))
 118                 return true;
 119         // Else, must test if the polygon intersect the pyamid.
 120         CPlane          planes[6];
 121         makePyramid(planes);
 122         CPolygon        poly(a,b,c);
 123         poly.clip(planes, 6);
 124         if(poly.getNumVertices()==0)
 125                 return false;
 126         return true;
 127 }
 128
 129 // ***************************************************************************
 130 bool                    CAABBox::intersect(const CVector &a, const CVector &b) const
 131 {
 132         // Trivial test.
 133         if(include(a) || include(b))
 134                 return true;
 135         // Else, must test if the segment intersect the pyamid.
 136         CPlane          planes[6];
 137         makePyramid(planes);
 138         CVector         p0=a , p1=b;
 139         // clip the segment against all planes
 140         for(uint i=0;i<6;i++)
 141         {
 142                 if(!planes[i].clipSegmentBack(p0, p1))
 143                         return false;
 144         }
 145         return true;
 146 }
 147
 148 // ***************************************************************************
 149 bool                    CAABBox::clipSegment(CVector &a, CVector &b) const
 150 {
 151         // Trivial test. If both are in, they are inchanged
 152         if(include(a) && include(b))
 153                 return true;
 154         // Else, must clip the segment againts the pyamid.
 155         CPlane          planes[6];
 156         makePyramid(planes);
 157         CVector         p0=a , p1=b;
 158         // clip the segment against all planes
 159         for(uint i=0;i<6;i++)
 160         {
 161                 if(!planes[i].clipSegmentBack(p0, p1))
 162                         return false;
 163         }
 164         // get result
 165         a= p0;
 166         b= p1;
 167         return true;
 168 }
 169
 170 // ***************************************************************************
 171 bool                    CAABBox::intersect(const CBSphere &s) const
 172 {
 173         if (Center.x + HalfSize.x < s.Center.x - s.Radius) return false;
 174         if (Center.y + HalfSize.y < s.Center.y - s.Radius) return false;
 175         if (Center.z + HalfSize.z < s.Center.z - s.Radius) return false;
 176
 177         if (Center.x - HalfSize.x > s.Center.x + s.Radius) return false;
 178         if (Center.y - HalfSize.y > s.Center.y + s.Radius) return false;
 179         if (Center.z - HalfSize.z > s.Center.z + s.Radius) return false;
 180
 181         return true;
 182 }
 183
 184
 185
 186 // ***************************************************************************
 187 void                    CAABBox::makePyramid(CPlane     planes[6]) const
 188 {
 189         planes[0].make(CVector(-1,0,0), Center-HalfSize);
 190         planes[1].make(CVector(+1,0,0), Center+HalfSize);
 191         planes[2].make(CVector(0,-1,0), Center-HalfSize);
 192         planes[3].make(CVector(0,+1,0), Center+HalfSize);
 193         planes[4].make(CVector(0,0,-1), Center-HalfSize);
 194         planes[5].make(CVector(0,0,+1), Center+HalfSize);
 195 }
 196
 197
 198 // ***************************************************************************
 199 void                    CAABBox::serial(NLMISC::IStream &f)
 200 {
 201         /* ***********************************************
 202          *      WARNING: This Class/Method must be thread-safe (ctor/dtor/serial): no static access for instance
 203          *      It can be loaded/called through CAsyncFileManager for instance
 204          * ***********************************************/
 205         (void)f.serialVersion(0);
 206         f.serial(Center);
 207         f.serial(HalfSize);
 208 }
 209
 210
 211 // ***************************************************************************
 212 void    CAABBox::extend(const CVector &v)
 213 {
 214         CVector         bmin= getMin(), bmax= getMax();
 215
 216         bmin.minof(bmin, v);
 217         bmax.maxof(bmax, v);
 218         setMinMax(bmin, bmax);
 219 }
 220
 221
 222 //==========================================================================
 223 /**
 224 * Compute the union of 2 aabboxes, that is the  aabbox that contains the 2.
 225 * Should end up in NLMISC
 226 */
 227
 228 CAABBox CAABBox::computeAABBoxUnion(const CAABBox &b1, const CAABBox &b2)
 229 {
 230         CAABBox result;
 231         CVector min, max;
 232         CVector min1 = b1.getMin()
 233                     ,max1 = b1.getMax()
 234                         ,min2 = b2.getMin()
 235                     ,max2 = b2.getMax();
 236         max.maxof(max1, max2);
 237         min.minof(min1, min2);
 238         result.setMinMax(min, max);
 239         return result;
 240 }
 241
 242
 243 //==========================================================================
 244 void    CAABBox::computeIntersection(const CAABBox &b1, const CAABBox &b2)
 245 {
 246         CVector min1 = b1.getMin(), max1 = b1.getMax(),
 247                         min2 = b2.getMin(), max2 = b2.getMax();
 248         CVector minr, maxr;
 249
 250         // don't test if intersect or not.
 251         maxr.minof(max1, max2);
 252         minr.maxof(min1, min2);
 253
 254         setMinMax(minr, maxr);
 255 }
 256
 257
 258 //==========================================================================
 259 CAABBox CAABBox::transformAABBox(const CMatrix &mat, const CAABBox &box)
 260 {
 261         // TODO : optimize this a bit if possible...
 262         CAABBox result;
 263
 264         /* OMG. Old code was false!!
 265                 if we have ht= M * h
 266                 then CVector(-ht.x, ht.y, ht.z) != M * CVector(-h.x, h.y, h.z) !!!!
 267         */
 268         // compute corners.
 269         CVector p[8];
 270         CVector min= box.getMin();
 271         CVector max= box.getMax();
 272         p[0].set(min.x, min.y, min.z);
 273         p[1].set(max.x, min.y, min.z);
 274         p[2].set(min.x, max.y, min.z);
 275         p[3].set(max.x, max.y, min.z);
 276         p[4].set(min.x, min.y, max.z);
 277         p[5].set(max.x, min.y, max.z);
 278         p[6].set(min.x, max.y, max.z);
 279         p[7].set(max.x, max.y, max.z);
 280         CVector tmp;
 281         min = max = mat * p[0];
 282         // transform corners.
 283         for(uint i=1;i<8;i++)
 284         {
 285                 tmp= mat * p[i];
 286                 min.minof(min, tmp);
 287                 max.maxof(max, tmp);
 288         }
 289
 290         result.setMinMax(min, max);
 291
 292         return result;
 293 }
 294
 295
 296
 297 // ***************************************************************************
 298 bool    CAABBoxExt::clipFront(const CPlane &p) const
 299 {
 300         // Assume normalized planes.
 301
 302         // if( SpherMax OUT )   return false.
 303         float   d= p*Center;
 304         if(d<-RadiusMax)
 305                 return false;
 306         // if( SphereMin IN )   return true;
 307         if(d>-RadiusMin)
 308                 return true;
 309
 310         // else, standard clip box.
 311         return CAABBox::clipFront(p);
 312 }
 313
 314
 315 // ***************************************************************************
 316 bool    CAABBoxExt::clipBack(const CPlane &p) const
 317 {
 318         // Assume normalized planes.
 319
 320         // if( SpherMax OUT )   return false.
 321         float   d= p*Center;
 322         if(d>RadiusMax)
 323                 return false;
 324         // if( SphereMin IN )   return true;
 325         if(d<RadiusMin)
 326                 return true;
 327
 328         // else, standard clip box.
 329         return CAABBox::clipBack(p);
 330 }
 331
 332
 333 // ***************************************************************************
 334 void                    CAABBoxExt::serial(NLMISC::IStream &f)
 335 {
 336         /* ***********************************************
 337          *      WARNING: This Class/Method must be thread-safe (ctor/dtor/serial): no static access for instance
 338          *      It can be loaded/called through CAsyncFileManager for instance
 339          * ***********************************************/
 340         CAABBox::serial(f);
 341         if(f.isReading())
 342                 updateRadius();
 343 }
 344
 345
 346 } // NLMISC