decsg (Partial Differential Equation Toolbox)

Partial Differential Equation Toolbox

Decompose Constructive Solid Geometry into minimal regions

Syntax

dl=decsg(gd) 
dl=decsg(gd,sf,ns) 
[dl,bt]=decsg(gd) 
[dl,bt]=decsg(gd,sf,ns) 
[dl,bt,dl1,bt1,msb]=decsg(gd) 
[dl,bt,dl1,bt1,msb]=decsg(gd,sf,ns)

Description

This function analyzes the Constructive Solid Geometry model (CSG model) that you draw. It analyzes the CSG model, constructs a set of disjoint minimal regions, bounded by boundary segments and border segments, and optionally evaluates a set formula in terms of the objects in the CSG model. We often refer to the set of minimal regions as the decomposed geometry. The decomposed geometry makes it possible for other toolbox functions to "understand" the geometry you specify. For plotting purposes a second set of minimal regions with a connected boundary is constructed.

The graphical user interface pdetool uses decsg for many purposes. Each time a new solid object is drawn or changed, pdetool calls decsg in order to be able to draw the solid objects and minimal regions correctly. The Delaunay triangulation algorithm, initmesh, also uses the output of decsg to generate an initial mesh.

dl=decsg(gd,sf,ns) decomposes the CSG model gd into the decomposed geometry dl. The CSG model is represented by the Geometry Description matrix, and the decomposed geometry is represented by the Decomposed Geometry matrix. decsg returns the minimal regions that evaluate to true for the set formula sf. The Name Space matrix ns is a text matrix that relates the columns in gd to variable names in sf.

dl=decsg(gd) returns all minimal regions. (The same as letting sf correspond to the union of all objects in gd.)

[dl,bt]=decsg(gd) and [dl,bt]=decsg(gd,sf,ns) additionally return a Boolean table that relates the original solid objects to the minimal regions. A column in bt corresponds to the column with the same index in gd. A row in bt corresponds to a minimal region index.

[dl,bt,dl1,bt1,msb]=decsg(gd) and [dl,bt,dl1,bt1,msb]=decsg(gd,sf,ns) return a second set of minimal regions dl1 with a corresponding Boolean table bt1. This second set of minimal regions all have a connected boundary. These minimal regions can be plotted by using MATLAB patch objects. The second set of minimal regions have borders that may not have been induced by the original solid objects. This occurs when two or more groups of solid objects have nonintersecting boundaries.

The calling sequences additionally return a sequence msb of drawing commands for each second minimal region. The first row contains the number of edge segment that bounds the minimal region. The additional rows contain the sequence of edge segments from the Decomposed Geometry matrix that constitutes the bound. If the index edge segment label is greater than the total number of edge segments, it indicates that the total number of edge segments should be subtracted from the contents to get the edge segment label number and the drawing direction is opposite to the one given by the Decomposed Geometry matrix.

Geometry Description Matrix

The Geometry Description matrix gd describes the CSG model that you draw using pdetool. The current Geometry Description matrix can be made available to the MATLAB main workspace by selecting the Export Geometry Description, Set Formula, Labels . . . option from the Draw menu in pdetool.

Each column in the Geometry Description matrix corresponds to an object in the CSG model. Four types of solid objects are supported. The object type is specified in row 1:

For the circle solid, row one contains 1, and the second and third row contain the center x- and y-coordinates, respectively. Row four contains the radius of the circle.
For a polygon solid, row one contains 2, and the second row contains the number, n, of line segments in the boundary of the polygon. The following n rows contain the x-coordinates of the starting points of the edges, and the following n rows contain the y-coordinates of the starting points of the edges.
For a rectangle solid, row one contains 3. The format is otherwise identical to the polygon format.
For an ellipse solid, row one contains 4, the second and third row contains the center x- and y-coordinates, respectively. Rows four and five contain the semiaxes of the ellipse. The rotational angle of the ellipse is stored in row six.

Set Formula

sf contains a set formula expressed with the set of variables listed in ns. The operators `+', `*', and `-' correspond to the set operations union, intersection, and set difference, respectively. The precedence of the operators `+' and `*' is the same. `-' has higher precedence. The precedence can be controlled with parentheses.

Name Space Matrix

The Name Space matrix ns relates the columns in gd to variable names in sf. Each column in ns contains a sequence of characters, padded with spaces. Each such character column assigns a name to the corresponding geometric object in gd. This way we can refer to a specific object in gd in the set formula sf.

Decomposed Geometry Matrix

The Decomposed Geometry matrix dl contains a representation of the decomposed geometry in terms of disjointed minimal regions that have been constructed by the decsg algorithm. Each edge segment of the minimal regions corresponds to a column in dl. We refer to edge segments between minimal regions as border segments and outer boundaries as boundary segments. In each such column rows two and three contain the starting and ending x-coordinate, and rows four and five the corresponding y-coordinate. Rows six and seven contain left and right minimal region labels with respect to the direction induced by the start and end points (counter clockwise direction on circle and ellipse segments). There are three types of possible edge segments in a minimal region:

For circle edge segments row one is 1. Rows eight and nine contain the coordinates of the center of the circle. Row 10 contains the radius.
For line edge segments row one is 2.
For ellipse edge segments row one is 4. Rows eight and nine contain the coordinates of the center of the ellipse. Rows 10 and 11 contain the semiaxes of the ellipse, respectively. The rotational angle of the ellipse is stored in
row 12.

Examples

The command sequence below starts pdetool and draws a unit circle and a unit square.

```
pdecirc(0,0,1) 
pderect([0 1 0 1])
```

Insert the set formula C1-SQ1. Export the Geometry Description matrix, set formula, and Name Space matrix to the MATLAB main workspace by selecting the Export Geometry Description . . . option from the Draw menu. Then type

[dl,bt]=decsg(gd,sf,ns);  
dl =
     2.0000   2.0000    1.0000    1.0000    1.0000
          0        0   -1.0000    0.0000    0.0000
     1.0000        0    0.0000    1.0000   -1.0000
          0   1.0000   -0.0000   -1.0000    1.0000
          0        0   -1.0000         0   -0.0000
          0        0    1.0000    1.0000    1.0000
     1.0000   1.0000         0         0         0
          0        0         0         0         0
          0        0         0         0         0
          0        0    1.0000    1.0000    1.0000

 bt =
     1        0

Note that there is one minimal region, with five edge segments, three circle edge segments, and two line edge segments.

Algorithm

The algorithm consists of the following steps:

Determine the intersection points between the borders of the model objects.
For each intersection point, sort the incoming edge segments on angle and curvature.
Determine if the induced graph is connected. If not, add some appropriate edges, and redo algorithm from step 1.
Cycle through edge segments of minimal regions.
For each original region, determine minimal regions inside it.
Organize output and remove the additional edges.

Note The input CSG model is not checked for correctness. It is assumed that no circles or ellipses are identical or degenerated and that no lines have zero length. Polygons must not be selfintersecting. Use the function csgchk to check the CSG model.

Diagnostics

NaN is returned if the set formula sf cannot be evaluated.

See Also

pdetool, pdegeom, pdebound, wgeom, wbound, pdecirc, pderect, pdepoly, pdeellip, csgchk, csgdel

csgdel dst, idst