Take a look at the new version of this page: [ beta version ]. Tell us what you think.

ABSTRACT

We present a system, ESOLID, that performs exact boundary evaluation of low degree curved solids in reasonable amounts of time. ESOLID performs accurate Boolean operations using exact representations and exact computations throughout. The demands of exact computation require a different set of algorithms and efficiency improvements than those found in a traditional inexact floating point based modeler. We describe the system architecture, representations, and issues in implementing the algorithms. We also describe a number of techniques that increase the efficiency of the system based on lazy evaluation, use of floating point filters, arbitrary floating point arithmetic with error bounds, and lower dimensional formulation of subproblems. ESOLID has been used for boundary evaluation of many complex solids. These include both synthetic datasets and parts of a Bradley Fighting Vehicle designed using the BRL-CAD solid modeling system. It is shown that ESOLID can correctly evaluate the boundary of solids that are very hard to compute using a fixed-precision floating point modeler. In terms of performance, it is about an order of magnitude slower as compared to a floating point boundary evaluation system on most cases.

REFERENCES

• 1: Oliver Aberth , Mark J. Schaefer, Precise computation using range arithmetic, via C++, ACM Transactions on Mathematical Software (TOMS), v.18 n.4, p.481-491, Dec. 1992 [doi>10.1145/138351.138377]
• 2: M. O. Benouamer, D. Michelucci, and B. Peroche. Error-free boundary evaluation based on a lazy rational arithmetic: A detailed implementation. Computer Aided Design, 26(6):403--416, June 1994
• 3: I. Biehl, J. Buchmann, and T. Papanikolaou. LiDIA: A library for computational number theory. Technical Report SFB 124-C1, Fachbereich Informatik, Universitat des Saarlandes, 1995
• 4: I. C. Braid, The synthesis of solids bounded by many faces, Communications of the ACM, v.18 n.4, p.209-216, April 1975 [doi>10.1145/360715.360727]
• 5: Hervé Brönnimann , Ioannis Z. Emiris , Victor Y. Pan , Sylvain Pion, Computing exact geometric predicates using modular arithmetic with single precision, Proceedings of the thirteenth annual symposium on Computational geometry, p.174-182, June 04-06, 1997, Nice, France [doi>10.1145/262839.262948]
• 6: Smita Brunnermeier and Sheila Martin. Interoperability cost analysis of the U.S. automotive supply chain. Technical Report RTI Project Number 7007-03, Research Triangle Institute, 1999. http://www.rti.org/publications
• 7: M. S. Casale , J. E. Bobrow, A set operation algorithm for sculptured solids modeled with trimmed patches, Computer Aided Geometric Design, v.6 n.3, p.235-247, Aug. 1989 [doi>10.1016/0167-8396(89)90026-5]
• 8: Kenneth L. Clarkson. Safe and effective determinant evaluation. Manuscript, February 1995
• 9: Joao Luiz Dibl Comba and Jorge Stolfi. Affine arithmetic and its applications to computer graphics. Anais do VII Sibgraphi, 1993
• 10: Tim Culver , John Keyser , Dinesh Manocha, Accurate computation of the medial axis of a polyhedron, Proceedings of the fifth ACM symposium on Solid modeling and applications, p.179-190, June 08-11, 1999, Ann Arbor, Michigan, United States [doi>10.1145/304012.304030]
• 11: J. H. Davenport, Y. Siret, and E. Tournier. Computer Algebra. Academic Press, London, 1993. 2nd edition
• 12: Helene Desaulniers and Neil F. Stewart. Semantic interpretation of inconsistent curve and surface data for the definition of solids. In Joe Warren, editor, Curves and Surfaces in Computer Vision and Graphics III, volume 1830 of SPIE Proceedings, pages 81--90. SPIE, Bellingham, WA, 1992
• 13: Paul H. Dietz, Jr. William H. Mermagen, and Paul R. Stay. An integrated environment for army, navy and air force target description support. Technical Report Memorandum Report BRL-MR-3754, Ballistics Research Laboratory, Aberdeen Proving Ground, MD, 1989
• 14: Phillip C. Dykstra and Michael John Muuss. The BRL-CAD package an overview. Technical report, Advanced Computer Systesms Team, Ballistics Research Laboratory, Aberdeen Proving Ground, MD, 1989
• 15: Gershon Elber. IRIT solid modeling system. http://www.cs.technion.ac.il/simgershon/irit/
• 16: Shiaofen Fang, Beat Bruderlin, and Xiaohong Zhu. Robustness in solid modeling: A tolerance-based intuitionistic approach. Computer Aided Design, 25(9):567--576, September 1993
• 17: Steven Fortune. Polyhedral modelling with multiprecision integer arithmetic. Computer-Aided Design, 29(2):123--133, 1997
• 18: Steven Fortune , Christopher J. Van Wyk, Efficient exact arithmetic for computational geometry, Proceedings of the ninth annual symposium on Computational geometry, p.163-172, May 18-21, 1993, San Diego, California, United States [doi>10.1145/160985.161015]
• 19: Steven Fortune , Christopher J. Van Wyk, Static analysis yields efficient exact integer arithmetic for computational geometry, ACM Transactions on Graphics (TOG), v.15 n.3, p.223-248, July 1996 [doi>10.1145/231731.231735]
• 20: Nicola Geismann , Michael Hemmer , Elmar Schömer, Computing a 3-dimensional cell in an arrangement of quadrics: exactly and actually!, Proceedings of the seventeenth annual symposium on Computational geometry, p.264-273, June 2001, Medford, Massachusetts, United States [doi>10.1145/378583.378689]
• 21: Christoph M. Hoffmann, The Problems of Accuracy and Robustness in Geometric Computation, Computer, v.22 n.3, p.31-40, March 1989 [doi>10.1109/2.16223]
• 22: C. M. Hoffmann , J. E. Hopcroft , M. S. Karasick, Towards implementing robust geometric computations, Proceedings of the fourth annual symposium on Computational geometry, p.106-117, June 06-08, 1988, Urbana-Champaign, Illinois, United States [doi>10.1145/73393.73405]
• 23: Christoph M. Hoffmann, Geometric and solid modeling: an introduction, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1989
• 24: C.-Y. Hu, N. M. Patrikalakis, and X. Ye. Robust interval solid modeling, Part I: representations. CAD, 28:807--818, 1996
• 25: C.-Y. Hu, N. M. Patrikalakis, and X. Ye. Robust interval solid modeling, Part II: boundary evaluation. CAD, 28:819--830, 1996
• 26: David J. Jackson, Boundary representation modelling with local tolerances, Proceedings of the third ACM symposium on Solid modeling and applications, p.247-254, May 17-19, 1995, Salt Lake City, Utah, United States [doi>10.1145/218013.218067]
• 27: J. R. Johnson, Real algebraic number computation using interval arithmetic, Papers from the international symposium on Symbolic and algebraic computation, p.195-205, July 27-29, 1992, Berkeley, California, United States [doi>10.1145/143242.143311]
• 28: V. Karamcheti , C. Li , I. Pechtchanski , C. Yap, A core library for robust numeric and geometric computation, Proceedings of the fifteenth annual symposium on Computational geometry, p.351-359, June 13-16, 1999, Miami Beach, Florida, United States [doi>10.1145/304893.304989]
• 29: Michael Karasick , Derek Lieber , Lee R. Nackman, Efficient Delaunay triangulation using rational arithmetic, ACM Transactions on Graphics (TOG), v.10 n.1, p.71-91, Jan. 1991 [doi>10.1145/99902.99905]
• 30: John Keyser , Shankar Krishnan , Dinesh Manocha, Efficient and accurate B-rep generation of low degree sculptured solids using exact arithmetic, Proceedings of the fourth ACM symposium on Solid modeling and applications, p.42-55, May 14-16, 1997, Atlanta, Georgia, United States [doi>10.1145/267734.267753]
• 31: John Keyser , Shankar Krishnan , Dinesh Manocha, Efficient and accurate B-rep generation of low degree sculptured solids using exact arithmetic: I—representations, Computer Aided Geometric Design, v.16 n.9, p.841-859, Oct. 1999 [doi>10.1016/S0167-8396(99)00032-1]
• 32: John Keyser , Shankar Krishnan , Dinesh Manocha, Efficient and accurate B-rep generation of low degree sculptured solids using arithmetic: II—computation, Computer Aided Geometric Design, v.16 n.9, p.861-882, Oct. 1999 [doi>10.1016/S0167-8396(99)00033-3]
• 33: John Keyser, Tim Culver, Dinesh Manocha, and Shankar Krishnan. Efficient and exact manipulation of algebraic points and curves. Computer Aided Design, 32(12):649--662, 2000. Special Issue on Robustness
• 34: John Christopher Keyser , Dinesh Manocha, Exact boundary evaluation for curved solids, 2000
• 35: S. Krishnan, D. Manocha, M. Gopi, T. Culver, and J. Keyser. BOOLE: A boundary evaluation system for boolean combinations of sculptured solids. International Journal of Computational Geometry and Applications, 2000. To appear
• 36: Shankar Krishnan , Dinesh Manocha, Efficient and accurate boundary evaluation algorithms for boolean combinations of sculptured solids, 1997
• 37: Shankar Krishnan , Mark Foskey , Tim Culver , John Keyser , Dinesh Manocha, PRECISE: efficient multiprecision evaluation of algebraic roots and predicates for reliable geometric computation, Proceedings of the seventeenth annual symposium on Computational geometry, p.274-283, June 2001, Medford, Massachusetts, United States [doi>10.1145/378583.378693]
• 38: M. Mantyla, Introduction to Solid Modeling, W. H. Freeman & Co., New York, NY, 1988
• 39: Kurt Mehlhorn , Stefan Näher, LEDA: a platform for combinatorial and geometric computing, Cambridge University Press, New York, NY, 1999
• 40: Aristides A. G. Requicha and Herbert B. Voelcker. Solid modeling: A historical summary and contemporary assessment. IEEE Computer Graphics and Applications, 2(2):9--24, March 1982
• 41: Aristides A. G. Requicha and Herbert B. Voelcker. Boolean operations in solid modeling: Boundary evaluation and merging algorithms. Proceedings of the IEEE, 73(1):30--44, January 1985
• 42: Mark Segal, Using tolerances to guarantee valid polyhedral modeling results, ACM SIGGRAPH Computer Graphics, v.24 n.4, p.105-114, Aug. 1990
• 43: Johnathan Richard Shewchuk, Robust adaptive floating-point geometric predicates, Proceedings of the twelfth annual symposium on Computational geometry, p.141-150, May 24-26, 1996, Philadelphia, Pennsylvania, United States [doi>10.1145/237218.237337]
• 44: Kokichi Sugihara. A robust and consistent algorithm for intersecting convex polyhedra. In M. Daehlen and L. Kjelldahl, editors, Proceedings of EUROGRAPHICS '94, volume 13, pages C--45--C--54. Blackwell Association, 1994
• 45: K. Sugihara , M. Iri, A solid modelling system free from topological inconsistency, Journal of Information Processing, v.12 n.4, p.380-393, 1989
• 46: Irina Voiculescu. Personal Communication, 1999
• 47: Chee Yap and Thomas Dube. The exact computation paradigm. In D. Z. Du and F. Hwang, editors, Computing in Euclidean Geometry, pages 452--492. World Scientific Press, Singapore, 1995
• 48: Norimasa Yoshida, Masato Shyokawa, and Fujio Yamaguchi. Solid modeling based on a new paradigm. Comput. Graph. Forum, 13(3):55--64, 1994. Proc. EUROGRAPHICS '94
• 49: Jiaxun Yu, Exact arithmetic solid modeling, Purdue University, West Lafayette, IN, 1992

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.5 Computational Geometry and Object Modeling

Additional Classification:
  G. Mathematics of Computing
  G.4 MATHEMATICAL SOFTWARE

  I. Computing Methodologies
  I.1 SYMBOLIC AND ALGEBRAIC MANIPULATION
      I.1.4 Applications

  J. Computer Applications
  J.6 COMPUTER-AIDED ENGINEERING

General Terms:
Design, Experimentation, Performance, Reliability

Keywords:
boundary evaluation, exact computation, robustness, system implementation