Princeton University
Computer Science Department

Computer Science 597D 
Advanced Topics in Computer Science: 
Geometric Modeling & Analysis
Fall 2003

Thomas Funkhouser

Global Shape Descriptors

Local Shape Descriptors


M. Audette, F. Ferrie, and T. Peters,
"An Algorithmic Overview of Surface Registration Techniques for Medical Imaging", 
Medical Image Analysis, Vol. 4, No. 3, Sep. 2000, pp 201-217. 

P. Besl and N. McKay,
"A Method for Registration of 3-D Shapes", 
IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol. 14, No. 2, Feb. 1992. 

J. Castanho, O. Bellon, and C. Tozzi,
"Image Registration and Image Interpolation in Volume Rendering of Cross Sections", 
Proceedings of IEEE International Conference on Systems, Man, and Cybernetics, v. 1, p. 1466-1471, 1995. 

P. Chang and J. Krumm,
"Object Recognition with Color Co-occurrence Histograms", 
IEEE Conference on Computer Visionand Pattern Recognition, June 1999. 

W. Grimson and D. Huttenlocher,
"On the Sensitivity of Geometric Hashing", 
Proceedings of the IEEE Third International Conference on Computer Vision, Dec. 1990, pp 334-338. 

W. Grimson and D. Huttenlocher,
"On the Sensitivity of the Hough Transform for Object Recognition", 
IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol. 12, No. 3, Mar. 1990, pp. 255-274. 

Y. Hecker and R. Bolle,
"On Geometric Hashing and the Generalized Hough Transform", 
IEEE Transactions on Systems, Man, and Cybernetics, Vol. 24, No. 9, Sep. 1994. 

Y. Lamdan and H. Wolfson,
"Geometric Hashing: A General and Efficient Model-Based Recognition Scheme", 
Proceedings of the IEEE Second International Conference on Computer Vision, Dec. 1988, pp 238-249. 

Y. Lamdan and H. Wolfson,
"On the error analysis of 'geometric hashing'", 
Proceeedings of the IEEE Conference on Computer Vision and Pattern Recognition, 1991, pp 22-27. 

H. Lee, J. Kittler, and K. Wong
"Generalised Hough Transform in Object Recognition", 
Proceedings of the 11th IAPR Conference on Pattern Recognition, 1992, pp 285-289. 

J. Maintz and M. Viergever,
"A Survey of Medical Image Registration", 
Medical Image Analysis, Vol. 2, No. 1, Sep. 1998, pp 1-36. 

C. Maurer and J. Fitzpatrick,
"A Review of Medical Image Registration", 
in Interactive ImageGuided Neurosurgery, R. J. Maciunas, Ed., pp. 17-44,
American Association of Neurological Surgeons, Park Ridge, IL, 1993. 

S. Rusinkiewicz and M. Levoy,
"Efficient Variants of the ICP Algorithm", 
Proceedings of the Third Intl. Conf. on 3D Digital Imaging and Modeling, 2001, pp. 145-152. 

K. Toennies, J. Udupa, G. Herman,
"Registration of 3D Objects and Surfaces", 
IEEE Computer Graphics and Applications, 1990, pp. 52-62. 

R. Veltkamp,
"Shape Matching: Similarity Measures and Algorithms", 
International Conference on Shape Modeling and Applications, 2001, pp. 188-197. 

H. Wolfson and I. Rigoutsos,
"Geometric Hashing: An Overview", 
IEEE Computational Science and Engineering, Vol. 4, Issue 4, 1997, pp. 10-21. 

Curve Matching

Surface Correspondence

Model-Based Shape Recognition

Mesh Segmentation

B. Chazelle, D. Dobkin, N. Shourhura, and A. Tal, 
"Strategies for Polyhedral Surface Decomposition: An experimental study",
Computational Geometry: Theory and Applications, 7, 4-5:327-342, 1995.

X. Li, T. Toon, T. Tan, and Z. Huang, 
"Decomposing meshes for interactive applications",
In Proceedings of 2001 Symposium on Interactive 3D Graphics: 35-42, 2001.

A. Mangan, and R. Whitaker, 
"Partitioning 3D Surface Meshes using Watershed Segmentation",
IEEE Transactions on Visualization and Computer Graphics, 5, 4:308-321, 1999.

S. Shlafman, A. Tal, and S. Katz, 
"Metamorphosis of Polyhedral Surfaces using Decomposition",
In Eurographics: 219-228, 2002.

