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.

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 [33] to Harrison's theory of chainlets [16], including Regge calculus in general relativity [26, 34], Tonti's work on the mathematical structure of physical theories [30] and their discrete formulation [31], plus multifarious researches into so-called mimetic discretization methods [28], discrete exterior calculus [11, 12], and discrete differential geometry [2, 10]. 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.

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 E3). But a solid 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 E3. 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 implemented using a fast parallel sampling method on a GPU.

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 multilinear 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. 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, and connectedness.

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.

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.

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.

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 /spl epsiv/-regularity that quantifies 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 /spl epsiv/-topological operations that are related to, but are distinct from, the common morphological operations. We also show that /spl epsiv/-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 /spl epsiv/. Many applications of /spl epsiv/-regularity include geometric data translation and solid model validation.

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 reprentation, 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.

One of the key unsolved problems in parametric solid modeling is a robust update (regeneration) of the solid's boundary representation, given a specified change in solid's parameter values.The fundamental difficulty lies in determining the mapping between boundary representations for solids in the same parametric family, also known as "persistent naming."We formulate the notion of Boundary Representation (BR-)variance for solids in the same parametric family based on the assumption of continuity: small changes in solid's parameter values should result in small changes in solid's boundary rep reeentation, which may include local collapses of cells in boundary representations.We show that our formulation gives the necessary conditions that must be satisfied by any BR-variant mappings between boundary representations.These conditions are powerful enough to identify invalid updates in many practical situations and provide a formal criteria for the recently proposed heuristic approaches to the "persistent naming" problem. Motivation Ambiguity of parametric solid modeling

important applications of b-rep -CSG conversion arise in solid modeling, image processing, and c,lsewhere.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 ]>:lras(J]ldTMt(} ~~clcnt C'SG representations in PADL-2 Categ[jric,s and Subject Ilescriptors: 1.3.5

Box-bisection is a method for solving nonlinear systems. Space is subdivided into boxes of smaller and smaller diameter, and each subbox is tested for the existence of solutions by a test that either eliminates it from further consideration or marks it for subdivision. Simple bisection uses a test for the exclusion of subboxes, but no test that guarantees the existence of a unique solution in a subbox. Using this simple bisection, we show that the passed boxes tend to cluster in geometrical configura- tions whose number is stable under subdivision. This implies for many problems that the work required to do simple bisection may be prohibitive. However, improvements may be possible by grouping clusters and dynamically redefining the box proportions. The restriction to second-degree systems is sufficient to display this behavior.

No abstract available.