# 7. Geometry Tools - VertLoc,LineCon,TriCon,ADTree,Pred

DevTools provides modules for performing useful operations on primitive geometry as typically used in graphics applications. The VertLoc module stores point coordinate locations and optional attributes. The major feature of the VertLoc module is the ability to perform coincident point queries quickly. The LineCon module stores line connectivity and performs line stripping functions. The TriCon module stores triangle connectivity and performs triangle stripping and other adjacency related functions. The ADTree, alternating digital tree, module performs general geometric searching operations.

## 7.1 Point Colocation - VertLoc

The VertLoc module stores point (vertex) locations and optional attributes which use a positive integer index as a point key. The optional attributes include color RGB triple, transparency, and normal vector and are specifically for use in graphics applications. The primary function of VertLoc besides the simple storage and retrieval of point information is the merging and query of coincident points. Point merging is subject to both spatial coincidence and attribute similarity. Two points which are coincident in space will not be merged if user defined associated attributes are dissimilar.

• Begin and end an instance of an object, return object error flag
```*vsy_VertLocBegin      - create an instance of a VertLoc object
vsy_VertLocEnd         - destroy an instance of a VertLoc object
vsy_VertLocError       - return VertLoc object error flag
```
• Set and query points
```vsy_VertLocDef         - define initial number of points
Inq         - inquire current point storage
vsy_VertLocInsert      - insert point at specified index
vsy_VertLocColor       - query point color
vsy_VertLocNormal      - query point normal vector
vsy_VertLocTrans       - query point transparency
vsy_VertLocRef         - query point coordinates
vsy_VertLocNum         - query largest inserted point index
vsy_VertLocClear       - remove all points
vsy_VertLocMerge       - merge coincident points
vsy_VertLocUnique      - query unique sets of coincident points
vsy_VertLocLowest      - query lowest index in a unique set
vsy_VertLocSetColor    - set current color attribute
vsy_VertLocSetTrans    - set current transparency attribute
vsy_VertLocSetNormal   - set current normal vector attribute
vsy_VertLocSetParamf   - set floating point merging parameters
vsy_VertLocSetParami   - set integer merging parameters
```
Instance a VertLoc object using vsy_VertLocBegin. Once a VertLoc is instanced, an approximate number of points (0 is allowed) to be stored may be defined using vsy_VertLocDef. This allocates an internal array for the storage of point information. As points are inserted the VertLoc module will adjust memory as required. The actual size of the allocated storage may be determined by calling vsy_VertLocInq.

Each new point is inserted by calling vsy_VertLocInsert. The point at a specified index may be found by calling vsy_VertLocRef. The largest point index currently inserted may be queried by calling vsy_VertLocNum. The method vsy_VertLocClear removes all points. Each point may be assigned a number of attributes which are stored along with the point coordinate. These attributes are specified by setting a current attribute value which is then assigned to all subsequently inserted points. These attributes include color RGB triple, transparency factor and normal vector. These attributes are specifically designed for use with graphics applications. The current color, transparency and normal vector are assigned by calling vsy_VertLocSetColor, vsy_VertLocSetTrans and vsy_VertLocSetNormal respectively. The assigned color, transparency and normal vector for any point may be queried by point index using vsy_VertLocColor, vsy_VertLocTrans and vsy_VertLocNormal respectively.

Once all points are inserted the function vsy_VertLocMerge will identify all coincident points and determine the number of unique point locations and the maximum number of points in any unique set. Once this function has been called then all points in any unique set may be queried using vsy_VertLocUnique. The unique set associated with any point and the associated lowest point index in the unique set may be queried using vsy_VertLocLowest. The absolute coordinate tolerance used to determine point coincidence is defined using vsy_VertLocSetParamf. The angular tolerance used for normal vectors is also defined using vsy_VertLocSetParamf. The merging process may be made independent of a particular attribute value using vsy_VertLocSetParami.

## 7.2 Function Descriptions

The currently available VertLoc functions are described in detail in this section.

#### NAME

*vsy_VertLocBegin - create an instance of an VertLoc object

#### C SPECIFICATION

```vsy_VertLoc *vsy_VertLocBegin ()
```

```None
```

#### FUNCTION RETURN VALUE

The function returns a pointer to the newly created VertLoc object. If the object creation fails, NULL is returned.

#### DESCRIPTION

Create an instance of a VertLoc object. Memory is allocated for the object private data and the pointer to the data is returned. The default color RGB triple is (0.,0.,0.), the default transparency is 0. and default normal vector is (0.,0.,0.).

Destroy an instance of a VertLoc object using

```     void vsy_VertLocEnd (vsy_VertLoc *vertloc)
```

Return the current value of a VertLoc object error flag using

```     Vint vsy_VertLocError (vsy_VertLoc *vertloc)
```

#### NAME

vsy_VertLocDef - define initial number of points

#### C SPECIFICATION

```void vsy_VertLocDef (vsy_VertLoc *vertloc,
Vint numvert)
```

#### INPUT ARGUMENTS

```vertloc      Pointer to VertLoc object.
numvert      Estimated number of points to be held.
```

```None
```

#### ERRORS

SYS_ERROR_MEMORY is generated if new storage was unable to be allocated. SYS_ERROR_VALUE is generated if a negative numvert is specified.

#### DESCRIPTION

Suggest a number of points to be stored in VertLoc. This is used to allocate the initial storage. If the number of inserted points is greater than this initial estimate, storage space in dynamically expanded to hold the extra points. This function removes any previously entered points.

Find the current length of the internal storage of a VertLoc using

```     void vsy_VertLocInq (vsy_VertLoc *vertloc,
Vint *numvert)
```

#### NAME

vsy_VertLocInsert - insert point at specified index

#### C SPECIFICATION

```void vsy_VertLocInsert (vsy_VertLoc *vertloc,
Vint index,
Vfloat x[3])
```

#### INPUT ARGUMENTS

```vertloc      Pointer to VertLoc object.
index        Point index
x            Coordinates of point
```

```None
```

#### ERRORS

SYS_ERROR_VALUE is generated if index is less than one. SYS_ERROR_MEMORY is generated if new storage was unable to be allocated.

#### DESCRIPTION

