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

CEETRON SAM 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.

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.1.1. Function Descriptions

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

vsy_VertLoc *vsy_VertLocBegin(void)

create an instance of a VertLoc object

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)

Returns:

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

void vsy_VertLocEnd(vsy_VertLoc *p)

destroy an instance of a VertLoc object

See vsy_VertLocBegin()

Vint vsy_VertLocError(vsy_VertLoc *p)

return the current value of a VertLoc object error flag

See vsy_VertLocBegin()

void vsy_VertLocDef(vsy_VertLoc *p, Vint numvert)

define initial number of points

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)

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.

Parameters:

  • p – Pointer to VertLoc object.

  • numvert – Estimated number of points to be held.

void vsy_VertLocInq(const vsy_VertLoc *p, Vint *numvert)

find the current length of the internal storage

See vsy_VertLocDef()

void vsy_VertLocSetParamf(vsy_VertLoc *p, Vint ptype, Vfloat fparam)

set floating point merging parameters

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 .

Errors

SYS_ERROR_ENUM is generated if an improper ptype is specified.

Parameters:

  • p – Pointer to VertLoc object.

  • ptype – Type of parameter to set 

    x=VERTLOC_TOL            Coordinate tolerance
 =VERTLOC_NTOL           Normal vector tolerance in degrees

  • fparam – Specifies the floating value that ptype will be set to.

void vsy_VertLocSetParami(vsy_VertLoc *p, Vint ptype, Vint iparam)

set integer merging parameters

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.

Errors

SYS_ERROR_ENUM is generated if an improper ptype is specified.

Parameters:

  • p – Pointer to VertLoc object.

  • ptype – Type of parameter to set 

    x=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

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

set current color attribute

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.

Errors

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

Parameters:

  • p – Pointer to VertLoc object.

  • c – RGB color components

void vsy_VertLocSetTrans(vsy_VertLoc *p, Vfloat t)

set current transparency attribute

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.

Errors

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

Parameters:

  • p – Pointer to VertLoc object.

  • t – Transparency

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

set current normal vector attribute

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.

Errors

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

Parameters:

  • p – Pointer to VertLoc object.

  • v – Normal vector

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

insert point at specified index

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.

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.

Parameters:

  • p – Pointer to VertLoc object.

  • index – Point index

  • x – Coordinates of point

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

query point coordinates

Query coordinates of point.

Errors

SYS_ERROR_VALUE is generated if an improper index is input.

Parameters:

  • p – Pointer to VertLoc object.

  • index – Point index

  • x – [out] Coordinates of point

void vsy_VertLocNum(vsy_VertLoc *p, Vint *numvert)

query largest inserted point index

Query for the largest inserted point index.

Parameters:

  • p – Pointer to VertLoc object.

  • numvert – [out] Largest inserted point index

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

query point color

Query color RGB components of point.

Errors

SYS_ERROR_VALUE is generated if an improper index is input.

Parameters:

  • p – Pointer to VertLoc object.

  • index – Point index

  • c – [out] Color RGB triple of point

void vsy_VertLocTrans(vsy_VertLoc *p, Vint index, Vfloat *t)

query point transparency

Query transparency of point.

Errors

SYS_ERROR_VALUE is generated if an improper index is input.

Parameters:

  • p – Pointer to VertLoc object.

  • index – Point index

  • t – [out] Transparency of point

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

query point normal vector

Query normal vector of point.

Errors

SYS_ERROR_VALUE is generated if an improper index is input.

Parameters:

  • p – Pointer to VertLoc object.

  • index – Point index

  • v – [out] Normal vector of point

void vsy_VertLocClear(vsy_VertLoc *p)

remove all points

Remove all defined points. The current attributes remain unchanged.

Parameters:

p – Pointer to VertLoc object.

void vsy_VertLocMerge(vsy_VertLoc *p, Vint *numunique, Vint *maxlocate)

merge coincident points

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.

Errors

  • SYS_ERROR_OPERATION is generated if no points are defined.

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

Parameters:

  • p – Pointer to VertLoc object.

  • numunique – [out] Number of unique coincident point sets

  • maxlocate – [out] Maximum number of points in any unique set

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

query unique sets of coincident points

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().

