High performance physics simulation - core class design

Question

Below is some stripped down code from a physics simulation. The classes Vector2, Line and Polygon are probably self explanatory.

I will focus here on the fact that Polygon stores its Vector2 vertices, as well as its Lines. The reason is that the calling code, here just operator<<, benefits from the convenience of simple ranged-for looping over Lines as well as Vec2 points. Also, the Lines pre-calculate and cache their lengths and normal vectors, which were found to be performance bottlenecks in the full application, which accesses these many times in the hot inner loop.

EDIT Just to clarify what the code calling the classes below does - not shown for simplicity. It mainly does collision detection of the Polygons with Particles. Essentially this amounts to:

for (auto&& p: polys) {
  for (auto&& l: p.lines) { 
    // access the pre-cached length and normal vector of `line` 
    l.len // some fast maths
    l.norm // more fast maths
  }
}

There are typically less than 10 Polygons and typically around 600 particles. The simulation runs at 20,000 frames per seconds, which means the above nested loop is called ~12'000'000 per second. This is why caching the std::hypot calls in Vector2::mag() inside Line::len is really worthwhile.

END OF EDIT

It was tempting to make Line::start and Line::end references to elements in the Polygon::points vector, to ensure consistency, reduce the size of Line slightly, allow future modification of points etc. The code below has these references.

However, the references cause somewhat subtle dangling problems as explored here. TLDR, in the original code, when polys in main() reallocates for growth, it does so by copying (!) the Polygon elements. This happens because the 3rd party type sf::ConvexShape is not movable. This makes the Line::start/end reference dangle, after a deep copy of Polygon::points.

The code below addresses this problem in 3 ways:

1. It makes the Polygon::shape a std::unique_ptr which makes Polygon a movable type again. This means, that when polys in main() reallocates it will do so using move-construction and that is guaranteed to keep the references in Polygon::Line in tact, because the Polygon::points (the heap memory part) won't move.
2. For safety we delete the Polygon copy constructor and copy assignment operator
3. For protection against future code refactoring we static_assert that Polygon must be nothrow move constructible, which is the condition std::vector cares about.

So here is the design query:

This all seems very awkward and brittle for a simple set of classes. Can we do better, more simply?

The obvious answer seems to be: Don't use references. Make copies of the points and store them inside Line. C++ is good at "value-types". This works and actually that's how the code was originally.

Another possibility is to store indices (rather than references) to the points vector inside lines, but then each Line is useless without a reference to its parent class,Polygon.

A possible, but not very good IMO, solution is to use a std::deque or std::list in main(), so that adding to it, does not copy/move things around in the first place. I think this is a bad solution, because the calling code must concern itself with the internals of Polygon.

The other question is: Should sf::ConvexShape be a member of Polygon, after all, it is this external coupling that, arguably, causes all the problems - because it is not a movable type.

Are there other alternatives? Discuss?

#include <SFML/Graphics.hpp>
#include <cmath>
#include <iostream>
#include <memory>
#include <ostream>
#include <type_traits>

template <typename T>
class Vector2 {
  public:
    T x{};
    T y{};

    constexpr Vector2(T x_, T y_) : x(x_), y(y_) {}

    constexpr Vector2() = default;

    [[nodiscard]] T       mag() const { return std::hypot(x, y); }
    [[nodiscard]] Vector2 norm() const { return *this / this->mag(); }
    [[nodiscard]] constexpr double  dot(const Vector2& rhs) const { return x * rhs.x + y * rhs.y; }

    // clang-format off
    constexpr Vector2& operator+=(const Vector2& obj) { x += obj.x; y += obj.y; return *this; }
    constexpr Vector2& operator-=(const Vector2& obj) { x -= obj.x; y -= obj.y; return *this; }
    constexpr Vector2& operator*=(double scale) { x *= scale; y *= scale; return *this; }
    constexpr Vector2& operator/=(double scale) { x /= scale; y /= scale; return *this; }
    // clang-format on

    constexpr bool operator==(const Vector2& rhs) const = default;

    constexpr friend Vector2 operator+(Vector2 lhs, const Vector2& rhs) { return lhs += rhs; }
    constexpr friend Vector2 operator-(Vector2 lhs, const Vector2& rhs) { return lhs -= rhs; }
    constexpr friend Vector2 operator*(Vector2 lhs, double scale) { return lhs *= scale; }
    constexpr friend Vector2 operator*(double scale, Vector2 rhs) { return rhs *= scale; }
    constexpr friend Vector2 operator/(Vector2 lhs, double scale) { return lhs /= scale; }

    friend std::ostream& operator<<(std::ostream& os, const Vector2& v) {
        return os << '[' << v.x << ", " << v.y << ']';
    }
};

using Vec2  = Vector2<double>;

