1/* -*-c++-*- OpenSceneGraph - Copyright (C) 1998-2006 Robert Osfield
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.
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.
14#ifndef OSG_BOUNDINGSPHERE
15#define OSG_BOUNDINGSPHERE 1
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
34class BoundingSphereImpl
38 typedef typename VT::value_type value_type;
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) {}
46 /** Creates a bounding sphere initialized to the given extents. */
47 BoundingSphereImpl(const vec_type& cntr, value_type rad) : _center(cntr),_radius(rad) {}
49 /** Creates a bounding sphere initialized to the given extents. */
50 BoundingSphereImpl(const BoundingSphereImpl& bs) : _center(bs._center),_radius(bs._radius) {}
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); }
55 /** Clear the bounding sphere. Reset to default values. */
58 _center.set(0.0,0.0,0.0);
62 /** Returns true of the bounding sphere extents are valid, false
64 inline bool valid() const { return _radius>=0.0; }
66 inline bool operator == (const BoundingSphereImpl& rhs) const { return _center==rhs._center && _radius==rhs._radius; }
67 inline bool operator != (const BoundingSphereImpl& rhs) const { return _center!=rhs._center || _radius!=rhs._radius; }
69 /** Set the bounding sphere to the given center/radius using floats. */
70 inline void set(const vec_type& center,value_type radius)
76 /** Returns the center of the bounding sphere. */
77 inline vec_type& center() { return _center; }
79 /** Returns the const center of the bounding sphere. */
80 inline const vec_type& center() const { return _center; }
82 /** Returns the radius of the bounding sphere. */
83 inline value_type& radius() { return _radius; }
84 /** Returns the const radius of the bounding sphere. */
85 inline value_type radius() const { return _radius; }
87 /** Returns the squared length of the radius. Note, For performance
88 * reasons, the calling method is responsible for checking to make
89 * sure the sphere is valid. */
90 inline value_type radius2() const { return _radius*_radius; }
92 /** Expands the sphere to encompass the given point. Repositions the
93 * sphere center to minimize the radius increase. If the sphere is
94 * uninitialized, set its center to v and radius to zero. */
95 template<typename vector_type>
96 void expandBy(const vector_type& v);
98 /** Expands the sphere to encompass the given point. Does not
99 * reposition the sphere center. If the sphere is
100 * uninitialized, set its center to v and radius to zero. */
101 template<typename vector_type>
102 void expandRadiusBy(const vector_type& v);
104 /** Expands the sphere to encompass the given sphere. Repositions the
105 * sphere center to minimize the radius increase. If the sphere is
106 * uninitialized, set its center and radius to match sh. */
107 void expandBy(const BoundingSphereImpl& sh);
109 /** Expands the sphere to encompass the given sphere. Does not
110 * repositions the sphere center. If the sphere is
111 * uninitialized, set its center and radius to match sh. */
112 void expandRadiusBy(const BoundingSphereImpl& sh);
114 /** Expands the sphere to encompass the given box. Repositions the
115 * sphere center to minimize the radius increase. */
116 template<typename BBT>
117 void expandBy(const BoundingBoxImpl<BBT>& bb);
119 /** Expands the sphere to encompass the given box. Does not
120 * repositions the sphere center. */
121 template<typename BBT>
122 void expandRadiusBy(const BoundingBoxImpl<BBT>& bb);
124 /** Returns true if v is within the sphere. */
125 inline bool contains(const vec_type& v) const
127 return valid() && ((v-_center).length2()<=radius2());
131 /** Returns true if there is a non-empty intersection with the given
132 * bounding sphere. */
133 inline bool intersects( const BoundingSphereImpl& bs ) const
135 return valid() && bs.valid() &&
136 ((_center - bs._center).length2() <= (_radius + bs._radius)*(_radius + bs._radius));
142template<typename vector_type>
143void BoundingSphereImpl<VT>::expandBy(const vector_type& v)
147 vec_type dv = vec_type(v)-_center;
148 value_type r = dv.length();
151 value_type dr = (r-_radius)*0.5;
152 _center += dv*(dr/r);
154 } // else do nothing as vertex is within sphere.
164template<typename vector_type>
165void BoundingSphereImpl<VT>::expandRadiusBy(const vector_type& v)
169 value_type r = (vec_type(v)-_center).length();
170 if (r>_radius) _radius = r;
171 // else do nothing as vertex is within sphere.
181void BoundingSphereImpl<VT>::expandBy(const BoundingSphereImpl& sh)
183 // ignore operation if incoming BoundingSphere is invalid.
184 if (!sh.valid()) return;
186 // This sphere is not set so use the inbound sphere
189 _center = sh._center;
190 _radius = sh._radius;
196 // Calculate d == The distance between the sphere centers
197 double d = ( _center - sh.center() ).length();
199 // New sphere is already inside this one
200 if ( d + sh.radius() <= _radius )
205 // New sphere completely contains this one
206 if ( d + _radius <= sh.radius() )
208 _center = sh._center;
209 _radius = sh._radius;
214 // Build a new sphere that completely contains the other two:
216 // The center point lies halfway along the line between the furthest
217 // points on the edges of the two spheres.
219 // Computing those two points is ugly - so we'll use similar triangles
220 double new_radius = (_radius + d + sh.radius() ) * 0.5;
221 double ratio = ( new_radius - _radius ) / d ;
223 _center[0] += ( sh.center()[0] - _center[0] ) * ratio;
224 _center[1] += ( sh.center()[1] - _center[1] ) * ratio;
225 _center[2] += ( sh.center()[2] - _center[2] ) * ratio;
227 _radius = new_radius;
232void BoundingSphereImpl<VT>::expandRadiusBy(const BoundingSphereImpl& sh)
238 value_type r = (sh._center-_center).length()+sh._radius;
239 if (r>_radius) _radius = r;
240 // else do nothing as vertex is within sphere.
244 _center = sh._center;
245 _radius = sh._radius;
251template<typename BBT>
252void BoundingSphereImpl<VT>::expandBy(const BoundingBoxImpl<BBT>& bb)
258 BoundingBoxImpl<vec_type> newbb(bb);
260 for(unsigned int c=0;c<8;++c)
262 vec_type v = bb.corner(c)-_center; // get the direction vector from corner
263 v.normalize(); // normalise it.
264 v *= -_radius; // move the vector in the opposite direction distance radius.
265 v += _center; // move to absolute position.
266 newbb.expandBy(v); // add it into the new bounding box.
269 _center = newbb.center();
270 _radius = newbb.radius();
275 _center = bb.center();
276 _radius = bb.radius();
282template<typename BBT>
283void BoundingSphereImpl<VT>::expandRadiusBy(const BoundingBoxImpl<BBT>& bb)
289 for(unsigned int c=0;c<8;++c)
291 expandRadiusBy(bb.corner(c));
296 _center = bb.center();
297 _radius = bb.radius();
302typedef BoundingSphereImpl<Vec3f> BoundingSpheref;
303typedef BoundingSphereImpl<Vec3d> BoundingSphered;
305#ifdef OSG_USE_FLOAT_BOUNDINGSPHERE
306 typedef BoundingSpheref BoundingSphere;
308 typedef BoundingSphered BoundingSphere;