From: thite@micrografx.com
Subject: Re: Bounding volumes (sphere vs box)
Organization: Micrografx, Inc.
X-Newsreader: Tin 1.1 PL5
Date: Fri, 2 Oct 92 21:16:10 GMT

tom wilson (wilson@cs.ucf.edu) wrote:
: I removed the NA distribution since this of interest to researchers throughout
: the world (it's not a FAQ about some PD program for once 8-).
: 
: djb@geovision.gvc.com (Darren Burns) wrote:
: >I'm implementing a ray-tracer and I'm using bounding volumes to
: >gather objects into groups and to avoid doing expensive calculations
: >when they're not needed (standard stuff).
: 
: >I had been under the impression that it was quicker to intersect
: >a line with a sphere than with a box.  I just did a timing test.
: >Basically I had a bunch of spheres or boxes sitting there and I
: >ray-traced the scene, once using spheres and once using boxes.
: >I found that the boxes were faster (not a lot, 11 seconds for
: >spheres vs 9 for boxes).  The volumes were about the same for
: >both types of objects; actually the spheres were a little smaller.
: 
: >I can draw two conclusions:
: 
: >1) My impression was wrong, and boxes are faster to intersect
: >   than spheres are.
: 
: >2) My sphere-intersection routine sucks rocks.
: 
: You must be careful when drawing your conclusion. I've found 3D boxes faster
: too, but it is very dependent upon what's inside as to whether or not it
: will be. Depending on how optimized your code is, the sphere BV may be
: faster to intersect with a ray, but the comparison doesn't end there. When
: a ray hits an object inside the BV, both the sphere and the box are a waste
: of time. When the object inside the BV is missed, it is up to the BV to
: cull as many rays as possible. You want to perform the ray-object intersection
: code as few times as possible when it will miss the object (you obviously
: must execute the code when there is a hit).
: 
: Also you must take into account the relative execution times of (1) ray-sphere
: (as BV) int., (2) ray-box int., and (3) ray-object int. If (3) is much greater
: than both (1) and (2), you may get a better answer from your test. Suppose you
: have 2 BVs: BV #1 is the slower of the two, but culls more misses, BV #2 is
: the faster of the two, but culls fewer misses. Which is better? That depends
: on how many rays are actually involved in the comparison, but let's be sloppy
: and just say: if the time saved by using the faster BV #2 is lost by executing
: the slower ray-object routine more times, BV #1 may actually be the better
: choice. Too many tests involve spheres or boxes around simple triangles.
: 
: Basically, you are introducing yourself to an old, but difficult-to-fully-
: solve problem. Much work has been done on the choice of BVs. Couple that with
: a construction of a hierarchy of BVs and you really have a mess. Find some
: of the bibliographies at ftp sites to see the work that has already been done
: (also you might find my collection of ray tracing abstracts which might give
: you a clue about what is discussed before you actively seek the papers --
: send me e-mail for more details if you'd like, I don't want to bother at the
: moment). The text An Introduction to Ray Tracing has a sufficient explanation
: of the background material.
: 
: The only strong conclusion I can make is that boxes work best for the scene(s)
: you tested. The may be a good choice in general, but that's a dangerous
: statement.
: 
: I hope I made some helpful comments. Others are appreciated.
: 
: Tom

Note that if you are using C++, you should have all your geometry inherit
from a CBoundingVolume class, which is mostly virtual.  This way, you can
derive a CSphericalBound class and a CCubeBound.  Each geometry class
should properly inherit from either of those (or at least include a
member of one of the types).

For instance:

	typedef int bool;

	class CBoundingVolume
	{
		public:
			virtual bool Intersect(const CVector& rRay) = 0;
	}

	class CSphericalBound : public CBoundingVolume
	{
		private:
			double radius;
		public:
			bool Intersect(const CVector& rRay) { /* test ray */ return bStatus; }
			// other methods like Increase, Decrease, etc, etc
	};	
	class CCubeBound : public CBoundingVolume
	{
		private:
			Vector FrontLeft;
			Vector BackRight;
		public:
			bool Intersect(const CVector& rRay) { /* test ray */ return bStatus; }
	};

A sphere really ought to instantiate a spherical BV.  A Box should
instantiate a cube as its BV.  Actually, a sphere geometry (if your
renderer can use non-mesh geometry) is a CSphericalBound and a
cube geometry is a CCubeBound.  But you get the picture, right?

In the case of a mesh based object, only the mesh generation code will
know which type of volume is best, and therefore it should be derived
from one of the above BV classes.

TH