Models and Representations for Parametric Family of Parts

S. Raghothama
Ph.D. Thesis, Mechanical Engineering Department, University of Wisconsin, Madison, September 2000.

Fast Forward Automatic Differentiation Library (FADLIB)

In this document we discuss the data structure and algorithms for direct application of recursive chain rules to numerical computations of partial derivatives in forward mode. The proposed data structure providing constant time access to the partial derivatives accelerates the automatic differentiation computations. We implemented the presented algorithms in a software package, which simplifies automatic differentiation of functions represented by a computer program. The library is available for public use and can be downloaded from http://sal-cnc.me.wisc.edu. This manual contains detailed descriptions of all library functions and several examples illustrating the applications and usage of the proposed automatic differentiation software.

I. Tsukanov, M. Hill
User Manual, December 2000.

On Shaping Moving Mechanical Parts

H. Ilies
Ph.D. Thesis, Mechanical Engineering Department, University of Wisconsin, Madison, June 2000.

Methods and Apparatus for Shaping Moving Geometric Shapes

H. Ilies, V. Shapiro
United States Patent no. 6,044,306, March 2000.

  • For licensing information, please contact Prof. V. Shapiro.
Transfinite Interpolation Over Implicitly Defined Sets

In a general setting, the transfinite interpolation problem requires constructing a single function f(x) that takes on the prescribed values and/or derivatives on some collection of point sets. The sets of points may contain isolated points, bounded or unbounded curves, as well as surfaces and regions of arbitrary topology. All such closed semi-analytic sets may be represented implicitly by real valued functions with guaranteed differential properties. Furthermore, such functions may be constructed automatically using the theory of R-functions. We show that such implicit representations may be used to solve the general transfinite interpolation problem using a generalization of the classical inverse distance weighting interpolation for scattered data. The constructed interpolants may be used to approximate boundary value and smoothing problems in a meshfree manner.

V.L. Rvachev, T.I. Sheiko, I. Tsukanov and V. Shapiro
Computer-Aided Geometric Design, Vol. 18, (2001), pp. 195-220
A Multivector Data Structure for Differential Forms and Equations

We use tools from algebraic topology to show that a class of structural differential equations may be represented combinatorially and thus by a computer data structure. In particular, every differential k-form may be represented by a formal k-cochain over a cellular structure that we call a starplex, and exterior differentiation is equivalent to the coboundary operation on the corresponding k-cochain. Furthermore, there is a one to one correspondence between this model and the classical finite cellular model supported by the Generalized Stokes’ Theorem, and translation between the two models can be completely automated. Our results point the way to a common combinatorial and data structure well-suited for a physical modeling computer algebra that unifies finite and infinitesimal, symbolic and numeric, geometric and physical descriptions of distributed phenomena. We illustrate the advantages of our approach by a prototype interactive physics editor that uses the computer algebra to automatically translate intuitive geometrical/physical descriptions of balance conditions created by the user into the corresponding symbolic differential and integral equations.

J. A. Chard, V. Shapiro
Mathematics and Computers in Simulation 54 (2000), pp. 33-64.

Completeness of RFM Solution Structures

The R-Function Method (RFM) solution structure is a functional expression that satisfies all given boundary conditions exactly and contains some undetermined functional components. It is complete if there exists a choice of undetermined component that transform the solution structure into an exact solution. Such a structure was used by Kantorovich (Kantorovich and Krylov, 1958) and his students to solve boundary value problems with homogeneous boundary conditions on geometrically simple domains. RFM is based on the theory of R-functions (Rvachev, 1982) that allows construction of a set of functions vanishing on the boundary and can be applied to problems with arbitrarily complex domains and boundary conditions. The resulting solution method is essentially meshfree, in the sense that the spatial discretization no longer needs to conform to the geometry of the domain, and can be completely automated. This paper summarizes the main principles of RFM, proves its completeness, and presents numerical results for several simple test problems.

V.L. Rvachev, T.I. Sheiko, V. Shapiro, and I. Tsukanov
Computational Mechanics 25 (2000), pp. 305-316.

