# Day 31, Optimizing triangles

Triangle rendering was painfully slow, as mentioned yesterday. Putting a little reflective shine on the floor and walls of the room took rendering time past 90 minutes. After a bit of research i tried a binary bounding volume hierarchy, dividing the list of shapes into subtrees, split evenly on the largest axis of the bounding box, recursively. This way we get a spacially balanced binary tree with the actual shapes as leaves, and theoretically get \(O(log\ n)\) instead of \(O(n)\) search time per ray. Huge difference, especially with rays branching recursively for reflections and refractions. Down from 90 to 6 minutes for the same scene.

*Edit:* As a surprise bonus, the high polygon version only took 11 minutes.

This marks the end of Devember 2018, but there’s still some more work to do on the raytracer before I let it go. The flat shading of triangles needs some normal interpolation, and the primitive volumes needs some constructive solid geometry operations to really shine.

## Next related

### Tea, Cocktails, and a Happy New Year

## Previous related

### Day 30, Triangles and teapots

The last of the primitive shapes, the triangle. By them selves they’re pretty boring, but when you stick loads of them together they make pretty teapots. Very. Slowly. And quite chunky, because low-polygon model. It sums up to 240 triangles after dividing some larger polygons, and takes about 20–30 minutes to render at the whopping resulution of 320x256 and no reflections. I probably need to research some kind of bounding hierarchy algorithm to automagically subdivide large groups of objects.

### Day 29, Groups

Transforming each object in the scene in global world reference space quickly becomes tiresome, so let’s introduce a new group “shape”. A group takes any number of objects and provides a common reference space for its children via its own transform. A group also helps reduce the search space in large scenes, by aggregating the bounding boxes of its children into a bounding box for the entire group. That way ray intersection tests against the children of the group only needs to happen when the group bounding box is intersected. Neat.

### Day 28, Celebratory cocktails

The latest addition to the supported shapes is the cone, a deformed kind of cylinder, also optionally capped and restricted to an interval along its length. With all these things we can make a cocktail to celebrate. With all these transparent parts, it takes more than 8 minutes to render.