Geometric structures for three-dimensional shape representation

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Geometric structures for three-dimensional shape representation

Full text

Pdf (1.17 MB)

Source

ACM Transactions on Graphics (TOG) archive
Volume 3 , Issue 4 (October 1984) table of contents

Pages: 266 - 286

Year of Publication: 1984

ISSN:0730-0301

Author

Jean-Daniel Boissonnat

INRIA, Domaine de Voluceau, Rocquencourt, B. P. 105-78150 Le Chesnay Cedex, France

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 21, Downloads (12 Months): 223, Citation Count: 56

Additional Information:

references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/357346.357349 What is a DOI?

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Jon Louis Bentley , Bruce W. Weide , Andrew C. Yao, Optimal Expected-Time Algorithms for Closest Point Problems, ACM Transactions on Mathematical Software (TOMS), v.6 n.4, p.563-580, Dec. 1980 [doi>10.1145/355921.355927]
	2	BOISSONNAT, J.D. Representation of objects by triangulating points in 3-D space. In ICPR 82 (Munich). 1982, IEEE, Silver Springs, CA. pp. 830-832.
	3	BOWVER, A. Computing Dirichlet tessetations. Comput. J. 24, 2 (May 1981), 162-166.
	4	James P. Ducan , Susan G. Mair, Sculptured Surfaces in Engineering and Medicine, Cambridge University Press, New York, NY, 1983
	5	FAUGEaAS, O~ D., HEad.aT, M., Muss{, P., AND BOISSONNAT, J. }:). Polyhedral approximation of 3-D objects without holes. Comput. Graph. Image Proc. 25 {Feb. 1984}, 169-183.
	6	FRANKE, R. Scattered data interpolation: Test of some methods. Math. Comput. 38, 157 (Jan. 1982), 181-200.
	7	Jerome H. Freidman , Jon Louis Bentley , Raphael Ari Finkel, An Algorithm for Finding Best Matches in Logarithmic Expected Time, ACM Transactions on Mathematical Software (TOMS), v.3 n.3, p.209-226, Sept. 1977 [doi>10.1145/355744.355745]
	8	H. Fuchs , Z. M. Kedem , S. P. Uselton, Optimal surface reconstruction from planar contours, Communications of the ACM, v.20 n.10, p.693-702, Oct. 1977 [doi>10.1145/359842.359846]
	9	GmLiN, P.J. Graphs, Surface and Homology. Chapman and Hall, London, England, 1977.
	10	HERMELiNE P. Triangulation automatique d'un polyedre en dimension N. R.A.LR.O. Anal. Numer. 16, 3 {1982), 211-242.
	11	KLEE, V. On the complexity of d-dimensional Voronoi diagrams. Arch. Math. 34 (1980), 75-80.
	12	LEE, D. T. Medial axis transformation of a planar shape. IEEE Trans. Pattern Anal. Mach. Intell. PAMI-4, 4 (July 1982), 363-369.
	13	O'ROURKE, J. Triangulation of minimal area as 3-D object models. In Proceedings of the International Joint Confereace on Artificial Intelligence 81 (Vancouver, Canada). 1981, pp. 664- 666.
	14	F. P. Preparata , S. J. Hong, Convex hulls of finite sets of points in two and three dimensions, Communications of the ACM, v.20 n.2, p.87-93, Feb. 1977 [doi>10.1145/359423.359430]
	15	ROGEaS, C.A. Packing and Covering. Cambridge University Press, Cambridge, England, 1964.
	16	SATO, Y., KITAGAWAS, H., AND FtJJITA, H. Shape measurement of curved objects using multiple slit-ray projections. IEEE Trans. Pattern Anal. Much. Intell. PAMI 4, 6 (Nov. 1982).
	17	Michael Ian Shamos, Computational geometry., 1978
	18	SHAPIRO, L. G., AND HARALICK, R.M. Decomposition of two-dimensional shapes by graphtheoretical clustering. IEEE Trar~. Pattern Anal. Mach. Intel}. PAMI-3 (Jan, 1979), 10-20.
	19	SJBSON, R. Locally equiangular triangulation. Comput. J. 21 (1978), 243-245.
	20	WATSON, P. P. Computing the a-dimensional Delaunay triangulation with application to Voronoi polytopes. Comput. J. 24, 2 (May 1981), 167-172.
	21	WILLIAMS, J, W.J. Algorithm 232. Heapsort. Commun. ACM 7, 6 (June 1964), 347-348.
	22	ZAHN, C. T. Graph-theoretical methods for detecting and describing gestalt cluster. IEEE Trans. Compat. C-20 (Jan. 1971), 68-86.