Insert the point index and assign coordinates x. The current color, transparency and normal are also associated with the point. Use vsy_VertLocRef to query the coordinates of a point. Point indices must be positive and start at 1. There should be no gaps in the index values specified. Any undefined indices are given point locations and attributes of zero.

#### NAME

vsy_VertLocRef - query point coordinates

#### C SPECIFICATION

```void vsy_VertLocRef (vsy_VertLoc *vertloc,
Vint index,
Vfloat x[3])
```

#### INPUT ARGUMENTS

```vertloc      Pointer to VertLoc object.
index        Point index
```

#### OUTPUT ARGUMENTS

```x            Coordinates of point
```

#### ERRORS

SYS_ERROR_VALUE is generated if an improper index is input.

#### DESCRIPTION

Query coordinates of point.

#### NAME

vsy_VertLocNum - query largest inserted point index

#### C SPECIFICATION

```void vsy_VertLocNum (vsy_VertLoc *vertloc,
Vint *numvert)
```

#### INPUT ARGUMENTS

```vertloc      Pointer to VertLoc object.
```

#### OUTPUT ARGUMENTS

```numvert      Largest inserted point index
```

#### DESCRIPTION

Query for the largest inserted point index.

#### NAME

vsy_VertLocColor - query point color

#### C SPECIFICATION

```void vsy_VertLocColor (vsy_VertLoc *vertloc,
Vint index,
Vfloat c[3])
```

#### INPUT ARGUMENTS

```vertloc      Pointer to VertLoc object.
index        Point index
```

#### OUTPUT ARGUMENTS

```c            Color RGB triple of point
```

#### ERRORS

SYS_ERROR_VALUE is generated if an improper index is input.

#### DESCRIPTION

Query color RGB components of point.

#### NAME

vsy_VertLocNormal - query point normal vector

#### C SPECIFICATION

```void vsy_VertLocNormal (vsy_VertLoc *vertloc,
Vint index,
Vfloat v[3])
```

#### INPUT ARGUMENTS

```vertloc      Pointer to VertLoc object.
index        Point index
```

#### OUTPUT ARGUMENTS

```v            Normal vector of point
```

#### ERRORS

SYS_ERROR_VALUE is generated if an improper index is input.

#### DESCRIPTION

Query normal vector of point.

#### NAME

vsy_VertLocTrans - query point transparency

#### C SPECIFICATION

```void vsy_VertLocTrans (vsy_VertLoc *vertloc,
Vint index,
Vfloat *t)
```

#### INPUT ARGUMENTS

```vertloc      Pointer to VertLoc object.
index        Point index
```

#### OUTPUT ARGUMENTS

```t            Transparency of point
```

#### ERRORS

SYS_ERROR_VALUE is generated if an improper index is input.

#### DESCRIPTION

Query transparency of point.

#### NAME

vsy_VertLocClear - remove all points

#### C SPECIFICATION

```void vsy_VertLocClear (vsy_VertLoc *vertloc)
```

#### INPUT ARGUMENTS

```vertloc      Pointer to VertLoc object.
```

```None
```

#### DESCRIPTION

Remove all defined points. The current attributes remain unchanged.

#### NAME

vsy_VertLocMerge - merge coincident points

#### C SPECIFICATION

```void vsy_VertLocMerge (vsy_VertLoc *vertloc,
Vint *numunique,
Vint *maxlocate)
```

#### INPUT ARGUMENTS

```vertloc      Pointer to VertLoc object.
```

#### OUTPUT ARGUMENTS

```numunique    Number of unique coincident point sets
maxlocate    Maximum number of points in any unique set
```

#### ERRORS

SYS_ERROR_OPERATION is generated if no points are defined. SYS_ERROR_MEMORY is generated if new storage was unable to be allocated.

#### DESCRIPTION

Merge coincident points subject to attribute similarity. The number of unique coincident point sets and the maximum number of points in any unique set are returned. Use vsy_VertLocUnique to query for the points in each unique set. Use vsy_VertLocLowest to query the unique set containing a specified point index and the lowest point index contained in the unique set. Use vsy_VertLocSetParamf to set the coordinate and normal vector tolerances for merging. Use vsy_VertLocSetParami to set disable a type of attribute value from participating in the merging process.

#### NAME

vsy_VertLocUnique - query unique sets of coincident points

#### C SPECIFICATION

```void vsy_VertLocUnique (vsy_VertLoc *vertloc,
Vint iunique
Vint *nix,
Vint ix[])
```

#### INPUT ARGUMENTS

```vertloc      Pointer to VertLoc object.
iunique      Unique set identifier
```

#### OUTPUT ARGUMENTS

```nix          Number of points in unique set
ix           Vector of point indices contained in unique set
```

#### ERRORS

SYS_ERROR_OPERATION is generated if vsy_VertLocMerge not called. SYS_ERROR_VALUE is generated if an improper iunique is input.

#### DESCRIPTION

Query for the number of points and point indices contained in a unique set. The unique sets are numbered 1 <= iunique <= numunique where numunique is returned by the function vsy_VertLocMerge. The number of points, nix, will not exceed the value of maxlocate returned by vsy_VertLocMerge.

#### NAME

vsy_VertLocLowest - query lowest index in a unique set

#### C SPECIFICATION

```void vsy_VertLocLowest (vsy_VertLoc *vertloc,
Vint index,
Vint *iunique
Vint *lowestindex)
```

#### INPUT ARGUMENTS

```vertloc      Pointer to VertLoc object.
index        Point index
```

#### OUTPUT ARGUMENTS

```iunique      Unique set containing index
lowestindex  Lowest point index contained in set iunique.
```

#### ERRORS

SYS_ERROR_OPERATION is generated if vsy_VertLocMerge not called. SYS_ERROR_VALUE is generated if an improper index is input.

#### DESCRIPTION

Query for the unique set, iunique, which contains a specified point index. The lowest point index, lowestindex, contained in the unique set is also returned.

#### NAME

vsy_VertLocSetColor - set current color attribute

#### C SPECIFICATION

```void vsy_VertLocSetColor (vsy_VertLoc *vertloc,
Vfloat c[3])
```

#### INPUT ARGUMENTS

```vertloc      Pointer to VertLoc object.
c            RGB color components
```

```None
```

#### ERRORS

SYS_ERROR_MEMORY is generated if new storage was unable to be allocated.

#### DESCRIPTION

