Table of Contents

20. Space and Range Searching - Space,Range

The Space and Range perform spatial search operations for geometric objects (e.g., points, lines, planes, boxes) and data range search operations for state values.

Table of Contents

20.1 Spatial Searching - Space

The Space module maintains a spatial decomposition of an unstructured or multi-block structured mesh which relates lists of node and element entities to regular spatial regions (e.g., blocks) in model space. The spatial decomposition can be used to significantly decrease the amount of time spent performing search operations on a mesh. Search efficiency is improved by first searching the decomposition regions for a geometric object such as an intersecting point or line, etc. If the object is in or intersects the region then the lists of entities in the region are searched. This strategy will only be efficient if the number of entities in a mesh is much larger than the number of spatial regions.

Users of a Space object may search for the element which contains a point, the list of elements which intersect a line, the list of elements which intersect a plane and the elements contained within a box. Also duplicate node and other node location searches may be made. Parameters may be set to select decomposition resolution, adaptivity level and extent attributes for certain search operations (e.g. finite or infinite lines). The functions associated with a Space object are the following.

Instance a Space object initially using vis_SpaceBegin. At this point a GridFun object must be set as an attribute object using vis_SpaceSetObject so that the Space object can access finite element model information.

Before generating the spatial decomposition kernel the spatial decomposition method and subdivision resolution and depth should be set if the default values are not acceptable. This spatial decomposition method subdivides model space into a set of blocks aligned to the world coordinate axes according to the subdivision resolution for each axis. The entities contained in each block are then determined and stored for each block. When a search or intersection is performed for the mesh only the entities in the blocks which contain the search point or intersect the block, rather than the entire mesh, need be considered. The default subdivision resolution is set to 10 for each coordinate axis. This means that model space will be decomposed into 1000 (10x10x10) blocks used for searching. The block decomposition resolution, depth, etc. may be changed using vis_SpaceSetParami. The actual data structures used to hold the spatial decomposition are private to the Space object. The spatial decomposition kernel must be generated using vis_SpaceKernel before any search queries are performed.

The user performs element searches in a Space object using a suite of functions. These functions fall into two basic categories, (1) query for the elements which contain a set of points, vis_SpacePointIdTran, and (2) query for the elements which intersect a geometrical object (line, plane or box), vis_SpaceLineGroup, vis_SpacePlaneGroup and vis_SpaceBoxGroup. The spatial decomposition kernel must be generated before any query functions are called. The kernel may be built using vis_SpaceKernel.

Node searches are performed using vis_SpacePointNodeIdTran and vis_SpaceDupNodeIdTran. The node spatial decomposition kernel must be generated before these query functions are called. The kernel may be built using vis_SpaceNodeKernel.

Table of Contents

20.2 Attribute Objects

A Space object uses a GridFun object to access finite element data from the host application.

The Space object calls the following grid functions set in the GridFun attribute object.

Coords
ElemCon
ElemNode
ElemNum
ElemTopo
Extent
Number
Topology

Table of Contents

20.3 Function Descriptions

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

Table of Contents , Space

NAME

*vis_SpaceBegin - create an instance of a Space object

C SPECIFICATION

vis_Space *vis_SpaceBegin ()

ARGUMENTS

None

FUNCTION RETURN VALUE

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

DESCRIPTION

Create an instance of a Space object. Memory is allocated for the object private data and the pointer to the data is returned. The default apaptive block depth is 0. The default resolution is 10 by 10 by 10.

Destroy an instance of a Space object using 

     void vis_SpaceEnd (vis_Space *space)

Return the current value of a Space object error flag using 

     Vint vis_SpaceError (vis_Space *space)

Table of Contents , Space

NAME

vis_SpaceBoxGroup - (thread safe) elements contained in a box.

C SPECIFICATION

void vis_SpaceBoxGroup (vis_Space *space,
                        Vfloat box_pts[8][3],
                        vis_Group *group,
                        vis_Group *groupdst)

