As a motivation, let me summarize a few things about how octrees are queried:
A query for data in a geometric primitive, like an Obb, is made
The usual representation of that geometric primitive doesn't support efficient intersection testing, instead it needs to compute derived data (intersecting axes usually, but Cell for the CellIDs in S2 queries)
We do many intersection tests against different octree nodes, and the computed data should not get re-computed each time, instead it should get cached/reused.
Then, once nodes are identified, the points in them are filtered using the PointCulling trait's contains() method.
Currently the caching is done in a pretty ad-hoc manner:
Frustum and Obb currently define an extra struct that holds the separating axes.
There is no caching for S2 and Aabb queries.
AllPoints queries do not need caching.
With this change:
The part about intersection testing is spilt off from point filtering, i.e. PointCulling no longer has an intersect_aabb() method.
Instead, all the PointLocation variants implement a trait to produce an intersection testing structure (it can be identical to itself) named HasAabbIntersector.
The produced intersection testing structure or "intersector" can borrow from, or be identical to, the geometric primitive. It can be reused many times and implements the actual IntersectAabb trait.
Benefits:
Better performance by caching S2 and Aabb queries
We can now write generic code over all PointLocation variants which receives an impl HasAabbIntersector. Compare nodes_in_location() in octree/mod.rs.
Capturing de-facto patterns like this with traits seems like a good idea because it forces new queries to follow them and it's cognitively easier: If you have something that implements HasAabbIntersector, you know you can search the octree nodes with it.
Drawbacks:
We should be able to tell Rust that any ConvexPolyhedron implementor is also a HasAabbIntersector implementor, but I got some conflicting traits errors. Resolving this would save us a few boilerplate implementations.
As a motivation, let me summarize a few things about how octrees are queried:
Cellfor theCellIDs in S2 queries)PointCullingtrait'scontains()method.Currently the caching is done in a pretty ad-hoc manner:
With this change:
PointCullingno longer has anintersect_aabb()method.PointLocationvariants implement a trait to produce an intersection testing structure (it can be identical to itself) namedHasAabbIntersector.IntersectAabbtrait.Benefits:
PointLocationvariants which receives animpl HasAabbIntersector. Comparenodes_in_location()in octree/mod.rs.HasAabbIntersector, you know you can search the octree nodes with it.Drawbacks:
ConvexPolyhedronimplementor is also aHasAabbIntersectorimplementor, but I got some conflicting traits errors. Resolving this would save us a few boilerplate implementations.