Nori
|
00001 /* 00002 This file is part of Nori, a simple educational ray tracer 00003 00004 Copyright (c) 2012 by Wenzel Jakob and Steve Marschner. 00005 00006 Nori is free software; you can redistribute it and/or modify 00007 it under the terms of the GNU General Public License Version 3 00008 as published by the Free Software Foundation. 00009 00010 Nori is distributed in the hope that it will be useful, 00011 but WITHOUT ANY WARRANTY; without even the implied warranty of 00012 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 00013 GNU General Public License for more details. 00014 00015 You should have received a copy of the GNU General Public License 00016 along with this program. If not, see <http://www.gnu.org/licenses/>. 00017 */ 00018 00019 #if !defined(__BBOX_H) 00020 #define __BBOX_H 00021 00022 #include <nori/ray.h> 00023 00024 NORI_NAMESPACE_BEGIN 00025 00026 /** 00027 * \brief Generic n-dimensional bounding box data structure 00028 * 00029 * Maintains a minimum and maximum position along each dimension and provides 00030 * various convenience functions for querying and modifying them. 00031 * 00032 * This class is parameterized by the underlying point data structure, 00033 * which permits the use of different scalar types and dimensionalities, e.g. 00034 * \code 00035 * TBoundingBox<Vector3i> integerBBox(Point3i(0, 1, 3), Point3i(4, 5, 6)); 00036 * TBoundingBox<Vector2d> doubleBBox(Point2d(0.0, 1.0), Point2d(4.0, 5.0)); 00037 * \endcode 00038 * 00039 * \tparam T The underlying point data type (e.g. \c Point2d) 00040 * \ingroup libcore 00041 */ 00042 template <typename _PointType> struct TBoundingBox { 00043 enum { 00044 Dimension = _PointType::Dimension 00045 }; 00046 00047 typedef _PointType PointType; 00048 typedef typename PointType::Scalar Scalar; 00049 typedef typename PointType::VectorType VectorType; 00050 00051 /** 00052 * \brief Create a new invalid bounding box 00053 * 00054 * Initializes the components of the minimum 00055 * and maximum position to \f$\infty\f$ and \f$-\infty\f$, 00056 * respectively. 00057 */ 00058 inline TBoundingBox() { 00059 reset(); 00060 } 00061 00062 /// Create a collapsed bounding box from a single point 00063 inline TBoundingBox(const PointType &p) 00064 : min(p), max(p) { } 00065 00066 /// Create a bounding box from two positions 00067 inline TBoundingBox(const PointType &min, const PointType &max) 00068 : min(min), max(max) { 00069 } 00070 00071 /// Test for equality against another bounding box 00072 inline bool operator==(const TBoundingBox &bbox) const { 00073 return min == bbox.min && max == bbox.max; 00074 } 00075 00076 /// Test for inequality against another bounding box 00077 inline bool operator!=(const TBoundingBox &bbox) const { 00078 return min != bbox.min || max != bbox.max; 00079 } 00080 00081 /// Calculate the n-dimensional volume of the bounding box 00082 inline Scalar getVolume() const { 00083 return (max - min).prod(); 00084 } 00085 00086 /// Calculate the n-1 dimensional volume of the boundary 00087 inline float getSurfaceArea() const { 00088 VectorType d = max - min; 00089 float result = 0.0f; 00090 for (int i=0; i<Dimension; ++i) { 00091 float term = 1.0f; 00092 for (int j=0; j<Dimension; ++j) { 00093 if (i == j) 00094 continue; 00095 term *= d[j]; 00096 } 00097 result += term; 00098 } 00099 return 2.0f * result; 00100 } 00101 00102 /// Return the center point 00103 inline PointType getCenter() const { 00104 return (max + min) * (Scalar) 0.5f; 00105 } 00106 00107 /** 00108 * \brief Check whether a point lies \a on or \a inside the bounding box 00109 * 00110 * \param p The point to be tested 00111 * 00112 * \param strict Set this parameter to \c true if the bounding 00113 * box boundary should be excluded in the test 00114 */ 00115 inline bool contains(const PointType &p, bool strict = false) const { 00116 if (strict) { 00117 return (p.array() > min.array()).all() 00118 && (p.array() < max.array()).all(); 00119 } else { 00120 return (p.array() >= min.array()).all() 00121 && (p.array() <= max.array()).all(); 00122 } 00123 } 00124 00125 /** 00126 * \brief Check whether a specified bounding box lies \a on or \a within 00127 * the current bounding box 00128 * 00129 * Note that by definition, an 'invalid' bounding box (where min=\f$\infty\f$ 00130 * and max=\f$-\infty\f$) does not cover any space. Hence, this method will always 00131 * return \a true when given such an argument. 00132 * 00133 * \param strict Set this parameter to \c true if the bounding 00134 * box boundary should be excluded in the test 00135 */ 00136 inline bool contains(const TBoundingBox &bbox, bool strict = false) const { 00137 if (strict) { 00138 return (bbox.min.array() > min.array()).all() 00139 && (bbox.max.array() < max.array()).all(); 00140 } else { 00141 return (bbox.min.array() >= min.array()).all() 00142 && (bbox.max.array() <= max.array()).all(); 00143 } 00144 } 00145 00146 /** 00147 * \brief Check two axis-aligned bounding boxes for possible overlap. 00148 * 00149 * \param strict Set this parameter to \c true if the bounding 00150 * box boundary should be excluded in the test 00151 * 00152 * \return \c true If overlap was detected. 00153 */ 00154 inline bool overlaps(const TBoundingBox &bbox, bool strict = false) const { 00155 if (strict) { 00156 return (bbox.min.array() < max.array()).all() 00157 && (bbox.max.array() > min.array()).all(); 00158 } else { 00159 return (bbox.min.array() <= max.array()).all() 00160 && (bbox.max.array() >= min.array()).all(); 00161 } 00162 } 00163 00164 /** 00165 * \brief Calculate the smallest squared distance between 00166 * the axis-aligned bounding box and the point \c p. 00167 */ 00168 inline Scalar squaredDistanceTo(const PointType &p) const { 00169 Scalar result = 0; 00170 00171 for (int i=0; i<Dimension; ++i) { 00172 Scalar value = 0; 00173 if (p[i] < min[i]) 00174 value = min[i] - p[i]; 00175 else if (p[i] > max[i]) 00176 value = p[i] - max[i]; 00177 result += value*value; 00178 } 00179 00180 return result; 00181 } 00182 00183 /** 00184 * \brief Calculate the smallest distance between 00185 * the axis-aligned bounding box and the point \c p. 00186 */ 00187 inline Scalar distanceTo(const PointType &p) const { 00188 return std::sqrt(squaredDistanceTo(p)); 00189 } 00190 00191 /** 00192 * \brief Calculate the smallest square distance between 00193 * the axis-aligned bounding box and \c bbox. 00194 */ 00195 inline Scalar squaredDistanceTo(const TBoundingBox &bbox) const { 00196 Scalar result = 0; 00197 00198 for (int i=0; i<Dimension; ++i) { 00199 Scalar value = 0; 00200 if (bbox.max[i] < min[i]) 00201 value = min[i] - bbox.max[i]; 00202 else if (bbox.min[i] > max[i]) 00203 value = bbox.min[i] - max[i]; 00204 result += value*value; 00205 } 00206 00207 return result; 00208 } 00209 00210 /** 00211 * \brief Calculate the smallest distance between 00212 * the axis-aligned bounding box and \c bbox. 00213 */ 00214 inline Scalar distanceTo(const TBoundingBox &bbox) const { 00215 return std::sqrt(squaredDistanceTo(bbox)); 00216 } 00217 00218 /** 00219 * \brief Check whether this is a valid bounding box 00220 * 00221 * A bounding box \c bbox is valid when 00222 * \code 00223 * bbox.min[dim] <= bbox.max[dim] 00224 * \endcode 00225 * holds along each dimension \c dim. 00226 */ 00227 inline bool isValid() const { 00228 return (max.array() >= min.array()).all(); 00229 } 00230 00231 /// Check whether this bounding box has collapsed to a single point 00232 inline bool isPoint() const { 00233 return (max.array() == min.array()).all(); 00234 } 00235 00236 /// Check whether this bounding box has any associated volume 00237 inline bool hasVolume() const { 00238 return (max.array() > min.array()).all(); 00239 } 00240 00241 /// Return the dimension index with the largest associated side length 00242 inline int getMajorAxis() const { 00243 VectorType d = max - min; 00244 int largest = 0; 00245 for (int i=1; i<Dimension; ++i) 00246 if (d[i] > d[largest]) 00247 largest = i; 00248 return largest; 00249 } 00250 00251 /// Return the dimension index with the shortest associated side length 00252 inline int getMinorAxis() const { 00253 VectorType d = max - min; 00254 int shortest = 0; 00255 for (int i=1; i<Dimension; ++i) 00256 if (d[i] < d[shortest]) 00257 shortest = i; 00258 return shortest; 00259 } 00260 00261 /** 00262 * \brief Calculate the bounding box extents 00263 * \return max-min 00264 */ 00265 inline VectorType getExtents() const { 00266 return max - min; 00267 } 00268 00269 /// Clip to another bounding box 00270 inline void clip(const TBoundingBox &bbox) { 00271 min = min.cwiseMax(bbox.min); 00272 max = max.cwiseMin(bbox.max); 00273 } 00274 00275 /** 00276 * \brief Mark the bounding box as invalid. 00277 * 00278 * This operation sets the components of the minimum 00279 * and maximum position to \f$\infty\f$ and \f$-\infty\f$, 00280 * respectively. 00281 */ 00282 inline void reset() { 00283 min.setConstant( std::numeric_limits<Scalar>::infinity()); 00284 max.setConstant(-std::numeric_limits<Scalar>::infinity()); 00285 } 00286 00287 /// Expand the bounding box to contain another point 00288 inline void expandBy(const PointType &p) { 00289 min = min.cwiseMin(p); 00290 max = max.cwiseMax(p); 00291 } 00292 00293 /// Expand the bounding box to contain another bounding box 00294 inline void expandBy(const TBoundingBox &bbox) { 00295 min = min.cwiseMin(bbox.min); 00296 max = max.cwiseMax(bbox.max); 00297 } 00298 00299 /// Return the position of a bounding box corner 00300 inline PointType getCorner(int index) const { 00301 PointType result; 00302 for (int i=0; i<Dimension; ++i) 00303 result[i] = (index & (1 << i)) ? max[i] : min[i]; 00304 return result; 00305 } 00306 00307 /// Return a string representation of the bounding box 00308 inline QString toString() const { 00309 QString result("BoundingBox["); 00310 if (!isValid()) 00311 result += "invalid"; 00312 else 00313 result += QString("min=%1, max=%2") 00314 .arg(min.toString()) 00315 .arg(max.toString()); 00316 return result + "]"; 00317 } 00318 00319 /** \brief Calculate the near and far ray-box intersection 00320 * points (if they exist). 00321 * 00322 * Also returns intersections along the negative ray direction. 00323 */ 00324 inline bool rayIntersect(const TRay<PointType, VectorType> &ray, Scalar &nearT, Scalar &farT) const { 00325 nearT = -std::numeric_limits<Scalar>::infinity(); 00326 farT = std::numeric_limits<Scalar>::infinity(); 00327 00328 /* For each pair of bounding box planes */ 00329 for (int i=0; i<Dimension; i++) { 00330 const Scalar 00331 rayO = ray.o[i], 00332 rayD = ray.d[i], 00333 minVal = min[i], 00334 maxVal = max[i]; 00335 00336 if (rayD == 0) { 00337 /* The ray is parallel to the planes */ 00338 if (rayO < minVal || rayO > maxVal) 00339 return false; 00340 } else { 00341 /* Calculate intersection distances */ 00342 Scalar t1 = (minVal - rayO) * ray.dRcp[i]; 00343 Scalar t2 = (maxVal - rayO) * ray.dRcp[i]; 00344 00345 if (t1 > t2) 00346 std::swap(t1, t2); 00347 00348 nearT = std::max(nearT, t1); 00349 farT = std::min(farT, t2); 00350 00351 if (nearT > farT) 00352 return false; 00353 } 00354 } 00355 return true; 00356 } 00357 00358 PointType min; ///< Component-wise minimum 00359 PointType max; ///< Component-wise maximum 00360 }; 00361 00362 00363 NORI_NAMESPACE_END 00364 00365 #endif /* __BBOX_H */