Game Project Part 3: Implementing View Occlusion

Commit 90e349e5ca764a71a7dea7cd771d0c2c3a7da11e

Here I will try to tackle a problem that I introduced in the last post - implementing a 2d visibility algorithm. Yes, this is a 3d game, but I'd like an effect similar to the one presented there. My idea is to create an underlying 2d linkage (that is, a faceless mesh composed of only vertices and edges) to represent the "walls" through which no light can pass. From there, we will run a fairly simple line segment collision algorithm on the shader for each edge, then darken any pixels that are in the "shadow".

Creating and Importing the View Occluder

I began by creating the linkage, which I'll be refering to as the view occluder in Blender.

Very simple, as you can see - about fifty edges.

Exporting it into the type of JSON files used by THREE.js involved some work. By default, the provided THREE.js exporter script only does vertices and faces. We will have to extend it to support edge connections for the linkage.

Thankfully, I already did this some time ago on my RTS project. I made a small script while I was working on adding pathfinding capabilities. The python script runs inside of the convenient built-in text editor, extracting mesh information from the Blender API. Here is the script:

# Run this from within Blender to export edge data to the desired text file. Replace the
# strings on lines 5 and 16 to edit the object and output file, respectively.
import bpy

object = bpy.data.objects['ViewOcclusion'].data

# Generate an empty sublist for every vertex
out = [[] for i in object.vertices]

for edge in object.edges:

    # Doubly linked edge array

    #out[edge.vertices[0]].append(edge.vertices[1])
    #out[edge.vertices[1]].append(edge.vertices[0])


    # Singly linked edge array
    if edge.vertices[0] > edge.vertices[1]:
        out[edge.vertices[1]].append(edge.vertices[0])
    else:
        out[edge.vertices[0]].append(edge.vertices[1])


save = open('/path/to/file.txt', 'w')
save.write(str(out))
save.close()

Inside of file.txt, you'll find an array full of vertex indicies that represent edge connections in the mesh. It looks like this:

[[3], [4, 2], [1, 3], [2, 0], [5, 1], [4, 6], [5, 7], [6, 8], [7], [10] ... ]

For more information, check out mapspec.mdown where I wrote a little bit about the datastructure that is used. That link will take you to the file as it is at the time of writing.

I manually added this array into the JSON file as generated by the THREE exporter. THREE.js will only parse the default parameters once a mesh has been loaded. With a little bit of ingenuity, we can overwrite the parse function to add on our extra edge data to the geometry object.

// Create a wrapper for the parsing function, which is automatically called by 
// JSONLoader
var oldParse = THREE.JSONLoader.prototype.parse;
THREE.JSONLoader.prototype.parse = function(json, texturePath) {
    var obj = oldParse(json, texturePath),
        geo = obj.geometry;

    geo.viewOcclusion = oldParse(json.viewOcclusion, texturePath).geometry;
    geo.viewOcclusion.edges = json.viewOcclusion.edges;

    geo.viewOcclusion.edgePairs = parseEdges(json.viewOcclusion.edges);

    return obj;
};

// viewOcclusion.edges are the edges exactly as defined in map.js

// Generates viewOcclusion.edgePairs, which collapse into an array of ints
// [Edge1A, Edge1B, Edge2A, Edge2B, ... ] that can be fed into a shader
function parseEdges(edges) {
    var edgePairs = [];

    for(var i = 0; i < edges.length; i++) {
        for(var j = 0; j < edges[i].length; j++) {
            edgePairs.push(i, edges[i][j]);
        }
    }

    return edgePairs;
}

It's a crude workaround, but it does what is should and is actually a pretty elegant solution! I am embedding the view occluder within the regular JSON file. That's why oldParse is being called twice - once for the regular mesh and once for the view occluder. The only thing I actually need it for in the view occluder is to convert the flat array representation of vertices into an array of THREE.Vector3s. We can skip most of the other dirty work because our mesh has no faces! :)

The second function above is self-explanatory; our nested array structure for the edges, while useful in JavaScript for future applications, cannot be fed into a shader. This function collapses it into a flat integer array of edge-forming vertex pairs.

With some extra effort, the view occluder can be visualized with help from the convenient THREE.Line class.

I had to mess around a little bit with the best way to do it. The lines are defined as a THREE.Geometry object, where the connections are in between all of the vertices. A problem arises because my data structure does not define "chains" of vertices in this way. Apparently you can create disconnected lines with a technique called indexing, but I found no problems with creating each edge as its own individual line and adding all of them as children to one big object! Don't fix what isn't broken, right?

Feeding View Occluder Geometry into a Shader

This proved to be quite a lot more challenging that I anticipated. First, let's try the obvious and add the uniforms to the material.

var vo = engine.map.viewOcclusion;

var uniforms = THREE.UniformsUtils.merge([
    THREE.UniformsLib.common,
    THREE.UniformsLib.lights,
    {
        'uPlayerPosition': {
            type: 'v3',
            value: engine.player.position
        },

        'uVOVerts': {
            type: 'v3v',
            value: vo.vertices
        },

        'uVOEdges': {
            type: 'iv1',
            value: vo.edgePairs
        }
    }
]);

