[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ skip to main content
10.1145/781606.781629acmconferencesArticle/Chapter ViewAbstractPublication PagesspmConference Proceedingsconference-collections
Article

Three-dimensional halfspace constructive solid geometry tree construction from implicit boundary representations

Published: 16 June 2003 Publication History

Abstract

This paper presents a new method to compute constructive solid geometry (CSG) tree representations of an object whose faces consist of planar and non-planar surfaces. The algorithm described accepts as input a valid boundary representation of an object consisting of piecewise implicit surfaces, and computes a halfspace CSG representation of the object. A class of objects that are describable by the surfaces bounding them are valid input for the algorithm of this work, although methods currently exist to compute the additional information necessary to process non-describable quadric objects as well. This work builds on and complements the other work in this area, in which dominating halfspaces are used to simplify the b-rep to CSG conversion process. We include factored faces to enable the factorization of dominating halfspaces throughout the algorithm. Thus, an efficient disjoint decomposition of the solid is obtained as a matter of course in the algorithm, so that CSG minimization is generally not necessary.This work is motivated by reverse engineering of mechanical parts, in which a model of a part is recovered from information obtained by some sort of sensing technique (e.g. CAT scanning, laser range finding). The recovery of a valid CSG-tree description of an object from a boundary representation of it can provide useful information to an engineer in the area of reverse engineering and in other areas related to solid modeling as well. The CSG tree also provides a relatively neutral representation that can enhance form feature recognition and translation.

References

[1]
F. Bernardini, C. L. Bajaj, J. Chen, and S. D. R. Automatic Reconstruction of 3D CAD Models from Digital Scans. International Journal of Computational Geometry & Applications, 9(4 & 5):327--369, 1999.
[2]
G. Birkhoff and T. C. Bartree. Modern Applied Algebra. McGraw-Hill, 1970.
[3]
J. Bloomenthal, editor. Introduction to Implicit Surfaces. Morgan Kaufman, 1997.
[4]
J. Bloomenthal and B. Byvill, editors. Implicit Surfaces. Morgan Kaufman, 1996.
[5]
P. Brunet and A. Vinacua. Modeling Closed Surfaces: A Comparison of Existing Methods. In Mathematical Methods in Computer Aided Geometric Design II. Academic Press, 1992.
[6]
S. F. Buchele. Three-Dimensional Binary Space Partitioning Tree and Constructive Solid Geometry Tree Construction from Algebraic Boundary Representations. PhD thesis, The University of Texas at Austin, 1999.
[7]
I. D. Faux and M. J. Pratt. Computational Geometry for Design and Manufacture. John Wiley & Sons, 1979.
[8]
J. Han and A. A. G. Requicha. Integration of Feature Based Design and Feature Recognition. Computer Aided Design, 29(5):393--403, 1997.
[9]
W. Lin and T. Chen. CSG-Based Object Recognition using Range Images. In Proceedings of the 9th International Conference on Pattern Recognition, pages 99--103, November 1988.
[10]
S. Menon and Y. S. Kim. Handling Blending Features in Form Feature Recognition using Convex Decomposition. In Proceedings 14th Annual ASME International Computers in Engineering Conference and Exhibition, volume 1, pages 79--92, 1994.
[11]
D. P. Peterson. Boundary to Constructive Solid Geometry Mappings: A Focus on 2D Issues. Computer Aided Design, 18(1):3--14, 1986.
[12]
A. A. G. Requicha and J. R. Rossignac. Solid Modeling and Beyond. IEEE Computer Graphics and Applications, pages 31--44, September 1992.
[13]
H. Sakurai and D. C. Gossard. Recognizing Shape Features in Solid Models. IEEE Computer Graphics and Applications, pages 22--32, September 1990.
[14]
V. Shapiro and D. L. Vossler. Construction and Optimization of CSG Representations. Computer Aided Design, 23(1):4--20, 1991.
[15]
V. Shapiro and D. L. Vossler. Efficient CSG Representations of Two-Dimensional Solids. Transactions of the ASME, 113:292--305, September 1991.
[16]
V. Shapiro and D. L. Vossler. Separation for Boundary to CSG Conversion. ACM Transactions on Graphics, 12(1):25--55, January 1993.
[17]
D. M. Y. Sommerville. Analytical Geometry of Three Dimensions. Cambridge University Press, 1939.
[18]
K. Tang and T. Woo. Algorithmic Aspects of Alternating Sum of Volumes: Part 1: Data Structure and Difference Operation. Computer Aided Design, 23(5):357--366, June 1991.
[19]
K. Tang and T. Woo. Algorithmic Aspects of Alternating Sum of Volumes: Part 2: Nonconvergence and its Remedy. Computer Aided Design, 23(6):435--443, July 1991.
[20]
D. L. Vossler. Sweep-to-CSG Conversion using Pattern Recognition Techniques. IEEE Computer Graphics and Applications, 5(8):61--68, August 1985.
[21]
D. L. Vossler and V. Shapiro. System and Method for Converting Boundary Representations to Constructive Solid Geometry Representations for Three-Dimensional Solid Object Modeling. Technical report, United States Patent No. 5,537,519, July 1996.
[22]
T. C. Woo. Feature Extraction by Volume Decomposition. In Proceedings on CAD/CAM Technology in Mechanical Engineering, pages 76--94, 1982.

Cited By

View all
  • (2024)Brep2Seq: a dataset and hierarchical deep learning network for reconstruction and generation of computer-aided design modelsJournal of Computational Design and Engineering10.1093/jcde/qwae00511:1(110-134)Online publication date: 19-Jan-2024
  • (2022)Implicit Conversion of Manifold B-Rep Solids by Neural Halfspace RepresentationACM Transactions on Graphics10.1145/3550454.355550241:6(1-15)Online publication date: 30-Nov-2022
  • (2021)Constrained projective dynamicsACM Transactions on Graphics10.1145/3450626.345987840:4(1-12)Online publication date: 19-Jul-2021
  • Show More Cited By

Recommendations

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences
SM '03: Proceedings of the eighth ACM symposium on Solid modeling and applications
June 2003
362 pages
ISBN:1581137060
DOI:10.1145/781606
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

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 16 June 2003

Permissions

Request permissions for this article.

Check for updates

Author Tags

  1. geometric and topological representations
  2. product and assembly modeling
  3. representation conversion
  4. reverse engineering

Qualifiers

  • Article

Conference

SM03
Sponsor:
SM03: 8th ACM Symposium on Solid Modeling and Applications
June 16 - 20, 2003
Washington, Seattle, USA

Acceptance Rates

SM '03 Paper Acceptance Rate 43 of 80 submissions, 54%;
Overall Acceptance Rate 86 of 173 submissions, 50%

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)17
  • Downloads (Last 6 weeks)2
