Welcome, Guest. Please login or register. Did you miss your activation email?

Author Topic: Bounding rectangle of transformed shapes  (Read 2904 times)

0 Members and 1 Guest are viewing this topic.

Nexus

  • SFML Team
  • Hero Member
  • *****
  • Posts: 6226
  • Thor Developer
    • View Profile
    • Bromeon
Bounding rectangle of transformed shapes
« on: May 02, 2015, 04:43:42 pm »
What does getGlobalBounds() return? As a user, I would clearly expect the minimal AABB that covers the area of the underlying geometry.

In order to obtain the global bounds, SFML transforms the local bounds, and then computes the bounding rect of those transformed local bounds. Now, for sf::Sprite which has a rectangular area, this works fine. For rotated sf::Shapes however, this yields rectangles which are considerably larger than necessary. The current behavior relies on a technical implementation detail and makes the shape's global bounds for all practical purposes (like simple collision detection, mouse clicking etc) useless.

I suggest adjusting sf::Shape::getGlobalBounds() in order to return the minimal bounding rectangle. I can create a pull request if you agree.
Zloxx II: action platformer
Thor Library: particle systems, animations, dot products, ...
SFML Game Development: first SFML book

Jesper Juhl

  • Hero Member
  • *****
  • Posts: 1405
    • View Profile
    • Email
Re: Bounding rectangle of transformed shapes
« Reply #1 on: May 02, 2015, 05:15:29 pm »
That sounds very reasonable to me.

Nexus

  • SFML Team
  • Hero Member
  • *****
  • Posts: 6226
  • Thor Developer
    • View Profile
    • Bromeon
Re: Bounding rectangle of transformed shapes
« Reply #2 on: May 02, 2015, 05:30:11 pm »
There's one drawback to keep in mind though.

Now, the local bounds are stored, as they don't change all the time. The global bounds are computed with a sf::Transform multiplication, so only 4 points need to be transformed.

After the change, every shape vertex would need to be transformed, before the bounding rect can be computed. Depending on the complexity of the shape, this may be a bit more effort. But I think that's acceptable, considering that sf::Shape isn't tailored for high-performance anyway (e.g. simple changes in the geometry lead to complete recomputation).
Zloxx II: action platformer
Thor Library: particle systems, animations, dot products, ...
SFML Game Development: first SFML book

Laurent

  • Administrator
  • Hero Member
  • *****
  • Posts: 32451
    • View Profile
    • SFML's website
    • Email
Re: Bounding rectangle of transformed shapes
« Reply #3 on: May 02, 2015, 06:02:11 pm »
I'm not sure this is acceptable. Since a sf::Shape has no way to know when its transform changes, you have to recompute the bounding rect completely, every time the function is called.

AABB are used for fast/approximate collision tests. So first, the current implementation is not useless, just more approximate than what it could be. And secondly, if we make it more precise but a lot more expensive, do we really gain anything, given that it is still not an exact test in the end? I can see two major use cases: people who use the global bounds to quickly check whether a more precise test is needed, and people who are ok with an approximate answer to the collision test. In both cases, improving the implementation will make things worse, and nothing better. So we should really think twice before "improving" this function.

By the way, if you change something, there's a typo in the function doc: a "sprite" that should be corrected to "shape" (line 236) ;D
Laurent Gomila - SFML developer

Nexus

  • SFML Team
  • Hero Member
  • *****
  • Posts: 6226
  • Thor Developer
    • View Profile
    • Bromeon
Re: Bounding rectangle of transformed shapes
« Reply #4 on: May 03, 2015, 11:31:28 am »
Since a sf::Shape has no way to know when its transform changes, you have to recompute the bounding rect completely, every time the function is called.
There would be a "partial" caching option that just stores the previous transform (or separate position/rotation/scale/origin) and compares them for equality, but that increases the object size and is not really cheap either. Especially not for shapes with only a handful of vertices.

AABB are used for fast/approximate collision tests. So first, the current implementation is not useless, just more approximate than what it could be. And secondly, if we make it more precise but a lot more expensive, do we really gain anything, given that it is still not an exact test in the end? I can see two major use cases: people who use the global bounds to quickly check whether a more precise test is needed, and people who are ok with an approximate answer to the collision test. In both cases, improving the implementation will make things worse, and nothing better. So we should really think twice before "improving" this function.
Good points.

My problem is mainly that the function name and even more the documentation are misleading. What's returned is not really the bounding rectangle, as people are used to this term -- it's rather a rectangle covering all the vertices, but not necessarily minimal or bounding. The very least we should do in my opinion is improve the documentation, and I'm sure you have nothing against that ;)

The other point is that while both functions (the minimal bounding rect, and the transformed local bounds) can be achieved using the public API, the former is considerably more complicated to implement. The latter is a trivial one-liner.
// Current implementation: transformed local rect
sf::FloatRect coveringRect(const sf::Shape& shape)
{
   return shape.getTransform().transformRect(shape.getLocalBounds());
}
vs.
// Alternate implementation: minimal bounding rect
sf::FloatRect boundingRect(const sf::Shape& shape)
{
        // Is this case handled or left as UB?
        if (shape.getPointCount() == 0)
                return sf::FloatRect();

        sf::Vector2f min = getTransform().transformPoint(shape.getPoint(0));
        sf::Vector2f max = min;

        for (std::size_t i = 1; i < shape.getPointCount(); ++i)
        {
                sf::Vector2f point = shape.getTransform().transformPoint(shape.getPoint(i));

                min.x = std::min(min.x, point.x);
                min.y = std::min(min.y, point.y);
                max.x = std::max(max.x, point.x);
                max.y = std::max(max.y, point.y);
        }

        // take into account outline
        min.x -= mOutlineThickness;
        min.y -= mOutlineThickness;
        max.x += mOutlineThickness;
        max.y += mOutlineThickness;

        return sf::FloatRect(min, max - min);
I just noticed the outline is a whole topic on its own. The above code doesn't work reliably since the outline may extrude further at sharp corners. So yes, it's probably going to be too complicated and people may want to handle it differently...

By the way, if you change something, there's a typo in the function doc: a "sprite" that should be corrected to "shape" (line 236) ;D
I can do that :)
Zloxx II: action platformer
Thor Library: particle systems, animations, dot products, ...
SFML Game Development: first SFML book

Laurent

  • Administrator
  • Hero Member
  • *****
  • Posts: 32451
    • View Profile
    • SFML's website
    • Email
Re: Bounding rectangle of transformed shapes
« Reply #5 on: May 03, 2015, 02:24:04 pm »
Indeed, the doc should be improved. I thought it was already mentioned somewhere, but it's not.
Laurent Gomila - SFML developer

Nexus

  • SFML Team
  • Hero Member
  • *****
  • Posts: 6226
  • Thor Developer
    • View Profile
    • Bromeon
Zloxx II: action platformer
Thor Library: particle systems, animations, dot products, ...
SFML Game Development: first SFML book

 

anything