University of Wisconsin–Madison

2001-2005

2005
Single-set and class-of-sets semantics for geometric models

Two major approaches to defining the semantics of inaccurate boundary representations have been proposed in the literature. They are referred to here as single-set semantics, and class-of-sets semantics, respectively. Our description of the distinction between these two approaches focuses on the nature of the topological regularity on which they are based (classical regularity vs. o-regularity). It is shown in this note that both approaches may be useful, depending on what information is available. As an illustrative example, an elementary result is given, for a point-membership-classification algorithm, that is sufficiently general to be of practical interest but sufficiently special to be transparent.

J. Qi, V. Shapiro, N. F. Stewart
Computer Aided Design, Volume 38 (2006), pages 1088-1098
2004
Representation of Heterogeneous Material Properties in Core Product Model

Core Product Model (CPM) was developed at NIST as a high level abstraction for representing product related information, to support data exchange, in a distributive and a collaborative environment. In this paper, we extend the CPM to components with continuously varying material properties. Such components are becoming increasing important and popular due to progress in design, analysis and manufacturing techniques. The key enabling concept for modeling of continuously varying material properties is that of distance fields associated with a set of material features, where values and rates of material properties are specified. Material fields, representing distribution of material properties within a component, are usually expressed as functions of distances to material features, and are controlled with a variety of differential, integral or algebraic constraints. Our formulation is independent of any particular platform or representation, and applies to most proposed techniques for representing continuously varying material properties. The proposed model is described using system independent Unified Modeling Language (UML) and is illustrated through a number of specific examples.

A. Biswas, S. Fenves, V. Shapiro, and R. Sriram
Technical Report, December 2004.

Epsilon – Regular Sets and Intervals

Regularity of sets (both open and closed) is fundamental in the classical theory of solid modeling and is implicit in many shape modeling representations. However, strictly speaking, the notion of regularity cannot be applied to real world shapes and/or computed geometric models that usually exhibit irregularity in the forms or errors, uncertainty, and/or approximation. We propose a notion of regularity that quantities regularity of shapes in terms of set intervals and subsumes the classical notions of open and closed regular sets as special exact cases. Our formulation relies on topological operations that are related to, but are distinct from, the common morphological operations. We also show that regular interval is bounded by two sets, such that the Hausdorff distance between the sets, as well the Hausdorff distance between their boundaries, is at most “. Many applications of regularity include geometric data translation and solid model validation.

J. Qi, V. Shapiro
Proceedings of IEEE International Conference on Shape Modeling and Applications, 15-17 June 2005.

Epsilon-Solidity in Geometric Data Translation

Classical theory of solid modeling relies on the notion of regular sets and presupposes exactness in both geometric data and algorithms. In contrast, modeling, exchange and translation of geometric models in engineering applications usually involve data approximations and algorithms with different numerical precisions. We argue that an appropriate formulation of the geometric data translation problems requires finite size neighborhoods, leading to the notion of e-topological operations. These operations are then used to formulate the definitions of e-regularity and e-solidity that extend and subsume the corresponding classical concepts as exact special cases. The proposed theory allows systematic classification and investigation of problems in geometric data translation. In particular, it explains why the current methods for validity checking of boundary representations are neither necessary nor sufficient for maintaining e-solidity in the presence of numerical inaccuracies, whereas geometric healing procedures may be avoided in many common situations. Furthermore, the proposed theory suggests how the classical solid modeling paradigm should be extended in order to deal with the outstanding problems in geometric robustness, validation, and data translation.

J. Qi, V. Shapiro
Technical Report, June 2004.

Published in two parts:

Part1: “Epsilon-Topological Formulation of Tolerant Solid Modeling” in Computer-Aided Design, Vol 38, No 4, April 2006


Part2: “Geometric Interoperability with epsilon-solidity” in Transactions of ASME, Journal of Computing and Information Science in Engineering, Vol. 6, No. 3, September 2006.

Field Modeling with Sampled Distances

