Thread: RE: [Algorithms] Bounding cones.
Brought to you by:
vexxed72
From: Paul Du B. <du...@do...> - 2004-01-27 20:43:56
|
> It's also > almost identical to the 2D version - finding bounding circles=20 > - but not > quite because the circles are the projections of the cones on=20 > the surface of the unit sphere This reminds me of the "find an empty region" problem discussed in the Johnstone/Williams quaternion spline paper. You want to find the largest empty region in s(2) populated by circles, and the paper wants the largest empty region in an S(3) populated by points. Still, the paper outlines a few attacks on the problem (with references) and it may give you some good insight. Section 7.4, "A rational quaternion spline of arbitrary continuity" p |
From: Johnson, J. <Jam...@si...> - 2004-01-27 23:45:40
|
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. |
From: Nick C. <nc...@nv...> - 2004-01-28 00:45:22
|
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 > |
From: Johnson, J. <Jam...@si...> - 2004-01-28 01:33:14
|
You're correct. I should have tested the obvious first. James -----Original Message----- From: gda...@li... [mailto:gda...@li...] On Behalf Of Nick Carter Sent: Tuesday, January 27, 2004 4:45 PM To: 'gda...@li...' Subject: RE: [Algorithms] Bounding cones. 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 ---------------------------------------------------- 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. |
From: Nick C. <nc...@nv...> - 2004-01-28 01:40:57
|
Tom, You have a way to compute the exact, minimal bounding cone for a set of 2 cones. Can you figure out a way to compute an exact, minimal bounding cone of 3 cones? I ask because the following seems to be true: that, given a arbitrary collection of 4 cones, one of the cones can be removed from the collection without changing the minimal bounding cone of the collection. Thus, (I postulate) from any collection C of cones, it suffices to select three "pivot cones" c1, c2, c3 from C, such that MinimumBoundingCone({c1,c2,c3}) is a cone that strictly contains every element of C. Or, conjectured another way, the minimum bounding cone of a cone-set C is the cone of maximum size from the collection of minimum bounding cones formed by triplets from C. If my reasoning is correct, this should lead to a straightforward search: init: // * number of cones in C int n // * array of cones that we're trying to compute the MBC of array C // * triplet vector we're trying to compute value T=<C[0],C[0],C[0]> // * boolean valued function that returns true iff cone is completely // within boundingcone function Contains(boundingcone,cone) // * a fast, cone-valued function that computes a minimum bounding cone of three cones // based on some algebraic definition. function MBC3(cone,cone,cone) loop: for k=0 to n { if (!Contains(MBC3(T[0],T[1],T[2]),C[k])) { // we want to insert C[k] into the triplet T if (Contains( MBC3(C[k], T[1], T[2]), T[0] )) T = <C[k],T[1],T[2]>; goto loop; // throw out T[0] else if (Contains( MBC3(C[k], T[0], T[2]), T[1] )) T = <C[k],T[0],T[2]>; goto loop; // throw out T[1] else if (Contains( MBC3(C[k], T[0], T[1]), T[2] )) T = <C[k],T[0],T[1]>; goto loop; // throw out T[2] else // numerical wonkiness, or else I'm fatally // wrong in my conjecture assert(0); } } // if we get here, MBC3(T) is a MBC of C. Thoughts? - nick carter > -----Original Message----- > From: Tom Forsyth [mailto:tom...@ee...] > Sent: Tuesday, January 27, 2004 4:05 PM > To: gda...@li... > Subject: RE: [Algorithms] Bounding cones. > > > Oooh - so close. Got me all excited. I eventually found a > paper that summarised (and even corrected!) the Sederberg & > Meyers paper, but it's just the same one I found - it adds > one cone at a time to an overall cone, and has the same > properties. They admit it's sub-optimal, but it's still a > good early-out culler. Except that's fine for their case - > the difference between culling perfectly and what they have > is an extra 1% - tiny. In my case, I have twice the pixels to > render :-( > > Ah well - good try though. Your citeseer-fu is strong. Cheers. > > TomF. > > > -----Original Message----- > > From: gda...@li... > > [mailto:gda...@li...] On > > Behalf Of Mark Duchaineau > > Sent: 27 January 2004 23:32 > > To: gda...@li... > > Subject: Re: [Algorithms] Bounding cones. > > > > > > There is a nice result by Sederberg and Meyers, but it is old > > and thus only > > available in libraries: > > > http://citeseer.nj.nec.com/context/178634/0 > > This link gives a number of papers that reference it, so > perhaps some of them will give a useful summary. > > Cheers, > > --Mark D. > > Tom Forsyth wrote: > > I have a bunch of circular-cross-section cones in 3D space, all > originating > > from a single point (assume it's the origin). > > > > > > ------------------------------------------------------- > 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 > |
From: Nick C. <nc...@nv...> - 2004-01-28 02:54:30
|
Here's another wild-ass idea, which assumes you have an efficient way to compute the minimum bounding sphere of a bunch of spheres. Map cones to spheres in the following manner: Intersect each cone in your collection with the unit sphere. This will give you a bunch of circles in R^3. Convert the circles into spheres, i.e. treat the circles as great circles of a sphere. Now: compute the minimum bounding sphere, S, of these spheres. Then: re-intersect S with the unit sphere, the result will be a circle, which you can then treat as a cone. Anyone care to verify/disprove that the resulting cone will be a bounding cone? I don't think it's necessarily minimal. - nick carter > -----Original Message----- > From: Jonathan Blow [mailto:jo...@nu...] > Sent: Tuesday, January 27, 2004 5:44 PM > To: gda...@li... > Subject: Re: [Algorithms] Bounding cones. > > > My approach to this problem would just be to throw a > clustering algorithm at the cones and then take the cluster > centroid as the middle of your new cone. It'll give you > higher quality results than two-at-a-time. > > In unfriendly environments (non-Ln, say), the standard > clustering algorithm becomes a sort of two-at-a-time scheme > anyway (k-means clustering). As for what exactly to cluster, > you could try to map to a space where each cone axis gives > you a point, or you could just stay in R3 and generate m > random points within each cone and just throw those into the > clustering algorithm. > > Such a k-means scheme will, I think, still give you better > results than the simple two-at-a-time expando-cone solution, > because with k-means the cluster center is allowed to adapt > to all the input data before you commit to increases in cone radius. > > Actually, since there's only one cluster and everything must > fit into the cluster, you might get away with something > simpler. Let's assume you just randomly generate a bunch of > sample points from each cone (like 1000 points -- uhh, let's > hope this is a preprocess). Take the mean and the covariance > of all these points, then transform the covariance into the > space of the mean. [see *]. Then you take the ellipsoid > corresponding to that covariance blob, and pick the two minor > axes. These give you a reasonable approximation for the > cross section of the cone. Likewise, the major axis of the > ellipsoid gives you a good approximation for the major axis > of the cone. Given that major axis, you can then just fit > the cone from there. > > As with all these things, you may want to perturb the > solution some in order to try and improve the results (uhh, > let's hope this is a preprocess). > > > [*: My gdmag article "My Friend, The Covariance Body" says > how to do this. > http://number-none.com/product/My%20Friend,%20the%20Covariance > %20Body/index.html > Jim Van Verth also has an appropriate article in Game > Programming Gems 4.] > > > > ----- Original Message ----- > From: "Tom Forsyth" <tom...@ee...> > To: <gda...@li...> > Sent: Tuesday, January 27, 2004 7:05 PM > Subject: RE: [Algorithms] Bounding cones. > > > > Oooh - so close. Got me all excited. I eventually found a > paper that > > summarised (and even corrected!) the Sederberg & Meyers paper, but > > it's just the same one I found - it adds one cone at a time to an > > overall cone, and has the same properties. They admit it's > > sub-optimal, but it's still a good early-out culler. Except that's > > fine for their case - the difference between culling perfectly and > > what they have is an extra 1% - tiny. In my case, I have twice the > > pixels to render :-( > > > > Ah well - good try though. Your citeseer-fu is strong. Cheers. > > > > TomF. > > > > > -----Original Message----- > > > From: gda...@li... > > > [mailto:gda...@li...] On > > > Behalf Of Mark Duchaineau > > > Sent: 27 January 2004 23:32 > > > To: gda...@li... > > > Subject: Re: [Algorithms] Bounding cones. > > > > > > > > > There is a nice result by Sederberg and Meyers, but it is old > > > and thus only > > > available in libraries: > > > > > http://citeseer.nj.nec.com/context/178634/0 > > > > This link gives a number of papers that reference it, so > perhaps some > > of them will give a useful summary. > > > > Cheers, > > > > --Mark D. > > > > Tom Forsyth wrote: > > > I have a bunch of circular-cross-section cones in 3D space, all > > originating > > > from a single point (assume it's the origin). > > > > > > > > > > > > ------------------------------------------------------- > > 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 > > > ------------------------------------------------------- > 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_id=6188 > |
From: Peter-Pike S. <pp...@wi...> - 2004-01-28 05:50:24
|
I haven't been following this thread that closely, but pedro sander did a very nice job of computing optimnal sphere/cone hiearchies for his Silhouette Clipping paper: http://pedrosander.com/publications/ (section 5 in the above paper) -Peter-Pike Sloan -----Original Message----- From: gda...@li... [mailto:gda...@li...] On Behalf Of Jonathan Blow Sent: Tuesday, January 27, 2004 7:27 PM To: gda...@li... Subject: Re: [Algorithms] Bounding cones. > However, you might have something there. If I simply took n points=20 > around the edge of each cone, where n is about 3-6 (could even change=20 > the number according to the size of the cone - typically I will have=20 > cones of widely varying sizes, since the objects vary widely in size,=20 > and are at very different distances to the light). Then cluster them,=20 > and use that as a starting guess. As long as the initial guess is=20 > fairly accurate, I think it's true to say you can then do the=20 > one-at-a-time merging and still get a very good bounding cone at the end. The covariance stuff is really fast, once you have the initial values inside the covariance matrices; you can just transform them and add them after that. And actually, you can compute the closed-form covariance of a cone, and evaluating that would probably be faster than using individual points. So my original 1000 points idea was overzealous and unnecessary. By default when using such closed-form covariance, big cones would be favored, but you can compensate for this just by scaling up the density of the small cones. I'm not saying it's the best solution for your problem, but it's worth trying if yer gonna investigate various solutions. ------------------------------------------------------- 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_id=3D6188 |
From: Tom F. <tom...@ee...> - 2004-01-28 11:07:25
|
Aha: "It can be shown that the central axis of such a cone has the following property: if one associates a point on the unit sphere with each face = normal in the cluster, and computes the 3D convex hull of this pointset, must = pass through the closest point from the origin to that convex hull." I guess that makes sense - the 2D version of the same thing "obviously works", but my brain doesn't find the 3D version as obvious. Not all that sure I want to try constructing the convex hull of circles = at runtime though - sounds expensive. ... Argh. I worked out a lovely O(n) algorithm where you only ever track at = most three cones that make up the bounding hull feature closest to the origin (either an edge or a plane) as you go along (similar to what Nick was saying). Problem is, that's not enough. You can never guarantee to throw away information and still get an optimal hull. Imagine a regular n-gon of cones of the same radius (Ci). Then place = another cone (C0) quite a way off. So the bounding cone is now formed by C0 and = one or two of Ci - the ones furthest from C0. But depending where you put = C0, it's a different Ci. So until you have C0, you can never throw away any = Ci, no matter how big n is. Which means that although Nick is (probably) right when he says that any bounding cone is formed by at most three cones, adding another cone may produce a new bounding cone that uses a _completely different three_. = Which is a pain. However, I suspect the number you actually need to track will be = reasonable in practice - you should be able to throw most of them away (anything = that is inside the hull is definately never going to be part of the hull in future). So this is certainly a plausable avenue of attack. Got me some maths to do. TomF. > -----Original Message----- > From: gda...@li...=20 > [mailto:gda...@li...] On=20 > Behalf Of Peter-Pike Sloan > Sent: 28 January 2004 05:50 > To: gda...@li... > Subject: RE: [Algorithms] Bounding cones. >=20 >=20 > I haven't been following this thread that closely, but pedro=20 > sander did > a very nice job of computing optimnal sphere/cone hiearchies for his > Silhouette Clipping paper: >=20 > http://pedrosander.com/publications/ >=20 > (section 5 in the above paper) >=20 > -Peter-Pike Sloan >=20 > -----Original Message----- > From: gda...@li... > [mailto:gda...@li...] On Behalf Of > Jonathan Blow > Sent: Tuesday, January 27, 2004 7:27 PM > To: gda...@li... > Subject: Re: [Algorithms] Bounding cones. >=20 > > However, you might have something there. If I simply took n points=20 > > around the edge of each cone, where n is about 3-6 (could=20 > even change=20 > > the number according to the size of the cone - typically I=20 > will have=20 > > cones of widely varying sizes, since the objects vary=20 > widely in size,=20 > > and are at very different distances to the light). Then=20 > cluster them,=20 > > and use that as a starting guess. As long as the initial guess is=20 > > fairly accurate, I think it's true to say you can then do the=20 > > one-at-a-time merging and still get a very good bounding cone at the > end. >=20 > The covariance stuff is really fast, once you have the initial values > inside the covariance matrices; you can just transform them=20 > and add them > after that. > And actually, you can compute the closed-form covariance of a=20 > cone, and > evaluating that would probably be faster than using individual points. > So my original 1000 points idea was overzealous and unnecessary. >=20 > By default when using such closed-form covariance, big cones would be > favored, but you can compensate for this just by scaling up=20 > the density > of the small cones. >=20 > I'm not saying it's the best solution for your problem, but it's worth > trying if yer gonna investigate various solutions. >=20 >=20 >=20 > ------------------------------------------------------- > The SF.Net email is sponsored by EclipseCon 2004 Premiere=20 > 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_id=3D6188 >=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 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 >=20 |
From: Paul Du B. <du...@do...> - 2004-01-28 06:12:17
|
Of the 3 algorithms mentioned in Johnstone, covariance is the 2nd one suggested.. The 3rd (exact) algorithm uses voronoi regions. It's solving for the largest empty region in S(3) but of course because of the geometry that's pretty much the same thing as finding the smallest enclosing region. To paraphrase for your case, find the point in S(2) farthest away from any of your cones; the opposite point is the center of your bounding cone. This farthest point will be some vertex in the voronoi diagram. Either compute the full thing (tricky) or find all possible voronoi verts (intersections of bisectors) and check for distance from your cones. Since you have O(n^2) bisectors, that's O(n^4) intersections and O(n^5) circle-circle distance checks. Hm...maybe it's better in practice. If it's not... computing the full diagram sounds like a fun and interesting problem. p |
From: Crosbie F. <cr...@cy...> - 2004-01-31 02:32:28
Attachments:
winmail.dat
|
> From: Paul Du Bois > To paraphrase for your case, find the point in S(2) farthest away > from any of your cones Then, one could find the nearest three cones? As those will then be sufficient to define the bounding cone. Dunno if that helps tho. |
From: Willem de B. <wd...@pl...> - 2004-01-28 09:01:46
|
Hello everyone, Very interesting problem, Tom. I think this belongs to that esoteric field called computational geometry; you should consult a book or two on the subject, it's got applications in all fields within computer graphics. Famous problems it tries to tackle include the optimal bounding volume problem. After my first coffe this morning, I decided you could pose your=20 problem mathematically, as follows: Definition 1: A cone C is defined as an axis V and the cosine of its half-angle, H.=20 Definition (theorem really) 2: Given two cones C1 and C2, WITH COMMON ORIGINS. C1 is contained=20 within C2 iff <V1,V2>+H1 <=3D H2. Where <,> denotes dot product. Tom Forsyth's Problem:=20 Given a collection {Ci} of cones with a common origin, axes {Vi} and cosine-half-angles {Hi}, find a cone C with axis Vc, such that Hc is minimised, and such that Ci is contained within C, for each i. So it seems to me, one could to treat this as a minimsation problem, try to find a Vc, so as to MINIMISE Hc, subject to N=20 inequality constraints of the form: <Vc,Vi>+Hi <=3D Hc.=20 So, maybe search for minimization, Kuhn-Tucker conditions, Lagrange multipliers, that sort of stuff? - Willem |
From: Willem de B. <wd...@pl...> - 2004-01-28 09:41:59
|
Actually, it might prove to be trickier than that. Hc as a=20 function of Vc is: Hc( Vc ) =3D max [ <Vi,Vc> + Hi ], for all 1<=3Di<=3DN And the inequality constraints also contain Hc, which is exactly the function we are trying to minimize. So, the problem is looking very problematic :) I do not (yet) know enough theory to work this all out; maybe a heuristic approach like Jonathan's is best at the moment.. - Willem -----Original Message----- From: Willem de Boer=20 Sent: Wednesday, January 28, 2004 10:02 AM To: 'gda...@li...' Subject: RE: [Algorithms] Bounding cones. Hello everyone, Very interesting problem, Tom. I think this belongs to that esoteric field called computational geometry; you should consult a book or two on the subject, it's got applications in all fields within computer graphics. Famous problems it tries to tackle include the optimal bounding volume problem. After my first coffe this morning, I decided you could pose your=20 problem mathematically, as follows: Definition 1: A cone C is defined as an axis V and the cosine of its half-angle, H.=20 Definition (theorem really) 2: Given two cones C1 and C2, WITH COMMON ORIGINS. C1 is contained=20 within C2 iff <V1,V2>+H1 <=3D H2. Where <,> denotes dot product. Tom Forsyth's Problem:=20 Given a collection {Ci} of cones with a common origin, axes {Vi} and cosine-half-angles {Hi}, find a cone C with axis Vc, such that Hc is minimised, and such that Ci is contained within C, for each i. So it seems to me, one could to treat this as a minimsation problem, try to find a Vc, so as to MINIMISE Hc, subject to N=20 inequality constraints of the form: <Vc,Vi>+Hi <=3D Hc.=20 So, maybe search for minimization, Kuhn-Tucker conditions, Lagrange multipliers, that sort of stuff? - Willem |
From: Gino v. d. B. <gva...@pl...> - 2004-01-28 11:57:00
|
> -----Original Message----- > From: Tom Forsyth [mailto:tom...@ee...] > Sent: Wednesday, January 28, 2004 12:07 > To: gda...@li... > Subject: RE: [Algorithms] Bounding cones. >=20 > [Stuff deleted] =20 > Which means that although Nick is (probably) right when he says that any > bounding cone is formed by at most three cones, adding another cone may > produce a new bounding cone that uses a _completely different three_. > Which > is a pain. > It is not as much a pain as it sems. This problem occurs also for bounding spheres. Welzl showed in http://citeseer.nj.nec.com/welzl91smallest.html that on average a randomized algorithm takes only linear time. That is, the number of "painful" moments is relatively small. =20 =20 > However, I suspect the number you actually need to track will be > reasonable > in practice - you should be able to throw most of them away (anything that > is inside the hull is definately never going to be part of the hull in > future). So this is certainly a plausable avenue of attack. You can take the structure of Welzl's algorithm (who took it from Seidel's LP algorithm) and add the necessary operations for your case: 1. Test a cone for containment in another cone 2. Construct a bounding cone for a set of 1 (trivial), 2, or 3 cones. Notably the hull for 3 cones could be a challenge. Gino van den Bergen www.dtecta.com =20 |
From: Willem de B. <wd...@pl...> - 2004-01-28 12:40:54
|
> >You can take the structure of Welzl's algorithm (who took it from >Seidel's LP algorithm) and add the necessary operations for your case: > > 1. Test a cone for containment in another cone > 2. Construct a bounding cone for a set of 1 (trivial), 2, or 3 > cones. > >Notably the hull for 3 cones could be a challenge. I think as a reasonable approximation, you could take the average of the 3 Vi's, that make up the three cones {Ci}, and use that as the V for your containing cone. Then compute H (ie., cos(half-angle-of-V)) from that..? - Willem |