HDK
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
UT_RTree.C File Reference
#include "UT_RTree.h"
#include "UT_Assert.h"
#include <SYS/SYS_Math.h>
#include <SYS/SYS_StaticAssert.h>
#include <iostream>
#include <algorithm>
#include <VM/VM_SIMD.h>
+ Include dependency graph for UT_RTree.C:

Go to the source code of this file.

Classes

struct  UT_BoxedItemT< BOXTYPE >
 
struct  UT_BoxedItemAxisOrderT< T >
 
class  UT_RNode< MAX_ORDER >
 
class  UT_RTreeResultAppenderIntArray
 
class  UT_RTreeResultAppenderBatchIntArray
 
class  UT_RTreeResultAcceptorRawIntIterator
 

Functions

template<typename T >
std::ostream & operator<< (std::ostream &os, const UT_BoxT< T > &b)
 
template<typename T >
std::ostream & operator<< (std::ostream &os, const UT_VelBoxT< T > &b)
 
template<typename T >
std::ostream & operator<< (std::ostream &os, const UT_BoxedItemT< T > &bf)
 
template<typename BOXTYPE >
void computeBoundingBox (BOXTYPE &bounding_box, const BOXTYPE *const begin, const BOXTYPE *const end)
 
template<typename BOXTYPE >
void computeBoundingBoxItem (BOXTYPE &bounding_box, const UT_BoxedItemT< BOXTYPE > *const begin, const UT_BoxedItemT< BOXTYPE > *const end)
 
size_t subtreeDetermineNumNodes (const int MAX_ORDER, const size_t size)
 
template<typename BOXTYPE >
void partitionForSubtrees (UT_BoxedItemT< BOXTYPE > *const begin, UT_BoxedItemT< BOXTYPE > *const end, const UT_BoxedItemAxisOrderT< BOXTYPE > &order, int subtree_size, int num_subtrees)
 
template<int MAX_ORDER, typename BOXTYPE >
UT_RNode< MAX_ORDER > * subtreeCreate (BOXTYPE &bounding_box, BOXTYPE shared_boxes[], UT_BoxedItemT< BOXTYPE > *const begin, UT_BoxedItemT< BOXTYPE > *const end, UT_RNode< MAX_ORDER > *const shared_nodes, UT_RNode< MAX_ORDER > *&shared_nodes_end)
 
template<int MAX_ORDER, typename BOXTYPE >
void subtreeCreateAssignment (BOXTYPE &bounding_box, BOXTYPE *const shared_boxes, const UT_RNode< MAX_ORDER > *const shared_nodes, const UT_RNode< MAX_ORDER > *const node, const BOXTYPE item_boxes[])
 
template<typename QUERY_SHAPE , typename RESULT_ACCEPTOR , int MAX_ORDER, typename BOXTYPE >
void subtreeGetIntersectingItems (RESULT_ACCEPTOR &acceptor, const UT_RNode< MAX_ORDER > *const shared_nodes, const BOXTYPE *const shared_boxes, const UT_RNode< MAX_ORDER > *const node, const QUERY_SHAPE &query_box)
 
template<typename QUERY_SHAPE , typename RESULT_ACCEPTOR , int MAX_ORDER, typename BOXTYPE , int BATCH_SIZE>
void subtreeGetIntersectingItemsBatch (RESULT_ACCEPTOR &acceptor, const UT_RNode< MAX_ORDER > *const shared_nodes, const BOXTYPE *const shared_boxes, const UT_RNode< MAX_ORDER > *const node, const QUERY_SHAPE *query_boxes)
 
template<int MAX_ORDER>
int UTsubtreeComputeMaxDepth (const UT_RNode< MAX_ORDER > shared_nodes[], const UT_RNode< MAX_ORDER > *const node)
 
template<typename QUERY_SHAPE , int MAX_ORDER, typename BOXTYPE >
void UTgetIntersectingItems (UT_Array< int > &results, const UT_RTreeGeneric< MAX_ORDER > &tree, const QUERY_SHAPE &query_box, const UT_RTreeAssignmentT< BOXTYPE > &assignment)
 