Traditional mesh-based approaches to the modeling and analysis of physical fields within geometric models require some form of topological reconstruction and conversion in the mesh generation process. Such manipulations tend to be tedious and error-prone manual processes that are not easily automated. We show that most field problems may be solved directly by using approximate distance fields computed from designed or sampled geometric data, thus avoiding many of the difficult reconstruction and meshing problems. With distances we can model fields that satisfy boundary conditions while approximating the governing differential equations to arbitrary precision. Because the method is based on sampling, it provides natural control for multi-resolution both in geometric detail of the domain and in accuracy of the computed physical field. We demonstrate the field modeling capability with several heat transfer applications, including a typical transient problem and a “scan and solve” approach to the simulation of a physical field in a real-world artifact.

M. Freytag, V. Shapiro, and I. Tsukanov
Computer Aided Design, Volume 38, Issue 2, February 2006, Pages 87-100.
2003
Meshfree Modeling and Analysis of Physical Fields in Hetrogeneous Media

Continuous and discrete variations in material properties lead to substantial difficulties for most mesh-based methods for modeling and analysis of physical fields. The meshfree method described in this paper relies on distance fields to boundaries and to material features in order to represent variations of material properties as well as to satisfy prescribed boundary conditions. The method is theoretically complete in the sense that all distributions of physical properties and all physical fields are represented by generalized Taylor series expansions in terms of powers of distance fields. We explain how such Taylor series can be used to constructsolution structures – spaces of functions satisfying the prescribed boundary conditions exactly and containing the necessary degrees of freedom to satisfy additional constraints. Fully implemented numerical examples illustrate the effectiveness of the proposed approach.

I. Tsukanov, V. Shapiro
Journal of Advances in Computational Mathematics, Volume 23 (2005), Number 1-2, pp. 95-124, 2005.

Equivalence Classes for Shape Synthesis of Moving Mechanical Parts

Moving parts in contact have been traditionally synthesized through specialized techniques that focus on completely specified nominal shapes. Given that the functionality does not completely constrain the geometry of any given part, the design process leads to arbitrarily specified portions of geometry, without providing support for systematic generation of alternative shapes satisfying identical or altered functionalities. Hence the design cycle of a product is forced to go into numerous and often redundantiterative stages that directly impact its efiectiveness. We argue that the shape synthesis of mechanical parts is more eficient and less error prone if it is based on techniques that identify the functional surfaces of the part without imposing arbitrary restrictions on its geometry. We demonstrate that such techniques can be formally defined for parts moving in contact through equivalence classes of mechanical parts that satisfy a given functionality. We show here that by replacing the completely specified geometry of the traditional approaches with partial geometry and functional specification, we can formally define classes of mechanical parts that are equivalent, in the sense that all members of the class satisfy the same functional specifications. Moreover, these classes of functionally equivalent parts are computable, may be represented unambiguously by maximal elements in each class, and contain all other functional designs that perform the same function.

H. Ilies, V. Shapiro
ASME/ACM Journal of Computing and Information Science in Engineering, Vol. 4, No. 3, March 2003, pp 20-27.

B-rep SE: Simplicially Enhanced Boundary Representation

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.

M. Freytag, V. Shapiro
Proceedings of International Convention on Shapes and Solids, June 2004.

Combinatoral Laws for Physically Meaningful Design

A typical computer representation of a design includes geometric and physical information organized in a suitable combinatorial data structure. Queries and transformations of these design representations are used to formulate most algorithms in computational design, including analysis, optimization, evolution, generation, and synthesis. Formal properties, and in particular existence and validity of the computed solutions, must be assured and preserved by all such algorithms. Using tools from algebraic topology, we show that a small set of the usual combinatorial operators: boundary (?), coboundary (d), and dualization (??) – are sufficient to represent a variety of physical laws and invariants. Specific examples include geometric integrity, balance and equilibrium, and surface smoothing. Our findings point a way toward systematic development of data structures and algorithms for design in a common formal computational framework.

