From: Tom Forsyth <tom.forsyth@ee...>  20040131 11:20:47

I think it's O(n^3) actually! n for the first vector, n for the second, = then n to check if that plane is on the hull. But yes, interesting idea. I think it should be fairly straightforward = to be able to take two cones and find the two planes that bound them (the = cones themselves are "end caps"). So you don't need to test a whole bunch of vectors on the cones, which helps. > Using this plane, and the other vector, shoot a vector down=20 > the center.=20 > This is the direction of the new cone, and the angle can be derived=20 > from the plane and vector (V) the you found. Not sure this is true. In general, the planes that you're finding will = _not_ touch the final bounding cone, so they're not chords. But iffthey are on = the bounding _hull_, then that means the cones they are between will touch = the bounding cone. But once you know which the magic three cones are, I think you can = either do it analytically, just anneal the solution down to an acceptable one. Annealing at this stage is fine because you know which three it is, so = it's not an O(n^something)  it's just a vaguely constant cost. Someone also mentioned finding the frustum planes directly rather than making a final single bounding cone. That's definately an interesting idea. TomF. > Original Message > From: gdalgorithmslistadmin@...=20 > [mailto:gdalgorithmslistadmin@...] On=20 > Behalf Of John Pollard > Sent: 29 January 2004 04:48 > To: gdalgorithmslist@... > Subject: Re: [Algorithms] Bounding cones. >=20 >=20 > Hmm, maybe this would work, but it may be a bit slow: >=20 > For each cone, build a list vectors that wrap around the cones origin=20 > (they would start at the origin, and travel along the cone=20 > hull). The=20 > number of vectors for each cone would be a function of each cones=20 > cos(theta). >=20 > Take two neighboring vectors (they should be neighbors, and belong to=20 > the same cone), and create a plane, where the normal should=20 > point away=20 > from all other vector end points. If all other vectors are=20 > on the back=20 > side of this plane, this is the correct plane, otherwise=20 > choose another=20 > two neighboring vectors until you find the correct plane. >=20 > If you don't find any planes that satisfy this, you can't solve it.=20 > Basically, we're looking for planes that are in the outer=20 > edge of the cones. >=20 > While checking if this was the correct plane, remember the=20 > vector that=20 > was the farthest from this plane, call the vector V, and the dist D. >=20 > Of all the planes that you find, choose the plane with the largest D. >=20 > Using this plane, and the other vector, shoot a vector down=20 > the center.=20 > This is the direction of the new cone, and the angle can be derived=20 > from the plane and vector (V) the you found. >=20 > Hope this makes sense. It's probably a tad bit slow, as it's=20 > O(n2), but=20 > could be a good starting point? >=20 > Tom Forsyth wrote: >=20 > > I have a bunch of circularcrosssection cones in 3D space,=20 > all originating > > from a single point (assume it's the origin). They are defined by a > > unitlength vector V (the central axis) and a cos(theta)=20 > 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=20 > cones and find > > the cone that tightly bounds both of them. So I can merge a=20 > bunch of cones > > by calling this on pairs of cones, but depending on the=20 > order you combine > > them you get a very loosefitting result, and the more=20 > cones you want to > > merge, the looser the result fits. > >=20 > > So I'm wondering if anyone knows a good way to find the=20 > bounding cone of a > > whole bunch of cones. If the cone angle goes over 180 then=20 > it's fine to > > return "don't know", so it doesn't need to handle crazy cases. > >=20 > > I'm using this to find frustums for shadowbuffers  each object is > > represented by a cone from the (point)light that bounds the=20 > mesh, and I want > > to find the frustum that bounds a collection of objects as=20 > tightly as > > possible. > >=20 > > I have a feeling this is a similar problem to finding good=20 > bounding spheres, > > but I don't know how to solve that particularly well=20 > either. It's also > > almost identical to the 2D version  finding bounding=20 > circles  but not > > quite because the circles are the projections of the cones=20 > on the surface of > > the unit sphere  you can't simply project them to a flat=20 > plane and solve > > the problem there because (a) which plane do you use? and=20 > (b) they're not > > circles when you project them, they're ellipses. > >=20 > > TomF. > >=20 > >=20 > >=20 > >=20 > >=20 > >=20 > >  > > The SF.Net email is sponsored by EclipseCon 2004 > > Premiere Conference on Open Tools Development and Integration > > See the breadth of Eclipse activity. February 35 in Anaheim, CA. > > http://www.eclipsecon.org/osdn > > _______________________________________________ > > GDAlgorithmslist mailing list > > GDAlgorithmslist@... > > https://lists.sourceforge.net/lists/listinfo/gdalgorithmslist > > Archives: > > http://sourceforge.net/mailarchive/forum.php?forum_ida88 > >=20 >=20 >=20 >=20 >  > The SF.Net email is sponsored by EclipseCon 2004 > Premiere Conference on Open Tools Development and Integration > See the breadth of Eclipse activity. February 35 in Anaheim, CA. > http://www.eclipsecon.org/osdn > _______________________________________________ > GDAlgorithmslist mailing list > GDAlgorithmslist@... > https://lists.sourceforge.net/lists/listinfo/gdalgorithmslist > Archives: > http://sourceforge.net/mailarchive/forum.php?forum_id=3D6188 >=20 