E. Zuckerberger, A. Tal, and S. Shlafman 
"Polyhedral Surface Decomposition with Applications",
Computers & Graphics, 26, 5:733-743, 2002.

S. Katz and A. Tal, 
"Hierarchical Mesh Decomposition using Fuzzy Clustering and Cuts",
In SIGGRAPH, ACM Transactions on Graphics, Volumne 22, Issue 3:954-961, 2003.

Medial Axis Computation

H. Blum,
A Transformation for Extracting New Descriptors of Shape,
in W. Wathen-Dunn, editor, Models for the Perception of Speech and Visual Form,
MIT Press, Cambridge MA, (1967).

C. J. Hilditch,
Linear Skeletons from Square Cupboards,
Machine Intelligence (4), 1969, pp. 403-420.

F. Leymarie and M. D. Levine,
Simulating the Grassfire Transform Using an Active Contour Model,
IEEE Transactions on Pattern Analysis and Machine Intelligence, v. 14, no. 1, pp. 56-75, 1992

F. L. Bookstein.
The line-skeleton.
Computer Graphics and Image Processing, 11:123--37, 1979.

G. Sanniti di Baja
Well-Shaped, Stable, and Reversible Skeletons from the (3,4)-Distance Transform,
Journal of Visual Communication and Image Representation, v. 5, no. 1, pp. 107-115. 1994

R. L. Ogniewicz and O. Kübler,
Hierarchic Voronoi Skeletons,
Pattern Recognition, 1995

T. B. Sebastian, P. N. Klein and B. B. Kimia
Recognition of Shapes by Editing Shock Graphs,
International Conference On Computer Vision, pp. 755-762, 2001

Skeleton Extraction

Topological Shape Matching

Steven Gold and Anand Rangarajan, 
"A Graduated Assignment Algorithm for Graph Matching,"
IEEE Transactions on Pattern Analysis and Machine Intelligence, 18(4):377--388, April 1996.

K. Siddiqi, A. Shokoufandeh, S. Dickinson, and S. Zucker,
"Shock Graphs and Shape Matching", 
International Journal of Computer Vision, Volume 30, 1999, pp 1--24. 

Ali Shokoufandeh, Ivan Marsic, and Sven Dickinson, 
"View-Based Object Recognition Using Saliency Maps," 
Image and Vision Computing, Volume 17, 1999, pp 445--460.

A. Shokoufandeh, S. Dickinson, K. Siddiqi, and S. Zucker,
"Indexing using a Spectral Encoding of Topological Structure", 
IEEE Conference on Computer Vision and Pattern Recognition, Fort Collins, CO, June 1999, pp 491--497.

Marcello Pelillo, Kaleem Siddiqi, and Steven Zucker, 
"Matching hierarchical structures using association graphs,"
IEEE Transactions on Pattern Analysis and Machine Intelligence, 21(11):1105-1120, 1999. 

Bin Luo and Edwin Hancock, 
"Structural Graph Matching Using the EM Algorithm and Singular Value Decomposition", 
IEEE PAMI, Vol 23, No 10, October 2001, pp. 1120-1136.

Thomas Sebastian, Philip Klein, Benjamin Kimia, 
"Recognition of Shapes by Editing Shock Graphs,", 
Proceedings, ICCV 2001, pp 755-762.

Marcello Pelillo, 
"Matching free trees, maximal cliques, and monotone game dynamics," 
IEEE Transactions on Pattern Analysis and Machine Intelligence, 24(11), 2002. 

Ali Shokoufandeh, Sven Dickinson, Clas Jonsson, Lars Bretzner, and Tony Lindeberg, 
"On the Representation and Matching of Qualitative Shape at Multiple Scales",
Proceedings, European Conference on Computer Vision, Springer, Copenhagen, May 2002.

Serhiy Kosinov and Terry Caelli, 
"Inexact Multisubgraph Matching Using Graph Eigenspace and Clustering Models", 
Proceedings, SSPR 2002, Springer, August 2002, pp 133-142.

M. Fatih Demirci, Ali Shokoufandeh, Yakov Keselman, Sven Dickinson, and Lars Bretzner, 
``Many-to-Many Matching of Scale-Space Hierarchies using Metric Embedding'',
Proceedings, Scale-Space '03, Skye, UK, June 10-12, 2003.

Yakov Keselman, Ali Shokoufandeh, M. Fatih Demirci, and Sven Dickinson, 
"Many-to-Many Graph Matching via Metric Embedding", 
Proceedings, IEEE Conference on Computer Vision and Pattern Recognition, Madison, WI, June 2003.

