Skip to main content

2006 | Buch

Geometric Modeling and Processing - GMP 2006

4th International Conference, Pittsburgh, PA, USA, July 26-28, 2006. Proceedings

herausgegeben von: Myung-Soo Kim, Kenji Shimada

Verlag: Springer Berlin Heidelberg

Buchreihe : Lecture Notes in Computer Science

insite
SUCHEN

Inhaltsverzeichnis

Frontmatter

Shape Reconstruction

Automatic Extraction of Surface Structures in Digital Shape Reconstruction

One of the most challenging goals in digital shape reconstruction is to create a high-quality surface model from measured data with a minimal amount of user assistance. We present techniques to automate this process and create a digital model that meets the requirements in mechanical engineering CAD/CAM/CAE. Such a CAD model is composed of a hierarchy of different types of surfaces, including primary surfaces, connecting features and vertex blends at their junctions, and obey a well-defined topological structure that we would like to reconstruct as faithfully as possible. First, combinatorially robust segmentation techniques, borrowed from Morse theory, are presented. This is followed by an algorithm to create a so-called feature skeleton, which is a curve network on the mesh that represents the region structure of the object. The final surface structure comprises the optimally located boundaries of edge blends and setback vertex blends, which are well aligned with the actual geometry of the object. This makes the surface structure sufficient for an accurate, CAD-like surface approximation including both quadrangular and trimmed surface representations. A few representative industrial objects reconstructed by Geomagic systems illustrate the efficiency and quality of the approach.

Tamas Várady, Michael A. Facello, Zsolt Terék
Ensembles for Normal and Surface Reconstructions

The majority of the existing techniques for surface reconstruction and the closely related problem of normal estimation are deterministic. Their main advantages are the speed and, given a reasonably good initial input, the high quality of the reconstructed surfaces. Nevertheless, their deterministic nature may hinder them from effectively handling incomplete data with noise and outliers. In our previous work [1], we applied a statistical technique, called

ensembles

, to the problem of surface reconstruction. We showed that an ensemble can improve the performance of a deterministic algorithm by putting it into a statistics based probabilistic setting. In this paper, with several experiments, we further study the suitability of ensembles in surface reconstruction, and also apply ensembles to normal estimation. We experimented with a widely used normal estimation technique [2] and Multi-level Partitions of Unity implicits for surface reconstruction [3], showing that normal and surface ensembles can successfully be combined to handle noisy point sets.

Mincheol Yoon, Yunjin Lee, Seungyong Lee, Ioannis Ivrissimtzis, Hans-Peter Seidel
Adaptive Fourier-Based Surface Reconstruction

In this paper, we combine Kazhdan’s FFT-based approach to surface reconstruction from oriented points with adaptive subdivision and partition of unity blending techniques. The advantages of our surface reconstruction method include a more robust surface restoration in regions where the surface bends close to itself and a lower memory consumption. The latter allows us to achieve a higher reconstruction accuracy than the original global approach. Furthermore, our reconstruction process is guided by a global error control achieved by computing the Hausdorff distance of selected input samples to intermediate reconstructions.

Oliver Schall, Alexander Belyaev, Hans-Peter Seidel

Curves and Surfaces I

Least–Squares Approximation by Pythagorean Hodograph Spline Curves Via an Evolution Process

The problem of approximating a given set of data points by splines composed of Pythagorean Hodograph (PH) curves is addressed. In order to solve this highly non-linear problem, we formulate an evolution process within the family of PH spline curves. This process generates a one–parameter family of curves which depends on a time–like parameter

t

. The best approximant is shown to be a stationary point of this evolution. The evolution process – which is shown to be related to the Gauss–Newton method – is described by a differential equation, which is solved by Euler’s method.

M. Aigner, Z. Šír, B. Jüttler
Geometric Accuracy Analysis for Discrete Surface Approximation

In geometric modeling and processing, computer graphics and computer vision, smooth surfaces are approximated by discrete triangular meshes reconstructed from sample points on the surface. A fundamental problem is to design rigorous algorithms to guarantee the geometric approximation accuracy by controlling the sampling density.

This theoretic work gives explicit formula to the bounds of Hausdorff distance, normal distance and Riemannian metric distortion between the smooth surface and the discrete mesh in terms of principle curvature and the radii of geodesic circum-circle of the triangles. These formula can be directly applied to design sampling density for data acquisition and surface reconstructions.

Furthermore, we prove the meshes induced from the Delaunay triangulations of the dense samples on a smooth surface are convergent to the smooth surface under both Hausdorff distance and normal fields. The Riemannian metrics and the Laplace-Beltrami operators on the meshes are also convergent. These theoretic results lay down the theoretic foundation for a broad class of reconstruction and approximation algorithms in geometric modeling and processing.

Junfei Dai, Wei Luo, Shing-Tung Yau, Xianfeng David Gu
Quadric Surface Extraction by Variational Shape Approximation

Based on Lloyd iteration, we present a variational method for extracting general quadric surfaces from a 3D mesh surface. This work extends the previous variational methods that extract only planes or special types of quadrics, i.e., spheres and circular cylinders. Instead of using the exact

L

2

error metric, we use a new approximate

L

2

error metric to make our method more efficient for computing with general quadrics. Furthermore, a method based on graph cut is proposed to smooth irregular boundary curves between segmented regions, which greatly improves the final results.

Dong-Ming Yan, Yang Liu, Wenping Wang

Geometric Processing I

Tracking Point-Curve Critical Distances

This paper presents a novel approach to continuously and robustly tracking critical (geometrically, perpendicular and/or extremal) distances from a moving plane point

$p \in \mathbb R^2$

to a static parametrized piecewise rational curve

γ

(

s

) (

$s \in \mathbb R$

). The approach is a combination of local marching, and the detection and computation of global topological change, both based on the differential properties of a constructed implicit surface. Unlike many techniques,

it does not use any global search strategy

except at initialization.

Implementing the mathematical idea from singularity community, we encode the critical distance surface as an implicit surface

$\mathcal{I}$

in the augmented parameter space. A point

p

s

= (

p

,

s

) is in the augmented parametric space

$\mathbb R^3 = \mathbb R^2 \times \mathbb R$

