openscenegraph
BoundingSphere
Go to the documentation of this file.
1/* -*-c++-*- OpenSceneGraph - Copyright (C) 1998-2006 Robert Osfield
2 *
3 * This library is open source and may be redistributed and/or modified under
4 * the terms of the OpenSceneGraph Public License (OSGPL) version 0.0 or
5 * (at your option) any later version. The full license is in LICENSE file
6 * included with this distribution, and on the openscenegraph.org website.
7 *
8 * This library is distributed in the hope that it will be useful,
9 * but WITHOUT ANY WARRANTY; without even the implied warranty of
10 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
11 * OpenSceneGraph Public License for more details.
12*/
13
14#ifndef OSG_BOUNDINGSPHERE
15#define OSG_BOUNDINGSPHERE 1
16
17#include <osg/Config>
18#include <osg/Export>
19#include <osg/Vec3f>
20#include <osg/Vec3d>
21
22namespace osg {
23
24template<typename VT>
25class BoundingBoxImpl;
26
27/** General purpose bounding sphere class for enclosing nodes/objects/vertices.
28 * Bounds internal osg::Nodes in the scene, assists in view frustum culling,
29 * etc. Similar in function to BoundingBox, it's quicker for evaluating
30 * culling but generally will not cull as aggressively because it encloses a
31 * greater volume.
32*/
33template<typename VT>
34class BoundingSphereImpl
35{
36 public:
37 typedef VT vec_type;
38 typedef typename VT::value_type value_type;
39
40 vec_type _center;
41 value_type _radius;
42
43 /** Construct a default bounding sphere with radius to -1.0f, representing an invalid/unset bounding sphere.*/
44 BoundingSphereImpl() : _center(0.0,0.0,0.0),_radius(-1.0) {}
45
46 /** Creates a bounding sphere initialized to the given extents. */
47 BoundingSphereImpl(const vec_type& cntr, value_type rad) : _center(cntr),_radius(rad) {}
48
49 /** Creates a bounding sphere initialized to the given extents. */
50 BoundingSphereImpl(const BoundingSphereImpl& bs) : _center(bs._center),_radius(bs._radius) {}
51
52 /** Creates a bounding sphere initialized to the given extents. */
53 BoundingSphereImpl(const BoundingBoxImpl<VT>& bb) : _center(0.0,0.0,0.0),_radius(-1.0) { expandBy(bb); }
54
55 BoundingSphereImpl& operator= (const BoundingSphereImpl &o){
56 _center = o._center;
57 _radius = o._radius;
58 return *this;
59 }
60
61 /** Clear the bounding sphere. Reset to default values. */
62 inline void init()
63 {
64 _center.set(0.0,0.0,0.0);
65 _radius = -1.0;
66 }
67
68 /** Returns true of the bounding sphere extents are valid, false
69 * otherwise. */
70 inline bool valid() const { return _radius>=0.0; }
71
72 inline bool operator == (const BoundingSphereImpl& rhs) const { return _center==rhs._center && _radius==rhs._radius; }
73 inline bool operator != (const BoundingSphereImpl& rhs) const { return _center!=rhs._center || _radius!=rhs._radius; }
74
75 /** Set the bounding sphere to the given center/radius using floats. */
76 inline void set(const vec_type& center,value_type radius)
77 {
78 _center = center;
79 _radius = radius;
80 }
81
82 /** Returns the center of the bounding sphere. */
83 inline vec_type& center() { return _center; }
84
85 /** Returns the const center of the bounding sphere. */
86 inline const vec_type& center() const { return _center; }
87
88 /** Returns the radius of the bounding sphere. */
89 inline value_type& radius() { return _radius; }
90 /** Returns the const radius of the bounding sphere. */
91 inline value_type radius() const { return _radius; }
92
93 /** Returns the squared length of the radius. Note, For performance
94 * reasons, the calling method is responsible for checking to make
95 * sure the sphere is valid. */
96 inline value_type radius2() const { return _radius*_radius; }
97
98 /** Expands the sphere to encompass the given point. Repositions the
99 * sphere center to minimize the radius increase. If the sphere is
100 * uninitialized, set its center to v and radius to zero. */
101 template<typename vector_type>
102 void expandBy(const vector_type& v);
103
104 /** Expands the sphere to encompass the given point. Does not
105 * reposition the sphere center. If the sphere is
106 * uninitialized, set its center to v and radius to zero. */
107 template<typename vector_type>
108 void expandRadiusBy(const vector_type& v);
109
110 /** Expands the sphere to encompass the given sphere. Repositions the
111 * sphere center to minimize the radius increase. If the sphere is
112 * uninitialized, set its center and radius to match sh. */
113 void expandBy(const BoundingSphereImpl& sh);
114
115 /** Expands the sphere to encompass the given sphere. Does not
116 * repositions the sphere center. If the sphere is
117 * uninitialized, set its center and radius to match sh. */
118 void expandRadiusBy(const BoundingSphereImpl& sh);
119
120 /** Expands the sphere to encompass the given box. Repositions the
121 * sphere center to minimize the radius increase. */
122 template<typename BBT>
123 void expandBy(const BoundingBoxImpl<BBT>& bb);
124
125 /** Expands the sphere to encompass the given box. Does not
126 * repositions the sphere center. */
127 template<typename BBT>
128 void expandRadiusBy(const BoundingBoxImpl<BBT>& bb);
129
130 /** Returns true if v is within the sphere. */
131 inline bool contains(const vec_type& v) const
132 {
133 return valid() && ((v-_center).length2()<=radius2());
134 }
135
136
137 /** Returns true if there is a non-empty intersection with the given
138 * bounding sphere. */
139 inline bool intersects( const BoundingSphereImpl& bs ) const
140 {
141 return valid() && bs.valid() &&
142 ((_center - bs._center).length2() <= (_radius + bs._radius)*(_radius + bs._radius));
143 }
144};
145
146
147template<typename VT>
148template<typename vector_type>
149void BoundingSphereImpl<VT>::expandBy(const vector_type& v)
150{
151 if (valid())
152 {
153 vec_type dv = vec_type(v)-_center;
154 value_type r = dv.length();
155 if (r>_radius)
156 {
157 value_type dr = (r-_radius)*0.5;
158 _center += dv*(dr/r);
159 _radius += dr;
160 } // else do nothing as vertex is within sphere.
161 }
162 else
163 {
164 _center = v;
165 _radius = 0.0;
166 }
167}
168
169template<typename VT>
170template<typename vector_type>
171void BoundingSphereImpl<VT>::expandRadiusBy(const vector_type& v)
172{
173 if (valid())
174 {
175 value_type r = (vec_type(v)-_center).length();
176 if (r>_radius) _radius = r;
177 // else do nothing as vertex is within sphere.
178 }
179 else
180 {
181 _center = v;
182 _radius = 0.0;
183 }
184}
185
186template<typename VT>
187void BoundingSphereImpl<VT>::expandBy(const BoundingSphereImpl& sh)
188{
189 // ignore operation if incoming BoundingSphere is invalid.
190 if (!sh.valid()) return;
191
192 // This sphere is not set so use the inbound sphere
193 if (!valid())
194 {
195 _center = sh._center;
196 _radius = sh._radius;
197
198 return;
199 }
200
201
202 // Calculate d == The distance between the sphere centers
203 double d = ( _center - sh.center() ).length();
204
205 // New sphere is already inside this one
206 if ( d + sh.radius() <= _radius )
207 {
208 return;
209 }
210
211 // New sphere completely contains this one
212 if ( d + _radius <= sh.radius() )
213 {
214 _center = sh._center;
215 _radius = sh._radius;
216 return;
217 }
218
219
220 // Build a new sphere that completely contains the other two:
221 //
222 // The center point lies halfway along the line between the furthest
223 // points on the edges of the two spheres.
224 //
225 // Computing those two points is ugly - so we'll use similar triangles
226 double new_radius = (_radius + d + sh.radius() ) * 0.5;
227 double ratio = ( new_radius - _radius ) / d ;
228
229 _center[0] += ( sh.center()[0] - _center[0] ) * ratio;
230 _center[1] += ( sh.center()[1] - _center[1] ) * ratio;
231 _center[2] += ( sh.center()[2] - _center[2] ) * ratio;
232
233 _radius = new_radius;
234
235}
236
237template<typename VT>
238void BoundingSphereImpl<VT>::expandRadiusBy(const BoundingSphereImpl& sh)
239{
240 if (sh.valid())
241 {
242 if (valid())
243 {
244 value_type r = (sh._center-_center).length()+sh._radius;
245 if (r>_radius) _radius = r;
246 // else do nothing as vertex is within sphere.
247 }
248 else
249 {
250 _center = sh._center;
251 _radius = sh._radius;
252 }
253 }
254}
255
256template<typename VT>
257template<typename BBT>
258void BoundingSphereImpl<VT>::expandBy(const BoundingBoxImpl<BBT>& bb)
259{
260 if (bb.valid())
261 {
262 if (valid())
263 {
264 BoundingBoxImpl<vec_type> newbb(bb);
265
266 for(unsigned int c=0;c<8;++c)
267 {
268 vec_type v = bb.corner(c)-_center; // get the direction vector from corner
269 v.normalize(); // normalise it.
270 v *= -_radius; // move the vector in the opposite direction distance radius.
271 v += _center; // move to absolute position.
272 newbb.expandBy(v); // add it into the new bounding box.
273 }
274
275 _center = newbb.center();
276 _radius = newbb.radius();
277
278 }
279 else
280 {
281 _center = bb.center();
282 _radius = bb.radius();
283 }
284 }
285}
286
287template<typename VT>
288template<typename BBT>
289void BoundingSphereImpl<VT>::expandRadiusBy(const BoundingBoxImpl<BBT>& bb)
290{
291 if (bb.valid())
292 {
293 if (valid())
294 {
295 for(unsigned int c=0;c<8;++c)
296 {
297 expandRadiusBy(bb.corner(c));
298 }
299 }
300 else
301 {
302 _center = bb.center();
303 _radius = bb.radius();
304 }
305 }
306}
307
308typedef BoundingSphereImpl<Vec3f> BoundingSpheref;
309typedef BoundingSphereImpl<Vec3d> BoundingSphered;
310
311#ifdef OSG_USE_FLOAT_BOUNDINGSPHERE
312 typedef BoundingSpheref BoundingSphere;
313#else
314 typedef BoundingSphered BoundingSphere;
315#endif
316}
317
318#endif