Analytic formulas for distance between geometric shapes.
John C Hart
jch at ad.uiuc.edu
Wed Jul 31 11:11:30 PDT 2002
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.
More information about the Compgeom-announce
mailing list