, where

p

varies over

$\mathbb R^2$

. In most situations, when

p

is perturbed, its corresponding critical distances can be evolved without structural change by marching along a sectional curve on

$\mathcal{I}$

. However, occasionally, when the perturbation crosses the evolute of

γ

, there is a transition event at which a pair of

p

’s current critical distances is annihilated, or a new pair is created and added to the set of

p

’s critical distances. To

safely

eliminate any global search for critical distances, we develop

robust

and efficient algorithm to perform the detection and computation of transition events.

Additional transition events caused by various curve discontinuities are also investigated. Our implementation assumes a B-spline representation for the curve and has interactive speed even on a lower end laptop computer.

Xianming Chen, Elaine Cohen, Richard F. Riesenfeld
Theoretically Based Robust Algorithms for Tracking Intersection Curves of Two Deforming Parametric Surfaces

This paper applies singularity theory of mappings of surfaces to 3-space and the generic transitions occurring in their deformations to develop algorithms for continuously and robustly tracking the intersection curves of two deforming parametric spline surfaces, when the deformation is represented as a family of generalized offset surfaces. This paper presents the mathematical framework, and develops algorithms accordingly, to

continuously

and

robustly

track the intersection curves of two deforming parametric surfaces, with the deformation represented as generalized offset vector fields. The set of intersection curves of 2 deforming surfaces over all time is formulated as an implicit 2-manifold

$\mathcal{I}$

in the augmented (by time domain) parametric space

$\mathbb R^5$

. Hyper-planes corresponding to some fixed time instants may

touch

$\mathcal{I}$

at some isolated transition points, which delineate transition events, i.e., the topological changes to the intersection curves. These transition points are the 0-dimensional solution to a rational system of 5 constraints in 5 variables, and can be computed efficiently and

robustly

with a rational constraint solver using subdivision and hyper-tangent bounding cones. The actual transition events are computed by contouring the local osculating paraboloids. Away from any transition points, the intersection curves do not change topology and evolve according to a simple evolution vector field that is constructed in the

euclidean space

in which the surfaces are embedded.

Xianming Chen, Richard F. Riesenfeld, Elaine Cohen, James Damon
Subdivision Termination Criteria in Subdivision Multivariate Solvers

The need for robust solutions for sets of non-linear multivariate constraints or equations needs no motivation. Subdivision-based multivariate constraint solvers [1, 2, 3] typically employ the convex hull and subdivision/domain clipping properties of the Bézier/B-spline representation to detect all regions that may contain a feasible solution. Once such a region has been identified, a numerical improvement method is usually applied, which quickly converges to the root. Termination criteria for this subdivision/domain clipping approach are necessary so that, for example, no two roots reside in the same sub-domain (root isolation).

This work presents two such termination criteria. The first theoretical criterion identifies sub-domains with at most a single solution. This criterion is based on the analysis of the normal cones of the multiviarates and has been known for some time [1]. Yet, a computationally tractable algorithm to examine this criterion has never been proposed. In this paper, we present such an algorithm for identifying sub-domains with at most a single solution that is based on a dual representation of the normal cones as parallel hyper-planes over the unit hyper-sphere. Further, we also offer a second termination criterion, based on the representation of bounding parallel hyper-plane pairs, to identify and reject sub-domains that contain no solution.

We implemented both algorithms in the multivariate solver of the IRIT [4] solid modeling system and present examples using our implementation.

Iddo Hanniel, Gershon Elber
Towards Unsupervised Segmentation of Semi-rigid Low-Resolution Molecular Surfaces

In this paper, we study a particular type of surface segmentation problem motivated by molecular biology applications. In particular, two input surfaces are given, coarsely modeling two different conformations of a molecule undergoing a semi-rigid deformation. The molecule consists of two subunits that move in a roughly rigid manner. The goal is to segment the input surfaces into these semi-rigid subcomponents. The problem is closely related to non-rigid surface registration problems, although considering only a special type of deformation that exists commonly in macromolecular movements (such as the popular

hinge motion

). We present and implement an efficient paradigm for this problem, which combines several existing and new ideas. We demonstrate the performance of our new algorithm by some preliminary experimental results in segmenting low-resolution molecular surfaces.

Yusu Wang, Leonidas J. Guibas

Curves and Surfaces II

Piecewise Developable Surface Approximation of General NURBS Surfaces, with Global Error Bounds

Developable surfaces possess qualities that are desirable in the manufacturing processes of CAD/CAM models. Specifically, models formed out of developable surfaces can be manufactured from planar sheets of material without distortion. This quality proves most useful when dealing with materials such as paper, leather or sheet metal, which cannot be easily stretched or deformed during production.

In this work, we present a semi-automatic algorithm to form a piecewise developable surface approximation of a general NURBS surface. These developable surfaces are constructed as envelopes of the tangent planes along a set of curves on the input surface. Furthermore, the Hausdorff distance between the given surface and the approximating set of developables is globally bounded by a user-provided threshold.

Jacob Subag, Gershon Elber
Efficient Piecewise Linear Approximation of Bézier Curves with Improved Sharp Error Bound

This paper presents an efficient algorithm for piecewise linear approximation of Bézier curves with improved sharp error bound. Given a Bézier curve of arbitrary degree, an approximation polygon having the same number of vertices as that of the control polygon is obtained through efficient local refinement of the initial control vertices. The approximation produces improved error bound compared with several existing solutions. With the explicit sharp error bound, it is also possible for prior estimation of necessary subdivisions to meet a pre-defined tolerance. The approximation can also be locally and adaptively refined for reducing the number of vertices of the piecewise linear approximation while meeting the required tolerance.

Weiyin Ma, Renjiang Zhang
Approximate μ-Bases of Rational Curves and Surfaces

The

μ

-bases of rational curves and surfaces are newly developed tools which play an important role in connecting parametric forms and implicit forms of curves and surfaces. However, exact

μ

-bases may have high degree with complicated rational coefficients and are often hard to compute (especially for surfaces), and sometimes they are not easy to use in geometric modeling and processing applications. In this paper, we introduce approximate

μ

-bases for rational curves and surfaces, and present an algorithm to compute approximate

