Search Results

Now showing 1 - 10 of 12
  • Item
    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.
  • Item
    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.
  • Item
    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.
  • Item
    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.
  • Item
    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.
  • Item
    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.
  • Item
    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.
  • Item
    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.
  • Item
    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.
  • Item
    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.