INPUT ARGUMENTS

space        Pointer to Space object.
box_pts      Array of the world coordinates of points defining a box.
group        Pointer to Group object of elements.
             If NULL, then all elements are assumed.

OUTPUT ARGUMENTS

groupdst     Pointer to derived Group object of elements.

ERRORS

VIS_ERROR_VALUE is generated if group is not an element, element face or element edge group. VIS_ERROR_OPERATION is generated if the spatial decomposition kernel has not been built using vis_SpaceKernel.

DESCRIPTION

Determine which elements intersect or are contained in the given box and add them to groupdst. The output groupdst must have been previously created and defined as an element group. Note that groupdst is not cleared by this function, in other words, the valid element entities are added to any existing elements in the output groupdst. The box defined by the input box_pts is assumed to have planar faces. The eight points must be defined on the hexahedral box using a linear Serendipity element convention.

If the decomposition kernel has not been previously generated, this call will automatically create it by calling vis_SpaceKernel with a NULL group argument.

Table of Contents , Space

NAME

vis_SpaceBoxNodeGroup - find the nodes contained in a box.

C SPECIFICATION

void vis_SpaceBoxNodeGroup (vis_Space *space,
                            Vfloat box_pts[8][3],
                            vis_Group *group,
                            vis_Group *groupdst)

INPUT ARGUMENTS

space        Pointer to Space object.
box_pts      Array of the world coordinates of points defining a box.
group        Pointer to Group object of nodes.
             If NULL, then all nodes are assumed.

OUTPUT ARGUMENTS

groupdst     Pointer to derived Group object of nodes.

ERRORS

VIS_ERROR_VALUE is generated if group is not a node group.

DESCRIPTION

Determine which nodes are contained in the given box and add them to groupdst. The output groupdst must have been previously created and defined as a node group. Note that groupdst is not cleared by this function, in other words, the valid node entities are added to any existing nodes in the output groupdst. The box defined by the input box_pts is assumed to have planar faces. The eight points must be defined on the hexahedral box using a linear Serendipity element convention.

If the decomposition kernel has not been previously generated, this call will automatically create it by calling vis_SpaceKernel with a NULL group argument.

Table of Contents , Space

NAME

vis_SpaceDupNodeIdTran - (thread safe) duplicate node search

C SPECIFICATION

void vis_SpaceDupNodeIdTran (vis_Space *space,
                             vis_Group *group,
                             vis_IdTran *idtran)

INPUT ARGUMENTS

space        Pointer to Space object.
group        Pointer to Group object of nodes.
             If NULL, then all nodes are assumed.

OUTPUT ARGUMENTS

idtran       Pointer to derived IdTran object of duplicate nodes.

ERRORS

VIS_ERROR_VALUE is generated if group is not a node group. VIS_ERROR_NULLOBJECT is generated if a GridFun object has not been set. VIS_ERROR_OPERATION is generated if the node decomposition kernel has not been called using vis_SpaceNodeKernel.

DESCRIPTION

Search for duplicate nodes within a group of nodes and return the duplicate nodes in the idtran object. For each node in the input group a zero is returned in idtran if there is no duplicate node, if there is a duplicate node then the duplicate node index is set in idtran. Note that idtran is initially cleared by this function. The search type is specified by the SPACE_NODE_SEARCH parameter and the tolerance is specified by SPACE_TOLERANCE. Use vis_SpaceSetParami and vis_SpaceSetParamf to set search parameters.

Table of Contents , Space

NAME

vis_SpaceKernel - generate spatial decomposition kernel.

C SPECIFICATION

void vis_SpaceKernel (vis_Space *space,
                      vis_Group *group)

INPUT ARGUMENTS

space        Pointer to Space object.
group        Pointer to a Group object of elements.

OUTPUT ARGUMENTS

none

DESCRIPTION