μ

-bases. The algorithm amounts to solving a generalized eigenvalue problem and some quadratic programming problems with linear constraints. As applications, approximate implicitization and degree reduction of rational curves and surfaces with approximate

μ

-bases are discussed. Both the parametric equations and the implicit equations of the approximate curves/surfaces are easily obtained by using the approximate

μ

-bases. As indicated by the examples, the proposed algorithm may be a useful alternative to other methods for approximate implicitization.

Liyong Shen, Falai Chen, Bert Jüttler, Jiansong Deng

Shape Deformation

Inverse Adaptation of Hex-dominant Mesh for Large Deformation Finite Element Analysis

In the finite element analysis of metal forming processes, many mesh elements are usually deformed severely in the later stage of the analysis because of the large deformation of the geometry. Such highly distorted elements are undesirable in finite element analysis because they introduce error into the analysis results and, in the worst case, inverted elements can cause the analysis to terminate prematurely. This paper proposes an inverse adaptation method that reduces or eliminates the number of inverted mesh elements created in the later stage of finite element analysis, thereby lessening the chance of early termination and improving the accuracy of the analysis results. By this method, a simple uniform mesh is created initially, and a pre-analysis is run in order to observe the deformation behavior of the elements. Next, an input hex-dominant mesh is generated in which each element is “inversely adapted,” or pre-deformed in such a way that it has approximately the opposite shape of the final shape that normal analysis would deform it into. Thus, when finite element analysis is performed, the analysis starts with an input mesh of inversely adapted elements whose shapes are not ideal. As the analysis continues, the element shape quality improves to almost ideal and then, toward the final stage of analysis, degrades again, but much less than would be the case without inverse adaptation. This method permits analysis to run to the end, or to a further stage, with few or no inverted elements. Besides pre-skewing the element shape, the proposed method is also capable of controlling the element size according to the equivalent plastic strain information collected from the pre-analysis. The method can be repeated iteratively until reaching the final stage of deformation.

Arbtip Dheeravongkit, Kenji Shimada
Preserving Form-Features in Interactive Mesh Deformation

Interactive mesh editing techniques that preserve discrete differential properties are promising to support the design of mechanical parts such as automobile sheet metal panels. However, existing methods lack the ability to manipulate form-features and hard constraints, which are common in engineering applications. In product design, some regions on a 3D model are often required to precisely preserve the surface types and parameters during deformation. In this paper, we propose a discrete framework for preserving the shapes of form-features using hard constraints in interactive shape deformation. Deformed shapes are calculated so that form-features translate and rotate while preserving their original shapes according to manipulating handles. In addition, we show how to constrain the motion of form features using linear constraints. The implemented system can achieve a real-time response for constrained deformation.

Hiroshi Masuda, Yasuhiro Yoshioka, Yoshiyuki Furukawa
Surface Creation and Curve Deformations Between Two Complex Closed Spatial Spline Curves

This paper presents an algorithm to generate a smooth surface between two closed spatial spline curves. With the assumption that the two input curves can be projected to a single plane so that the projections do not have any mutual or self intersections, and so that one projection completely encloses the other. We describe an algorithm that generates a temporal deformation between the input curves, one which can be thought of as sweeping a surface. Instead of addressing feature matching, as many planar curve deformation algorithms do, the deformation method described generates intermediate curves that behave like wavefronts as they evolve from the shape of one boundary curve to a medial type curve, and then gradually take on the characteristics of the second boundary curve. This is achieved in a manner that assures there will be neither singularities in the parameterization nor self-intersections in the projected surface.

Joel Daniels II, Elaine Cohen

Shape Description

Computing a Family of Skeletons of Volumetric Models for Shape Description

Skeletons are important shape descriptors in object representation and recognition. Typically, skeletons of volumetric models are computed via an iterative thinning process. However, traditional thinning methods often generate skeletons with complex structures that are unsuitable for shape description, and appropriate pruning methods are lacking. In this paper, we present a new method for computing skeletons on volumes by alternating thinning and a novel skeleton pruning routine. Our method creates a family of skeletons parameterized by two user-specified numbers that determine respectively the size of curve and surface features on the skeleton. As demonstrated on both real-world models and medical images, our method generates skeletons with simple and meaningful structures that are particularly suitable for describing cylindrical and plate-like shapes.

Tao Ju, Matthew L. Baker, Wah Chiu
Representing Topological Structures Using Cell-Chains

A new topological representation of surfaces in higher dimensions, “cell-chains” is developed. The representation is a generalization of Brisson’s cell-tuple data structure. Cell-chains are identical to cell-tuples when there are no degeneracies: cells or simplices with identified vertices. The proof of correctness is based on axioms true for maps, such as those in Brisson’s cell-tuple representation. A critical new condition (axiom) is added to those of Lienhardt’s n-G-maps to give “cell-maps”. We show that cell-maps and cell-chains characterize the same topological representations.

David E. Cardoze, Gary L. Miller, Todd Phillips
Constructing Regularity Feature Trees for Solid Models

Approximate geometric models, e.g. as created by reverse engineering, describe the approximate shape of an object, but do not record the underlying design intent. Automatically inferring geometric aspects of the design intent, represented by feature trees and geometric constraints, enhances the utility of such models for downstream tasks. One approach to design intent detection in such models is to decompose them into

regularity features

. Geometric regularities such as symmetries may then be sought in each regularity feature, and subsequently be combined into a global, consistent description of the model’s geometric design intent. This paper describes a systematic approach for finding such regularity features based on recovering broken symmetries in the model. The output is a tree of regularity features for subsequent use in regularity detection and selection. Experimental results are given to demonstrate the operation and efficiency of the algorithm.

M. Li, F. C. Langbein, R. R. Martin
Insight for Practical Subdivision Modeling with Discrete Gauss-Bonnet Theorem

In this paper, we introduce an insight for practical subdivision modeling to improve the quality of control mesh structures. Our approach is based on a discrete version of Gaussian-Bonnet theorem on piecewise planar manifold meshes and vertex angle deflections that determines local geometric behavior. Based on discrete Gaussian-Bonnet theorem, summation of angle deflections of all vertices is independent of mesh structure and it depends on only the topology of the mesh surface. Based on this result, it can be possible to improve organization of mesh structure of a shape according to its intended geometric structure.

