Analytic formulas for distance between geometric shapes.

[John C Hart]

Here's some more references:

This paper has a bunch of distance algorithms for a variety of
primitives in its appendix:
J.C. Hart. Sphere tracing: A geometric method for the antialiased ray
tracing of implicit surfaces. The Visual Computer 12 (10), Dec. 1996,
pp. 527-545. Available online at:
http://graphics.cs.uiuc.edu/~jch/papers/zeno.ps.gz

Some optimizations are also available in:
S. Worley, J.C. Hart. Hyper-rendering of hyper-textured surfaces. Proc.
of Implicit Surfaces '96 , Oct. 1996, pp. 99-104.
http://graphics.cs.uiuc.edu/~jch/papers/hyper.pdf

There's also a really nice book I just bought at SIGGRAPH that has a
chapter devoted to computing distance functions and finding their
stationary points (to find the closest distance from a point to all of
the points on a surface).

	Nicholas M. Patrikalakis & Takashi Maekawa. Shape Interrogation
	for Computer Aided Design and Manufacturing. Springer, 2002.
	ISBN: 3540424547.

Good luck,
-John

> -----Original Message-----
> From: Paul Heckbert [mailto:ph+ at cs.cmu.edu] 
> Sent: Tuesday, July 30, 2002 11:12 PM
> To: Dickinson, John; compgeom-discuss at research. bell-labs. 
> com (E-mail)
> Cc: Hart, John
> Subject: Re: Analytic formulas for distance between geometric shapes.
> 
> 
> Reference regarding distance from a point to an ellipsoid 
> (requires roots of 6th degree polynomial):
> 
> @INCOLLECTION{Hart94,
> AUTHOR={John C. Hart},
> TITLE={Distance to an Ellipsoid},
> BOOKTITLE={Graphics Gems IV},
> EDITOR={Paul Heckbert},
> PAGES={113-119},
> PUBLISHER={Academic Press},
> YEAR={1994},
> ADDRESS={Boston},
> KEYWORDS={ray tracing, ellipse},
> SUMMARY={
> Gives the formulas necessary to find the distance from a 
> point to an ellipsoid, or from a point to an ellipse.  These 
> formulas can be useful for geometric modeling or for ray tracing. }, }
> 
> ----- Original Message -----
> From: "Dickinson, John" <John.Dickinson at nrc.ca>
> To: "compgeom-discuss at research. bell-labs. com (E-mail)" 
> <compgeom-discuss at research.bell-labs.com>
> Sent: Wednesday, July 24, 2002 11:29 AM
> Subject: Analytic formulas for distance between geometric shapes.
> 
> 
> > I am looking for analytic formulas for distance between basic 
> > geometric shapes arbitrarily located and orientated in space.  Any 
> > references
> (papers,
> > books) would be greatly appreciated.
> >
> > The Sphere is the easy example as the distance between two 
> spheres in 
> > the distance between their centers minus the sum of their 
> radii.  On 
> > the other hand orientated boxes can't be done analytically 
> but must be 
> > done face by face.
> >
> > How about other shapes formed by implicit quadratic 
> equations (eggs, 
> > ovaloids, ...) that form not purely symmetric shapes which can be
> orientated
> > inspace. Do any of these shapes have analytic formulae for distance?
> >
> > John
> >
> > --
> > -((Insert standard disclaimer here))-|---  Ray's Rule for 
> Precision ----
> > John Kenneth Dickinson, Ph.D.        |   "Measure with micrometer;
> > Research Council Officer  IMTI-NRC   |    Mark with chalk;
> > email: john.dickinson at nrc.ca         |    Cut with axe."
> >
> >
> >
> > -------------
> > The compgeom mailing lists: see 
> > http://netlib.bell-labs.com/netlib/compgeom/readme.html
> > or send mail to compgeom-request at research.bell-labs.com 
> with the line: 
> > send readme Now archived at 
> > http://www.uiuc.edu/~sariel/CG/compgeom/maillist.html.
> >
> 

-------------
The compgeom mailing lists: see
http://netlib.bell-labs.com/netlib/compgeom/readme.html
or send mail to compgeom-request at research.bell-labs.com with the line:
send readme
Now archived at http://www.uiuc.edu/~sariel/CG/compgeom/maillist.html.