SIAM News Blog
SIAM News
Print

Geometric Design: Visualization and Representation

SIAG/GD Offers a Forum for Evolving Research in the Field

By Gudrun Albrecht, Daniel Gonsor, Stephen Mann, and Thomas J. Peters

Due to dramatic progress in computer technology over the last sixty years, visualization of three-dimensional (3D) geometrical objects has become an essential part of many applications in fields such as the automotive and airplane industries, architecture, medicine, mechanical engineering, and the advertising sector. Geometric design—based mainly on geometry, applied mathematics, and computer science—provides curve and surface representations and associated algorithms.

SIAM’s biennial conference on geometric design, organized by the Activity Group on Geometric Design (SIAG/GD), remains a top forum for staying abreast of evolving research in the field. The conference fosters connections between academia and industry, educating academics of the problems facing industry and allowing the two sectors to exchange information about the latest mathematical developments in curves and surfaces. In the earliest days, the conference focused on Bézier and B-spline curves, (mostly tensor product) surfaces, and algorithms for working with such representations. Over the decades, the topics discussed at the conference expanded to include new research, such as triangular Bézier patches, \(n\)-sided surface patches, general dimensionality, blossoming, multiresolution techniques leading to wavelets, subdivision surfaces, and isogeometric analysis. The best of these methods have been adopted by industry and appear in many commercial products today.

It is important to distinguish between the two basic methods for curve and surface representation, namely the representation by implicit versus parametric equations. For example, a surface in 3D space may be described by one (implicit) equation of the form \(f(x,y,z)=0\) or by three (parametric) equations of the form \(x=(u,v), \enspace y=y(u,v), \enspace z=z(u,v)\) with the parameters \(u,v\).

The implicit representation is well-suited for solid modeling, a special form of geometric modeling where a solid is a bounded, closed set of points in 3D Euclidean space. Many solid modeling systems are based on quadric primitives like planes, spheres, cylinders and cones, i.e., their 3D objects are bounded by quadric surfaces or their subsets. More complex-shaped quadrics, such as ellipsoids, hyperboloids, and paraboloids, are also found. Quadric surfaces also find applications in image processing, and have been generalized to super-quadrics in the context of computer graphics.

Dupin cyclides are well-suited to smoothly join quadric surfaces. Their discovery dates back to the early 19th century, when Charles Dupin defined them as envelopes of a variable sphere that touches three given spheres. Many authors have dealt with the problem of finding Bézier and B-Spline representations of well-known surfaces such as quadrics and Dupin cyclides [2-3].

Parametric representations of curves and surfaces are well-suited for the control of position and tangency on a curve or surface, as well as for the computation of curvature at curve or surface points. Therefore, they see wide implementation in geometric design. Parametric representations almost exclusively utilize blending functions that rely on both pure polynomials and their rational generalizations. The especially well-behaved Bernstein polynomials and B-spline basis functions are commonly used to signify the polynomials yielding the Bernstein-Bézier and the B-spline representations of curves and surfaces respectively; rational B-splines are commonly referred to as Non-Uniform Rational B-Splines (NURBS) [10]. Due to the useful geometrical relation between the curve itself and the control polygon, Bézier and B-spline curves are easy to handle and represent the standard for curve representation in the current commercial computer aided design (CAD) systems.

There are many ways of analysing these geometric representations. Methods for visual analysis commonly used in geometric design include shaded images, various forms of reflection lines, and false coloring with curvature information. Figure 1 shows a comparative visual analysis of four methods for G1 interpolation of 3D points and associated normals [9] by curved triangular Bézier patches.

Figure 1. Quality analysis of four piecewise triangular G1 Bézier interpolants by highlight lines (top row) and Gaussian curvature (bottom row). Image credit: [7].

Methods for mathematically analyzing Bézier/B-spline curves and surfaces include blossoming (a form of polar forms), which converts a degree \(n\) curve/surface \(F\) into an \(n\)-variate function that is affine in each variable, the blossom \(f\). The multi-affine nature of the blossom allows for a geometric analysis of most of the properties of Bézier and B-spline curves and surfaces. For example, starting with the control points labeled with their blossom values, and looking at the blossom values of the intermediate points constructed by the repeated affine combinations of de Casteljau’s algorithm, shows that the algorithm (a) evaluates the curve, (b) gives the derivatives of the curve at the evaluation point, and (c) subdivides the curve [20]. Several textbooks, such as [10], offer other developments of Bézier and B-spline curves and surfaces.

One example of an industrial collaboration involving Bézier curves is the synchronous visualization of molecular simulations on high performance computing platforms. The prediction of impending self-intersections of a writhing molecule was the central focus. Unfortunately, the typical animation method of analyzing each frame for self-intersections is not predictive, and the knot equivalence of isotopy became fundamental. A molecule was modeled as a knot by a Bézier curve within a tubular neighborhood. Molecular perturbations within this neighborhood preserved isotopy, ensuring that no new self-intersections could occur unless the curve approached the boundary of the neighborhood. Since the displayed graphics were piecewise linear (PL) approximations, an additional imperative was to ensure that each PL approximation was ambient isotopic to the knot [19]. Given an initial PL knot, one can then generate an ambient isotopic Bézier curve within a user-chosen error bound [18]; Figure 2 shows the convergence of an iterative algorithm for the stick knot 41. Researchers are now extending the software to consider unresolved issues on PL knots.