Ergun Akleman, Jianer Chen

Shape Recognition

Shape-Based Retrieval of Articulated 3D Models Using Spectral Embedding

We present an approach for robust shape retrieval from data-bases containing articulated 3D shapes. We represent each shape by the eigenvectors of an appropriately defined affinity matrix, obtaining a spectral embedding. Retrieval is then performed on these embeddings using global shape descriptors. Transformation into the spectral domain normalizes the shapes against articulation (bending), rigid-body transformations, and uniform scaling. Experimentally, we show absolute improvement in retrieval performance when conventional shape descriptors are used in the spectral domain on the McGill database of articulated 3D shapes. We also propose a simple eigenvalue-based descriptor, which is easily computed and performs comparably against the best known shape descriptors applied to the original shapes.

Varun Jain, Hao Zhang
Separated Medial Surface Extraction from CT Data of Machine Parts

This paper describes a new method for extracting separated medial surfaces from CT (Computed Tomography) data of machine parts. Plate structures are common mechanical structures such as car body shells. When designing such structures in CAD (Computer Aided Design) and CAE (Computer Aided Engineering) systems, their shapes are usually represented as surface models associated with their thickness values. In this research we are aiming at extracting medial surface models of a plate structure from its CT data so as to be used in CAD and CAE systems. However, such a structure consist of many components which are adjacent each other. For example, car body shells are consist of many welded plates. CT imaging technology has some weak points in the area. One of them is that, if there are two or more objects made of same material, CT scanner cannot make the distinction between them. The problem is caused by the principles of CT imaging technology. Because CT image represents the mass distribution within a cross section, we cannot separate the objects only from image information. However, there are many requests for scanning assembled parts and separating objects made of same material. Therefore, we propose a method to separate each components. CT data has not enough information amount as has been metinoned, so we adopt other knowledge about model shapes. We conclude with experiments on welded mechine parts for effectiveness of our method.

Tomoyuki Fujimori, Yohei Kobayashi, Hiromasa Suzuki
Two-Dimensional Selections for Feature-Based Data Exchange

Proper treatment of selections is essential in parametric feature-based design. Data exchange is one of the most important operators in any design paradigm. In this paper we address two-dimensional selections (faces and surfaces) in feature-based data exchange (FBDE). We define the problem formally and present algorithms to address it, in general and in various cases in which feature rewrites are necessary. The general algorithm operates at a geometric level and does not require solving the persistent naming problem, which is required for selection support inside a single CAD system. All algorithms are applicable to the Universal Product Representation (UPR) FBDE architecture, and the general algorithm is also applicable to the STEP parametrics specification.

Ari Rappoport, Steven Spitz, Michal Etzion

Geometric Modeling

Geometric Modeling of Nano Structures with Periodic Surfaces

Commonly used boundary-based solid and surface modeling methods in traditional computer aided design are not capable of constructing configurations with large numbers of particles or complex topology. In this paper, we propose a new geometric modeling scheme, periodic surface, for material design at atomic, molecular, and meso scales. At molecular scale, periodicity of the model allows thousands of particles to be built efficiently. At meso scale, inherent porosity of the model represents morphology of polymer and macromolecule naturally. Model construction and operation methods are developed to build crystal and molecular models based on periodic surfaces.

Yan Wang
Minimal Mean-Curvature-Variation Surfaces and Their Applications in Surface Modeling

Physical based and geometric based variational techniques for surface construction have been shown to be advanced methods for designing high quality surfaces in the fields of CAD and CAGD. In this paper, we derive a Euler-Lagrange equation from a geometric invariant curvature integral functional–the integral about the mean curvature gradient. Using this Euler-Lagrange equation, we construct a sixth-order geometric flow (named as minimal mean-curvature-variation flow), which is solved numerically by a divided-difference-like method. We apply our equation to solving several surface modeling problems, including surface blending, N-sided hole filling and point interpolating. The illustrative examples provided show that this sixth-order flow yields high quality surfaces.

Guoliang Xu, Qin Zhang
Parametric Design Method for Shapes with Aesthetic Free-Form Surfaces

In this paper, a parametric design method for aesthetic shapes which provides a direct and interactive modeling is presented. As used in an actual automobile design, our method utilizes a curve-ruler to create a free-form surface. In order to construct a surface, a curve-ruler is defined by a function like a polynomial at first. And then, two guide curves are generated by Bézier curves. Moving a curve-ruler on guide curves, a free-form surface is obtained as its locus. Designer only designates a type parameter of the curve-ruler and the parameters to allocate the curve-ruler on the guide curves. To construct a whole shape of a product, we introduce another set of parameters to control an outer shape. In this way, it is possible to control the local surface and the global shape independently. Moreover, the methods to generate a fillet, trimmed surface and features are presented. We have implemented a prototype system and will demonstrate its application on an automobile.

Tetsuo Oya, Takenori Mikami, Takanobu Kaneko, Masatake Higashi

Curves and Surfaces III

Control Point Removal Algorithm for T-Spline Surfaces

This paper discusses the problem of removing control points from a T-spline control grid while keeping the surface unchanged. An algorithm is proposed to detect whether a specified control point can be removed or not and to compute the new control points if the point is removable. The algorithm can be viewed as a reverse process of the T-spline local knot insertion algorithm. The extension of the algorithm to remove more control points is also discussed.

Yimin Wang, Jianmin Zheng
Shape Representations with Blossoms and Buds

Polynomials, either on their own or as components of splines, play a fundamental role for shape representations in computer-aided geometric design (CAGD) and computer graphics. This paper shows that any polynomial

p

(

t

) of degree

d

n

can be represented in the form of a blossom of another polynomial

b

(

t

) of degree

d

evaluated off the diagonal at the linear functions

X

j

(

t

),

j

=1, ...,

n

, chosen under some conditions expressed in terms of the elementary symmetric functions. The polynomial

b

(

t

) is called a

bud

of the polynomial

p

(

t

). An algorithm for finding a bud

b

(

t

) of a given polynomial

