UT_RTree.h

Go to the documentation of this file.

/*
 * PROPRIETARY INFORMATION.  This software is proprietary to
 * Side Effects Software Inc., and is not to be reproduced,
 * transmitted, or disclosed in any way without written permission.
 *
 * NAME:        RTree.h (UT Library, C++)
 *
 * COMMENTS:
 */

#ifndef __RTree_H__
#define __RTree_H__

#include "UT_API.h"

#include "UT_RTreeBox.h"

#include "UT_Array.h"

#include <memory>

namespace UT
{

template< typename ITEM_INDEX, int MAX_ORDER > class RTreeT;
template< typename FT > class RTreeConfigurationT;

//
// Construct an R-tree that contains items with indices in [ 0, num_items ).
// During the construction, item_box[ i ] is used as the bounding box
// for item #i. 
// These boxes determine only the initial structure of the R-tree;
// the passed-in box positions and dimensions are not stored in the R-tree.
//
// Empty boxes are allowed: each item that has an empty box is guaranteed
// to never be returned by any of the getIntersectingItems queries.
// This is useful because it helps avoid the need for re-indexing
// in the client code, in case certain items need to be omitted from the tree.
//
// 'num_items' must be less than 2^{ 8 * sizeof(ItemIndex) - 2 }
// In case ItemIndex is 32 bit int, this is 2^30 == 1073741824
//
template< typename ITEM_INDEX, int MAX_ORDER, typename FT >
RTreeT< ITEM_INDEX, MAX_ORDER > constructRTree( const UT_BoxT< FT > item_box[], const ITEM_INDEX num_items );

// Convenience version of constructRTree that takes a UT_Array of boxes
template< typename ITEM_INDEX, int MAX_ORDER, typename FT >
RTreeT< ITEM_INDEX, MAX_ORDER > constructRTree( const UT_Array< UT_BoxT< FT > >& item_box );

template< typename ITEM_INDEX, int MAX_ORDER, typename FT >
RTreeConfigurationT< FT > constructRTreeConfiguration( const UT::RTreeT< ITEM_INDEX, MAX_ORDER >& tree, const UT_BoxT< FT > item_box[], const ITEM_INDEX num_items );

// Convenience version of constructRTreeConfiguration that takes a UT_Array of boxes
template< typename ITEM_INDEX, int MAX_ORDER, typename FT >
RTreeConfigurationT< FT > constructRTreeConfiguration( const RTreeT< ITEM_INDEX, MAX_ORDER >& tree, const UT_Array< UT_BoxT< FT > >& item_box );


//
// For each item i, if item_box[i] intersects query_box, call accept_item( i ).
// This assumes there exists a free-standing 'intersects' function that takes a 
// QUERY_SHAPE and a UT_BoxT< FT >.
//
template< typename ITEM_INDEX, int MAX_ORDER, typename FT, typename QUERY_SHAPE, typename ACCEPT_ITEM >
void forEachIntersecting(
    ACCEPT_ITEM&& accept_item,
    const RTreeT< ITEM_INDEX, MAX_ORDER >& tree,
    const RTreeConfigurationT< FT >& configuration,
    const QUERY_SHAPE& query_shape
);

//
// Assign a new box to each item: To item index i, assign item_box[ i ].
// Updated configurations can be used with the original tree,
// for example, when alternating collision detection and collision response passes.
// however, when the boxes change too much from the boxes used to construct
// the R-tree, queries become less efficient, in which case 
// a new R-tree should be built.
//
// ITEM_BOX must be an array-like type (it supports operator[]),
// for example, const ITEM_BOX*, UT_Array< ITEM_BOX> or std::vector< ITEM_BOX >
// Each element item_box[ i ] must convert into a UT_BoxT< FT >.
//
// 'num_items' must match the number of items in the tree
//
template< typename ITEM_INDEX, int MAX_ORDER, typename FT >
void updateConfiguration(
    RTreeConfigurationT< FT >& configuration,
    const RTreeT< ITEM_INDEX, MAX_ORDER >& tree,
    const UT_BoxT< FT > item_box[],
    const ITEM_INDEX num_items
);

template< typename ITEM_INDEX_REP, int MAX_ORDER >
class RNodeT;

//
// ItemIndexUnderlyingInteger:
// Map ITEM_INDEX value to its underlying integer representation.
// This can be specialized for any strong index type that needs to be used with RTreeT.
// (e.g., GA_Offset, GA_Index, SC::StrongIndex ).
//
// Primary
// This catches all cases where ITEM_INDEX is a built-in integer type
//
template< typename ITEM_INDEX >
struct ItemIndexUnderlyingInteger
{
    constexpr auto operator()( const ITEM_INDEX i ) const noexcept
    {
        return i;
    }
};

template< typename ITEM_INDEX >
struct ItemIndex_UnderlyingIntegerType : SYS_TypeIdentity< SYS_RemoveCVRef_t< decltype( ItemIndexUnderlyingInteger< ITEM_INDEX >{}( std::declval< ITEM_INDEX >() ) ) > > {};

template< typename ITEM_INDEX >
using ItemIndex_UnderlyingIntegerType_t = typename ItemIndex_UnderlyingIntegerType< ITEM_INDEX >::type;

//
// The order of the R-Tree is the number of children that each
// internal node in the tree has. Picking a higher value of
// MAX_ORDER will reduce the height of the R-tree.
// R-tree stores a containment structure for the boxes that are
// passed to its contructor, but doesn't store any actual boxes.
// That's why RTree doesn't take the number type T as a template parameter.
//
template< typename ITEM_INDEX, int MAX_ORDER >
class RTreeT
{
public:
    // Each item held by the R-tree is represented by an index
    // These indices are relative to arrays held by the client code
    using ItemIndex = ITEM_INDEX;
    static constexpr int max_order = MAX_ORDER;