Figure 2. Stick knot, 0th, & 4th collinear insertions. Image credit: Thomas J. Peters.

Geometric design applications are also relevant for constructing suitable trajectories for computer numeric control (CNC) machining applications. Parametric polynomial Pythagorean-Hodograph (PH) curves introduced by Farouki and Sakkalis are important for CNC machining [14] because they have the useful property of admitting a closed form representation of their arc-length, thus permitting rational offset curves. Farouki gives an account on most of the work accomplished in this field [13].  Romani et al. generalized these curves to Algebraic-Trigonometric Pythagorean-Hodograph (ATPH) curves [23], and Albrecht et al. recently proposed the promising and general class of Pythagorean Hodograph B-Spline curves [1].

Subdivision curves and surfaces have become a popular alternative to the implicit and parametric curve and surface representations, especially in animation applications. Subdivision is a versatile tool that is both intuitive and easy to use and implement. Subdivision schemes are defined via iterative algorithms that exploit simple refinement rules to generate denser and denser point sequences, starting from an initial point set and ultimately converging to a continuous, potentially-smooth function. Several textbooks provide more detail on the theory of subdivision curves and surfaces [22, 24]. 

While subdivision methods are popular in computer animation systems, their integration into CAD applications has taken much longer. The European project NIIT4CAD investigated the practical integration of subdivision surfaces in a commercial CAD system [4-5, 8]. Figure 3 shows a result of Albrecht and Romani’s conic and convexity-preserving subdivision method [4].

Figure 3. Results of a subdivision method applied to real-world data. Starting polylines are visible in the left column, while the center and right columns display refined polylines obtained after seven steps of the algorithm. Data of the bottom row (bottle opener) are courtesy of the CAD company think3. Image credit: [2].

Although computer aided geometric design (CAGD) is a mature and well-developed field of mathematics [11-12], we are periodically confronted with industrial problems and situations that challenge the effectiveness of current, state-of-the-art CAGD theory and tools. Creative use of existing theory and techniques may prove adequate in such situations [16]. Sometimes the solution to a desired property (e.g., faster and more accurate rendering of spline surfaces) may merely require diligent review of existing literature [21], or in rarer situations, a completely novel approach [17].

Additionally, new fields and applications are immersed in CAGD challenges. Foremost among these are alternative materials, including new design and manufacturing (and design-for-manufacturing) techniques, carbon fiber composite materials, and additive manufacturing with materials ranging from polymers to titanium. A slightly different perspective involves meeting existing challenges by taking advantage of new approaches such as isogeometric analysis, which, among other benefits, alleviates the prevalent problem of producing grids from existing geometrical representations to perform various analyses. This in turn leads to the issues of alternative geometrical representations designed to overcome limitations to traditional representations, such as tensor-product polynomial splines and NURBS. Generally such alternatives require a tradeoff with traditional representations. Rational Geometric Splines (RAGS) [6, 7] which are designed to preserve the most important properties of the traditional spline representation without the inherent restrictive rectangular topology, offer an example of one such tradeoff. See Figure 4 for an example of RAGS modeling a surface of higher-order genus incompatible with traditional methods. 

Figure 4. An example of RAGS modeling a surface of higher-order genus. On the left is a grid, and on the right is a surface with colored patches. Image credit: [4].
Further enforcement of interactions between CAD and virtual reality is another promising research line for the future. This might allow more intuitive means to replace the current practice of interacting with geometric models using mouse and keyboard. Fünfzig et al. offer a first step in this direction by describing a haptic interaction with a CAD profile curve [15]. Future CAD designers might work in 3D immersion with the CAD objects and feel, move, and modify them via appropriate intuitive interfaces.

Healthy membership numbers and diversity of participating fields (academia, industry, and government) attest to both the relevance of the field and the SIAG/GD’s vibrancy. Conference attendance has remained modest but steady; the 2017 conference on geometric design will be held next July with the SIAM Annual Meeting in Pittsburgh, PA. Membership diversity is a high priority for SIAM; this is especially true within the SIAG, which reaches out to young and underrepresented practitioners and researchers through outreach programs. Meanwhile, the existence of other active contributing organizations, such as the Association for Computing Machinery’s Symposium on Solid and Physical Modeling, Shape Modeling International, and the Symposium on Geometry Processing, demonstrates the continued relevance of geometric design. In fact, the three organizations hosted a joint event—the International Geometry Summit 2016—in Berlin, Germany this summer titled the International Geometry Summit 2016. Plans for a follow-up event with SIAG/GD as a participant are materializing.


