Advice for implementing Envelope

[ckaran]

I'm working on developing a continuous collision detection system, and just realized that for what I'm doing it makes more sense to use object-oriented capsules. Basically, I have a large set of hyperspheres that are each moving with their own individual velocities, and I need to know when they start or stop intersecting. My plan is to create a tree with n + 1 dimensions, where the extra dimension is time. A sphere's location will then include time as well as it's position. A minimal volume capsule that is oriented along the line segment defined by the sphere's center's start and end point removes most uninteresting points quickly, which is the whole point of having the r* tree.

My problem is that rstar doesn't implement a capsule Envelope type, so I need to figure out how to do it myself, which is the point of this issue. I need to understand the various required methods better so that I can properly implement my capsule type. So, here are my questions:

• new_empty creates a new, empty envelope, but the docs don't state what the expected shape of the envelope is. Looking at the code for AABB, it looks like we're supposed to create an envelope that encompasses the maximum volume possible. Is this correct?
• For merge, is it allowed to move self's center? What about its orientation? Based on the AABB code, it appears that the center is recalculated each time, so I'm guessing that moving the center is OK, I just want to be sure. I don't think this is a problem for merged as you're creating a brand new envelope, but if it is, I'd like to know.
• area really means volume, correct? How accurate does this need to be? If we have to round this value, do we round up or down?
• How accurate does intersection_area have to be? Do we round up or down? As a side note, the intersections of capsules are not in general capsules. Calculating this volume is going to be slow; is there a good way to avoid doing this as much as possible?
• For distance_2 Is this always supposed to be the distance from the point to the closest point enclosed by the envelope? This seems to be what the AABB code is effectively doing, but I just want to be sure.
• Can you explain min_max_dist_2 a bit more? I'm still not getting it.
• What is margin_value? What is the margin? If I have to round a value, do I round up or down?
• Which point should I use to sort the envelopes by in sort_envelopes? How does it apply to envelopes that are object oriented rather than axis-oriented? I'm thinking about two capsules whose centers coincide and are the same shape, but one is rotated 180 degrees relative to the other. Physically they are the same, but since their endpoints are reversed, this could have an effect.
• What precisely is partition_envelopes trying to accomplish??? I really can't tell.

[Stoeoef]

Yep, Envelope is rather left undocumented at the moment. It's meant as an extension point for other coordinate types like longitude / latitude points or repeating groups. Since that has not been done yet, there are no other implementations to look at available. Note: Your "capsules" link above links to the Envelope documentation, is this on purpose?

I'm happy to see someone try to implement another Envelope type as this will hopefully give new insights about the "right" Envelope abstraction. However, it might be that r-trees cannot offer what you really plan to do - they were designed with other problems in mind. That's just a disclaimer that I'm not entirely sure if r-trees are the best fit for your use case. That being said, I'll do my best to elaborate a bit on your questions:

new_empty creates a new, empty envelope, but the docs don't state what the expected shape of the envelope is.

Any envelope created by new must behave "nicely" with other envelopes:

• A new envelope does not intersect any other envelope
• other_envelope.merge(new_envelope) must be other_envelope
• area needs to be 0 (maybe <= 0, I'm not sure)

Looking at the code for AABB, it looks like we're supposed to create an envelope that encompasses the maximum volume possible. Is this correct?

The AABB::new_empty creates a bounding box with the maximum negative value! That's a small optimization to store implicitly that this is a "new" envelope. The usual precondition envelope.lower() < envelope.upper() is intentionally violated.

For merge, is it allowed to move self's center? What about its orientation? Based on the AABB code, it appears that the center is recalculated each time, so I'm guessing that moving the center is OK, I just want to be sure. I don't think this is a problem for merged as you're creating a brand new envelope, but if it is, I'd like to know.

Yes, moving the center is allowed. The only condition that must be met is that the resulting envelope contains the source envelopes.

How accurate does intersection_area have to be? Do we round up or down? As a side note, the intersections of capsules are not in general capsules. Calculating this volume is going to be slow; is there a good way to avoid doing this as much as possible?

It's only used as a heuristic to decide which envelopes should be split or merged. It doesn't need to be accurate. If two objects do not intersect, the method should return 0.

For distance_2 Is this always supposed to be the distance from the point to the closest point enclosed by the envelope? This seems to be what the AABB code is effectively doing, but I just want to be sure.

Yes, I believe your understanding is correct. It can also be the squared distance, though.

Can you explain min_max_dist_2 a bit more? I'm still not getting it.

Yep, min_max_dist_2 is complicated. I think you can return f64::max_value() if you don't want to implement this. This disallows some pruning during nearest neighbor search, but it shouldn't be too impactful. The original paper gives a good introduction about the idea behind "MINMAXDIST".

What is margin_value? What is the margin? If I have to round a value, do I round up or down?

margin_value seems to be a mistranslation. It should rather be called circumference_value perimeter_value. Example: A rectangle of length 2 and width 1 has the circumference perimeter of 6, circumference_value perimeter_value must be proportional to that. I'll rename that

Which point should I use to sort the envelopes by in sort_envelopes? How does it apply to envelopes that are object oriented rather than axis-oriented? I'm thinking about two capsules whose centers coincide and are the same shape, but one is rotated 180 degrees relative to the other. Physically they are the same, but since their endpoints are reversed, this could have an effect.

What precisely is partition_envelopes trying to accomplish??? I really can't tell.

I'll try to answer these questions simultaneously as they belong together. Sometimes, the r-tree algorithm needs to split an envelope into several, smaller envelopes. To do so, it will arrange all contained objects in a "logical" order and then choose a split index that tells where to split the arranged objects into two encompassing envelopes. Since arranging objects is only sensible in one dimension, the axis parameter specifies which dimension to look at for sorting. Example: A list of AABBs is sorted by their lower field. Other "sensible" arrangements would be using the center or the upper field for sorting.

It sounds like sorting by capsule center should work well for you.

partition_envelopes is a weaker version of select_envelopes and only used for bulk loading. Instead of sorting the whole collection, it only requires to [select the smallest selection_size] values. You can simply ignore the selection_size parameter and do whatever sort_envelopes does for a correct implementation. To speed up bulk selection significantly, I'd strongly suggest to use a proper selection sort algorithm though. Have a look at the AABB implementation in this case.

[ckaran]

Note: Your "capsules" link above links to the Envelope documentation, is this on purpose?

Nope, definitely a mistake :sweat: Should have linked to https://en.wikipedia.org/wiki/Capsule_(geometry)

margin_value seems to be a mistranslation. It should rather be called circumference_value perimeter_value. Example: A rectangle of length 2 and width 1 has the circumference perimeter of 6, circumference_value perimeter_value must be proportional to that. I'll rename that

Sounds good, but that brings up another question; what happens in higher dimensions? Is it actually the surface area of the envelope? Maybe hypersurface_area or hyperperimeter_area would be more accurate even if it is a mouthful and still needs to be explained in the docs...

As for my other questions, I think they're all answered! Thank you! I'm under some tight deadlines right now, but my current plan (assuming you don't beat me to it!) is to capture everything you've said in doc comments for Envelope, and then send you a pull request for it. I'll wait until you have 0.6.0 pushed out though, as well as the changes you have above applied, I don't want to introduce too many merge conflicts.

My future plan is to implement Envelope on a hypersphere type; that should be relatively easy to implement, and will give us a chance to test out how the code behaves when there is more than one Envelope type in a given tree.

[Stoeoef]

Sounds good, but that brings up another question; what happens in higher dimensions? Is it actually the surface area of the envelope? Maybe hypersurface_area or hyperperimeter_area would be more accurate even if it is a mouthful and still needs to be explained in the docs...

Yep, that's correct. I guess this (and a similar adaption for area, which can totally be a volume) should be mentioned in the doc comments. I would prefer to keep their names simple, though. Thus, "volume" and "surface_area" seem to be a good fit, the rest can be explained in the docs.

I'll wait until you have 0.6.0 pushed out though, as well as the changes you have above applied, I don't want to introduce too many merge conflicts.

That's done already! 0.6.0 has been published.

[Stoeoef]

My future plan is to implement Envelope on a hypersphere type; that should be relatively easy to implement, and will give us a chance to test out how the code behaves when there is more than one Envelope type in a given tree.

That sounds great!

Note that "more than one Envelope type (at the same time)" is not an intended use case, just for clarification. Also, now that I know what a capsule is, I do believe that using them as an envelope type should work just fine. For calculating intersection_area and area, approximating the capsule with a box of the same dimensions might work decently.

Looking at the usage of the other functions in the Envelope trait I do believe that only a few of them are really required for r-trees with r* insertion strategy: Required: new_empty, contains_envelope, area, merge, merged, intersection_area, min_max_dist_2 Probably not required for insertion: contains_point, intersects Required for nearest neighbor lookup: distance_2

It would be a good idea to move the non-strictly required methods out of Envelope into their new, own traits.

[ckaran]

Note that "more than one Envelope type (at the same time)" is not an intended use case, just for clarification.

Ah, glad to know that. I was assuming that you could mix & match to your heart's content.

Also, now that I know what a capsule is, I do believe that using them as an envelope type should work just fine. For calculating intersection_area and area, approximating the capsule with a box of the same dimensions might work decently.

Good to know.

But now that you know what a capsule is, you can see how it can have an orientation that isn't (necessarily) axis-oriented. My plan is just to use the centers of the two hemispheres as the endpoints in a vector, which fairly naturally handles orientation, but I'm not sure if that will cause any hiccups for the r tree. That is, if I have one capsule oriented 'up', and another oriented to the 'right', will that cause any issues for the r tree? What happens if one of the capsules is oriented at a 45 degree angle (or some other arbitrary angle?).

Come to think of it, partitioning a given capsule is going to lead to some headaches as well; the resultant pair of capsules may not be oriented the same as each other, or even as the original. Moreover, if all elements of the original capsule are required to be fully enclosed within the set of partitions, then there will be cases where the partitions overlap to some extent. I know that the r* tree was designed to handle this eventuality, but it is something to consider.

[IcanDivideBy0]

Hello, Since I'm interested in developing some enveloppe types, I'm jumping in! I have 2 different use cases, both are related to 3D graphics, so I'm gonna assume :

• first I'd like to develop a frustrum enveloppe, which could be useful for... frustrum culling. I think I can get this one done pretty easily, but, the tree is composed of "meshes" (AABB enveloppe) and frustrum would be a different type of enveloppe, so a way to make two enveloppes interact (with the same point type) can be interesting for this use case.
• secondly, I'd like to add ray casting inside the tree: currently I have to test against all nodes to get a ray intersection, which defeats the purpose of using a tree at all... This one seems a bit more difficult, I don't see a way to wrap a ray into an enveloppe :/

Do you think this is some use cases RStar should support? or should I give up on this and maybe try my chance with bvh?

One thing I can think of right now which might worth adding to RTree: adding the ability to traverse tree with custom user code (closure). Such a closure may return an enum like Inside, Outside, Intersect for the current enveloppe, and be called while descending the hierarchy accordingly to its result.

[IcanDivideBy0]

oops! nevermind I totally missed the locate_with_selection_function method! Cheers

[Stoeoef]

Hi there!

Do you think this is some use cases RStar should support? or should I give up on this and maybe try my chance with bvh?

Usually, other spatial indexes like BVHs or octtrees are better if you only need to load the contained objects once and then leave the hierarchy unchanged. At least that's what I've read and what sounds like a realistic trade-off. If you do need to insert and remove objects dynamically, r-trees should be a viable choice.

first I'd like to develop a frustrum enveloppe, which could be useful for... frustrum culling.

TBH, other envelope types do not exists at the moment, I'm not sure myself how well suited the current Envelope trait is for the types of extensions that I wanted to support. The use cases I were thinking about when designing the Envelope trait were envelopes on a torus and envelopes on a sphere.

Do you intend to create some sort of frustum tree, where each parent frustum contains its child frustums? Or do you have something different in mind? Would approximating all frustums by their AABB be a feasible solution?

[IcanDivideBy0]

If you do need to insert and remove objects dynamically, r-trees should be a viable choice.

I'm currently using rstar for a game, so object are created, removed and their positions changes pretty often, I didn't tried to push the limits yet but rstar seem a pretty good fit for now :+1: .

Do you intend to create some sort of frustum tree, where each parent frustum contains its child frustums? Or do you have something different in mind? Would approximating all frustums by their AABB be a feasible solution?

No no, I needed to select objects inside a frustrum (camera projection), SelectionFunction doing the job perfectly! here is what I ended with:

use rstar::{RTreeObject, SelectionFunction, AABB};
use std::convert::TryFrom;
use nalgebra_glm as glm;

struct SpacialObject {
    pub aabb: AABB<[f32; 3]>,
}

impl RTreeObject for SpacialObject {
    type Envelope = AABB<[f32; 3]>;

    fn envelope(&self) -> Self::Envelope {
        self.aabb
    }
}

struct FrustrumSelect {
    view_proj: glm::Mat4,
}

impl SelectionFunction<SpacialObject> for FrustrumSelect {
    fn should_unpack_parent(&self, envelope: &<SpacialObject as RTreeObject>::Envelope) -> bool {
        let a = envelope.lower();
        let b = envelope.upper();

        let verts = [
            glm::vec4(a[0], a[1], a[2], 1.0),
            glm::vec4(a[0], a[1], b[2], 1.0),
            glm::vec4(a[0], b[1], a[2], 1.0),
            glm::vec4(a[0], b[1], b[2], 1.0),
            glm::vec4(b[0], a[1], a[2], 1.0),
            glm::vec4(b[0], a[1], b[2], 1.0),
            glm::vec4(b[0], b[1], a[2], 1.0),
            glm::vec4(b[0], b[1], b[2], 1.0),
        ];

        verts.iter().any(|vert| {
            let clip = self.view_proj * vert;
            let ndc = glm::vec4_to_vec3(&clip) / clip.w;

            #[rustfmt::skip]
            let is_inside = {
                ndc.x >= -1.0 && ndc.x <= 1.0 &&
                ndc.y >= -1.0 && ndc.y <= 1.0 &&
                ndc.z >=  0.0 && ndc.z <= 1.0
            };

            is_inside
        })
    }

    fn should_unpack_leaf(&self, _leaf: &SpacialObject) -> bool {
        true
    }
}

[adamreichold]

Closing as this was more of discussion and there other Envelope implementations available to look at, e.g. those from the geo crate.