Thread: [Algorithms] Bounding cones.
Brought to you by:
vexxed72
From: Tom F. <tom...@ee...> - 2004-01-27 19:37:49
|
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. |
From: <cas...@ya...> - 2004-01-27 22:42:48
|
Tom Forsyth wrote: > 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. Hey, that problem is really interesting! Here is a quick idea, but don't know for sure if it will really work. 1.- First determine if the circles are in euclidean position. 2.- Rotate them so that they lie on the same side of the sphere. 3.- Use an stereographic projection, note that this projection is conformal, so the projected circles are still circles. 4.- Find the minimun enclosing circle in 2d and undo your projection. I don't know for sure if that circle is really the minimum enclosing circle, but it seems to be. If it is, maybe steps 1 and 2 aren't necesary, but in that case your minimun enclosing circle algorithm will have to handle external circles. -- Ignacio Castaño cas...@ya... |
From: Mark D. <duc...@ll...> - 2004-01-27 23:32:22
|
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). |
From: Tom F. <tom...@ee...> - 2004-01-28 00:05:00
|
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...=20 > [mailto:gda...@li...] On=20 > Behalf Of Mark Duchaineau > Sent: 27 January 2004 23:32 > To: gda...@li... > Subject: Re: [Algorithms] Bounding cones. >=20 >=20 > There is a nice result by Sederberg and Meyers, but it is old=20 > and thus only > available in libraries: >=20 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). |
From: Jonathan B. <jo...@nu...> - 2004-01-28 01:43:41
|
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 |
From: Tom F. <tom...@ee...> - 2004-01-28 02:26:55
|
Heh - nope, not a preprocess. This is realtime. And it has to be = moderately swift, coz I'm doing it around eight times for every object lit by each light every frame. Then I have to actually render some stuff :-) (I'll probably have to do it less frequently than this anyway - there's other overheads killing me, but...) However, you might have something there. If I simply took n points = around the edge of each cone, where n is about 3-6 (could even change the = number according to the size of the cone - typically I will have cones of = widely varying sizes, since the objects vary widely in size, and are at very different distances to the light). Then cluster them, and use that as a starting guess. As long as the initial guess is fairly accurate, I think it's true to say you can then do the one-at-a-time merging and still get = a very good bounding cone at the end. Since I'm going to then turn this into a square frustum for rendering, there's a limit to just how good this bounding cone needs to be - I'm = always going to be rendering (4-PI)/PI=3D21% more pixels than the cone anyway. = It was the average 2-4x number of pixels I wasn't keen on! And Nick had a good idea. The algorithm certainly sounds plausable. I'll have to sit down with a bit of paper and scribble some geometry to see = if I can figure out how to directly find the bounding cone of three cones. = Two was easy because everything interesting happens along a single plane. Cheers all - good ideas. TomF. > -----Original Message----- > From: gda...@li...=20 > [mailto:gda...@li...] On=20 > Behalf Of Jonathan Blow > Sent: 28 January 2004 01:44 > To: gda...@li... > Subject: Re: [Algorithms] Bounding cones. >=20 >=20 > My approach to this problem would just be to throw a=20 > clustering algorithm at > the cones and then take the cluster centroid as the middle of=20 > your new cone. > It'll give you higher quality results than two-at-a-time. =20 >=20 > In unfriendly environments (non-Ln, say), the standard=20 > clustering algorithm becomes > a sort of two-at-a-time scheme anyway (k-means clustering). =20 > As for what > exactly to cluster, you could try to map to a space where=20 > each cone axis > gives you a point, or you could just stay in R3 and generate=20 > m random points > within each cone and just throw those into the clustering algorithm. >=20 > Such a k-means scheme will, I think, still give you better=20 > 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=20 > before you commit > to increases in cone radius. >=20 > Actually, since there's only one cluster and everything must=20 > 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=20 > (like 1000 points -- uhh, > let's hope this is a preprocess). Take the mean and the=20 > covariance of all > these points, then transform the covariance into the space of=20 > the mean. [see *]. > Then you take the ellipsoid corresponding to that covariance=20 > 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=20 > ellipsoid gives > you a good approximation for the major axis of the cone. =20 > Given that major > axis, you can then just fit the cone from there. >=20 > As with all these things, you may want to perturb the=20 > solution some in order > to try and improve the results (uhh, let's hope this is a preprocess). >=20 >=20 > [*: My gdmag article "My Friend, The Covariance Body" says=20 > 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=20 > Programming Gems 4.] >=20 >=20 >=20 > ----- Original Message -----=20 > From: "Tom Forsyth" <tom...@ee...> > To: <gda...@li...> > Sent: Tuesday, January 27, 2004 7:05 PM > Subject: RE: [Algorithms] Bounding cones. >=20 >=20 > > Oooh - so close. Got me all excited. I eventually found a paper that > > summarised (and even corrected!) the Sederberg & Meyers=20 > paper, but it's just > > the same one I found - it adds one cone at a time to an=20 > overall cone, and > > has the same properties. They admit it's sub-optimal, but=20 > it's still a good > > early-out culler. Except that's fine for their case - the=20 > difference between > > culling perfectly and what they have is an extra 1% - tiny.=20 > In my case, I > > have twice the pixels to render :-( > >=20 > > Ah well - good try though. Your citeseer-fu is strong. Cheers. > >=20 > > TomF. > >=20 > > > -----Original Message----- > > > From: gda...@li...=20 > > > [mailto:gda...@li...] On=20 > > > Behalf Of Mark Duchaineau > > > Sent: 27 January 2004 23:32 > > > To: gda...@li... > > > Subject: Re: [Algorithms] Bounding cones. > > >=20 > > >=20 > > > There is a nice result by Sederberg and Meyers, but it is old=20 > > > and thus only > > > available in libraries: > > >=20 > > http://citeseer.nj.nec.com/context/178634/0 > >=20 > > This link gives a number of papers that reference it, so=20 > perhaps some > > of them will give a useful summary. > >=20 > > Cheers, > >=20 > > --Mark D. > >=20 > > 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). > >=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 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 >=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_id=3D6188 >=20 |
From: Jonathan B. <jo...@nu...> - 2004-01-28 03:26:57
|
> However, you might have something there. If I simply took n points around > the edge of each cone, where n is about 3-6 (could even change the number > according to the size of the cone - typically I will have cones of widely > varying sizes, since the objects vary widely in size, and are at very > different distances to the light). Then cluster them, and use that as a > starting guess. As long as the initial guess is fairly accurate, I think > it's true to say you can then do the 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. |
From: Andrew W. <awi...@ma...> - 2004-01-28 18:54:46
|
Just a thought: * Sum the Vs weighted by solid angle to give V' -- take that as your projective plane direction. * Find the farthest point of each projected cone from the origin. Ostensibly you could work out the projected ellipse and work from there, but I bet there's a faster way. * Fit a circle to the points -- your enclosing spotlight is in direction V' with theta coming from that circle. Projecting to a plane only starts to fail as the enclosing angle gets up towards 180, which is an acceptable failure case only. This isn't going to be optimal, and maybe the results won't be good enough, but, I can imagine it being reasonably fast, and it doesn't suffer from hysteresis. For better results you could do a bounding ellipse and work backwards to a spotlight that's not aligned with V'. I wonder if it's not faster to drop down a level and do direct frustum plane fitting to the bounding spheres of the objects? A. 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). 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 > > > |
From: Greg S. <gr...@st...> - 2004-01-28 20:42:13
|
I know you asked for an algorithm to merge cones, but for what you're trying to do, do you have access to any other information besides the cone for each object? I imagine it would be pretty easy to merge the bounding boxes of your objects, and form a cone from the light to the center of the bbox, with a theta of arcsin(bounding_radius/distance)? I'm sure I'm missing something here though - maybe this isn't tight enough of a fit. -----Original Message----- From: gda...@li... [mailto:gda...@li...]On Behalf Of Tom Forsyth Sent: Tuesday, January 27, 2004 2:38 PM 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 |
From: Tom F. <tom...@ee...> - 2004-01-29 05:45:05
|
Yeah, a bounding box aligned to, say, the world axis isn't nearly good enough. Think of two very small objects at (1,1,1) and (10,10,10) relative to the light. The bounding cone is pretty slim. But the bounding box is 9 units on a side, which is enormous! And yes, this is a moderately common case :-) TomF. > -----Original Message----- > From: gda...@li... > [mailto:gda...@li...] On > Behalf Of Greg Seegert > Sent: 28 January 2004 20:41 > To: gda...@li... > Subject: RE: [Algorithms] Bounding cones. > > > I know you asked for an algorithm to merge cones, but for > what you're trying > to do, do you have access to any other information besides > the cone for each > object? I imagine it would be pretty easy to merge the > bounding boxes of > your objects, and form a cone from the light to the center of > the bbox, with > a theta of arcsin(bounding_radius/distance)? I'm sure I'm > missing something > here though - maybe this isn't tight enough of a fit. > > -----Original Message----- > From: gda...@li... > [mailto:gda...@li...]On Behalf Of Tom > Forsyth > Sent: Tuesday, January 27, 2004 2:38 PM > 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 > > > > ------------------------------------------------------- > 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: John P. <jo...@3d...> - 2004-01-31 04:40:02
|
Hmm, maybe this would work, but it may be a bit slow: For each cone, build a list vectors that wrap around the cones origin (they would start at the origin, and travel along the cone hull). The number of vectors for each cone would be a function of each cones cos(theta). Take two neighboring vectors (they should be neighbors, and belong to the same cone), and create a plane, where the normal should point away from all other vector end points. If all other vectors are on the back side of this plane, this is the correct plane, otherwise choose another two neighboring vectors until you find the correct plane. If you don't find any planes that satisfy this, you can't solve it. Basically, we're looking for planes that are in the outer edge of the cones. While checking if this was the correct plane, remember the vector that was the farthest from this plane, call the vector V, and the dist D. Of all the planes that you find, choose the plane with the largest D. Using this plane, and the other vector, shoot a vector down the center. This is the direction of the new cone, and the angle can be derived from the plane and vector (V) the you found. Hope this makes sense. It's probably a tad bit slow, as it's O(n2), but could be a good starting point? 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). 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 > |
From: Tom F. <tom...@ee...> - 2004-01-31 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: gda...@li...=20 > [mailto:gda...@li...] On=20 > Behalf Of John Pollard > Sent: 29 January 2004 04:48 > To: gda...@li... > 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 circular-cross-section cones in 3D space,=20 > 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)=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 loose-fitting 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 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 >=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 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 |
From: Crosbie F. <cr...@cy...> - 2004-01-31 21:22:42
|
How about tesselating a sphere and precomputing indices to bounding circles? Say your sphere is tesselated in regular polygons (bar peculiar tiles). You tabulate a list of all potential minimal bounding circles (for all permutations of tesselation pattern). Each polygon contains a list of indices to all circles that contain it. You then project your cones and wherever they cover or intersect with a tile, the whole tile is marked, and all indexed circles are rejected. What you are then left with is a list of virgin circles. If you've ordered them by size, it should be easy to find the largest. This is then your candidate minimal bounding circle. You can shrink this by the diameter of a tile, and create a rejection circle and reject all cones that fall within it. You could conduct this process iteratively on successively greater resolution tesselated spheres. Perhaps you map a peculiar tile to your cones' centroid (to eliminate it and its antipode from consideration - if the peculiarities are only at poles)? There may also be symmetry optimisations available. |