p

(

t

) is presented. Successively, a bud of

b

(

t

) can be computed and so on, to form a sequence of representations. The information represented by the original polynomial is preserved in its buds. This scheme can be used for encoding/decoding geometric design information.

L. Yohanes Stefanus
Manifold T-Spline

This paper develops the manifold T-splines, which naturally extend the concept and the currently available algorithms/techniques of the popular planar tensor-product NURBS and T-splines to arbitrary manifold domain of any topological type. The key idea is the global conformal parameterization that intuitively induces a tensor-product structure with a finite number of zero points, and hence offering a natural mechanism for generalizing the tensor-product splines throughout the entire manifold. In our shape modeling framework, the manifold T-splines are globally well-defined except at a finite number of extraordinary points, without the need of any tedious trimming and patching work. We present an efficient algorithm to convert triangular meshes to manifold T-splines. Because of the natural, built-in hierarchy of T-splines, we can easily reconstruct a manifold T-spline surface of high-quality with LOD control and hierarchical structure.

Ying He, Kexiang Wang, Hongyu Wang, Xianfeng Gu, Hong Qin

Subdivision Surfaces

Composite $\sqrt{2}$ Subdivision Surfaces

This paper presents a new unified framework for subdivisions based on a

$\sqrt{2}$

splitting operator, the so-called composite

$\sqrt{2}$

subdivision. The composite subdivision scheme generalizes 4-direction box spline surfaces for processing irregular quadrilateral meshes and is realized through various atomic operators. Several well-known subdivisions based on both the

$\sqrt{2}$

splitting operator and 1-4 splitting for quadrilateral meshes are properly included in the newly proposed unified scheme. Typical examples include the midedge and 4-8 subdivisions based on the

$\sqrt{2}$

splitting operator that are now special cases of the unified scheme as the simplest dual and primal subdivisions, respectively. Variants of Catmull-Clark and Doo-Sabin subdivisions based on the 1-4 splitting operator also fall in the proposed unified framework. Furthermore, unified subdivisions as extension of tensor-product B-spline surfaces also become a subset of the proposed unified subdivision scheme. In addition, Kobbelt interpolatory subdivision can also be included into the unified framework using VV-type (vertex to vertex type) averaging operators.

Guiqing Li, Weiyin Ma
Tuned Ternary Quad Subdivision

A well-documented problem of Catmull and Clark subdivision is that, in the neighborhood of extraordinary point, the curvature is unbounded and fluctuates. In fact, since one of the eigenvalues that determines elliptic shape is too small, the limit surface can have a saddle point when the designer’s input mesh suggests a convex shape. Here, we replace, near the extraordinary point, Catmull-Clark subdivision by another set of rules derived by refining each bi-cubic B-spline into nine. This provides many localized degrees of freedom for special rules so that we need not reach out to, possibly irregular, neighbor vertices when trying to improve, or tune the behavior. We illustrate a strategy how to sensibly set such degrees of freedom and exhibit tuned ternary quad subdivision that yields surfaces with bounded curvature, nonnegative weights and full contribution of elliptic and hyperbolic shape components.

Tianyun Ni, Ahmad H. Nasri

Geometric Processing II

Simultaneous Precise Solutions to the Visibility Problem of Sculptured Models

We present an efficient and robust algorithm for computing continuous visibility for two- or three-dimensional shapes whose boundaries are NURBS curves or surfaces by lifting the problem into a higher dimensional parameter space. This higher dimensional formulation enables solving for the visible regions over all view directions in the domain simultaneously, therefore providing a reliable and fast computation of the

visibility chart

, a structure which simultaneously encodes the visible part of the shape’s boundary from every view in the domain. In this framework, visible parts of planar curves are computed by solving two polynomial equations in three variables (

t

and

r

for curve parameters and

θ

for a view direction). Since one of the two equations is an inequality constraint, this formulation yields two-manifold surfaces as a zero-set in a 3-D parameter space. Considering a projection of the two-manifolds onto the

-plane, a curve’s location is invisible if its corresponding parameter belongs to the projected region. The problem of computing hidden curve removal is then reduced to that of computing the projected region of the zero-set in the

-domain. We recast the problem of computing boundary curves of the projected regions into that of solving three polynomial constraints in three variables, one of which is an inequality constraint. A topological structure of the visibility chart is analyzed in the same framework, which provides a reliable solution to the hidden curve removal problem. Our approach has also been extended to the surface case where we have two degrees of freedom for a view direction and two for the model parameter. The effectiveness of our approach is demonstrated with several experimental results.

Joon-Kyung Seong, Gershon Elber, Elaine Cohen
Density-Controlled Sampling of Parametric Surfaces Using Adaptive Space-Filling Curves

Low-discrepancy point distributions exhibit excellent uniformity properties for sampling in applications such as rendering and measurement. We present an algorithm for generating low-discrepancy point distributions on arbitrary parametric surfaces using the idea of converting the 2D sampling problem into a 1D problem by adaptively mapping a space-filling curve onto the surface. The 1D distribution takes into account the parametric mapping by employing a corrective approach similar to histogram equalisation to ensure that it gives a 2D low-discrepancy point distribution on the surface. This also allows for control over the local density of the distribution, e.g. to place points more densely in regions of higher curvature. To allow for parametric distortion, the space-filling curve is generated adaptively to cover the surface evenly. Experiments show that this approach efficiently generates low-discrepancy distributions on arbitrary parametric surfaces and creates nearly as good results as well-known low-discrepancy sampling methods designed for particular surfaces like planes and spheres. However, we also show that machine-precision limitations may require surface reparameterisation in addition to adaptive sampling.

J. A. Quinn, F. C. Langbein, R. R. Martin, G. Elber

Engineering Applications

Verification of Engineering Models Based on Bipartite Graph Matching for Inspection Applications

Engineering Inspection (EI) requires automated verification of freeform parts. Currently, parts are verified by using alignment techniques on the inspected part and a CAD model. Applying the alignment on points or meshes is demanding and time-consuming. This work proposes a new alignment method to be applied on segments rather than on mesh elements. First, a discrete curvature analysis is applied on the meshes, and segments are extracted. Then, the inspected and CAD models are represented by segment graphs. Finally, a bipartite graph matching process is applied on the segment graphs, which are combined to be the two sides of a bipartite graph. As a result, a Combinatorial Matching Tree (CMT) is defined, and potential alignments are determined. The feasibility of the proposed segments alignment is demonstrated on real scanned engineering parts.

