More Web Proxy on the site http://driver.im/

Article

An algorithm for deciding similarities of 3-D objects

Authors:

Susumu Furukawa,

Mitsuru KurodaAuthors Info & Claims

SMA '02: Proceedings of the seventh ACM symposium on Solid modeling and applications

Pages 367 - 375

https://doi.org/10.1145/566282.566334

Published: 17 June 2002 Publication History

Abstract

A new algorithm for deciding the similarity of polyhedral objects is presented. The method consists of the following five sub-procedures.

A polyhedron is decomposed into only convex components and represented as a hierarchical tree structure with those convex components, which has already been developed by the authors.

From the tree structure, a new data structure called two layer structure, which consists of convex components separated into two layers, i.e., the first layer includes only positive convex components to be added and the second layer represents negative convex components to be subtracted from positive ones, is constructed.

The two layer structure of an object is compared with that of another object.

Each component of an object is compared with the corresponding convex component of the other object.

Similarity of those two polyhedral objects is decided. In addition, similar and dissimilar parts can be recognized, even if two objects are totally not similar.

The algorithm is implemented in C language and numerical similarities are calculated for various concave polyhedrons, and the correlation coefficient between numerical similarities and our feeling is calculated. The result is over 0.8. This means that the numerical similarities closely match our expectation.

References

[1]

Bond, A.H. and Jain, R.: A Formal Definition and Automatic Extraction of Group Technology Codes, In ASME Computers in Engineering Conference, 1, pp.537--542, 1988

[2]

Zhang, H. and Alting, L.: Computerized Manufacturing Process Planning Systems, Chapman & Hall, pp.81--101, 1994

Digital Library

[3]

Grabowski, H., Anderl, R., Geiger, K. and Schmitt, M.: Vision Based On-Line Inspection of Manufactured Parts, Human Aspects in Computer Integrated Manufacturing, Olling, G.J. and Kimura, F.(Eds.), Elsevier Science Pub., pp.593--607, 1992

Digital Library

[4]

Chin, R. and Dyer, C.: Model-Based Recognition in Robot Vision, ACM Computing Surveys, 18, 1, pp.67--108, 1986

Digital Library

[5]

Thompson, W.B., Riesenfeld, R.F. and Owen, J.C.: Determining the Similarity of Geometric Models, Proc. of Workshop on Image Understanding, pp.1157--1160, 1996

[6]

Shum, H.Y., Hebert, M. and Ikeuchi, K.: On 3D Shape Similarity, Proc. IEEE Conf. Computer Vision and Pattern Recognition, pp.526--531, 1996

Digital Library

[7]

Elinson, A., Nau, D.S. and Regli, W.C.: Feature-Based Similarity Assessment of Solid Models, Proc. ACM Symp. Solid Modeling and Applications, pp.297--310, 1997

Digital Library

[8]

McWherter, D., Peabody, M., Shokoufandeh, A. and Regli, W.C.: Database Techniques for Archival of Solid Models, Proc. ACM Symp. Solid Modeling and Applications, pp.78--87, 2001

Digital Library

[9]

Keim, D.A.: Efficient Geometry-Based Similarity Search of 3D Spatial Databases, Proc. ACM SIGMOD Int. Conf. On Management of Data, Philadelphia, PA, pp.419--430, 1999

Digital Library

[10]

Furukawa, S. and Kobatake, S.: Consideration on Hierarchical Tree Structures and Processing of 3-D Objects, The 23rd Annual Conference of Japan Society for Information Processing, pp.797--798, 1981. (in Japanese)

[11]

Furukawa, S., Kobatake, S. and Ishizuka, G.: Succinct Representation of 3-D Object and Its Application to Hidden-Line Problem, CAPE'83, Warmann E.A.(Ed.), Elsevier Science Pub., Amsterdam, pp.631--642, 1983

[12]

Furukawa, S.: An Algorithm for Constructing Hierarchical Tree Structures of Polyhedra (1st Report) The Case of Polyhedra without Holes, Journal of the JSPE, 51, 11, pp.2071--2076, 1985. (in Japanese)

[13]

Furukawa, S.: An Algorithm for Constructing Hierarchical Tree Structures of Polyhedra (2nd Report) The Case of Polyhedra with Holes, Journal of the JSPE, 52, 11, pp.1905--1909, 1986. (in Japanese)

[14]

Woo, T.C.: Feature Extraction by Volume Decomposition, Proc. Conf. CAD/CAM Tech. Mech. Eng., Cambridge, MA, pp.76--94, 1982

[15]

Kim, Y.S. and Wilde, D.J.: A Convergent Convex Decomposition of Polyhedral Objects, SIAM Conf. Geometric Design, Tempe, USA 1989

[16]

Kim, Y.S.: Recognition of Form Features Using Convex Decomposition, Computer-Aided Design, 24, 9, pp.461--476, 1992

[17]

Mukai, S., Furukawa, S., Obi, M. and Kimura, F.: An Algorithm for Deciding Similarities of Convex Polyhedra, Computers & Graphics, 18, 2, pp.171--176, 1994

[18]

Furukawa, S.: An Efficient Convex Hull Algorithm for Finite Points Set in 3-D Space, Technical Report of M41 Group in Yamanashi University, 1, pp.1--7, 1986

Cited By

