Line data Source code
1 : /*
2 : * Copyright (c) 2006-2016, Visualization and Multimedia Lab,
3 : * University of Zurich <http://vmml.ifi.uzh.ch>,
4 : * Eyescale Software GmbH,
5 : * Blue Brain Project, EPFL
6 : *
7 : * This file is part of VMMLib <https://github.com/VMML/vmmlib/>
8 : *
9 : * Redistribution and use in source and binary forms, with or without
10 : * modification, are permitted provided that the following conditions are met:
11 : *
12 : * Redistributions of source code must retain the above copyright notice, this
13 : * list of conditions and the following disclaimer. Redistributions in binary
14 : * form must reproduce the above copyright notice, this list of conditions and
15 : * the following disclaimer in the documentation and/or other materials provided
16 : * with the distribution. Neither the name of the Visualization and Multimedia
17 : * Lab, University of Zurich nor the names of its contributors may be used to
18 : * endorse or promote products derived from this software without specific prior
19 : * written permission.
20 : * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
21 : * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
22 : * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
23 : * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
24 : * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
25 : * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
26 : * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
27 : * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
28 : * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
29 : * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
30 : * POSSIBILITY OF SUCH DAMAGE.
31 : */
32 : #ifndef __VMML__AXIS_ALIGNED_BOUNDING_BOX__HPP__
33 : #define __VMML__AXIS_ALIGNED_BOUNDING_BOX__HPP__
34 :
35 : #include <vmmlib/vector.hpp>
36 : #include <limits>
37 :
38 : namespace lunchbox { template< class T > void byteswap( T& ); }
39 :
40 : namespace vmml
41 : {
42 : /**
43 : * An axis-aligned bounding box.
44 : *
45 : * An empty bounding box has undefined, implementation-specific values. Read
46 : * operations (getMin(), getMax(), getSize(), isIn(), etc.) have undefined
47 : * semantics on an empty bounding box. set() and merge() operations will define
48 : * the bounding box correctly.
49 : */
50 : template< typename T > class AABB
51 : {
52 : public:
53 : /** Create an empty bounding box. */
54 : AABB();
55 :
56 : /** Create a new bounding box from two corner points */
57 : AABB( const vector< 3, T >& pMin, const vector< 3, T >& pMax );
58 :
59 : /** Create a new bounding box from a bounding sphere */
60 : AABB( const vector< 4, T >& sphere );
61 :
62 : /** @return true if the given point is within this bounding box. */
63 : bool isIn( const vector< 3, T >& point ) const;
64 :
65 : /** @return true if the given sphere is within this bounding box. */
66 : bool isIn( const vector< 4, T >& sphere ) const;
67 :
68 : /**
69 : * @return true if this bounding box is in front of the given plane
70 : * ([normal.x|y|z, d] notation).
71 : */
72 : bool isInFront( const vector< 4, T >& plane ) const;
73 :
74 : /** @return the minimum corner point */
75 : const vector< 3, T >& getMin() const;
76 :
77 : /** @return the maximum corner point */
78 : const vector< 3, T >& getMax() const;
79 :
80 : /** Create the union of this and the given bounding box */
81 : void merge( const AABB< T >& aabb );
82 :
83 : /** Create the union of this and the given point */
84 : void merge( const vector< 3, T >& point );
85 :
86 : /** Clear this bounding box */
87 : void reset();
88 :
89 : /** @return true if this bounding box has not been set */
90 : bool isEmpty() const;
91 :
92 : /** @return true if this and the other bounding box are identical */
93 : bool operator==( const AABB< T >& other ) const;
94 :
95 : /** @return true if this and the other bounding box are not identical */
96 : bool operator!=( const AABB< T >& other ) const;
97 :
98 : /** @return the center of this bounding box */
99 : vector< 3, T > getCenter() const;
100 :
101 : /** @return the size of this bounding box */
102 : vector< 3, T > getSize() const;
103 :
104 : /**
105 : * Compute the nearest and furthest point of this box relative to the given
106 : * plane.
107 : */
108 : void computeNearFar( const vector< 4, T >& plane, vector< 3, T >& nearPoint,
109 : vector< 3, T >& farPoint ) const;
110 :
111 : /** @return a bounding box of size one with the minimum point at zero. */
112 : static AABB< T > makeUnitBox();
113 :
114 : private:
115 : vector< 3, T > _min;
116 : vector< 3, T > _max;
117 : template< class U > friend void lunchbox::byteswap( U& );
118 : };
119 :
120 : template< typename T > inline
121 0 : std::ostream& operator << ( std::ostream& os, const AABB< T >& aabb )
122 : {
123 0 : return os << aabb.getMin() << " - " << aabb.getMax();
124 : }
125 :
126 : template< typename T > AABB< T >::AABB()
127 : : _min( std::numeric_limits< T >::max( ))
128 : , _max( std::numeric_limits< T >::min( ))
129 : {}
130 :
131 1 : template<> inline AABB< float >::AABB()
132 2 : : _min( std::numeric_limits< float >::max( ))
133 2 : , _max( -std::numeric_limits< float >::max( ))
134 1 : {}
135 :
136 : template<> inline AABB< double >::AABB()
137 : : _min( std::numeric_limits< double >::max( ))
138 : , _max( -std::numeric_limits< double >::max( ))
139 : {}
140 :
141 : template< typename T >
142 9 : AABB< T >::AABB( const vector< 3, T >& pMin, const vector< 3, T >& pMax)
143 9 : : _min( vector< 3, T >( std::min( pMin[0], pMax[0] ),
144 9 : std::min( pMin[1], pMax[1] ),
145 9 : std::min( pMin[2], pMax[2] )))
146 9 : , _max( vector< 3, T >( std::max( pMin[0], pMax[0] ),
147 9 : std::max( pMin[1], pMax[1] ),
148 45 : std::max( pMin[2], pMax[2] )))
149 9 : {}
150 :
151 : template< typename T > AABB< T >::AABB( const vector< 4, T >& sphere )
152 : {
153 : _max = _min = sphere.getCenter();
154 : _max += sphere.getRadius();
155 : _min -= sphere.getRadius();
156 : }
157 :
158 : template< typename T > inline bool AABB< T >::isIn( const vector< 3, T >& pos ) const
159 : {
160 : if ( pos.x() > _max.x() || pos.y() > _max.y() || pos.z() > _max.z() ||
161 : pos.x() < _min.x() || pos.y() < _min.y() || pos.z() < _min.z( ))
162 : {
163 : return false;
164 : }
165 : return true;
166 : }
167 :
168 : template< typename T > inline
169 : bool AABB< T >::isIn( const vector< 4, T >& sphere ) const
170 : {
171 : const vector< 3, T >& sv = sphere.getCenter();
172 : sv += sphere.getRadius();
173 : if ( sv.x() > _max.x() || sv.y() > _max.y() || sv.z() > _max.z() )
174 : return false;
175 : sv -= sphere.getRadius() * 2.0f;
176 : if ( sv.x() < _min.x() || sv.y() < _min.y() || sv.z() < _min.z() )
177 : return false;
178 : return true;
179 : }
180 :
181 : template< typename T > inline
182 6 : bool AABB< T >::isInFront( const vector< 4, T >& plane ) const
183 : {
184 6 : const auto& extent = getSize() * 0.5f;
185 6 : const float d = plane.dot( getCenter() );
186 12 : const float n = extent.x() * std::abs( plane.x( )) +
187 6 : extent.y() * std::abs( plane.y( )) +
188 6 : extent.z() * std::abs( plane.z( ));
189 :
190 6 : return !( d - n >= 0 || d + n > 0 );
191 : }
192 :
193 4 : template< typename T > inline const vector< 3, T >& AABB< T >::getMin() const
194 : {
195 4 : return _min;
196 : }
197 :
198 4 : template< typename T > inline const vector< 3, T >& AABB< T >::getMax() const
199 : {
200 4 : return _max;
201 : }
202 :
203 : template< typename T > inline
204 1 : bool AABB< T >::operator==( const AABB< T >& other ) const
205 : {
206 1 : return _min == other._min && _max == other._max;
207 : }
208 :
209 : template< typename T > inline
210 : bool AABB< T >::operator!=( const AABB< T >& other ) const
211 : {
212 : return _min != other._min || _max != other._max;
213 : }
214 :
215 13 : template< typename T > vector< 3, T > AABB< T >::getCenter() const
216 : {
217 13 : return ( _min + _max ) * 0.5f;
218 : }
219 :
220 15 : template< typename T > vector< 3, T > AABB< T >::getSize() const
221 : {
222 15 : return _max - _min;
223 : }
224 :
225 : template< typename T >
226 1 : void AABB< T >::merge( const AABB<T>& aabb )
227 : {
228 1 : const vector< 3, T >& min = aabb.getMin();
229 1 : const vector< 3, T >& max = aabb.getMax();
230 :
231 1 : if ( min.x() < _min.x() )
232 1 : _min.x() = min.x();
233 1 : if ( min.y() < _min.y() )
234 1 : _min.y() = min.y();
235 1 : if ( min.z() < _min.z() )
236 1 : _min.z() = min.z();
237 :
238 1 : if ( max.x() > _max.x() )
239 0 : _max.x() = max.x();
240 1 : if ( max.y() > _max.y() )
241 0 : _max.y() = max.y();
242 1 : if ( max.z() > _max.z() )
243 0 : _max.z() = max.z();
244 1 : }
245 :
246 : template< typename T >
247 2 : void AABB< T >::merge( const vector< 3, T >& point )
248 : {
249 2 : if ( point.x() < _min.x() )
250 1 : _min.x() = point.x();
251 2 : if ( point.y() < _min.y() )
252 1 : _min.y() = point.y();
253 2 : if ( point.z() < _min.z() )
254 1 : _min.z() = point.z();
255 :
256 2 : if ( point.x() > _max.x() )
257 2 : _max.x() = point.x();
258 2 : if ( point.y() > _max.y() )
259 2 : _max.y() = point.y();
260 2 : if ( point.z() > _max.z() )
261 2 : _max.z() = point.z();
262 2 : }
263 :
264 : template< typename T > inline void AABB< T >::reset()
265 : {
266 : _min = std::numeric_limits< T >::max();
267 : _max = -std::numeric_limits< T >::max();
268 : }
269 :
270 4 : template< typename T > inline bool AABB< T >::isEmpty() const
271 : {
272 4 : return _min.x() >= _max.x() || _min.y() >= _max.y() || _min.z() >= _max.x();
273 : }
274 :
275 : template< typename T > inline void
276 : AABB< T >::computeNearFar( const vector< 4, T >& plane,
277 : vector< 3, T >& nearPoint,
278 : vector< 3, T >& farPoint ) const
279 : {
280 : for( size_t i = 0; i < 3; ++i )
281 : {
282 : if( plane[ i ] >= 0.0 )
283 : {
284 : nearPoint[ i ] = _min[ i ];
285 : farPoint[ i ] = _max[ i ];
286 : }
287 : else
288 : {
289 : nearPoint[ i ] = _max[ i ];
290 : farPoint[ i ] = _min[ i ];
291 : }
292 : }
293 : }
294 :
295 2 : template< typename T > AABB< T > AABB< T >::makeUnitBox()
296 : {
297 2 : return AABB( vector< 3, T >(), vector< 3, T >( 1 ));
298 : }
299 :
300 : }
301 :
302 : #endif
|