Search

The quality of 3D object transformation very often relies on the quality of the matching between the two objects. Geometric considerations regarding scale, rotation and translation, and user defined constraints are used to control the matching. Nevertheless, more complex measures regarding volumetric or topological similarity between the shape are more difficult to define even manually. Choosing an appropriate representation can assist in finding more robust definitions for such measures resulting in an enhanced and comprehensive automatic matching algorithm. In this paper present a hierarchal union of spheres object representation. The underlying topology of this volumetric representation can be defined as a distinct skeletal mode), the zero alpha-shape. This structure can then be used to find better matching and yield better transformations when complex topologies are involved. Our shape matching approach begins by defining a hierarchical model on top of the zero alpha shape, which induce a hierarchy on the union of spheres. Shape matching and alignment including topology and volume constraints are solved progressively while traversing this hierarchy. [ABSTRACT FROM AUTHOR]

In the edge contraction algorithm for surface simplification, two major steps are (i) ordering of the edges to be collapsed, and (ii) positioning of the new vertex to replace the collapsed edge. The accuracy of the simplified result greatly depends on which procedures are taken in the above steps. During the simplification process, degenerate cases can occur in which the optimization problem for the new vertex position produces multiple solutions. In the previous algorithms, such redundancy was utilized to achieve other desirable effeets (e.g, increasing the regularness of the triangles). In this paper we give a complete characterization of the geometric situation for the degenerate cases, and show that performing edge contraction procedure in those cases can produce unexpected damage to the original shape. To cope with the problem, we propose a new procedure, called edge elimination, which eliminates the degenerate edge and all the adjacent ones, and then retriangulates the bole in a way the geometrical shape remains unchanged. The new algorithm proceeds like the edge contraction algorithm. Whenever it has to process a degenerate edge, however, the edge elimination procedure is performed instead of edge contraction. [ABSTRACT FROM AUTHOR]

Prevalent discretization methods based on Delaunay triangulations and advancing fronts, which sample and mesh simultaneously, can guarantee well shaped triangles but at a fairly high computational cost. In this paper we present a novel and flexible two-part sampling and meshing algorithm, which produces topologically correct meshes on arbitrary boundary representations whose faces are represented parametrically, without requiring an initial coarse mesh. Our method is based on a hybrid spatial partitioning scheme driven by user-designed subdivision rules that combines the power of quadtree decomposition with the flexibility of the binary decompositions to produce meshes that favor prescribed geometric properties. Importantly, the algorithm offers a performance increase of approximately two orders of magnitude over Delaunay based methods and at least one order of magnitude over advancing front methods. At the same time, our algorithm is practically as fast as the computationally optimal algorithm based on a pure quadtree decomposition, but with a markedly better distribution in the regions with parametric distortion. The hierarchical nature of our surface decomposition is well suited to interactive applications and multithreaded implementation. [ABSTRACT FROM AUTHOR]

In the field of reverse engineering one often faces the problem of repairing triangulations with holes, intersecting triangles, Möbius-band-like structures or other artifacts. In this paper we present a novel approach for generating manifold triangle meshes from such incomplete or imperfect triangulations. Even for heavily damaged triangulations representing dosed surfaces with arbitrary genus, our algorithm results in correct manifold triangle manifolds triangle meshes. The algorithm is based on a randomized optimization technique from probability calculus called simulated annealing. [ABSTRACT FROM AUTHOR]

Despite international efforts to support specification and exchange of CAD data through acknowledged standards and data interfaces, in practice several problems still remain. One type of problem is related to the reconstruction and verification of CAD data containing defects. Major problems causing such defects are related to differences in the internal modeling accuracy of systems. Generated models that sometimes contain degenerated edges and faces having either almost zero length or zero area exacerbate the situation. Defects in the topology and / or the geometry of such geometrie models have a severe impact on computeraided post-design processes such as finite element analysis, STL file generation, tool path generation, etc. In the meantime, until improvements can be made in the processes that generated those corrupted CAD data, correction of pessible errors in CAD data can be achieved by introdueing ah intermediate post-processing stcp aimed at reconstructing an error-free, valid solid model. Within the given scope of this paper, we introduce and investigate the application of a face-sewing operator, which can be applied to CAD data based either on surface models or on solid models. Operation and quality of the model reconstruction are determined by the tolerantes of spatial model space points located on the face boundaries and their distantes apart. Due to the use of reference kernel architecture featuring a Brep scheme within ah integrated multi-dimensional topology supporting both surface models and solid models, a CAD data interface based on a standard data exchange format and an internal translator that classifies, converts and correlates pure geometric entities, sub-setting geometric entities and topological entities, open and highly flexible system architecture in respect to considered CAD data and geometric models can be maintained. [ABSTRACT FROM AUTHOR]

Surface matching is a common task in computer graphics and computer vision. In this paper, we introduce a novel algorithm that aligns scanned point-based surfaces to the related 3D model without assumptions about their relative position and orientation. Our method estimates the transformation that matches two surfaces from a pair of corresponding points using their surface positions, normals and an assistant direction on the tangent plane. This approximate alignment is used as the input of ICP algorithm to refine the registration of the surface to the model. The algorithm is easy to implement and proved to be reliable even with coarse point clouds. Furthermore, with the help of feature points, we can improve the reliability of our surface matching algorithm. [ABSTRACT FROM AUTHOR]