F. Fishkel, A. Fischer, S. Ar
A Step Towards Automated Design of Side Actions in Injection Molding of Complex Parts

Side actions contribute to mold cost by resulting in an additional manufacturing and assembly cost as well as by increasing the molding cycle time. Therefore, generating shapes of side actions requires solving a complex geometric optimization problem. Different objective functions may be needed depending upon different molding scenarios (e.g., prototyping versus large production runs). Manually designing side actions is a challenging task and requires considerable expertise. Automated design of side actions will significantly reduce mold design lead times. This paper describes algorithms for generating shapes of side actions to minimize a customizable molding cost function.

Ashis Gopal Banerjee, Satyandra K. Gupta
Finding All Undercut-Free Parting Directions for Extrusions

For molding and casting processes, geometries that have undercut-free parting directions (UFPDs) are preferred for manufacturing. Identifying all UFPDs for arbitrary geometries at interactive speeds remains an open problem, however; for polyhedral parts with

n

vertices, existing algorithms take at least

O

(

n

4

) time. In this paper, we introduce a new algorithm to calculate all the UFPDs for extrusions, an important class of geometry for manufacturing in its own right and a basic geometric building block in solid modeling systems. The algorithm is based on analyzing the 2D generator profile for the extrusion, building on our previous results for 2D undercut analysis of polygons. The running time is

O

(

n

2

log

n

) to find the exact set of UFPDs or

O

(

n

) to find a slightly conservative superset of the UFPDs, where

n

is the geometric complexity of the 2D generator profile. Using this approach, the set of possible UFPDs for a part containing multiple extruded features can be reduced based upon an analysis of each such feature, efficiently identifying many parts that have no UFPDs and reducing the search time for complete algorithms that find all UFPDs.

Xiaorui Chen, Sara McMains

Short Papers

Robust Three-Dimensional Registration of Range Images Using a New Genetic Algorithm

Given two approximately aligned range images of a real object, it is possible to carry out the registration of those images using numerous algorithms such as ICP. Registration is a fundamental stage in a 3D reconstruction process. Basically the task is to match two or more images taken in different times, from different sensors, or from different viewpoints. In this paper, we discuss a number of possible approaches to the registration problem and propose a new method based on the manual pre-alignment of the images followed by an automatic registration process using a novel genetic optimization algorithm. Results for real range data are presented. This procedure focuses, on the problem of obtaining the best correspondence between points through a robust search method between partially overlapped images.

John Willian Branch, Flavio Prieto, Pierre Boulanger
Geometrical Mesh Improvement Properties of Delaunay Terminal Edge Refinement

The use of edge based refinement in general, and Delaunay terminal edge refinement in particular are well established for adaptive meshing, but largely on a heuristic basis. In this paper, we present some theoretical results on geometric improvement, and it limitations, for these methods. Angle bounds for simple longest edge bisection are reviewed and extended. Terminal edges are local maximal edges in a mesh; two additional bounds that apply to simple bisection of terminal edges in Delaunay meshes are presented. The angle properties of Delaunay insertion of the midpoint of a terminal edge are described.

Bruce Simpson, Maria-Cecilia Rivara
Matrix Based Subdivision Depth Computation for Extra-Ordinary Catmull-Clark Subdivision Surface Patches

A new subdivision depth computation technique for extra-ordinary Catmull-Clark subdivision surface (CCSS) patches is presented. The new technique improves a previous technique by using a matrix representation of the second order norm in the computation process. This enables us to get a more precise estimate of the rate of convergence of the second order norm of an extra-ordinary CCSS patch and, consequently, a more precise subdivision depth for a given error tolerance.

Gang Chen, Fuhua (Frank) Cheng
Hierarchically Partitioned Implicit Surfaces for Interpolating Large Point Set Models

We present a novel hierarchical spatial partitioning method for creating interpolating implicit surfaces using compactly supported radial basis functions (RBFs) from scattered surface data. From this hierarchy of functions we can create a range of models from coarse to fine, where a coarse model approximates and a fine model interpolates. Furthermore, our method elegantly handles irregularly sampled data and hole filling because of its multiresolutional approach. Like related methods, we combine neighboring patches without surface discontinuities by overlapping their embedding functions. However, unlike partition-of-unity approaches we do not require an additional explicit blending function to combine patches. Rather, we take advantage of the compact extent of the basis functions to directly solve for each patch’s embedding function in a way that does not cause error in neighboring patches. Avoiding overlap error is accomplished by adding phantom constraints to each patch at locations where a neighboring patch has regular constraints within the area of overlap (the function’s radius of support). Phantom constraints are also used to ensure the correct results between different levels of the hierarchy. This approach leads to efficient evaluation because we can combine the relevant embedding functions at each point through simple summation. We demonstrate our method on the Thai statue from the Stanford 3D Scanning Repository. Using hierarchical compactly supported RBFs we interpolate all 5 million vertices of the model.

David T. Chen, Bryan S. Morse, Bradley C. Lowekamp, Terry S. Yoo
A New Class of Non-stationary Interpolatory Subdivision Schemes Based on Exponential Polynomials

We present a new class of non-stationary, interpolatory subdivision schemes that can exactly reconstruct parametric surfaces including exponential polynomials. The subdivision rules in our scheme are interpolatory and are obtained using the property of reproducing exponential polynomials which constitute a

shift-invariant space

. It enables our scheme to exactly reproduce rotational features in surfaces which have trigonometric polynomials in their parametric equations. And the mask of our scheme converges to that of the polynomial-based scheme, so that the analytical smoothness of our scheme can be inferred from the smoothness of the polynomial based scheme.

Yoo-Joo Choi, Yeon-Ju Lee, Jungho Yoon, Byung-Gook Lee, Young J. Kim
Detection of Closed Sharp Feature Lines in Point Clouds for Reverse Engineering Applications

