Implementing Intersections data structure that is able to hold a container of multiple types that maintains order in C++

Question

I am trying to implement a way to store intersections of rays with arbitrary objects. So far I thought I could make the object derived from an interface and put that as the type in the Intersection alongside the time t the ray intersects the object. Then I need another data structure to hold all the intersections while maintaing order where the closes intersections are earlier. This is my current implementation but it feels quite convoluted and might be too slow later on. I am looking for ideas to improve it or resources that I can learn from to develop a better way.

enum class VObjectType {
    SPHERE,
    CUBE

};


class GeometricObject {
    public:
    virtual ~GeometricObject() = default;
    virtual Tuple<float> origin() const = 0;
    virtual int id() const = 0;
    virtual VObjectType type() const = 0;
    virtual void printType() const = 0;
};
template<typename prec>
class VSphere: public GeometricObject {
    public:
    Tuple<float> m_origin; 
    static int idCounter;
    int m_id;
    VSphere() : m_id{++idCounter}, m_origin{Tuple<prec>::point(0,0,0)} {};
    VSphere(Tuple<float> o) : m_id{++idCounter}, m_origin{o} {};

    Tuple<float> origin() const override {
        return m_origin;
    }
    int id() const override {
        return m_id;
    }
    VObjectType type() const override {
        return VObjectType::SPHERE;
    }
    void printType() const override {
        std::cout << "Sphere" << std::endl;
    }

};
template<typename prec>
class VCube: public GeometricObject {
    public:
    Tuple<float> m_origin;
    static int idCounter;
    int m_id;
    VCube() : m_id{++idCounter}, m_origin{Tuple<float>::point(0,0,0)} {};
    VCube(Tuple<float> o) : m_id{++idCounter}, m_origin{o} {};

    Tuple<float> origin() const override {
        return m_origin;
    }
    int id() const override {
        return m_id;
    }
    VObjectType type() const override {
        return VObjectType::CUBE;
    }
    void printType() const override {
        std::cout << "Cube" << std::endl;
    }
};

template<typename prec>
int VSphere<prec>::idCounter = 0;
template<typename prec>
int VCube<prec>::idCounter = 0;

template<typename prec>
struct VIntersection {
    prec t;
    std::shared_ptr<GeometricObject> object;

    template<typename T>
    VIntersection(prec t, T&& obj) 
    : t{t}, object{std::make_shared<std::decay_t<T>>(std::forward<T>(obj))} {};

    template<typename T>
    VIntersection(prec t, T* obj)
        : t{t}, object{std::shared_ptr<T>(obj)} {};

    template<typename T>
    VIntersection(prec t, std::shared_ptr<T> obj)
        : t{t}, object{std::move(obj)} {};

    bool operator==(const VIntersection& i) const {
        return (t == i.t && object->id() == i.object->id()) && 
        (object->origin() == i.object->origin()) && 
        (object->type() == i.object->type());
    }
};
template<typename prec>
struct VIntersections {
    std::vector<VIntersection<prec>> intersections;
    std::vector<VIntersection<prec>> negIntersections;

    VIntersections() = default;

    void add(const VIntersection<prec>& i){
        if (i.t < 0) {
            auto it = std::lower_bound(negIntersections.begin(), negIntersections.end(), i, 
            [](const VIntersection<prec>& i1, const VIntersection<prec>& i2) {
                return i1.t > i2.t;
            });
            negIntersections.insert(it, i);
        } else {
        auto it = std::lower_bound(intersections.begin(), intersections.end(), i, 
        [](const VIntersection<prec>& i1, const VIntersection<prec>& i2) {
            return i1.t < i2.t;
        });
        intersections.insert(it, i);
        }
    }

    std::optional<VIntersection<prec>> hit() {
        if (intersections.empty()) {
            //return VIntersection<prec>(-10000000000000000, VSphere<prec>());
            return std::nullopt;
        }
        return intersections.front();
    }

    int count() const {
        return intersections.size() + negIntersections.size();
    }

    const VIntersection<prec>& operator[](size_t i) const {
        if (i < intersections.size()) {
            return intersections.at(i);
        } else {
            return negIntersections.at(i - intersections.size());
        }

    }

};