Set current color RGB components to be assigned to subsequent points defined by vsy_VertLocInsert. The components should be in the interval [0.,1.]. Internally each component is stored as an 8 bit integer.

#### NAME

vsy_VertLocSetTrans - set current transparency attribute

#### C SPECIFICATION

```void vsy_VertLocSetTrans (vsy_VertLoc *vertloc,
Vfloat t)
```

#### INPUT ARGUMENTS

```vertloc      Pointer to VertLoc object.
t            Transparency
```

```None
```

#### ERRORS

SYS_ERROR_MEMORY is generated if new storage was unable to be allocated.

#### DESCRIPTION

Set current transparency factor to be assigned to subsequent points defined by vsy_VertLocInsert. The transparency factor should be in the interval [0.,1.]. Internally the factor is stored as an 8 bit integer.

#### NAME

vsy_VertLocSetNormal - set current normal vector attribute

#### C SPECIFICATION

```void vsy_VertLocSetNormal (vsy_VertLoc *vertloc,
Vfloat v[3])
```

#### INPUT ARGUMENTS

```vertloc      Pointer to VertLoc object.
v            Normal vector
```

```None
```

#### ERRORS

SYS_ERROR_MEMORY is generated if new storage was unable to be allocated.

#### DESCRIPTION

Set current normal vector components to be assigned to subsequent points defined by vsy_VertLocInsert. The components should be in the interval [0.,1.]. Internally each component is stored as an 8 bit integer.

#### NAME

vsy_VertLocSetParamf - set floating point merging parameters

#### C SPECIFICATION

```void vsy_VertLocSetParamf (vsy_VertLoc *vertloc,
Vint ptype,
Vfloat fparam)
```

#### INPUT ARGUMENTS

```vertloc      Pointer to VertLoc object.
ptype        Type of parameter to set
=VERTLOC_TOL            Coordinate tolerance
=VERTLOC_NTOL           Normal vector tolerance in degrees
fparam       Specifies the floating value that ptype will be set to.
```

```None
```

#### ERRORS

SYS_ERROR_ENUM is generated if an improper ptype is specified.

#### DESCRIPTION

Set point colocation operation parameters. The VERTLOC_TOL parameter is a Cartesian coordinate tolerance for determining the colocation of points. The default VERTLOC_TOL is .00001 .

The VERTLOC_NTOL parameter is an angular normal vector tolerance for determining the colocation of points. The default VERTLOC_NTOL is 0.0 .

#### NAME

vsy_VertLocSetParami - set integer merging parameters

#### C SPECIFICATION

```void vsy_VertLocSetParami (vsy_VertLoc *vertloc,
Vint ptype,
Vint iparam)
```

#### INPUT ARGUMENTS

```vertloc      Pointer to VertLoc object.
ptype        Type of parameter to set
=VERTLOC_COLORTRANSATT  Color and Transparency flag
=VERTLOC_NORMALATT      Normal vector flag
iparam       Specifies the integer value that ptype will be set to.
=SYS_OFF      Ignore attribute value during merging
=SYS_ON       Consider attribute value during merging
```

```None
```

#### ERRORS

SYS_ERROR_ENUM is generated if an improper ptype is specified.

#### DESCRIPTION

Set point colocation sensitivity to a type of attribute. The VERTLOC_COLORTRANSATT and VERTLOC_NORMALATT parameters may be used to ignore a particular type of attribute value during the merging process. The default is SYS_ON.

## 7.3 Line Connectivity - LineCon

The LineCon module stores line connectivity and performs adjacency related functions such as ling stripping for graphics applications.

• Begin and end an instance of an object, return object error flag
```*vsy_LineConBegin       - create an instance of a LineCon object
vsy_LineConEnd          - destroy an instance of a LineCon object
vsy_LineConError        - return LineCon object error flag
```
• Set and query lines
```vsy_LineConDef          - define initial number of line
Inq          - inquire current line storage
vsy_LineConAppend       - append a line
vsy_LineConRef          - query line connectivity
vsy_LineConNum          - query number of appended lines
vsy_LineConClear        - remove all lines
vsy_LineConProcess      - create strip information
vsy_LineConStrip        - query line strips
vsy_LineConSetParami    - set line stripping parameters
```
Instance a LineCon object using vsy_LineConBegin. Once a LineCon is instanced, an approximate number of lines (0 is allowed) to be stored may be defined using vsy_LineConDef. This allocates an internal array for the storage of line information. As lines are appended the LineCon module will adjust memory as required. The actual size of the allocated storage may be determined by calling vsy_LineConInq.

Each new line is appended by calling vsy_LineConAppend. Indices are assigned to the lines as they are appended. The first line is assigned an index of 1. The index is incremented for each appended line. The line at a specified index may be found by calling vsy_LineConRef. The largest line index currently appended may be queried by calling vsy_LineConNum. The method vsy_LineConClear removes all lines. Once all lines have been entered, call vsy_LineConProcess to create line adjacency information which is required to perform subsequent line stripping query operations. Query for line stripping information using vsy_LineConStrip. The maximum length of generated line strips may be defined using vsy_LineConSetParami.

## 7.4 Function Descriptions

The currently available LineCon functions are described in detail in this section.

#### NAME

*vsy_LineConBegin - create an instance of a LineCon object

#### C SPECIFICATION

```vsy_LineCon *vsy_LineConBegin ()
```

```None
```

#### FUNCTION RETURN VALUE

The function returns a pointer to the newly created LineCon object. If the object creation fails, NULL is returned.

#### DESCRIPTION

Create an instance of a LineCon object. Memory is allocated for the object private data and the pointer to the data is returned.

Destroy an instance of a LineCon object using

```     void vsy_LineConEnd (vsy_LineCon *linecon)
```

Return the current value of a LineCon object error flag using

```     Vint vsy_LineConError (vsy_LineCon *linecon)
```

#### NAME

vsy_LineConDef - define initial length of storage array

#### C SPECIFICATION

```void vsy_LineConDef (vsy_LineCon *linecon,
Vint numline)
```

#### INPUT ARGUMENTS

```linecon      Pointer to LineCon object.
numline      Estimated number of lines to be held.
```

```None
```

#### ERRORS

SYS_ERROR_MEMORY is generated if new storage was unable to be allocated. SYS_ERROR_VALUE is generated if a negative numline is specified.

