Solid Modeling

Permanent URI for this community

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

Browse

Now showing 1 - 20 of 43

3D Discrete Skeleton Generation by Wave Propagation on PR-Octree for Finite Element Mesh Sizing
(The Eurographics Association, 2004) Quadros, W. R.; Shimada, K.; Owen, S. J.; Gershon Elber and Nicholas Patrikalakis and Pere Brunet
This paper proposes a new algorithm to generate a disconnected, three-dimensional (3D) skeleton and an application of such a skeleton to generate a finite element (FE) mesh sizing function of a solid. The mesh sizing function controls the element size and the gradient, and it is crucial in generating a desired FE mesh. Here, a geometry-based mesh sizing function is generated using a skeleton. A discrete skeleton is generated by propagating a wave from the boundary towards the interior on an octree lattice of an input solid model. As the wave propagates, the distance from the boundary and direction of the wave front are calculated at the lattice-nodes (vertices) of the new front. An approximate Euclidean distance metric is used to calculate the distance traveled by the wave. Skeleton points are generated at the region where the opposing fronts meet. The distance at these skeleton points is used to measure both proximity between geometric entities and feature size, and is utilized to generate the mesh size at the lattice-nodes. The proposed octree-based skeleton is more accurate and efficient than traditional voxel-based skeleton and proves to be great tool for mesh sizing function generation.
Actual Morphing: A Physical-Based Approach for Blending Two 2D/3D Shapes
(The Eurographics Association, 2004) Hu, S. M.; Li, C. F.; Zhang, H.; Gershon Elber and Nicholas Patrikalakis and Pere Brunet
When two topologically identical shapes are blended, various possible transformation paths exist from the source shape to the target shape. Which one is the most plausible? Here we propose that the transformation process should obey a quasi-physical law. This paper combines morphing with deformation theory from continuum mechanics. By using strain energy, which reflects the magnitude of deformation, as an objective function, we convert the problem of path interpolation into an unconstrained optimization problem. To reduce the number of variables in the optimization we adopt shape functions, as used in the finite element method (FEM). A point-to-point correspondence between the source and target shapes is naturally established using these polynomial functions plus a distance map.
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.
B-rep SE: Simplicially Enhanced Boundary Representation
(The Eurographics Association, 2004) Freytag, M.; Shapiro, V.; Gershon Elber and Nicholas Patrikalakis and Pere Brunet
Boundary representation (B-rep) is a popular representation scheme for mechanical objects due to its ability to accurately represent piecewise smooth surfaces bounding solids. However, non-trivial topology and geometry of the surface patches hinder point generation, classification, searching, and other algorithms. We propose a new hybrid representation that addresses these shortcomings by imposing on the boundary representation an additional simplicial structure. The simplicial structure applies a triangle-mesh metaphor to the usual boundary representation, allowing access to points on the exact solid boundary or its many approximations. The resulting simplicially enhanced boundary representation (B-rep SE) simplifies and accelerates the usual boundary representation queries. We discuss full implementation of B-rep SE with the Parasolid kernel and demonstrate the advantages of B-rep SE in applications that integrate and visualize arbitrary fields on a solid's boundary.
Compression, Segmentation, and Modeling of Filamentary Volumetric Data
(The Eurographics Association, 2004) McCormick, B.; Busse, B.; Doddapaneni, P.; Melek, Z.; Keyser, J.; Gershon Elber and Nicholas Patrikalakis and Pere Brunet
We present a data structure for the representation of filamentary volumetric data, called the L-block. While the L-block can be used to represent arbitrary volume data sets, it is particularly geared towards representing long, thin, branching structures that prior volumetric representations have difficulty dealing with efficiently. The data structure is designed to allow for easy compression, storage, segmentation, and reconstruction of volumetric data such as scanned neuronal data. By ''polymerizing'' adjacent connected voxels into connected components, L-block construction facilitates real-time data compression and segmentation, as well as subsequent geometric modeling and visualization of embedded objects within the volume data set. We describe its application in the context of reconstruction of brain microstructure at a neuronal level of detail.
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.
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.
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.
Developability-preserved Free-form Deformation of Assembled Patches
(The Eurographics Association, 2004) Wang, C. C. L.; Tang, K.; Gershon Elber and Nicholas Patrikalakis and Pere Brunet
A novel and practical approach is presented in this paper that solves a constrained free-form deformation (FFD) problem where the developability of the tessellated embedded surface patches is preserved during the lattice deformation. The formulated constrained FFD problem has direct application in areas of product design where the surface developability is required, such as clothing, ship hulls, automobile parts, etc. In the proposed approach, the developability-preserved FFD problem is formulated as a constrained optimization problem. Different from other contained FFD approaches, the positions of lattice control points are not modified in our algorithm - as their control is insufficient in regards to the developability of all the nodes in the mesh. Moreover, the optimization is performed on the parameters of the mesh nodes rather than directly modifying their 3D coordinates, which avoids the time-consuming inverse calculation of the parameters of every node in a non-parallelepiped control lattice when further deformations are required.
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 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.
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.
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.
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.
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.
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.
Frontmatter Solid Modeling 2014
(The Eurographics Association, 2004) Gershon Elber and Nicholas Patrikalakis and Pere Brunet
Table of Contents and Preface, Committees, Cover
Handling Degeneracies in Exact Boundary Evaluation
(The Eurographics Association, 2004) Ouchi, K.; Keyser, J.; Gershon Elber and Nicholas Patrikalakis and Pere Brunet
We present a method for dealing with degenerate situations in an exact boundary evaluation system. We describe the possible degeneracies that can arise and how to detect them. We then present a numeric perturbation method that is simpler to implement within a complex system than symbolic perturbation methods.
History Based Reactive Objects for Immersive CAD
(The Eurographics Association, 2004) Convard, T.; Bourdot, P.; Gershon Elber and Nicholas Patrikalakis and Pere Brunet
Virtual Environments (VE) allow direct 3D interaction, better perception of shapes and a feel of immersion, properties that are highly desirable for design tasks. Traditional CAD software extensively use WIMP interfaces (Windows, Icons, Menus and Pointing device), but these interaction models are not suited in VE. Moreover, during a design task, the use of dialog boxes, buttons, etc. deteriorates the user's focus on his work. However, to fully bene t from immersive interaction we need more reactive behavior from 3D objects. The objects data structures must provide ef cient ways for real-time modi cation of the geometric de nitions of solids via direct 3D interactions. We will present an approach that replaces the traditional editing of the construction history graph in parametric modelers. A description of data structures and algorithms that allow the user to implicitly modify the history of a solid through a direct 3D interaction on topological elements of the objects will be given. The techniques presented here are validated in a VE prototype, using the OpenCASCADE geometric kernel and a multimodal interface.

Browse

Browsing Solid Modeling by Title

Results Per Page

Sort Options