On Shaping with Motion

Mehanial parts are modeled as (predominantly rigid) solid shapes that may move in space in order to function, be manufactured (for example, machine or be machined), and be assembled or disassembled. While it is clear that such mechanical shapes are greatly influuenced by collision, interference, containment, and contact constraints through prescribed motions, the motion itself is usually not part of these shape models. This in turn leads to proliferation of computational methods for modeling and analysis of various motion-related constraints. We show that all motion-related constraints can be formulated and applied within the same computational framework that treats motion as an integral part of the model. Our approach relies on two computational utilities. The first one is the unsweep operation which, given an arbitrary n-dimensional subset of Euclidean space E and a general motion M, returns the largest subset of E that remains inside E under M. The second modeling utility is a disjoint decomposition of space induced by the operations of unsweep and the standard set operations. The proposed approach subsumes and unifies the traditional sweep-based modeling of moving parts, and provides improved computational support for mechanical shape design.

H. Ilies, V. Shapiro
ASME Transactions, Journal of Mechanical Design, vol. 122, no. 4, December 2000, pp. 567-574.
Consistent Updates in Dual Representation Systems

Dual representation systems rely on a parametric model to create and to manipulate the boundary representation of a solid. Parametric and boundary representations remain consistent if they continue to model the same solid, after updates applied to the parametric model and/or to the boundary representation. We consider the problem of verifying the consistency between the boundary representation and the CSG representation which is a restricted case of parametric representation. We determine the necessary and sufficient conditions for consistency of the two representations, identify the required computational utilities, and describe two implemented and tested algorithms. Our algorithms rely on sign-invariant space decompositions and can be used to verify consistency of other representations, including parametric definitions such as feature attachments. They could also be used to verify consistency of boundary and parametric representations in different systems, or corresponding representations in integrated modeling environments.

S. Raghotha, V. Shapiro
Computer-Aided Design, 32(8-9), Aug, 2000, pp: 463-477

A preliminary version of this paper appeared in Proceedings of the Fifth ACM Symposium on Solid Modeling and Applications, Ann Arbor, MI, June 1999. Won the Best Paper Award.
Implicit Functions with Guaranteed Differential Properties

Theory of R-functions provides the methodology for constructing exact implicit functions for any semi-analytic set. This paper systematically explores and compares the known constructions in terms of their differential properties and explains how such functions may be constructed automatically from CSG and boundary representations of solids. The constructed functions may be automatically differentiated and integrated and have many important applications in mesh-free engineering analysis, motion planning, and scientific visualization.

I. Tsukanov, V. Shapiro
Proceedings of the Fifth ACM Symposium on Solid Modeling and Applications, Ann Arbor, MI, June 1999.

Meshfree Simulation of Deforming Domains

Spatial discretization of the domain and/or boundary conditions prevents application of many numerical techniques to physical problems with time-varying geometry and boundary conditions. By contrast, the R-functions method (RFM) for solving boundary and initial value problems discretizes not the domain but the underlying functional space, while the prescribed boundary conditions are satisfied exactly. The clean and modular separation of geometric information from the numerical procedures results in a solution technique that is essentially meshfree and allows an almost effortless modification of geometrical shapes, boundary conditions, and the governing equations. We show that these properties of the RFM make it highly suitable for automated modeling and simulation of nonstationary physical problems with time-varying geometries and boundary conditions.

I. Tsukanov, V. Shapiro
Computer Aided Design 31 (1999), pp 459-471.

A Common Structure for Models of Distributed Phenomena

J. Chard
M.S. Thesis, Mechanical Engineering Department, University of Wisconsin, Madison, May 1998
The Dual of Sweep, Computer Aided Design