#### DESCRIPTION

Suggest a number of lines to be stored in LineCon. This is used to allocate the initial storage. If the number of appended lines is greater than this initial estimate, storage space in dynamically expanded to hold the extra lines. This function removes any previously entered lines.

Find the current length of the internal storage of a LineCon using

```     void vsy_LineConInq (const vsy_LineCon *linecon,
Vint *numline)
```

#### NAME

vsy_LineConAppend - append a line

#### C SPECIFICATION

```void vsy_LineConAppend (vsy_LineCon *linecon,
Vint ix[2])
```

#### INPUT ARGUMENTS

```linecon       Pointer to LineCon object.
ix            Line connectivity
```

```None
```

#### ERRORS

SYS_ERROR_MEMORY is generated if new storage was unable to be allocated.

#### DESCRIPTION

Append a line connectivity. Indices are assigned to the lines as they are appended. The first line is assigned an index of 1. The index is incremented for each appended line. The line connectivity, ix, may contain integer connection indices which may be negative, zero, or positive.

#### NAME

vsy_LineConRef - query line connectivity

#### C SPECIFICATION

```void vsy_LineConRef (vsy_LineCon *linecon,
Vint index,
Vint ix[2])
```

#### INPUT ARGUMENTS

```linecon      Pointer to LineCon object.
index        Line index
```

#### OUTPUT ARGUMENTS

```ix            Line connectivity
```

#### ERRORS

SYS_ERROR_VALUE is generated if an improper index is input.

#### DESCRIPTION

Query line connectivity.

#### NAME

vsy_LineConNum - query number of appended lines

#### C SPECIFICATION

```void vsy_LineConNum (vsy_LineCon *linecon,
Vint *numlin)
```

#### INPUT ARGUMENTS

```linecon      Pointer to LineCon object.
```

#### OUTPUT ARGUMENTS

```numlin       Largest appended line index
```

#### DESCRIPTION

Query for the largest appended line index.

#### NAME

vsy_LineConClear - remove all lines

#### C SPECIFICATION

```void vsy_LineConClear (vsy_LineCon *linecon)
```

#### INPUT ARGUMENTS

```linecon       Pointer to LineCon object.
```

```None
```

#### DESCRIPTION

Remove all lines.

#### NAME

vsy_LineConProcess - create strip information

#### C SPECIFICATION

```void vsy_LineConProcess (vsy_LineCon *linecon,
Vint *numstrip,
Vint *maxlength)
```

#### INPUT ARGUMENTS

```linecon      Pointer to LineCon object.
```

#### OUTPUT ARGUMENTS

```numstrip     Number of line strips
maxlength    Maximum length of any line strip
```

#### ERRORS

SYS_ERROR_OPERATION is generated if no lines defined. SYS_ERROR_MEMORY is generated if new storage was unable to be allocated.

#### DESCRIPTION

Create stripping information. The number of line strips created and the maximum number of points in any strip is returned. Note that the minimum number of points in a line strip is 2. Use vsy_LineConStrip to query for the connectivity of each strip.

#### NAME

vsy_LineConStrip - query line strips

#### C SPECIFICATION

```void vsy_LineConStrip (vsy_LineCon *linecon,
Vint istrip,
Vint *nix,
Vint it[],
Vint ix[])
```

#### INPUT ARGUMENTS

```linecon      Pointer to LineCon object.
istrip       Strip identifier
```

#### OUTPUT ARGUMENTS

```nix          Number of points in strip
it           Vector of line indices contained in strip
ix           Vector of point indices contained in strip
```

#### ERRORS

SYS_ERROR_OPERATION is generated if vsy_LineConProcess not called. SYS_ERROR_VALUE is generated if an improper istrip is input.

#### DESCRIPTION

Query for the number of points and line and point indices in a strip. The strips are numbered 1 <= istrip <= numstrip where numstrip is returned by the function vsy_LineConProcess. The number of line indices returned is nix-1. The number of points, nix, will not exceed the value of maxlength returned by vsy_LineConProcess.

#### NAME

vsy_LineConSetParami - set line stripping parameters

#### C SPECIFICATION

```void vsy_LineConSetParami (vsy_LineCon *linecon,
Vint ptype,
Vint iparam)
```

#### INPUT ARGUMENTS

```linecon      Pointer to LineCon object.
ptype        Type of parameter to set
=LINECON_MAXLENGTH       Maximum line strip point length
fparam       Specifies the integer value that ptype will be set to.
```

```None
```

#### ERRORS

SYS_ERROR_ENUM is generated if an improper ptype is specified.

#### DESCRIPTION

Set line stripping parameters. The LINECON_MAXLENGTH parameter is the maximum number of points which a line strip can contain. If a value of zero is specified then the line strip length is unlimited. The default LINECON_MAXLENGTH is 64.

## 7.5 Triangle Connectivity - TriCon

The TriCon module stores triangle connectivity and performs adjacency related functions such as triangle stripping for graphics applications.

• Begin and end an instance of an object, return object error flag
```*vsy_TriConBegin       - create an instance of a TriCon object
vsy_TriConEnd          - destroy an instance of a TriCon object
vsy_TriConError        - return TriCon object error flag
```
• Set and query triangles
```vsy_TriConDef          - define initial number of triangles
Inq          - inquire current triangle storage
vsy_TriConAppend       - append a triangle
vsy_TriConRef          - query triangle connectivity
vsy_TriConNum          - query number of appended triangles
vsy_TriConClear        - remove all triangles
vsy_TriConProcess      - create adjacency and strip information
vsy_TriConStrip        - query triangle strips
vsy_TriConSetParami    - set triangle stripping parameters
```
Instance a TriCon object using vsy_TriConBegin. Once a TriCon is instanced, an approximate number of triangles (0 is allowed) to be stored may be defined using vsy_TriConDef. This allocates an internal array for the storage of triangle information. As triangles are appended the TriCon module will adjust memory as required. The actual size of the allocated storage may be determined by calling vsy_TriConInq.

