Analytic formulas for distance between geometric shapes.

[Gabriel Taubin]

> From: Dickinson, John 
> To: compgeom-discuss at research. bell-labs. com (E-mail) 
> 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."

You may be interested in these two papers that I wrote quite a while
ago. The problem was to decide which pixels are cut by an algebraic
curve. The approach was based on good (fast, accurate, etc.)
approximations to the distance from the center of the pixel to the
curve (works for higher dimmensions too). The main problem was to make
sure the singularities were properly dealt with.

An Accurate Algorithm for Rasterizing Algebraic Curves and Surfaces,
by G. Taubin.
IEEE Computer Graphics & Applications, March 1994. 

Distance approximations for Rasterizing Implicit Curves,
by G. Taubin.
ACM Transactions on Graphics, January 1994 

You can download the papers from the publications page in my IBM
web site. You will also find a Java applet demo there that you can
play with.

---------------------------------------------------------------------
 Dr. Gabriel Taubin                             taubin at computer.org
 IBM T. J. Watson Research Center               taubin at us.ibm.com
 P.O.Box 704, Yorktown Heights, NY 10598        cell : (914)-217-7378
 http://www.research.ibm.com/people/t/taubin    phone: (914)-784-7095
                                                fax  : (914)-784-7667
---------------------------------------------------------------------




-------------
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.