Search

Minkowski Pythagorean hodograph (MPH) curves provide a means for representing domains with rational boundaries via the medial axis transform. Based on the observation that MPH curves are not the only curves that yield rational envelopes, we define and study rational envelope (RE) curves that generalise MPH curves while maintaining the rationality of their associated envelopes.To demonstrate the utility of RE curves, we design a simple interpolation algorithm using RE curves, which is in turn used to produce rational surface blends between canal surfaces. Additionally, we initiate the study of rational envelope surfaces as a surface analogy to RE curves. We define rational envelope (RE) curves as a generalisation of MPH curves.RE curves are used in a simple canal surface blending scheme.We initiate the study of RE surfaces.

The medial axis transform (MAT) of a 3D shape includes the set of centers and radii of the maximally inscribed spheres, and is a complete shape descriptor that can be used to reconstruct the original shape. It is a compact representation that jointly describes geometry, topology, and symmetry properties of a given shape. In this work, we present P2MAT-NET, a neural network which learns the pattern of sparse point clouds and transform them into spheres approximating MAT. The experimental results illustrate that P2MAT-NET demonstrates better performance than state-of-the-art methods in computing MAT from point clouds, in terms of MAT quality to approximate the 3D shapes. The computed MAT can be used as an intermediate descriptor for downstream applications such as 3D shape recognition from point clouds. Our results show that it can achieve competitive performance in recognition with state-of-the-art methods.

Curve skeletons of 3D objects are central to many geometry analysis tasks in the field of computer graphics. A desirable skeleton has to meet at least four requirements: (1) topologically homotopic to the primitive shape, (2) truly well-centred, (3) feature preserving and (4) has a reasonable degree of smoothness. There are at least a couple of difficulties with skeletonization. On the one hand, finding the “best” skeleton is related to visual perception, to some extent, and thus hard to be completely solved by a pure geometric technique. On the other hand, how to exactly characterize the centredness of a skeleton, without a pre-computed medial axis surface, still remains challenging. Due to the fact that skeletons are able to encode the overall structure, a skeleton has been used to guide segmentation of a shape, which implies that there exists a dual relationship between segmentation and skeletonization. Based on the underlying duality, we propose to generate skeletons from a reliable segmentation result that is more easily available by deep learning or alternative techniques. In implementation, we first extract a collection of samples and then compute the Voronoi diagram restricted in the volume w.r.t. those samples, followed by transforming the clipped Voronoi diagram into a graph G . We further equip each edge in G with a centredness score. The user-specific segmentation result is then used to decompose G into a set of subgraphs G i = 1 k . The next task is to compute the Steiner tree for each subgraph while requiring that the Steiner trees of two adjacent parts G i and G j must be linked together. The global structure of the final skeleton inherits the proximity configuration of the user-specific segmentation, and thus is topologically homotopic to the primitive shape. At the same time, the centredness of the final skeleton is taken into full consideration by maximizing the overall centredness score. We also integrate the other two requirements carefully into our algorithmic framework. We conduct extensive experiments to evaluate the new approach in terms of the above-mentioned aspects. The experimental results show that our approach has an obvious advantage over the state-of-the-arts. As a by-product of our algorithm, users can obtain skeletons with different levels of details by editing the segmentation configurations.

Saving material and improving strength are two important but conflicting requirements in 3D printing. We propose a novel method for designing the internal supporting frame structures of 3D objects based on their medial axis such that the objects are fabricated with minimal amount of material but can still withstand specified external load. Our method is inspired by the observation that the medial axis, being the skeleton of an object, serves as a natural backbone structure of the object to improve its resistance to external loads. A hexagon-dominant framework beneath the boundary surface is constructed and a set of tree-like branching bars are designed to connect this framework to the medial axis. The internal supporting structure is further optimized to minimize the material cost subject to strength constraints. Models fabricated with our method are intended to withstand external loads from various directions, other than just from a particular direction as considered in some other existing methods. Experimental results show that our method is capable of processing various kinds of input models and producing stronger and lighter 3D printed objects than those produced with other existing methods.

In this paper, we study the persistent homology of the offset filtration of algebraic varieties. We prove the algebraicity of two quantities central to the computation of persistent homology. Moreover, we connect persistent homology and algebraic optimization. Namely, we express the degree corresponding to the distance variable of the offset hypersurface in terms of the Euclidean Distance Degree of the starting variety, obtaining a new way to compute these degrees. Finally, we describe the non-properness locus of the offset construction and use this to describe the set of points that are topologically interesting (the medial axis and center points of the bounded components of the complement of the variety) and relevant to the computation of persistent homology.

While rational curves are extensively used as a standard medium of representation in computer aided geometric design, their curvature may diverge where the tangent vector vanishes and the medial axis of the domain bounded by such curves develops peculiar behaviors. The approach of prior studies cannot be directly employed in this situation since the boundary curves cease to be real-analytic at those points. In addition to a careful re-examination of the properties of the medial axis still valid in the current setting, we present a detailed investigation of the medial axis near the points of infinite curvature that will serve as a theoretical foundation of future studies on its exact computation.