Each new triangle is appended by calling vsy_TriConAppend. Indices are assigned to the triangles as they are appended. The first triangle is assigned an index of 1. The index is incremented for each appended triangle. The triangle at a specified index may be found by calling vsy_TriConRef. The largest triangle index currently appended may be queried by calling vsy_TriConNum. The method vsy_TriConClear removes all triangles. Once all triangles have been entered, call vsy_TriConProcess to create triangle adjacency information which is required to perform subsequent triangle stripping or adjacency query operations. Query triangle adjacency information for a specified triangle index using vsy_TriConAdj. Query for triangle stripping information using vsy_TriConStrip. The maximum length of generated triangle strips may be defined using vsy_TriConSetParami.

## 7.6 Function Descriptions

The currently available TriCon functions are described in detail in this section.

#### NAME

*vsy_TriConBegin - create an instance of a TriCon object

#### C SPECIFICATION

```vsy_TriCon *vsy_TriConBegin ()
```

```None
```

#### FUNCTION RETURN VALUE

The function returns a pointer to the newly created TriCon object. If the object creation fails, NULL is returned.

#### DESCRIPTION

Create an instance of a TriCon object. Memory is allocated for the object private data and the pointer to the data is returned.

Destroy an instance of a TriCon object using

```     void vsy_TriConEnd (vsy_TriCon *tricon)
```

Return the current value of a TriCon object error flag using

```     Vint vsy_TriConError (vsy_TriCon *tricon)
```

#### NAME

vsy_TriConDef - define initial length of storage array

#### C SPECIFICATION

```void vsy_TriConDef (vsy_TriCon *tricon,
Vint numtri)
```

#### INPUT ARGUMENTS

```tricon       Pointer to TriCon object.
numtri       Estimated number of triangles to be held.
```

```None
```

#### ERRORS

SYS_ERROR_MEMORY is generated if new storage was unable to be allocated. SYS_ERROR_VALUE is generated if a negative numtri is specified.

#### DESCRIPTION

Suggest a number of triangles to be stored in TriCon. This is used to allocate the initial storage. If the number of appended triangles is greater than this initial estimate, storage space in dynamically expanded to hold the extra triangles. This function removes any previously entered triangles.

Find the current length of the internal storage of a TriCon using

```     void vsy_TriConInq (const vsy_TriCon *tricon,
Vint *numtri)
```

#### NAME

vsy_TriConAppend - append a triangle

#### C SPECIFICATION

```void vsy_TriConAppend (vsy_TriCon *tricon,
Vint ix[3])
```

#### INPUT ARGUMENTS

```tricon        Pointer to TriCon object.
ix            Triangle connectivity
```

```None
```

#### ERRORS

SYS_ERROR_MEMORY is generated if new storage was unable to be allocated.

#### DESCRIPTION

Append a triangle connectivity. Indices are assigned to the triangles as they are appended. The first triangle is assigned an index of 1. The index is incremented for each appended triangle. The triangle connectivity, ix, may contain integer connection indices which may be negative, zero, or positive.

#### NAME

vsy_TriConRef - query triangle connectivity

#### C SPECIFICATION

```void vsy_TriConRef (vsy_TriCon *tricon,
Vint index,
Vint ix[3])
```

#### INPUT ARGUMENTS

```tricon       Pointer to TriCon object.
index        Triangle index
```

#### OUTPUT ARGUMENTS

```ix            Triangle connectivity
```

#### ERRORS

SYS_ERROR_VALUE is generated if an improper index is input.

#### DESCRIPTION

Query triangle connectivity.

#### NAME

vsy_TriConNum - query number of appended triangles

#### C SPECIFICATION

```void vsy_TriConNum (vsy_TriCon *tricon,
Vint *numtri)
```

#### INPUT ARGUMENTS

```tricon       Pointer to TriCon object.
```

#### OUTPUT ARGUMENTS

```numtri       Largest appended triangle index
```

#### DESCRIPTION

Query for the largest appended triangle index.

#### NAME

vsy_TriConClear - remove all triangles

#### C SPECIFICATION

```void vsy_TriConClear (vsy_TriCon *tricon)
```

#### INPUT ARGUMENTS

```tricon        Pointer to TriCon object.
```

```None
```

#### DESCRIPTION

Remove all triangles.

#### NAME

vsy_TriConProcess - create adjacency and strip information

#### C SPECIFICATION

```void vsy_TriConProcess (vsy_TriCon *tricon,
Vint *numstrip,
Vint *maxlength)
```

#### INPUT ARGUMENTS

```tricon       Pointer to TriCon object.
```

#### OUTPUT ARGUMENTS

```numstrip     Number of triangle strips
maxlength    Maximum length of any triangle strip
```

#### ERRORS

SYS_ERROR_OPERATION is generated if no triangles defined. SYS_ERROR_MEMORY is generated if new storage was unable to be allocated.

#### DESCRIPTION

Create adjacency and stripping information. The number of triangle strips created and the maximum number of points in any strip is returned. Note that the minimum number of points in a triangle strip is 3. Use vsy_TriConStrip to query for the connectivity of each strip. Use vsy_TriConAdj to query for triangles adjacent to a specified triangle.

#### C SPECIFICATION

```void vsy_TriConAdj (vsy_TriCon *tricon,
Vint index,
Vint aix[3],
Vint aed[3])
```

#### INPUT ARGUMENTS

```tricon       Pointer to TriCon object.
index        Triangle index
```

#### OUTPUT ARGUMENTS

```aix          Indices of adjacent triangles
aed          Edge number of adjacent triangles
```

#### ERRORS

SYS_ERROR_OPERATION is generated if vsy_TriConProcess not called. SYS_ERROR_VALUE is generated if an improper index is input.

#### DESCRIPTION

Query for the triangles adjacent to a specified triangle index. The adjacent triangles are returned in aix across each edge of triangle index. A zero is returned in aix if there is no triangle across the edge. The edge number of the adjacent triangles are returned in aed. Edges are numbered (1,2,3). If there is no triangle across an edge, a zero is returned in aed.

#### NAME

vsy_TriConStrip - query triangle strips

#### C SPECIFICATION

```void vsy_TriConStrip (vsy_TriCon *tricon,
Vint istrip,
Vint *nix,
Vint it[],
Vint ix[])
```

#### INPUT ARGUMENTS

```tricon       Pointer to TriCon object.
istrip       Strip identifier
```

#### OUTPUT ARGUMENTS

```nix          Number of points in strip
it           Vector of triangle indices contained in strip
ix           Vector of point indices contained in strip
```