    RTreeT( RTreeT&& );
    ~RTreeT();

    RTreeT() = delete;
    RTreeT( const RTreeT& ) = delete;
    RTreeT& operator=( const RTreeT& ) = delete;

private:
    using ItemIndexRep = ItemIndex_UnderlyingIntegerType_t< ITEM_INDEX >;
    using Node = RNodeT< ItemIndexRep, MAX_ORDER >;

    // Single contiguous array containing all the R-tree nodes
    exint myNumNodes;
    std::unique_ptr< Node[] > myNodes;

    // myRoot is non owned; it points to an element of the array myNodes
    Node* myRoot;
    
    // Number of items passed into constructor
    ItemIndexRep myNumItems;

    template< typename FT >
    RTreeT( const UT_BoxT< FT > item_box[], const ITEM_INDEX num_items );
    
    // Convenience version that takes a UT_Array of boxes instead
    template< typename FT >
    RTreeT( const UT_Array< UT_BoxT< FT > >& item_box );

    template< typename ALT_ITEM_INDEX, int ALT_MAX_ORDER, typename FT >
    friend RTreeT< ALT_ITEM_INDEX, ALT_MAX_ORDER > constructRTree( const UT_BoxT< FT > item_box[], const ALT_ITEM_INDEX num_items );

    template< typename ALT_ITEM_INDEX, int ALT_MAX_ORDER, typename FT >
    friend RTreeConfigurationT< FT > constructRTreeConfiguration( const RTreeT< ALT_ITEM_INDEX, ALT_MAX_ORDER >& tree, const UT_BoxT< FT > item_box[], const ALT_ITEM_INDEX num_items );

    template< typename ALT_ITEM_INDEX, int ALT_MAX_ORDER, typename FT, typename QUERY_SHAPE, typename ACCEPT_ITEM >
    friend void forEachIntersecting(
        ACCEPT_ITEM&& accept_item,
        const RTreeT< ALT_ITEM_INDEX, ALT_MAX_ORDER >& tree,
        const RTreeConfigurationT< FT >& configuration,
        const QUERY_SHAPE& query_shape
    );

    template< typename ALT_ITEM_INDEX, int ALT_MAX_ORDER, typename FT >
    friend void updateConfiguration(
        RTreeConfigurationT< FT >& configuration,
        const RTreeT< ALT_ITEM_INDEX, ALT_MAX_ORDER >& tree,
        const UT_BoxT< FT > item_box[],
        const ALT_ITEM_INDEX num_items
    );

    template< typename ALT_ITEM_INDEX, int ALT_MAX_ORDER >
    friend exint heapMemoryUsage( const RTreeT< ALT_ITEM_INDEX, ALT_MAX_ORDER >& tree );
};

template< typename FT >
exint heapMemoryUsage( const RTreeConfigurationT< FT >& configuration );

// This is an assigment of a box to each item stored in the R-tree.
// It is passed an argument to queries on the R-tree.
// This way, an R-tree can be re-used efficiently if the item boxes change.
// This will only remain efficient as long as the configuration of boxes
// doesn't change dramatically.
template< typename FT >
class RTreeConfigurationT
{
public:
    RTreeConfigurationT( RTreeConfigurationT&& a );
    
private:
    using Box = UT_BoxT< FT >;

