Factorize a function where inheritance is unwanted

Question

I have this piece of code which I'd like to improve:

std::optional<IntersectionInfo> Scene::intersects(const Ray& ray) const
{
 float closest = std::numeric_limits<float>::max();
 int index = -1;
 int i = 0;
 for(auto& sphere : _spheres)
 {
 auto [b, d] = Intersections::intersects(ray, sphere._shape);
 if(b && d < closest)
 {
 closest = d;
 index = i;
 }
 i++;
 }
 i = 0;
 bool isPlane = false;
 for(auto& plane : _planes)
 {
 auto [b, d] = Intersections::intersects(ray, plane._shape);
 if(b && d < closest)
 {
 closest = d;
 index = i;
 isPlane = true;
 }
 i++;
 }
 i = 0;
 bool isBox = false;
 for(auto& box : _boxes)
 {
 auto [b, d] = Intersections::intersects(ray, box._shape);
 if(b && d < closest)
 {
 closest = d;
 index = i;
 isBox = true;
 }
 }
 i = 0;
 bool isTri = false;
 for(auto& tri : _triangles)
 {
 auto [b, d] = Intersections::intersects(ray, tri._shape);
 if(b && d < closest)
 {
 closest = d;
 index = i;
 isTri = true;
 }
 }
 if(index != -1)
 {
 IntersectionInfo info;
 info._intersection = ray._position + ray._direction * closest;
 if(isTri)
 {
 info._normal = Intersections::computeIntersectionNormal(ray, info._intersection, _triangles[index]._shape);
 info._material = *_triangles[index]._material;
 }
 else if(isBox)
 {
 info._normal = Intersections::computeIntersectionNormal(ray, info._intersection, _boxes[index]._shape);
 info._material = *_boxes[index]._material;
 }
 else if(isPlane)
 {
 info._normal = Intersections::computeIntersectionNormal(ray, info._intersection, _planes[index]._shape);
 info._material = *_planes[index]._material;
 }
 else
 {
 info._normal = Intersections::computeIntersectionNormal(ray, info._intersection, _spheres[index]._shape);
 info._material = *_spheres[index]._material;
 }
 info._intersection += info._normal * 0.001f;
 return info;
 }
 return {};
}

This function operates over several vectors (_spheres, _planes, _boxes and _triangles) which stores different types. Since the code is syntactically identical (but intersects and computeIntersectionNormal calls varies depending on the input type), I'd like to find a way to improve it.

An obvious solution would be to use inheritance and have a single vector storing a Shape, which would have virtual members for intersects and computeInteresctionNormal, however :

• I do not wish to change the existing type structures just for the sake of this function.
• This function is an hot loop of my program inheritance has shown a visible cost.

I'd also would like to avoid macros (unless they are really simple).

I came up with this :

enum class ShapeType
{
 None,
 Sphere,
 Plane,
 Box,
 Triangle
};
template<typename Shape>
std::function<IntersectionInfo()> intersectsWithShapes(const std::vector<MaterialShape<Shape>>& materialShapes, const Ray& ray, ShapeType currentType, float& closest, int& index, ShapeType& type)
{
 int i = 0;
 for(const auto& materialShape : materialShapes)
 {
 auto [b, d] = Intersections::intersects(ray, materialShape._shape);
 if(b && d < closest)
 {
 closest = d;
 index = i;
 type = currentType;
 }
 i++;
 }
 return [&]()
 {
 IntersectionInfo info;
 info._intersection = ray._position + ray._direction * closest;
 info._normal = Intersections::computeIntersectionNormal(ray, info._intersection, materialShapes[index]._shape);
 info._material = *materialShapes[index]._material;
 info._intersection += info._normal * 0.001f;
 return info;
 };
}
std::optional<IntersectionInfo> Scene::intersects(const Ray& ray) const
{
 float closest = std::numeric_limits<float>::max();
 int index = -1;
 auto type = ShapeType::None;
 auto F1 = intersectsWithShapes(_spheres, ray, ShapeType::Sphere, closest, index, type);
 auto F2 = intersectsWithShapes(_planes, ray, ShapeType::Plane, closest, index, type);
 auto F3 = intersectsWithShapes(_boxes, ray, ShapeType::Box, closest, index, type);
 auto F4 = intersectsWithShapes(_triangles, ray, ShapeType::Triangle, closest, index, type);
 decltype(F1) F;
 switch(type)
 {
 case ShapeType::None: return {};
 case ShapeType::Sphere: F = F1; break;
 case ShapeType::Plane: F = F2; break;
 case ShapeType::Box: F = F3; break;
 case ShapeType::Triangle: F = F4; break;
 }
 return F();
}

I prefer this over the above function because adding a shape is simpler and less prone to error, and the entire interesting code is located in a small function. But it's not ideal because now Scene::intersects() is entirely made of boilerplate code, it's not obvious to guess why intersectsWithShapes returns a lambda, and this introduces a visible cost (althrough this time, only in debug build).