#### ERRORS

SYS_ERROR_OPERATION is generated if vsy_TriConProcess not called. SYS_ERROR_VALUE is generated if an improper istrip is input.

#### DESCRIPTION

Query for the number of points and triangle and point indices in a strip. The strips are numbered 1 <= istrip <= numstrip where numstrip is returned by the function vsy_TriConProcess. The number of triangle indices returned is nix-2. The number of points, nix, will not exceed the value of maxlength returned by vsy_TriConProcess.

#### NAME

vsy_TriConSetParami - set triangle stripping parameters

#### C SPECIFICATION

```void vsy_TriConSetParami (vsy_TriCon *tricon,
Vint ptype,
Vint iparam)
```

#### INPUT ARGUMENTS

```tricon       Pointer to TriCon object.
ptype        Type of parameter to set
=TRICON_MAXLENGTH       Maximum tristrip point length
fparam       Specifies the integer value that ptype will be set to.
```

```None
```

#### ERRORS

SYS_ERROR_ENUM is generated if an improper ptype is specified.

#### DESCRIPTION

Set triangle stripping parameters. The TRICON_MAXLENGTH parameter is the maximum number of points which a triangle strip can contain. The default TRICON_MAXLENGTH is 64.

## 7.7 Geometric Searching, Alternating Digital Tree - ADTree

The ADTree module performs general geometric searching functions. The tree may be used to store geometric points or geometric objects with extent. Geometric point and extent searches may then be performed.

• Begin and end an instance of an object, return object error flag
```*vsy_ADTreeBegin       - create an instance of a ADTree object
```
• Set and query lines
```vsy_ADTreeDef          - define initial number of objects and bounds
Inq          - inquire current number of objects and bounds
vsy_ADTreeRemove       - remove point or extent
vsy_ADTreeSetParamd    - set point search tolerance
```
Instance a ADTree object using vsy_ADTreeBegin. Once a ADTree is instanced, call vsy_ADTreeDef to define the geometric type, either point or extent, an approximate number of geometric objects to be inserted, and the fixed global extent bounds of all objects to be inserted.

New point entities are inserted by calling vsy_ADTreeInsertPoint. Point entities may only be inserted in a tree which has been initially defined as a point tree. New extent entities are inserted by calling vsy_ADTreeInsertExtent. Extent entities may only be inserted in a tree which has been initially defined as an extent tree. Each inserted point or extent is given an integer key name by the user. Any point or extent entity may be removed from the tree by calling vsy_ADTreeRemove with the integer key of the entity to be deleted.

The alternating digital tree may be queried for all entities which are contained or partially contained within the extent of an input object. Any tree may searched for either an input extent using vsy_ADTreeRefExtentInit or input point with associated tolerance bound using vsy_ADTreeRefPointInit. The point coordinate tolerance is specified using vsy_ADTreeSetParamd. Once the search is initiated, the contained entities are queried using repeated calls to either vsy_ADTreeRefExtentNext or vsy_ADTreeRefPointNext. The number of entity hits may be queried using vsy_ADTreeGetInteger.

## 7.8 Function Descriptions

The currently available ADTree functions are described in detail in this section.

#### C SPECIFICATION

```vsy_ADTree *vsy_ADTreeBegin ()
```

```None
```

#### FUNCTION RETURN VALUE

The function returns a pointer to the newly created ADTree object. If the object creation fails, NULL is returned.

#### DESCRIPTION

Create an instance of a ADTree object. Memory is allocated for the object private data and the pointer to the data is returned.

Destroy an instance of a ADTree object using

```     void vsy_ADTreeEnd (vsy_ADTree *adtree)
```

Return the current value of a ADTree object error flag using

```     Vint vsy_ADTreeError (vsy_ADTree *adtree)
```

#### NAME

vsy_ADTreeDef - define initial length of storage array

#### C SPECIFICATION

```void vsy_ADTreeDef (vsy_ADTree *adtree,
Vint type,
Vint len,
Vdouble xmin[3],
Vdouble xmax[3])
```

#### INPUT ARGUMENTS

```adtree       Pointer to ADTree object.
type         Entity type
len          Estimated number of entities to be held.
xmin         Minimum x,y,z coordinates of global extent
xmax         Maximum x,y,z coordinates of global extent
```

```None
```

#### ERRORS

SYS_ERROR_ENUM is generated if an improper type is specified.

#### DESCRIPTION

Define the entity type to be held in the tree and the global coordinate extents of all entities to be inserted. Also an approximate number of entities may be specified. Only point entities may be inserted in a ADTREE_POINT tree, and only extent entities may be inserted in a ADTREE_EXTENT tree. This function removes any previously entered entities.

Find the current defined values of an ADTree using

```     void vsy_ADTreeInq (const vsy_ADTree *adtree,
Vint *type,
Vint *len,
Vdouble xmin[3],
Vdouble xmax[3])
```

#### C SPECIFICATION

```void vsy_ADTreeGetInteger (vsy_ADTree *adtree,
Vint type,
Vint iparam[])
```

#### INPUT ARGUMENTS

```adtree        Pointer to ADTree object.
type         Type of integer information to query
=ADTREE_NUMHITS         Get number of contained entities
```

#### OUTPUT ARGUMENTS

```iparam       Returned integer information
```

#### ERRORS

VIS_ERROR_ENUM is generated if an improper type is specified.

#### DESCRIPTION

Query for integer search information. This function is useful for determining the number of contained entities found during a call to vsy_ADTreeRefExtentInit or vsy_ADTreeRefExtentNext.

#### C SPECIFICATION

```void vsy_ADTreeInsertExtent (vsy_ADTree *adtree,
Vint key,
Vdouble xmin[3],
Vdouble xmax[3])
```

#### INPUT ARGUMENTS

```adtree       Pointer to ADTree object.
key          Entity key
xmin         Minimum coordinate extent of entity
xmax         Maximum coordinate extent of entity
```

```None
```

#### ERRORS

SYS_ERROR_OPERATION is generated if the tree is not an extent tree. SYS_ERROR_VALUE is generated if an improper key is input.

#### DESCRIPTION

Insert a geometric entity with extent defined by the points xmin and xmax. The user defined key must be not equal to zero.

#### C SPECIFICATION

