Proposal for Adaptable Shape-Aware Generic Queries

[NullSenseStudio]

Summary

Queries can be easily split into two categories: ordered (nearest_, farthest_) and unordered (traverse, traverse_iterator).
Traits for supporting these categories can be defined in a way to allow simple adaptation, match shapes based on their specific geometry, and returning a byproduct produced by the query to shape interaction, while not being overly complicated for implementation. Existing traversal functions should be replaced to match the naming of the kind of query they use and have return type parity.

Current Limitations

• traverse/traverse_iterator
  • doesn't match shapes wrt their geometry, only their AABB
  • generic implementation does not support inverted queries without defining a separate query
• nearest_traverse_iterator/farthest_traverse_iterator
  • doesn't match shapes wrt their geometry, only their AABB
  • non-generic query, only rays
  • ordering by AABB distance is not always the same as ordering by shape distance Nearest AABB Traversal Is Insufficient for Nearest Shape Traversal #159
  • no fast, non-allocating method for only the first ray hit
• nearest_child_traverse_iterator/farthest_child_traverse_iterator
  • similar issues to the methods which replaced it above
• nearest_to
  • non-generic query, only points
  • requires different shape structs for multiple distance queries on the same type of shape (nearest vertex, edge, or surface of a triangle for instance)
  • no way to whitelist/blacklist shapes without building a different BVH and prefiltering all shapes
  • doesn't support returning more than one shape (k-nearest neighbors)
  • doesn't return additional information produced by the query (surface point, vertex index, etc)

Adaptation

What I mean by adaptation is having extra methods on query objects that adjust how they operate. It's similar to function chains on iterators.

For unordered queries these can be things like:

• shape_filter((&Shape) -> bool) -> ShapeFilter (whitelist/blacklist shapes before adding to collection/iterator)
• map_byproduct<B>((&Shape, Self::Byproduct) -> B) -> MapByproduct<Byproduct=T> (allow for mutating/removing of parts of the byproduct to only what you need, less allocation/stack usage)
• or(UnorderedQuery) -> OrQuery
• and(UnorderedQuery) -> AndQuery
• invert() -> InvertedQuery

And for ordered queries:

• shape_filter((&Shape) -> bool) -> ShapeFilter (whitelist/blacklist shapes before adding to collection/iterator)
• traverse_filter(UnorderedQuery) -> TraverseFilter (limit visited nodes and returned shapes to ones matching both the OrderedQuery and UnorderedQuery)
• distance_in(RangeBounds<T>) -> DistanceFilter (limit visited nodes and returned shapes within a range)
• map_byproduct<B>((&Shape, Self::Byproduct) -> B) -> MapByproduct<Byproduct=T> (allow for mutating/removing of parts of the byproduct to only what you need, less allocation/stack usage)
• rev() -> ReversedQuery

Traverse Methods

I'd like to replace the current methods with ones specific to their kind of query and allow for returned types/fast paths that some are missing.
These can be reduced down to [un]ordered_collect::<FromQuery> and [un]ordered_iter with helper methods like: [un]ordered_first = [un]ordered_collect::<Option<_>>, [un]ordered_vec = [un]ordered_collect::<Vec<_>>, and [un]ordered_inline::<const N> = [un]ordered_collect::<heapless::Vec<_, N>>.

FromQuery Traits

Allows traversal functions to have one implementation for various collection type outputs.

trait FromUnorderedQuery<'shape, Shape, Byproduct> {
    /// Initialize empty
    fn new() -> Self;

    /// Indicate to unordered traversal functions whether it should stop traversal for limited size collections like Option and heapless::Vec
    fn is_full(&self) -> bool;

    /// Insert an item into the collection
    fn ingress(&self, shape: &'shape Shape, byproduct: Byproduct);
}