Sven Dickinson's publications

Dickinson & Shoukoufandeh's course in Copenhagen

View-Based Shape Matching

Feature Detection

Symmetry Detection

Symmetry Transform

3D Object Representations

Taxonomy of Geometric Representations
Bruce Naylor

Computational Representations of Geometry,
Bruce Naylor et al.,
SIGGRAPH `96 Course Notes, 1996.

A Primer on Shapes: Curves and Surfaces,
Ardy Gshtasby, Alyn Rockwood, Demetri Terzopolos,
Siggraph 2001 Course 7, August, 2001.

New Directions in Shape Representations,
Hanspeter Pfister, Alyn Rockwood, et al.
Siggraph 2001 Course 33, August, 2001.

Mesh Representations

Winged-Edge Polhedron Representation,
B. Baumgard,
Ph.D. Thesis, Stanford University, STAN-CS-320, 1972.

I.C. Braid, R.C. Hillyard, I.A. Stroud,
Stepwise Construction of Polyhedra in Geometric Modelling,
CAD Group Document No. 100, University of Cambridge Computer Laboratory, October, 1978.

Tony Woo,
A Combinatorial Analysis of Boundary Data Structure Schemata,
IEEE CG&A, March, 1985

Kevin Weiler,
Edge-Based Data Structures for Solid Modeling in Curved-Surface Environments,
IEEE CG&A, January, 1985.

Voxel Representations

Display of Surfaces from Volume Data,
Marc Levoy,
IEEE Computer Graphics and Applications,Vol. 8, No. 3, May, 1988
[Volume Rendering at Stanford]

Volume Graphics,
A. Kaufman, D. Cohen and R. Yagel,
IEEE Computer, Vol. 26, No. 7, July 1993, pp. 51-64.
[SUNY at Stoney Brook Visualization Lab]

Volume-Sampled 3D Modeling,
S. Wang and A. Kaufman,
IEEE Computer Graphics & Appplications 14(5), September 1994, pp.26-32.

Voxels as a Computational Representation of Geometry,
A. Kaufman,
SIGGRAPH `96 Course Notes.

Mesh Simplification

Adaptive display algorithm for interactive frame rates during visualization of complex virtual environments
Thomas A. Funkhouser and Carlo H. Séquin,

