University of Wisconsin–Madison

Older


Real Functions for Representation of Rigid Solids

A range of values of a real function f : Ed + Iw can be used to implicitly define a subset of Euclidean space Ed. Such “implicit functions” have many uses in geometric and solid modeling. This paper focuses on the properties and construction of real functions for the representation of rigid solids (compact, semi-analytic, and regular subsets of Ed). We review some known facts about real functions defining compact semi-analytic sets, and their applications. The theory of R-functions developed in (Rvachev, 1982) provides means for constructing real function representations of solids described by the standard (non-regularized) set operations. But solids are not closed under the standard set operations, and such real function representations are rarely available in modem solid modeling systems. More generally, assuring that a real function f represents a regular set may be difficult. Until now, the regularity has either been assumed, or treated in an ad hoc fashion. We show that topological and extremal properties of real functions can be used to test for regularity, and discuss procedures for constructing real functions with desired properties for arbitrary solids.

V. Shapiro
Computer-Aided Geometric Design, Vol. 11, No. 2, 1994.

Chain Models of Physical Behavior for Engineering Analysis and Design

The relationship between geometry(form) and physical behaviour(function) dominates many engineering activities. The lack of uniform and rigouros computational models for this relationship has resulted in a plethora of inconsistent(and thus usually incompatibe) computer aided design (CAD) tools and systems, causing unreasonable overhead in time, effort, and cost, and limiting to the extent to which CAD tools are used in practice. It seems clear that the formulization of the relationship between form and function is a prerequiste to taking full advantage of computers in automating design and analysis of engineering systems. We present a unified computational model of physical behaviour that explcitly links geometric and physical representations. The proposed approach characterizes physical systems in terms of their algebraic-topological properties: cell complexes, chains and, operations on them.

R. S. Palmer, V. Shapiro
Research in Engineering Design, Vol. 5, No. 3, 1994.

  • Invited paper for the special issue in Advances in Representations and Reasoning for Mechanical CAD.
Separation for Boundary to CSG Conversion

Important applications of b-rep – CSG conversion arise in solid modeling, image processing, and elsewhere. In addition, the problem is of considerable theoretical interest. One of the most difficult steps in performing b-rep ~ CSG conversion for a curved solid object consists of determining o set of half-spaces that is sufficient for a CSG representation of the solid. This usually requires the construction of additional half-spaces whose boundaries do not contribute to the boundary of the solid. Such half-spaces are called separating half-spaces because their purpose is to separate certain subsets inside the solid from those outside of the solid, Construction of separating half-spaces is specific to a particular geometric domain, but several generic approaches are possible. We use the information present in the boundary of the solid being converted to study the constraints on the degree of separating half-spaces, and show that a suff]cicnt set of linear separating half-spaces exists for any solid whose boundary contains only planar edges. A compl[,te construction is given for solids whose faces lie in convex surfaces. Separation for more L,cneral solids, whose b-rep includes othm surfaces and nonplanar edges, is alsa discussed, but this general problem remains poorly understood. We apply the boundary-based separation to solids hounded by genera] quadric surfaces, Specifically, we prove that a sufficient set of linear separating half-spaces exists for any such solid and consider the required constructions in several common situations. The presented results allowed a successful implementation of an experimental b-rep + CSW conversion system that converts natural quadric b-reps in Parasolid to efficient CSG representations in PADL-2

V. Shapiro, D. L. Vossler
ACM Transactions on Graphics, January 1993.

Efficient CSG Representations of 2-Dimensional Solids

Good methods are known for converting a Constructive Salid–Geometry (CSG) representation of a solid into a boundary representation (b-rep) of the solid, but not for performing the inverse conversion, b-rep- CSG, which is the subject of this paper. Important applications of b-rep-CSG conversion arise in solid modeling, image processing, and elsewhere. The problem can be divided into two tasks: (1) finding a set afhal/spaces that is necessarya nd sufficient (but not unique) to represent a given solid, and (2) constructing an efficient CSG representation using those hal/spaces. This paper solves the problem for curved planar solids, i.e., r-sets in £2, with or without holes, whose boundary is given by a collection of edges. The edges may be subsets of straight lines or convex curves .(i.e., curves which intersect any line in at most two points). We prove a number of results and describe algorithms that have been fully implemented for solids bounded by line segments and circular arcs. Empirical results show that the computed CSG representations are superior to those produced by earlier algorithms, and produce superior three-dimensional CSG representations for mechanical parts defined by contour sweeping. A companion paper generalizes the results to higher dimensional solids.

V. Shapiro, D. L. Vossler
Transactions of ASME, Journal of Mechanical Design, Vol. 113, No. 3, pp. 292–305, September 1991.

Construction and Optimization of CSG Representations

Boundary representations(B-reps) and Constructive solid geometry(CSG) are widely used representation scheme for solids. While the problem of computing a B-rep from a CSG representation is relatively well understood, the inverse problem of B-rep to CSG conversion has not been addressed in general. The ability to perform B-rep to CSG conversion has important implications for the architecture of solid modelling systems, and in addition, is of considerable theoretical interest. This paper presents a general approach to B-rep to CSG conversion based on the partition of Euclidean space by surfaces induced from a B-rep, and on the well known fact that clsoed regualr sets and regularised set operations form a Boolean algebra. It is shown that the conversion problem is well defined, and that the solution results in a CSG representation that is unique for a fixed set of halfspaces that serve as a ‘basis’ for the representation. The ‘basis’ set contains halfspaces induced from a B-rep plus additional non-unique separating halfspaces.

V. Shapiro, D. L. Vossler
Computer Aided Design “Beyond Solid Modelling“

On the role of geometry in mechanical design

A complete design usually specifies a mechanical system in terms of component parts and assembly relationships. Each part has a fully defined nominal or ideal form and well defined material properties. Tolerances are used to permit variations in the form and properties of the components, and are used also to permit variations in the assembly relationships. Thus the geometry and material properties of the system and all of its pieces are fully defined (at least in principle). Henceforth we shall focus on geometry and, for reasons that will become evident, will not deal with materials despite their obvious importance

V. Shapiro, H. Voelcker
Research in Engineering Design, Vol. 1, No. 1, pp 69-73, 1989.

Theory of R-functions and Applications: A Primer

A R-function is a real valued function characterized by some property that is completely determined by the corresponding property of its arguments,e.g., the sign of some real function is completely determined by the sign of their arguments. This primer summarizes some basic results from the theory of R-functions and describes some of the applications.

V. Shapiro
Technical Report CPA88-3, Cornell University, November 1988.