Solid Modeling

Permanent URI for this community

https://diglib.eg.org/handle/10.2312/999

Browse

Now showing 1 - 20 of 43

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.
Euler Operators for Stratified Objects with Incomplete Boundaries
(The Eurographics Association, 2004) Gomes, A. J. P.; Gershon Elber and Nicholas Patrikalakis and Pere Brunet
Stratified objects such as those found in geometry-based systems (e.g. CAD systems and animation systems) can be stepwise constructed and manipulated through Euler operators. The operators proposed in this paper extend prior operators (e.g. the Euler-Masuda operators) provided that they can process n-dimensional stratified subanalytic objects with incomplete boundaries. The subanalytic objects form the biggest closed family of geometric objects defined by analytic functions. Basically, such operators are attachment, detachment, subdivision, and coaslescence operations without a prescribed order, providing the user with significant freedom in the design and programming of geometric applications.
Residual Iteration and Accurate Polynomial Evaluation for Shape-interrogation Applications
(The Eurographics Association, 2004) Hoffmann, C.; Park, with G.; Simard, J-R.; Stewart, N. F.; Gershon Elber and Nicholas Patrikalakis and Pere Brunet
Surface interrogation and intersection depend crucially on good root-finding algorithms, which in turn depend on accurate polynomial evaluation. Conventional algorithms for evaluation typically encounter difficulties near multiple roots, or roots that are very close, and this may lead to gross errors in the geometric computation, or even catastrophic failure. In this paper we study the cost and accuracy of several approaches to polynomial evaluation, explaining the reasons for non-convergence of certain methods, and supporting our subsequent conclusions with the results of benchmarking experiments.
Update Operations on 3D Simplicial Decompositions of Non-manifold Objects
(The Eurographics Association, 2004) Floriani, L. De; Hui, A.; Gershon Elber and Nicholas Patrikalakis and Pere Brunet
We address the problem of updating non-manifold mixed-dimensional objects, described by three-dimensional simplicial complexes embedded in 3D Euclidean space. We consider two local update operations, edge collapse and vertex split, which are the most common operations performed for simplifying a simplicial complex. We examine the effect of such operations on a 3D simplicial complex, and we describe algorithms for edge collapse and vertex split on a compact representation of a 3D simplicial complex, that we call the Non-Manifold Indexed data structure with Adjacencies (NMIA). We also discuss how to encode the information needed for performing a vertex split and an edge collapse on a 3D simplicial complex. The encoding of such information together with the algorithms for updating the NMIA data structure form the basis for de ning progressive as well as multi-resolution representations for objects described by 3D simplicial complexes and for extracting variable-resolution object descriptions.
Tolerance Envelopes of Planar Parametric Part Models
(The Eurographics Association, 2004) Ostrovsky-Berman, Y.; Joskowicz, L.; Gershon Elber and Nicholas Patrikalakis and Pere Brunet
We present a framework for the systematic study of parametric variation in planar mechanical parts and for ef ciently computing approximations of their tolerance envelopes. Part features are speci ed by explicit functions de ning their position and shape as a function of parameters whose nominal values vary along tolerance intervals. Their tolerance envelopes model perfect form Least and Most Material Conditions (LMC/MMC). Tolerance envelopes are useful in many design tasks such as quantifying functional errors, identifying unexpected part collisions, and determining device assemblability. We derive geometric properties of the tolerance envelopes and describe four ef cient algorithms for computing rst-order linear approximations with increasing accuracy. Our experimental results on three realistic examples show that the implemented algorithms produce better results in terms of accuracy and running time than the commonly used Monte Carlo method.
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.
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.
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.
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.
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.
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).
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.
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.
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.
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.

Browse

Browsing Solid Modeling by Issue Date

Results Per Page

Sort Options