V. Ramaswamy, V. Shapiro
ASME/ACM Journal of Computing and Information Science in Engineering, Vol. 4, No. 3, March 2004, pp 3-10.

Appeared as Paper DETC2003/DTM-48654 in Proceedings of 15th International Conference on Design Theory and Methodology, ASME Design Technical Conferences, September 2-6, 2003 Chicago, Illinois. Won the Best Paper Award
2002

The ABC`s of an Interactive Physics System

J. Chard
Ph.D. Thesis, Mathematics and Computation in Engineering, Mechanical Engineering Department, University of Wisconsin, Madison, September 2002.

Data Structure and Algorithms for Fast Automatic Differentiation

In this paper we discuss the data structure and algorithms for the direct application of generalized Leibnitz rules to the numerical computation of partial derivatives in forward mode. The proposed data structure provides constant time access to the partial derivatives, which accelerates the automatic differentiation computations. The interaction among elements of the data structure is explained by several numerical examples. The paper contains analysis of the developed data structure and algorithms.

I. Tsukanov, M. Halli
Technical Report, July 2002.
Heterogeneous Material Modeling with Distance Fields

We propose a universal approach to the problem of computer modeling of shapes with continuously varying material properties satisfying prescribed material conditions on a finite collection of material features and global constraints. The central notion is a parameterization of space by distances from the material features – either exactly or approximately. Functions of such distances provide a systematic and intuitive means for modeling of desired material distributions as they arise in design, manufacturing, analysis and optimization of components with varying material properties. The proposed framework subsumes and generalizes a number of earlier proposals for heterogeneous material modeling. It is theoretically complete in the sense that it allows representation of all material property functions. We demonstrate that the approach can be implemented within the existing framework of solid modeling and its numerous advantages, including: precise and intuitive control using explicit, analytic, differential, and integral constraints specified on the native geometry; guaranteed smoothness and analytic properties without meshing; and applicability to material features of arbitrary dimension, shape, and topology.

A. Biswas, I. Tsukanov, V. Shapiro
Computer-Aided Geometric Design, Vol. 21, 2004, pp 215-242.
The Architecture of SAGE – A Meshfree System Based on RFM

In a meshfree system, a geometric model of a domain neither conforms to, nor is restricted by a spatial discretization. Such systems for engineering analysis offer numerous advantages over the systems that are based on traditional mesh-based methods, but they also requires radical approaches to enforcing boundary conditions and novel computational tools for differentiation, integration, and visualization of fields and solutions. We show that all of these challenges can be overcome, and describe SAGE (Semi-Analytic Geometry Engine) – a successful system specifically intended for meshfree engineering analysis. Our approach and individual modules are based on Rvachev’s Function Method (RFM) but the described techniques, algorithms, and software are applicable to all mesh-based and meshfree methods and have broad use beyond solutions of boundary value problems.

I. Tsukanov, V. Shapiro
In Engineering with Computers, Vol. 18, No. 4, 2002, pp. 295-311.

Topological Framework for Part Families

One of the fundamental unsolved problems in geometric design of mechanical solids has been the lack of a proper notion of family or class. Numerous heuristic and often incompatible definitions are used throughout the CAD industry, and it is usually not clear how to generate members of a family or, to decide if a given object belongs to an assumed family. Until these difficulties are resolved, no guarantees or standards for parametric modeling are possible, and all efforts to allow exchange of parametric representations between different CAD systems are likely to remain futile. Standardizing on a particular definition may be difficult, because parametric families depend intrinsically not only on shape but also on its representation. We classify families into parameter-space and representation-space, and show that both types are representation-induced families. We propose a formal framework for families based on the notion of topological categories. Every parametric family is defined by the representation-induced topological space of solids that are closed under the continuous maps in the assumed topology. We illustrate several well defined families and formally define a special but important case of CSGinduced family that generalizes to the more general case of feature-induced families.

S. Raghothama, V. Shapiro
ASME Transactions, Journal of Computing and Information Science in Engineering Vol. 2, December 2002, pp. 246-255.

A preliminary version appeared in – Proceedings of the Seventh ACM Symposium on Solid Modeling and Applications, Saarbrücken, Germany, June 2002.
A Meshfree Method for Incompressible Fluid Dynamics Problems

We show that meshfree variational methods may be utilized for solution of incompressible fluid dynamics problems using the R-function method (RFM). The proposed approach constructs an approximate solution that satisfies all prescribed boundary conditions exactly using approximate distance fields for portions of the boundary, transfinite interpolation, and computations on a non-conforming spatial grid. We give detailed implementation of the method for two common formulations of the incompressible fluid dynamics problem: first using scalar stream function formulation and then using vector formulation of the Navier-Stokes problem with artificial compressibility approach. Extensive numerical comparisons with commercial solvers and experimental data for the benchmark back-facing step channel problem reveal strengths and weaknesses of the proposed meshfree method.

I. Tsukanov, V. Shapiro, S. Zhang
International Journal for Numerical Methods in Engineering, Volume 58, Number 1, 2003, pp. 127-158.
2001
Approximate Distance Fields with Non-Vanishing Gradients

For a given set of points S, a Euclidean distance field is defined by associating with every point p of Euclidean space Ed a value that is equal to the Euclidean distance from to S. Such distance fields have numerous computational applications, but are expensive to compute and may not be sufficiently smooth for some applications. Instead, popular implicit modeling techniques rely on various approximate fields constructed in a piecewise manner. All such constructions lead to sacrifices in distance properties that have not been properly studied or characterized. We show that the quality of an approximate distance field may be characterized locally near the boundary by its order of normalization and can be studied in terms of the field derivatives. The approach allows systematic quantitative assessment and comparison of various construction methods. In particular, we provide detailed analysis of several popular field construction methods that rely on set decompositions and R-functions, as well as identify the key factors affecting the quality of the constructed fields.

A. Biswas, V. Shapiro
Graphical Models, Vol. 66, Issue 3, May 2004, pp 133-159.

Solid Modeling

Solid modeling is a consistent set of principles for mathematical and computer modeling of three-dimensional solids. The collection evolved over the last thirty years, and is now mature enough to be termed a discipline. Its major themes are theoretical foundations, geometric and topological representations, algorithms, systems, and applications. Solid modeling is distinguished from other areas in geometric modeling and computing by its emphasis on informational completeness, physical fidelity, and universality. This article revisits the main ideas and foundations of solid modeling in engineering, summarizes recent progress and bottlenecks, and speculates on possible future directions.

V. Shapiro
G. Farin, J. Hoschek, M.-S. Kim, eds, Handbook of Computer Aided Geometric Design, pages 473-518, Elsevier Science Publishers, 2001.

A Class of Forms from Function: The Case of Parts Moving in Contact

We consider the general problem of designing mechanical parts moving in contact under the influence of externally applied loads. Geometrically, the problem may be characterized in terms of a conjugate triplet which is formed by the two shapes moving in contact and their relative motion.We show that every such triplet belongs to one or more classes of functionally equivalent designs that may be represented uniquely by maximal triplets, corresponding respectively to the two largest contact shapes that are guaranteed to contain all other possible solutions to the contact design problem. In practical terms, the proposed characterization of the contact problem enables the systematic exploration of the design space using fully defined representatives of the functionally equivalent class of parts. Furthermore, such exploration may be performed using standard tools from geometric modeling, and without assuming any particular parametrization that necessarily restrict both the design space and possible computational techniques for exploring feasible designs. Because it supports generation of an essentially unlimited space of design solutions for a given contact problem, the proposed approach is particularly effective at the conceptual design stage.

H. Ilies, V. Shapiro
Research in Engineering Design, Vol. 13, No. 3, 2002, pp. 157-166.

A preliminary version appeared as technical paper DETC2001/DTM-21704 in Proceedings of DETC’01, ASME Design Theory and Methodology Conference, September 2001.