    // Box #s of node n is stored at index ( MAX_ORDER * tree.myNumNodes ) + s
    // of myNodeSlotBox
    exint myNodeSlotBoxSize;
    std::unique_ptr< Box[] > myNodeSlotBox;


    RTreeConfigurationT(
        const exint node_slot_box_size,
        std::unique_ptr< Box[] >&& node_slot_box
    );

    // Disallow    
    RTreeConfigurationT() = delete;
    RTreeConfigurationT( const RTreeConfigurationT& ) = delete;
    RTreeConfigurationT& operator=( const RTreeConfigurationT& ) = delete;
    
    template< typename ITEM_INDEX, int MAX_ORDER > friend class RTreeT;


    template< typename ITEM_INDEX, int MAX_ORDER, typename ALT_FT >
    friend RTreeConfigurationT< ALT_FT > constructRTreeConfiguration( const RTreeT< ITEM_INDEX, MAX_ORDER >& tree, const UT_BoxT< ALT_FT > item_box[], const ITEM_INDEX num_items );

    template< typename ITEM_INDEX, int MAX_ORDER, typename ALT_FT, typename QUERY_SHAPE, typename ACCEPT_ITEM >
    friend void forEachIntersecting(
        ACCEPT_ITEM&& accept_item,
        const RTreeT< ITEM_INDEX, MAX_ORDER >& tree,
        const RTreeConfigurationT< ALT_FT >& configuration,
        const QUERY_SHAPE& query_shape
    );

    template< typename ITEM_INDEX, int MAX_ORDER, typename ALT_FT >
    friend void updateConfiguration(
        RTreeConfigurationT< ALT_FT >& configuration,
        const RTreeT< ITEM_INDEX, MAX_ORDER >& tree,
        const UT_BoxT< ALT_FT > item_box[],
        const ITEM_INDEX num_items
    );
    friend exint heapMemoryUsage <>( const RTreeConfigurationT< FT >& configuration );
};

//
// Convenience for assigning boxes stored in containers other than built-in arrays
//

template< typename ITEM_INDEX, int MAX_ORDER, typename FT >
void updateConfiguration(
    RTreeConfigurationT< FT >& configuration,
    const RTreeT< ITEM_INDEX, MAX_ORDER >& tree,
    const UT_Array< UT_BoxT< FT > >& item_box
);

//
// Helpers for storing query results in containers
//

// On return, 'results' consists of all items i for which item_box[i] 
// intersects 'query_shape'.
// The contents of "results" from before the call are cleared, so it
// is not neccessary to call results.clear() before calling this function.
template< typename QUERY_SHAPE, typename ITEM_INDEX, int MAX_ORDER, typename FT >
void getIntersecting(
    UT_Array< ITEM_INDEX >& results,
    const RTreeT< ITEM_INDEX, MAX_ORDER >& tree,
    const RTreeConfigurationT< FT >& configuration,
    const QUERY_SHAPE& query_shape
);

// Return all items i for which item_box[ i ] intersects query_box.
// The resulting items will be stored in the range [ items_begin, items_end ),
// where items_end is the return value.
// It is assumed that the array starting at items_begin is large enough
// to contain the results (at most the total number of items).
template< typename QUERY_SHAPE, typename ITEM_INDEX, int MAX_ORDER, typename FT >
ITEM_INDEX* getIntersectingRaw(
    const RTreeT< ITEM_INDEX, MAX_ORDER >& tree,
    const RTreeConfigurationT< FT >& configuration,
    const QUERY_SHAPE& query_shape, 
    ITEM_INDEX*const items_begin
);

// Various R-tree types

// RTree with index type 'int': max number of items is 2^30
// (two most significant bits are used as flags)
using RTree16Int = RTreeT< int, 16 >;
using RTree2Int  = RTreeT< int,  2 >;
using RTreeInt   = RTreeT< int,  2 >;

// RTree with index type 'exint': up to 2^62 items in theory
// (two most significant bits are used as flags)
using RTree = RTreeT< exint,  2 >;

// R-tree box configurations for various float types
using RTreeConfigurationF = RTreeConfigurationT< fpreal32 >;
using RTreeConfigurationD = RTreeConfigurationT< fpreal64 >;
using RTreeConfiguration = RTreeConfigurationT< fpreal64 >;

// R-tree boxes for various float types
using RTreeBoxF = UT_BoxT< fpreal32 >;
using RTreeBoxD = UT_BoxT< fpreal64 >;
using RTreeBox = UT_BoxT< fpreal64 >;

}
// namespace UT

//
// The below typedefs and functions are used by existing code
// that used R-tree before its interface got updated.
//