The reconstruction of a surface model from a point cloud is an important task in the reverse engineering of industrial parts. We aim at constructing a

curve network

on the point cloud that will define the border of the various surface patches. In this paper, we present an algorithm to extract

closed

sharp feature lines, which is necessary to create such a closed curve network. We use a first order segmentation to extract candidate feature points and process them as a graph to recover the sharp feature lines. To this end, a minimum spanning tree is constructed and afterwards a reconnection procedure closes the lines. The algorithm is fast and gives good results for real-world point sets from industrial applications.

Kris Demarsin, Denis Vanderstraeten, Tim Volodine, Dirk Roose
Feature Detection Using Curvature Maps and the Min-cut/Max-flow Algorithm

Automatic detection of features in three-dimensional objects is a critical part of shape matching tasks such as object registration and recognition. Previous approaches often required some type of user interaction to select features. Manual selection of corresponding features and subjective determination of the difference between objects are time consuming processes requiring a high level of expertise. The

Curvature Map

represents shape information for a point and its surrounding region and is robust with respect to grid resolution and mesh regularity. It can be used as a measure of local surface similarity. We use these curvature map properties to extract feature regions of an object. To make the selection of the feature region less subjective, we employ a min-cut/max-flow graph cut algorithm with vertex weights derived from the curvature map property. A multi-scale approach is used to minimize the dependence on user defined parameters. We show that by combining curvature maps and graph cuts in a multi-scale framework, we can extract meaningful features in a robust way.

Timothy Gatzke, Cindy Grimm
Computation of Normals for Stationary Subdivision Surfaces

This paper proposes a method for computing of normals for stationary subdivision surfaces.

In [1, 2], we derived a new necessary and sufficient condition for

C

k

-continuity of stationary subdivision schemes. First, we showed that tangent plane continuity is equivalent to the convergence of difference vectors. Thus, using “normal subdivision matrix” [3], we derived a necessary and sufficient condition of tangent plane continuity for stationary subdivision at extraordinary points (including degree 6). Moreover, we derived a necessary and sufficient condition for

C

1

-continuity.

Using the analysis, we show that at general points on stationary subdivision surfaces, the computation of the exact normal is an infinite sum of linear combinations of cross products of difference vectors even if the surfaces are

C

1

-continuous. So, it is not computable. However, we can compute the exact normal of subdivision surfaces at the limit position of a vertex of original mesh or of

j

-th subdivided mesh for any finite

j

even if the surfaces are not regular.

Hiroshi Kawaharada, Kokichi Sugihara
Voxelization of Free-Form Solids Represented by Catmull-Clark Subdivision Surfaces

A voxelization technique and its applications for objects with arbitrary topology are presented. It converts a free-form object from its continuous geometric representation into a set of voxels that best approximates the geometry of the object. Unlike traditional 3D scan-conversion based methods, our voxelization method is performed by recursively subdividing the 2D parameter space and sampling 3D points from selected 2D parameter space points. Moreover, our voxelization of 3D closed objects is guaranteed to be leak-free when a 3D flooding operation is performed. This is ensured by proving that our voxelization results satisfy the properties of separability, accuracy and minimality.

Shuhua Lai, Fuhua (Frank) Cheng
Interactive Face-Replacements for Modeling Detailed Shapes

In this paper, we present a method that allows novice users to interactively create partially self-similar manifold surfaces without relying on shape grammars or fractal methods. Moreover, the surfaces created using our method are connected. The modelers that are based on traditional fractal methods or shape grammars usually create disconnected surfaces and restrict the creative freedom of users. In most cases, the shapes are defined by hard-coded schemes that provide only a few parameters that can be adjusted by the users. We present a new approach for modeling such shapes. With this approach, novice users can interactively create a variety of unusual and interesting partially self-similar manifold surfaces.

Eric Landreneau, Ergun Akleman, John Keyser
Straightest Paths on Meshes by Cutting Planes

Geodesic paths and distances on meshes are used for many applications such as parameterization, remeshing, mesh segmentation, and simulations of natural phenomena. Noble works to compute shortest geodesic paths have been published. In this paper, we present a new approach to compute the straightest path from a source to one or more vertices on a manifold mesh with a boundary. A cutting plane with a source and a destination vertex is first defined. Then the straightest path between these two vertices is created by intersecting the cutting plane with faces on the mesh. We demonstrate that our straightest path algorithm contributes to reducing distortion in a shape-preserving linear parameterization by generating a measured boundary.

Sungyeol Lee, Joonhee Han, Haeyoung Lee
3D Facial Image Recognition Using a Nose Volume and Curvature Based Eigenface

The depth information in the face represents personal features in detail. In this study, the important personal facial information was presented by the surface curvatures and the features of vertical and horizontal of nose volume extracted from the face. The approach works by the depth of nose, the area of nose and the volume of nose based both on a vertical and horizontal are calculated. And the principal components analysis (PCA), which is calculated using the curvature data, was presented different features for each person. To classify the faces, the cascade architectures of fuzzy neural networks (CAFNNs), which can guarantee a high recognition rate as well as parsimonious knowledge base, are considered. In the experimental results, 3D images demonstrate the effectiveness of the proposed methods.

Yeunghak Lee, Ikdong Kim, Jaechang Shim, David Marshall
Surface Reconstruction for Efficient Colon Unfolding

Unfolding is a new visualization method for colorectal disease and polyp detection. Compared with a virtual endoscopy method, it is more suitable for medical applications because it gives us unfold images of the inner surface in an organ. However, since conventional unfold methods generate only 2D images, it is difficult to show the surface at a first glance and to manage unfolding results with diverse viewing controls such as rotation and magnification. To solve it, we propose an efficient unfolding method using surface reconstruction. Firstly, we generate a 2D unfold image using volume ray casting. At the same time, we store distance values from each sample point on a central path to colon surface, for all rays. After making a height field from the distance values, we reconstruct a 3D surface model. Lastly, a 3D unfold image is acquired by mapping the 2D unfold image into the 3D surface model. Since our method offers the overall shape of an organ surface, the problematic areas can be identified quickly and inspected afterwards in more detail.

