cgal
cgal copied to clipboard
CGAL
Nef_3: Allocate a big enough vector for the nodes of the K3_tree
Summary of Changes
Replace the boost::container::deque<Node> nodes; by an std::vector<Node> and reserve (too much) .
Release Management
- Affected package(s): Nef_3
When you say "(too much)", is it worst case O(n) or something else? (I use Big-O to refer to memory not speed)
Do you think it could be made more accurate by pre-processing the vertices, to calculate the number of nodes needed? this could also be done when applying "presorting the data in each of k dimensions prior to building the tree", as per: https://jcgt.org/published/0004/01/03/
I made it of size 2 * number of elements to store in case that each leaf node stores only one element, in order to be sure that no reallocation happens.
I made it of size 2 * number of elements to store in case that each leaf node stores only one element, in order to be sure that no reallocation happens.
That sounds reasonable.Previously I made this change:
https://github.com/CGAL/cgal/blob/68a1fb4aad6741a56cc25d045abd3dd620dacdc8/Nef_3/include/CGAL/Nef_3/K3_tree.h#L650
To ensure that each leaf contains at least two vertices. So changing this back or changing the 2 * might be worth investigation?
To ensure that each leaf contains at least two vertices. So changing this back or changing the
2 *might be worth investigation?
I missed that. You are right that the 2 * is then not needed.
I missed that. You are right that the
2 *is then not needed.
I think I should explain why I made that change. The K3_tree is mostly intended for looking up objects. Since an edge always contains 2 points, it doesn't make sense to me to split smaller than 2 points. Obviously, in the case where it is finding a vertex it now has at least 2 to check, but I didn't think this made a significant difference.
#include <CGAL/Exact_predicates_exact_constructions_kernel.h>
#include <CGAL/Polyhedron_3.h>
#include <CGAL/Nef_polyhedron_3.h>
#include <iostream>
using K = CGAL::Exact_predicates_exact_constructions_kernel;
using P = CGAL::Polyhedron_3<K>;
using N = CGAL::Nef_polyhedron_3<K>;
using V = CGAL::Vector_3<K>;
int main(int argc, char* argv[])
{
std::ifstream cube("cube.off"); // cube.off is attached to comment in cube.zip file
P p;
cube >> p;
N result;
for(int i=0; i<=33; i+=11) {
N n(p);
CGAL::Aff_transformation_3<K> t(CGAL::TRANSLATION,V(0,0,i));
n.transform(t);
result += n;
}
}
@afabri Hello, and Happy New Year :confetti_ball: :tada:
The number of nodes in a kd-tree depends on the number of points you are inserting and the structure of the tree. It is not possible to determine the number of nodes in the tree without more information.
If the points are uniformly distributed, the tree is likely to have a balanced structure, with roughly the same number of points in each leaf node. On the other hand, if the points are concentrated in a small region of the space, the tree is likely to be more imbalanced, with some leaf nodes having many points and others having few points.
Furthermore, if the std::vector is under-allocated when it grows the referential integrity of the vector is invalidated, which is what causes the crash in my comment
Therefore the best approach is to revert back to using std::deque, which does not invalidate pointers, references, or iterators when it grows. However, I realise initially the whole purpose of the change was to use a container which could be preallocated, even though I don't think this can be done, you made some other changes which I still think are worthwhile.
--- a/Nef_3/include/CGAL/Nef_3/K3_tree.h
+++ b/Nef_3/include/CGAL/Nef_3/K3_tree.h
@@ -210,7 +210,7 @@ private:
Object_list object_list;
};
- typedef std::vector<Node> Node_range;
+ typedef std::deque<Node> Node_range;
typedef Node* Node_handle;
@@ -437,7 +437,6 @@ public:
CGAL_NEF_TRACEN("reference counted " << reference_counted);
#endif
non_efective_splits=0;
- nodes.reserve(vertices.size() + edges.size() + facets.size());
root = build_kdtree(vertices, edges, facets, 0);
}
const Object_list& objects_around_point( const Point_3& p) const {
Hello @GilesBathgate, All the best for the new year. And please never give up on reminders. They are really appreciated, and you see that it also works. Best, Andreas