RE: [Algorithms] Bounding cones.

[Tom F. <tom...@ee...>]

Aha:

"It can be shown that the central axis of such a cone has the following
property: if one associates a point on the unit sphere with each face =
normal
in the cluster, and computes the 3D convex hull of this pointset, must =
pass
through the closest point from the origin to that convex hull."

I guess that makes sense - the 2D version of the same thing "obviously
works", but my brain doesn't find the 3D version as obvious.

Not all that sure I want to try constructing the convex hull of circles =
at
runtime though - sounds expensive.

...

Argh. I worked out a lovely O(n) algorithm where you only ever track at =
most
three cones that make up the bounding hull feature closest to the origin
(either an edge or a plane) as you go along (similar to what Nick was
saying). Problem is, that's not enough. You can never guarantee to throw
away information and still get an optimal hull.

Imagine a regular n-gon of cones of the same radius (Ci). Then place =
another
cone (C0) quite a way off. So the bounding cone is now formed by C0 and =
one
or two of Ci - the ones furthest from C0. But depending where you put =
C0,
it's a different Ci. So until you have C0, you can never throw away any =
Ci,
no matter how big n is.

Which means that although Nick is (probably) right when he says that any
bounding cone is formed by at most three cones, adding another cone may
produce a new bounding cone that uses a _completely different three_. =
Which
is a pain.

However, I suspect the number you actually need to track will be =
reasonable
in practice - you should be able to throw most of them away (anything =
that
is inside the hull is definately never going to be part of the hull in
future). So this is certainly a plausable avenue of attack.

Got me some maths to do.

TomF.


> -----Original Message-----
> From: gda...@li...=20
> [mailto:gda...@li...] On=20
> Behalf Of Peter-Pike Sloan
> Sent: 28 January 2004 05:50
> To: gda...@li...
> Subject: RE: [Algorithms] Bounding cones.
>=20
>=20
> I haven't been following this thread that closely, but pedro=20
> sander did
> a very nice job of computing optimnal sphere/cone hiearchies for his
> Silhouette Clipping paper:
>=20
> http://pedrosander.com/publications/
>=20
> (section 5 in the above paper)
>=20
> -Peter-Pike Sloan
>=20
> -----Original Message-----
> From: gda...@li...
> [mailto:gda...@li...] On Behalf Of
> Jonathan Blow
> Sent: Tuesday, January 27, 2004 7:27 PM
> To: gda...@li...
> Subject: Re: [Algorithms] Bounding cones.
>=20
> > However, you might have something there. If I simply took n points=20
> > around the edge of each cone, where n is about 3-6 (could=20
> even change=20
> > the number according to the size of the cone - typically I=20
> will have=20
> > cones of widely varying sizes, since the objects vary=20
> widely in size,=20
> > and are at very different distances to the light). Then=20
> cluster them,=20
> > and use that as a starting guess. As long as the initial guess is=20
> > fairly accurate, I think it's true to say you can then do the=20
> > one-at-a-time merging and still get a very good bounding cone at the
> end.
>=20
> The covariance stuff is really fast, once you have the initial values
> inside the covariance matrices; you can just transform them=20
> and add them
> after that.
> And actually, you can compute the closed-form covariance of a=20
> cone, and
> evaluating that would probably be faster than using individual points.
> So my original 1000 points idea was overzealous and unnecessary.
>=20
> By default when using such closed-form covariance, big cones would be
> favored, but you can compensate for this just by scaling up=20
> the density
> of the small cones.
>=20
> I'm not saying it's the best solution for your problem, but it's worth
> trying if yer gonna investigate various solutions.
>=20
>=20
>=20
> -------------------------------------------------------
> The SF.Net email is sponsored by EclipseCon 2004 Premiere=20
> 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=3D6188
>=20
>=20
> -------------------------------------------------------
> 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
>=20