Path: utzoo!attcan!utgpu!jarvis.csri.toronto.edu!rutgers!mit-eddie!bloom-beacon!athena.mit.edu!tada From: tada@athena.mit.edu (Michael Zehr) Newsgroups: comp.graphics Subject: Re: Ray Traced Bounding Spheres Message-ID: <11444@bloom-beacon.MIT.EDU> Date: 15 May 89 16:35:00 GMT References: <17241@versatc.UUCP> <17249@versatc.UUCP> <8411@phoenix.Princeton.EDU> <4057@rpi.edu> Sender: daemon@bloom-beacon.MIT.EDU Reply-To: tada@athena.mit.edu (Michael Zehr) Organization: Massachusetts Institute of Technology Lines: 44 In article <17241@versatc.UUCP>, ritter@versatc.UUCP (Jack Ritter) writes: > Given a cluster of points in 3 space, is there > a good method for finding the minumum radius > sphere which encloses all the points? In article sarrel@galley.cis.ohio-state.edu (Marc Sarrel) writes: >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: [...] People seem to be having a problem understanding what the problem is. The problem is not limited to 3 points (like one poster's solution), nor is it to find which pair of points are farthest apart in a set of points. The real problem is to speed up a ray-tracing program by providing some sort of bounding sphere for an object. This is really 2 problems: 1. given a set of points, find the minimum-bounding sphere 2. given a set of points, quickly find a "good" bounding sphere if the data is static, but you're going to view it from many directions (or lighting models, etc), then you want 1. it doesn't really matter how long it takes, because it's done once and used many times. but you want it to be minimal, to save as much time as possible. if the data isn't static (the points move with respect to each other between each run of the program) then you want to find the bounding sphere quickly. and it's better to quickly find a sphere that's slightly larger than what's needed if it takes a less time to compute it. In conclusion... be sure you understand the problem before giving a solution. try and be more certain of your "knowing" the solution. but do go ahead and post a possible solution. (i'm not trying to discourage people from posting, i'm trying to prevent people from using a solution that isn't.) -michael j zehr