Creates a spatial decomposition for the entities defined in group. The input group must have been previously created and defined as an element group. The current SPACE_RESOLUTION, SPACE_ADAPT_RESOLUTION and SPACE_DEPTH parameters will be used to decompose model space into a set of blocks. These decomposition parameters are set using vis_SpaceSetParami. Each entity in group will be added to the block it is contained in.

Once the decomposition kernel is created, then space searches may be performed. If this function is called and the decomposition kernel has already been generated, then the function immediately returns without altering the object state.

Table of Contents , Space

NAME

vis_SpaceNodeKernel - generate node spatial decomposition kernel.

C SPECIFICATION

void vis_SpaceNodeKernel (vis_Space *space)

INPUT ARGUMENTS

space        Pointer to Space object.

OUTPUT ARGUMENTS

none

DESCRIPTION

Creates the node spatial decomposition for all nodes. This kernel is required before using the vis_SpacePointNodeIdTran and vis_SpaceDupNodeIdTran functions.

Table of Contents , Space

NAME

vis_SpaceLineGroup - (thread safe) elements intersecting a line

C SPECIFICATION

void vis_SpaceLineGroup (vis_Space *space,
                         Vfloat line_pts[2][3], 
                         vis_Group *group)
                         vis_Group *groupdst)

INPUT ARGUMENTS

space        Pointer to Space object.
line_pts     Array of the world coordinates of
             the two points defining the end points of a line.
group        Pointer to Group object of elements.
             If NULL, then all elements are assumed.

OUTPUT ARGUMENTS

groupdst     Pointer to derived Group object of elements.

ERRORS

VIS_ERROR_VALUE is generated if group is not an element, element face or element edge group. VIS_ERROR_OPERATION is generated if the spatial decomposition kernel has not been built using vis_SpaceKernel.

DESCRIPTION

Determine which elements intersect the given line and add them to groupdst. The output groupdst must have been previously created and defined as an element group. Note that groupdst is not cleared by this function, in other words the valid element entities are added to any existing elements in the output groupdst.

By default element intersections are computed assuming an infinite line whose direction is specified by line_pts. The element intersections can be set to be computed for a finite or infinite line by using the function vis_SpaceSetParami to appropriately set the SPACE_LINE_INFINITE parameter.

If the decomposition kernel has not been previously generated, this call will automatically create it by calling vis_SpaceKernel with a NULL group argument.

Table of Contents , Space

NAME

vis_SpacePlaneGroup - (thread safe) elements intersecting a plane

C SPECIFICATION

void vis_SpacePlaneGroup (vis_Space *space,
                          Vfloat plane_pts[4][3], 
                          vis_Group *group,
                          vis_Group *groupdst)

INPUT ARGUMENTS

space        Pointer to Space object.
plane_pts    Array of the world coordinates of the four points 
             defining the plane.
group        Pointer to Group object of elements.
             If NULL, then all elements are assumed.

OUTPUT ARGUMENTS

groupdst     Pointer to derived Group object of elements.

ERRORS

VIS_ERROR_VALUE is generated if group is not an element, element face or element edge group. VIS_ERROR_OPERATION is generated if the spatial decomposition kernel has not been built using vis_SpaceKernel.

DESCRIPTION

Determine which elements intersect the given plane and add them to groupdst. The output groupdst must have been previously created and defined as an element group. Note that groupdst is not cleared by this function, in other words the valid element entities are added to any existing elements in the output groupdst.

Element intersections are computed assuming a plane specified by the four world coordinate points in plane_pts. The first three points of plane_pts specify the plane. The fourth point is projected to the plane.

Element intersections can be set to be computed for an finite or infinite plane by using the function vis_SpaceSetParami to appropriately set the SPACE_PLANE_INFINITE parameter. For a finite plane the values in plane_pts contain the four points defining the edges of a planar quadrilateral. The four points must be defined on the quadrilateral plane in linear Serendipity element convention.

