## RE: [Algorithms] Bounding cones.

 RE: [Algorithms] Bounding cones. From: Nick Carter - 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:jon@...] > Sent: Tuesday, January 27, 2004 5:44 PM > To: gdalgorithms-list@... > 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" > 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 > > > ------------------------------------------------------- > 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_id=6188 > ```