Solid Modeling 04

Permanent URI for this collection

https://diglib7.eg.org/handle/10.2312/1000

Browse

Now showing 1 - 20 of 43

Optimization Techniques for Approximation with Subdivision Surfaces
(The Eurographics Association, 2004) Marinov, M.; Kobbelt, L.; Gershon Elber and Nicholas Patrikalakis and Pere Brunet
We present a method for scattered data approximation with subdivision surfaces which actually uses the true representation of the limit surface as a linear combination of smooth basis functions associated with the control vertices. This is unlike previous techniques which used only piecewise linear approximations of the limit surface. By this we can assign arbitrary parameterizations to the given sample points, including those generated by parameter correction. We present a robust and fast algorithm for exact closest point search on Loop surfaces by combining Newton iteration and non-linear minimization. Based on this we perform unconditionally convergent parameter correction to optimize the approximation with respect to the L2 metric and thus we make a well-established scattered data tting technique which has been available before only for B-spline surfaces, applicable to subdivision surfaces. Further we exploit the fact that the control mesh of a subdivision surface can have arbitrary connectivity to reduce the L1 error up to a certain user-de ned tolerance by adaptively restructuring the control mesh. By employing iterative least squares solvers, we achieve acceptable running times even for large amounts of data and we obtain high quality approximations by surfaces with relatively low control mesh complexity compared to the number of sample points. Since we are using plain subdivision surfaces, there is no need for multiresolution detail coef cients and we do not have to deal with the additional overhead in data and computational complexity associated with them.
An Effective Condition for Sampling Surfaces with Guarantees
(The Eurographics Association, 2004) Boissonnat, J. D.; Oudot, S.; Gershon Elber and Nicholas Patrikalakis and Pere Brunet
The notion of e-sample, as introduced by Amenta and Bern, has proven to be a key concept in the theory of sampled surfaces. Of particular interest is the fact that, if E is an e-sample of a smooth surface S for a suf ciently small e, then the Delaunay triangulation of E restricted to S is a good approximation of S, both in a topological and in a geometric sense. Hence, if one can construct an e-sample, one also gets a good approximation of the surface. Moreover, correct reconstruction is ensured by various algorithms. In this paper, we introduce the notion of loose e-sample. We show that the set of loose e-samples contains and is asymptotically identical to the set of e-samples. The main advantage of loose e-samples over e-samples is that they are easier to check and to construct. We also present a simple algorithm that constructs provably good surface samples and meshes.
A Framework for Multiresolution Adaptive Solid Objects
(The Eurographics Association, 2004) Chang, Y.- S.; Qin, H.; Gershon Elber and Nicholas Patrikalakis and Pere Brunet
Despite the growing interest in subdivision surfaces within the computer graphics and geometric processing communities, subdivision approaches have been receiving much less attention in solid modeling. This paper presents a powerful new framework for a subdivision scheme that is defined over a simplicial complex in any n-D space. We first present a series of definitions to facilitate topological inquiries during the subdivision process. The scheme is derived from the double (k+1)-directional box splines over k-simplicial domains. Thus, it guarantees a certain level of smoothness in the limit on a regular mesh. The subdivision rules are modified by spatial averaging to guarantee C1 smoothness near extraordinary cases. Within a single framework, we combine the subdivision rules that can produce 1-, 2-, and 3-manifold in arbitrary n-D space. Possible solutions for non-manifold regions between the manifolds with different dimensions are suggested as a form of selective subdivision rules according to user preference. We briefly describe the subdivision matrix analysis to ensure a reasonable smoothness across extraordinary topologies, and empirical results support our assumption. In addition, through modifications, we show that the scheme can easily represent objects with singularities, such as cusps, creases, or corners. We further develop local adaptive refinement rules that can achieve level-of-detail control for hierarchical modeling. Our implementation is based on the topological properties of a simplicial domain. Therefore, it is flexible and extendable. We also develop a solid modeling system founded on our theoretical framework to show potential benefits of our work in industrial design, geometric processing, and other applications.
Image Based Bio-CAD Modeling and Its Applications to Biomedical and Tissue Engineering
(The Eurographics Association, 2004) Starly, B.; Darling, A.; Gomez, C.; Nam, J.; Sun, W.; Shokoufandeh, A.; Regli, W.; Gershon Elber and Nicholas Patrikalakis and Pere Brunet
CAD has been traditionally used to assist in engineering design and modeling for representation, analysis and manufacturing. Advances in Information Technology and in Biomedicine have created new uses for CAD with many novel and important biomedical applications, particularly in tissue engineering in which the CAD based bio-tissue informatics model provides critical information of tissue biological, biophysical, and biochemical properties for modeling, design, and fabrication of complex tissue substitutes. This paper will present some salient advances of bio-CAD modeling and application in computer-aided tissue engineering, including biomimetic design, analysis, simulation and freeform fabrication of tissue engineered substitutes. Overview of computer-aided tissue engineering will be given. Methodology to generate bio-CAD modeling from high resolution non-invasive imaging, the medical imaging process and the 3D reconstruction technique will be described. Enabling state-of-the-art computer program in assisting the 3D reconstruction and in biomodeling development will be introduced. Utilization of the bio-CAD model for the description and representation of the morphology, heterogeneity, and organizational structure of tissue anatomy will also be presented.
Topological and Geometric Beautification of Reverse Engineered Geometric Models
(The Eurographics Association, 2004) Langbein, F. C.; Marshall, A. D.; Martin, R. R.; Mills, B. I.; Gao, C. H.; Gershon Elber and Nicholas Patrikalakis and Pere Brunet
Boundary representation models reverse engineered from 3D range data suffer from various inaccuracies caused by noise in the measured data and the model building software. Beauti cation aims to improve such models in a post-processing step solely working with the boundary representation model. The improved model should exhibit topological and geometric regularities representing the original, ideal design intent. This paper gives an overview of algorithms for a complete beauti cation system suitable for improving the topology and the geometry of low to medium complexity reverse engineered models.
Connected and Manifold Sierpinski Polyhedra
(The Eurographics Association, 2004) Akleman, E.; Srinivasan, V.; Gershon Elber and Nicholas Patrikalakis and Pere Brunet
In this paper, we present a subdivision-inspired scheme to construct generalized Sierpinski polyhedron. Unlike usual Sierpinski polyhedra construction schemes, which create either an infinite set of disconnected tetrahedra or a non-manifold polyhedron, our robust construction scheme creates one connected and manifold polyhedron. Moreover, unlike the original schemes, this new scheme can be applied to any manifold polyhedral mesh and based on the shape of this initial polyhedra a large variety of Sierpinski polyhedra can be obtained.Our basic scheme can be viewed as applying simplest subdivision scheme [23] to an input polyhedron, but retaining old vertices. The porous structure is then obtained by removing the refined facets of the simplest subdivision.
Shape Similarity Measurement Using Ray Distances for Mass Customization
(The Eurographics Association, 2004) Hwang, T. J.; Lee, K.; Jeong, J. H.; Oh, H. Y.; Gershon Elber and Nicholas Patrikalakis and Pere Brunet
Custom-tailored products are defined as products having various sizes and shapes tailored to meet the customer's different tastes or needs. Thus fabrication of custom-tailored products inherently involves inefficiency. To minimize this inefficiency, a new paradigm is proposed in this work. In this paradigm, different parts are grouped into several groups according to their sizes and shapes. For grouping the different parts, similarity measurement algorithm is used. Similarity comparison starts with the determination of the closest pose between two shapes in consideration. The closest pose is derived by comparing the ray distances while one shape is virtually rotated with respect to the other. Shape similarity value and overall similarity value calculated from ray distances are also used for grouping. A prototype system based on the proposed methodology has been implemented and applied to the grouping and machining of the shoe lasts of various shapes and sizes.
Physics-based Modelling and Simulation of Functional Cloth for Virtual Prototyping Applications
(The Eurographics Association, 2004) Fontana, M.; Rizzi, C.; Cugini, U.; Gershon Elber and Nicholas Patrikalakis and Pere Brunet
A CAD-oriented system is proposed for the design of complex-shaped functional cloth, provided with a physics-based modelling core for simulation and virtual prototyping tasks. Textiles are physically modelled as particle grids in 3D space subjected to Newtonian dynamics, with internal spring, bending and shear forces derived from KES-F data measuring material behaviour. Interactions with the environment are expressed as external forces, collisions against obstacles, self-collisions and constraints. Differently from physicsbased animation systems, the proposed system is conceived for real design purposes, and includes functionalities emulating the construction process of actual clothing and structural textiles, e.g., mesh sewing/assembly, insertion of small components, multilayered fabric composition, mechanical shape deformation, and 2D-to-3D mapping methods. As applications, several cases of textile configurations are considered, with geometric models directly provided by industrial companies and presenting different levels of design complexities, such as garment models (e.g., men's jackets) for the clothing sector, or functional textiles used in the automotive industry (e.g., soft car tops).
Fast Continuous Collision Detection for Articulated Models
(The Eurographics Association, 2004) Redon, S.; Lin, M. C.; Manocha, D.; Gershon Elber and Nicholas Patrikalakis and Pere Brunet
We present a novel algorithm to perform continuous collision detection for articulated models. Given two discrete configurations of the links of an articulated model, we use an ''arbitrary in-between motion'' to interpolate its motion between two successive time steps and check the resulting trajectory for collisions. Our approach uses a three-stage pipeline: (1) dynamic bounding-volume hierarchy (D-BVH) culling based on interval arithmetic; (2) culling refinement using the swept volume of line swept sphere (LSS) and graphics hardware accelerated queries; (3) exact contact computation using OBB-trees and continuous collision detection between triangular primitives. The overall algorithm computes the time of collision, contact locations and prevents any interpenetration between the articulated model with the environment. We have implemented the algorithm and tested its performance on a 2.4 GHz Pentium PC with 1 Gbyte of RAM and a NVIDIA GeForce FX 5800 graphics card. In practice, our algorithm is able to perform accurate and continuous collision detection between articulated models and complex environments at nearly interactive rates.
Implicit Curve and Surface Design Using Smooth Unit Step Functions
(The Eurographics Association, 2004) Li, Q.; Gershon Elber and Nicholas Patrikalakis and Pere Brunet
This paper presents an implicit curve and surface design technique that uses smooth unit step functions. With the proposed method, an implicit curve or surface can be generated by inputting a sequence of points together with the normals at these points of the curve or surface to be designed. By choosing appropriate smooth unit step functions, these curves and surfaces can be designed to any required degree of smoothness.
Efficient and Robust Computation of an Approximated Medial Axis
(The Eurographics Association, 2004) Yang, Y.; Brock, O.; Moll, R. N.; Gershon Elber and Nicholas Patrikalakis and Pere Brunet
The medial axis can be viewed as a compact representation for an arbitrary model; it is an essential geometric structure in many applications. A number of practical algorithms for its computation have been aimed at speeding up its computation and at addressing its instabilities. In this paper we propose a new algorithm to compute the medial axis with arbitrary precision. It exhibits several desirable properties not previously combined in a practical and ef cient algorithm. First, it allows for a tradeoff between computation time and accuracy, making it well-suited for applications in which an approximation of the medial axis suf ces, but computational ef ciency is of particular concern. Second, it is output sensitive: the computation complexity of the algorithm does not depend on the size of the representation of a model, but on the size of the representation of the resulting medial axis. Third, the densities of the approximated medial axis points in different areas are adaptive to local free space volumes, based on the assumption that a coarser approximation in wide open area can still suf ce the requirements of the applications. We present theoretical results, bounding the error introduced by the approximation process. The algorithm has been implemented and experimental results are presented that illustrate its computational ef ciency and robustness.
Automatic Building of Structured Geological Models
(The Eurographics Association, 2004) Brandel, S.; Schneider, S.; Perrin, M.; Guiard, N.; Rainaud, J. F.; Lienhardt, P.; Bertrand, Y.; Gershon Elber and Nicholas Patrikalakis and Pere Brunet
The present article proposes a method to signi cantly improve the construction and updating of 3D geological models used for oil and gas exploration. The proposed method takes advantage of the speci c structures which characterize geological objects. We present a prototype of a geological pilot which enables monitoring the automatic building of a 3D model topologically and geologically consistent, starting from a set of unsegmented surfaces. The geological pilot uses a Geological Evolution Scheme (GES) which records all the interpretation elements that the exploration geologist, who is the end user, wishes to introduce into the model. The model building is performed by reading instructions deduced from the GES. Topology is dealt with step by step by using a 3D Generalized Maps (3-G-Maps) data model enriched to enable the manipulation of objects having speci c geological attributes. The result is a correct 3D model on which geological links between objects can easily be visualized. This model can automatically be revised in case of changes in the geometric data or in the interpretation. In its nal version, the created modular tool will be plugged in 3D modelers currently used in exploration geology in order to improve their performance.
A Condition for Isotopic Approximation
(The Eurographics Association, 2004) Chazal, F.; Cohen-Steiner, D.; Gershon Elber and Nicholas Patrikalakis and Pere Brunet
In this paper, we give a very simple and purely topological condition for two surfaces to be isotopic. This work is motivated by the problem of surface approximation. Applications to implicit surfaces are given, as well as connections with the well-known concepts of medial axis and local feature size.
Spline Approximation of General Volumetric Data
(The Eurographics Association, 2004) Roessl, C.; Zeilfelder, F.; Nuernberger, G.; Seidel, Hans-Peter; Gershon Elber and Nicholas Patrikalakis and Pere Brunet
We present an efficient algorithm for approximating huge general volumetric data sets, i.e. the data is given over arbitrarily shaped volumes and consists of up to millions of samples. The method is based on cubic trivariate splines, i.e. piecewise polynomials of total degree three defined w.r.t. uniform type-6 tetrahedral partitions of the volumetric domain. Similar as in the recent bivariate approximation approaches (cf. [10, 15]), the splines in three variables are automatically determined from the discrete data as a result of a two-step method (see [40]), where local discrete least squares polynomial approximations of varying degrees are extended by using natural conditions, i.e. the continuity and smoothness properties which determine the underlying spline space. The main advantages of this approach with linear algorithmic complexity are as follows: no tetrahedral partition of the volume data is needed, only small linear systems have to be solved, the local variation and distribution of the data is automatically adapted, Bernstein-Bézier techniques well-known in Computer Aided Geometric Design (CAGD) can be fully exploited, noisy data are automatically smoothed. Our numerical examples with huge data sets for synthetic data as well as some real-world data confirm the efficiency of the methods, show the high quality of the spline approximation, and illustrate that the rendered iso-surfaces inherit a visual smooth appearance from the volume approximating splines.
Constraint-based Design of B-spline Surfaces from Curves
(The Eurographics Association, 2004) Michalik, P.; Bruderlin, B. D.; Gershon Elber and Nicholas Patrikalakis and Pere Brunet
In this paper we describe the design of B-spline surface models by means of curves and tangency conditions. The intended application is the conceptual constraint-driven design of surfaces from hand-sketched curves. The solving of generalized curve surface constraints means to find the control points of the surface from one or several curves, incident on the surface, and possibly additional tangency and smoothness conditions. This is accomplished by solving large, and generally under-constrained, and badly conditioned linear systems of equations. For this class of linear systems, no unique solution exists and straight forward methods such as Gaussian elimination, QR-decomposition, or even blindly applied Singular Value Decomposition (SVD) will fail. We propose to use regularization approaches, based on the so-called L-curve. The L-curve, which can be seen as a numerical high frequency filter, helps to determine the regularization parameter such that a numerically stable solution is obtained. Additional smoothness conditions are defined for the surface to filter out aliasing artifacts, which are due to the discrete structure of the piece-wise polynomial structure of the B-spline surface. This leads to a constrained optimization problem, which is solved by Modified Truncated SVD: a L-curve based regularization algorithm which takes into account a user defined smoothing constraint.
Contour Interpolation with Bounded Dihedral Angles
(The Eurographics Association, 2004) Bereg, S.; Jiang, M.; Zhu, B.; Gershon Elber and Nicholas Patrikalakis and Pere Brunet
In this paper, we present the first nontrivial theoretical bound on the quality of the 3D solids generated by any contour interpolation method. Given two arbitrary parallel contour slices with n vertices in 3D, let a be the smallest angle in the constrained Delaunay triangulation of the corresponding 2D contour overlay, we present a contour interpolation method which reconstructs a 3D solid with the minimum dihedral angle of at least a 8 . Our algorithm runs in O(nlogn) time where n is the size of the contour overlay. We also present a heuristic algorithm that optimizes the dihedral angles of a mesh representing a surface in 3D.
From Computer Geometry to Manufacturing Algorithms
(The Eurographics Association, 2004) Cohen, E.; Gershon Elber and Nicholas Patrikalakis and Pere Brunet
Abstractly, machining a shape is rather a simple task, that is, one is merely asked to subtractively metamorphose a superset of stock material into the ultimate shape of a given geometric model. In practice, however, there are a multitude of technical considerations that make automating this process rather a formidable and generally unsolved problem.This presentation will discuss some of the practical and technical considerations of machining a desired shape from a block of stock material. When a realistic cost function is introduced where literally ¸Stime is money,ˇT formulating a winning strategy for efficiently eliminating material while optimizing cutter path times as well as automatic tool changes becomes a complex matter involving much mathematical richness. Just as computer architecture affects computing complexity analysis, so machine tool architecture can significantly alter the cost functions and corresponding strategies of various manufacturing algorithms. Finally, the quality of the desired finish, the closeness of the approximation, as it were, has a major influence on what strategies emerge as superior. Further, new technologies are changing the fundamental cost functions so that new strategies are called for. Many examples and some video will be presented to illustrate the issues, especially in cases that may not be intuitive to the uninitiated. No prior manufacturing experience will be assumed for this talk.
Efficient Processing of 3D Scanned Models
(The Eurographics Association, 2004) Scopigno, R.; Gershon Elber and Nicholas Patrikalakis and Pere Brunet
The construction of detailed and accurate 3D models is made easier by the increasing diffusion of automatic sampling devices (often called 3D scanners). These allow to build digital models of real 3D objects in a cost- and time-effective manner. The talk will present the capabilities of this technology focusing mainly on some issues which are preventing a wider use of this technology, such as for example the considerable user intervention required and the complexity of the models produced.Another emerging issue is how to support the visual presentation of the models (local or remote) with guaranteed interactive rendering and data protection. Some examples of the results of current projects, mainly in the Cultural Heritage field, will be shown.
Medial Axis Extraction and Shape Manipulation of Solid Objects Using Parabolic PDEs
(The Eurographics Association, 2004) Du, H.; Qin, H.; Gershon Elber and Nicholas Patrikalakis and Pere Brunet
Shape skeletonization (i.e., medial axis extraction) is powerful in many visual computing applications, such as pattern recognition, object segmentation, registration, and animation. This is because medial axis (or skeleton) provides more compact representations for solid models while preserving their topological properties and other features. Meanwhile, PDE techniques are widely utilized in computer graphics fields to model solid objects and natural phenomena, formulate physical laws to govern the behavior of objects in real world, and provide means to measure the feature of movements, such as velocity, acceleration, change of energy, etc. Certain PDEs such as diffusion equations and Hamilton-Jacobi equation have been used to detect medial axes of 2D images and volumetric data with ease. However, using such equations to extract medial axes or skeletons for solid objects bounded by arbitrary polygonal meshes directly is yet to be fully explored. In this paper, we expand the use of diffusion equations to approximate medial axes of arbitrary 3D solids represented by polygonal meshes based on their differential properties. It offers an alternative but natural way for medial axis extraction for commonly used 3D polygonal models. By solving the PDE along time axis, our system can not only quickly extract diffusion-based medial axes of input meshes, but also allow users to visualize the extraction process at each time step. In addition, our model provides users a set of manipulation toolkits to sculpt extracted medial axes, then use diffusion-based techniques to recover corresponding deformed shapes according to the original input datasets. This skeleton-based shape manipulation offers a fast and easy way for animation and deformation of complicated solid objects.
Integrated Feature-Based and Geometric CAD Data Exchange
(The Eurographics Association, 2004) Spitz, S. N.; Rappoport, A.; Gershon Elber and Nicholas Patrikalakis and Pere Brunet
Data exchange between CAD systems is an extremely important solid modeling concept, fundamental both for the theory of the field and for its practical applications. The two main data exchange (DE) paradigms are geometric and parametric DE. Geometric DE is the ordinary method, in which the boundary representation of the object is exchanged. Parametric (or featurebased) DE is a novel method where, given a parametric history (feature) graph in a source system, the goal is to construct a graph in the target system that results in similar geometry while preserving as much parametric information as possible. Each method has its uses and associated problems. In this paper, we introduce Geometry Per Feature (GPF), a method for integration of parametric and geometric data exchange at the single part (object) level. Features can be exchanged either parametrically or geometrically, according to user guidelines and system constraints. At the target system, the resulting model is represented using a history tree, regardless of the amount of original parametric features that have been rewritten as geometric ones. Using this method we maximize the exchange of overall parametric data and overcome one of the main stumbling blocks for feature-based data exchange.

Browse

Browsing Solid Modeling 04 by Issue Date

Results Per Page

Sort Options