Polygonal Simplification: An Overview,
Carl Erikson,
Technical Report TR96-016, University of North Carolina, Chapel Hill, 1996.
[Carl Erikson's Simplification Page]

A Survey of Polygonal Simplification Algorithms,
David Luebke,
Technical Report TR97-045, University of North Carolina, Chapel Hill, 1997.

Survey of Surface Simplification Algorithms,
Paul Heckbert and Michael Garland,
SIGGRAPH 97 course on Multiresolution Surface Modeling, 1997.

Surface Simplification Using Quadric Error Metrics,
Michael Garland and Paul Heckbert,
[Michael Garland's page on simplification with quadric error measures]
[Michael Garland's Multiresolution Modeling Page]

A Developer’s Survey of Polygonal Simplification Algorithms
David Luebke,
IEEE Computer Graphics &Applications (May 2001).
[David Luebke's Simplification Page at UNC]

Level of Detail for 3D Graphics. 
David Luebke, Martin Reddy, Jonathan Cohen, Amitabh Varshney, Benjamin Watson, and Robert Huebner. 
Morgan-Kaufmann Publishers, San Francisco (July 2002).

Multiresolution Meshes

Matthias Eck, et al,
Multiresolution Analysis of Arbitrary Meshes,

Progressive Meshes,
Hugues Hoppe,

Dynamic View-Dependent Simplification of Polygonal Models,
Julie Xia and Amitabh Varshney, 
IEEE Visualization `96.

A. Certain, J. Popovic, T. Duchamp, D. Salesin, W. Stuetzle, and T. DeRose,
Interactive Multiresolution Surface Viewing,

Real-time, continuous level of detail rendering of height fields
Peter Lindstrom, David Koller, William Ribarsky, Larry F. Hodges, Nick Faust and Gregory A. Turner,

Progressive simplicial complexes,
Jovan Popovic and Hugues Hoppe,

Multiresolution Surfaces of Arbitrary Topological Type,
M. Lounsbery, T. DeRose, and J. Warren,
ACM Transactions on Graphics, 16, 1, January, 1997, 34-73.

View-dependent refinement of progressive meshes
Hugues Hoppe

View-dependent simplification of arbitrary polygonal environments
David Luebke and Carl Erikson

Multiresolution Modeling: Survey & future opportunities,
M. Garland, Eurographics '99,
State of the Art Report, September 1999.

Mesh Processing

Geometric Signal Processing on Large Polygonal Meshes,
Leif Kobbelt, Gabriel Taubin,
Siggraph 2001 Course 17, August, 2001.

Point-Based Modeling and Rendering

The Use of Points as a Display Primitive
Marc Levoy and Turner Whitted
Technical Report 85-022, Computer Science Department,
University of North Carolina at Chapel Hill, January, 1985.
[Paper link]

Point Sample Rendering,
Grossman, J.P. and Dally, William J.,
Proceedings of the 9th Eurographics Workshop on Rendering,
June 29 - July 1, 1998, Vienna, Austria, pp. 181-192.

A Survey and Classification of Real Time Rendering Methods,
Matthias Zwicker, Markus Gross, Hanspeter Pfister,
MERL, TR2000-09,  April 2000.

Surfels: surface elements as rendering primitives
Hanspeter Pfister, Matthias Zwicker, Jeroen van Baar and Markus Gross,
[Surfels link]

QSplat: a multiresolution point rendering system for large meshes
Szymon Rusinkiewicz and Marc Levoy,
[QSplat link]

Capturing,Processing and Rendering Real-World Scenes.
Nyland, Lars and Lastra, Anselmo and McAllister, David K. and Popescu, Voicu and McCue, Chris,
(to appear in) Videometrics and Optical Methods for 3D Shape Measurement,
Electronic Imaging 2001, Photonics West, January 22, 2001. SPIE Vol. 4309.
[UNC's laser scanning page] [UNC's point rendering page]

Interactive exploration of acquired 3D data.
Nyland, Lars, David McAllister, Voicu Popescu, Chris McCue, and Anselmo Lastra,
Proceedings of the SPIE Applied Image and Pattern Recognition Conference (AIPR99)
Washington, DC, October 13-15, 1999.

Ray Tracing Point Sampled Geometry
Gernot Schaufler and Henrik Wann Jensen
Proc. 2000 Eurographics Workshop on Rendering

Surface splatting
Matthias Zwicker, Hanspeter Pfister, Jeroen van Baar and Markus Gross

Spectral processing of point-sampled geometry
Mark Pauly and Markus Gross

Implicit Surfaces

Beyond Blobs: Recent Advances in Implicit Surfaces
Terry Yoo, Greg Turk, H. Quynh Dinh, John Hart, James O'Brien, Ross Whitaker
Course 29 Notes, SIGGRAPH 2002.

Introduction to Implicit Surfaces 
J. Bloomenthal, ed., 
Morgan Kaufmann Publishers, 1997.

Implicit Surfaces
Jules Bloomenthal,
to appear in the Encyclopedia of Computer Science and Technology (ã Marcel Dekker, Inc., NY).

Convolution Surfaces
Bloomenthal, J. and Shoemake, K. 

Implicit Surfaces that Interpolate,
Greg Turk, Huong Quynh Dinh, James O'Brien and Gary Yngve 
Shape Modelling International 2001
Genova, Italy, May 7-11, 2001, pp. 62-71.

Shape Transformation Using Variational Implicit Functions,
Greg Turk and James O'Brien, 
SIGGRAPH 99, August 1999, pp. 335-342.

Implicit Surfaces for Geometric Modeling and Computer Graphics
Jai Menon, Brian Wyvill, et al.
Course 11 Notes, SIGGRAPH 96

Brian Wyvill, Geoff Wyvill
Field Functions for Implicit Surfaces
Visual Computer, Issue 5 1989

Polygonization of Implicit Surfaces
Jules Bloomenthal
Computer Aided Geometric Design, Issue 5, 1988

Brian Wyvill, Craig McPheeters, Geoff Wyvill
Animating Soft Objects
The Visual Computer, Issue 4 1986

Brian Wyvill, Craig McPheeters, Geoff Wyvill
Soft Objects
Advanced Computer Graphics (Proc. CG Tokyo 1986)

Nelson L. Max
Computer Representation of Molecular Surfaces
IEEE Computer Graphics and Applications, Aug 1983

James F. Blinn
A Generalization of Algebraic Surface Drawing
ACM Transactions on Graphics, July 1982

A Bibliography of Implicit Surfaces

Another Bibliograph of Implicit Surfaces