Abstract
This paper presents a simple method for computing the intersection curve of a ruled surface and a free-form surface. The basic idea is to reduce the problem of surface intersection to the one of projecting an appropriate curve such as a directrix of the ruled surface, along its indicatrix curve (direction vector field of its generating lines), onto the free-form surface; the projection curve is just the intersection curve. With techniques in classical differential geometry, we derive the differential equations of the intersection curve in the cases of parametrically and implicitly defined free-form surfaces. The intersection curve naturally inherits the parameter of the chosen directrix. Moreover, it is independent of the base surface geometry and its parameterization, and is obtained by numerically solving the initial-value problem for a system of first-order ordinary differential equations in the parametric domain associated to the surface representation for parametric case or in 3D space for implicit case. Some experimental examples are also given to demonstrate that the presented method is effective and potentially useful in computer aided design and computer graphics.
Similar content being viewed by others
References
Bajaj, C.L., Hoffmann, C.M., Lynch, R.E.: Tracing surface intersections. Comput. Aided Geom. Des. 5(4), 285–307 (1988)
Wang, W.-P., Joe, B., Goldman, R.: Computing quadric surface intersections based on an analysis of plane cubic curves. Graph. Models 64(6), 335–367 (2003)
Grandine, T.A., Klein, F.W.: A new approach to the surface intersection problem. Comput. Aided Geom. Des. 14(2), 111–134 (1997)
Bajaj, C.L., Xu, G.: NURBS approximation of surface–surface intersection curves. Adv. Comput. Math. 2(1), 1–21 (1994)
Sederberg, T.M., Nishita, T.: Geometric Hermite approximation of surface patch intersection curves. Comput. Aided Geom. Des. 8(2), 97–114 (1991)
Puig-Pey, J., Gálvez, A., Iglesias, A.: A new differential approach for parametric-implicit surface intersection. Lect. Notes Comput. Sci. 2657, 897–906 (2003)
Puig-Pey, J., Gálvez, A., Iglesias, A.: A differential method for parametric surface intersection. Lect. Notes Comput. Sci. 3044, 651–660 (2004)
Wu, S.-T., Andrade, L.N.: Marching along a regular surface/surface intersection with circular steps. Comput. Aided Geom. Des. 16(4), 246–268 (1999)
Elber, G., Choi, J.-J., Kim, M.-S.: Ruled tracing. Vis. Comput. 13(2), 78–94 (1997)
Song, X.W., Sederberg, T.W., Zheng, J.M.: Linear perturbation methods for topologically consistent representations of free-form surface intersections. Comput. Aided Geom. Des. 21(3), 303–319 (2004)
Martin, R.R., de Pont, J., Sharrock, T.J.: Cyclide Surfaces in computer aided design. In: Gregory, J.A. (ed.) Mathematics of Surfaces, pp. 253–267. Oxford University Press, Oxford, UK (1986)
Johnstone, J.: A new intersection algorithm for cyclides and swept surfaces using circle decomposition. Comput. Aided Geom. Des. 10(1), 1–24 (1993)
Heo, H.-S., Kim, M.-S., Elber, G.: The intersection of two ruled surfaces. Comput. Aided Des. 31(1), 33–50 (1999)
Seong, J.-K., Kim K.-J., Kim. M.-S., Elber, G., Martin, R.R.: Intersecting a freeform surface with a general swept surface. Comput. Aided Des. 37(5), 473–483 (2005)
Do Carmo M.P.: Differential Geometry of Curves and Surfaces. Prentice-Hall, Englewood Cliffs, New Jersey (1976)
Hoschek, J., Schwanecke, U.: Intersection and approximation with ruled surfaces. In: Cripps, R. (ed.) The Mathematics of Surfaces VIII, pp.213–231. Information Geometers, Winchester (1998)
Peternell, M., Pottmann, H., Ravani, B.: On the computational geometry of ruled surfaces. Comput. Aided Des. 31(1), 17–32 (1999)
Hughes, J., Möller,T.: Building an orthonormal basis from a unit vector. J. Graphics Tools 4(4), 33–35 (1999)
Seong, J.-K., Kim, K.-J., Kim M.-S., Elber, G.: Intersecting a Freeform Surface with a Ruled or a Ringed Surface. In: Proceedings of the Geometric Modeling and Processing 2004, pp. 38–48. Tsinghua University, Beijing, 13–15 April 2004
Dixon, A.L.: The eliminant of three quantics in two independent variables. Proc. London Math. Soc. 6, 49–69, 209–236 (1908)
Manocha, D., Krishnan, S.: Algebraic pruning: a fast technique for curve and surface intersection. Comput. Aided Geom. Des. 14(9), 823–845 (1997)
Martínez, J.M.: Practical quasi-Newton methods for solving non-linear systems. J. Comput. Appl. Math. 124(1–2), 97–121 (2000)
Lester, D., Chambers, S., Lu, H.L.: A constructive algorithm for finding the exact roots of polynomials with computable real coefficients. Theor. Comp. Sci. 279(1–2), 51–64(2002)
Fortune, S.: Polynomial root finding using iterated Eigenvalue computation. In: Mourrain, B. (ed.) Proceedings of the 2001 International Symposium on Symbolic and Algebraic Computation(ISSAC), pp. 121–128. ACM, New York (2001)
Krishnan, S., Manocha, D.: An efficient surface intersection algorithm based on lower dimensional formulation. ACM Trans.Graph. 16(1), 74–106 (1997)
Krishnan, S., Manocha, D.: Algebraic loop detection and evaluation algorithms for curve and surface interrogations. In: Proceedings of Graphics Interface, pp. 87–94, Toronto, Canada, 22–24 May 1996
Manocha, D., Demmel, J.: Algorithms for intersecting parametric and algebraic curves II: multiple intersections. CVGIP: GMIP 57(2), 81–100 (1995)
Manocha, D., Demmel, J.: Algorithms for intersecting parametric and algebraic curves I: simple intersections. ACM Trans. Graph. 13(1), 73–100 (1994)
Hanrahan, P.: A survey of ray-surface intersection algorithms. In: Glassner, A.S. (ed.) An Introduction to Ray Tracing, pp. 79–120. Academic, London (1989)
The MathWorks, Inc.: Using MATLAB, version 6, The MathWorks, Natick, MA (2000)
Press, W.H., Teukolsky, S.A., Vetterling, W.T., Flanneery, B.P.: Numerical Recipes (2nd edition), Cambridge University Press, Cambridge (1992)
Puig-Pey, J., Gálvez, A., Iglesias, A.: Helical curves on surface for computer aided geometric design and manufacturing. Lect. Notes Comput. Sci. 3044, 771–784 (2004)
Wolter, F.-E., Tushy, S.T.: Approximation of high-degree and procedural curves. Eng. Comput. 8(2), 61–80 (1992)
Qu, J., Sarma, R.: The continuous non-linear approximation of procedurally defined curves using integral B-Splines. Eng. Comput. 20(1), 22–30 (2004)
Renner, G., Weiβ, V.: Exact and approximate computation of B-spline curves on surfaces. Comput. Aided Des. 36(4), 351–362 (2004)
Wang, W., Goldman, R., Tu, C.: Enhacing Levin’s method for computing quadric-surface intersections. Comput. Aided Geom. Des. 20(7), 401–422 (2003)
Heo, H.-S., Hong, S.J., Seong, J.-K., Kim, M.-S., Elber, G.: The intersection of two ringed surfaces and some related problems. Graph. Models 63(4), 228–244 (2001)
Patrikalakis, N.M., Maekawa, T.: Shape Intersection problems. In: G. Farin, J. Hoschek, M.S. Kim (eds): Handbook of Computer Aided geometric Design. Chapter 25, pp. 623–650. Elsevier, Amsterdam (2002)
Patrikalakis, N.M., Maekawa, T.: Shape Interrogation for Computer Aided Geometric Design and Manufacturing. Springer, Heidelberg (2002)
Elber, G., Kim, M.-S.: Geometric constraint solver using multivariate rational spline functions. In: Proceedings of ACM symposium on solid modeling and applications 2001, pp. 1–10, Ann Arbor, Michigan, USA, 4–8 June, 2001
Puig-Pey, J., Galvez, A., Iglesias, A. Rodriguez, J., Corcuera, P., Gutierrez, F.: Some applications of scalar and vector fields to geometric processing of surfaces. Computers & Graphics 29(5), 723–729 (2005)
Abdel-Malek, K., Yeh, H.J.: On the determination of starting points for parametric surface intersections. Comput. Aided Des. 29(1), 21–35 (1997)
Author information
Authors and Affiliations
Corresponding author
Additional information
An erratum to this article can be found at http://dx.doi.org/10.1007/s11075-007-9128-9
Rights and permissions
About this article
Cite this article
Wang, X., Zhang, W. & Zhang, L. Intersection of a ruled surface with a free-form surface. Numer Algor 46, 85–100 (2007). https://doi.org/10.1007/s11075-007-9118-y
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11075-007-9118-y