Sukhyun Lim, Hye-Jin Lee, Byeong-Seok Shin
Spectral Sequencing Based on Graph Distance

The construction of linear mesh layouts has found various applications, such as implicit mesh filtering and mesh streaming, where a variety of layout quality criteria, e.g., span and width, can be considered. While spectral sequencing, derived from the Fiedler vector, is one of the best-known heuristics for minimizing width, it does not perform as well as the Cuthill-Mckee (CM) scheme in terms of span. In this paper, we treat optimal mesh layout generation as a problem of preserving graph distances and propose to use the subdominant eigenvector of a kernel (affinity) matrix for sequencing. Despite the non-sparsity of the affinity operators we use, the layouts can be computed efficiently for large meshes through subsampling and eigenvector extrapolation. Our experiments show that the new sequences obtained outperform those derived from the Fiedler vector, in terms of spans, and those obtained from CM, in terms of widths and other important quality criteria. Therefore, in applications where several such quality criteria can influence algorithm performance simultaneously, e.g., mesh streaming and implicit mesh filtering, the new mesh layouts could potentially provide a better trade-off.

Rong Liu, Hao Zhang, Oliver van Kaick
An Efficient Implementation of RBF-Based Progressive Point-Sampled Geometry

In this paper we address practical implementation issues of generating a progressive representation of point-sampled geometry. Fast and stable algorithms are proposed to efficiently implement a progressive version of the modified RBF Shepard’s method. Comparisons with several well-known methods are presented, showing that the proposed algorithms can achieve good balance between geometric error reduction and time efficiency.

Yong-Jin Liu, Kai Tang, Joneja Ajay
Segmentation of Scanned Mesh into Analytic Surfaces Based on Robust Curvature Estimation and Region Growing

For effective application of laser or X-ray CT scanned mesh models in design, analysis, and inspection etc, it is preferable that they are segmented into desirable regions as a pre-processing. Engineering parts are commonly covered with analytic surfaces, such as planes, cylinders, spheres, cones, and tori. Therefore, the portions of the part’s boundary where each can be represented by a type of analytic surface have to be extracted as regions from the mesh model. In this paper, we propose a new mesh segmentation method for this purpose. We use the mesh curvature estimation with sharp edge recognition, and the non-iterative region growing to extract the regions. The proposed mesh curvature estimation is robust for measurement noise. Moreover, our proposed region growing enables to find more accurate boundaries of underlying surfaces, and to classify extracted analytic surfaces into higher-level classes of surfaces: fillet surface, linear extrusion surface and surface of revolution than those in the existing methods.

Tomohiro Mizoguchi, Hiroaki Date, Satoshi Kanai, Takeshi Kishinami
Finding Mold-Piece Regions Using Computer Graphics Hardware

An important step in the mold design process that ensures disassembly of mold pieces consists of identifying various regions on the part that will be formed by different mold pieces. This paper presents an efficient and robust algorithm to find and highlight the mold-piece regions on a part. The algorithm can be executed on current-generation computer graphics hardware. The complexity of the algorithm solely depends on the time to render the given part. By using a system that can quickly find various mold-piece regions on a part, designers can easily optimize the part and mold design and if needed make appropriate corrections upfront, streamlining the subsequent design steps.

Alok K. Priyadarshi, Satyandra K. Gupta
A Method for FEA-Based Design of Heterogeneous Objects

This paper introduces an iterative method for FEA-based design of heterogeneous objects. A heterogeneous solid model is first created by referring to the libraries of primary materials and composition functions. The model is then discretized into an object model onto which appropriate material properties are mapped. Discretization converts continuous material variation inside an object into stepwise variation. Next, the object model is adaptively meshed and converted into a finite element model. FEA using ANSYS software is finally performed to estimate stress levels. This FEA-based design cycle is repeated until a satisfactory solution is obtained. An example (FGM pressure vessel) is shown to illustrate the entire FEA-based design cycle.

Ki-Hoon Shin, Jin-Koo Lee
Time-Varying Volume Geometry Compression with 4D Lifting Wavelet Transform

Geometry compression is an effective way to distribute high-volume geometry data within limited bandwidth and storage capacity. In this paper, a new time-varying 3D geometry compression method based on 4D lifted wavelet transform is presented. In this hybrid approach, geometric information and animation are compressed based volume grid values. Isosurfaces are reconst-ructed from decompressed grid values. With rescaling and integer-to-integer lifting, compression ratio is significantly increased without compromising quality of surfaces.

Yan Wang, Heba Hamza
A Surface Displaced from a Manifold

We present a new surface representation scheme based on a manifold structure and displacement functions. Given a geometric model represented as a point cloud, we construct a domain manifold which is a smooth surface blended from simple local patches. The original points are then projected on to the local patches and their displacements are adjusted so that the final displaced surface approximates the given point data with high precision. We demonstrate the effectiveness of our approach in various applications, including multi-resolution representations and skeleton-driven shape deformation.

Seung-Hyun Yoon
Smoothing of Meshes and Point Clouds Using Weighted Geometry-Aware Bases

In Sorkine et al. proposed a least squares based representation of meshes, which is suitable for compression and modeling. In this paper we look at this representation from the viewpoint of Tikhonov regularization. We show that this viewpoint yields a smoothing algorithm, which can be seen as shape approximation using

weighted

geometry aware bases, where the weighting factor is determined by the algorithm. The algorithm combines the Laplacian smoothing approach with the smoothing spline approach, where a global deviation constraint is imposed on the approximation. We use the generalized Laplacian matrix to measure smoothness and show how it can be modified in order to obtain smoothing behavior similar to that of curvature flow and feature preserving smoothing algorithms. The method is applicable to meshes, polygonal curves and point clouds in arbitrary dimensional spaces.

Tim Volodine, Denis Vanderstraeten, Dirk Roose
Backmatter
Metadaten
Titel
Geometric Modeling and Processing - GMP 2006
herausgegeben von
Myung-Soo Kim
Kenji Shimada
Copyright-Jahr
2006
Verlag
Springer Berlin Heidelberg
Electronic ISBN
978-3-540-36865-6
Print ISBN
978-3-540-36711-6
DOI
https://doi.org/10.1007/11802914