If the decomposition kernel has not been previously generated, this call will automatically create it by calling vis_SpaceKernel with a NULL group argument.

Table of Contents , Space

NAME

vis_SpacePointIdTran - (thread safe) elements containing points

C SPECIFICATION

void vis_SpacePointIdTran (vis_Space *space,
                           Vint num_pts, 
                           Vfloat pts[][3],
                           vis_Group *group,
                           vis_IdTran *idtran, 
                           Vfloat r[][3])

INPUT ARGUMENTS

space        Pointer to Space object.
num_pts      The number of points to search. 
pts          Array of the world coordinate points of the search points. 
group        Pointer to Group object of elements.
             If NULL, then all elements are assumed.

OUTPUT ARGUMENTS

idtran       Pointer to a IdTran object of elements
r            Array of the local coordinates of the search points
             within an element.

ERRORS

VIS_ERROR_VALUE is generated if group is not an element, element face or element edge group. VIS_ERROR_OPERATION is generated if the spatial decomposition kernel has not been built using vis_SpaceKernel.

DESCRIPTION

Determine which elements the specified search points are contained in and and return them in idtran. The output idtran must have been previously created. Note that idtran is initially cleared by this function.

The output array r must be defined with a size of num_pts. If a point is contained in an element then the element number is recorded in the idtran object and the local coordinates for the point relative to the element are computed and returned in r. If the point is not contained in an element, a zero is recorded in the idtran object and the local coordinates returned in r are undefined.

Table of Contents , Space

NAME

vis_SpacePointNodeIdTran - (thread safe) nodes close to points

C SPECIFICATION

void vis_SpacePointNodeIdTran (vis_Space *space,
                               Vint num_pts, 
                               Vfloat pts[][3],
                               vis_Group *group,
                               vis_IdTran *idtran)

INPUT ARGUMENTS

space        Pointer to Space object.
num_pts      The number of points to search. 
pts          Array of the world coordinate points of the search points. 
group        Pointer to Group object of nodes.
             If NULL, then all nodes are assumed.

OUTPUT ARGUMENTS

idtran       Pointer to derived IdTran object of duplicate nodes.

ERRORS

VIS_ERROR_VALUE is generated if group is not a node group. VIS_ERROR_NULLOBJECT is generated if a GridFun object has not been set. VIS_ERROR_OPERATION is generated if the node decomposition kernel has not been called using vis_SpaceNodeKernel.

DESCRIPTION

Search for nodes within a group of nodes which are close to a specified set of search points. Return the nodes which satisfy the search criteria in the idtran object. For each search point a zero is returned in idtran if there is no close node, if there is a close node then the node index is set in idtran. Note that idtran is initially cleared by this function. The search type is specified by the SPACE_NODE_SEARCH parameter and the tolerance is specified by SPACE_TOLERANCE. Use vis_SpaceSetParami and vis_SpaceSetParamf to set search parameters.

Table of Contents , Space

NAME

vis_SpaceSetParam - set parameters for search operations.

C SPECIFICATION

void vis_SpaceSetParamf (vis_Space *space,
                         Vint ptype, 
                         Vfloat fparam)
void vis_SpaceSetParami (vis_Space *space,
                         Vint ptype, 
                         Vint iparam)

INPUT ARGUMENTS

space        Pointer to Space object.
ptype        Parameter type to set. 
             =SPACE_DEPTH             Decomposition depth
             =SPACE_LINE_INFINITE     Infinite/finite line intersection
             =SPACE_PLANE_INFINITE    Infinite/finite plane intersection
             =SPACE_NODE_SEARCH       Specify node search type
             =SPACE_REFINE            Specify refinements
             =SPACE_RESOLUTION        Specify zero level decomposition
             =SPACE_RESOLUTION_ADAPT  Specify multi-level decomposition
             =SPACE_TOLERANCE         Specify floating point world
                                      coordinate distance tolerance
