3D Euler spirals for 3D curve completion. (English) Zbl 1244.65022

Summary: Shape completion is an intriguing problem in geometry processing with applications in computer-aided design and graphics. This paper defines a new type of 3D curve, which can be utilized for curve completion. It can be considered as the extension to three dimensions of the 2D Euler spiral. We prove several properties of this curve – properties that have been shown to be important for the appeal of curves. We illustrate its utility in two applications. The first is “fixing” curves detected by algorithms for edge detection on surfaces. The second is shape illustration in archaeology, where the user would like to draw curves that are missing due to the incompleteness of the input model.


65D17 Computer-aided design (modeling of curves and surfaces)
Full Text: DOI


[1] Harary, G.; Tal, A., The natural 3D spiral, Computer graphics forum, 30, 2, 237-246, (2011)
[2] Kolomenkin, M.; Shimshoni, I.; Tal, A., Demarcating curves for shape illustration, ACM transactions on graphics, 27, 5, 157, (2008), 1-9
[3] Zatzarinni, R.; Tal, A.; Shamir, A., Relief analysis and extraction, ACM transactions on graphics, 28, 5, 136, (2009), 1-9
[4] DeCarlo, D.; Finkelstein, A.; Rusinkiewicz, S.; Santella, A., Suggestive contours for conveying shape, ACM transactions on graphics, 22, 3, 848-855, (2003)
[5] Judd, T.; Durand, F.; Adelson, E., Apparent ridges for line drawing, ACM transactions on graphics, 26, 3, 19, (2007), 1-7
[6] Yoshizawa, S.; Belyaev, A.; Seidel, H.P., Fast and robust detection of crest lines on meshes, (), 227-232
[7] Barequet, G.; Kumar, S., Repairing CAD models, (), 363-370
[8] Barequet, G.; Sharir, M., Filling gaps in the boundary of a polyhedron, Computer aided geometric design, 12, 2, 207-229, (1995) · Zbl 0875.68921
[9] Sharf, A.; Alexa, M.; Cohen-Or, D., Context-based surface completion, ACM transactions on graphics, 23, 3, 878-887, (2004)
[10] De Boor, C., A practical guide to splines, (2001), Springer · Zbl 0987.65015
[11] Farin, G., Curves and surfaces for computer aided geometric design, (1993), Academic Press
[12] Farouki, R.; Neff, C., Hermite interpolation by Pythagorean hodograph quintics, Mathematics of computation, 64, 212, 1589-1609, (1995) · Zbl 0847.68125
[13] Farouki, R., Pythagorean-hodograph curves: algebra and geometry inseparable, (2008), Springer · Zbl 1144.51004
[14] Singh, M.; Fulvio, J., Visual extrapolation of contour geometry, Pnas, 102, 3, 939-944, (2005)
[15] Moreton, H.; Séquin, C., Functional optimization for fair surface design, ACM siggraph, 26, 2, 167-176, (1992)
[16] Kimia, B.; Frankel, I.; Popescu, A., Euler spiral for shape completion, International journal of computer vision, 54, 1, 159-182, (2003) · Zbl 1076.68096
[17] R. Levien, The Euler spiral: a mathematical history, Tech. Rep. UCB/EECS-2008-111, EECS Department, University of California, Berkeley, 2008.
[18] McCrae, J.; Singh, K., Sketching piecewise clothoid curves, Computers & graphics, 33, 4, 452-461, (2009)
[19] Knuth, D., Mathematical typography, Bulletin AMS, 1, 2, 337-372, (1979) · Zbl 0404.92025
[20] G. Harary, A. Tal, 3D Euler spirals for 3D curve completion, in: Annual Symposium on Computational Geometry, 2010, pp. 393-402. · Zbl 1284.68599
[21] Harary, G.; Tal, A., Visualizing 3D Euler spirals, in: Annual Symposium on Computational Geometry, 2010, pp. 107-108 · Zbl 1284.65032
[22] Ullman, S., Filling-in the gaps: the shape of subjective contours and a model for their generation, Biological cybernetics, 25, 1, 1-6, (1976)
[23] M. Brady, W. Grimson, D. Langridge, Shape encoding and subjective contours, in: First Annual National Conference on Artificial Intelligence, 1980, pp. 15-17.
[24] Chui, K.; Chiu, W.; Direct, K. Yu, 5-axis tool-path generation from point cloud input using 3D biarc Fitting, Robotics and computer-integrated manufacturing, 24, 2, 270-286, (2008)
[25] T. Sharrock, R. Martin, Biarc in three dimensions, in: The Mathematics of Surfaces II, 1996, pp. 395-411.
[26] Rutkowski, W., Shape completion, Computer graphics and image processing, 9, 89-101, (1979)
[27] Horn, B., The curve of least energy, ACM transactions on mathematical software, 9, 4, 441-460, (1983) · Zbl 0533.41007
[28] R. Levien, The Elastica: a mathematical history, Tech. Rep. UCB/EECS-2008-103, EECS Department, University of California, Berkeley, 2008.
[29] E. Mehlum, Appell and the apple (nonlinear splines in space), in: Mathematical Methods for Curves and Surfaces, 1995, pp. 365-384. · Zbl 0834.41007
[30] Mumford, D., Elastica and computer vision, Algebraic geometry and its applications, 491-506, (1994) · Zbl 0798.53003
[31] Born, M., Untersuchungen über die stabilität der elastischen linie in ebene und raum: unter verschiedenen grenzbedingungen, (1906), Dieterich · JFM 38.0984.03
[32] Glaeser, G.; Stachel, H., Open geometry: opengl+ advanced geometry, (1999), Springer · Zbl 0917.68211
[33] Mehlum, E., Nonlinear splines, Computer aided geometric design, 173-207, (1974)
[34] Meek, D.; Walton, D., Clothoid spline transition spirals, Mathematics of computation, 59, 199, 117-133, (1992) · Zbl 0756.65005
[35] Walton, D.; Meek, D., A controlled clothoid spline, Computers & graphics, 29, 3, 353-363, (2005)
[36] Walton, D.; Meek, D., G1 interpolation with a single cornu spiral segment, Journal of computational and applied mathematics, 223, 1, 86-96, (2007) · Zbl 1155.65013
[37] L. Guiqing, L. Xianmin, L. Hua, 3D discrete clothoid splines, in: International Conference on Computer Graphics, 2001, pp. 321-324.
[38] do Carmo, M., Differential geometry of curves and surfaces, (1976), Prentice Hall · Zbl 0326.53001
[39] Forsyth, A., Calculus of variations, (1960), Dover NY · JFM 53.0480.01
[40] Graustein, W., Differential geometry, (2006), Dover · Zbl 0139.14701
[41] Ascher, U.; Petzold, L., Computer methods for ordinary differential equations and differential-algebraic equations, (1998), Society for Industrial Mathematics · Zbl 0908.65055
[42] Stern, E., Excavations at dor, (1995), Institute of Archaeology of the Hebrew University Jerusalem
[43] Brown, B.; Toler-Franklin, C.; Nehab, D.; Burns, M.; Dobkin, D.; Vlachopoulos, A.; Doumas, C.; Rusinkiewicz, S.; Weyrich, T., A system for high-volume acquisition and matching of fresco fragments: reassembling theran wall paintings, ACM transactions on graphics, 27, 3, 84, (2008), 1-10
[44] Koller, D.; Trimble, J.; Najbjerg, T.; Gelfand, N.; Levoy, M., Fragments of the city: stanfordʼs digital forma urbis romae project, Journal of Roman archaeology, 61, 237-252, (2006)
[45] Rushmeier, H., Egypt eternal experiences and research directions, Recording, modeling and visualization of cultural heritage, 22-27, (2006)
[46] Vrubel, A.; Bellon, O.; Silva, L., A 3D reconstruction pipeline for digital preservation, Computer vision and pattern recognition, 2687-2694, (2009)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.