opennurbs_rtree.h
/* $NoKeywords: $ */
/*
//
// Copyright (c) 1993-2012 Robert McNeel & Associates. All rights reserved.
// OpenNURBS, Rhinoceros, and Rhino3D are registered trademarks of Robert
// McNeel & Associates.
//
// THIS SOFTWARE IS PROVIDED "AS IS" WITHOUT EXPRESS OR IMPLIED WARRANTY.
// ALL IMPLIED WARRANTIES OF FITNESS FOR ANY PARTICULAR PURPOSE AND OF
// MERCHANTABILITY ARE HEREBY DISCLAIMED.
//
// For complete openNURBS copyright information see <http://www.opennurbs.org>.
//
////////////////////////////////////////////////////////////////
*/
#if !defined(OPENNURBS_RTREE_INC_)
#define OPENNURBS_RTREE_INC_
/*
The opennurbs rtree code is a modifed version of the
free and unrestricted R-tree implementation obtianed from
http://www.superliminal.com/sources/sources.htm
The first lines on the website indicate the code is free and unrestricted:
Free Source Code
Here are a few useful bits of free source code.
You're completely free to use them for any purpose whatsoever.
All I ask is that if you find one to be particularly valuable,
then consider sending feedback. Please send bugs and suggestions too.
Enjoy
The readme.txt file included with the R-tree source says
LICENSE:
Entirely free for all uses. Enjoy!
The original authors are
AUTHORS
* 1983 Original algorithm and test code by Antonin Guttman and Michael Stonebraker, UC Berkely
* 1994 ANCI C ported from original test code by Melinda Green - melinda@superliminal.com
* 1995 Sphere volume fix for degeneracy problem submitted by Paul Brook
* 2004 Templated C++ port by Greg Douglas
The opennurbs version adds some custom memory allocation and replaces
the leaf iterator. The rest of the changes are cosmetic.
*/
// Minimum and maximum number of elements
// in ON_RTreeNode::m_branch[].
// must have ON_RTree_MAX_NODE_COUNT > ON_RTree_MIN_NODE_COUNT
#define ON_RTree_MIN_NODE_COUNT 2
#define ON_RTree_MAX_NODE_COUNT 6
/*
In a test of a sphere mesh with mesh: 8385 vertices, 8192 polygons
and ON_RTree_MAX_NODE_COUNT = 3, 4, 5, and 6, the memory use was
most efficient with ON_RTree_MAX_NODE_COUNT=6
Memory Usage MAX_NODE_COUNT = 3
ON_RTree: 1212 KB (1241136) (352 wasted)
ON_RTree: 7036 nodes, 5881 unused branches (321 KB) 0.835844 per node
Memory Usage MAX_NODE_COUNT = 4
ON_RTree: 1152 KB (1179720) (5568 wasted)
ON_RTree: 5051 nodes, 6962 unused branches (380 KB) 1.37834 per node
Memory Usage MAX_NODE_COUNT = 5
ON_RTree: 1040 KB (1065504) (11808 wasted)
ON_RTree: 3655 nodes, 6429 unused branches (351 KB) 1.75896 per node
Memory Usage MAX_NODE_COUNT = 6
ON_RTree: 995 KB (1019592) (3440 wasted)
ON_RTree: 2951 nodes, 6564 unused branches (358 KB) 2.22433 per node
*/
// This struct is used instead of ON_BoundingBox to avoid calling
// constructors.
struct ON_RTreeBBox
{
double m_min[3];
double m_max[3];
};
struct ON_RTreeSphere
{
double m_point[3];
double m_radius;
};
struct ON_RTreeCapsule
{
double m_point[2][3];
double m_radius;
double m_domain[2];
};
struct ON_RTreeBranch
{
ON_RTreeBBox m_rect;
// If ON_RTreeNode.m_level > 0, then m_child points to a child node.
// If ON_RTreeNode.m_level == 0, then m_id identifies the leaf element.
union
{
struct ON_RTreeNode* m_child;
ON__INT_PTR m_id;
};
};
struct ON_RTreeLeaf
{
ON_RTreeBBox m_rect;
ON__INT_PTR m_id;
};
// The ON_RTreeNode is used at root, branch and leaf nodes.
// When m_level > 0, the node is a branch.
// When m_level = 0, the node is a leaf.
struct ON_RTreeNode
{
inline bool IsInternalNode() const
{ return (m_level > 0); } // internal nodes have m_level > 0
inline bool IsLeaf() const
{ return (m_level == 0); } // branch nodes have m_level = 0
// m_level must be a signed int to insure signed compares work correctly
int m_level; // =0 at leaf nodes, > 0 at branch nodes
// The m_branch[] array contains m_count elements
// 0 <= m_count <= ON_RTree_MAX_NODE_COUNT
// m_count must be a signed int to insure signed compares work correctly
int m_count;
ON_RTreeBranch m_branch[ON_RTree_MAX_NODE_COUNT];
};
struct ON_RTreeSearchResult
{
int m_capacity; // m_id[] array capacity (search terminates when m_count == m_capacity)
int m_count; // number of elements in m_id[]
ON__INT_PTR* m_id; // m_id[] = array of search results.
};
class ON_CLASS ON_RTreeMemPool
{
public:
ON_RTreeMemPool( ON_MEMORY_POOL* heap, std::size_t leaf_count );
~ON_RTreeMemPool();
ON_RTreeNode* AllocNode();
void FreeNode(ON_RTreeNode* node);
struct ON_RTreeListNode* AllocListNode();
void FreeListNode(struct ON_RTreeListNode* list_node);
void DeallocateAll();
/*
Returns:
Total number of bytes of heap memory allocated.
*/
std::size_t SizeOf() const;
/*
Returns:
Number of bytes of heap memory not currently in use.
*/
std::size_t SizeOfUnusedBuffer() const;
private:
void GrowBuffer();
struct Blk
{
struct Blk* m_next;
};
// linked list of unused ON_RTreeNode
struct Blk* m_nodes;
// linked list of unused ON_RTreeListNode
struct Blk* m_list_nodes;
// buffer for new allocations
unsigned char* m_buffer;
std::size_t m_buffer_capacity;
struct Blk* m_blk_list; // linked list used to free all allocated memory
std::size_t m_sizeof_blk; // total amount of memory in each block.
ON_MEMORY_POOL* m_heap;
std::size_t m_sizeof_heap; // total amount of heap memory in this rtree
};
////////////////////////////////////////////////////////////////
//
// ON_RTreeIterator
//
// The ON_RTreeIterator class can be used to iterate each leaf
// in an ON_RTree.
//
class ON_CLASS ON_RTreeIterator
{
public:
/*
Description:
Construct an empty iterator. Call Initialize() to attach
the iterator to an R-tree.
Remark:
Any calls to ON_RTree::Insert() or ON_RTree::Remove() that modify
an R-tree being iterated invalidate the iterator. The iterator
must be re-initialized before being used again.
There is no connection between the order elements are inserted
in an R-tree and the order the elements are iterated by an
iterator.
*/
ON_RTreeIterator();
ON_RTreeIterator(const class ON_RTree& a_rtree);
~ON_RTreeIterator();
/*
Description:
Initialize an iterator to iterate every leaf in the rtree.
Parameters:
a_rtree - [in]
R-tree to iterate
Example:
See the comment for ON_RTreeIterator::First().
Returns:
True if a_rtree has at least one element.
Remarks:
Any calls to ON_RTree::Insert() or ON_RTree::Remove() that modify
this node or its children will invalidate this iterator and it
must be re-initialized.
There is no connection between the order elements are inserted
in an R-tree and the order the elements are iterated by an
iterator.
*/
bool Initialize(const class ON_RTree& a_rtree);
/*
Description:
Initialize an iterator to iterate every leaf on or below a_node.
Parameters:
a_node - [in]
R-tree node to iterate
Example:
See the comment for ON_RTreeIterator::First().
Returns:
True if a_node has at least one element.
Remarks:
Any calls to ON_RTree::Insert() or ON_RTree::Remove() that modify
this node or its children will invalidate this iterator and it
must be re-initialized.
There is no connection between the order elements are inserted
in an R-tree and the order the elements are iterated by an
iterator.
*/
bool Initialize(const struct ON_RTreeNode* a_node);
/*
Description:
Get the value of the current leaf element. Calling Value()
does not increment or decrement the iterator.
Example:
See the comment for ON_RTreeIterator::First().
Return:
Null pointer if there are no more leaves to iterate
A pointer to the current R-tree leaf. When there are no more leaves,
the returned pointer is null.
*/
const ON_RTreeBranch* Value() const;
/*
Description:
Reset the iterator so the current leaf is the first leaf in
the R-tree. The Initialize() functions automatically do
this, but First() can be called if an iterator needs to be
used more than once or to make code easy to read and understand.
Example:
Iterate every leaf in an R-tree.
ON_RTree rtree;
...
ON_RtreeIterator rit(rtree);
const ON_RTreeBranch* rtree_leaf;
for ( rit.First(); 0 != (rtree_leaf = rit.Value()); rit.Next() )
{
// leaf id = rtree_leaf->m_id
// leaf bounding box = rtree->m_rect
}
Returns:
True if a call to Value() will return a non-null pointer.
See Also:
ON_RTreeIterator::Last();
*/
bool First();
/*
Description:
Increment the iterator to the next leaf in the R-tree.
Example:
See the comment for ON_RTreeIterator::First()
Returns:
True if a call to Value() will return a non-null pointer.
False if there is not a next leaf and all susequent calls to
Value() will return null.
See Also:
ON_RTreeIterator::Prev();
*/
bool Next();
/*
Description:
Set the iterator so the current leaf is the last leaf in the R-tree.
Example:
Iterate an R-tree in reverse order.
ON_RTree rtree;
...
ON_RTreeIterator rit(rtree);
const ON_RTreeBranch* rtree_leaf;
for ( rit.Last(); 0 != (rtree_leaf = rit.Value()); rit.Prev() )
{
// leaf id = rtree_leaf->m_id
// leaf bounding box = rtree->m_rect
}
Returns:
True if a call to Value() will return a non-null pointer.
See Also:
ON_RTreeIterator::First();
*/
bool Last();
/*
Description:
Decrement the iterator to the previous leaf in the R-tree.
Example:
See the comment for ON_RTreeIterator::Last()
Returns:
True if a call to Value() will return a non-null pointer.
False if there is not a previous leaf and all susequent calls to
Value() will return null.
See Also:
ON_RTreeIterator::Next();
*/
bool Prev();
private:
enum { MAX_STACK = 32 }; // Max stack size. Allows almost n^32 where n is number of branches in node
struct StackElement
{
const struct ON_RTreeNode* m_node;
int m_branchIndex; // must be a signed int to insure signed compares work correctly
};
bool PushChildren(struct StackElement* sp, bool bFirstChild);
StackElement m_stack[MAX_STACK]; // stack
StackElement* m_sp; // stack pointer (null or points into m_stack[])
const ON_RTreeNode* m_root; // root of tree being iterated
};
class ON_CLASS ON_RTree
{
public:
ON_RTree( ON_MEMORY_POOL* heap = 0, std::size_t leaf_count = 0 );
~ON_RTree();
/*
Description:
Create an R-tree with an element for each face in the mesh.
The element id is set to the index of the face.
Parameters:
mesh - [in]
Returns:
True if successful.
*/
bool CreateMeshFaceTree( const class ON_Mesh* mesh );
/*
Description:
Insert an element into the RTree.
Parameters:
a_min - [in]
a_max - [in]
3d bounding box of the element. The values in a_min[3] and a_max[3]
must satisfy
a_min[0] <= a_max[0],
a_min[1] <= a_max[1], and
a_min[1] <= a_max[1].
a_dataId - [in]
id of the element. This can be either a pointer or an integer id.
Returns:
True if element was successfully inserted.
Remarks:
Calling Insert() or Remove() invalidates any ON_RTreeIterator
used to iterate this rtree.
*/
bool Insert(const double a_min[3], const double a_max[3], void* a_element_id);
bool Insert(const double a_min[3], const double a_max[3], int a_element_id);
bool Insert2d(const double a_min[2], const double a_max[2], void* a_element_id);
bool Insert2d(const double a_min[2], const double a_max[2], int a_element_id);
/*
Description:
Remove an element from the RTree.
Parameters:
a_min - [in]
a_max - [in]
3d bounding box of the element. The values in a_min[3] and a_max[3]
must satisfy
a_min[0] <= a_max[0],
a_min[1] <= a_max[1], and
a_min[2] <= a_max[2].
a_dataId - [in]
id of the element. This can be either a pointer or an integer id.
Returns:
True if element was successfully removed.
Remarks:
Calling Insert() or Remove() invalidates any ON_RTreeIterator
used to iterate this rtree.
*/
bool Remove(const double a_min[3], const double a_max[3], void* a_elementId);
bool Remove(const double a_min[3], const double a_max[3], int a_elementId);
bool Remove2d(const double a_min[2], const double a_max[2], void* a_elementId);
bool Remove2d(const double a_min[2], const double a_max[2], int a_elementId);
/*
Description:
Remove all elements from the R-tree.
*/
void RemoveAll();
/*
Description:
Search the R-tree for all elements whose bounding boxes overlap
a_rect.
Parameters:
a_rect - [in/out]
The version of search that has ON_RTreeBBox* a_rect as the first
argument, allows you to shrink the a_rect as the search progresses.
This is useful for doing things like searching for closest points.
If you want to shrink a_rect, you must use a_context to pass it
to the resultCallback function and shrink it in the resultCallback
function. In the callback, the modified rect must be contained
in the previous rect.
a_sphere - [in/out]
The version of search that has ON_RTreeSphere* a_sphere as the first
argument, allows you to shrink the a_sphere as the search progresses.
This is useful for doing things like searching for closest points.
If you want to shrink a_sphere, you must use a_context to pass it
to the resultCallback function and shrink it in the resultCallback
function. In the callback, the modified sphere must be contained
in the previous sphere.
a_capsule - [in/out]
The version of search that has ON_RTreeSphere* a_capsule as the first
argument, allows you to shrink the a_capsule as the search progresses.
This is useful for doing things like searching for closest points.
If you want to shrink a_capsule, you must use a_context to pass it
to the resultCallback function and shrink it in the resultCallback
function. In the callback, the modified capsule must be contained
in the previous capsule.
a_min - [in]
a_max - [in]
(a_min,a_max) is the bounding box of the search region.
a_results - [out]
The ids of elements that overlaps the search region.
resultCallback - [in]
A function to call when leaf nodes overlap.
a_context - [in]
pointer passed to the resultCallback() function.
Returns:
True if entire tree was searched. It is possible no results were found.
Remarks:
If you are using a Search() that uses a resultCallback() function,
then return true to keep searching and false to terminate the search.
*/
bool Search(
ON_RTreeSphere* a_sphere,
bool ON_MSC_CDECL resultCallback(void* a_context, ON__INT_PTR a_id),
void* a_context
) const;
bool Search(
ON_RTreeCapsule* a_capsule,
bool ON_MSC_CDECL resultCallback(void* a_context, ON__INT_PTR a_id),
void* a_context
) const;
bool Search(
ON_RTreeBBox* a_rect,
bool ON_MSC_CDECL resultCallback(void* a_context, ON__INT_PTR a_id),
void* a_context
) const;
/*
Description:
Search the R-tree for all elements whose bounding boxes overlap
the set of points between to parallel planes.
Parameters:
a_plane_eqn - [in]
a_min - [in]
a_max - [in]
The region between the parallel planes is the set point points
where the value of the plane equation is >= a_min and <= a_max.
resultCallback - [in]
A function to call when leaf nodes overlap the region between
the parallel planes.
a_context - [in]
pointer passed to the resultCallback() function.
Returns:
True if entire tree was searched. It is possible no results were found.
Remarks:
If you are using a Search() that uses a resultCallback() function,
then return true to keep searching and false to terminate the search.
*/
bool Search(
const double a_plane_eqn[4],
double a_min,
double a_max,
bool ON_MSC_CDECL resultCallback(void* a_context, ON__INT_PTR a_id),
void* a_context
) const;
bool Search(const double a_min[3], const double a_max[3],
bool ON_MSC_CDECL resultCallback(void* a_context, ON__INT_PTR a_id), void* a_context
) const;
bool Search(const double a_min[3], const double a_max[3],
ON_RTreeSearchResult& a_result
) const;
bool Search(const double a_min[3], const double a_max[3],
ON_SimpleArray<ON_RTreeLeaf>& a_result
) const;
bool Search(const double a_min[3], const double a_max[3],
ON_SimpleArray<void*>& a_result
) const;
bool Search(const double a_min[3], const double a_max[3],
ON_SimpleArray<int>& a_result
) const;
bool Search2d(const double a_min[2], const double a_max[2],
bool ON_MSC_CDECL resultCallback(void* a_context, ON__INT_PTR a_id), void* a_context
) const;
bool Search2d(const double a_min[2], const double a_max[2],
ON_RTreeSearchResult& a_result
) const;
bool Search2d(const double a_min[2], const double a_max[2],
ON_SimpleArray<ON_RTreeLeaf>& a_result
) const;
bool Search2d(const double a_min[2], const double a_max[2],
ON_SimpleArray<void*>& a_result
) const;
bool Search2d(const double a_min[2], const double a_max[2],
ON_SimpleArray<int>& a_result
) const;
/*
Description:
Search two R-trees for all pairs elements whose bounding boxes overlap.
Parameters:
a_rtreeA - [in]
a_rtreeB - [in]
tolerance - [in]
If the distance between a pair of bounding boxes is <= tolerance,
then the pair is added to a_result[].
a_result - [out]
Pairs of ids of elements who bounding boxes overlap.
Returns:
True if entire tree was searched. It is possible no results were found.
*/
static bool Search(
const ON_RTree& a_rtreeA,
const ON_RTree& a_rtreeB,
double tolerance,
ON_SimpleArray<ON_2dex>& a_result
);
/*
Description:
Search two R-trees for all pairs elements whose bounding boxes overlap.
Parameters:
a_rtreeA - [in]
a_rtreeB - [in]
tolerance - [in]
If the distance between a pair of bounding boxes is <= tolerance,
then resultCallback() is called.
resultCallback - [out]
callback function
a_context - [in] argument passed through to resultCallback().
Returns:
True if entire tree was searched. It is possible no results were found.
*/
static bool Search(
const ON_RTree& a_rtreeA,
const ON_RTree& a_rtreeB,
double tolerance,
void ON_MSC_CDECL resultCallback(void* a_context, ON__INT_PTR a_idA, ON__INT_PTR a_idB),
void* a_context
);
/*
Description:
Search two R-trees for all pairs elements whose bounding boxes overlap.
Parameters:
a_rtreeA - [in]
a_rtreeB - [in]
tolerance - [in]
If the distance between a pair of bounding boxes is <= tolerance,
then resultCallback() is called.
resultCallback - [out]
callback function
Return true for the search to continue and false to terminate the search.
a_context - [in] argument passed through to resultCallback().
Returns:
True if entire tree was searched. It is possible no results were found.
*/
static bool Search(
const ON_RTree& a_rtreeA,
const ON_RTree& a_rtreeB,
double tolerance,
bool ON_MSC_CDECL resultCallback(void* a_context, ON__INT_PTR a_idA, ON__INT_PTR a_idB),
void* a_context
);
/*
Returns:
Number of elements (leaves).
Remark:
No internal count is maintained, so this function traverses the
tree to count the leaves. If efficiency is important, save the
result.
*/
int ElementCount();
/*
Returns:
Pointer to the root node.
*/
const ON_RTreeNode* Root() const;
/*
Returns:
Bounding box of the entire R-tree;
*/
ON_BoundingBox BoundingBox() const;
/*
Returns:
Number of bytes of heap memory used by this R-tree.
*/
std::size_t SizeOf() const;
private:
void SplitNode(ON_RTreeNode*, ON_RTreeBranch*, ON_RTreeNode**);
bool AddBranch(ON_RTreeBranch*, ON_RTreeNode*, ON_RTreeNode**);
bool InsertRectRec(ON_RTreeBBox*, ON__INT_PTR, ON_RTreeNode*, ON_RTreeNode**, int);
bool InsertRect(ON_RTreeBBox*, ON__INT_PTR, ON_RTreeNode**, int);
void LoadNodes(ON_RTreeNode*, ON_RTreeNode*, struct ON_RTreePartitionVars*);
bool RemoveRect(ON_RTreeBBox*, ON__INT_PTR, ON_RTreeNode**);
bool RemoveRectRec(ON_RTreeBBox*, ON__INT_PTR, ON_RTreeNode*, struct ON_RTreeListNode**);
void ReInsert(ON_RTreeNode*, struct ON_RTreeListNode**);
void RemoveAllRec(ON_RTreeNode*);
ON_RTreeNode* m_root;
std::size_t m_reserved;
ON_RTreeMemPool m_mem_pool;
};
#endif
ON_RTreeSphere::m_radius
double m_radius
Definition: opennurbs_rtree.h:93
ON_RTreeBBox::m_min
double m_min[3]
Definition: opennurbs_rtree.h:86
ON_RTreeSphere
Definition: opennurbs_rtree.h:90
ON_RTreeNode::m_branch
ON_RTreeBranch m_branch[ON_RTree_MAX_NODE_COUNT]
Definition: opennurbs_rtree.h:139
ON_RTreeNode::m_level
int m_level
Definition: opennurbs_rtree.h:133
ON_RTreeBranch::m_rect
ON_RTreeBBox m_rect
Definition: opennurbs_rtree.h:105
ON_RTreeLeaf::m_id
ON__INT_PTR m_id
Definition: opennurbs_rtree.h:119
ON_RTreeNode
Definition: opennurbs_rtree.h:125
ON_RTreeCapsule::m_point
double m_point[2][3]
Definition: opennurbs_rtree.h:98
ON_RTreeBranch::m_child
struct ON_RTreeNode * m_child
Definition: opennurbs_rtree.h:111
ON_RTreeCapsule
Definition: opennurbs_rtree.h:96
ON_RTreeSearchResult::m_count
int m_count
Definition: opennurbs_rtree.h:145
ON_SimpleArray
Definition: opennurbs_array.h:46
ON_BoundingBox
Definition: opennurbs_bounding_box.h:25
ON_RTreeSearchResult
Definition: opennurbs_rtree.h:142
ON_RTreeBBox
Definition: opennurbs_rtree.h:84
ON_Mesh
Definition: opennurbs_mesh.h:989
ON_RTreeMemPool
Definition: opennurbs_rtree.h:149
ON_RTreeCapsule::m_radius
double m_radius
Definition: opennurbs_rtree.h:99
ON_RTreeLeaf::m_rect
ON_RTreeBBox m_rect
Definition: opennurbs_rtree.h:118
ON_RTreeNode::m_count
int m_count
Definition: opennurbs_rtree.h:138
ON_RTreeCapsule::m_domain
double m_domain[2]
Definition: opennurbs_rtree.h:100
ON_RTree
Definition: opennurbs_rtree.h:378
ON_RTreeNode::IsLeaf
bool IsLeaf() const
Definition: opennurbs_rtree.h:129
ON_RTreeSphere::m_point
double m_point[3]
Definition: opennurbs_rtree.h:92
ON_RTreeBBox::m_max
double m_max[3]
Definition: opennurbs_rtree.h:87
ON_RTreeBranch
Definition: opennurbs_rtree.h:103
ON_RTreeNode::IsInternalNode
bool IsInternalNode() const
Definition: opennurbs_rtree.h:127
ON_RTreeSearchResult::m_capacity
int m_capacity
Definition: opennurbs_rtree.h:144
ON_RTreeLeaf
Definition: opennurbs_rtree.h:116
ON_RTreeIterator
Definition: opennurbs_rtree.h:206
ON_RTreeSearchResult::m_id
ON__INT_PTR * m_id
Definition: opennurbs_rtree.h:146
ON_RTreeBranch::m_id
ON__INT_PTR m_id
Definition: opennurbs_rtree.h:112