using UT_RTree16Int = UT::RTree16Int;
using UT_RTree2Int = UT::RTree2Int;
using UT_RTreeInt = UT::RTreeInt;

using UT_RTree = UT::RTree;

template< typename FT > using UT_RTree2IntConfigurationT = UT::RTreeConfigurationT< FT >;
template< typename FT > using UT_RTree16IntConfigurationT = UT::RTreeConfigurationT< FT >;
template< typename FT > using UT_RTreeIntConfigurationT = UT::RTreeConfigurationT< FT >;
template< typename FT > using UT_RTreeConfigurationT = UT::RTreeConfigurationT< FT >;

using UT_RTree2IntConfigurationF = UT_RTree16IntConfigurationT< fpreal32 >;
using UT_RTree16IntConfigurationF = UT_RTree16IntConfigurationT< fpreal32 >;
using UT_RTreeIntConfiguration = UT_RTreeIntConfigurationT< fpreal64 >;

using UT_RTreeConfigurationF = UT::RTreeConfigurationF;
using UT_RTreeConfigurationD = UT::RTreeConfigurationD;
using UT_RTreeConfiguration = UT::RTreeConfiguration;

using UT_BoxF = UT::RTreeBoxF;
using UT_BoxD = UT::RTreeBoxD;
using UT_Box = UT::RTreeBox;

template< typename FT >
UT_RTree16Int UTconstructRTree16Int( const UT_Array< UT_BoxT< FT > >& item_box );

template< typename FT >
UT_RTree2Int UTconstructRTree2Int( const UT_Array< UT_BoxT< FT > >& item_box );

template< typename FT >
UT_RTreeInt UTconstructRTreeInt( const UT_BoxT< FT > item_box[], const UT_RTreeInt::ItemIndex num_items );

template< typename FT >
UT_RTreeInt UTconstructRTreeInt( const UT_Array< UT_BoxT< FT > >& item_box );

template< typename FT >
UT_RTree UTconstructRTree( const UT_BoxT< FT > item_box[], const UT_RTree::ItemIndex num_items );

template< typename FT >
UT_RTree UTconstructRTree( const UT_Array< UT_BoxT< FT > >& item_box );

template< typename FT >
UT_RTree2IntConfigurationT< FT > UTconstructRTree2IntConfiguration( const UT_RTree2Int& tree, const UT_Array< UT_BoxT< FT > >& item_box );

template< typename FT >
UT_RTree16IntConfigurationT< FT > UTconstructRTree16IntConfiguration( const UT_RTree16Int& tree, const UT_Array< UT_BoxT< FT > >& item_box );

template< typename FT >
UT_RTreeIntConfigurationT< FT > UTconstructRTreeIntConfiguration( const UT_RTreeInt& tree, const UT_Array< UT_BoxT< FT > >& item_box );

template< typename FT >
UT_RTreeIntConfigurationT< FT > UTconstructRTreeIntConfiguration( const UT_RTreeInt& tree, const UT_BoxT< FT > item_box[], const UT_RTree::ItemIndex num_items );

template< typename FT >
UT_RTreeConfigurationT< FT> UTconstructRTreeConfiguration( const UT_RTree& tree, const UT_Array< UT_BoxT< FT > >& item_box );

template< typename FT >
auto UTmakeUniqueRTree2Int( const UT_Array< UT_BoxT< FT > >& item_box );

template< typename FT >
auto UTmakeUniqueRTree16Int( const UT_Array< UT_BoxT< FT > >& item_box );

template< typename FT >
auto UTmakeUniqueRTreeInt( const UT_Array< UT_BoxT< FT > >& item_box );

template< typename FT >
auto UTmakeUniqueRTreeInt( const UT_BoxT< FT > item_box[], const UT_RTree::ItemIndex num_items );

template< typename FT >
auto UTmakeUniqueRTree2IntConfiguration( const UT_RTree2Int& tree, const UT_Array< UT_BoxT< FT > >& item_box );

template< typename FT >
auto UTmakeUniqueRTree16IntConfiguration( const UT_RTree16Int& tree, const UT_Array< UT_BoxT< FT > >& item_box );

template< typename FT >
auto UTmakeUniqueRTreeIntConfiguration( const UT_RTreeInt& tree, const UT_Array< UT_BoxT< FT > >& item_box );

template< typename FT >
auto UTmakeUniqueRTreeIntConfiguration( const UT_RTreeInt& tree, const UT_BoxT< FT > item_box[], const UT_RTree::ItemIndex num_items );

#include "UT_RTreeImpl.h"

#endif // __RTree_H__