template<typename QUERY_SHAPE , int MAX_ORDER, typename BOXTYPE , int BATCH_SIZE>
void UTappendIntersectingItemsBatch (UT_Array< int > *results, const UT_RTreeGeneric< MAX_ORDER > &tree, const QUERY_SHAPE *query_boxes, const UT_RTreeAssignmentT< BOXTYPE > &assignment)
 
template<typename QUERY_SHAPE , int MAX_ORDER, typename BOXTYPE >
void UTappendIntersectingItems (UT_Array< int > &results, const UT_RTreeGeneric< MAX_ORDER > &tree, const QUERY_SHAPE &query_box, const UT_RTreeAssignmentT< BOXTYPE > &assignment, exint baseindex)
 
template<typename QUERY_SHAPE , int MAX_ORDER, typename BOXTYPE >
intUTgetIntersectingItems (const UT_RTreeGeneric< MAX_ORDER > &tree, const QUERY_SHAPE &query_box, const UT_RTreeAssignmentT< BOXTYPE > &assignment, int *const items_begin)
 
template<>
void subtreeGetIntersectingItemsBatch< UT_BoxT< float >, UT_RTreeResultAppenderBatchIntArray, 4, UT_BoxT< float >, 4 > (UT_RTreeResultAppenderBatchIntArray &acceptor, const UT_RNode< 4 > *const shared_nodes, const UT_BoxT< float > *const shared_boxes, const UT_RNode< 4 > *const node, const UT_BoxT< float > *query_boxes)
 

Function Documentation

template<typename BOXTYPE >
void computeBoundingBox ( BOXTYPE &  bounding_box,
const BOXTYPE *const  begin,
const BOXTYPE *const  end 
)
inline

Definition at line 483 of file UT_RTree.C.

template<typename BOXTYPE >
void computeBoundingBoxItem ( BOXTYPE &  bounding_box,
const UT_BoxedItemT< BOXTYPE > *const  begin,
const UT_BoxedItemT< BOXTYPE > *const  end 
)
inline

Definition at line 502 of file UT_RTree.C.

template<typename T >
std::ostream& operator<< ( std::ostream &  os,
const UT_BoxT< T > &  b 
)
inline

Definition at line 260 of file UT_RTree.C.

template<typename T >
std::ostream& operator<< ( std::ostream &  os,
const UT_VelBoxT< T > &  b 
)
inline

Definition at line 416 of file UT_RTree.C.

template<typename T >
std::ostream& operator<< ( std::ostream &  os,
const UT_BoxedItemT< T > &  bf 
)
inline

Definition at line 469 of file UT_RTree.C.

template<typename BOXTYPE >
void partitionForSubtrees ( UT_BoxedItemT< BOXTYPE > *const  begin,
UT_BoxedItemT< BOXTYPE > *const  end,
const UT_BoxedItemAxisOrderT< BOXTYPE > &  order,
int  subtree_size,
int  num_subtrees 
)
inline

Partition the range of boxed items [begin, end) according to the given comparison function such that all items in the range [0, m-1] are less than or equal to all items in [m, 2m-1], which are less than or equal to all items in [2m, 3m-1], etc, where m is the subtree size.

Definition at line 728 of file UT_RTree.C.

template<int MAX_ORDER, typename BOXTYPE >
UT_RNode<MAX_ORDER>* subtreeCreate ( BOXTYPE &  bounding_box,
BOXTYPE  shared_boxes[],
UT_BoxedItemT< BOXTYPE > *const  begin,
UT_BoxedItemT< BOXTYPE > *const  end,
UT_RNode< MAX_ORDER > *const  shared_nodes,
UT_RNode< MAX_ORDER > *&  shared_nodes_end 
)
inline

Definition at line 755 of file UT_RTree.C.