CITED BY 56

	Nina Amenta , Sunghee Choi , Ravi Krishna Kolluri, The power crust, Proceedings of the sixth ACM symposium on Solid modeling and applications, p.249-266, May 2001, Ann Arbor, Michigan, United States
	Nina Amenta , Marshall Bern, Surface reconstruction by Voronoi filtering, Proceedings of the fourteenth annual symposium on Computational geometry, p.39-48, June 07-10, 1998, Minneapolis, Minnesota, United States
	Chandrajit L. Bajaj , Fausto Bernardini , Guoliang Xu, Automatic reconstruction of surfaces and scalar fields from 3D scans, Proceedings of the 22nd annual conference on Computer graphics and interactive techniques, p.109-118, September 1995
	Stefan Funke , Edgar A. Ramos, Smooth-surface reconstruction in near-linear time, Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.781-790, January 06-08, 2002, San Francisco, California
	Nickolas S. Sapidis , Renato Perucchio, Domain Delaunay Tetrahedrization of arbitrarily shaped curved polyhedra defined in a solid modeling system, Proceedings of the first ACM symposium on Solid modeling foundations and CAD/CAM applications, p.465-480, June 05-07, 1991, Austin, Texas, United States
	Brian Curless , Marc Levoy, A volumetric method for building complex models from range images, Proceedings of the 23rd annual conference on Computer graphics and interactive techniques, p.303-312, August 1996
	P. D. Alevizos , J. Boissonnat , M. Yvinec, An optimal O(n log n) algorithm for contour reconstruction from rays, Proceedings of the third annual symposium on Computational geometry, p.162-170, June 08-10, 1987, Waterloo, Ontario, Canada
	Frederic Banégas , Marc Jaeger , Dominique Michelucci , M. Roelens, The ellipsoidal skeleton in medical applications, Proceedings of the sixth ACM symposium on Solid modeling and applications, p.30-38, May 2001, Ann Arbor, Michigan, United States
	Xuetao Li , Tong Wing Toon , Zhiyong Huang, Decomposing polygon meshes for interactive applications, Proceedings of the 2001 symposium on Interactive 3D graphics, p.35-42, March 2001
	Tamal K. Dey , Joachim Giesen, Detecting undersampling in surface reconstruction, Proceedings of the seventeenth annual symposium on Computational geometry, p.257-263, June 2001, Medford, Massachusetts, United States
	Dominique Attali, r-regular shape reconstruction from unorganized points, Proceedings of the thirteenth annual symposium on Computational geometry, p.248-253, June 04-06, 1997, Nice, France
	Jean-Daniel Boissonnat , Frédéric Cazals, Smooth surface reconstruction via natural neighbour interpolation of distance functions, Proceedings of the sixteenth annual symposium on Computational geometry, p.223-232, June 12-14, 2000, Clear Water Bay, Kowloon, Hong Kong
	M. Dillencourt, Toughness and Delaunay triangulations, Proceedings of the third annual symposium on Computational geometry, p.186-194, June 08-10, 1987, Waterloo, Ontario, Canada
	Fausto Bernardini , Chandrajit L. Bajaj , Jindong Chen , Daniel R. Schikore, A triangulation-based object reconstruction method, Proceedings of the thirteenth annual symposium on Computational geometry, p.481-484, June 04-06, 1997, Nice, France
	Nina Amenta , Marshall Bern , Manolis Kamvysselis, A new Voronoi-based surface reconstruction algorithm, Proceedings of the 25th annual conference on Computer graphics and interactive techniques, p.415-421, July 1998
	Herbert Edelsbrunner , Ernst P. Mücke, Three-dimensional alpha shapes, ACM Transactions on Graphics (TOG), v.13 n.1, p.43-72, Jan. 1994
	Tamal K. Dey , Wulue Zhao, Approximate medial axis as a voronoi subcomplex, Proceedings of the seventh ACM symposium on Solid modeling and applications, June 17-21, 2002, Saarbrücken, Germany
	Greg Turk , Marc Levoy, Zippered polygon meshes from range images, Proceedings of the 21st annual conference on Computer graphics and interactive techniques, p.311-318, July 1994
	Duane W. Storti , George M. Turkiyyah , Mark A. Ganter , Chek T. Lim , Derek M. Stal, Skeleton-based modeling operations on solids, Proceedings of the fourth ACM symposium on Solid modeling and applications, p.141-154, May 14-16, 1997, Atlanta, Georgia, United States
	Udo Adamy , Joachim Giesen , Matthias John, Surface reconstruction using umbrella filters, Computational Geometry: Theory and Applications, v.21 n.1, p.63-86, January 2002
	Mark Foskey , Ming C. Lin , Dinesh Manocha, Efficient computation of a simplified medial axis, Proceedings of the eighth ACM symposium on Solid modeling and applications, June 16-20, 2003, Seattle, Washington, USA
	Marc Alexa , Johannes Behr , Daniel Cohen-Or , Shachar Fleishman , David Levin , Claudio T. Silva, Point set surfaces, Proceedings of the conference on Visualization '01, October 21-26, 2001, San Diego, California
	Anders Adamson , Marc Alexa, Approximating and intersecting surfaces from points, Proceedings of the 2003 Eurographics/ACM SIGGRAPH symposium on Geometry processing, June 23-25, 2003, Aachen, Germany
	Dominique Attali , Jean-Daniel Boissonnat , André Lieutier, Complexity of the delaunay triangulation of points on surfaces the smooth case, Proceedings of the nineteenth annual symposium on Computational geometry, June 08-10, 2003, San Diego, California, USA
	Tamal K. Dey , Samrat Goswami, Tight cocone: a water-tight surface reconstructor, Proceedings of the eighth ACM symposium on Solid modeling and applications, June 16-20, 2003, Seattle, Washington, USA
	Raphaëlle Chaine, A geometric convection approach of 3-D reconstruction, Proceedings of the 2003 Eurographics/ACM SIGGRAPH symposium on Geometry processing, June 23-25, 2003, Aachen, Germany
	Eric L. Schwartz , Bjorn Merker , Estarose Wolfson , Alan Shaw, Applications of Computer Graphics and Image Processing to 2D and 3D Modeling of the Functional Architecture of Visual Cortex, IEEE Computer Graphics and Applications, v.8 n.4, p.13-23, July 1988
	Michal Varnuska , Ivana Kolingerova, Improvements to surface reconstruction by the CRUST algorithm, Proceedings of the 19th spring conference on Computer graphics, April 24-26, 2003, Budmerice, Slovakia
	Herbert Edelsbrunner , Ernst P. Mücke, Three-dimensional alpha shapes, Proceedings of the 1992 workshop on Volume visualization, p.75-82, October 19-20, 1992, Boston, Massachusetts, United States
	Sanjeev Saxena , P. C. Bhatt , V. C. Prasad, Efficient VLSI Parallel Algorithm for Delaunay Triangulation on Orthogonal Tree Network in Two and Three Dimensions, IEEE Transactions on Computers, v.39 n.3, p.400-404, March 1990
	Fausto Bernardini , Joshua Mittleman , Holly Rushmeier , Cláudio Silva , Gabriel Taubin, The Ball-Pivoting Algorithm for Surface Reconstruction, IEEE Transactions on Visualization and Computer Graphics, v.5 n.4, p.349-359, October 1999
	Marc Soucy , Denis Laurendeau, A General Surface Approach to the Integration of a Set of Range Views, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.17 n.4, p.344-358, April 1995
	P. T. Sander , S. W. Zucker, Inferring Surface Trace and Differential Structure from 3-D Images, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.12 n.9, p.833-854, September 1990
	Ravikrishna Kolluri , Jonathan Richard Shewchuk , James F. O'Brien, Spectral surface reconstruction from noisy point clouds, Proceedings of the 2004 Eurographics/ACM SIGGRAPH symposium on Geometry processing, July 08-10, 2004, Nice, France
	Marc Alexa , Johannes Behr , Daniel Cohen-Or , Shachar Fleishman , David Levin , Claudio T. Silva, Computing and Rendering Point Set Surfaces, IEEE Transactions on Visualization and Computer Graphics, v.9 n.1, p.3-15, January 2003
	Tamal K. Dey , Joachim Giesen , Samrat Goswami , James Hudson , Rephael Wenger , Wulue Zhao, Undersampling and oversampling in sample based shape modeling, Proceedings of the conference on Visualization '01, October 21-26, 2001, San Diego, California
	H. Ugail, Spine based shape parameterisation for PDE surfaces, Computing, v.72 n.1-2, p.195-206, April 2004
	Tamal K. Dey , Samrat Goswami, Provable surface reconstruction from noisy samples, Proceedings of the twentieth annual symposium on Computational geometry, June 08-11, 2004, Brooklyn, New York, USA
	Lyubomir Zagorchev , Ardeshir Goshtasby, A paintbrush laser range scanner, Computer Vision and Image Understanding, v.101 n.2, p.65-86, February 2006
	Tamal K. Dey , Samrat Goswami, Provable surface reconstruction from noisy samples, Computational Geometry: Theory and Applications, v.35 n.1, p.124-141, August 2006
	Michal Varnuska , Ivana Kolingerova, Boundary filtering approach in surface reconstruction, International Journal of Computational Science and Engineering, v.3 n.1, p.14-22, July 2007
	Ali Akgunduz , Dan Zetu , Pat Banerjee, Viewpoint-based shape recovery from multiple views, Artificial Intelligence for Engineering Design, Analysis and Manufacturing, v.14 n.5, p.359-372, November 2000
	Daniel Freedman, An incremental algorithm for reconstruction of surfaces of arbitrary codimension, Computational Geometry: Theory and Applications, v.36 n.2, p.106-116, February, 2007
	Michael Kazhdan , Matthew Bolitho , Hugues Hoppe, Poisson surface reconstruction, Proceedings of the fourth Eurographics symposium on Geometry processing, June 26-28, 2006, Cagliari, Sardinia, Italy
	P. Alliez , D. Cohen-Steiner , Y. Tong , M. Desbrun, Voronoi-based variational reconstruction of unoriented point sets, Proceedings of the fifth Eurographics symposium on Geometry processing, July 04-06, 2007, Barcelona, Spain
	Jean-Daniel Boissonnat , Pooran Memari, Shape reconstruction from unorganized cross-sections, Proceedings of the fifth Eurographics symposium on Geometry processing, July 04-06, 2007, Barcelona, Spain
	J. D. Boissonnat, Reconstruction of solids, Proceedings of the first annual symposium on Computational geometry, p.46-54, June 05-07, 1985, Baltimore, Maryland, United States
	Hui Xie , Kevin T. McDonnell , Hong Qin, Surface Reconstruction of Noisy and Defective Data Sets, Proceedings of the conference on Visualization '04, p.259-266, October 10-15, 2004
	Udo Adamy , Joachim Giesen , Matthias John, New techniques for topologically correct surface reconstruction, Proceedings of the conference on Visualization '00, p.373-380, October 2000, Salt Lake City, Utah, United States
	Andrew D. J. Cross , Edwin R. Hancock, Graph Matching With a Dual-Step EM Algorithm, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.20 n.11, p.1236-1253, November 1998
	Jochen Süßmuth , Günther Greiner, Ridge based curve and surface reconstruction, Proceedings of the fifth Eurographics symposium on Geometry processing, July 04-06, 2007, Barcelona, Spain
	Michael Kazhdan, Reconstruction of solid models from oriented point sets, Proceedings of the third Eurographics symposium on Geometry processing, July 04-06, 2005, Vienna, Austria
	Marco Marcon , Luca Piccarreta , Augusto Sarti , Stefano Tubaro, Fast PDE approach to surface reconstruction from large cloud of points, Computer Vision and Image Understanding, v.112 n.3, p.274-285, December, 2008
	James Gain , Dominique Bechmann, A survey of spatial deformation from a user-centered perspective, ACM Transactions on Graphics (TOG), v.27 n.4, p.1-21, October 2008
	Hisamoto Hiyoshi, Optimization-based approach for curve and surface reconstruction, Computer-Aided Design, v.41 n.5, p.366-374, May, 2009
	Feng Zhao, Extracting and representing qualitative behaviors of complex systems in phase spaces, Proceedings of the 12th international joint conference on Artificial intelligence, p.1144-1149, August 24-30, 1991, Sydney, New South Wales, Australia