As an infinite union operation, sweep of a moving object through space is a powerful and natural addition to the Boolean set operations that incorporates motion-related information for the purposes of shaping, collision detection, and simulation of moving objects. Use of sweep has been hindered by limited computational support and by the fact that it is a `material growing’ operation, whereas many applications, such as interference elimination and mechanism design, appear to be better modeled by a `material removal’ operation. This paper formally defines a new geometric modeling operation of unsweep. Given an arbitrary subset E of Euclidean space and a general motion M, unsweep(E;M) returns the largest subset of E that remains inside the original E under M. When M is a translation, unsweep(E;M) naturally reduces to the standard Minkowski difference of E and the trajectory generated by the inverted motion ^M . In this sense, the operation of unsweep is a generalization of Minkowski difierence that corresponds to a `material removal’ operation, it can be also defined as an infinite intersection operation, and is the dual of sweep in a precise set-theoretic sense. We show that unsweep has attractive theoretical and computational properties, including a practical point membership test for arbitrary general motions. By duality, the established properties of unsweep extend to the general sweep operation and can be used to improve the computational support for general sweeps.

H. Ilies, V. Shapiro
Volume 31, Number 3, March 1999, pages 185-201.

A Convex Deficiency Tree Algorithm for Curved Polygons

Boolean set representations of curved two-dimensional polygons are expressions constructed from planar halfspaces and (possibly regularized) set operations. Such representations arise often in geometric modeling, computer vision, robotics, and computational mechanics. The convex deficiency tree (CDT) algorithm described in this paper constructs such expressions automatically for polygons bounded by linear and curved edges that are subsets of convex curves. The running time of the algorithm is not worse than O(n2 log n) and the size of the constructed expressions is linear in the number of polygon edges. The algorithm has been fully implemented for polygons bounded by linear and circular edges.

V. Shapiro
International Journal of Computational Geometry and Applications, Vol. 11, No. 2, 2001, pp 215-238.

Boundary Representation Deformation in Parametric Solid Modeling

One of the major unsolved problems in parametric solid modeling is a robust update (regeneration) of the solid’s boundary representation, given a specified change in the solid’s parameter values. The fundamental difficulty lies in determining the mapping between boundary representations for solids in the same parametric family. Several heuristic approaches have been proposed for dealing with this problem, but the formal properties of such mappings are not well understood. We propose a formal definition for Boundary Representation (BR-)deformation for solids in the same parametric family, based on the assumption of continuity: small changes in solid parameter values should result in small changes in the solid’s boundary representation, which may include local collapses of cells in the boundary representation. The necessary conditions that must be satisfied by any BR-deforming mappings between boundary representations are powerful enough to identify invalid updates in many (but not all) practical situations, and the algorithms to check them are simple. Our formulation provides a formal criterion for the recently proposed heuristic approaches to persistent naming,” and explains the difficulties in devising sufficient tests for BR-deformation encountered in practice. Finally, our methods are also applicable to more general cellular models of pointsets and should be useful in developing universal standards in parametric modeling.

S. Raghothama, V. Shapiro
ACM Transactions on Graphics, vol. 17, no. 4, Oct. 1998, pp 259-286.
Implicit Function Modeling of Solidification in Metal Casting

Solidification of metal castings can be modeled by an implicit real-valued function whose behaviour is determined by physical parameters prescribed on the boundary of a casting. We show hwo to construct such funtions using theory of R-functions for two dimensional castings represented by their boundaries. The parameterized form of the constructed functions is convenient for studying, controlling, and optimizing their behaviour in terms of the physical paramters specified on the boundary of casting. The proposed approach can also be used for modelling multiple cavities in a same sand mold, generalizes to three dimensional castings, and is applicable to other physical phenomena that maybe suitable for analysis based on empirical knowledge.

V.L. Rvachev, T.I. Sheiko, V. Shapiro, and J.J Uicker
ASME Transactions, Journal of Mechanical Design, Vol. 119, No. 4, December 1997, pp 466-473.
UNSWEEP: Formulation and Computational Properties

We introduce and formally define a new geometric modeling operation unsweep(E;M) which, given an arbitrary n-dimensional subset of Euclidean space E and a general motion M, returns the subset of E that remains inside E under M. This new operation is dual to the usual sweeping operation and has important applications in mechanical design. When M is a translation, unsweep(E;M) naturally reduces to the usual Minkowski difference of E and the trajectory generated by the inverted motion ^M : We show that unsweep has attractive computational properties and give a practical point membership test for arbitrary general motions. By duality, the established properties of unsweep can be used to develop a practical point membership test for general sweeps.

H. Ilies, V. Shapiro
Proceedings of the 4th ACM Symposium on Solid Modeling and Applications.
An Approach to Systematic Part Design

The rise of solid modeling as a principal medium for mechanical product description can be traced to the requirement of informational completeness of geometric representations. Unfortunately, traditional geometry-based systems do not contain important information needed for many engineering activities and tend to force costly iterations in a product development cycle. We seek to understand spatial properties and combinatorial structure of mechanical parts in terms of simple interacting constructs related to part functionality and manufacturing processes. Existence of such a structure is illustrated for a simple part that is characterized in terms of its kinematics, strength, spatial containment, and manufacturing characteristics. The resulting explicit representation of correspondence between mechanical characteristics and spatial elements allows systematic product development, efficient modification procedures, and rational tolerancing approaches { eliminating many costly errors and iterations in a product development cycle. The study also highlights the lack of and the need for formal models supporting systematic design process.

H. Illies, V. Shapiro
Proceedings of the 5th IFIP WG5.2 Workshop on Geometric Modeling in CAD, May 19-23, 1996, Airlie, Virginia.
Well-Formed Set Representations of Solids

All Point Membership Classification (PMC) algorithms on solids constructed using regularized set operations require representing and computing neighborhoods of a point with respect to the represented solid. Such computations involve some of the more sensitive and difficult algorithms in solid modeling. We establish the necessary and sufficient conditions under which set-theoretic constructions are well-formed so that PMC amounts to evaluating a ternary logic expression and does not require any neighborhood computations. We demonstrate well-formedness of any monotone set expression whose primitives form a simple arrangement in Ed, and of common representations for polyhedral objects constructed using `decreasing convex hull’ algorithms. Well-formed representations exist for every solid but not for every fixed collection of primitives. We also give a necessary and sufficient test for existence of such representations. Identifying and eliminating neighborhood computations whenever possible should lead to simpler, more efficient, and robust geometric algorithms that are also more suitable for hardware implementation. Finally, well-formed set representations can be trivially translated into representations of solids by real-valued implicit functions.

