There are some things I don't like but I weren't able to solve them any nicer having to support C++98. Namely, the transformInternal helper functions.
Maybe I’ll add a few more tests for the 3D case.
Thank you for the initial patch. I’ve several comment though!
1 - API-wise, I'm concerned about the usage of operator* for this task. If we use it, then it should rather be: box = transform * box, and so box *= transform does not make sense. Maybe it would be safer and less ambiguous to avoid abusing operator * and use explicit functions, e.g.:
I agree, it should rather be transform * box and prohibiting integral types should either be done when instantiating Isometries, or rather not at all (for the pi/2-use case).
Also, I think there is no need to limit this to Isometries (I did not try it, but I think the formulas work for arbitrary affine transformations as well)
I’m not really sure how would the algorithms work with non-isometries. What about starting with isometries and once it works for them, we can put more effort in designing non-isometric test cases?
@Gael Guennebaud ad 1) Yeah, you’re right, I used the wrong op. I wanted to make it possible to do the transform in-place, where it makes sense only when using *=.
So should I completely abandon operators and create these transform methods? Or I can create the transform methods and then redirect operator(Transform, AlignedBox) to one of these methods.
ad 2) So is it really possible to create "integral rotations" in Eigen? What is the RotationBase subtype which implements this? Or is it just Matrix3i?
ad 6) Do we need to care for such identities? Isn’t it apparent that such expression is prone to round-off errors?
Ad 2: The point is that here is definitely not the right place to prohibit integral rotations (you are actually just ignoring the linear part, which is even more wrong). Transform is currently always stored as a matrix (the size depends on the template parameters).
You could make specializations for Translation for higher efficiency.
I did some changes in the direction you suggested. Please, have a look at it.
I tested the identity example and it really doesn't work due to rounding errors, but I think any sane user would expect these can come into play. Maybe if I implement scaling, we can add a method containsApprox() or something similar.
Regarding the (now outdated) comment about single-point bounding boxes: it's true that the transform always applies rotation about the local axis after translation is done, which results in no (visible) rotation for single-point boxes. But can't the other order of rotation/translation be represented again by another transform? Or should I reverse the order of transforms inside the new methods? Or an optional argument like translateFirst?
And I still don’t get how one could transform an integral box by pi/2. Even this doesn’t compile:
Of course, we can make a specialization with non-integral transforms for integral types with rounding if this is what you meant…
You can't combine vectors/matrices/quaternions with different scalars. You could generate an integer matrix which just contains a single ±1 per row/column (this covers all rotations and reflections by multiples of pi/2).
You should not make any special implementations for different scalar types.
Ok, I think the updated implementation supports this scenario.
I greatly simplified the code throwing away all the special cases and leaving in just the generic algorithm. The code now also allows for integral rotations, and even the rounding error test works! I think all the comments from the first review of @Gael Guennebaud are addressed now.
In addition to the inlined comments, there is still the issue that the linear part is applied relatively to the center of the box, which is confusing. For the default behavior I would expect:
I also have a concern about the unit tests which are not randomized. The unit tests should verify expected properties on random boxes and transformation similar to the above example.
If I understand your example correctly, then B2.min() will should be the same as A*B1.min()? But that’s incorrect in my point of view, as after applying rotation, another corner may become the minimal corner than the one that was minimal before! I’ve already seen (and fixed) bugs caused by this wrong type of assumption: https://github.com/ros-planning/moveit/pull/699 .
So what do you think should the AABB rotate about? The min corner? The max corner? Something else? To me, the center of the box seems like the only unique point which makes sense to be treated as the transform origin.
As for the randomized tests, I’m not a big fan of them, but I can add them. But I still think added a good set of standard and extreme positions will do a better job than a randomized test.
Nobody said that B2.min()==A*B1.min(), but B2 should be the smallest bounding box which includes A*p for all points p of B1. That means, if A is a pure rotation, it should rotate around the origin (not around the center of the box -- if that really is a common use case, we might consider adding an extra method for that with some obvious naming).
Regarding randomized unit-tests: Of course some border cases can/should be tested additionally to randomized tests, but just hard-coding a few "standard positions" is more likely to hide some non-obvious errors. And even border cases could be partially randomized (like a box with B.min()==B.max())
Good point. Yes for consistency we should just use transform.
I’ve done some changes requested in the inline comments, and renamed transformInPlace to transform.
One inline comment also suggested that v_delta shouldn’t be cast to NonInteger and then back to Scalar. I think not doing the casts is wrong in the integer case. Imagine a 2D box with min = (0, 0), max = (1, 1). v_delta in this case is (-0.5, 0.5). If it weren’t cast to NonInteger, it’d be (0, 0). But that’s only implementation problem - if I look at the function from the point of view of an “outside” user as a blackbox, I’d expect that a 90 deg rotation transform will just transform the box and not squeeze it to zero.
One alternative to casting to NonInteger would be to use the slower method - computing all 4 ( 8 ) transformed vertices and manually finding their cwise min and max. I’m not sure here how to follow. Maybe someone would like to use this method instead of the originally proposed one (e.g. to avoid some rounding errors as @Christoph Hertzberg pointed out). My idea is to add either a bool parameter allowNonIntegerComputations, or, more generally, a computeStrategy parameter. This would switch between these two implementations.
What do you think about it?
I’m still working on the transform method actually rotating around origin. I need to get the test cases right, then i’ll push these changes, too.
This should work for floating point or integer types (as long as it does not overflow):
One could add Scalar(2)*transform.translation() to rotated_center_2, instead of adding it to m_max and m_min (this could save a few ops).
All compilers should be smart enough to replace the division by 2 by either a shift or a multiplication with Scalar(0.5).
Awesome, this looks really clear! I was heading this direction in my thoughts, but didn’t finish it… I really like this solution.
In the latest commit, I put it in the code and fixed the tests accordingly. Next, I’ll play with affine transforms. I’d like to verify in tests that it actually also works for them. Scaling looks pretty straightforward and there isn’t much this implementation could do bad. Shearing also looks compatible, but let’s have a few tests for it. Or maybe I won’t create separate tests for reflection, scaling etc. and I’ll directly create a test with randomized (general) affine transforms.
I also added a few randomized tests to the current implementation as was requested.
And I'm still pretty sure this works for arbitrary Affine transformations (no need to limit this to Isometries).
I added randomized tests with both rotation and full affine transforms. I also changed the API to support Affine transforms.