Skip to main content
main-content

Über dieses Buch

This volume contains the papers presented at 6th Conference on Geometric Modeling and Processing (GMP 2010) held in Castro Urdiales, Spain during June16–18,2010. GeometricModelingandProcessingisabiannualinternational conference series on geometric modeling, simulation and computing. Previously, GMPhasbeenheldinHongKong(2000),Saitama,Japan(2002),Beijing,China (2004), Pittsburgh, USA (2006) and Hangzhou, China (2008). GMP 2010 received a total of 30 submissions that were reviewed by three to four Program Committee members on average. While the number of subm- sions dropped signi?cantly from previous years, the quality did not and was still quite high overall. Based on the reviews received, the committee decided to - cept 20 papers for inclusion in the proceedings. Additionally, extended versions of selected papers were considered for a special issue of Computer-Aided - sign (CAD) and Computer-Aided Geometric Design (CAGD). The paper topics spanned a wide variety and include: – Solutions of transcendental equations – Volume parameterization – Smooth curves and surfaces – Isogeometric analysis – Implicit surfaces – Computational geometry Many people helped make this conference happen and we are grateful for their help. We would especially like to thank the Conference Chair, all of the authors who submitted papers, the ProgramCommittee members who reviewed the papers and all of the participants at the conference.

Inhaltsverzeichnis

Frontmatter

Global Solutions of Well-Constrained Transcendental Systems Using Expression Trees and a Single Solution Test

Abstract
We present an algorithm which is capable of globally solving a well-constrained transcendental system over some sub-domain \(D\subset \mathbb R^n\), isolating all roots. Such a system consists of n unknowns and n regular functions, where each may contain non-algebraic (transcendental) functions like sin, \(\exp\) or log. Every equation is considered as a hyper-surface in \(\mathbb R^n\) and thus a bounding cone of its normal field can be defined over a small enough sub-domain of D. A simple test that checks the mutual configuration of these bounding cones is used that, if satisfied, guarantees at most one zero exists within the given domain. Numerical methods are then used to trace the zero. If the test fails, the domain is subdivided. Every equation is handled as an expression tree, with polynomial functions at the leaves, prescribing the domain. The tree is processed from its leaves, for which simple bounding cones are constructed, to its root, which allows to efficiently build a final bounding cone of the normal field of the whole expression. The algorithm is demonstrated on curve-curve and curve-surface intersection problems.
Maxim Aizenshtein, Michael Bartoň, Gershon Elber

Surfaces with Rational Chord Length Parameterization

Abstract
We consider a rational triangular Bézier surface of degree n and study conditions under which it is rationally parameterized by chord lengths (RCL surface) with respect to the reference circle. The distinguishing property of these surfaces is that the ratios of the three distances of a point to the three vertices of an arbitrary triangle inscribed to the reference circle and the ratios of the distances of the parameter point to the three vertices of the corresponding domain triangle are identical. This RCL property, which extends an observation from [10,13] about rational curves parameterized by chord lengths, was firstly observed in the surface case for patches on spheres in [2]. In the present paper, we analyze the entire family of RCL surfaces, provide their general parameterization and thoroughly investigate their properties.
Bohumír Bastl, Bert Jüttler, Miroslav Lávička, Zbyněk Šír

Support Function of Pythagorean Hodograph Cubics and G 1 Hermite Interpolation

Abstract
The Tschirnhausen cubic represents all non-degenerate Pythagorean Hododgraph cubics. We determine its support function and represent it as a convolution of a centrally symmetrical curve and a curve with linear normals. We use the support function to parametrize the Tschirnhausen cubic by normals. This parametrization is then used to an elegant and complete solution of the G 1 Hermite interpolation by Pythagorean Hodograph cubics. We apply the resulting algorithm to various examples and extend it to the interpolation by offsets of PH cubics.
Eva Černohorská, Zbynek Šír

Piecewise Tri-linear Contouring for Multi-material Volumes

Abstract
The ability to model objects composed of multiple materials has become increasingly more demanded in scientific applications. The visualization of a discrete multi-material volume often suffers from voxelization of the boundary between materials. We propose a contouring method that can be efficiently implemented on the GPU to reduce the artifacts and jaggedness along the material boundaries. Our method extends naturally from the standard tri-linear contouring in a signed volume, and further provides sub-voxel accuracy for representing three or more materials.
Powei Feng, Tao Ju, Joe Warren

An Efficient Algorithm for the Sign Condition Problem in the Semi-algebraic Context

