RE: [Algorithms] Bounding cones.

[Nick C. <nc...@nv...>]

I don't think that this iterative technique will always generate the
smallest cone -- it doesn't seem to work in the case of 2D circles.
Consider three small circles of equal radius whose centers are mutually
equidistant (i.e., in the pattern of an equilateral triangle).  Then the
minimum bounding circle of any two of the small circles will not be fully
contained in the minimum bounding circle of all three of the small circles.
So there's no way to "build up" a minimum bounding circle in the iterative
way that James suggests.

This counterexample is easily extended from circles to cones: consider three
cones, of small theta, whose centerlines, pairwise, are at equal angles to
one another.

I'm very curious about bounds on optimality of like iterative techniques, in
either the 2D-circle or 3D-cone (which is still 2 dof) cases.  Does anyone
know?

 - nick carter

> -----Original Message-----
> From: Johnson, James [mailto:Jam...@si...] 
> Sent: Tuesday, January 27, 2004 3:45 PM
> To: gda...@li...
> Subject: RE: [Algorithms] Bounding cones.
> 
> 
> 
> 
> If you could choose the two cones which generate the smallest 
> cone (need to define this clearly), could you then 
> iteratively perform this on the remaining set until one cone 
> is produced. Would this generate the smallest cone? How could 
> you prove it?
> 
> What I describe sounds like O(n^2) or maybe worse. It might 
> give some insight into the problem. Regardless I'm sure I'll 
> be thinking about this one for awhile. Cool problem!
> 
> James
> 
> -----Original Message-----
> From: gda...@li...
> [mailto:gda...@li...] On 
> Behalf Of Tom Forsyth
> Sent: Tuesday, January 27, 2004 11:38 AM
> To: gda...@li...
> Subject: [Algorithms] Bounding cones.
> 
> 
> I have a bunch of circular-cross-section cones in 3D space, 
> all originating from a single point (assume it's the origin). 
> They are defined by a unit-length vector V (the central axis) 
> and a cos(theta) term, where theta is half the base angle. 
> All points P on the cone obey the equation 
> (P.V)/|P|=cos(theta). I've worked out the maths to take two 
> cones and find the cone that tightly bounds both of them. So 
> I can merge a bunch of cones by calling this on pairs of 
> cones, but depending on the order you combine them you get a 
> very loose-fitting result, and the more cones you want to 
> merge, the looser the result fits.
> 
> So I'm wondering if anyone knows a good way to find the 
> bounding cone of a whole bunch of cones. If the cone angle 
> goes over 180 then it's fine to return "don't know", so it 
> doesn't need to handle crazy cases.
> 
> I'm using this to find frustums for shadowbuffers - each 
> object is represented by a cone from the (point)light that 
> bounds the mesh, and I want to find the frustum that bounds a 
> collection of objects as tightly as possible.
> 
> I have a feeling this is a similar problem to finding good 
> bounding spheres, but I don't know how to solve that 
> particularly well either. It's also almost identical to the 
> 2D version - finding bounding circles
> - but not quite because the circles are the projections of 
> the cones on the surface of the unit sphere - you can't 
> simply project them to a flat plane and solve the problem 
> there because (a) which plane do you use? and (b) they're not 
> circles when you project them, they're ellipses.
> 
> TomF.
> 
> 
> 
> 
> 
> 
> -------------------------------------------------------
> The SF.Net email is sponsored by EclipseCon 2004
> Premiere Conference on Open Tools Development and Integration 
> See the breadth of Eclipse activity. February 3-5 in Anaheim, 
> CA. http://www.eclipsecon.org/osdn 
> _______________________________________________
> GDAlgorithms-list mailing list GDA...@li...
> https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
> Archives: http://sourceforge.net/mailarchive/forum.php?forum_ida88
> 
> ----------------------------------------------------
> Vivendi Universal Games- <<http://www.vugames.com>>:
> 
> The information transmitted is intended only for the
> 
> person or entity to which it is addressed and may
> 
> contain confidential and/or privileged material of
> 
> Vivendi Universal Games which is for the exclusive
> 
> use of the individual designated above as the
> 
> recipient. Any review, retransmission, dissemination
> 
> or other use of, or taking of any action in reliance
> 
> upon, this information by persons or entities other
> 
> than the intended recipient is prohibited. If you
> 
> received this in error, please contact immediately
> 
> the sender by returning e-mail and delete the
> 
> material from any computer. If you are not the
> 
> specified recipient, you are hereby notified that
> 
> all disclosure, reproduction, distribution or action
> taken on the basis of this message is prohibited.
> 
> 
> -------------------------------------------------------
> The SF.Net email is sponsored by EclipseCon 2004
> Premiere Conference on Open Tools Development and Integration 
> See the breadth of Eclipse activity. February 3-5 in Anaheim, 
> CA. http://www.eclipsecon.org/osdn 
> _______________________________________________
> GDAlgorithms-list mailing list GDA...@li...
> https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
> Archives: http://sourceforge.net/mailarchive/forum.php?forum_ida88
>