Presents a technique to generate a smooth patch network that best represents a segmented data set that is partitioned by curves. Issues involved in the generation of the smooth patch network; Computation of base surface, a concept shape obtained by best estimation possible; Algorithm to determine proper parameters given a set of random points and a base surface.

Examines algorithms for fitting circular arcs and straight line segment to measured data. Discussions on algebraic and geometric methods; Outcome of an empirical analysis; Presentation of an automatic fitter.

Style sketches are an essential tool for the expression and the definition of the shape of industrial products. We present a novel wavelet approach for sketch segmentation and editing expressly addressed to the designer needs. Starting from a 2D curve drawn by a user with a graphics tablet, our algorithm converts it in a B-spline representation, detects the style features, allows interactive smoothing and continuous local and global editing. The novelty compared to the existing literature is the combination of: (i) unified wavelet approach to segmentation, smoothing and editing, (ii) support for endpoint C0 and C1 continuity constraints and (iii) implementation with an interactive pen-tablet interface. Our approach requires low memory footprints with time complexity linear in the number of control points. We validated the algorithm with synthetic and practical tests. [ABSTRACT FROM AUTHOR]

We present a general framework for reconstructing binary images with disjoint components from the horizontal and vertical projections. We develop a backtracking algorithm that works for binary images having components from an arbitrary class. Thus, a priori knowledge about the components of the image to be reconstructed can be incorporated into the reconstruction process. In addition, we show how to extend the algorithm to obtain a branch-and-bound scheme useful to reconstruct images satisfying some further properties (for example similarity to a model image) as much as possible. Experimental results are also presented. [ABSTRACT FROM AUTHOR]

The topic of interpolation between slices has been an intriguing problem for many years, as it offers means to visualize and investigate a three-dimensional object given only by its level sets. A slice consists of multiple non-intersecting simple contours, each defined by a cyclic list of vertices. An interpolation solution matches between a number of such slices (two or more at a time), providing means to create a closed surface connecting these slices, or the equivalent morph from one slice to another. We offer a method to incorporate the influence of more than two slices at each point in the reconstructed surface. We investigate the flow of the surface from one slice to the next by matching vertices and extracting differential geometric quantities from that matching. Interpolating these quantities with surface patches then allows a nonlinear reconstruction which produces a free-form, non-intersecting surface. No assumptions are made about the input, such as on the number of contours in each slice, their geometric similarity, their nesting hierarchy, etc., and the proposed algorithm handles automatically all branching and hierarchical structures. The resulting surface is smooth and does not require further subdivision measures. [ABSTRACT FROM AUTHOR]

We present an approach to find dense point-to-point correspondences between two deformed surfaces corresponding to different postures of the same non-rigid object in a fully automatic way. The approach requires no prior knowledge about the shapes being registered or the initial alignment of the shapes. We consider surfaces that are represented by possibly incomplete triangular meshes. We model the deformations of an object as isometries. To solve the correspondence problem, our approach maps the intrinsic geometries of the surfaces into a low-dimensional Euclidean space via multi-dimensional scaling. This results in posture-invariant shapes that can be registered using rigid correspondence algorithms. [ABSTRACT FROM AUTHOR]

Shape idealization techniques provide a simplified description of a geometric model. Idealized descriptions are useful for recognition, animation, and other applications, providing a compact and efficient alternative to manipulating the complete model. Often idealized models are visually interesting in their own right and provide an appealing artistic impression of the models. We describe an algorithm for automatic generation of idealized bead figures from recognizable 3D models (animals, humans, etc.). The bead figures approximate the model by a set of cylindrical shapes threaded onto a skeleton of the model. As such, they provide volumetric shape information in addition to the skeleton. The bead figures can be used by applications requiring a simple and compact description of the shapes. They also provide a visually appealing, toy-like description which can be used in artistic applications. The input models are given as 3D triangulated meshes. A bead figure is generated using the skeleton of the model, often referred to as the "stick figure". The skeleton reflects the structure of the original mesh and its features, using a small number of edges. Once the skeleton is computed. beads are threaded onto it to create the final model. Computation of a compact and concise skeleton which captures the features of the model is crucial for realistic bead figure generation. The figure making process involves voxelization of the model computation of the 3D Euclidean distance transform (DT); extraction of the skeleton from the DT data (combined with the model's curvature information); and threading the beads over the skeleton. In addition to the generation of the beaded figures, our work also introduces a novel skeleton construction algorithm. The algorithm has several advantages over existing methods and may be used in other applications which utilize skeletons. [ABSTRACT FROM AUTHOR]

We present an algorithm that for a given simple non-convex polygon P finds an approximate Inner-cover by large convex polygons. The algorithm is based on an initial partitioning of P into a set C of disjoint convex polygons which are an exact tessellation of P. The algorithm then builds a set of large convex polygons contained in P by constructing the convex hulls of subsets of C. We discuss different strategies for selecting the subsets and we claim that in most cases our algorithm produces an effective approximation of P. [ABSTRACT FROM AUTHOR]

Presents the technique of parametric context-sensitive L-systems with affine geometry interpretation to specify subdivision algorithms for curves. Comparison of L-system notation with standard mathematical notations; Inference of L-systems using subdivision matrices; Practical application of L-system notation.