“Using tolerances to guarantee valid polyhedral modeling results” by Segal
Conference:
Type(s):
Title:
- Using tolerances to guarantee valid polyhedral modeling results
Session/Category Title: Object Space Methods
Presenter(s)/Author(s):
Moderator(s):
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. Amon. Topologically reliable display of algebraic curves. Proceedings of SIGGRAPH’83 (Detroit, Michigan, July 25-29, 1983). In Computer Graphics 17,3 (July 1983), 219-227.
2. John Francis Canny. The Complexity of Robot Motion Planning. PhD thesis, MIT, 1987.
3. David Dobkin and Deborah Silver. Recipes for geometry & numerical analysismpart I: An empirical study. In Proceedings of the Fourth ACM Symposium on Computational Geometry, pages 93-105, Urbana, Illinois, 1988.
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. W. Randolph Franklin, Peter Y.E Wu, and Sumitro Samaddar. Prolog and geometry projects. IEEE CG & A 6,11 (November 1986), 46-55.
6. Leonidas Guibas, David Salesin, and Jorge Stolfi. Epsilon geometry: Building robust algorithms from imprecise computations. In Proceedings of the Fifth A CM Symposium on Computational Geometry, pages 208-217, 1989.
7. Cristoph M. Hoffmann, John E. Hopcroft, and Michael E. Karasick. Robust set operations on polyhedral solids. IEEE CG & A 9,6 (November 1989), 50-59.
8. Cristoph M. Hoffmann, John E. Hopcroft, and Michael S. Karasick. Towards implementing robust geometric computations. In Proceedings of the Fourth ACM Symposium on Computational Geometry, pages 106-117, Urbana, Illinois, 1988. “1”1,4
9. John E. Hopcroft and Peter J. Kahn. A paradigm for robust geometric algorithms. Technical Report TR 89-1044, Department of Computer Science, Comell University, October 1989.
10. David H. Laidlaw, W. Benjamin Trumbore, and John E Hughes. Constructive solid geometry for polyhedral objects. Proceedings of SIGGRAPH’86 (Dallas, Texas, August 18-22, 1986). In Computer Graphics 20,4 (August 1986), 161-170.
11. Martti M~intyl~i. Boolean operations of 2-manifolds through vertex neighborhood classification. ACM Transactions on Graphics 5,1 (January 1986), 1-29.
12. Victor Milenkovic. Verifiable implementations of geometric algorithms using finite precision arithmetic. Artificial Intelligence 37 (1988), 377–401.
13. Victor Milenkovic. Calculating approximate curve arrangements using rounded arithmetic. In Proceedings of the Fifth ACM Symposium on Computational Geometry, pages 197- 207, ! 989.
14. S.P. Mudur and P.A. Koparkar. Interval methods for processing geometric objects. IEEE CG & A 4,2 (February 1984), 7-17.
15. I.E. Sutherland, R.F. Sproull, and R.A. Schumacker. A Characterization of Ten Hidden-Surface Removal Algorithms. Computing Surveys 6,1 (March 1974), 1-55.
16. Thomas Ottmann, Gerald Thiemt, and Christian Ullrich. Numerical stability of geometric algorithms. In Proceedings of the Third ACM Symposium on Computational Geometry, pages 119-125, Waterloo, Ontario, 1987.
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 and Carlo H. Srquin. Consistent calculations for solid modeling. In Proceedings of the First ACM Symposium on Computational Geometry, pages 29-38, 1985.
19. Mark Segal and Carlo H. Srquin. Partitioning polyhedral objects into non-intersecting parts. IEEE CG & A 8,1 (January 1988), 53-67.
20. J. Stoer and R. Bulirsch. Introduction to Numerical Analysis. Springer-Verlag, New York, 1980.
21. Chee-Keng Yap. A geometric consistency theorem for a symbolic perturbation scheme. In Proceedings of the Fourth ACM Symposium on Computational Geometry, pages 134- 142, Urbana, Illinois, 1988.