And the accompanying declarations within the fragment shader: (all of my experiments here are in the fragment shader for simplicity sake)

uniform vec3 uPlayerPosition;

uniform vec3 uVOVerts[];
uniform int uVOEdges[];

varying vec3 vLightFront;
varying vec4 vWorldPosition;

But we get an error: ERROR: 0:43: 'uVOVerts' : unsized array declarations not supported. Uh oh. But it's okay! With some more playing around, it turns out that THREE.ShaderMaterial supports adding custom DEFINE statements in the shader prefix. It's a very simple solution.

// JS
var defines = {
    'uVOVertsLength': vo.vertices.length,
    'uVOEdgesLength': vo.edgePairs.length
};

// GLSL
uniform vec3 uVOVerts[ uVOVertsLength ];
uniform int uVOEdges[ uVOEdgesLength ];

And it compiles without error!

Calculating Shadows

Now we have to loop through each and every edge, calculating if the current pixel is within a shadowed area or not. If the line segment formed between the player position and the current pixel intersects the current edge, then the pixel must be shaded black.

Here are the prerequisite functions defined in GLSL:

// Hope to Jesus that no lines are perfectly parallel or have verticies 
// exactly on the origin
vec2 intersectPoint(vec2 a, vec2 b, vec2 c, vec2 d) {
    float slope1, slope2, c1, c2;

    // Calculate slopes of both lines
    slope1 = (b.y - a.y) / (b.x - a.x);
    slope2 = (d.y - c.y) / (d.x - c.x);

    // Calculate y-intercepts of both lines
    c1 = a.y - (a.x * slope1);
    c2 = c.y - (c.x * slope2);

    // (m1x + y1 = m2x + y2) boils down to (x = (y2 - y1) / (m1 - m2))
    float ix = (c2 - c1) / (slope1 - slope2),
          iy = (ix * slope1) + c1;

    return vec2(ix, iy);
}

bool onLine(vec2 point, vec2 a, vec2 b) {

    // Make sure x is in the domain of both lines
    // Checking just x should be enough
    return (point.x < max(a.x, b.x)) && (point.x > min(a.x, b.x));
}

bool intersect(vec2 a, vec2 b, vec2 c, vec2 d) {
    vec2 i = intersectPoint(a, b, c, d);

    return onLine(i, a, b) && onLine(i, c, d);
}

bool withinRadius(vec2 a, vec2 b, float radius) {
    // deltaX^2 + deltaY^2 < r^2 
    return ((b.x - a.x) * (b.x - a.x)) + ((b.y - a.y) * (b.y - a.y)) < (radius * radius);
}

Looping through each edge SHOULD be an easy thing to do but, surprise surprise, GLSL doesn't like it.

vec3 vertA, vertB;
for(int i = 0; i < uVOEdgesLength; i += 2) {

    vertA = uVOVerts[uVOEdges[i]];
    vertB = uVOVerts[uVOEdges[i + 1]];

    if(intersect(vertA.xz, vertB.xz, uPlayerPosition.xz, vWorldPosition.xz)) {
        gl_FragColor *= 0.0;
    }
}

ERROR: 0:255: '[]' : Index expression must be constant. John Smith writes about this issue in Hassles with array access in WebGL. One of his clever workarounds is to, get this, use a for loop to go through every value until we reach the one we want, then use the index variable instead of the original variable! This sounds confusing, so let me explain.

Above, for both vertA or vertB, we have two indexing operations. The first is uVOEdges[i], which compiles happily because WebGL counts index variables as constants. The second is when we take that value and use it as an index into uVOVerts, forming the overall expression uVOVerts[uVOEdges[i]]. WebGL doesn't like you using non-constants for indices, hence the error was raised. Smith's workaround uses the index of a second for loop for accessing the second array. Thus the following code will compile:

int edgeA, edgeB;
vec3 vertA, vertB;

for(int i = 0; i < uVOEdgesLength; i += 2) {
    edgeA = uVOEdges[i];
    edgeB = uVOEdges[i + 1];

    for(int j = 0; j < 200; j++) {
        if(j == edgeA) {
            vertA = uVOVerts[j];
        }

        if(j == edgeB) {
            vertB = uVOVerts[j];
        }
    }

    //Disable for slowness

    if(intersect(vertA.xz, vertB.xz, uPlayerPosition.xz, vWorldPosition.xz)) {
        gl_FragColor *= 0.0;
    }
}

It's bizzare to be sure, but it works, and it's awesome! I love those moments when your program finally works like it should. Here's a screenshot and a couple bonus images of the debugging process.

---

There is one problem, though - the performance is horrendous! I can get a solid 20fps when I resize the my chrome window to the smallest possible size. When fullscreened, I get one frame every 5-10 seconds or so. It's no surprise; this system is a combination of non-practical workarounds. As the old engineering saying goes "First make it work, then make it work better!" In the next post, I will document my attempts to improve performance and optimize the system to the point of playability.