fparam       Specifies the float value that ptype will be set to.
iparam       Specifies the integer value that ptype will be set to.
             =SPACE_NODE_LOWEST       Return node with lowest index.
             =SPACE_NODE_CLOSEST      Return closest node.
             =SPACE_NODE_ANY          Return any node.

OUTPUT ARGUMENTS

none

ERRORS

VIS_ERROR_ENUM is generated if an improper ptype is specified. VIS_ERROR_ENUM is generated if an improper SPACE_NODE_SEARCH is specified. VIS_ERROR_VALUE is generated if an improper depth, resolution or refinement is specified.

DESCRIPTION

Set spatial decomposition depth. If the depth is set to 0, then a single block decomposition is performed using the resolution specified by SPACE_RESOLUTION. If the depth is greater than 0, it specifies the maximum number of adaptive decomposition levels which may be generated using resolution SPACE_RESOLUTION_ADAPT. By default SPACE_DEPTH is set to 0.

Specify whether line and plane intersections are performed assuming finite or infinite line and plane extents using SPACE_LINE_INFINITE and SPACE_PLANE_INFINITE respectively. By default SPACE_LINE_INFINITE and SPACE_PLANE_INFINITE are on.

Specify the type of node location to be performed by vis_SpacePointNodeIdTran. If SPACE_NODE_SEARCH is set to SPACE_NODE_LOWEST then the node with the lowest index which satisfies the search constraint is returned; if set to SPACE_NODE_CLOSEST then the node closest to the input point is returned; if set to SPACE_NODE_ANY then any node which satisfies the search constraint is returned. By default SPACE_NODE_SEARCH is set to SPACE_NODE_LOWEST.

Specify the refinement used to subdivide elements for intersection testing with SPACE_REFINE. If used for graphical picking, this refinement should match the refinement visualization context used to draw the entities to be picked. By default SPACE_REFINE is set to 0.

Specify the resolution of the spatial decomposition using SPACE_RESOLUTION and SPACE_RESOLUTION_ADAPT. SPACE_RESOLUTION_ADAPT is only used if SPACE_DEPTH is greater than 0. To obtain an "octtree" decomposition, set both parameters to 2 and SPACE_DEPTH to the desired maximum depth of the octtree. By default SPACE_RESOLUTION is set to 10 and SPACE_RESOLUTION_ADAPT is set to 4.

Specify the distance tolerance to be used in point location and intersection testing using SPACE_TOLERANCE. By default SPACE_TOLERANCE is set to .0001 .

Table of Contents , Space

NAME

vis_SpaceSetObject - set pointers to attribute objects.

C SPECIFICATION

void vis_SpaceSetObject (vis_Space *space,
                         Vint objecttype,
                         Vobject *object)

INPUT ARGUMENTS

space        Pointer to Space object.
objecttype   The name of the object type to be set.
             =VIS_GRIDFUN            GridFun object
object       Pointer to the object to be set.

OUTPUT ARGUMENTS

None

ERRORS

VIS_ERROR_OBJECTTYPE is generated if an improper objecttype is specified.

DESCRIPTION

Set a pointer to an attribute object. A GridFun attribute object is required so that all finite element topology, connectivity, node coordinate and node and element association queries will be made through the GridFun interface.

Table of Contents

20.4 Range Searching - Range

The Range module augments a Space object's spatial decomposition of a mesh to relate state ranges for groups of entities to regular spatial regions (e.g., blocks) in model space. The augmented spatial decomposition can be used to significantly decrease the amount of time spent performing search operations on a mesh for entities which contain a given state value. Search efficiency is improved by first searching the decomposition regions (whose number should be much smaller than the number of entities in a mesh) for a state range. If the range is within the ranges for the region then the lists of entities in the region are searched. This strategy will only be efficient if the number of entities in a mesh is much larger than the number of spatial regions. The functions associated with a Range object are the following.

