A marching method for parametric surface/surface intersection. (English) Zbl 0716.65013

Barnhill, R. E.; Kersey, S. N.

Comput. Aided Geom. Des. 7, No. 1-4, 257-280 (1990).

From the authors’ abstract: A general marching method for surface/surface intersection is described for smooth parametric surfaces defined over rectangular and triangular domains. Surface equations are not required explicitly - only evaluated surface positions and tangents. The algorithm is based on an extension of a marching method presented by the first author, G. Farin, M. Jordan and B. R. Piper [ibid. 4, 3-16 (1987; Zbl 0642.65010)]. The new algorithm permits the intersection of triangular surfaces, and the intersection of surfaces that generate tangent and branch points, and tangent tracks. A method for approximating step length, and methods for relaxing intersection points onto surface boundaries are included. These ideas are discussed and illustrative colour examples are also included.

Reviewer: C.Simerská

MSC:

65D17

Computer-aided design (modeling of curves and surfaces)

Keywords:

subdivision; bounding boxes; octrees; geometric modelling; marching method; surface/surface intersection; parametric surfaces; intersection of triangular surfaces

Citations:

Zbl 0642.65010

References:

[1]	Barnhill, R.E., Geometry processing: curvature analysis and surface/surface intersection, (), 51-60
[2]	Barnhill, R.E.; Farin, G.; Jordan, M.; Piper, B.R., Surface⧸surface intersection, Computer aided geometric design, 4, 3-16, (1987) · Zbl 0642.65010
[3]	Barnhill, R.E., Geometry processing, September 14-16, St. Louis, MO, AIAA/AHS/ASEE aircraft design, systems and operations meeting, (1987)
[4]	DeMontaudouin, Y.; Tiller, W.; Vold, H., Applications of power series in computational geometry, Computer aided design, 18, (1986)
[5]	Faux, I.D.; Pratt, M.J., Computational geometry for design and manufacture, (1979), Ellis Horwood Chichester, UK · Zbl 0395.51001
[6]	Gregory, J.A. (1989), Private communications, Arizona State University, March-April.
[7]	Houghton, E.G.; Emnett, R.F.; Factor, J.D.; Sabharwal, C.L., Implementation of a divide-and-conquer method for intersection of parametric surfaces, Computer aided geometric design, 2, 173-183, (1985) · Zbl 0613.65143
[8]	Marchant, P., A numerical method for intersections of parametric surfaces, ()
[9]	Mortenson, M.E., Geometric modeling, (1985), Wiley New York
[10]	Mullenheim, G., Convergence of a surface/surface intersection algorithm, Computer aided geometric design, (1990), to appear. · Zbl 0704.65009
[11]	Prakash, P.V.; Patrikalakis, N.M., Algebraic and rational polynomial surface intersections, MIT report, (1988)
[12]	Pratt, M.J.; Geisow, A.D., Surface/surface intersection problems, ()
[13]	Sabharwal, C.L.; Factor, J.D., Cross intersections between any two C0 parametric surfaces, Ausgraph, (1988)
[14]	Samet, H., Neighbor finding techniques for images represented by quadtrees, Computer graphics and image processing, 18, 37-57, (1982) · Zbl 0531.68041
[15]	Samet, H., The quadtree and related hierarchical data structures, Computing surveys, 16, 187-260, (1984)
[16]	Von Herzon, B.; Barr, A.H., Accurate triangulations of deformed, intersecting surfaces, ACM computer graphics, 21, (1987), SIGGRAPH Proceedings.