Automated Analysis of Acquired Geometry Through Sampled Distances

M. Freytag
Technical Report, Spatial Automation Lab, University of Wisconsin-Madison
Finite Elements in Analysis and Design

We describe a significant extension of the Finite element method (FEM) that allows Finite element analysis (FEA) to be performed in situ, on a native geometric representation of a solid domain. The proposed method, called Scan&Solve, is a particular implementation of the solution structure method (SSM) that builds on the classical ideas of Kantorovich and Rvachev. It can be applied to any geometric model and used within any geometric modeling system that supports two fundamental queries: point membership testing and distance to boundary computation. The advantages of this approach include unmatched flexibility in handling geometric errors, small features, complex boundary conditions, and interfaces, while maintaining most of the benefits of classical FEA. This paper describes the technical background behind the proposed method, compares it to classical FEA formulation, details its implementation, and demonstrates its advantages.

M. Freytag, V. Shapiro, and I. Tsukanov
Technical Report, Spatial Automation Lab, University of Wisconsin-Madison
Group Morphology with Convolution Algebras

Group morphology is an extension of mathematical morphology with classical Minkowski sum and difference operations generalized respectively to Minkowski product and quotient operations over arbitrary groups. We show that group morphology is a proper setting for unifying, formulating and solving a number of important problems, including translational and rotational configuration space problems, mechanism workspace computation, and symmetry detection. The proposed computational approach is based on group convolution algebras, which extend classical convolutions and the Fourier transform to non-commutative groups. In particular, we show that all Minkowski product and quotient operations may be represented implicitly as sublevel sets of the same real-valued convolution function.

M. Lysenko, S. Nelaturi, and V. Shapiro
Symposium of Solid Modeling, 2010

This paper has been expanded, revised with corrections, and sent for review at the Journal of Computer Aided Geometric Design. See M. Lysenko, S. Nelaturi, and V. Shapiro, Non-commutative Morphology: Shapes, Filters, and Convolutions, Computer Aided Geometric Design: Special Issue, Solid and Physical Modeling 2011. Under review.
Configuration Products and Quotients in Geometric Modeling

The six-dimensional space SE(3) is traditionally associated with the space of configurations of a rigid solid (a subset of Euclidean three-dimensional space R3). But a solid itself can be also considered to be a set of configurations, and therefore a subset of SE(3). This observation removes the artificial distinction between shapes and their configurations, and allows formulation and solution of a large class of problems in mechanical design and manufacturing. In particular, the configuration product of two subsets of configuration space is the set of all configurations obtained when one of the sets is transformed by all configurations of the other. The usual definitions of various sweeps, Minkowski sum, and other motion related operations are then realized as projections of the configuration product into R3. Similarly, the dual operation of configuration quotient subsumes the more common operations of unsweep and Minkowski difference. We identify the formal properties of these operations that are instrumental in formulating and solving both direct and inverse problems in computer aided design and manufacturing. Finally, we show that all required computations may be approximated using a fast parallel sampling method on a GPU and provide error estimates for the approximation.

S. Nelaturi, V. Shapiro
Computer-Aided Design: Special Issue on Solid And Physical Modeling Symposium, 2009

A preliminary version of this paper appears in the Proceedings of the 2009 ACM Symposium on Solid and Physical Modeling “Configuration Products in Geometric Modeling”
Discrete Physics using Metrized Chains

Over the last fifty years, there have been numerous efforts to develop comprehensive discrete formulations of geometry and physics from first principles: from Whitney’s geometric integration theory to Harrison’s theory of chainlets, including Regge calculus in general relativity, Tonti’s work on the mathematical structure of physical theories and their discrete formulation, plus multifarious researches into so-called mimetic discretization methods, discrete exterior calculus, and discrete differential geometry. All these approaches strive to tell apart the different mathematical structures—topological, differentiable, metrical—underpinning a physical theory, in order to make the relationships between them more transparent. While each component is reasonably well understood, computationally effective connections between them are not yet well established, leading to difficulties in combining and progressively refining geometric models and physics-based simulations. This paper proposes such a connection by introducing the concept of metrized chains, meant to establish a discrete metric structure on top of a discrete measure-theoretic structure embodied in the underlying notion of measured (real-valued) chains. These, in turn, are defined on a cell complex, a finite approximation to a manifold which abstracts only its topological properties.

