From: Nick Carter <ncarter@nv...>  20040128 02:54:30

Here's another wildass 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: reintersect 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:jon@...] > Sent: Tuesday, January 27, 2004 5:44 PM > To: gdalgorithmslist@... > 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 twoatatime. > > In unfriendly environments (nonLn, say), the standard > clustering algorithm becomes a sort of twoatatime scheme > anyway (kmeans 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 kmeans scheme will, I think, still give you better > results than the simple twoatatime expandocone solution, > because with kmeans 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://numbernone.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.forsyth@...> > To: <gdalgorithmslist@...> > 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 > > suboptimal, but it's still a good earlyout 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 citeseerfu is strong. Cheers. > > > > TomF. > > > > > Original Message > > > From: gdalgorithmslistadmin@... > > > [mailto:gdalgorithmslistadmin@...] On > > > Behalf Of Mark Duchaineau > > > Sent: 27 January 2004 23:32 > > > To: gdalgorithmslist@... > > > 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 circularcrosssection 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 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 > > >  > 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=6188 > 