The Universal Product Representation (UPR) and Feature-Based Data Exchange

Ari Rappoport

Feature-based data exchange (FBDE) is one of the major technical challenges in Solid and Geometric Modeling. In this page I explain the problem and its significance to academic research, and present a brief overview of the Universal Product Representation (UPR) solution. This page deals strictly with the academic, scientific aspects of the UPR.


Parametric Feature Based Design

Parametric feature-based design (PFBD) is a shape design paradigm that combines two of the central concepts in geometric modeling: shape features and parametric object families. In PFBD, a shape is defined through the procedural or declarative combination of shape features. In the former, a feature is any operation that creates new geometry or modifies the shape of existing geometry. Features are invoked at a certain order. In the latter, features are usually collections of geometric entities, which define an object through a system of simultaneous constraints and equations.

In both methods, what is defined is a parametric family of shapes rather than a single shape. In the procedural approach, both the features and the way in which they are combined with the existing object are parameterized, in the sense that it is possible to modify a vector of parameters and obtain a different shape. In the declarative approach, the vector of parameters is derived from the constraints and equations utilized.

Parametric feature based design is the major design paradigm used in modern computer-aided design (CAD) systems. The fact that the design is feature-based enables designers to define objects in terms that parallel their functionality and the way that people think of them. The fact that the design is parametric enables rapid modifications to the object, in order to experiment with many alternatives and to quickly respond to changing requirements. Modern CAD systems combine the procedural and the declarative approaches into a single powerful design model.

Technically, an object in PFBD is represented as a directed a-cyclic graph. The nodes of the graph correspond to features. The output of a node represents the state of the object after the invocation of the node's feature. An arc from node A to node B means that the feature (operation) represented by node B is invoked on the output of node A. Declarative modeling is supported by viewing a system of simultaneous constraints as a single (albeit very powerful) feature.

A shape is thus defined as the output of a `program' that includes both sequential procedures and declarative logic programs. The situation is more complex than the analogue to a computer program, because it often happens that the semantics of a node in the graph depends on particular details of the output of the node that leads to it. In particular, many features are selection operations, which select a subset of the previous shape. Such subsets can be geometric pointsets or more abstract entities, usually one- or two-dimensional entities from the boundary representation (Brep) of the object.

PFBD is an extension of the classic Constructive Solid Geometry (CSG) representation. It extends CSG in the number and types of operations (CSG allows only affine transformations and Boolean operations) and in the usage of selections and declarative features.

Note: the description above is a simplified one. The paradigm actually contains functional programming as well, since it allows a node (or a set of nodes) to be an argument of another node, as is the case in the "pattern" feature. I am currently working on formalizing the theoretical foundations of this aspect of the paradigm.

Data Exchange

Data exchange is the informal name of the operation of representation conversion, a fundamental operation in geometric modeling. A shape is given in a particular representation which needs to be converted to another. The two representations can be radically different, e.g., when converting between a boundary representation (Brep) and CSG, or be two different implementations of the same modeling paradigm, e.g., when converting between two Brep systems. The term `data exchange' is usually reserved to the latter case.

The main challenge in representation conversion is to make it as lossless as possible. Understanding the types of losses that arise in data exchange operations sheds lights on the inherent properties of modeling paradigms and on their implementations. For example, even data exchange between two Brep systems cannot be lossless in practice due to numerical inaccuracies stemming from the fact that floating point arithmetic is used for representing geometric locations and distances. Overcoming these so-called tolerancing problems is one of the major problems in solid and geometric modeling, and is tightly related to data exchange.

The Importance of Feature-Based Data Exchange

Owing to the centrality of feature-based modeling, parametric modeling, and representation conversion and data exchange to solid and geometric modeling, feature-based data exchange is evidently a major theoretical and practical problem in the field.

The problem becomes even more important when keeping in mind the deep technical challenges involved in it on one hand (see below), and its practical significance to manufacturing enterprises on the other hand. Potential practical applicability makes any scientific problem more important, since it complements theoretical discussions by a new set of derivative questions that many times are also challenging from a scientific point of view.