template<int MAX_ORDER, typename BOXTYPE >
void subtreeCreateAssignment ( BOXTYPE &  bounding_box,
BOXTYPE *const  shared_boxes,
const UT_RNode< MAX_ORDER > *const  shared_nodes,
const UT_RNode< MAX_ORDER > *const  node,
const BOXTYPE  item_boxes[] 
)
inline

Definition at line 886 of file UT_RTree.C.

size_t subtreeDetermineNumNodes ( const int  MAX_ORDER,
const size_t  size 
)
inline

Definition at line 672 of file UT_RTree.C.

template<typename QUERY_SHAPE , typename RESULT_ACCEPTOR , int MAX_ORDER, typename BOXTYPE >
void subtreeGetIntersectingItems ( RESULT_ACCEPTOR &  acceptor,
const UT_RNode< MAX_ORDER > *const  shared_nodes,
const BOXTYPE *const  shared_boxes,
const UT_RNode< MAX_ORDER > *const  node,
const QUERY_SHAPE &  query_box 
)
inline

Definition at line 942 of file UT_RTree.C.

template<typename QUERY_SHAPE , typename RESULT_ACCEPTOR , int MAX_ORDER, typename BOXTYPE , int BATCH_SIZE>
void subtreeGetIntersectingItemsBatch ( RESULT_ACCEPTOR &  acceptor,
const UT_RNode< MAX_ORDER > *const  shared_nodes,
const BOXTYPE *const  shared_boxes,
const UT_RNode< MAX_ORDER > *const  node,
const QUERY_SHAPE *  query_boxes 
)
inline

Definition at line 996 of file UT_RTree.C.

template<>
void subtreeGetIntersectingItemsBatch< UT_BoxT< float >, UT_RTreeResultAppenderBatchIntArray, 4, UT_BoxT< float >, 4 > ( UT_RTreeResultAppenderBatchIntArray acceptor,
const UT_RNode< 4 > *const  shared_nodes,
const UT_BoxT< float > *const  shared_boxes,
const UT_RNode< 4 > *const  node,
const UT_BoxT< float > *  query_boxes 
)
inline

Definition at line 1442 of file UT_RTree.C.

template<typename QUERY_SHAPE , int MAX_ORDER, typename BOXTYPE >
void UTappendIntersectingItems ( UT_Array< int > &  results,
const UT_RTreeGeneric< MAX_ORDER > &  tree,
const QUERY_SHAPE &  query_box,
const UT_RTreeAssignmentT< BOXTYPE > &  assignment,
exint  baseindex 
)
inline

Definition at line 1306 of file UT_RTree.C.

template<typename QUERY_SHAPE , int MAX_ORDER, typename BOXTYPE , int BATCH_SIZE>
void UTappendIntersectingItemsBatch ( UT_Array< int > *  results,
const UT_RTreeGeneric< MAX_ORDER > &  tree,
const QUERY_SHAPE *  query_boxes,
const UT_RTreeAssignmentT< BOXTYPE > &  assignment 
)
inline

Definition at line 1294 of file UT_RTree.C.

template<typename QUERY_SHAPE , int MAX_ORDER, typename BOXTYPE >
void UTgetIntersectingItems ( UT_Array< int > &  results,
const UT_RTreeGeneric< MAX_ORDER > &  tree,
const QUERY_SHAPE &  query_box,
const UT_RTreeAssignmentT< BOXTYPE > &  assignment 
)
inline

Definition at line 1281 of file UT_RTree.C.

template<typename QUERY_SHAPE , int MAX_ORDER, typename BOXTYPE >
int* UTgetIntersectingItems ( const UT_RTreeGeneric< MAX_ORDER > &  tree,
const QUERY_SHAPE &  query_box,
const UT_RTreeAssignmentT< BOXTYPE > &  assignment,
int *const  items_begin 
)
inline

Definition at line 1348 of file UT_RTree.C.

template<int MAX_ORDER>
int UTsubtreeComputeMaxDepth ( const UT_RNode< MAX_ORDER >  shared_nodes[],
const UT_RNode< MAX_ORDER > *const  node 
)
inline

Definition at line 1057 of file UT_RTree.C.