Path: utzoo!utgpu!jarvis.csri.toronto.edu!mailrus!tut.cis.ohio-state.edu!galley.cis.ohio-state.edu!sarrel From: sarrel@galley.cis.ohio-state.edu (Marc Sarrel) Newsgroups: comp.graphics Subject: Re: Ray Traced Bounding Spheres Message-ID: Date: 15 May 89 02:39:48 GMT References: <17241@versatc.UUCP> <17249@versatc.UUCP> <8411@phoenix.Princeton.EDU> Sender: news@tut.cis.ohio-state.edu Organization: Ohio State Computer Science Lines: 48 In-reply-to: mplevine@phoenix.Princeton.EDU's message of 14 May 89 16:08:32 GMT Well, I don't argue that the posted algorithm works (although I'm not sure about its linearity), I don't think that it answers the question exactly. Here is my solution, which I _know_ to be linear in the number of points. Problem: Given a set of points in three space, find the two that are farthest apart and use them to define a minimum bounding sphere. Solution: 1) Pick a point, any point, call it p1 2) Find the farthest point from p1, call it p2. 3) Find the farthest point from p2, call it p3. 4) Use p2, p3 and the distance between them to define your minimum bounding sphere. That's it. It is guaranteed to be linear, too. The reason that this algorithm works is as follows. We know that there are two points such that the distance between them is greater than the distance between any other two points, call them p2 and p3 (as above). Call the line between p2 and p3 d1 (for diameter). Call the point midway along d1 c1 (for center). Put a plane perpendicular to d1 through the point c1. This divides the points into two sets. For all the points on one side of the plane, point p2 is the farthest away and for all the points on the other side, p3 is farthest away. Now, we can see that step two above finds one of the points that define the bounding sphere and that step three must find the other. QED (for an informal argument). If you don't beleive that it works, try a few examples from the 2D case to convince yourself. I don't know if this has been published anywhere (I'm almost sure that it has), but I can't remember reading about it. It was inspired by a "Computer Games" (or whatever it was called at the time) column in an old issue of Scientific American. The main problem with implementing this algorithm is that the square and square root function needed to calculate distances are expensive. In practice, the square root can be ignored except to calculate the final distance for the diameter. However, there may be more efficient algorithms that don't bear any relation to this one. -=- "Master, why is the letter 'i' the symbol for current?" "Because there is no letter 'i' in the word 'current'." "Master, why do we use the letter 'j' for sqrt(-1)?" "Because we use the letter 'i' for current." Whereupon the Master struck the Disciple, and the Disciple became enlightened.