Using tolerances to guarantee valid polyhedral modeling results

ABSTRACT

A polyhedral solid modeler that operates on boundary representations of objects must infer topological information from numerical data. Unavoidable errors (due to limited precision) affect these calculations so that their use may produce ambiguous or contradictory results. These effects cause existing polyhedral modelers to fail when presented with objects that nearly align or barely intersect[10][7].An object description associating a tolerance with each of its topological features (vertices, edges, and faces) is introduced. The use of tolerances leads to a definition of topological consistency that is readily applied to boundary representations. The implications of using tolerances to aid in making consistent topological determinations from imprecise geometric data are explored and applied to the calculations of a polyhedral solid modeler. The resulting modeler produces a consistent polyhedral boundary when given consistent boundaries as input.

REFERENCES

• 1: Dennis S. Arnon, Topologically reliable display of algebraic curves, Proceedings of the 10th annual conference on Computer graphics and interactive techniques, p.219-227, July 25-29, 1983, Detroit, Michigan, United States
• 2: John Francis Canny. The Complexity of Robot Motion Planning. PhD thesis, MIT, 1987.
• 3: D. P. Dobkin , D. Silver, Recipes for geometry and numerical analysis - Part I: an empirical study, Proceedings of the fourth annual symposium on Computational geometry, p.93-105, June 06-08, 1988, Urbana-Champaign, Illinois, United States [doi>10.1145/73393.73404]
• 4: A. Robin Forrest. Computational geometry and software engineering: Towards a geometric computing environment. in David E Rogers and Rae A. Earnshaw, editors, Techniques for Computer Graphics, pages 23-37. Springer-Verlag, New York, 1987.
• 5: William Randolph Franklin , Peter Y F Wu , Sumitro Samaddar , Margaret Nichols, Prolog and geometry projects, IEEE Computer Graphics and Applications, v.6 n.11, p.46-55, November 1986 [doi>10.1109/MCG.1986.276671]
• 6: D. Salesin , J Stolfi , L. Guibas, Epsilon geometry: building robust algorithms from imprecise computations, Proceedings of the fifth annual symposium on Computational geometry, p.208-217, June 05-07, 1989, Saarbruchen, West Germany [doi>10.1145/73833.73857]
• 7: Christoph M. Hoffmann , John E. Hopcroft , Michael E. Karasick, Robust Set Operations on Polyhedral Solids, IEEE Computer Graphics and Applications, v.9 n.6, p.50-59, November 1989 [doi>10.1109/38.41469]
• 8: 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]
• 9: John E. Hopcroft , Peter J. Kahn, A Paradigm for Robust Geometric Algorithms, Cornell University, Ithaca, NY, 1989
• 10: David H. Laidlaw , W. Benjamin Trumbore , John F. Hughes, Constructive solid geometry for polyhedral objects, Proceedings of the 13th annual conference on Computer graphics and interactive techniques, p.161-170, August 1986
• 11: Martti Mäntylä, Boolean operations of 2-manifolds through vertex neighborhood classification, ACM Transactions on Graphics (TOG), v.5 n.1, p.1-29, Jan. 1986 [doi>10.1145/7529.7530]
• 12: Victor J. Milenkovic, Verifiable implementation of geometric algorithms using finite precision arithmetic, Artificial Intelligence, v.37 n.1-3, p.377-401, Dec. 1988 [doi>10.1016/0004-3702(88)90061-6]
• 13: V. Milenkovic, Calculating approximate curve arrangements using rounded arithmetic, Proceedings of the fifth annual symposium on Computational geometry, p.197-207, June 05-07, 1989, Saarbruchen, West Germany [doi>10.1145/73833.73856]
• 14: S.P. Mudur and P.A. Koparkar. Interval methods for processing geometric objects. IEEE CG & A 4,2 (February 1984), 7-17.
• 15: Ivan E. Sutherland , Robert F. Sproull , Robert A. Schumacker, A Characterization of Ten Hidden-Surface Algorithms, ACM Computing Surveys (CSUR), v.6 n.1, p.1-55, March 1974 [doi>10.1145/356625.356626]
• 16: T. Ottmann , G. Theimt , C. Ullrich, Numerical stability of geometric algorithms, Proceedings of the third annual symposium on Computational geometry, p.119-125, June 08-10, 1987, Waterloo, Ontario, Canada [doi>10.1145/41958.41970]
• 17: Aristides A. G. Requicha. Toward a theory of geometric tolerancing. International Journal of Robotics Research 2,4 (Winter 1983), 45-60.
• 18: Mark Segal , Carlo H. Séquin, Consistent calculations for solids modeling, Proceedings of the first annual symposium on Computational geometry, p.29-38, June 05-07, 1985, Baltimore, Maryland, United States [doi>10.1145/323233.323238]
• 19: Segal Segal , Carlo H. Sequin, Partitioning Polyhedral Objects into Nonintersecting Parts, IEEE Computer Graphics and Applications, v.8 n.1, p.53-67, January 1988 [doi>10.1109/38.490]
• 20: J. Stoer and R. Bulirsch. Introduction to Numerical Analysis. Springer-Verlag, New York, 1980.
• 21: C. K. Yap, A geometric consistency theorem for a symbolic perturbation scheme, Proceedings of the fourth annual symposium on Computational geometry, p.134-142, June 06-08, 1988, Urbana-Champaign, Illinois, United States [doi>10.1145/73393.73407]

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.5 Computational Geometry and Object Modeling
          Subjects: Curve, surface, solid, and object representations

Additional Classification:
  G. Mathematics of Computing
  G.4 MATHEMATICAL SOFTWARE
      Subjects: Reliability and robustness

  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.5 Computational Geometry and Object Modeling
          Subjects: Geometric algorithms, languages, and systems

General Terms:
Algorithms, Reliability