trait FromOrderedQuery<'shape, T: BHValue, Shape, Byproduct> {
    /// Initialize empty
    fn new() -> Self;

    /// Indicate to ordered traversal functions whether the distance of a shape or node is greater than or equal to the maximum contained distance for limited size collections like Option and heapless::Vec
    fn is_distance_excluded(&self, distance: T) -> bool;

    /// Insert an item into the collection. The collection may have to be insertion sorted to keep track of the maximum contained distance, or lazy sorted in ordered_egress for non-limited size collections. When full it should silently fail if is_distance_excluded returns true, or pop the maximum distance shape when it returns false
    fn ingress(&self, shape &'shape Shape, distance: T, byproduct: Byproduct);

    /// Called after traversal is finished and before the collection is returned. Modifies contained distances with the OrderedQuery::external_distance function and sorts if necessary
    fn egress<const D: usize>(&self, query: &impl OrderedQuery<'shape, T, D, Shape>);
}

Coverage Enum

Indicates to traversal functions whether a node is relevant to the query.

enum Coverage {
    /// All descendants can't match the query, do not traverse children
    Excluded,
    /// Can't determine whether all descendants are included or not
    Pending,
    /// All descendants match the query, unordered queries don't need to perform AABB tests on descendants
    Included,
}

Using an enum (rather than a boolean in the IntersectsAabb trait) allows for inverting an unordered query, where Excluded and Included are inversions of each other and pending is the inversion of itself.

NodeState Trait

When a query is a composite of multiple queries it can be beneficial to keep track of coverage for each to not test more than what's necessary. Enables parent to child short-circuit evaluation for "or" type of queries.

trait NodeState {
    /// Initialize to a neutral state
    fn new_pending() -> Self;

    /// The combined coverage of the internal state
    fn coverage(&self) - Coverage;
}

UnorderedQuery Trait

Would "boolean" prefixes be preferred over "unordered"?

trait UnorderedQuery<'shape, T: BHValue, const D: usize, Shape> {
    /// Any additional information produced by the query
    type Byproduct;
    /// State tracking from parent to child nodes
    type State: NodeState;

    /// Determines if a node is relevant to the query
    fn aabb_match(&self, state: &Self::State, aabb: &Aabb<T, D>) -> Self::State;

    /// Determines if a shape is relevant to the query, returning Some when it is
    fn shape_match(&self, state: &Self::State, shape: &'shape Shape, shape_index: usize) -> Option<Byproduct>
}

OrderedQuery Trait

Would "distance" prefixes be preferred over "ordered"?

trait OrderedQuery<'shape, T: BHValue, const D: usize, Shape> {
    /// Any additional information produced by the query
    type Byproduct;
    /// State tracking from parent to child nodes
    type State: NodeState;

    /// Determines if a node is relevant to the query and calculates its minimum and maximum distance
    fn aabb_distance(&self, state: &Self::State, aabb: &Aabb<T, D>) -> (RangeInclusive<T>, Self::State)

    /// Determines if a shape is relevant to the query and calculates its distance, returning Some when it is
    fn shape_distance(&self, state: &Self::State, shape: &'shape Shape) -> Option<(T, Self::Byproduct)>

    /// Modifies distances such as those from OrderedQuery::distance_in so they may be accurately compared against distances used during traversal
    fn internal_distance(&self, external_distance: T) -> T;

    /// Modifies distances before they are returned, allowing for a different distance to be used during traversal such as squared or negated
    fn external_distance(&self, internal_distance: T) -> T;
}

// Ordered queries can act as unordered queries through a blanket implementation that removes distance info
impl<...> UnorderedQuery<...> for OrderedQuery<...> {
    ...
}

Backwards Compatibility

For the most part traversal methods match the use of what they're replacing:

Old	New
traverse(&query, &shapes)	unordered_vec(&query, &shapes)
traverse_iterator(&query, &shapes)	unordered_iter(&query, &shapes)
nearest_traverse_iterator(&ray, &shapes)	ordered_iter(&ray, &shapes)
farthest_traverse_iterator(&ray, &shapes)	ordered_iter(&ray.rev(), &shapes)
nearest_to(point, &shapes)	ordered_first(&point, &shapes)

With the exception of no match for the nearest_child_traverse_iterator and farthest_child_traverse_iterator, which in my opinion both shouldn't have been kept when they were replaced. Ordered iterators could be implemented with heapless::BinaryHeap to keep its non-allocating behavior but without its ordering issues.

Built-in query objects could only be implemented for built-in shapes since queries would also be responsible for shape tests. Though if we want to match current non-shape-aware behavior they may be implemented to generically handle any shape, but only re-test their AABBs in UnorderedQuery::match_shape and OrderedQuery::shape_distance, which I don't recommend.

The PointDistance trait may be kept with a blanket implementation for OrderedQuery so that nalgebra::Point may still be used as a query.

Remarks

Thanks for reading! I know it's a lot to look through. Feel free to ask me to clarify anything here or post your own opinions on this.

I am willing to work on this myself. I'll wait to know if this proposal is generally accepted as is or if any tweaks should be made first.

[svenstaro]

@finnbear What do you think?

[finnbear]

Thanks for your proposal; I've read this twice and here are my thoughts :)

while not being overly complicated for implementation

👀

Existing traversal functions should be replaced

It would be a good sign if the old ones could be re-implemented in terms of the new ones, with no loss in performance. They could then be deprecated for a while, instead of removed (an immediate breaking change).

generic implementation [of traverse/traverse_iterator] does not support inverted queries without defining a separate query

I'm guessing you mean returning all shapes not matched by the original query.

[nearest_traverse_iterator/farthest_traverse_iterator] non-generic query, only rays
[nearest_to] non-generic query, only points

While neither is generic, they do similar things that may cover common use cases, while remaining simple and well-defined (albeit buggy in the case of the former).

no fast, non-allocating method for only the first ray hit

I agree that such an API should exist.

shape_filter((&Shape) -> bool) -> ShapeFilter

Sorry if I missed this, but do your proposed queries implement Rust's Iterator trait? If so, I would expect Iterator::filter to work, and I see the motivation of shape_filter as enabling query composition. If not Iterator, this seems like a regression (in how idiomatic the library is) compared to the old API's.

map_byproduct<B>((&Shape, Self::Byproduct) -> B) -> MapByproduct<Byproduct=T>

Please give one, simple example of using a "byproduct" to help explain what you mean by that.

limit visited nodes and returned shapes to ones matching both the OrderedQuery and UnorderedQuery

I suspect that limiting to visited nodes on some of these operators would produce unintended, chaotic consequences. Especially with distance_in, as the lower distance bound could affect whether large parent nodes that encompass the entire query are traversed. If added, it might require some warnings in the documentation.

I'd like to replace the current methods with ones specific to their kind of query and allow for returned types/fast paths that some are missing.
FromUnorderedQuery
FromOrderedQuery

These seem reasonable, except for the implication that the old API's should be removed.

/// Indicate to ordered traversal functions whether the distance of a shape or node is greater than or equal to the maximum contained distance for limited size collections like Option and heapless::Vec
    fn is_distance_excluded(&self, distance: T) -> bool;

I don't understand why a floating point distance would be used to limit which items can be inserted into a finite integer number of slots.

Using an enum (rather than a boolean in the IntersectsAabb trait)

/// All descendants match the query, unordered queries don't need to perform AABB tests on descendants
    Included,

To state the obvious, the IntersectsAabb trait is oblivious to the descendants.

Would "boolean" prefixes be preferred over "unordered"?
Would "distance" prefixes be preferred over "ordered"?

I think ordered/unordered are fine.

With the exception of no match for the nearest_child_traverse_iterator and farthest_child_traverse_iterator, which in my opinion both shouldn't have been kept when they were replaced.

I agree - they don't need to be replaced, but I would be against removing them without a period of deprecation, just in case.

I am willing to work on this myself. I'll wait to know if this proposal is generally accepted as is or if any tweaks should be made first.

This proposal adds significant flexibility but also significant complexity. It's not obvious to me how to implement this, especially as you imply that a byproduct of the generic implementation would be a fix for #159 which affects a specific implementation. I'm not inclined to accept (or deny) this, but I'm happy to review code that implements it ❤️

[NullSenseStudio]

It would be a good sign if the old ones could be re-implemented in terms of the new ones, with no loss in performance. They could then be deprecated for a while, instead of removed (an immediate breaking change).

I had actually made the OrderedQuery variant before figuring it would be a good idea to ask for opinions on the whole proposal here, which matched nearest_to's performance when collecting to an Option. Although without the NodeState or farthest aabb distance calculation, which I expect the compiler can optimize it away when it's unused.

I'm guessing you mean returning all shapes not matched by the original query.

Yes

Sorry if I missed this, but do your proposed queries implement Rust's Iterator trait? If so, I would expect Iterator::filter to work, and I see the motivation of shape_filter as enabling query composition. If not Iterator, this seems like a regression (in how idiomatic the library is) compared to the old API's.

No they are not iterators, I just mention them due to their similarity. Take for instance:

iter.filter(|x| x.color == RED).rev()
query.shape_filter(|x| x.color == RED).rev()

They both largely do the same thing, but the Iterator trait is not efficient for BVH traversal due to needing to keep track of a stack for unordered queries or binary heap for ordered queries. The role of the query is to define which nodes and shapes of the BVH to traverse and in what order before being pushed to a collection or iterator.

Please give one, simple example of using a "byproduct" to help explain what you mean by that.

UV coordinates of a ray to triangle intersection. Currently shape tests are done outside of the traversal functions so you have direct access to that but with shape ordering issues. Since the shape tests are moved into the query it needs a way to forward those produced UV coordinates into the collection or iterator, otherwise you'd need redundant calculations to get them afterward.

I suspect that limiting to visited nodes on some of these operators would produce unintended, chaotic consequences. Especially with distance_in, as the lower distance bound could affect whether large parent nodes that encompass the entire query are traversed. If added, it might require some warnings in the documentation.

I don't think you'll have to worry about distance_in. As long as the ranges produced by aabb_distance and the one provided by distance_in overlap or one encompasses the other then the nodes will be traversed. Though having query.rev().distance_in() could be troublesome in that order as rev swaps and negates the start and end of the range produced by aabb_distance.

These seem reasonable, except for the implication that the old API's should be removed.

Sure, deprecating or removal can be considered later.

I don't understand why a floating point distance would be used to limit which items can be inserted into a finite integer number of slots.

For ordered queries it's important that fixed-size collections receive the lowest distance shapes. During traversal these shapes would be inserted in a semi-sorted manner with their distance determining whether they are better suited than what's currently in the collection. Having this separate from ingress as well allows for pruning of parent nodes where their lowest possible distance is higher than what's currently in the collection. This matches the behavior of nearest_to's recursive function while allowing for more than just Option.

To state the obvious, the IntersectsAabb trait is oblivious to the descendants.

Yes, the current trait is more akin to true being Pending and false being Excluded. Adding to that, the Included variant would be meaningful to box queries when the query fully encompasses an aabb.

I'm not inclined to accept (or deny) this, but I'm happy to review code that implements it ❤️

Thanks!

[finnbear]

Thanks, your response makes sense!

the Iterator trait is not efficient for BVH traversal due to needing to keep track of a stack for unordered queries or binary heap for ordered queries. The role of the query is to define which nodes and shapes of the BVH to traverse and in what order before being pushed to a collection or iterator.

Based on what you said, here is my understanding, which could be wrong:

Operation	Iterator	Query	Efficiency
Get all results	for r in iter	for r in ordered_iter(query)	*Greater?
Get only first result	iter.next()	ordered_first(query)	Equal?
Get first 2 results	for r in iter.take(2)	for r in ordered_iter(query).take(2)	**Less?

* because you claimed iterators were inefficient for this
** because it sounds like you are proposing to collect all the results and then "push" them to an iterator. is this where collecting the query into a heapless::Vec<_, 2> comes in?

[NullSenseStudio]

* because you claimed iterators were inefficient for this

Sorry for the confusion. Queries aren't iterators the same way rays and IntersectsAabb aren't iterators, but may be used to guide BVH iterators in their own defined way. [un]ordered_iter returns an iterator just like traverse_iterator or nearest_traverse_iterator do.

** because it sounds like you are proposing to collect all the results and then "push" them to an iterator. is this where collecting the query into a heapless::Vec<_, 2> comes in?

No, the iterators will still behave the same in returning a result from Iterator::next when it first matches a shape (unordered), or when it's not possible for another shape to have a lower distance (ordered). Iterators on this proposed query design will largely be copied and pasted from existing ones, just with any needed changes to operate with the query instead of what they currently do.

ordered_first(&query, &shapes) has an efficiency advantage over ordered_iter(&query, &shapes).next() in using a recursive function rather than pushing and popping with a binary heap. The same goes for ordered_collect::<heapless::Vec<_, 2>>(&query, &shapes) vs ordered_iter(&query, &shapes).take(2).

[finnbear]

Thanks for the clarification. I have no further questions, and I'm looking forward to seeing a proof of concept :)

Since bvh::Bvh internals are pub, you can probably use/publish your queries with bvh regardless of whether your changes are ultimately accepted into bvh itself.

[NullSenseStudio]

Would it be preferred to split this into multiple PRs or just one? I figured splitting it starting with unordered query, then ordered, and finally the adaptation methods.

[finnbear]

I will review your changes in any format you choose. Please be aware that, within a 'ready' PR, commits should each have a meaningful name and content and collectively form a logical progression (e.g. feature + docs, add test, add fuzzing). For me, this typically means rebasing smaller commits into larger, properly-named ones.