A. DiCarlo, F. Milicchio, A. Paoluzzi, and V. Shaprio
2009 SIAM/ACM Joint Conference on Geometric and Physical Modeling

Construction of Distance Field Based Representations of Material Properties

A. Biswas
Technical Report, Spatial Automation Lab, University of Wisconsin-Madison

Geometrically Adaptive Numerical Integration

Numerical integration over solid domains often requires geometric adaptation to the solid’s boundary. Traditional approaches employ hierarchical adaptive space decomposition, where the integration cells intersecting the boundary are either included or discarded based on their position with respect to the boundary and/or statistical measures. These techniques are inadequate when accurate integration near the boundary is particularly important. In boundary value problems, for instance, a small error in the boundary cells can lead to a large error in the computed field distribution. We propose a novel technique for exploiting the exact local geometry in boundary cells. A classification system similar to marching cubes is combined with a suitable parameterization of the boundary cell’s geometry. We can then allocate integration points in boundary cells using the exact geometry instead of relying on statistical techniques. We show that the proposed geometrically adaptive integration technique yields greater accuracy with fewer integration points than previous techniques.

B. Luft, V. Shapiro, I. Tsukanov
2008 ACM Symposium on Solid and Physical Modeling

Feasible Spaces in Weld Gun Selection

S. Nelaturi, A. Abhyankar, V. Shapiro, and R. Tilove
IEEE Conference on Automation Science and Engineering, 2008

Spatial Characterization of Reconfigurable Devices

S. Nelaturi, V. Shapiro

Shape Optimization Using Constructive Representations

J. Chen
Ph.D. Thesis, Computer Science Department, University of Wisconsin, Madison, December 2007

Validation and Translation of Epsilon-Solids

J. Qi, Ph.D. Thesis
Mechanical Engineering Department, University of Wisconsin, Madison, October 2007
Optimization of Continuous Heterogeneous Models

A heterogeneous model consists of a solid model and a number of spatially distributed material attributes. Much progress has been made in developing methods for construction, design, and editing of such models. We consider the problem of optimization of a heterogeneous model, and show that its representation by a continuous function de¯ned over a constructively represented domain naturally leads to simple and e®ective optimization procedures. Using minimum compliance optimization problem as an example, we show that the design sensitivities are directly obtainable in terms of material and geometric parameters, which can be used in any standard gradient-based optimization procedures. The proposed approach allows both local control of the material properties and global control of geometric variations, and can be used with many existing techniques for material modeling. Numerical experiments are given to demonstrate these representational advantages.

J. Chen, V. Shapiro
Technical Report, Spatial Automation Lab, University of Wisconsin-Madison
Scan and Solve: Acquiring the Physics of Artifacts

Existing physical artifacts including sculpture, mechanical parts, and anatomical structures are commonly acquired by modern surface and volumetric scanning technologies for archival, visualization, and diagnostic purposes. While the native representations for such data are largely sufficient for visualization purposes, more advanced field simulation currently requires extensive manual conversions into simplified surface and volume meshes compatible with the traditional finite element analysis pipeline. These conversions are tedious, error-prone, and require expertise in the mesh construction process. We demonstrate automated field simulation on acquired artifacts, bypassing the di±cult geometric and topological meshing problems through a meshfree paradigm based on approximate distance fields computed from the native acquired data through sampling.

M. Freytag, V. Shapiro, I. Tsukanov
Proceedings of the ASME 2007 International Design Engineering Technical Conferences & Computers and Information in Engineering Conference, September 4-7, 2007, Las Vegas, USA.

Differentiable Distance Fields from Scanned Data

M. Freytag, V. Shapiro, and I. Tsukanov
Technical Report, March 2007

Semi-Analytic Geometry with R-functions

