Table of Contents

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.

Table of Contents

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.

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.

Table of Contents

7.2 Function Descriptions

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

Table of Contents , VertLoc

NAME

*vsy_VertLocBegin - create an instance of an VertLoc object

C SPECIFICATION

vsy_VertLoc *vsy_VertLocBegin ()

ARGUMENTS

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)

Table of Contents , 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.

OUTPUT ARGUMENTS

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)

Table of Contents , VertLoc

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

OUTPUT ARGUMENTS

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.

Table of Contents , VertLoc

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.

Table of Contents , VertLoc

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.

Table of Contents , VertLoc

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.

Table of Contents , VertLoc

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.

Table of Contents , VertLoc

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.

Table of Contents , VertLoc

NAME

vsy_VertLocClear - remove all points

C SPECIFICATION

void vsy_VertLocClear (vsy_VertLoc *vertloc)

INPUT ARGUMENTS

vertloc      Pointer to VertLoc object.

OUTPUT ARGUMENTS

None

DESCRIPTION

Remove all defined points. The current attributes remain unchanged.

Table of Contents , VertLoc

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.

Table of Contents , VertLoc

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.

Table of Contents , VertLoc

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.

Table of Contents , VertLoc

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

OUTPUT ARGUMENTS

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.

Table of Contents , VertLoc

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

OUTPUT ARGUMENTS

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.

Table of Contents , VertLoc

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

OUTPUT ARGUMENTS

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.

Table of Contents , VertLoc

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.

OUTPUT ARGUMENTS

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 .

Table of Contents , VertLoc

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

OUTPUT ARGUMENTS

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.

Table of Contents

7.3 Line Connectivity - LineCon

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

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.

Table of Contents

7.4 Function Descriptions

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

Table of Contents , LineCon

NAME

*vsy_LineConBegin - create an instance of a LineCon object

C SPECIFICATION

vsy_LineCon *vsy_LineConBegin ()

ARGUMENTS

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)

Table of Contents , 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.

OUTPUT ARGUMENTS

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)

Table of Contents , LineCon

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

OUTPUT ARGUMENTS

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.

Table of Contents , LineCon

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.

Table of Contents , LineCon

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.

Table of Contents , LineCon

NAME

vsy_LineConClear - remove all lines

C SPECIFICATION

void vsy_LineConClear (vsy_LineCon *linecon)

INPUT ARGUMENTS

linecon       Pointer to LineCon object.

OUTPUT ARGUMENTS

None

DESCRIPTION

Remove all lines.

Table of Contents , LineCon

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.

Table of Contents , LineCon

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.

Table of Contents , LineCon

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.

OUTPUT ARGUMENTS

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.

Table of Contents

7.5 Triangle Connectivity - TriCon

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

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.

Table of Contents

7.6 Function Descriptions

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

Table of Contents , TriCon

NAME

*vsy_TriConBegin - create an instance of a TriCon object

C SPECIFICATION

vsy_TriCon *vsy_TriConBegin ()

ARGUMENTS

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)

Table of Contents , 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.

OUTPUT ARGUMENTS

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)

Table of Contents , TriCon

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

OUTPUT ARGUMENTS

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.

Table of Contents , TriCon

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.

Table of Contents , TriCon

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.

Table of Contents , TriCon

NAME

vsy_TriConClear - remove all triangles

C SPECIFICATION

void vsy_TriConClear (vsy_TriCon *tricon)

INPUT ARGUMENTS

tricon        Pointer to TriCon object.

OUTPUT ARGUMENTS

None

DESCRIPTION

Remove all triangles.

Table of Contents , TriCon

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.

Table of Contents , TriCon

NAME

vsy_TriConAdj - query triangle adjacency information

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.

Table of Contents , TriCon

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.

Table of Contents , TriCon

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.

OUTPUT ARGUMENTS

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.

Table of Contents

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.

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.

Table of Contents

7.8 Function Descriptions

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

Table of Contents , ADTree

NAME

*vsy_ADTreeBegin - create an instance of a ADTree object

C SPECIFICATION

vsy_ADTree *vsy_ADTreeBegin ()

ARGUMENTS

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)

Table of Contents , 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
             =ADTREE_POINT            Point entities
             =ADTREE_EXTENT           Extent entities
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

OUTPUT ARGUMENTS

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])

Table of Contents , ADTree

NAME

vsy_ADTreeGetInteger - get integer information

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.

Table of Contents , ADTree

NAME

vsy_ADTreeInsertExtent - insert extent

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

OUTPUT ARGUMENTS

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.

Table of Contents , ADTree

NAME

vsy_ADTreeInsertPoint - insert point

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

OUTPUT ARGUMENTS

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.

Table of Contents , ADTree

NAME

vsy_ADTreeRefExtentInit - initiate extent search

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

OUTPUT ARGUMENTS

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.

Table of Contents , ADTree

NAME

vsy_ADTreeRefExtentNext - query entities

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.

Table of Contents , ADTree

NAME

vsy_ADTreeRefPointInit - initiate point search

C SPECIFICATION

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

INPUT ARGUMENTS

adtree       Pointer to ADTree object.
x            Coordinate center of query

OUTPUT ARGUMENTS

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.

Table of Contents , ADTree

NAME

vsy_ADTreeRefPointNext - query entities

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.

Table of Contents , ADTree

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

OUTPUT ARGUMENTS

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.

Table of Contents , ADTree

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
             =ADTREE_TOLERANCE        Set point search tolerance
dparam       Specifies the value that ptype will be set to.

OUTPUT ARGUMENTS

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.

Table of Contents

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.

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.

Table of Contents

7.10 Function Descriptions

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

Table of Contents , Pred

NAME

*vsy_PredBegin - create an instance of a Pred object

C SPECIFICATION

vsy_Pred *vsy_PredBegin ()

ARGUMENTS

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)

Table of Contents , 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.

Table of Contents , Pred

NAME

vsy_PredPushFPU - push FPU state and set

C SPECIFICATION

void vsy_PredPushFPU (vsy_Pred *pred)

INPUT ARGUMENTS

pred       Pointer to Pred object.

OUTPUT ARGUMENTS

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.

Table of Contents , Pred

NAME

vsy_PredPopFPU - pop (restore) pushed FPU state

C SPECIFICATION

void vsy_PredPopFPU (vsy_Pred *pred)

INPUT ARGUMENTS

pred       Pointer to Pred object.

OUTPUT ARGUMENTS

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.

Table of Contents , Pred

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

OUTPUT ARGUMENTS

None

ERRORS

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.

Table of Contents , Pred

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

OUTPUT ARGUMENTS

None

ERRORS

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.

Table of Contents , Pred

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

OUTPUT ARGUMENTS

None

ERRORS

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.

Table of Contents , Pred

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

OUTPUT ARGUMENTS

None

ERRORS

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.

Table of Contents , Pred

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

ERRORS

None

DESCRIPTION

Compute the intersection status of a line with a triangle.