Abstract
We study algebraic complexity of the sign condition problem for any given family of polynomials. Essentially, the problem consists in determining the sign condition satisfied by a fixed family of polynomials at a query point, performing as little arithmetic operations as possible. After defining precisely the sign condition and the point location problems, we introduce a method called the dialytic method to solve the first problem efficiently. This method involves a linearization of the original polynomials and provides the best known algorithm to solve the sign condition problem. Moreover, we prove a lower bound showing that the dialytic method is almost optimal. Finally, we extend our method to the point location problem.
The dialytic method solves (non-uniformly) the sign condition problem for a family of s polynomials in R[X 1,...,X n ] given by an arithmetic circuit \(\Gamma_{\mathcal F}\) of non-scalar complexity L performing \({\mathcal O}((L+n)^5\log(s))\) arithmetic operations.
If the polynomials are given in dense representation and d is a bound for their degrees, the complexity of our method is \({\mathcal O}(d^{5n} log(s))\). Comparable bounds are obtained for the point location problem.
Rafael Grimson

Constraints on Curve Networks Suitable for G 2 Interpolation

Abstract
When interpolating a network of curves to create a C 1 surface from smooth patches, the network has to satisfy an algebraic condition, called the vertex enclosure constraint. We show the existence of an additional constraint that governs the admissibility of curve networks for G 2 interpolation by smooth patches.
Thomas Hermann, Jorg Peters, Tim Strotman

Computing the Distance between Canal Surfaces

Abstract
A canal surface is the envelope of a one-parameter set of moving spheres. We present an accurate and efficient method for computing the distance between two canal surfaces. First, we use a set of cone-spheres to enclose a canal surface. A cone-sphere is a surface generated by sweeping a sphere along a straight line segment with the radius of the sphere changing linearly; thus it is a truncated circular cone capped by spheres at the two ends. Then, for two canal surfaces we use the distances between their bounding cone-spheres to approximate their distance; the accuracy of this approximation is improved by subdividing the canal surfaces into more segments and use more cone-spheres to bound the segments, until a pre-specified threshold is reached. We present a method for computing tight bounding cone-spheres of a canal surface, which is an interesting problem in its own right. Based on it, we present a complete method for efficiently computing the distances between two canal surfaces using the distances among all pairs of their bounding cone-spheres. The key to its efficiency is a novel pruning technique that can eliminate most of the pairs of cone-spheres that do not contribute to the distance between the original canal surfaces. Experimental comparisons show that our method is more efficient than Lee et al’s method [13] for computing the distance between two complex objects composed of many canal surfaces.
Yanpeng Ma, Changhe Tu, Wenping Wang

A Subdivision Approach to Planar Semi-algebraic Sets

Abstract
Semi-algebraic sets occur naturally when dealing with implicit models and boolean operations between them. In this work we present an algorithm to efficiently and in a certified way compute the connected components of semi-algebraic sets given by intersection or union of conjunctions of bi-variate equalities and inequalities. For any given precision, this algorithm can also provide a polygonal and isotopic approximation of the exact set. The idea is to localize the boundary curves by subdividing the space and then deduce their shape within small enough cells using only boundary information. Then a systematic traversal of the boundary curve graph yields polygonal regions isotopic to the connected components of the semi-algebraic set. Space subdivision is supported by a kd-tree structure and localization is done using Bernstein representation. We conclude by demonstrating our C++ implementation in the CAS Mathemagix.
Angelos Mantzaflaris, Bernard Mourrain

Non-manifold Medial Surface Reconstruction from Volumetric Data

Abstract
We present a method for medial surface reconstruction from volumetric data of thin-plate objects including junctions. Given medial voxels and distance fields computed from binarized volumes, we polygonize medial voxels by covering them with spherical supports and connecting the center points of the supports. These spherical supports are constructed by distributing spheres depending on the topological type of the voxels so that junction and boundary voxels are distributed first. Triangular meshes are built from Voronoi diagrams on medial voxels. This improvement builds correct junctions, whereas conventional voxel-based methods tend to result in small cavities around them. This paper also demonstrates several results computed from CT-scanned engineering objects.
Takashi Michikawa, Hiromasa Suzuki

Decomposing Scanned Assembly Meshes Based on Periodicity Recognition and Its Application to Kinematic Simulation Modeling

