Eliminate axis-aligned bounding box (AABB) variables

Question

I have an axis-aligned bounding box (AABB) that I've coded, but at the moment it is very redundant. I feel like there are variables that I can get rid of. I need the AABB to be very fast, and I'd like it to be more lightweight than it is.

#pragma once

#include "Engine.h"
// Collision
#include "Vec2D.h"
// End Collision

#include "Renderer.h"

struct ENGINE_API AABB {
private:
    Vec2D min;
    Vec2D max;

    double x;
    double y;
    double width;
    double height;
    double xwidth; // x + width
    double yheight; // y + height

    double vertMid; // vertical mid, cached for quadtree
    double horzMid; // horizontal mid, cached for quadtree

    // Normalize
    void calcMid() {
        vertMid = x + (width / 2);
        horzMid = y + (height / 2);
        xwidth = x + width;
        yheight = y + height;
    }

    void init(Vec2D, Vec2D);
    // End Normalize
public:
    // Constructor
    AABB(Vec2D min, Vec2D max) {
        init(min, max);
    }

    AABB(double x, double y, double width, double height){
        init(Vec2D(x, y), Vec2D(x + width, y + height));
    }
    // End Constructor

    // Getters
    double getX()const {
        return x;
    }

    double getY()const {
        return y;
    }

    double getWidth()const {
        return width;
    }

    double getHeight()const {
        return height;
    }

    double getHorzMid()const {
        return horzMid;
    }

    double getVertMid()const {
        return vertMid;
    }

    double getXWidth()const {
        return xwidth;
    }

    double getYHeight()const {
        return yheight;
    }
    // End Getters

    // Base
    bool collides(AABB other) {
        if (xwidth < other.x || x > other.xwidth) { return false; }
        if (yheight < other.y || y > other.yheight) { return false; }

        return true;
    }

    bool contains(Vec2D point) {
        if (x > point.getX() || xwidth < point.getX()) { return false; }
        if (y > point.getY() || yheight < point.getY()) { return false; }

        return true;
    }

    void move(double x, double y) {
        this->x = x;
        this->y = y;
        calcMid();
    }
    // End Base
    // Testing
    void render(Renderer& renderer) {
        sf::RectangleShape shape;
        shape.setPosition(x, y);
        shape.setOutlineColor(sf::Color::Red);
        shape.setOutlineThickness(3);
        shape.setSize(sf::Vector2f(width, height));
        renderer.render(shape);
    }
    // End Testing
};

And the messy part:

void AABB::init(Vec2D one, Vec2D two) {
    double x1 = one.getX();
    double y1 = one.getY();
    double xx = two.getX();
    double yy = two.getY();

    if (x1 > xx) {
        if (y1 > yy) {
            min = Vec2D(xx, yy);
            max = Vec2D(x1, y1);
        }
        else {
            min = Vec2D(xx, y1);
            max = Vec2D(x1, yy);
        }
    }
    else {
        if (y1 > yy) {
            min = Vec2D(x1, yy);
            max = Vec2D(xx, y1);
        }
        else {
            min = Vec2D(x1, y1);
            max = Vec2D(xx, yy);
        }
    }

    x = min.getX();
    y = min.getY();
    width = max.getX() - x;
    height = max.getY() - y;

    calcMid();
}

Answer 1

In a comment in your other question you claimed,

Thank you, Caching vertMid and horzMid really helped.

Whether caching is helpful depends on:

• How often you used the cached data
• How tight your performance requirements are
• Whether your cache implementation is reliable

One of your comments says,

// vertical mid, cached for quadtree

Only your testing can show whether that optimization is helpful.

From a performance point of view, in general:

• If it's not used it's harmful to cache
• If it's used once then it's harmless/useless to cache
• If it's used several times then it's useful to cache

However making something bigger (by caching extra values) can also have some negative effect on performance, e.g. because you can't fit so many objects in the CPU cache (which is faster than memory): which is why you should profile/test to see whether caching makes it faster in practice as well as in theory.

---

If you want to eliminate duplicate variables, you only need 4 doubles:

• min and max
• or, x and either width or xwidth, and y and either height and yheight

---

I found your xwidth and yheight names confusing to read; I would have preferred 'right' and 'bottom'.

---

If you have large structs, you may improve performance by curing your habit of passing objects by value instead of by reference. For example, this ...

bool collides(AABB other)

... should be ...

bool collides(const AABB& other) const

---

You can also use different classes for different purposes. For example, the AABB bounds member of your Quadtree class needs getHorzMid() and getVertMid() members, but those methods aren't needed/used by the AABB which you return using Locatable::getAABB(). So you could use two classes, e.g. AABB (without getHorzMid and getVertMid members), and a SplittableAABB class (used as a member of Quadtree) which adds those members.

---

I don't much like AABB as a class name: partly because all-upper-case looks like a macro to me: consider Bounds or Rect or Rectangle instead.

---

Your current code creates but doesn't read the initialize the min and max data members.

Your move method doesn't update the data in these members (rendering that data untrue).

Maybe Vec2D min and Vec2D max should be (temporary) local variables of your init function, not (permanent) member data of the class.

The parameters passed to the AABB(Vec2D min, Vec2D max) constructor should probably be named one and two not min and max (and should possibly be passed by reference not by value).

Answer 2

adding and halving is cheap, don't bother optimizing it out unless it is a problem

all you need is min and max and derive the rest from that:

double getMinX()const {
    return min.getX();
}


double getWidth()const {
    return max.getX()-min.getX();
}


double getXMid()const {
    return (max.getX()+min.getX())/2;
}


double getMaxX()const {
    return max.getX();
}

bool contains(Vec2D point) {
    if (min.getX() > point.getX() || max.getX() < point.getX()) { return false; }
    if (min.getY() > point.getY() || max.getY() < point.getY()) { return false; }

    return true;
}

and so on

however given that this is just a POD you can make the fields public and not bother with the accessor methods

Answer 3

Synopsis

I see there's already an accepted answer for this question and that the question is a few years old. I'd like to add my review and feedback anyway since I believe it would add over what's already been said.

I've written code for an AABB structure before so I've had opportunity to think of this problem in the past. That said, I agree that there are variables that you can get rid of and having taken a look at your code, I'd prefer the AABB to be lighter weight as well — though what's "lighter weight" is more subjective of course than a count of variables.

Review

I'm just reciting here points from the C++ Core Guidelines that come first to mind for me on looking at your code:

1. "Prefer initialization to assignment in constructors" (C.49).
2. "Make a function a member only if it needs direct access to the representation of a class" (C.4).
3. "Use class if the class has an invariant; use struct if the data members can vary independently" (C.2).
4. I'd rather the AABB class itself didn't cache data. Or: "use compact data structures" (Per.16), "space is time" (Per.18), but also "don't make claims about performance without measurements" (Per.6).
5. Your AABB code doesn't seem to have a default constructor: "Ensure that a value type class has a default constructor" (C.43).

Alternative Approach

An approach that I liked taking when I had worked on an AABB before was to step back and think in terms of invariants: i.e. recognize what properties really have to be maintained for the end result to reliably represent an axis aligned bounding box. From that perspective, there's really only the min and max values on each axis.

For two dimensional space as it seems you're using, would you believe that the AABB only needs two variables then? And moreover that these two variables are completely independent of each other such that the AABB can be a class that simply publicly exposes the two variables? I was happily surprised and pleased when I realized that indeed this was the case.

For the moment, let's call the type of each of this AABB class I and see this AABB:

struct aabb {
    // The following could instead be a 2-element array of I.
    // That'd be preferable IMO but not for here/now.
    I x; // data relates to the x-axis
    I y; // data relates to the y-axis
};

As is, this AABB class needs only non-friend non-member functions to manipulate its instances. I prefer these and put forward that:

1. we should prefer non-friend non-member functions, and
2. we should avoid writing functions as methods unless the function needs unfettered access to non-public data.

At least that is, if we want to improve encapsulation.

Okay so now back to I... What is this class I perhaps you ask?? It's a class that represents an interval defined by a minimum value and a maximum value. That's really the only invariant needed to be maintained in an AABB. Here's a skeleton of class for this (written herein by hand and which could itself be improved more I'd bet but hopefully serves for illustration):

class interval {
    using value_type = double; // or float, or templated type, etc. 

    // Use infinity if has_infinity() true, else max() & lowest()...
    // Where min & max are initialized crossed-over.
    value_type min_ = +std::numeric_limits<value_type>::infinity();
    value_type max_ = -std::numeric_limits<value_type>::infinity();

    using pair_type = std::pair<value_type, value_type>;

    interval(pair_type pair):
        min_{pair.first}, max_{pair.second} {}

public:
    interval() = default;

    interval(const value_type& a, const value_type& b):
        interval{std::minmax(a, b)} {}

    // add copy constructor, copy assignment, etc.

    value_type get_min() const { return min_; }
    value_type get_max() const { return max_; }

    // some non-const methods needed if the interval needs to be modifiable

    // say we need to be able shift the interval...
    interval& shift(const value_type& arg) {
        min_ += arg;
        max_ += arg;
    }

    // or to include a new point (possibly expanding interval)
    interval& include(const value_type& arg) {
        min_ = std::min(arg, min_);
        max_ = std::max(arg, max_);
    }
};

// Now just using interval::get_min() and interval::get_max()
// the following can be written as a "free function".
bool is_overlapping(const interval& a, const interval& b);

Here the interval class is certainly more involved than the AABB class. Through the composition however, I think we can agree that the AABB class itself has at least been simplified.

For instance, the collides functionality for the AABB can this way be implemented something like the following (also as a "free function"):

bool is_overlapping(const aabb& arg1, const aabb& arg2)
{
    return is_overlapping(arg1.x, arg2.x) && is_overlapping(arg1.y, arg2.y);
}

Or, say for example to include a Vec2D into an aabb:

aabb& include(aabb& var, const Vec2D& val) {
    var.x.include(val.getX());
    var.y.include(val.getY());
}

Is the composition using the interval class simpler overall??

Recall that in your code, you have all this code combined into the methods of the AABB class. It's basically got twice the code for maintaining the invariant of the interval compared to having two instances of an interval class. That duplication is unnecessary of course if the same result can be had without the duplication, to wit is the interval class.

I'm not a fan of the dogma I see us wielding (us coders that is), but the "single responsibility principle" (in "SOLID") comes to mind here and is probably worthwhile bringing up nevertheless. If you're not familiar with it already, take a gander at the link I've provided for it (to Wikipedia).

For complete and working examples of interval and AABB classes (though by no means meant to be perfect examples; only complete & working ones), you can take a look at Interval and AABB.