• Toby Speight: The current question title, which states your concerns about the code, is too general to be useful here. Please edit to the site standard, which is for the title to simply state the task accomplished by the code. Please see How to get the best value out of Code Review: Asking Questions for guidance on writing good question titles.

Answer 1

Could we not use a second template function instead of the lambda? e.g.:

template<class Shape>
IntersectionInfo getIntersectionInfo(std::vector<MaterialShape<Shape>> const& materialShapes, Ray const& ray, float closest, std::size_t index)
{
 auto position = ray._position + ray._direction * closest;
 auto normal = Intersections::computeIntersectionNormal(ray, position, materialShapes[index]._shape);
 auto material = *materialShapes[index]._material;
 position += info._normal * 0.001f;
 return { position, normal, material };
};

Then we can call it directly from the switch statement:

std::optional<IntersectionInfo> Scene::intersects(const Ray& ray) const
{
 float closest = std::numeric_limits<float>::max();
 int index = -1;
 auto type = ShapeType::None;
 intersectsWithShapes(_spheres, ray, ShapeType::Sphere, closest, index, type);
 intersectsWithShapes(_planes, ray, ShapeType::Plane, closest, index, type);
 intersectsWithShapes(_boxes, ray, ShapeType::Box, closest, index, type);
 intersectsWithShapes(_triangles, ray, ShapeType::Triangle, closest, index, type);
 switch(type)
 {
 case ShapeType::None: return {};
 case ShapeType::Sphere: return getIntersectionInfo(_spheres, ray, closest, index);
 case ShapeType::Plane: return getIntersectionInfo(_planes, ray, closest, index);
 case ShapeType::Box: return getIntersectionInfo(_boxes, ray, closest, index);
 case ShapeType::Triangle: return getIntersectionInfo(_triangles, ray, closest, index);
 }
 return { };
}

---

Another possibility is to use a std::variant for the shape type. We can then store all the shapes in one container and use std::visit to dispatch to functions that need the specific types, something like:

using Shape = std::variant<Sphere, Plane, Box, Triangle>;
std::optional<IntersectionInfo> Scene::intersects(Ray const& ray) const
{
 auto hit = false;
 auto closestDistance = std::numeric_limits<float>::max();
 auto closestIndex = std::size_t(-1);
 auto const intersects = [&] (auto const& shape) { return Intersections::intersects(ray, shape) };
 for (auto i = std::size_t{ 0 }; i != _shapes.size(); ++i)
 {
 auto [b, d] = std::visit(intersects, _shapes[i]._shape); // _shape is now the "Shape" variant type
 if (!b) continue;
 if (d >= closest) continue;
 hit = true;
 closestDistance = d;
 closestIndex = i;
 }
 if (!hit) return { };
 auto const getInfo = [&] (auto const& shape)
 {
 auto position = ray._position + ray._direction * closestDistance;
 auto normal = Intersections::computeIntersectionNormal(ray, position, shape);
 auto material = *_shapes[closestIndex]._material;
 
 position += info._normal * 0.001f;
 
 return { position, normal, material };
 };
 return std::visit(getInfo, _shapes[closestIndex]._shape);
}

std::visit will cast the variant to the correct type, and pass it to the lambda.

The lambda takes an auto argument, which effectively means it has a templated call operator:

struct anonymous_lambda_type
{
 template<class ShapeT>
 auto operator()(ShapeT const& shape) { ... };
}

We could instead define our own functor using overloading if we needed to change the behavior based on the specific type (which we don't here):

struct ray_intersection
{
 std::tuple<bool, float> operator()(Sphere const& sphere) { ... }
 std::tuple<bool, float> operator()(Plane const& plane) { ... }
 ...
};

• JDługosz: The variant would dispatch to the shape with the same overhead as the virtual function. Making each shape in its own collection is faster, just just because it saves an indirection in the function call, but processes all the like things together so the code for one shape stays in the cache.
• user673679: I guess. I think we'd probably want to implement an acceleration structure (BVH, grid, etc.) before worrying about that though.
• JDługosz: Not using virtual functions was mentioned in the OP. Faking it with the same or higher overhead would be just as bad for the same reasons he mentioned.
• user673679: I'm not sure that's true. It's all run-time polymorphism, whether we use a "type" enum and a switch statement, a variant, or actual inheritance. The only way to know is to measure it and see. (And it seems that performance isn't actually such an issue, because we're not using any kind of acceleration structure.)
• JDługosz: Regardless, he says he doesn't want to use virtual functions because of whatever reasons; it doesn't make sense to suggest a more complex workaround that technically doesn't use virtual functions but actually has those same issues. The reply should be "go ahead, if you didn't measure it it's not the limiting factor anyway." not do something equivalent but more difficult.