In previous articles, the rendering code has only supported spheres. Sphere interesct is easy (I might discuss that in another article), and that is why I started with it. But if we want to build more complex scenes, we need to support triangles. Triangles can be used to build anything, even spheres.

For this to work we need to first decide how the triangles will be defined, and since I am making the decisisions, the triangles will be defined as this:

{
  pt0: [0,0,0],
  pt1: [0.5,1,0],
  pt2: [1,0,0],
  normal: [0, 0, -1], // This will be calculated
  color: [1, 0, 0],
  isTriangle: true,
}

In words, a triangle is just tree points in 3D space. How the points are ordered does matter, as it will determine the direction of the normal, when it is calculated using the cross product.

The other important structure needed is the Ray, previous entries have already defined it but will put it here for reference:

{
  origin: [0, 0, 0],
  direction: [0, 0, 1],
}

To make this intersection test happen, we will pretend the ray origin is at the (0,0,0) coordinate, and will translate the triangle points, substracting the ray origin from each of the triangle vertices.

After that, we need to permute the triangle direction dimensions, so the one with the biggest absolute value is moved to the z axis, the other two are assigned arbitrarily.

Next, we use the z axis to calculate some factors that will be used to apply a shear transformation to the triangle vertices. This makes it so the triangle is projected on the plane perpendicular to the z axis, making it easy to check if the ray hits inside it.

For this test, we calculate the edges of the transformed triangle and check if the point (0,0) is inside it. There are two inital tests that need to succed for this point to be found inside the triangle:

All the edges must have the same sign
The edges sum (determinant) should be different than zero

If those pass then it means the line defined by the ray direction passes through the triangle, but since the ray is not an infinite line and has a direction, we need to make sure tha the distance from the ray origin to the point inside the triangle is positive; if it is, then we have a valid hit.

The process is expressed in code as follows:

function createTriangleIntersectFunction(args) {
    const { vector } = args;
    const triangleIntersect = (ray, triangle) => {
        const { pt0, pt1, pt2, normal } = triangle;
        let pt0_t = vector(pt0).sub(ray.origin);
        let pt1_t = vector(pt1).sub(ray.origin);
        let pt2_t = vector(pt2).sub(ray.origin);
        const k = vector(ray.origin).abs().maxDimension();
        const i = (k + 1) % 3;
        const j = (i + 1) % 3;

        const [pdx, pdy, pdz] = vector(ray.direction).permute(i, j, k).value();
        const sz = 1.0 / pdz;
        const sx = -pdx * sz;
        const sy = -pdy * sz;

        pt0_t = pt0_t.permute(i, j, k).value();
        pt1_t = pt1_t.permute(i, j, k).value();
        pt2_t = pt2_t.permute(i, j, k).value();

        const pt0_t_0 = pt0_t[0] + sx * pt0_t[2];
        const pt0_t_1 = pt0_t[1] + sy * pt0_t[2];
        const pt0_t_2 = pt0_t[2] * sz;
        const pt1_t_0 = pt1_t[0] + sx * pt1_t[2];
        const pt1_t_1 = pt1_t[1] + sy * pt1_t[2];
        const pt1_t_2 = pt1_t[2] * sz;
        const pt2_t_0 = pt2_t[0] + sx * pt2_t[2];
        const pt2_t_1 = pt2_t[1] + sy * pt2_t[2];
        const pt2_t_2 = pt2_t[2] * sz;

        const e0 = pt1_t_0 * pt2_t_1 - pt1_t_1 * pt2_t_0;
        const e1 = pt2_t_0 * pt0_t_1 - pt2_t_1 * pt0_t_0;
        const e2 = pt0_t_0 * pt1_t_1 - pt0_t_1 * pt1_t_0;

        if ((e0 < 0.0 || e1 < 0.0 || e2 < 0.0) && (e0 > 0.0 || e1 > 0.0 || e2 > 0.0)) {
            return { hit: false };
        }

        const det = e0 + e1 + e2;
        if (det == 0.0) {
            return { hit: false };
        }

        const t_scaled = e0 * pt0_t_2 + e1 * pt1_t_2 + e2 * pt2_t_2;

        if (det < 0.0 && t_scaled >= 0.0) {
            return { hit: false };
        }

        if (det > 0.0 && t_scaled <= 0.0) {
            return { hit: false };
        }

        const t = t_scaled / det;

        if (t > 0.007) {
            const point = vector(ray.direction).scale(t).add(ray.origin).value();
            return {
                hit: true,
                distance: t,
                point,
                normal,
            };
        }

        return {
            hit: false,
        };
    };

    return {
        triangleIntersect,
    };
}

const canvas = document.getElementById("canvas-1");
const ctx = canvas.getContext("2d");
const width = canvas.width;
const height = canvas.height;

renderingPipeline({ width, height }).then((result) => {
    const { bitmap } = result;
    const finalBitmap = new Uint32Array(width * height);
    for(let i = 0 ; i < bitmap.length; i++) {
        const [r, g, b] = bitmap[i];
        finalBitmap[i] = (255 << 24) | (Math.floor(b * 255) << 16) | (Math.floor(g * 255) << 8) | Math.floor(r * 255);
    }

    const imageData = new ImageData(new Uint8ClampedArray(finalBitmap.buffer), width);
    ctx.putImageData(imageData, 0, 0);
});

This triangle intersection test is the one used in the PBRT book, but without the barycentric coordinates calculation, because we are not doing any texture mapping.

Also, you should notice that the code calcualtes several values that are dependant on the Ray used for intersection test. In this simple example, it would not make any difference, but when working with more complex scenes, we could pre-compute those values and reuse them to speedup the intersection tests. The whole path tracing implementation here is super slow, but it also offers plenty of speedup opportunities, you just need to get creative.

Finally, this algorithm I implemented here is a very straight forward way to calculate a Ray-Triangle intsersection; there are plenty of others with varying performance characteristics and optimization benefits, for example the Möller–Trumbore intersection algorithm which I currently use in my Light render is faster than the one in this article in some circumstances, but you also need to precompute some values for the triangles.

As is always the case, experiment to find what works best for your case.

Eccentric Developments

run startx on login - Raspbian Jessie Lite

Previous Posts