```void vsy_ADTreeInsertPoint (vsy_ADTree *adtree,
Vint key,
Vdouble x[3])
```

#### INPUT ARGUMENTS

```adtree       Pointer to ADTree object.
key          Entity key
x            coordinate location of point
```

```None
```

#### ERRORS

SYS_ERROR_OPERATION is generated if the tree is not an point tree. SYS_ERROR_VALUE is generated if an improper key is input.

#### DESCRIPTION

Insert a point entity at coordinate location x. The user defined key must be not equal to zero.

#### C SPECIFICATION

```void vsy_ADTreeRefExtentInit (vsy_ADTree *adtree,
Vdouble xmin[3],
Vdouble xmax[3])
```

#### INPUT ARGUMENTS

```adtree       Pointer to ADTree object.
xmin         Minimum coordinate extent of query
xmax         Maximum coordinate extent of query
```

```None
```

#### DESCRIPTION

Initiate geometry search for all entities contained or partially contained within the input extent, xmin and xmax. The number of "hits" may be queried using vsy_ADTreeGetInteger. Each entity key which satisfies the query is returned using successive calls to vsy_ADTreeRefExtentNext. Input extent searches may be performed on either point or extent trees.

#### C SPECIFICATION

```void vsy_ADTreeRefExtentNext (vsy_ADTree *adtree,
Vint *key)
```

#### INPUT ARGUMENTS

```adtree       Pointer to ADTree object.
```

#### OUTPUT ARGUMENTS

```key          Entity key
```

#### DESCRIPTION

Query for entity indices which satisfied the search initiated by a previous call to vsy_ADTreeRefExtentInit. Each successive call returns an entity key until a key of zero is returned, signaling that all entities have been queried.

#### C SPECIFICATION

```void vsy_ADTreeRefPointInit (vsy_ADTree *adtree,
Vdouble x[3])
```

#### INPUT ARGUMENTS

```adtree       Pointer to ADTree object.
x            Coordinate center of query
```

```None
```

#### DESCRIPTION

Initiate geometry search for all entities contained or partially contained within a tolerance extent centered on the input point, x. The tolerance is specified using vsy_ADTreeSetParamd. The tolerance extent is plus and minus the tolerance about point x. The number of "hits" may be queried using vsy_ADTreeGetInteger. Each entity key which satisfies the query is returned using successive calls to vsy_ADTreeRefPointNext. Input point searches may be performed on either point or extent trees.

#### C SPECIFICATION

```void vsy_ADTreeRefPointNext (vsy_ADTree *adtree,
Vint *key)
```

#### INPUT ARGUMENTS

```adtree       Pointer to ADTree object.
```

#### OUTPUT ARGUMENTS

```key          Entity key
```

#### DESCRIPTION

Query for entity indices which satisfied the search initiated by a previous call to vsy_ADTreeRefPointInit. Each successive call returns an entity key until a key of zero is returned, signalling that all entities have been queried.

#### NAME

vsy_ADTreeRemove - remove point or extent

#### C SPECIFICATION

```void vsy_ADTreeRemove (vsy_ADTree *adtree,
Vint key)
```

#### INPUT ARGUMENTS

```adtree       Pointer to ADTree object.
key          Entity key
```

```None
```

#### ERRORS

SYS_ERROR_VALUE is generated if an improper key is input.

#### DESCRIPTION

Remove an entity key. If the entity key does not exist then no operation is performed.

#### NAME

vsy_ADTreeSetParamd - set point search tolerance

#### C SPECIFICATION

```void vsy_ADTreeSetParamd (vsy_ADTree *adtree,
Vint ptype,
Vdouble dparam)
```

#### INPUT ARGUMENTS

```adtree       Pointer to ADTree object.
ptype        Type of parameter to set
dparam       Specifies the value that ptype will be set to.
```

```None
```

#### ERRORS

SYS_ERROR_ENUM is generated if an improper ptype is specified.

#### DESCRIPTION

Set searching parameters. The ADTREE_TOLERANCE parameter specifies the coordinate tolerance to be used in point searches using vsy_ADTreeRefPointInit. The default ADTREE_TOLERANCE is 0001.

## 7.9 Geometric Predicates - Pred

The Pred module performs exact geometric computations returning results to machine double precision. It may be used to determine whether a point is inside, on or outside a sphere or circle and whether a triangle or tetrahedron volume is positive, zero or negative. Exact arithmetic may be defeated by the use of internal extended precision floating-point registers. Various common compiler/computer combinations which may defeat exact arithmetic have been identified and coding exists in Pred to configure the platforms corectly. These compilers include Windows Visual Studio, LINUX gcc and Intel compilers.

• Begin and end an instance of an object, return object error flag
```*vsy_PredBegin       - create an instance of a Pred object
vsy_PredEnd          - destroy an instance of a Pred object
vsy_PredError        - return Pred object error flag
```
• Query lines
```vsy_PredExact        - check to determine if exact arithmetic
vsy_PredPushFPU      - push FPU state and set
vsy_PredPopFPU       - pop (restore) pushed FPU state
vsy_PredIncircle     - determines whether point is inside circle
vsy_PredInsphere     - determines whether point is inside sphere
vsy_PredOrient2d     - computes orientation of a triangle
vsy_PredOrient3d     - computes orientation of a tetrahedron
vsy_PredIntersectLineTri - computes line-triangle intersection
```
Instance a Pred object using vsy_PredBegin. Once a Pred is instanced, call a predicate function such as vsy_PredOrient3d. Call the function vsy_PredPushFPU to save the current FPU state and set that required for the exact arithmetic computations. Note that the function vsy_PredExact should be called after the call to vsy_PredPushFPU to determine whether exact arithmetic is able to be performed. Call vsy_PredPopFPU to restore the saved FPU state. Exact arithmetic computations should not be performed after this call. No alterations of the FPU state can be allowed between the calls to vsy_PredPushFPU and vsy_PredPopFPU.

The Pred object is used extensively by certain mesh generation models in VisTools/Mesh, in particular the 3D volume meshing modules and the 2D plane meshing modules.

## 7.10 Function Descriptions

The currently available Pred functions are described in detail in this section.

#### NAME

*vsy_PredBegin - create an instance of a Pred object

#### C SPECIFICATION

```vsy_Pred *vsy_PredBegin ()
```

```None
```