template<typename prec>
void vIntersects(const VSphere<prec>& s,
 const Ray<prec>& r, VIntersections<prec>& ts) {
    Tuple<prec> sphereToRay = r.origin - s.origin();
    prec a = dot<prec>(r.direction, r.direction);
    prec b = 2 * dot<prec>(r.direction, sphereToRay);
    prec c = dot<prec>(sphereToRay, sphereToRay) - 1;

    prec discriminant = b*b - 4 * a * c;
    if (discriminant < 0){
        return;
    }
    prec t1 = (-b - std::sqrt(discriminant)) / (2 * a);
    prec t2 = (-b + std::sqrt(discriminant)) / (2 * a);

    ts.add(VIntersection<prec>(t1, s));
    ts.add(VIntersection<prec>(t2, s));
}

template<typename prec>
void vIntersects(const VCube<prec>& c,
 const Ray<prec>& r, VIntersections<prec>& ts) {
    
    //get some random values for now
    prec t1 = 1;
    prec t2 = 2;

    ts.add(VIntersection<prec>(t1, c));
    ts.add(VIntersection<prec>(t2, c));
}

Answer 1

Inconsistent use of precision

Some of your classes are templated on the type of coordinates, however in other places you hardcode float. Make sure you are consistent.

Identifiers are not unique

Each geometric object type has its own counter for generating identifiers. However, consider a caller that doesn't know about the derived types, and just calls id() on the base class. It could get the same number back from different objects. This is probably not a good idea. I recommend using a global counter so all identifiers are really unique.

Note that it's also not enough to use the combination of type() and id(), since you can have both VSphere<float> and VSphere<double>, and they currently each would have their own counter.

Also note that it's better to use std::size_t instead of int for unique identifies, for the same reason that you use the former for array indices.

Naming things

You have used some uncommon or confusing names for some of the types:

• VCube, VSphere, VIntersection: what's with the V? Does it mean anything? Is it necessary? And if everything has the same prefix, maybe it is better to create a namespace and put them in there.
• Tuple<>: this is very confusing as while a tuple holds multiple values, in computer science it generally is considered to be something like an anonymous struct, which can hold multiple different types (see std::tuple). Here you are just using it to hold 3-dimensional coordinates. vec3 or Vector3 would then be a more idiomatic name (see for example Eigen and GLM).
• prec: I get that it means precision, but it's actually the type used to hold values. value_type would be a more idiomatic name, some other common names would be scalar or real.

Data structures

Your data structures are indeed far from efficient. Why does a VIntersection store a geometric object in a std::shared_ptr? I don't see any sharing happening in all of your code. It's then better to use std::unique_ptr as that is much more efficient.

In VIntersections, you use two std::vectors to store intersections. The problem is that keeping std::vector sorted is expensive; each time you add an entry it will be an \$O(N)\$ operation, and since you will be adding multiple intersections, all the adds together cost \$O(N^2)\$. It would be better to use some data type that is better at sorting, like std::set, std::map or std::priority_queue. The drawback of those is that looking up elements by arbitrary index is no longer a cheap operation (but iterating from front to back still is cheap). So, do you really need operator[]?

Do you really need to store all intersections along a ray? Assuming you are trying to build a ray tracer, I can see how that might be important for transparent objects, but for opaque ones you only need the closest hit. And what about the "negative" intersections?

Consider using std::variant

Inheritance is one way to store polymorphic types of objects in a container, but as you have noticed, you can only store pointers to base classes. You then often end up having to allocate each object. While using a smart pointer was indeed a smart choice, as manual memory management should be avoided, it would be much nicer if there was no need for all this.

A very different approach to polymorphism is to use std::variant. It would look like this:

template<typename prec>
class VSphere {
    …
};

template<typename prec>
class VCube {
    …
};

…

template<typename prec>
using GeometricObject = std::variant<VSphere<prec>, VCube<prec>, …>;

template<typename prec>
struct VIntersection {
    prec t;
    GeometricObject<prec> object;
    …
};

Note how there is no more inheritance, and GeometricObjects can now be stored by value. The only drawback is that to operate on the actual object stored inside a GeometricObject, you need to use std::visit(), which might take some getting used to if you have never used it before.