RE: [Algorithms] Bounding cones.

[Johnson, J. <Jam...@si...>]

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|=3Dcos(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>>:=0D
The information transmitted is intended only for the=0D
person or entity to which it is addressed and may=0D
contain confidential and/or privileged material of=0D
Vivendi Universal Games which is for the exclusive=0D
use of the individual designated above as the=0D
recipient. Any review, retransmission, dissemination=0D
or other use of, or taking of any action in reliance=0D
upon, this information by persons or entities other=0D
than the intended recipient is prohibited. If you=0D
received this in error, please contact immediately=0D
the sender by returning e-mail and delete the=0D
material from any computer. If you are not the=0D
specified recipient, you are hereby notified that=0D
all disclosure, reproduction, distribution or action
taken on the basis of this message is prohibited.