Consistent calculations for solids modeling

ABSTRACT

Algorithms for computer graphics or solids modeling must often infer the structure of geometrical objects from numerical data. Unavoidable errors (due to limited precision) affect the calculations from which these data are produced and may thus affect topological information so derived. Ambiguities or even contradictions may result from inferences made from an object's representation. To resolve these ambiguities for arbitrary polyhedral objects, we introduce a minimum feature size and a face thickness and show how to convert any object description into a form which insures topological immunity to numerical perturbations. The minimum feature size depends on the object's overall dimensions and on its placement in space. The face thickness depends on how well a face's vertices conform to its computed plane.

REFERENCES

• 1: 1. A. Baer, C. Eastman, and M. Henrion, "Geometric Modelling: A Survey," CAD, vol. 11 (5), pp. 253-272, Sept. 1979.
• 2: 2. R. B. Tilove, "Set Membership Classification: A Unified Approach to Geometric Intersection Problems," IEEE Transactions on Computers, vol. C-29, pp. 874- 883, Oct. 1980.
• 3: Aristides G. Requicha, Representations for Rigid Solids: Theory, Methods, and Systems, ACM Computing Surveys (CSUR), v.12 n.4, p.437-464, Dec. 1980 [doi>10.1145/356827.356833]
• 4: 4. G. H. Golub and C. F. Van Loan, Matrix Computations, Johns Hopkins, Baltimore, MD, 1983.
• 5: 5. W. M. Newman and R. F Sproull, "Plane Equations," in Principles of Interactive Computer Graphics, 2nd Edition, p. 499, McGraw-Hill, New York, 1979.
• 6: 6. G. T. Whyburn, Analytic Topology, American Mathematical Society, Providence, RI, 1942.
• 7: Griffith Hamlin, Jr. , C. William Gear, Raster-scan hidden surface algorithm techniques, ACM SIGGRAPH Computer Graphics, v.11 n.2, p.206-213, Summer 1977
• 8: 8. C.H. Séquin and P. R. Wensley, "Visible Feature Return at Object Resolution," To be published in IEEE CG & A, May 1985.
• 9: 9. M. Segal, "Partitioning Intersecting Polyhedra into Non-Intersecting Parts," In Preparation.

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:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Geometrical problems and computations

General Terms:
Algorithms, Design, Measurement, Performance, Theory, Verification