Errors

  • SYS_ERROR_OPERATION is generated if vsy_VertLocMerge() not called.

  • SYS_ERROR_VALUE is generated if an improper iunique is input.

Parameters:

  • p – Pointer to VertLoc object.

  • iunique – Unique set identifier

  • nix – [out] Number of points in unique set

  • ix – [out] Vector of point indices contained in unique set

void vsy_VertLocLowest(vsy_VertLoc *p, Vint index, Vint *iunique, Vint *lowestindex)

query lowest index in a unique set

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.

Errors

  • SYS_ERROR_OPERATION is generated if vsy_VertLocMerge() not called.

  • SYS_ERROR_VALUE is generated if an improper index is input.

Parameters:

  • p – Pointer to VertLoc object.

  • index – Point index

  • iunique – [out] Unique set containing index

  • lowestindex – [out] Lowest point index contained in set iunique.

7.2. 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().

7.2.1. Function Descriptions

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

vsy_LineCon *vsy_LineConBegin(void)

create an instance of a LineCon object

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)

Returns:

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

void vsy_LineConEnd(vsy_LineCon *p)

destroy an instance of a LineCon object

See vsy_LineConBegin()

Vint vsy_LineConError(vsy_LineCon *p)

return the current value of a LineCon object error flag

See vsy_LineConBegin()

void vsy_LineConDef(vsy_LineCon *p, Vint numline)

define initial length of storage array

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)

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.

Parameters:

  • p – Pointer to LineCon object.

  • numline – Estimated number of lines to be held.

void vsy_LineConInq(const vsy_LineCon *p, Vint *numline)

find the current length of the internal storage

See vsy_LineConDef()

void vsy_LineConSetParami(vsy_LineCon *p, Vint ptype, Vint iparam)

set line stripping parameters

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.

Errors

SYS_ERROR_ENUM is generated if an improper ptype is specified.

Parameters:

  • p – Pointer to LineCon object.

  • ptype – Type of parameter to set 

    x=LINECON_MAXLENGTH       Maximum line strip point length

  • iparam – Specifies the integer value that ptype will be set to.

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

append a line

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.

Errors

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

Parameters:

  • p – Pointer to LineCon object.

  • ix – Line connectivity

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

query line connectivity

Query line connectivity.

Errors

SYS_ERROR_VALUE is generated if an improper index is input.

Parameters:

  • p – Pointer to LineCon object.

  • index – Line index

  • ix – [out] Line connectivity

void vsy_LineConNum(vsy_LineCon *p, Vint *numlin)

query number of appended lines

Query for the largest appended line index.

Parameters:

  • p – Pointer to LineCon object.

  • numlin – [out] Largest appended line index

void vsy_LineConClear(vsy_LineCon *p)

remove all lines

Remove all lines.

Parameters:

p – Pointer to LineCon object.

void vsy_LineConProcess(vsy_LineCon *p, Vint *numstrip, Vint *maxlength)

create strip information

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.

Errors

  • SYS_ERROR_OPERATION is generated if no lines defined.

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

Parameters:

  • p – Pointer to LineCon object.

  • numstrip – [out] Number of line strips

  • maxlength – [out] Maximum length of any line strip

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

query line strips

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().

Errors

  • SYS_ERROR_OPERATION is generated if vsy_LineConProcess() not called.

  • SYS_ERROR_VALUE is generated if an improper istrip is input.

Parameters:

  • p – Pointer to LineCon object.

  • istrip – Strip identifier

  • nix – [out] Number of points in strip

  • it – [out] Vector of line indices contained in strip

  • ix – [out] Vector of point indices contained in strip

7.3. 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().

7.3.1. Function Descriptions

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

vsy_TriCon *vsy_TriConBegin(void)

create an instance of a TriCon object

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)

Returns:

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

void vsy_TriConEnd(vsy_TriCon *p)

destroy an instance of a TriCon object

See vsy_TriConBegin()

Vint vsy_TriConError(vsy_TriCon *p)

return the current value of a TriCon object error flag

See vsy_TriConBegin()

void vsy_TriConDef(vsy_TriCon *p, Vint numtri)

define initial length of storage array

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)

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.

Parameters:

  • p – Pointer to TriCon object.

  • numtri – Estimated number of triangles to be held.