V. L. Rvachev called R-functions \logically-charged functions” because they encode complete logical information within the standard setting of real analysis. He invented them in the 1960s as a means for unifying logic, geometry, and analysis within a common computational framework { in an e®ort to develop a new computationally e®ective language for modeling and solving boundary value problems. Over the last forty years, R-functions have been accepted as a valuable tool in computer graphics, geometric modeling, computational physics, and in many areas of engineering design, analysis, and optimization. Yet, many elements of the theory of R-functions continue to be rediscovered in di®erent application areas and special situations. The purpose of this survey is to expose the key ideas and concepts behind the theory of R-functions, explain the utility of R-functions in a broad range of applications, and to discuss selected algorithmic issues arising in connection with their use.

V. Shapiro
ACTA Numerica, Volume 16, 2007, pages 239-303
Solid and Physical Modeling with Chain Complexes

In this paper we show that the (co)chain complex associated with a decomposition of the computational domain, commonly called a mesh in computational science and engineering, can be represented by a block-bidiagonal matrix that we call the Hasse matrix. Moreover, we show that topology-preserving mesh refinements, produced by the action of (the simplest) Euler operators, can be reduced to multi-linear transformations of the Hasse matrix representing the complex. Our main result is a new representation of the (co)chain complex underlying field computations, a representation that provides new insights into the transformations induced by local mesh refinements. This paper is a further contribution towards bridging the subject of computer representations for solid and physical modeling—which flourished border-line between computer graphics, engineering mechanics and computer science with its own methods and data structures—under the general cover of linear algebra and algebraic topology. The main advantage of such an approach is that topology, geometry and physics may coexist in one and the same formalized framework, concurring together to define, represent and simulate the behavior of the model. Our approach is based on first principles and is general in that it applies to most representational domains that can be characterized as cell complexes, without any restrictions on their type, dimension, codimension, orientability, manifoldness, connectedness. Contrary to what might appear at first sight, the theoretical complexity of the present approach is not greater than that of current methods, provided that sparse-matrix techniques with double element access (by rows and by columns) are employed. Last but not least, our tensorbased approach is a significant step forward in achieving close integration of geometrical representations and physics-based simulations, i.e., in the concurrent modeling of shape and behavior.

A. DiCarlo, F. Milicchio, A. Paoluzzi, and V. Shapiro
Proceedings of the 2007 ACM Symposium on Solid and Physical Modeling, Beijing, China, June 4-6, 2007.

Shape Sensitivity of Constructive Representations

Most solid models are archived using boundary representations, but they are created, edited, and optimized using high level constructive methods that rely on parameterized Boolean set operations and feature-based techniques. Downstream applications often require optimization of integral-valued performance measures over such models that include volume, mass, and energy properties, as well as more general distributed fields (stress, temperature, etc.). A key computational utility in all such applications is the computation of the sensitivity of the performance measure with respect to the parameters in the solid’s construction history. We show that for a class of performance measures defined as domain integrals, the sensitivity with respect to a parameter requires integration over a subset of the solid’s boundaries that is affected by that parameter. In contrast to earlier methods, the proposed approach for computing sensitivities does not require solid’s boundary to remain homeomorphic, and may be used with most types of constructive representations, including CSG and feature-based representations, where the defining Boolean expression may not be known. Simplicity and effectiveness of the proposed technique are illustrated on several common shape optimization problems.

J. Chen, M. Freytag, V. Shapiro
Proceedings of the 2007 ACM Symposium on Solid and Physical Modeling, Beijing, China, June 4-6, 2007.

A Codimension-Zero Approach to Discretizing and Solving Field Problems

Computational science and engineering are dominated by field problems. Traditionally, engineering practice involves repeated iterations of shape design (i.e., shaping and modeling of material properties), simulation of the physical field, evaluation of the result, and re-design. In this paper, we propose a specific interpretation of the algebraic topological formulation of field problems, which is conceptually simple, physically sound, computational effective and comprehensive. In the proposed approach, physical information is attached to an adaptive, full-dimensional decomposition of the domain of interest. Giving preeminence to the cells of highest dimension allows us to generate the geometry and to simulate the physics simultaneously. We will also demonstrate that our formulation removes artificial constraints on the shape of discrete elements and unifies commonly unrelated methods in a single computational framework. This framework, by using an efficient graph-representation of the domain of interest, unifies several geometric and physical finite formulations, and supports local progressive refinement (and coarsening) effected only where and when required.

F. Milicchio, A. DiCarlo, A. Paoluzzi and V. Shapiro
Technical Report, September 2007

Adaptive Multiresolution Refinement With Distance Fields

This paper describes a multiresolution approach to field modeling that can be used with any meshfree or mesh based method for adaptive solution refinement. The refined solution is represented as a superposition of a coarse (unrefined) solution and a sequence of refinements that provide additional degrees of freedom with higher spatial or functional resolution. Each refinement is treated as a solution to a boundary value problem within a specified refinement window. The proposed approach is based on the meshfree method with distance fields and guarantees Cm continuity of the refined solutions with matching or non-matching grids. The method does not restrict the shape of the refinement window and does not place any constraints on the type of basis functions, or relative position and resolution of the refinement grids. Combining the proposed approach with hierarchical space decompositions and a posteriori error estimators results in an effective tool for automatic solution refinement. Carefully chosen numerical examples illustrate the power and advantages of the proposed approach.

I. Tsukanov and V. Shapiro
International Journal of Numerical Methods in Engineering, accepted for publication, 2007.

Homotopy conditions for tolerant geometric queries

Algorithms for many geometric queries rely on representations that are comprised of combinatorial (logical, incidence) information, usually in a form of a graph or a cell complex, and geometric data that represents embeddings of the cells in the Euclidean space Ed. Whenever geometric embeddings are imprecise, their incidence relationships may become inconsistent with the associated combinatorial model. Tolerant algorithms strive to compute on such representations despite the inconsistencies, but the meaning and correctness of such computations have been a subject of some controversy. This paper argues that a tolerant algorithm usually assumes that the approximate geometric representation corresponds to a subset of Ed that is homotopy equivalent to the intended exact set.We show that the Nerve Theorem provides systematic means for identifying sufficient conditions for the required homotopy equivalence, and explain how these conditions are used in the context of geometric and solid modeling.

V. Shapiro
Proceedings of the Dagstuhl Workshop on Reliable Implementation of Real Number Algorithms: Theory and Practice, January 2006 (to be published in LNCS by Springer)

Shape Optimization with Topological Changes and Parametric Control

Recent advances in shape optimization rely on free-form implicit representations, such as level sets,to support boundary deformations and topological changes. By contrast, parametric shape optimization is formulated directly in terms of meaningful geometric design variables, but usually does not support free-form boundary and topological changes. We propose a novel approach to shape optimization that combines and retains the advantages of the earlier optimization techniques. The shapes in the design space are represented implicitly as level sets of a higher-dimensional function that is constructed using B-splines (to allow free-form deformations), and parameterized primitives combined with R-functions (to support desired parametric changes). Our approach to shape design and optimization offers great flexibility because it provides explicit parametric control of geometry and topology within a large space of free-form shapes. The resulting method is also general in that it subsumes most other types of shape optimization as special cases. We describe an implementation of the proposed technique with attractive numerical properties. The explicit construction of an implicit representation supports straightforward sensitivity analysis that can be used with most gradient-based optimization methods. Furthermore, our implementation does not require any error-prone polygonization or approximation of level sets (isocurves and isosurfaces). The effectiveness of
the method is demonstrated by several numerical examples.

J. Chen, V. Shapiro, K. Suresh, and I. Tsukanov
International Journal of Numerical Methods in Engineering, Volume 71, No 3, 2007, pages 313-346.

A short version appears as Paper DETC2006-99612, Proceedings of 32nd Design Automation Conference, ASME International Design Engineering Technical Conferences, September 10-13, 2006, Philadelphia, Pennsylvania. Won the Best Paper Award.