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

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

Begin and end an instance of an object, return object error flag
- vis_SpaceBegin() - create an instance of a Space object
- vis_SpaceEnd() - destroy an instance of a Space object
- vis_SpaceError() - return Space object error flag
Set, manipulate and query entities
- vis_SpaceBoxGroup() - (thread safe) elements contained in a box.
- vis_SpaceBoxNodeGroup() - find the nodes contained in a box.
- vis_SpaceDupNodeIdTran() - (thread safe) duplicate node search
- vis_SpaceKernel() - generate spatial decomposition kernel.
- vis_SpaceNodeKernel() - generate node spatial decomposition kernel.
- vis_SpaceLineGroup() - (thread safe) elements intersecting a line.
- vis_SpacePlaneGroup() - (thread safe) elements intersecting a plane.
- vis_SpacePointIdTran() - (thread safe) elements containing points.
- vis_SpacePointNodeIdTran() - (thread safe) nodes close to points.
- vis_SpaceSetObject() - set pointers to attribute objects.
- vis_SpaceSetParam() - set parameters for search operations.

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

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

5.3. Function Descriptions

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

vis_Space *vis_SpaceBegin(void)

create an instance of a Space object

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)

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

void vis_SpaceEnd(vis_Space *p)

destroy an instance of a Space object

See vis_SpaceBegin()

Vint vis_SpaceError(vis_Space *p)

return the current value of a Space object error flag

See vis_SpaceBegin()

void vis_SpaceSetObject(vis_Space *p, Vint objecttype, Vobject *object)

set pointers to attribute objects.

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.

Errors: VIS_ERROR_OBJECTTYPE is generated if an improper objecttype is specified.

Parameters:

p – Pointer to Space object.
objecttype – The name of the object type to be set.
```
x=VIS_GRIDFUN           GridFun object
```
object – Pointer to the object to be set.

void vis_SpaceSetParamf(vis_Space *p, Vint ptype, Vfloat fparam)

set parameters for search operations.

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 .

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.

Parameters:

p – Pointer to Space object.

ptype – Parameter type to set.

x=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 value that ptype will be set to.

x=SPACE_NODE_LOWEST       Return node with lowest index.
 =SPACE_NODE_CLOSEST      Return closest node.
 =SPACE_NODE_ANY          Return any node.

void vis_SpaceGetParamf(vis_Space *p, Vint type, Vfloat *value)

set parameters for search operations.

See vis_SpaceSetParamf()

void vis_SpaceKernel(vis_Space *p, vis_Group *group)

generate spatial decomposition kernel.

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.

Parameters:

p – Pointer to Space object.
group – Pointer to a Group object of elements.

void vis_SpaceNodeKernel(vis_Space *p)

generate node spatial decomposition kernel.

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

Parameters:: p – Pointer to Space object.

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

(thread safe) elements containing points

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.

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

Parameters:

p – 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.
idtran – [out] Pointer to a IdTran object of elements
r – [out] Array of the local coordinates of the search points within an element.

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

(thread safe) elements intersecting a line

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.

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

Parameters:

p – 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.
groupdst – [out] Pointer to derived Group object of elements.

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

(thread safe) elements intersecting a plane

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.

Use vis_SpacePlaneGroup() for single precision calculation. Use vis_SpacePlaneGroupdv() for double precision calculation.

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

Parameters:

p – 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.
groupdst – [out] Pointer to derived Group object of elements.

void vis_SpacePlaneGroupdv(vis_Space *p, Vdouble pts[4][3], vis_Group *subset, vis_Group *group)

(thread safe) elements intersecting a plane

See vis_SpacePlaneGroup()

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

find the nodes contained in a box.

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.

Errors: VIS_ERROR_VALUE is generated if group is not a node group.

Parameters:

p – Pointer to Space object.
box_pts – Array of the world coordinates of points defining a box.
group – Pointer to Group object of nodes.
groupdst – [out] Pointer to derived Group object of nodes.

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

(thread safe) elements contained in a box.

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.

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

Parameters:

p – 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.
groupdst – [out] Pointer to derived Group object of elements.

void vis_SpaceDupNodeIdTran(vis_Space *p, vis_Group *group, vis_IdTran *idtran)

(thread safe) duplicate node search

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.

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

Parameters:

p – Pointer to Space object.
group – Pointer to Group object of nodes. If NULL, then all nodes are assumed.
idtran – [out] Pointer to derived IdTran object of duplicate nodes.

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

(thread safe) nodes close to points

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.

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

Parameters:

p – 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.
idtran – [out] Pointer to derived IdTran object of duplicate nodes.

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

Begin and end an instance of an object, return object error flag
- vis_RangeBegin() - create an instance of a Range object
- vis_RangeEnd() - destroy an instance of a Range object
- vis_RangeError() - return Range object error flag
Set, manipulate and query entities
- vis_RangeSetObject() - set pointers to attribute objects.
- vis_RangeSetState() - set State objects.
- vis_RangeSurfGroup() - find the elements containing a state value.

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

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

5.6. Function Descriptions

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

vis_Range *vis_RangeBegin(void)

create an instance of a Range object

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)

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

void vis_RangeEnd(vis_Range *p)

destroy an instance of a Range object

See vis_RangeBegin()

Vint vis_RangeError(vis_Range *p)

return the current value of a Range object error flag

See vis_RangeBegin()

void vis_RangeSetObject(vis_Range *p, Vint objecttype, Vobject *object)

set pointers to attribute objects.

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.

Errors: VIS_ERROR_OBJECTTYPE is generated if an improper objecttype is specified.

Parameters:

p – Pointer to Range object.

objecttype – The name of the object type to be set.

x=VIS_GRIDFUN            GridFun object
 =VIS_SPACE              Space object

object – Pointer to the object to be set.

void vis_RangeSetState(vis_Range *p, Vint index, vis_State *state)

set State object.

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.

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.

Parameters:

p – Pointer to Range object.
index – State index to set
```
0 <= index <= 15.
```
state – Pointer to State object

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

find the elements containing a state value.

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.

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.

Parameters:

p – 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.
groupdst – [out] Pointer to derived Group object of elements.

5. Space and Range Searching - Space, Range

5.1. Spatial Searching - Space

5.2. Attribute Objects

5.3. Function Descriptions

5.4. Range Searching - Range

5.5. Attribute Objects

5.6. Function Descriptions

5. Space and Range Searching - Space, Range 

5.1. Spatial Searching - Space 

5.4. Range Searching - Range 