template <typename Number>
struct Line {
    // references on start and end can dangle if the std::vector<Vec2> points in Polygon is copied
    const Vector2<Number>& start;
    const Vector2<Number>& end;   // and Polygon::shape is not a unique_ptr
    const double           len;   // used for performance caching (sqrt is expensive)
    const Vector2<Number>  norm;  // more performance caching

    Line(const Vector2<Number>& start_, const Vector2<Number>& end_) // NOLINT similar params
        : start(start_), end(end_), len((end - start).mag()), norm((end - start) / len) {}

    friend std::ostream& operator<<(std::ostream& os, const Line& l) {
        return os << l.start << "=>" << l.end << "(" << l.len << ")";
    }
};

static constexpr float vsScale = 125.0F;

sf::Vector2f visualize(const Vec2& v) {
    return sf::Vector2f(static_cast<float>(v.x), static_cast<float>(v.y)) * vsScale;
}

class Polygon {
  public:
    std::unique_ptr<sf::ConvexShape> shape; // has to be a uniq_ptr to make Polygon movable
    std::vector<Vec2>                points;
    std::vector<Line<double>>        lines;

    explicit Polygon(std::vector<Vec2> points_)
        : shape(new sf::ConvexShape), points(std::move(points_)) {
        shape->setPointCount(points.size());
        lines.reserve(points.size());
        for (std::size_t x = 0; x != points.size(); x++) {
            shape->setPoint(x, visualize(points[x]));
            // modulo wraps end around to start
            lines.emplace_back(points[x], points[(x + 1) % points.size()]);
        }
    }

    Polygon(const Polygon&) = delete;            // copying would invalidate references in Lines
    Polygon& operator=(const Polygon&) = delete; // no copying

    // reinstate the default move constructor, move assignment operator and destructor
    Polygon(Polygon&&) = default;            // move only type to protect references
    Polygon& operator=(Polygon&&) = default; // move only
    ~Polygon() = default;
    
    void draw(sf::RenderWindow& window) {
        for (std::size_t x = 0; x < points.size(); x++) shape->setPoint(x, visualize(points[x]));
        window.draw(*shape);
    }

    // helpers
    static Polygon Square(Vec2 pos, double tilt) {
        return Polygon({Vec2(4, 0.5) + pos, Vec2(-4, 0.5) + pos, Vec2(-4, -0.5 + tilt) + pos,
                        Vec2(4, -0.5 - tilt) + pos});
    }

    static Polygon Triangle(Vec2 pos) {
        return Polygon({Vec2(1, 1) + pos, Vec2(-1, 1) + pos, Vec2(0, -1) + pos});
    }

    friend std::ostream& operator<<(std::ostream& os, const Polygon& p) {
        for (auto&& v: p.points) os << v;
        os << "  :  ";
        for (auto&& l: p.lines) os << l;
        return os;
    }
};

static_assert(std::is_nothrow_move_constructible_v<Polygon>, "Polygon must be nothrow move constructible");

int main() {
    std::vector<Polygon> polys;
    polys.push_back(Polygon::Square(Vec2(6.01, 10), -0.75));
    polys.push_back(Polygon::Square(Vec2(14, 10), 0.75)); // reallocates, but safely
    polys.push_back(Polygon::Triangle(Vec2(100, 100)));

    for (auto&& p: polys) std::cout << p << "\n";
}

Answer 1

Missing #includes

You are using std::vector, but did not #include <vector>. The code compiles, but that is because SFML happens to include these things for you. Do not rely on that though.

Polygon stores too much

Polygon has both a shape, points and lines. These three things all represent the same polygon. Redundant information not only costs more memory to store, but also adds the burden of keeping everything in sync. I suggest that you only store points. This also matches the input to the constructor.

Reduce the responsibilities of Polygon

Your Polygon does multiple things. Apart from storing the points that make up a polygon, it also stores sf::ConvexShape, has a draw() function that will draw that shape, and has static convenience functions for creating squares and triangles. I would rather keep everything to the bare essentials for representing polygons, and move the drawing functions and convenience functions out of Polygon. Consider creating a free function to_shape() to convert a Polygon to a sf::ConvexShape:

sf::ConvexShape to_shape(const Polygon& polygon) {
    sf::ConvexShape shape;
    auto point_count = polygon.points.size();
    shape.setPointCount(point_count);
    for (std::size_t i = 0; i < point_count; ++i)
        shape.setPoint(i, visualize(polygon.points[i]));
    return shape;
}

And for example Triangle() can be trivially converted to a free function as well:

Polygon Triangle(Vec2 pos) {
    return {Vec2(1, 1) + pos, Vec2(-1, 1) + pos, Vec2(0, -1) + pos};
}

And then you can still write things like:

std::vector<Polygon> polys;
polys.push_back(Triangle({100, 100}));
...
for (const auto& poly: polys)
    window.draw(to_shape(poly));

Note how this completely avoids having to use std::unique_ptr to store sf::ConvexShapes. There is also no need to store lines, the only user of it is operator<<(), and it could simply create Lines on the fly if really desired.