search

dimforge / ncollide

2 and 3-dimensional collision detection library in Rust.
https://ncollide.org
Apache License 2.0
921 stars 105 forks source link

Provide bounding volume methods without an isometry parameter #283

Closed ghost closed 5 years ago

ghost commented 5 years ago

As discussed in #282. When doing AABB computations for triangles, passing in Isometry::identity() as the transform to the aabb method is expensive in the cases where we don't need to transform the shape. Therefore, we should provide a version of this method that doesn't take an isometry parameter.

sebcrozet commented 5 years ago

Thank you for opening this issue!

If think your suggestion was a good one: modify the HasBoundingVolume trait to add a method as follows: fn local_bounding_volume(&self) -> BV; that does not include the transform. This method won't make the type parameter N intervene, but don't think that will be an issue.

We could do something similar for other traits, like for example by adding a local_support_point to the SupportMap trait to avoid the transform. But that's out of the scope of this issue of course.

A long time ago, the HasBoundingVolume trait had an additional type parameter M (as shown is that old version of bounding_volume.rs) for the transform type. This allowed the transform to be set as Id which represents the identity transformations with all its methods set to no-ops. This allowed to avoid the cost of the transformation when the transform is known at compile-time to be the identity. This capability disappeared when most type parameters except the numeric type N were removed from ncollide to make the API simpler. I don't want to re-add this type parameter, so the new local_bounding_volume method seems like the best approach.

ghost commented 5 years ago

After I had finished typing that, I was looking at the types that actually implement HasBoundingVolume and it occurred to me that it is only ever implemented for AABB and BoundingSphere. For bounding spheres the rotation component of the transform will do nothing, so this made me think that the performance impact of the transform can be negligible for bounding spheres. This made me second guess my suggestion, but maybe it still is a good one.

A long time ago, the HasBoundingVolume trait had an additional type parameter M (as shown is that old version of bounding_volume.rs) for the transform type. This allowed the transform to be set as Id which represents the identity transformations with all its methods set to no-ops. This allowed to avoid the cost of the transformation when the transform is known at compile-time to be the identity. This capability disappeared when most type parameters except the numeric type N were removed from ncollide to make the API simpler. I don't want to re-add this type parameter, so the new local_bounding_volume method seems like the best approach.

Interesting! While looking into this I did briefly wonder if nalgebra had some sort of compile-time optimization for identity elements.

sebcrozet commented 5 years ago

For bounding spheres the rotation component of the transform will do nothing, so this made me think that the performance impact of the transform can be negligible for bounding spheres. This made me second guess my suggestion, but maybe it still is a good one.

I think your suggestion is still good because bounding spheres are a very special case. In the future we will have more bounding volume types (k-DOP, OBB, etc.) and most of them will be rotation-dependent.