Reflects downloads up to 21 Dec 2024

Other Metrics

Citations

Cited By

View all
  • (2024)Brep2Seq: a dataset and hierarchical deep learning network for reconstruction and generation of computer-aided design modelsJournal of Computational Design and Engineering10.1093/jcde/qwae00511:1(110-134)Online publication date: 19-Jan-2024
  • (2022)Implicit Conversion of Manifold B-Rep Solids by Neural Halfspace RepresentationACM Transactions on Graphics10.1145/3550454.355550241:6(1-15)Online publication date: 30-Nov-2022
  • (2021)Constrained projective dynamicsACM Transactions on Graphics10.1145/3450626.345987840:4(1-12)Online publication date: 19-Jul-2021
  • (2021)Total relightingACM Transactions on Graphics10.1145/3450626.345987240:4(1-21)Online publication date: 19-Jul-2021
  • (2021)Consistent depth of moving objects in videoACM Transactions on Graphics10.1145/3450626.345987140:4(1-12)Online publication date: 19-Jul-2021
  • (2021)Boundary-sampled halfspacesACM Transactions on Graphics10.1145/3450626.345987040:4(1-15)Online publication date: 19-Jul-2021
  • (2021)Fusion 360 galleryACM Transactions on Graphics10.1145/3450626.345981840:4(1-24)Online publication date: 19-Jul-2021
  • (2021)Guaranteed globally injective 3D deformation processingACM Transactions on Graphics10.1145/3450626.345975740:4(1-13)Online publication date: 19-Jul-2021
  • (2021)Fast diffraction pathfinding for dynamic sound propagationACM Transactions on Graphics10.1145/3450626.345975140:4(1-13)Online publication date: 19-Jul-2021
  • (2021)Pareto gamutsACM Transactions on Graphics10.1145/3450626.345975040:4(1-17)Online publication date: 19-Jul-2021
  • Show More Cited By

View Options

Login options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Media

Figures

Other

Tables

Share

Share

Share this Publication link

Share on social media