Path: utzoo!attcan!utgpu!jarvis.csri.toronto.edu!mailrus!tut.cis.ohio-state.edu!ukma!xanth!nic.MR.NET!umn-cs!uf!ken From: ken@uf.msc.umn.edu (Kenneth Chin-Purcell) Newsgroups: comp.graphics Subject: Re: Ray Traced Bounding Spheres Summary: Be careful! Message-ID: <12851@umn-cs.CS.UMN.EDU> Date: 15 May 89 14:15:07 GMT References: <17241@versatc.UUCP> <17249@versatc.UUCP> <8411@phoenix.Princeton.EDU> Sender: news@umn-cs.CS.UMN.EDU Reply-To: ken@uf.msc.umn.edu (Kenneth Chin-Purcell) Distribution: usa Organization: Minnesota Supercomputer Center, Inc. Lines: 37 In article sarrel@galley.cis.ohio-state.edu (Marc Sarrel) writes: >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. You are assuming that a line between the two farthest points defines the axis of the minimum bounding sphere. I don't think this is true. Take these three points: P3 xxxxxxx xx xx x x ---------P1---axis----P2--------- x x xx xx xxxxxxx P1 and P2 are the farthest apart. Use line P1-P2 to define the axis of sphere x. There is a region, near the equator of the sphere, where a point (P3) could be outside the sphere, yet less than P1-P2 distance from either point. To visualize this, think of two larger spheres, each with *radius* P1-P2, one centered at P1, the other at P2. The intersection of these spheres is the region where P3 can be while keeping P1 and P2 the farthest points. Sphere x is just a subset of this region. Since in general it takes 4 points to define a sphere, my intuition leads me to think that the true general solution will involve 4 bounding points. -- Ken Chin-Purcell (aka ken@msc.umn.edu) Minnesota Supercomputer Center "Seymore doesn't 1200 Washinton Ave., Minneapolis, MN 55415 believe in paging"