Abstract
Along with the rapid growth of industrial X-ray CT scanning systems, it is now possible to non-destructively acquire the entire meshes of assemblies consisting of a set of parts. For the advanced inspections of the assemblies, such as estimation of their assembling errors or examinations of their behaviors in the motions, based on their CT scanned meshes, it is necessary to accurately decompose the mesh and to extract a set of partial meshes each of which correspond to a part. Moreover it is required to create models which can be used for the real-product based simulations. In this paper, we focus on CT scanned meshes of gear assemblies as examples and propose beneficial methods for establishing such advance inspections of the assemblies. We first propose a method that accurately decomposes the mesh into partial meshes each of which corresponds to a gear based on periodicity recognitions. The key idea is first to accurately recognize the periodicity of each gear and then to extract the partial meshes as sets of topologically connected mesh elements where periodicities are valid. Our method can robustly and accurately recognize periodicities from noisy scanned meshes. In contrast to previous methods, our method can deal with single-material CT scanned meshes and can estimate the correct boundaries of neighboring parts with no previous knowledge. Moreover it can efficiently extract the partial meshes from large scanned meshes containing about one million triangles in a few minutes. We also propose a method for creating simulation models which can be used for a gear teeth contact evaluation using extracted partial meshes and their periodicities. Such an evaluation of teeth contacts is one of the most important functions in kinematic simulations of gear assemblies for predicting the power transmission efficiency, noise and vibration. We demonstrate the effectiveness of our method on a variety of artificial and CT scanned meshes.
Tomohiro Mizoguchi, Satoshi Kanai

Automatic Generation of Riemann Surface Meshes

Abstract
Riemann surfaces naturally appear in the analysis of complex functions that are branched over the complex plane. However, they usually possess a complicated topology and are thus hard to understand. We present an algorithm for constructing Riemann surfaces as meshes in \({\mathbb R}^3\) from explicitly given branch points with corresponding branch indices. The constructed surfaces cover the complex plane by the canonical projection onto \({\mathbb R}^2\) and can therefore be considered as multivalued graphs over the plane – hence they provide a comprehensible visualization of the topological structure.
Complex functions are elegantly visualized using domain coloring on a subset of \({\mathbb C}\). By applying domain coloring to the automatically constructed Riemann surface models, we generalize this approach to deal with functions which cannot be entirely visualized in the complex plane.
Matthias Nieser, Konstantin Poelke, Konrad Polthier

G 1 Bézier Surface Generation from Given Boundary Curve Network with T-Junction

Abstract
T-junctions usually appear in surface modeling processes that start with a given curve network. However, since T-shaped patches are not available in current CAD system so existing G 1 surface generation methods are restricted to n-sided patches. Therefore a designer must design a curve network without T-junctions, or subdivide it into n-sided patches, to avoid T-shaped topologies. We generate G 1 Bézier surfaces at a T-junction by combining the coplanar G 1 continuity condition with the de Casteljau algorithm to avoid the collision of twist points. Both T-junctions in the middle of boundary curves and at 3-valent vertices are considered. Our method requires no subdivision or triangulation of the surface, and the curve network is not changed.
Min-jae Oh, Sung Ha Park, Tae-wan Kim

Efficient Point Projection to Freeform Curves and Surfaces

Abstract
We present an efficient algorithm for projecting a given point to its closest point on a family of freeform C 1-continuous curves and surfaces. The algorithm is based on an efficient culling technique that eliminates redundant curves and surfaces which obviously contain no projection from the given point. Based on this scheme, we can reduce the whole computation to considerably smaller subproblems, which are then solved using a numerical method. In several experimental results, we demonstrate the effectiveness of the proposed approach.
Young-Taek Oh, Yong-Joon Kim, Jieun Lee, Myung-Soo Kim, Gershon Elber

Construction of Minimal Catmull-Clark’s Subdivision Surfaces with Given Boundaries

Abstract
Minimal surface is an important class of surfaces. They are widely used in the areas such as architecture, art and natural science etc.. On the other hand, subdivision technology has always been active in computer aided design since its invention. The flexibility and high quality of the subdivision surface makes them a powerful tool in geometry modeling and surface designing. In this paper, we combine these two ingredients together aiming at constructing minimal subdivision surfaces. We use the mean curvature flow, a second order geometric partial differential equation, to construct minimal Catmull-Clark’s subdivision surfaces with specified B-spline boundary curves. The mean curvature flow is solved by a finite element method where the finite element space is spanned by the limit functions of the modified Catmull-Clark’s subdivision scheme.
Qing Pan, Guoliang Xu

Parameterization of Star-Shaped Volumes Using Green’s Functions

Abstract
Parameterizations have a wide range of applications in computer graphics, geometric design and many other fields of science and engineering. Although surface parameterizations have been widely studied and are well developed, little research exists on the volumetric data due to the intrinsic difficulties in extending surface parameterization algorithms to volumetric domain. In this paper, we present a technique for parameterizing star-shaped volumes using the Green’s functions. We first show that the Green’s function on the star shape has a unique critical point. Then we prove that the Green’s functions can induce a diffeomorphism between two star-shaped volumes. We develop algorithms to parameterize star shapes to simple domains such as balls and star-shaped polycubes, and also demonstrate the volume parameterization applications: volumetric morphing, anisotropic solid texture transfer and GPU-based volumetric computation.
Jiazhi Xia, Ying He, Shuchu Han, Chi-Wing Fu, Feng Luo, Xianfeng Gu

