2000 

Models and Representations for Parametric Family of Parts


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://salcnc.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.


On Shaping Moving Mechanical Parts


Methods and Apparatus for Shaping Moving Geometric Shapes


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 semianalytic sets may be represented implicitly by real valued functions with guaranteed differential properties. Furthermore, such functions may be constructed automatically using the theory of Rfunctions. 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.

1999


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 kform may be represented by a formal kcochain over a cellular structure that we call a starplex, and exterior differentiation is equivalent to the coboundary operation on the corresponding kcochain. 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 wellsuited 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.


Completeness of RFM Solution Structures
The RFunction 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 Rfunctions (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.


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 motionrelated constraints. We show that all motionrelated 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 ndimensional 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 sweepbased modeling of moving parts, and provides improved computational support for mechanical shape design.

1998


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 signinvariant 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.


Implicit Functions with Guaranteed Differential Properties
Theory of Rfunctions provides the methodology for constructing exact implicit functions for any semianalytic 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 meshfree engineering analysis, motion planning, and scientific visualization.


Meshfree Simulation of Deforming Domains
Spatial discretization of the domain and/or boundary conditions prevents application of many numerical techniques to physical problems with timevarying geometry and boundary conditions. By contrast, the Rfunctions 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 timevarying geometries and boundary conditions.


A Common Structure for Models of Distributed Phenomena

1997


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 motionrelated 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 settheoretic 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.


A Convex Deficiency Tree Algorithm for Curved Polygons
Boolean set representations of curved twodimensional 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.


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 BRdeforming 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 BRdeformation 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.

1996


Implicit Function Modeling of Solidification in Metal Casting
Solidification of metal castings can be modeled by an implicit realvalued 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 Rfunctions 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.


UNSWEEP: Formulation and Computational Properties
We introduce and formally define a new geometric modeling operation unsweep(E;M) which, given an arbitrary ndimensional 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.


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 geometrybased 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.


WellFormed 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 settheoretic constructions are wellformed so that PMC amounts to evaluating a ternary logic expression and does not require any neighborhood computations. We demonstrate wellformedness 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. Wellformed 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, wellformed set representations can be trivially translated into representations of solids by realvalued implicit functions.

1995


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 highlevel, parameterized, and usermodifiable 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 welldefined. 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.


Maintenance of Geometric Representations Through Space Decompositions
The ability to transform between distinct geometric representations is the key to success of multiplerepresentation 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 $ brep 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.
