Perspective-Correct Texture Mapping

Question

I am working on a small rendering engine for a personal project and I am having issues with the texture mapping part of it.

It seems to work for some cases, but not for others. For example, when one of the vertices is behind the camera, the texture is stretched.

Seemingly Correct case Incorrect case

I am guessing that it has something to do with the texture mapping not being perspective-correct. I have tried various changes mainly involving the z-distance to the camera, but I could not find any quick fix to my code.

Here is my code for the perspective projection:

public double[] project(double x, double y, double z) {
    double tx = x - camera.x;
    double ty = z - camera.z;
    double tz = y - camera.y;

    double cx = Math.cos(camera.pitch);
    double cy = Math.cos(camera.yaw);
    double cz = Math.cos(camera.roll);

    double sx = Math.sin(camera.pitch);
    double sy = Math.sin(camera.yaw);
    double sz = Math.sin(camera.roll);

    double dx = cy * (sz * ty + cz * tx) - sy * tz;
    double dy = sx * (cy * tz + sy * (sz * ty + cz * tx)) + cx * (cz * ty - sz * tx);
    double dz = cx * (cy * tz + sy * (sz * ty + cz * tx)) - sx * (cz * ty - sz * tx);

    double ez = 1.0 / Math.tan(FOV / 2.0);

    double bx = ez / dz * dx;
    double by = ez / dz * dy;

    if (dz < 0.0) {
        bx = -bx;
        by = -by;
    }

    int px = (int) (width + bx * height) / 2;
    int py = (int) (height + by * height) / 2;

    return new double[] { px, py, dz };
}

and here my code for the texture mapping:

public double[] map(double x, double y, double x0, double y0, double x1, double y1, double x2, double y2, double x3, double y3) {
    double A = (x0 - x) * (y0 - y2) - (y0 - y) * (x0 - x2);
    double B = ((x0 - x) * (y1 - y3) - (y0 - y) * (x1 - x3) + (x1 - x) * (y0 - y2) - (y1 - y) * (x0 - x2)) / 2.0;
    double C = (x1 - x) * (y1 - y3) - (y1 - y) * (x1 - x3);

    double det = A - 2.0 * B + C;

    double u;
    if (det == 0.0) {
        u = A / (A - C);
        if (Double.isNaN(u) || u < 0.0 || u > 1.0)
            return null;
    } else {
        double u1 = ((A - B) + Math.sqrt(B * B - A * C)) / det;
        boolean u1valid = !Double.isNaN(u1) && u1 >= 0.0 && 1.0 >= u1;

        double u2 = ((A - B) - Math.sqrt(B * B - A * C)) / det;
        boolean u2valid = !Double.isNaN(u2) && u2 >= 0.0 && 1.0 >= u2;

        if (u1valid && u2valid)
            u = u1 < u2 ? u2 : u1;
        else if (u1valid)
            u = u1;
        else if (u2valid)
            u = u2;
        else
            return null;
    }

    double v1 = ((1.0 - u) * (x0 - x) + u * (x1 - x)) / ((1.0 - u) * (x0 - x2) + u * (x1 - x3));
    boolean v1valid = !Double.isNaN(v1) && v1 >= 0.0 && 1.0 >= v1;

    double v2 = ((1.0 - u) * (y0 - y) + u * (y1 - y)) / ((1.0 - u) * (y0 - y2) + u * (y1 - y3));
    boolean v2valid = !Double.isNaN(v2) && v2 >= 0.0 && 1.0 >= v2;

    double v;
    if (v1valid && v2valid)
        v = v1 < v2 ? v2 : v1;
    else if (v1valid)
        v = v1;
    else if (v2valid)
        v = v2;
    else
        return null;

    return new double[] { u, v };
}

and here is my quad drawing code:

public void renderFace(Screen screen, int x0, int y0, int z0, int x1, int y1, int z1, int x2, int y2, int z2, int x3, int y3, int z3) {
    boolean render = true;

    double[] p0 = screen.project(x0, y0, z0);
    int px0 = (int) p0[0], py0 = (int) p0[1];
    render |= p0[2] >= ZCLIP && px0 >= 0 && px0 < screen.width && py0 >= 0 && py0 < screen.height;

    double[] p1 = screen.project(x1, y1, z1);
    int px1 = (int) p1[0], py1 = (int) p1[1];
    render |= p1[2] >= ZCLIP && px1 >= 0 && px1 < screen.width && py1 >= 0 && py1 < screen.height;

    double[] p2 = screen.project(x2, y2, z2);
    int px2 = (int) p2[0], py2 = (int) p2[1];
    render |= p2[2] >= ZCLIP && px2 >= 0 && px2 < screen.width && py2 >= 0 && py2 < screen.height;

    double[] p3 = screen.project(x3, y3, z3);
    int px3 = (int) p3[0], py3 = (int) p3[1];
    render |= p3[2] >= ZCLIP && px3 >= 0 && px3 < screen.width && py3 >= 0 && py3 < screen.height;

    if (!render)
        return;

    int minX = Math.min(Math.min(px0, px1), Math.min(px2, px3));
    if (minX < 0)
        minX = 0;
    if (minX > screen.width)
        minX = screen.width;

    int minY = Math.min(Math.min(py0, py1), Math.min(py2, py3));
    if (minY < 0)
        minY = 0;
    if (minY > screen.height)
        minY = screen.height;

    int maxX = Math.max(Math.max(px0, px1), Math.max(px2, px3));
    if (maxX < 0)
        maxX = 0;
    if (maxX > screen.width)
        maxX = screen.width;

    int maxY = Math.max(Math.max(py0, py1), Math.max(py2, py3));
    if (maxY < 0)
        maxY = 0;
    if (maxY > screen.height)
        maxY = screen.height;

    if (minX == maxX || minY == maxY)
        return;

    for (int py = minY; py < maxY; ++py)
        for (int px = minX; px < maxX; ++px) {
            double[] uv = screen.map(px + 0.5, py + 0.5, px0, py0, px1, py1, px2, py2, px3, py3);
            if (uv == null)
                continue;
            double u = uv[0], v = uv[1];

            double pz = (1 - u) * ((1 - v) * p0[2] + v * p2[2]) + u * ((1 - v) * p1[2] + v * p3[2]);
            if (pz < ZCLIP)
                continue;

            int texX = 15 - Math.min(15, (int) (16 * u));
            int texY = 15 - Math.min(15, (int) (16 * v));
            screen.setPixel(px, py, pz, Art.WALLS.getPixel(texX, texY) * BRICKS);
        }
}

Can anyone point out what I am doing wrong? I am not very experienced as this is my first try at implementing a game engine.

Thank you for any insight.

Answer 1

Your code isn't wrong at all. You are dealing with matrices and vertices the right way (your 3D simulation actually works), and even texture mapping is fine. Matter is, your texture mapping algorithm uses just a linear interpolation to map a point in the 3D space to a point in the 2D plan of a given texture.

Texture mapping
When mapping texture to mesh polygons, you usually consider a 3-ple in the tridimensional space (three 3D vertices), and associate it to another 3-ple in a 2D plan (three 2D vertices inside a texture). When drawing, the three 3D vertices are projected on the screen ([x,y,z] to [x',y']); then the triangle considered on the texture (our three 2D vertices) is drawn on the screen, eventually transforming the 2D vertices to fit the previous projection. You know this because you actually did it.
But, the texture mapping algorithm you implemented is an affine texture mapping, meaning that the triangles are drawn using only plane affine transformations (thus, translation, rotation, scaling, flipping/mirroring), so when drawing you are considering the coordinates as they are, without information about their actual depth in their tridimensional counterparts. You are just drawing sprites.

Perspective correction To draw textures correctly in a 3D space projection, we need to consider the vertices along with some information about their depth in the space in relation to the 3D camera position. To accomplish perspective correction for textures, we consider the linear interpolation formula:

, where .

Affine texture mapping directly interpolates between two values, and lerping twice lets the engine to draw every texel needed. This is a fast calculation to perform, but the result is not that realistic.

By introducing information about depth, we are telling the engine that our triangle is not a flat shape on the screen, and this is achieved by editing the interpolation formula as follows:

where z_i is the depth of vertex i in the interpolation. This way, when moving along the texture the computed texel will be in a different position compared to lerp, reflecting real perspective projection with much more fidelity. Usually this computation is harder to perform than lerping, and due to this complexity a dedicated GPU is preferable (and optimized) to calculate texture coordinates. Letting the CPU do all the work means forcing vertex processing, and is not good for your game performance.

Here's a comparison between the original texture (chessboard), its affine texture mapping, and perspective-correct texture mapping.

Drawing from texture to screen is achieved by screen sub division tecniques. These are methods to divide those area on the screen designated for drawing textures into pieces before performing texture drawing.