RE: [Algorithms] Bounding cones.

[Nick C. <nc...@nv...>]

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:jo...@nu...] 
> Sent: Tuesday, January 27, 2004 5:44 PM
> To: gda...@li...
> 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" <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
> 
> 
> -------------------------------------------------------
> 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
>