We describe and fully analyze an algorithm for C^2 Hermite interpolation by Pythagorean hodograph curves of degree 9 in Minkowski space R^2^,^1. We show that for any data there exists a four-parameter system of interpolants and we identify the one which preserves symmetry and planarity of the input data and which has the optimal approximation degree. The new algorithm is applied to an efficient approximation of segments of the medial axis transform of a planar domain leading to rational parameterizations of the offsets of the domain boundaries with a high order of approximation.

As observed by [Choi, H.I., Han, Ch.Y., Moon, H.P., Roh, K.H., Wee, N.S., 1999. Medial axis transform and offset curves by Minkowski Pythagorean hodograph curves. Computer-Aided Design 31, 59-72], curves in Minkowski space R^2^,^1 are very well suited to describe the medial axis transform (MAT) of a planar domain, and Minkowski Pythagorean hodograph (MPH) curves correspond to domains, where both the boundaries and their offsets are rational curves [Moon, H.P., 1999. Minkowski Pythagorean hodographs. Computer Aided Geometric Design 16, 739-753]. Based on these earlier results, we give a thorough discussion of G^1 Hermite interpolation by MPH cubics, focusing on solvability and approximation order. Among other results, it is shown that any analytic space-like curve without isolated inflections can be approximately converted into a G^1 spline curve composed of MPH cubics with the approximation order being equal to four. The theoretical results are illustrated by several examples. In addition, we show how the curvature of a curve in Minkowski space is related to the boundaries of the associated planar domain.

In the paper, strong proofs of some basics facts about the medial axis transform of a planar region Ω with smooth boundary curve(s) are given. In particular the decomposition of Choi et al. (1997) is derived from the set of regular disks. Two special algorithms to compute the medial axis are presented. Due to the decomposition, they can be applied to each part of Ω separately. Emphasis is given to the local analysis of the boundary's curvatures. This leads to an interesting connection to the theory of Dupin cyclides. With this mean, a predictor/corrector algorithm (as in the numerical analysis of ODE's) is developed. The examples show that the predictor yields already an excellent approximation; so only a few refining steps of the corrector are necessary.

Many applications, such as contour machining, rapid prototyping, and reverse engineering by laser scanner or coordinate measuring machine, involve sampling of free-from surfaces along section cuts by a family of parallel planes with equidistant spacing ∆ and common normal N. To ensure that such planar sections provide faithful descriptions of the shape of a surface, it is desirable to choose the relative orientation that maximizes, over the entire surface, the minimum angle between N and the local surface normal n. We address this optimization problem by computing the (symmetrized) Gauss map for the surface, projecting it stereographically onto a plane, and invoking the medial axis transform for the complement of its image to identify the orientation N that is “most distant” from the symmetrized Gauss map boundary. Using a Gauss map algorithm described elsewhere, the method is implemented in the context of bicubic Bezier surfaces, and applied to the problem of minimizing the greatest scallop height incurred in contour machining of surfaces using a 3-axis milling machine with a ball-end cutter.  2001 Elsevier Science B.V. All rights reserved.

We introduce the Minkowski Pythagorean hodograph (MPH) curve as a polynomial curve whose speed measured under the Minkowski metric is polynomial. It is a generalization of the Pythagorean hodograph (PH) curve. The MPH curve is well adapted to the representation of the medial axis transform of a planar domain. In fact, if the smooth curve segment of the medial axis transform is written in the MPH form, the boundaries of the corresponding domain are easily computed as rational curves of the MPH curve parameter. Furthermore, just subtracting a constant value from the radius, the offset curves can be obtained as rational curves. We also give the characterization of MPH curves which is invariant under the Lorentz transform.

The medial axis of a planar domain is the locus of points having at least two distinct closest points on the domain boundary. Segments of the medial axes of domains with curved boundaries fall into the two broad categories of point/curve bisectors and curve/curve bisectors. Certain “degenerate” forms of these bisectors, of a different intrinsic nature than the general instances and requiring appropriate algorithm modifications, arise generically in medial-axes computations. These include (i) point/curve bisectors where the point lies on the curve; (ii) curve/curve bisectors where the two curves are identical, i.e., the self-bisector of a curve; and (iii) curve/curve bisectors for distinct curves that share (with various orders of continuity) a common endpoint . We elucidate the geometrical nature of these special bisector forms, and develop algorithms (or algorithm modifications) for computing them. Together with existing algorithms for generic bisectors, they comprise a full complement of basic tools required in medial-axis computations.

We briefly introduce to the basics of Laguerre geometry and then show that this classical sphere geometry can be applied to solve various problems in geometric design. In the present part, we focus on applications of the cyclographic model of Laguerre geometry and the cyclographic map. It relates the medial axis and Voronoi curves/surfaces to special surface/surface intersection and the corresponding trimming procedures to hidden line removal. Rational canal surfaces are treated as cyclographic images of rational curves in R 4. This leads to a simple control structure for rational canal surfaces. Its practical use is demonstrated at hand of modeling techniques with Dupin cyclides.

Medial axis transforms, or skeletons, have many applications in computer aided geometric design and analysis. Construction of skeletons is an active area of research. We consider the inverse problem, that of recovering boundary surfaces from given skeleton elements. The skeleton of any 3D object will, in general, consist of curves and surfaces. In this paper, we first outline a method for reconstructing boundary surfaces corresponding to skeletal curves, and then extend the method for reconstruction of boundary surfaces corresponding to skeletal surfaces. Implemented examples for both curves and surfaces are included.