The Challenge in Feature-Based Data Exchange

The scientific challenge inherent in the problem of feature-based data exchange is readily grasped when realizing that the problem is more complex than the problem of automatic conversion of programs between programming languages. As explained above, in parametric feature-based design an object is represented as a program that is procedural and declarative at the same time. Translating such a program to a different language is obviously a difficult algorithmic task. The main issue is of course the fact that the two languages do not necessarily have the same expressive power.

In the case of FBDE, the two languages are never directly equivalent, because one parametric feature-based design system will always have at least one feature not directly supported by another. The number of different features and sub-features in a modern CAD system is easily in the hundreds or even thousands, and many of them are unique.

The FBDE problem can thus be phrased in the following abstract manner: given a directed a-cyclic graph whose nodes are operations from a given operation set S, how would we translate it to use a different operation repertoire T such that the objects at the output of the graph would be as similar as possible? This problem is obviously an interesting and deep one from a computer science point of view. Since the operations are geometric in nature, the problem raises many interesting questions in the theory of geometric modeling and computational geometry.

Overview of the UPR Solution

Previous approaches to data exchange have tried to define a common set of features, basically limiting the expressive power of the representations on both sides to be identical. The UPR takes a radically different approach, tackling the problem in its full technical difficulty, assuming that the feature sets or even the basic modeling paradigms on both sides are not identical.

The central concept in the UPR architecture is that of a rewrite. A rewrite is any representation conversion of an entity, meant to be used when the original entity (or another rewrite) do not yield satisfactory results. An entity can be a whole assembly, a sub-assembly, a single part, a sub-part of an object, a feature collection, a single feature, a part of a feature, or even an equation or a single parameter.

Another important concept is that of verification data. Each entity has associated data used for verifying that it has been exported or imported correctly. Verification data is usually both geometric (point samples, curves, surfaces etc) and symbolic (the partial graph structure of the Brep of the object, the assembly structure, etc).

The UPR system is comprised of three parts: export, UPR file, and import. The export process generates a UPR file that contains as much as possible of the original data. Ideally, the data is not modified at all in this process (apart from implementational issues related to the actual file format, which are not interesting from a scientific point of view.) The import process builds the feature graph one node at a time. After each new node, verification data is used in order to check that it has been imported correctly (or as correctly as the expressive power of the receiving system allows.) In case of failure (or of an insufficient level of success), the best rewrite for the situation is found (or computed on the fly) and invoked by undoing the previous new node and creating a new node according to the rewrite instructions.

A short paper describing the UPR architecture at a greater length than this page is [Rappoport 93].

A major type of rewrite is the `Brep per feature' rewrite, which replaces a parametric feature node by its geometric effect. In other words, it considers the output of the graph node on the sending side and creates a new node that when connected to the graph creates the same output on the receiving side. The algorithm is described in detail in [Spitz and Rappoport 04].

As explained above, a major type of operation in PFBD is the selection operation, which selects a subset of the geometry and/or topology of the object for usage of future features. This operation is related to the well known `persistent naming' problem. Translating selections in one system to proper ones in another system is an interesting, difficult and crucial problem. Algorithms for supporting one- and two-dimensional selections are presented in detail in [Rappoport et al 05, Rappoport et al 06].

Implementation

The UPR architecture has been implemented. The implementation has been done in a commercial company (Proficiency Ltd.), but all of the conceptual details are open for academic discussion. Many have been published in scientific papers (see below).

The current implementation supports all high-end CAD system in today's markets: Catia V5, Unigraphics, I-DEAS, ProEngineer, and Catia V4. Several versions of each system are supported. The UPR supports both single parts and assemblies. The system is accessed through a web server that provides a user interface and is responsible for distributing the data exchange task between several computational agents possibly located over the web.

The number of data exchange operations done using the system is well over 100,000. The system is being used regularly on real data in large well known manufacturing organizations. These numbers constitute a proof that the technical challenges have been overcome. (Note that this does not say much on the commercial viability of such a project. As stated above, this page does not address commercial aspects, only academic ones.)

Publications