Instance a Range object initially using vis_RangeBegin. At this point a GridFun object must be set as an attribute object so the the Range object can access finite element model information. A Space object must be set as an attribute object to provide the block decomposition for searching.

The Range module uses State objects to define the field quantities used for searching. Each field quantity or state is associated with an integer index between 0 and 15. A Range object can manage up to 16 fields simultaneously. The states are associated with an index using vis_RangeSetState. Once a state has been set, it's associated index may be referenced in a query function such as vis_RangeSurfGroup.

Table of Contents

20.5 Attribute Objects

Before a Range object can be used a Space object must be created and attached to it as an attribute object using vis_RangeSetObject. A Range object also uses a GridFun object to access finite element data from the host application. The GridFun object used should be the same GridFun object used as an attribute object to Space.

The Range object calls the following grid functions set in the GridFun attribute object.

ElemNode

Table of Contents

20.6 Function Descriptions

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

Table of Contents , Range

NAME

*vis_RangeBegin - create an instance of a Range object

C SPECIFICATION

vis_Range *vis_RangeBegin ()

ARGUMENTS

None

FUNCTION RETURN VALUE

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

DESCRIPTION

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

Destroy an instance of a Range object using 

     void vis_RangeEnd (vis_Range *Range)

Return the current value of a Range object error flag using 

     Vint vis_RangeError (vis_Range *Range)

Table of Contents , Range

NAME

vis_RangeSetObject - set pointers to attribute objects.

C SPECIFICATION

void vis_RangeSetObject (vis_Range *range,
                         Vint objecttype,
                         Vobject *object)

INPUT ARGUMENTS

range        Pointer to Range object.
objecttype   The name of the object type to be set.
             =VIS_GRIDFUN            GridFun object
             =VIS_SPACE              Space object
object       Pointer to the object to be set.

OUTPUT ARGUMENTS

None

ERRORS

VIS_ERROR_OBJECTTYPE is generated if an improper objecttype is specified.

DESCRIPTION

Set a pointer to an attribute object. A GridFun attribute object is required so that all finite element topology, connectivity, node coordinate and node and element association queries will be made through the GridFun interface. A Space attribute object is also required.

Table of Contents , Range

NAME

vis_RangeSetState - set State object.

C SPECIFICATION

void vis_RangeSetState (vis_Range *range,
                        Vint index,
                        vis_State *state);

INPUT ARGUMENTS

range        Pointer to Range object.
index        State index to set
             0 <= index <= 15.
state        Pointer to State object

OUTPUT ARGUMENTS

None

ERRORS

VIS_ERROR_VALUE is generated if an index out of range is specified. VIS_ERROR_OPERATION is generated if the state object is improper.

DESCRIPTION

Set a State object for the Range object relating it with an integer index. The index will then be used to search for related state values. The State object should contain either node or element node data.

Table of Contents , Range

NAME

vis_RangeSurfGroup - find the elements containing a state value.

C SPECIFICATION

void vis_RangeSurfGroup (vis_Range *range,
                         Vint index,
                         Vfloat value,
                         vis_Group *group,
                         vis_Group *groupdst)

INPUT ARGUMENTS

range        Pointer to Range object.
index        State index to search      
value        Value to search for
group        Pointer to Group object of elements.
             If NULL, then all elements are assumed.

OUTPUT ARGUMENTS

groupdst     Pointer to derived Group object of elements.

ERRORS

VIS_ERROR_VALUE is generated if group is not an element, element face or element edge group. VIS_ERROR_VALUE is generated if an improper index is specified. VIS_ERROR_NULLOBJECT is generated if a Space attribute object has not been set or the index does not have an associated State object.

DESCRIPTION

Determine which elements contain the given value of the specified state index and add them to groupdst. An element contains a given value if any two nodes in the element lie above and below the value. The output groupdst must have been previously created and defined as an element group. Note that groupdst is not cleared by this function, in other words the valid element entities are added to any existing elements in the output groupdst.