From: Nick Carter <ncarter@nv...>  20040128 01:40:57

Tom, You have a way to compute the exact, minimal bounding cone for a set of 2 cones. Can you figure out a way to compute an exact, minimal bounding cone of 3 cones? I ask because the following seems to be true: that, given a arbitrary collection of 4 cones, one of the cones can be removed from the collection without changing the minimal bounding cone of the collection. Thus, (I postulate) from any collection C of cones, it suffices to select three "pivot cones" c1, c2, c3 from C, such that MinimumBoundingCone({c1,c2,c3}) is a cone that strictly contains every element of C. Or, conjectured another way, the minimum bounding cone of a coneset C is the cone of maximum size from the collection of minimum bounding cones formed by triplets from C. If my reasoning is correct, this should lead to a straightforward search: init: // * number of cones in C int n // * array of cones that we're trying to compute the MBC of array C // * triplet vector we're trying to compute value T=<C[0],C[0],C[0]> // * boolean valued function that returns true iff cone is completely // within boundingcone function Contains(boundingcone,cone) // * a fast, conevalued function that computes a minimum bounding cone of three cones // based on some algebraic definition. function MBC3(cone,cone,cone) loop: for k=0 to n { if (!Contains(MBC3(T[0],T[1],T[2]),C[k])) { // we want to insert C[k] into the triplet T if (Contains( MBC3(C[k], T[1], T[2]), T[0] )) T = <C[k],T[1],T[2]>; goto loop; // throw out T[0] else if (Contains( MBC3(C[k], T[0], T[2]), T[1] )) T = <C[k],T[0],T[2]>; goto loop; // throw out T[1] else if (Contains( MBC3(C[k], T[0], T[1]), T[2] )) T = <C[k],T[0],T[1]>; goto loop; // throw out T[2] else // numerical wonkiness, or else I'm fatally // wrong in my conjecture assert(0); } } // if we get here, MBC3(T) is a MBC of C. Thoughts?  nick carter > Original Message > From: Tom Forsyth [mailto:tom.forsyth@...] > Sent: Tuesday, January 27, 2004 4:05 PM > To: gdalgorithmslist@... > 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 > 