This work describes the Semiconductor Wafer Representation (SWR) for representing and manipulating wafer state during process and device simulation. The goal of the SWR is to provide an object-oriented interface to a collection of functions designed for developing and integrating Technology CAD (TCAD) applications. By providing functions which can be common across many applications, we aim to greatly reduce tool development and integration time. Corporate, vendor, and university TCAD developers have worked together under the auspices of the CAD Framework Initiative to create an architecture and C++ programming interface for an SWR 1.0 draft standard. Here we describe this architecture and the results of creating and using a prototype implementation of the standard both to integrate existing TCAD tools and to develop simple new tools.>

An automatic method for generating finite element meshes for multiply connected planar domains with polygonal boundaries (i.e. planar polygons with polygonal holes) is described. The symmetric axis transform is used to obtain a planar graph that partitions the given domain. This transformation may introduce edges in the graph that are too long or too short for generating good meshes. A silver processing algorithm, which transforms the graph into another graph devoid of such edges, is presented. Finally, additional modes are placed on the edges of the graph to obtain a triangulation, and this process is applied iteratively, yielding the final mesh. The method automatically increases the mesh density in regions of rapid change in shape and allows both global and local control of the mesh density. The method also admits the imposition of node compatibility constraints along domain boundaries, thus making the method suitable for meshing planar cell complexes (i.e multiple polygonal domains with shared boundaries in two-dimensional space) and for generating boundary elements for polyhedra in three-dimensional space.>

Many fundamental tests performed by geometric algorithms can be formulated in terms of finding the sign of a determinant. When these tests are implemented using fixed precision arithmetic such as floating point, they can produce incorrect answers; when they are implemented using arbitrary-precision arithmetic, they are expensive to compute. We present adaptive-precision algorithms for finding the signs of determinants of matrices with integer and rational elements. These algorithms were developed and tested by integrating them into the Guibas-Stolfi Delaunay triangulation algorithm. Through a combination of algorithm design and careful engineering of the implementation, the resulting program can triangulate a set of random rational points in the unit circle only four to five times slower than can a floating-point implementation of the algorithm. The algorithms, engineering process, and software tools developed are described.

A standard technique in solid modeling is to represent planes (or lines) by explicit equations and to represent vertices and edges implicitly by means of combinatorial information. Numerical problems that arise from using floating-point arithmetic to implement operations on solids can be avoided by using exact arithmetic. Since the execution time of exact arithmetic operators increases with the number of bits required to represent the operands, it is important to avoid increasing the number of bits required to represent the plane (or line) equation coefficients. Set operations on solids do not increase the number of bits required. However, rotating a solid greatly increases the number of bits required, thus adversely affecting efficiency. One proposed solution to this problem is to round the coefficients of each plane (or line) equation without altering the combinatorial information. We show that such rounding is NP-complete.

Developers of application software must often work with “legacy systems.” These are systems that have evolved over many years and are considered irreplaceable, either because it is thought that duplicating their function would be too expensive, or because they are trusted by users. Because of their age, such systems are likely to have been implemented in a conventional language with limited use of data abstraction or encapsulation. The lack of abstraction complicates adding new applications to such systems and the lack of encapsulation impedes modifying the system because applications depend on system internals. We describe our experience providing and using an object-oriented interface to a legacy system.

Abstract TGMS (tiered geometric modelling system) is an experimental system intended to reduce the difficulty and cost of developing new solid modelling applications while preserving investment in an existing, time‐tested, solid modeller. The application developer writes programs in the TGMS language, which consists of a base language augmented by data types (classes) for geometry. The base programming language is AML/X, an object‐oriented language intended for use in design and manufacturing applications. Solid modelling is done using an interface to GDP (geometric design processor), an existing, production‐quality solid modelling system. TGMS shows how a system written in a non‐object‐oriented language can be used as a base for an object‐oriented application programming environment. This paper presents the design of TGMS and discusses important aspects of its implementation. The TGMS language defines classes and methods that provide an interface to functions and data represented in a non‐object‐oriented language. To implement TGMS, issues related to communication, storage management and consistency were addressed. These, and other, implementation issues are discussed. The paper includes sample programs and a summary of feedback from TGMS users. It concludes that the use of object‐oriented programming for geometry has many benefits, and that an object‐oriented system can be built on top of a non‐object‐oriented system at less cost than building the equivalent object‐oriented system from scratch.

Abstract In object‐oriented systems, it is oftern useful for objects to be allowed to carry out some action before they are deallocated. This can be done by defining a destroy method in the object's class, and arranging for the memory system to send a message invoking this method immediately before deallocating the object. This allows resources associated with the object to be returned to the system, limited cross‐language garbage collection, and other, more complex, behaviour. During the execution of the destroy method it is possible for new references to objects to be created. Care must be taken that the garbage collection does not erroneously free such objects. Algorithms are presented to implement destroy methods in systems using reference counting and mark‐scan garbage collection techniques. Properties that are desirable in such systems are also discussed.

A high-level structure for a CAD modelling system development environment is proposed based on the thesis that domain independent and domain dependent modelling system functions can and should be separated. The thesis is supported by example functions drawn from a solid modelling system and a VLSI layout system.

Blum's two-dimensional shape description method based on the symmetric axis transform (SAT) is generalized to three dimensions. The method uniquely decomposes an object into a collection of sub-objects each drawn from three separate, but not completely independent, primitive sets defined in the paper: width primitives, based on radius function properties; axis primitives, based on symmetric axis curvatures; and boundary primitives, based on boundary surface curvatures. Width primitives are themselves comprised of two components: slope districts and curvature districts. Visualizing the radius function as if it were the height function of some mountainous terrain, each slope district corresponds to a mountain face together with the valley below it. Curvature districts further partition each slope district into regions that are locally convex, concave, or saddle-like. Similarly, axis (boundary) primitives are regions of the symmetric surface where the symmetric surface (boundary surfaces) are locally convex, concave, or saddle-like. Relations among the primitive sets are discussed.

The configuration of the critical points of a smooth function of two variables is studied under the assumption that the function is Morse, that is, that all of its critical points are nondegenerate. A critical point configuration graph (CPCG) is derived from the critical points, ridge lines, and course lines of the function. Then a result from the theory of critical points of Morse functions is applied to obtain several constraints on the number and type of critical points that appear on cycles of a CPCG. These constraints yield a catalog of equivalent CPCG cycles containing four entries. The slope districts induced by a critical point configuration graph appear useful for describing the behavior of smooth functions of two variables, such as surfaces, images, and the radius function of three-dimensional symmetric axes.