RE: [Algorithms] Bounding cones.

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

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 cone-set 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, cone-valued 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...@ee...] 
> Sent: Tuesday, January 27, 2004 4:05 PM
> To: gda...@li...
> 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
>