Optimal Analysis-Aware Parameterization of Computational Domain in Isogeometric Analysis

Abstract
In isogeometric analysis (IGA for short) framework, computational domain is exactly described using the same representation as that employed in the CAD process. For a CAD object, we can construct various computational domain with same shape but with different parameterization. One basic requirement is that the resulting parameterization should have no self-intersections. In this paper, a linear and easy-to-check sufficient condition for injectivity of planar B-spline parameterization is proposed. By an example of 2D thermal conduction problem, we show that different parameterization of computational domain has different impact on the simulation result and efficiency in IGA. For problems with exact solutions, we propose a shape optimization method to obtain optimal parameterization of computational domain. The proposed injective condition is used to check the injectivity of initial parameterization constructed by discrete Coons method. Several examples and comparisons are presented to show the effectiveness of the proposed method. Compared with the initial parameterization during refinement, the optimal parameterization can achieve the same accuracy but with less degrees of freedom.
Gang Xu, Bernard Mourrain, Régis Duvigneau, André Galligo

Construction of Subdivision Surfaces by Fourth-Order Geometric Flows with G 1 Boundary Conditions

Abstract
In this paper, we present a method for constructing Loop’s subdivision surface patches with given G 1 boundary conditions and a given topology of control polygon, using several fourth-order geometric partial differential equations. These equations are solved by a mixed finite element method in a function space defined by the extended Loop’s subdivision scheme. The method is flexible to the shape of the boundaries, and there is no limitation on the number of boundary curves and on the topology of the control polygon. Several properties for the basis functions of the finite element space are developed.
Guoliang Xu, Qing Pan

Efficient Computation of 3D Clipped Voronoi Diagram

Abstract
The Voronoi diagram is a fundamental geometry structure widely used in various fields, especially in computer graphics and geometry computing. For a set of points in a compact 3D domain (i.e. a finite 3D volume), some Voronoi cells of their Voronoi diagram are infinite, but in practice only the parts of the cells inside the domain are needed, as when computing the centroidal Voronoi tessellation. Such a Voronoi diagram confined to a compact domain is called a clipped Voronoi diagram. We present an efficient algorithm for computing the clipped Voronoi diagram for a set of sites with respect to a compact 3D volume, assuming that the volume is represented as a tetrahedral mesh. We also describe an application of the proposed method to implementing a fast method for optimal tetrahedral mesh generation based on the centroidal Voronoi tessellation.
Dong-Ming Yan, Wenping Wang, Bruno Lévy, Yang Liu

Selecting Knots Locally for Curve Interpolation with Quadratic Precision

Abstract
There are several prevailing methods for selecting knots for curve interpolation. A desirable criterion for knot selection is whether the knots can assist an interpolation scheme to achieve the reproduction of polynomial curves of certain degree if the data points to be interpolated are taken from such a curve. For example, if the data points are sampled from an underlying quadratic polynomial curve, one would wish to have the knots selected such that the resulting interpolation curve reproduces the underlying quadratic curve; and in this case the knot selection scheme is said to have quadratic precision. In this paper we propose a local method for determining knots with quadratic precision. This method improves on upon our previous method that entails the solution of a global equation to produce a knot sequence with quadratic precision. We show that this new knot selection scheme results in better interpolation error than other existing methods, including the chord-length method, the centripetal method and Foley’s method, which do not possess quadratic precision.
Zhang Caiming, Wang Wenping, Wang Jiaye, Li Xuemei

Eigenmodes of Surface Energies for Shape Analysis

Abstract
In this work, we study the spectra and eigenmodes of the Hessian of various discrete surface energies and discuss applications to shape analysis. In particular, we consider a physical model that describes the vibration modes and frequencies of a surface through the eigenfunctions and eigenvalues of the Hessian of a deformation energy, and we derive a closed form representation for the Hessian (at the rest state of the energy) for a general class of deformation energies. Furthermore, we design a quadratic energy, such that the eigenmodes of the Hessian of this energy are sensitive to the extrinsic curvature of the surface.
Based on these spectra and eigenmodes, we derive two shape signatures. One that measures the similarity of points on a surface, and another that can be used to identify features of the surface. In addition, we discuss a spectral quadrangulation scheme for surfaces.
Klaus Hildebrandt, Christian Schulz, Christoph von Tycowicz, Konrad Polthier

Backmatter

Weitere Informationen