International Journal of Computational Geometry & Applications

This paper deals with a representation of assembly features. Modeling the product at each stage of the assembly process, taking into account all pertinent geometrical, technological and functional data, distinguishes our model from the ones described in the literature. A representation such as this also greatly contributes to the designing of a system that includes the various stages in the development and manufacture of a product. To reach our goal, we let the user interactively input a set of features that cannot be supported by a solid modeler. The system automatically deduces other features pertaining to faces, parts and subassemblies. Given the object-oriented structure that we chose, the different features can be abstractly represented as object attributes. This can assist the method engineer in the automatic generation of assembly sequences or resources. Examples are given to validate the concept.

In this paper, we briefly review the existing direct implicit geometry generation methods, which include creation of blending surfaces, a limited family of sweeps, and reconstruction of solid geometry from a sample set of surface data points. A broader approach is presented, utilizing the properties of the graph of the implicit defining function, to systematically construct swept solids and perform morphing between sections by implicit methods.

This paper presents a unified approach for incorporating free-form solids in bilateral Brep and CSG representation schemes, by resorting to low-degree (quadratic, cubic) algebraic surface patches. We develop a general CSG solution that represents a free-form solid as a boolean combination of a direct term and a complicated delta term. This solution gives rise to the trunctet-subshell conditions, under which the delta term computation can be obviated. We use polyhedral smoothing to construct a Brep consisting of quadratic algebraic patches that meet with tangent-plane continuity, such that the trunctet-subshell conditions are guaranteed automatically. This guarantee is not currently available for cubic patches. The general CSG solution thus applies whenever trunctet-subshell conditions are violated, e.g. sometimes for cubic patches or sometimes for patches of any degree that are subject to shape control operations. Manifold solids of arbitrary topology can be represented in our dual representation system. Ensuing CSG constructs are parallel processed on the RayCasting Engine to support a wide range of solid modeling applications, including general sweeping, Minkowski operations, NC machining, and touch-sense probing.

The medial axis transform of a 2D region was introduced by Blum in the 1960's as an aid to the description of biological shape. It is an alternative representation of a region which is often more amenable to analysis. This property has led to its use in diverse fields including pattern recognition and automatic finite element mesh generation. There are two widely agreed mathematical definitions for the medial axis transform which are closely related. It is shown that these definitions are not in general equivalent, despite being so far many types of region.

In this paper, precise mathematical definitions of the medial axis transform and its key points (atoms) are given, and an O(n²) algorithm for its computation via those atoms presented. This algorithm is described in terms of simple polygons whose sole boundary consists of circular arcs and straight line segments, then extended to polygons with holes. It is shown how more complex edges could be accommodated. In comparison with existing algorithms it is simple to implement and stable in the presence of geometric degeneracy.

The bisector of two plane curve segments (other than lines and circles) has, in general, no simple — i.e., rational — parameterization, and must therefore be approximated by the interpolation of discrete data. A procedure for computing ordered sequences of point/tangent/curvature data along the bisectors of polynomial or rational plane curves is described, with special emphasis on (i) the identification of singularities (tangent–discontinuities) of the bisector; (ii) capturing the exact rational form of those portions of the bisector with a terminal footpoint on one curve; and (iii) geometrical criteria the characterize extrema of the distance error for interpolants to the discretely–sample data. G¹ piecewise– parabolic and G² piecewise–cubic approximations (with O(h⁴) and O(h⁶) convergence) are described which, used in adaptive schemes governed by the exact error measure, can be made to satisfy any prescribed geometrical tolerance.

In this paper we describe the DCEL system: a geometric software package which implements a polyhedral programming environment. This package enables fast prototyping of geometric algorithms for polyhedra or for polyhedral surfaces. We provide an overview of the system's functionality and demonstrate its use in several applications.

Problems presented at the open-problem session of the 14th Annual ACM Symposium on Computational Geometry are listed.