Contour tracing by piecewise linear approximations

ABSTRACT

We present a method for tracing a curve that is represented as the contour of a function in Euclidean space of any dimension. The method proceeds locally by following the intersections of the contour with the facets of a triangulation of space. The algorithm does not fail in the presence of high curvature of the contour; it accumulates essentially no round-off error and has a well-defined integer test for detecting a loop. In developing the algorithm, we explore the nature of a particular class of triangulations of Euclidean space, namely, those generated by reflections.

REFERENCES

• 1: At.t.aowp.R, E. L., ANn (',~.nRa, K. Simplieiml And emntinllnf.imn mpthnd.~ fnr ApprnYirngf.ina fixed points and solutions to systems of equations. SIAM Rev. 22 (dan. 1980), 28-85.
• 2: ALLGOWER, E. L., AND SCHMIDT, P.H. An algorithm for piecewise linear approximation of an implicitly defined manifold. SIAM d. Numer. Anal. 22 (April 1985), 322-346.
• 3: 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
• 4: BLANCHARD, P. Complex analytic dynamics on the Riemann sphere. Bull. Am. Math. Soc. I1 (duly 1984), 85-141.
• 5: CONWAY, J. n., AND SLOaNE, N. d.A. Fast quantizing and decoding algorithms for lattice quantizers and codes. IEEE Trans. In{. Theory 28 (Mar. 1982), 227-232.
• 6: COXETER, H. S. M. Discrete groups generated by reflections. Ann. Math. 35 (duly i934), 588-621.
• 7: COXETER, H. S.M. Regular Polytopes. 3rd ed. Dover, New York, 1973.
• 8: DONGARRA, J. J., BUNCH, J. R., MOLER, C. B., AND STEWART, G. W. LZNPACK Users'Guide. SIAM, Philadelphia, Pa., 1979.
• 9: DUNEAU, M., AND KATZ, A. Quasiperiodic patterns and icosahedral symmetry. J. Physique 47 (Feb. 1986), 181-196.
• 10: James D. Foley , Andries Van Dam, Fundamentals of interactive computer graphics, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1982
• 11: GEISOW, A. Surface interrogations. Ph.D. thesis, Dept. of Computer Science, Univ. of East Anglia, Norwich, U.K., 1983
• 12: GUILLEMIN, V., AND POLLACK, A. Differential Topology. Prentice-Hail, Englewood Cliffs, N.J., 1974.
• 13: HOFFMAN, K. Analysis in Euclidean Space. Prentice-Hall, Englewood Cliffs, N.J., 1975.
• 14: KARAMARDIAN, S., ED. Fixed Points: Algorithms and Applications. Academic Press, New York, 1977.
• 15: James M. Ortega , Werner C. Rheinboldt, Iterative solution of nonlinear equations in several variables, Society for Industrial and Applied Mathematics, Philadelphia, PA, 2000
• 16: OSTROWSKI, A.M. Solutions of Equations and Systems of Equations. 2nd ed. Academic Press, New York, 1966
• 17: REQUICHA, A., AND VOELCKER, S. Solid modeling: Current status and research directions. IEEE Comput. Graph. Appl. 3 (Oct. 1983), 25-37.
• 18: SABIN, M. A. Contouring~The state of the art. In Fundamental Algorithms for Computer Graphics, R. A. Earnshaw, Ed. Springer-Verlag, New York, 1985.
• 19: SCARF, H. The approximation of fixed points of a continuous mapping. SIAM J. Appl. Math. 15 (Sept. 1967), 1328-1343.
• 20: SPERNER, E. Neuer Beweis fur die Invarianz der Dimensionszahl und des Gebietes. Abh. a. d. Math. Sem. D. Univ. Hamburg 6 (1928), 265-272.
• 21: TODD, M.J. The Computation of Fixed Points with Applications. Lecture Notes in Economics and Mathematical Systems, 124. Springer-Verlag, New York, 1976.
• 22: TUKEY, P. A., AND TUKEY, J.W. Data-driven view selection; agglomeration and sharpening. In Interpreting Multivariate Data, V. Barnett, Ed. Wiley, New York, 1981, 215-243.

INDEX TERMS

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

General Terms:
Algorithms, Theory