SGP15: Eurographics Symposium on Geometry Processing (CGF 34-5)https://diglib.eg.org:443/handle/10.2312/143282019-06-24T19:10:54Z2019-06-24T19:10:54ZA One-dimensional Homologically Persistent Skeleton of an Unstructured Point Cloud in any Metric SpaceKurlin, Vitaliyhttps://diglib.eg.org:443/handle/10.1111/cgf127132017-03-16T11:30:06Z2015-01-01T00:00:00ZA One-dimensional Homologically Persistent Skeleton of an Unstructured Point Cloud in any Metric Space
Kurlin, Vitaliy
Mirela Ben-Chen and Ligang Liu
Real data are often given as a noisy unstructured point cloud, which is hard to visualize. The important problem is to represent topological structures hidden in a cloud by using skeletons with cycles. All past skeletonization methods require extra parameters such as a scale or a noise bound. We define a homologically persistent skeleton, which depends only on a cloud of points and contains optimal subgraphs representing 1-dimensional cycles in the cloud across all scales. The full skeleton is a universal structure encoding topological persistence of cycles directly on the cloud. Hence a 1-dimensional shape of a cloud can be now easily predicted by visualizing our skeleton instead of guessing a scale for the original unstructured cloud. We derive more subgraphs to reconstruct provably close approximations to an unknown graph given only by a noisy sample in any metric space. For a cloud of n points in the plane, the full skeleton and all its important subgraphs can be computed in time O(n log n).
2015-01-01T00:00:00ZHomotopic Morphing of Planar CurvesDym, NadavShtengel, AnnaLipman, Yaronhttps://diglib.eg.org:443/handle/10.1111/cgf127122017-03-16T15:15:16Z2015-01-01T00:00:00ZHomotopic Morphing of Planar Curves
Dym, Nadav; Shtengel, Anna; Lipman, Yaron
Mirela Ben-Chen and Ligang Liu
This paper presents an algorithm for morphing between closed, planar piecewise-C1 curves. The morph is guaranteed to be a regular homotopy, meaning that pinching will not occur in the intermediate curves. The algorithm is based on a novel convex characterization of the space of regular closed curves and a suitable symmetric length-deviation energy. The intermediate curves constructed by the morphing algorithm are guaranteed to be regular due to the convexity and feasibility of the problem. We show that our method compares favorably with standard curve morphing techniques, and that these methods sometimes fail to produce a regular homotopy, and as a result produce an undesirable morph. We explore several applications and extensions of our approach, including morphing networks of curves with simple connectivity, morphing of curves with different turning numbers with minimal pinching, convex combination of several curves, and homotopic morphing of b-spline curves via their control polygon.
2015-01-01T00:00:00ZCan Bi-cubic Surfaces be Class A?Karciauskas, KestutisPeters, Jörghttps://diglib.eg.org:443/handle/10.1111/cgf127112017-03-16T11:30:04Z2015-01-01T00:00:00ZCan Bi-cubic Surfaces be Class A?
Karciauskas, Kestutis; Peters, Jörg
Mirela Ben-Chen and Ligang Liu
Class A surface' is a term in the automotive design industry, describing spline surfaces with aesthetic, non- oscillating highlight lines. Tensor-product B-splines of degree bi-3 (bicubic) are routinely used to generate smooth design surfaces and are often the de facto standard for downstream processing. To bridge the gap, this paper explores and gives a concrete suggestion, how to achieve good highlight line distributions for irregular bi-3 tensor-product patch layout by allowing, along some seams, a slight mismatch of normals below the industry- accepted tolerance of one tenth of a degree. Near the irregularities, the solution can be viewed as transforming a higher-degree, high-quality formally smooth surface into a bi-3 spline surface with few pieces, sacrificing formal smoothness but qualitatively retaining the shape.
2015-01-01T00:00:00ZPerfect Matching Quad Layouts for Manifold MeshesRazafindrazaka, Faniry H.Reitebuch, UlrichPolthier, Konradhttps://diglib.eg.org:443/handle/10.1111/cgf127102017-03-16T15:15:16Z2015-01-01T00:00:00ZPerfect Matching Quad Layouts for Manifold Meshes
Razafindrazaka, Faniry H.; Reitebuch, Ulrich; Polthier, Konrad
Mirela Ben-Chen and Ligang Liu
This paper introduces a new approach to automatically generate pure quadrilateral patch layouts on manifold meshes. The algorithm is based on a careful construction of a singularity graph of a given input frame field or a given periodic global parameterization. A pure quadrilateral patch layout is then derived as a constrained minimum weight perfect matching of that graph. The resulting layout is optimal relative to a balance between coarseness and geometric feature alignment. We formulate the problem of finding pure quadrilateral patch layouts as a global optimization problem related to a well-known concept in graph theory. The main advantage of the new method is its simplicity and its computation speed. Patch layouts generated by the present algorithm are high quality and are very competitive compared to current state of the art.
2015-01-01T00:00:00Z