# Cellular Topology Data Structure

## Concepts

Cellular topology is used to decompose a non-manifold object into internally connected two-dimensional (sheet) and three-dimensional (solid) regions. Cellular topology ignores one-dimensional (wire) regions. Each of these connected regions is represented by a cell that is 2D or 3D. The interior of each two-dimensional or three-dimensional cell is inherently two-dimensional or three-dimensional. 2D cells may have holes in their interior; 3D cells may have voids in their interior. The cellular topology in ACIS is constructed on top of the ACIS topological structure, which is unaltered by the presence of the cellular topology.

To understand ACIS' cellular topology one must first understand ACIS' topology. For instance, there are three types of faces:

• A single-sided face separates the "inside" from "outside" of a solid region.
• A sheet face is categorized as "double-sided both-outside", implying that the normals on both sides of the face point into a void region.
• An internal face is categorized as "double-sided both-inside", implying that the normals on both sides of the face point into a solid region.

The fundamental elements of the ACIS cellular topology model are the cell, c-shell, and c-face. A c-shell exists only on three-dimensional cells. It is analogous to a shell in the ACIS Topology. It allows a three-dimensional cell to have internal voids. Because two-dimensional cells do not contain internal voids, they do not need c-shells. Both c-shells and two-dimensional cells consist of a single set of connected c-faces. Each c-face can be thought of as a face use. Each single-sided face has one c-face; whereas, each sheet face and internal face has two c-faces. A c-shell consists entirely of c-faces on single-sided and interior faces; whereas a two-dimensional cell consists entirely of c-faces on sheet faces.

To help illustrate these concepts see the four figures below. A solid body with an internal void is depicted in Figure. Solid Body with Internal Void. The cellular topology for this body has one 3D cell, two c-shells, and twelve c-faces. Each face in the body has one c-face. The solid body in Figure. Solid Body with Internal Faces has been subdivided by internal faces. This body has twelve c-shells and twelve 3D cells. Each c-shell consists of six c-faces. The three faces in the sheet body depicted in Figure. Sheet Body with Three Faces are connected by a single non-manifold edge. The cellular topology of this body has six c-faces and three 2D cells. The solid body in Figure. Solid Body with Non-manifold Edge has three solid regions connected along a non-manifold edge. The cellular topology for this body contains three c-shells and three 3D cells. Each c-shell consists of six c-faces.

 Solid Body with Internal Void Solid Body with Internal Faces Sheet Body with Three Faces Solid Body with Non-manifold Edge

Because the interior of each 2D or 3D cell is inherently 2D or 3D, cells are usually two-manifold or three-manifold regions; however, cells are not always two-manifold or three-manifold. For instance, if both sides of an internal face point into the same 3D region, that 3D region (3D cell) will contain the internal face and be non-manifold. In other words a 3D cell can contain a internal face. If the internal face is not connected to any other faces, it will constitute its own internal c-shell, and represent an infinitesimally thin void in the cell. As another example, a single sheet face may contain a non-manifold vertex. In this case, the 2D cell containing this face will also be non-manifold. Many other similar, non-manifold cases exist and can be represented by ACIS' cellular topology data structure.

## Implementation

The ACIS cellular topology (CT) data structure is an optional data structure that may be added to or removed from the standard ACIS topology data structure. The CT data structure is attached to the standard topology data structure using attributes. Attributes are places on FACEs and LUMPs to provide pointers into the CT data structure.

The concepts of cells, c-shells, and c-faces are implemented in the CELL, CSHELL, CFACE classes. There are two subclasses of CELL: CELL2D and CELL3D.

• A CELL2D contains a list of CFACEs, each of which points to a face that is double-sided and both-outside. A c-face is a reference to one side of a face. It can be thought of as a face use by a cell. Because sheet faces have c-faces on both sides, each sheet face is used twice by its 2D cell.
• A CELL3D contains a list of CSHELLs (connected sets of CFACEs that bound the 3D region of the cell). A c-shell is a connected portion of a 3D cell's boundary. It is similar to a shell in the ACIS topological structure. The first c-shell in a cell's list of c-shells is the peripheral c-shell. All other c-shells in the list represent interior boundaries of the cell.

A CSHELL points to a list of CFACEs, each of which represents the use of a face in either a FORWARD or REVERSE sense. Each face points back to its CFACE(s) through an ATTRIB_FACECFACE. Single-sided FACEs have one CFACE; double-sided FACEs have two CFACEs, one on the front and one on the back of the FACE. The cellular topology of a LUMP is attached using an instance of an ATTRIB_CELL. The ATTRIB_CELL contains a list of CELLs in the LUMP. Actually, the ATTRIB_CELL contains a pointer to the head of a singly-linked list of CELLs. If SUPERCELLs are present, the ATTRIB_CELL contains a pointer to the first SUPERCELL. A SUPERCELL hierarchy may be optionally computed to provide a hierarchical cellular data structure. The supercells function much like subshells, including expand and flatten operations. They can significantly speed up global operations on large models. For instance, if a bin-tree or oct-tree hierarchy of supercells existed, it would be must faster to determine which cell contained a given point, rather than testing every cell in a body. As with subshells, supercell decompositions are typically generated by an application-specific algorithm rather than using the demonstration API, api_ct_expand.

The following figure illustrates the CT data structure on a LUMP. All lists are NULL terminated. Each CELL points back to its LUMP; each CSHELL to its CELL; each CFACE to its owner (its CSHELL or CELL2D); and each ATTRIB_FACECFACE to its front and back CFACEs. Because a CFACE points back to either a CELL2D or a CSHELL, its owner pointer is of type ENTITY.

Cellular Topology Data Structure

The following diagram depicts the derivation of each CT class from ENTITY. Because the CT classes are derived from ENTITY they can be copied, debugged, saved and restored, and they participate in "undoing" and "redoing" of modeling operations. Cellular topology behaves just like model topology.

Derivation of CT Classes from the ENTITY Class

## The cell_granularity Option

The cell_granularity option allows applications to change the definition of two-dimensional cells. The default value for this option, "manifold", creates two-dimensional cells from sets of sheet faces that form two-manifold regions. If this option has a value of "face" when cells are computed, every sheet face will be in a separate two-dimensional cell. If this option has a value of "connected" when cells are computed, two-dimensional cells will contain all connected sheet faces. For more information on the behavior of this option, refer to cell_granularity.