References
[1] Albrecht, G., Canonne, J.C., Beccari, C.V., & Romani, L. (2016). Pythagorean-Hodograph B-Spline curves. Preprint, arXiv.org. https://arxiv.org/abs/1609.07888 
[2] Albrecht G., & Degen, W.L.F. (1997). Construction of Bézier rectangles and triangles on the symmetric Dupin horn cyclide by means of inversion. Computer Aided Geometric Design, 14, 349-375.
[3] Albrecht, G., Paluszny, M., & Lentini, M. (2016). An intuitive way for constructing parametric quadric triangles. Comp. Appl. Math., 35(2), 595-617.
[4] Albrecht, G., & Romani, L. (2012). Convexity preserving interpolatory subdivision with conic precision. Applied Mathematics and Computation, 219, 4049-4066.
[5] Antonelli, M., Beccari, C.V., Casciola, G., Ciarloni, R., & Morigi, S. (2013). Subdivision surfaces integrated in a CAD system. Computer-Aided Design, 45(11), 1294-1305.
[6] Beccari, C., Gonsor, D., & Neamtu, M. (2014). RAGS: Rational geometric splines for surfaces of arbitrary topology. Computer Aided Geometric Design, 31, 97-110.
[7] Beccari, C., & Neamtu, M. (2016). On constructing RAGS via homogeneous splines. Computer Aided Geometric Design, 43, 109-122.
[8] Beccari, C.V., Farella, E., Liverani, A., Morigi, S., & Rucci, M. (2010). A fast interactive reverse-engineering system. Computer-Aided Design, 42(10), 860-873.
[9] Boschiroli, M., Fünfzig, C., Romani, L., & Albrecht, G. (2012, January). G1 rational blend interpolatory schemes: A comparative study. Graphical Models, 74(1), 29-49.
[10] Farin, G. (2001). Curves and Surfaces for CAGD, A Practical Guide. San Francisco, CA: Morgan Kaufmann Publishers, Inc.
[11] Farin, G., & Hansford, D. (2000). Essentials of CAGD. Natick, MA: AK Peters, Ltd.
[12] Farin, G., Hoschek, J., & Kim, M.S. (2002). Handbook of Computer Aided Geometric Design. Amsterdam: Elsevier.
[13] Farouki, R.T. (2008). Pythagorean-Hodograph Curves: Algebra and Geometry Inseparable. New York, NY: Springer.
[14] Farouki, R.T., & Sakkalis, T. (1990). Pythagorean hodographs. IBM J. Res. Develop., 34, 736-752.
[15] Fünfzig, C., Thomin, P., & Albrecht, G. (2010). Haptic manipulation of rational parametric planar cubics using shape constraints. In S.Y. Shin, S. Ossowski, M. Schumacher, M.J. Palakal, and C-C. Hung (Eds). Proceedings of the 25th ACM Symposium on Applied Computing (pp. 1253-1257). Sierre, Switzerland: Association for Computing Machinery.
[16] Grandine, T. (2000, June). Applications of contouring. SIAM Review, 42(2), 297-316.
[17] Grandine, T., & Hogan, T. (2004). A parametric quartic spline interpolant to position, tangent and curvature. Computing-Geometric Modeling Dagstuhl, 72, 65-78.
[18] Li, J., Peters, T.J., Jordan, K.E., & Zaffetti, P. (2016). Computational topology: isotopic convergence to a stick knot. Topology and its Applications, 206, 276-283.
[19] Li, J., Peters, T.J., Marinelli, K., Kovalev, E., & Jordan, K.E. (2015). Topological subtleties for molecular movies. Topology and its Applications, 188, 91-96.
[20] Mann, S. (2006). A Blossoming Development of Splines. San Rafael, CA: Morgan & Claypool.
[21] Peters, J. (2003). Mid-structures linking curved and linear geometry. In SIAM Conference on Geometric Design and Computing. Seattle, WA: Society for Industrial and Applied Mathematics
[22] Peters, J., & Reif, U. (2008). Subdivision Surfaces. New York, NY: Springer.
[23] Romani, L., Saini, L., & Albrecht, G. (2014). Algebraic-trigonometric Pythagorean-Hodograph curves and their use for Hermite interpolation. Advances in Computational Mathematics, 40(5-6), 977-1010.
[24] Warren, J., & Weimer, H. (2001). Subdivision Methods for Geometric Design, A Constructive Approach. San Francisco, CA: Morgan Kaufmann Publishers, Inc.

Gudrun Albrecht, professor of applied mathematics at the University of Valenciennes, France from 2002 to 2016, is currently changing affiliation to the Mathematics Department at the National University of Colombia in Medellin, Colombia. Daniel Gonsor is a member of the Applied Mathematics group of the Boeing Research & Technology organization in North Charleston, South Carolina. Stephen Mann is a professor in the Cheriton School of Computer Science and cross-appointed to the Department of Mechanical and Mechatronics Engineering at the University of Waterloo. Thomas J. Peters is a professor of computer science and engineering and a professor of mathematics at the University of Connecticut, with years of industrial experience in computer aided design and computer generated imagery.

blog comments powered by Disqus