#### FUNCTION RETURN VALUE

The function returns a pointer to the newly created Pred object. If the object creation fails, NULL is returned.

#### DESCRIPTION

Create an instance of a Pred object. Memory is allocated for the object private data and the pointer to the data is returned.

Destroy an instance of a Pred object using

```     void vsy_PredEnd (vsy_Pred *pred)
```

Return the current value of a Pred object error flag using

```     Vint vsy_PredError (vsy_Pred *pred)
```

#### NAME

vsy_PredExact - check to determine if exact arithmetic

#### C SPECIFICATION

```void vsy_PredExact (vsy_Pred *pred,
Vint *pass)
```

#### INPUT ARGUMENTS

```pred       Pointer to Pred object.
```

#### OUTPUT ARGUMENTS

```pass      x=SYS_ON        Able to do exact arithmetic
=SYS_OFF       Unable to do exact arithmetic
```

#### DESCRIPTION

Check if exact arithmetic is able to be performed. This is dependent upon compiler options. Pred is able to configure itself properly for most common compilers/platforms.

#### NAME

vsy_PredPushFPU - push FPU state and set

#### C SPECIFICATION

```void vsy_PredPushFPU (vsy_Pred *pred)
```

#### INPUT ARGUMENTS

```pred       Pointer to Pred object.
```

```None
```

#### DESCRIPTION

Save current FPU state and that required to perform exact arithmetic. Use vsy_PredPopFPU to restore the saved FPU state. Exact arithmetic computations may only be performed between calls to vsy_PredPushFPU and vsy_PredPopFPU.

#### NAME

vsy_PredPopFPU - pop (restore) pushed FPU state

#### C SPECIFICATION

```void vsy_PredPopFPU (vsy_Pred *pred)
```

#### INPUT ARGUMENTS

```pred       Pointer to Pred object.
```

```None
```

#### ERRORS

SYS_ERROR_OPERATION is generated if an FPU state has not been pushed.
```None
```

#### DESCRIPTION

Restore saved FPU state. Exact arithmetic computations may not be performed until vsy_PredPushFPU is called.

#### NAME

vsy_PredIncircle - determines whether point is inside circle

#### C SPECIFICATION

```Vdouble vsy_PredIncircle (vsy_Pred *pred,
Vdouble a[2],
Vdouble b[2],
Vdouble c[2],
Vdouble d[2])
```

#### INPUT ARGUMENTS

```pred       Pointer to Pred object.
a          Two-dimensional coordinates of first point in circle
b          Two-dimensional coordinates of second point in circle
c          Two-dimensional coordinates of third point in circle
e          Point whose position relative to circle is to be determined
```

```None
```

```None
```

#### DESCRIPTION

Returns a double precision number that indicates the position of point d relative to the circle in the x-y plane defined by a-b-c. If greater than zero then point d is inside the circle; if equal to zero then it is on the circle; and if less than zero it is outside the circle.

#### NAME

vsy_PredInsphere - determines whether point is inside sphere

#### C SPECIFICATION

```Vdouble vsy_PredInsphere (vsy_Pred *pred,
Vdouble a[3],
Vdouble b[3],
Vdouble c[3],
Vdouble d[3],
Vdouble e[3])
```

#### INPUT ARGUMENTS

```pred       Pointer to Pred object.
a          Coordinates of first point in sphere
b          Coordinates of second point in sphere
c          Coordinates of third point in sphere
d          Coordinates of fourth point in sphere
e          Point whose position relative to sphere is to be determined
```

```None
```

```None
```

#### DESCRIPTION

Returns a double precision number that indicates the position of point e relative to the sphere defined by a-b-c-d. If greater than zero then point e is inside the sphere; if equal to zero then it is on the sphere; and if less than zero it is outside the sphere.

#### NAME

vsy_PredOrient2d - Computes orientation of a triangle

#### C SPECIFICATION

```Vdouble vsy_PredOrient2d (vsy_Pred *pred,
Vdouble a[2],
Vdouble b[2],
Vdouble c[2])
```

#### INPUT ARGUMENTS

```pred        Pointer to Pred object.
a           Two-dimensional coordinates of first point in triangle
b           Two-dimensional coordinates of second point in triangle
c           Two-dimensional coordinates of third point in triangle
```

```None
```

```None
```

#### DESCRIPTION

Returns a double precision number that reflects the orientation of the triangle. If greater than zero, then a-b-c define a triangle where the cross-product ab X ac points in the positive z-direction; if equal to zero, then then the cross product is zero and the triangle is degenerate; if less than zero then the cross-product points in the negative z-direction and the element is inverted.

#### NAME

vsy_PredOrient3d - Computes orientation of a tetrahedron

#### C SPECIFICATION

```Vdouble vsy_PredOrient3d (vsy_Pred *pred,
Vdouble a[3],
Vdouble b[3],
Vdouble c[3],
Vdouble d[3])
```

#### INPUT ARGUMENTS

```pred        Pointer to Pred object.
a           Coordinates of first point in tetrahedron
b           Coordinates of second point in tetrahedron
c           Coordinates of third point in tetrahedron
d           Coordinates of fourth point in tetrahedron
```

```None
```

```None
```

#### DESCRIPTION

Returns a double precision number that reflects the orientation of the tetrahedron. If greater than zero, then a-b-c-d define a proper tetrahedron; if equal to zero, then a-b-c-d define a flat element of zero volume; if less than zero then the element is inverted.

#### NAME

vsy_PredIntersectLineTri - computes line-triangle intersection

#### C SPECIFICATION

```void vsy_PredIntersectLineTri (vsy_Pred *pred,
Vdouble xt[3][3],
Vdouble xl[2][3],
Vint *code,
Vint *ient,
Vint *ierr)
```

#### INPUT ARGUMENTS

```pred        Pointer to Pred object.
xt          Coordinates of triangle
xl          Coordinates of line
```

#### OUTPUT ARGUMENTS

```code        Intersection code
=0        No intersection
=1        Intersects inside triangle
=2        Intersects on edge
=3        Intersects on vertex
=-1       Intersects and is parallel
ient        Intersection edge or vertex index (one based)
ierr        Error flag
=0        No error
=1        Triangle is zero area
```

```None
```

#### DESCRIPTION

Compute the intersection status of a line with a triangle.