V. Shapiro
International Journal of Computational Geometry and Applications, Volume 9, Number 2, 1999, pages 125–150.
What is a Parametric Family of Solids?

Classical solid modeling systems are being rapidly replaced by new parametric solid modeling systems, where solid models are defined and manipulated through high-level, parameterized, and user-modifiable definitions. We show that such parametric solid modeling systems inherited the unsolved technical problems of earlier dual representation (boundary and CSG) systems which may limit their functionality and performance. In particular, the modern systems may not robustly support parametric and variational modeling, because the meaning of a parametric family” is not always well-defined. We investigate existing practices in parametric modeling, discuss corresponding mathematical models and limitations of parametric families, and explore technical difficulties that must be resolved to take full advantage of parametric solid modeling.

D. L. Vossler and V. Shapiro
Proceedings of the 3rd ACM/IEEE Symposium on Solid Modeling and Applications, Salt Lake City, Utah, May 17-19, 1995.

Maintenance of Geometric Representations Through Space Decompositions

The ability to transform between distinct geometric representations is the key to success of multiple-representation modeling systems. But the existing theory of geometric modeling does not directly address or support construction, conversion, and comparison of geometric representations. A study of classical problems of CSG $ b-rep conversions, CSG optimization, and other representation conversions suggests a natural relationship between a representation scheme and an appropriate decomposition of space. We show that a hierarchy of space decompositions corresponding to different representation schemes can be used to enhance the theory and to develop a systematic approach to maintenance of geometric representations.

V. Shapiro
International Journal of Computational Geometry and Applications, Vol. 6, No. 4, 1997, pp 383-418.