Solid Modeling

Permanent URI for this community

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

Browse

Now showing 1 - 20 of 43

Plumber: A Multi-scale Decomposition of 3D Shapes into Tubular Primitives and Bodies
(The Eurographics Association, 2004) Mortara, M.; Patane, G.; Spagnuolo, M.; Falcidieno, B.; Rossignac, J.; Gershon Elber and Nicholas Patrikalakis and Pere Brunet
Plumber is a specialized shape classi cation method for detecting tubular features of 3D objects represented by a triangle mesh. The Plumber algorithm segments a surface into connected components that are either body parts or elongated features, that is, handle-like and protrusion-like features, together with their concave counterparts, i.e. narrow tunnels and wells. The segmentation can be done at single or multi-scale, and produces a shape graph which codes how the tubular components are attached to the main body parts. Moreover, each tubular feature is represented by its skeletal line and an average cross-section radius.
Multiresolution Heterogeneous Solid Modeling and Visualization Using Trivariate Simplex Splines
(The Eurographics Association, 2004) Hua, J.; He, Y.; Qin, H.; Gershon Elber and Nicholas Patrikalakis and Pere Brunet
This paper presents a new and powerful heterogeneous solid modeling paradigm for representing, modeling, and rendering of multi-dimensional, physical attributes across any volumetric objects. The modeled solid can be of complicated geometry and arbitrary topology. It is formulated using a trivariate simplex spline defined over a tetrahedral decomposition of any 3D domain. Heterogeneous material attributes associated with solid geometry can be modeled and edited by manipulating the control vectors and/or associated knots of trivariate simplex splines easily. The multiresolution capability is achieved by interactively subdividing any regions of interest and allocating more knots and control vectors accordingly. We also develop a feature-sensitive fitting algorithm that can reconstruct a more compact, continuous trivariate simplex spline from structured or unstructured volumetric grids. This multiresolution representation results from the adaptive and progressive tetrahedralization of the 3D domain. In addition, based on the simplex spline theory, we derive several theoretical formula and propose a fast direct rendering algorithm for interactive data analysis and visualization of the simplex spline volumes. Our experiments demonstrate that the proposed paradigm augments the current modeling and visualization techniques with the new and unique advantages.
Shortest Circuits with Given Homotopy in a Constellation
(The Eurographics Association, 2004) Michelucci, D.; Neveu, M.; Gershon Elber and Nicholas Patrikalakis and Pere Brunet
Abstract A polynomial method is described for computing the shortest circuit with a prescribed homotopy on a surface. The surface is not described by a mesh but by a constellation: a set of sampling points. Points close enough (their distance is less than a prescribed threshold) are linked with an edge: the induced graph is not a triangulation but still permits to compute homologic and homotopic properties. Advantages of constellations over meshes are their simplicity and robustness.
Frontmatter Solid Modeling 2014
(The Eurographics Association, 2004) Gershon Elber and Nicholas Patrikalakis and Pere Brunet
Table of Contents and Preface, Committees, Cover
Stability and Homotopy of a Subset of the Medial Axis
(The Eurographics Association, 2004) Chazal, F.; Lieutier, A.; Gershon Elber and Nicholas Patrikalakis and Pere Brunet
Medial Axis is known to be unstable for non smooth objects. The Medial Axis has applications in image analysis and mathematical morphology, Solid Modeling, or domain decomposition for CAD to CAE (i.e. Finite Elements) models generation.
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.
Reconstruction with 3D Geometric Bilateral Filter
(The Eurographics Association, 2004) Miropolsky, A.; Fischer, A.; Gershon Elber and Nicholas Patrikalakis and Pere Brunet
In recent years, reverse engineering (RE) techniques have been developed for surface reconstruction from 3D scanned data. Typical sampling data, however, usually is large scale and contains unorganized points, thus leading to some anomalies in the reconstructed object. To improve performance and reduce processing time, Hierarchical Space Decomposition (HSD) methods can be applied. These methods are based on reducing the sampled data by replacing a set of original points in each voxel by a representative point, which is later connected in a mesh structure. This operation is analogous to smoothing with a simple low- pass filter (LPF). Unfortunately, this principle also smoothes sharp geometrical features, an effect that is not desired. The high performance results of bilateral filtering for removing noise from 2D images while preserving details motivated us to extend this filtering and apply it to 3D scan points. This paper introduces anisotropic 3D scan point filtering, which we have defined as 3D Geometric Bilateral Filtering (GBF). The proposed GBF method smoothes low curvature regions while preserving sharp geometric features, and it is robust, simple and fast.
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.
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.
Medial-Axis Based Solid Representation
(The Eurographics Association, 2004) Shaham, A.; Shamir, A.; Cohen-Or, D.; Gershon Elber and Nicholas Patrikalakis and Pere Brunet
The medial axis (MA) of an object and medial axis transform (MAT) have many applications in solid modeling, computer graphics and other areas. Exact computation of MA is complex and various medial axis approximation algorithms were studied. One of the most successful is based on the computation of the Voronoi diagram of a set of sample points on the boundary of the object. Based on this method we present a novel representation of solids, which we call a pair-mesh. The pair-mesh is a deformable manifold surface triangulation where each node deforms between a pair of vertices one on the MA approximation and one on the boundary. Consequently, it provides a continuous map between the inner Voronoi based structure and the boundary of the shape, encompassing the topological structures of them both. This representation can also be seen as a partitioning of the volume between the two, where each element in the partition is either a tetrahedron or a pyramid and includes vertices from both the MA approximation and the reconstructed boundary.
Progressive Dimension-Independent Boolean Operations
(The Eurographics Association, 2004) Paoluzzi, A.; Pascucci, V.; Scorzelli, G.; Gershon Elber and Nicholas Patrikalakis and Pere Brunet
This paper introduces a new progressive multi-resolution approach for representating and processing polyhedral objects of any dimension. Our representation, a variant of BSP trees [Nay90] combined with the Split scheme introduced in [BP96], allows progressive streaming and rendering of solid models at multiple levels of detail (LOD). Boolean set operations are computed progressively by reading in input a stream of incremental refinements of the operands. Each refinement of the input is mapped immediately to a refinement of the output so that the result is also represented as a stream of progressive refinements. The computation of complex models results in a tree of pipelined processes that make continuous progress concurrently, so that coarse approximations of the final results are obtained nearly instantly, long before the input operands are fully processed. We demonstrate the practical effectiveness of this approach with models constructed with our prototype system.
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.
Tracing Surface Intersection with a Validated ODE System Solver
(The Eurographics Association, 2004) Mukundan, H.; Ko, K. H.; Maekawa, T.; Sakkalis, T.; Patrikalakis, N. M.; Gershon Elber and Nicholas Patrikalakis and Pere Brunet
This paper presents a robust method for tracing intersection curve segments between continuous rational parametric surfaces, typically rational polynomial parametric surface patches. The tracing procedure is based on a validated ordinary differential equation (ODE) system solver which can be applied, without substantial overhead, for transversal as well as tangential intersections. Application of the validated ODE solver in the context of eliminating the phenomenon of straying and looping is discussed. In addition, we develop a method to fulfill the condition of a continuous gap-free boundary with a definite numerically verified upper bound for the intersection curve error in parameter space and is further mapped to an upper bound for the intersection curve error in 3D model space, which assists in defining well-formed boundary representation models of complex 3D solids.
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.
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.
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.
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.

Browse

Browsing Solid Modeling by Issue Date

Results Per Page

Sort Options