void vsy_TriConInq(const vsy_TriCon *p, Vint *numtri)

find the current length of the internal storage

See vsy_TriConDef()

void vsy_TriConSetParami(vsy_TriCon *p, Vint ptype, Vint iparam)

set triangle stripping parameters

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.

Errors

SYS_ERROR_ENUM is generated if an improper ptype is specified.

Parameters:

  • p – Pointer to TriCon object.

  • ptype – Type of parameter to set 

    x=TRICON_MAXLENGTH       Maximum tristrip point length

  • iparam – Specifies the integer value that ptype will be set to.

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

append a triangle

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.

Errors

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

Parameters:

  • p – Pointer to TriCon object.

  • ix – Triangle connectivity

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

query triangle connectivity

Query triangle connectivity.

Errors

SYS_ERROR_VALUE is generated if an improper index is input.

Parameters:

  • p – Pointer to TriCon object.

  • index – Triangle index

  • ix – [out] Triangle connectivity

void vsy_TriConNum(vsy_TriCon *p, Vint *numtri)

query number of appended triangles

Query for the largest appended triangle index.

Parameters:

  • p – Pointer to TriCon object.

  • numtri – [out] Largest appended triangle index

void vsy_TriConClear(vsy_TriCon *p)

remove all triangles

Remove all triangles.

Parameters:

p – Pointer to TriCon object.

void vsy_TriConProcess(vsy_TriCon *p, Vint *numstrip, Vint *maxlength)

create adjacency and strip information

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.

Errors

  • SYS_ERROR_OPERATION is generated if no triangles defined.

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

Parameters:

  • p – Pointer to TriCon object.

  • numstrip – [out] Number of triangle strips

  • maxlength – [out] Maximum length of any triangle strip

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

query triangle strips

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().

Errors

  • SYS_ERROR_OPERATION is generated if vsy_TriConProcess() not called.

  • SYS_ERROR_VALUE is generated if an improper istrip is input.

Parameters:

  • p – Pointer to TriCon object.

  • istrip – Strip identifier

  • nix – [out] Number of points in strip

  • it – [out] Vector of triangle indices contained in strip

  • ix – [out] Vector of point indices contained in strip

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

query triangle adjacency information

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.

Errors

  • SYS_ERROR_OPERATION is generated if vsy_TriConProcess() not called.

  • SYS_ERROR_VALUE is generated if an improper index is input.

Parameters:

  • p – Pointer to TriCon object.

  • index – Triangle index

  • aix – [out] Indices of adjacent triangles

  • aed – [out] Edge number of adjacent triangles

7.4. 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().

7.4.1. Function Descriptions

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

vsy_ADTree *vsy_ADTreeBegin(void)

create an instance of an ADTree object

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)

Returns:

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

void vsy_ADTreeEnd(vsy_ADTree *p)

destroy an instance of an ADTree object

See vsy_ADTreeBegin()

Vint vsy_ADTreeError(vsy_ADTree *p)

return the current value of a ADTree object error flag using

See vsy_ADTreeBegin()

void vsy_ADTreeDef(vsy_ADTree *p, Vint type, Vdouble xmin[3], Vdouble xmax[3])

define initial length of storage array

Define the entity type to be held in the tree and the global coordinate extents of all entities to be inserted. 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])

Errors

SYS_ERROR_ENUM is generated if an improper type is specified.

Parameters:

  • p – Pointer to ADTree object.

  • type – Entity type 

    x=ADTREE_POINT            Point entities
 =ADTREE_EXTENT           Extent entities

  • xmin – Minimum x,y,z coordinates of global extent

  • xmax – Maximum x,y,z coordinates of global extent

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

find the current defined values

See vsy_ADTreeDef()

void vsy_ADTreeSetParamd(vsy_ADTree *p, Vint ptype, Vdouble dparam)

set point search tolerance

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.

Errors

SYS_ERROR_ENUM is generated if an improper ptype is specified.

Parameters:

  • p – Pointer to ADTree object.

  • ptype – Type of parameter to set 

    x=ADTREE_TOLERANCE        Set point search tolerance

  • dparam – Specifies the value that ptype will be set to.

void vsy_ADTreeInsertPoint(vsy_ADTree *p, Vint key, Vdouble x[])