Huang SWang HZhao YLin Z(2018)An analytical representation of conformal mapping for genus-zero implicit surfaces and its application to surface shape similarity assessmentComputer-Aided Design10.1016/j.cad.2015.02.00264:C(9-21)Online publication date: 30-Dec-2018
https://dl.acm.org/doi/10.1016/j.cad.2015.02.002
Yubin YHui LYao Z(2007)Content-Based 3-D Model RetrievalIEEE Transactions on Systems, Man, and Cybernetics, Part C: Applications and Reviews10.1109/TSMCC.2007.90575637:6(1081-1098)Online publication date: 1-Nov-2007
https://dl.acm.org/doi/10.1109/TSMCC.2007.905756
Hong TLee KKim S(2006)Similarity comparison of mechanical parts to reuse existing designsComputer-Aided Design10.1016/j.cad.2006.05.00438:9(973-984)Online publication date: Sep-2006
https://doi.org/10.1016/j.cad.2006.05.004
Show More Cited By

Index Terms

An algorithm for deciding similarities of 3-D objects
1. Applied computing

Recommendations

Deciding Polyhedrality of Spectrahedra

Spectrahedra are linear sections of the cone of positive semidefinite matrices which, as convex bodies, generalize the class of polyhedra. In this paper we investigate the problem of recognizing when a spectrahedron is polyhedral. We generalize and ...
A geometric algorithm for automated design of multi-stage molds for manufacturing multi-material objects
SMA '01: Proceedings of the sixth ACM symposium on Solid modeling and applications

This paper describes a geometric algorithm for automated design of multi-stage molds for manufacturing multi-material objects. In multi-stage molding process, the desired multi-material object is produced by carrying out multiple molding operations in a ...
Partial Similarity of Objects, or How to Compare a Centaur to a Horse

Similarity is one of the most important abstract concepts in human perception of the world. In computer vision, numerous applications deal with comparing objects observed in a scene with some a priori known patterns. Often, it happens that while two ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

SMA '02: Proceedings of the seventh ACM symposium on Solid modeling and applications

June 2002

424 pages

ISBN:1581135068

DOI:10.1145/566282

Conference Chairs:
Hans-Peter Seidel
Max-Planck-Institut für Informatik, Saarbrücken, Germany
,
Vadim Shapiro
University of Wisconsin, Madison, U.S.A.
,
Program Chairs:
Kunwoo Lee
Seoul National University, Seoul, Korea
,
Nick Patrikalakis
Massachsetts Institute of Technology, Cambridge, U.S.A.

Copyright © 2002 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

SIGGRAPH: ACM Special Interest Group on Computer Graphics and Interactive Techniques

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 17 June 2002

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Conference

SM02

Sponsor:

SIGGRAPH

SM02: ACM Symposium on Solid Modeling and Applications 2002

June 17 - 21, 2002

Saarbrücken, Germany

Acceptance Rates

SMA '02 Paper Acceptance Rate 43 of 93 submissions, 46%;

Overall Acceptance Rate 86 of 173 submissions, 50%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

11
Total Citations
View Citations
541
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 18 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Huang SWang HZhao YLin Z(2018)An analytical representation of conformal mapping for genus-zero implicit surfaces and its application to surface shape similarity assessmentComputer-Aided Design10.1016/j.cad.2015.02.00264:C(9-21)Online publication date: 30-Dec-2018
https://dl.acm.org/doi/10.1016/j.cad.2015.02.002
Yubin YHui LYao Z(2007)Content-Based 3-D Model RetrievalIEEE Transactions on Systems, Man, and Cybernetics, Part C: Applications and Reviews10.1109/TSMCC.2007.90575637:6(1081-1098)Online publication date: 1-Nov-2007
https://dl.acm.org/doi/10.1109/TSMCC.2007.905756
Hong TLee KKim S(2006)Similarity comparison of mechanical parts to reuse existing designsComputer-Aided Design10.1016/j.cad.2006.05.00438:9(973-984)Online publication date: Sep-2006
https://doi.org/10.1016/j.cad.2006.05.004
Ohbuchi RTakei T(2003)Shape-Similarity Comparison of 3D Models Using Alpha ShapesProceedings of the 11th Pacific Conference on Computer Graphics and Applications10.5555/946250.946958Online publication date: 8-Oct-2003
https://dl.acm.org/doi/10.5555/946250.946958
Ohbuchi RMinamitani TTakei T(2003)Shape-Similarity Search of 3D Models by using Enhanced Shape FunctionsProceedings of the Theory and Practice of Computer Graphics 200310.5555/832264.833421Online publication date: 3-Jun-2003
https://dl.acm.org/doi/10.5555/832264.833421
(2003)Journal of the Society of Mechanical Engineers10.1299/jsmemag.106.1014_398106:1014(398)Online publication date: 2003
https://doi.org/10.1299/jsmemag.106.1014_398
Ohbuchi RNakazawa MTakei TSebe NLew MDjeraba C(2003)Retrieving 3D shapes based on their appearanceProceedings of the 5th ACM SIGMM international workshop on Multimedia information retrieval10.1145/973264.973272(39-45)Online publication date: 7-Nov-2003
https://dl.acm.org/doi/10.1145/973264.973272
Ohbuchi RMinamitani TTakei T(2003)Shape-similarity search of 3D models by using enhanced shape functionsProceedings of Theory and Practice of Computer Graphics, 2003.10.1109/TPCG.2003.1206936(97-104)Online publication date: 2003
https://doi.org/10.1109/TPCG.2003.1206936
Ohbuchi RTakei T(2003)Shape similarity comparison of 3D models using alpha shapes11th Pacific Conference onComputer Graphics and Applications, 2003. Proceedings.10.1109/PCCGA.2003.1238271(293-302)Online publication date: 2003
https://doi.org/10.1109/PCCGA.2003.1238271
Ohbuchi ROtagiri TIbato MTakei T(2002)Shape-similarity search of three-dimensional models using parameterized statistics10th Pacific Conference on Computer Graphics and Applications, 2002. Proceedings.10.1109/PCCGA.2002.1167870(265-274)Online publication date: 2002
https://doi.org/10.1109/PCCGA.2002.1167870
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents