Abstract
Two tolerance-based methods are presented: the linear model method and the curved model method, both of which make geometric algorithms robust by testing for ambiguous situations and correcting them. The linear model method only applies to linear objects. It faithfully preserves the original meaning of the problem but may detect too many ambiguous situations and fail. The curved model method can be used for both linear and curved objects and creates fewer ambiguities, but it does not necessarily preserve all the properties of linear objects because it uses a curved model to approximate linear object. Both methods are implemented and applied for 3D Boolean operations on polyhedra.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Allen, G. Testing the accuracy of solid modellers. Computer Aided Engineering (June 1985), 50–54.
Bruderlin, B. Detecting ambiguities: an optimistic approach to robustness problems in computational geometry. Tech. Rep. UUCS 90-003 (submitted), Computer Science Department, University of Utah, April 1990.
Bruderlin, B. Robust regularized set operations on polyhedra. In Proc. of Hawaii International Conference on System Science (January 1991).
Edelsbrunner, H., and Mucke, E. Simulation of simlicity: a technique to cope with degenerate cases in geometric algorithms. In Proc. of 4th ACM Symposium on Comp. Geometry (June 1988), pp. 118–133.
Greene, D., and Yao, F. Finite resolution computational geometry. In Proc. 27th IEEE Symp. Fundations of Computer Science (1986), pp. 143–152.
Guibas, L., Salesin, D., and Stolfi, J. Epsilon geometry: building robust algorithms from imprecise computations. In Proc. of 5th ACM Symposium on Computational Geometry (1989), p.
Hoffmann, C. M. The problems of accuracy and robustness in geometric computation. IEEE Computer 22, 3 (March 1989), 31–41.
Hoffmann, C. M., Hopcroft, J. E., and Karasick, M. S. Robust set operations on polyhedral solids. IEEE Computer Graphics and Application 9 (November 1989).
Milenkovic, V. Verifiable implementations of geometric algorithm using finite precision arithmetic. Artificial Intelligence 37 (1988), 377–401.
Requicha, A. A. G. Solid modeling — a 1988 update. In CAD Based Programming for Sensory Robots (1988), B. R., Ed., Springer Verlag, New York, pp. 3–22.
Segal, M. Using tolerances to guarantee valid polyhedral modeling results. Computer Graphics 24, 4 (1990), 105–114.
Sugihara, K., and Iri, M. Geometric algorithms in finite precision arithmetic. Res. Mem. 88-14, Math. Eng. and Information Physicas, University of Tokyo, 1988.
Yap, C. K. A geometric consistency theorem for a symbolic perturbation theorem. In Proc. of 4th ACM Symposium on Comp. Geometry (June 1988), pp. 134–142.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1991 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Fang, S., Brüderlin, B. (1991). Robustness in geometric modeling — Tolerance-based methods. In: Bieri, H., Noltemeier, H. (eds) Computational Geometry-Methods, Algorithms and Applications. CG 1991. Lecture Notes in Computer Science, vol 553. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-54891-2_7
Download citation
DOI: https://doi.org/10.1007/3-540-54891-2_7
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-54891-1
Online ISBN: 978-3-540-46459-4
eBook Packages: Springer Book Archive