Work at SourceForge, help us to make it a better place! We have an immediate need for a Support Technician in our San Francisco or Denver office.

Re: [Algorithms] Bounding cones.

 Re: [Algorithms] Bounding cones. From: Jonathan Blow - 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" To: 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: gdalgorithms-list-admin@... > > [mailto:gdalgorithms-list-admin@...] On > > Behalf Of Mark Duchaineau > > Sent: 27 January 2004 23:32 > > To: gdalgorithms-list@... > > 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 > GDAlgorithms-list@... > https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list > Archives: > http://sourceforge.net/mailarchive/forum.php?forum_ida88 ```