insert point

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

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.

Parameters:

  • p – Pointer to ADTree object.

  • key – Entity key

  • x – coordinate location of point

void vsy_ADTreeInsertExtent(vsy_ADTree *p, Vint key, Vdouble xmin[], Vdouble xmax[])

insert extent

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

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.

Parameters:

  • p – Pointer to ADTree object.

  • key – Entity key

  • xmin – Minimum coordinate extent of entity

  • xmax – Maximum coordinate extent of entity

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

initiate point search

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.

Parameters:

  • p – Pointer to ADTree object.

  • x – Coordinate center of query

void vsy_ADTreeRefPointNext(vsy_ADTree *p, Vint *key)

query entities

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, signaling that all entities have been queried.

Parameters:

  • p – Pointer to ADTree object.

  • key – [out] Entity key

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

initiate extent search

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.

Parameters:

  • p – Pointer to ADTree object.

  • xmin – Minimum coordinate extent of query

  • xmax – Maximum coordinate extent of query

void vsy_ADTreeRefExtentNext(vsy_ADTree *p, Vint *key)

query entities

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.

Parameters:

  • p – Pointer to ADTree object.

  • key – [out] Entity key

void vsy_ADTreeRemove(vsy_ADTree *p, Vint key)

remove point or extent

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

Errors

SYS_ERROR_VALUE is generated if an improper key is input.

Parameters:

  • p – Pointer to ADTree object.

  • key – Entity key

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

get integer information

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().

Errors

VIS_ERROR_ENUM is generated if an improper type is specified.

Parameters:

  • p – Pointer to ADTree object.

  • type – Type of integer information to query 

    x=ADTREE_NUMHITS         Get number of contained entities

  • iparam – [out] Returned integer information

7.5. 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.

7.5.1. Function Descriptions

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

vsy_Pred *vsy_PredBegin(void)

create an instance of a Pred object

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)

Returns:

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

void vsy_PredEnd(vsy_Pred *p)

destroy an instance of a Pred object

See vsy_PredBegin()

Vint vsy_PredError(vsy_Pred *p)

return the current value of a Pred object error flag

See vsy_PredBegin()

void vsy_PredPushFPU(vsy_Pred *p)

push FPU state and set

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().

Parameters:

p – Pointer to Pred object.

void vsy_PredPopFPU(vsy_Pred *p)

pop (restore) pushed FPU state

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

Errors

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

Parameters:

p – Pointer to Pred object.

Vdouble vsy_PredOrient2d(vsy_Pred *p, Vdouble *a, Vdouble *b, Vdouble *c)

Computes orientation of a triangle.

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.

Parameters:

  • p – 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

Vdouble vsy_PredOrient3d(vsy_Pred *p, Vdouble *b, Vdouble *a, Vdouble *c, Vdouble *d)

computes orientation of a tetrahedron

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.

Parameters:

  • p – 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

Vdouble vsy_PredIncircle(vsy_Pred *p, Vdouble *a, Vdouble *b, Vdouble *c, Vdouble *d)

determines whether point is inside circle

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.

Parameters:

  • p – 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

  • d – Point whose position relative to circle is to be determined

Vdouble vsy_PredInsphere(vsy_Pred *p, Vdouble *a, Vdouble *b, Vdouble *c, Vdouble *d, Vdouble *e)

determines whether point is inside sphere

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.

Parameters:

  • p – 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

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

computes line-triangle intersection

Compute the intersection status of a line with a triangle.

Parameters:

  • p – Pointer to Pred object.

  • xt – Coordinates of triangle

  • xl – Coordinates of line

  • code – [out] Intersection code 

    x=0        No intersection
 =1        Intersects inside triangle
 =2        Intersects on edge
 =3        Intersects on vertex
 =-1       Intersects and is parallel

  • ient – [out] Intersection edge or vertex index (one based)

  • ierr – [out] Error flag 

    x=0        No error
 =1        Triangle is zero area

void vsy_PredExact(vsy_Pred *p, Vint *pass)

check to determine if exact arithmetic

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.

Parameters:

  • p – Pointer to Pred object.

  • pass – [out] Indicates if exact arithmetic can be performed (SYS_ON/SYS_OFF) 

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