From: Jonathan Blow <jon@nu...>  20040128 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 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 