Added AlignedBox::transformed(AffineTransform).

#650 Open

Bitbucket cannot automatically merge this request.

The commits that make up this pull request have been removed.

Bitbucket cannot automatically merge this request due to conflicts.

Review the conflicts on the Overview tab. You can then either decline the request or merge it manually on your local system using the following commands:

hg update 3.3
hg pull -r 3.3
hg merge 55d82f64a4c3
hg commit -m 'Merged in peci1/eigen/3.3 (pull request #650)'
  1. Martin Pecka

Resolves 1623.

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.

Comments (21)

  1. Gael Guennebaud

    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.:

    AlignedBox transformed(const IsometryTransform&) const;
    AlignedBox& transformInPlace(const IsometryTransform&);

    2 - I would not silently bypass the rotation part for integral types because rotations of pi/2 are perfectly fine.

    3 - In contrast, I would add a generic specialization of transform*(...) for translations.

    4 - I don’t think you need a different implementation for dynamic and static sizes, what would you implement differently?

    5 - To reduce temporaries, you could do something like:

    tmp = t.linear().cwiseAbs() * sizes();
    m_min = center()+t.translation();
    m_max = m_min + tmp;
    m_moin -= tmp;

    6 - How to deal with round-off errors? For instance, I’m pretty sure that the following would fail:

    AlignedBoxType B1 = ...;
    IsometryType A;
    AlignedBoxType B2;
    1. Christoph Hertzberg

      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)

      1. Martin Pecka author

        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?

  2. Martin Pecka author

    @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?

    1. Christoph Hertzberg

      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.

  3. Martin Pecka author

    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?

  4. Martin Pecka author

    And I still don’t get how one could transform an integral box by pi/2. Even this doesn’t compile:

    const Vector3i q = Quaternionf::UnitRandom() * Vector3i::Ones();

    So how would I put in a pi/2 rotation?

    Of course, we can make a specialization with non-integral transforms for integral types with rounding if this is what you meant…

    1. Christoph Hertzberg

      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.

  5. Martin Pecka author

    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.

  6. Gael Guennebaud

    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:

    AlignedBoxType B1 = ...;
    IsometryType A = ...;
    AlignedBoxType B2 = B1.transformed(A);
      assert( B2.contains(A*(B1.min()+B1.sizes().cwiseProduct(VectorType::Random().cwiseAbs()))) );

    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.

  7. Martin Pecka author

    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: .

    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.

    1. Christoph Hertzberg

      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())

  8. Martin Pecka author

    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.

    1. Christoph Hertzberg

      This should work for floating point or integer types (as long as it does not overflow):

      // two times rotated extend:
      VectorType rotated_extend_2 = (transform.linear().cwiseAbs() * sizes());
      // two times rotated center:
      VectorType rotated_center_2 = transform.linear() * (m_max + m_min);
      m_max = (rotated_center_2 + rotated_extend_2) / Scalar(2) + transform.translation();
      m_min = (rotated_center_2 - rotated_extend_2) / Scalar(2) + transform.translation();
      1. Christoph Hertzberg

        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).

        1. Martin Pecka author

          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.

      2. Christoph Hertzberg

        And I'm still pretty sure this works for arbitrary Affine transformations (no need to limit this to Isometries).

  9. Martin Pecka author

    I added randomized tests with both rotation and full affine transforms. I also changed the API to support Affine transforms.