Rendering tiles method 2 (part 7)

So I promised a second approach to the same tile rendering demo in my previous post. With this approach we'll put the solution on its head.

This solution isn't necessarily better or faster, it can be depending on how complex your map is and whether you applied the optimizations to the previous method I suggested or not.
It is however a very worth while technique to learn.

What we are doing in essence here is to draw every pixel on screen and figure out what part of our map should be drawn here. We'll be moving part of our solution into our fragment shader. That in itself should sound some alarm bells as this will increase the workload of the GPU however we are removing overhead as we no longer generate a complex mesh nor attempt to draw anything that would have been off screen. It is how this balance shifts that determines whether this approach is better or worse.

As simple as our example is we're probably implementing a slower solution. However when you are looking at multiple layers of the maps drawn over each other it would be possible to combine the logic within a single fragment shader and possibly remove a lot of overhead.

Inverse of a matrix

One new function that was added to our math library is a function that generates the inverse of a matrix. The inverse of a matrix is a matrix that applies the inverse of the translation of that matrix. Say you have a matrix that rotates an object 90 degrees clockwise, the inverse of that matrix would rotate the object 90 degrees counter clockwise.

It isn't always possible to create the inverse of a matrix but generally speaking it works very well.

In our case we're going to take the inverse of our projection matrix. This allows us to take a screen coordinate, apply our inverse matrix and figure out the coordinate for our "model". Remember that in our original example we generated a 40x40 mesh for rendering our map, it is the coordinates within this 40x40 mesh that we calculate.

Applying our inverse matrix to every pixel we are rendering would be very wasteful but luckily for us we're dealing with a linear projection. As a result we only need to calculate our coordinates at each corner of the screen and interpolate those values, something OpenGL is very good at. We'll look into this a little more once we look at our vertex shader.

Where did my model-view-projection matrix go?!?

First however we take a very important sidestep. I've made only minor changes to my sample application. I don't tent to remove things often used as we may change things back for our next example. In our shader loader we are now loading "invtilemap.vs" and "invtilemap.fs" instead of our orignal tilemap shader. While I'm still defining my mvp matrix we are now using the inverse of this matrix in our solution.

What you'll see is that our call:

mvpId = glGetUniformLocation(shaderProgram, "mvp");

will fail even though our mvp variable is defined in our shader, it just isn't used. GLSL will automatically filter out any unused variables during compiling the shader and thus there is no variable to obtain our uniform location for.

There is a lot of debate to be found on the internet about this and various strategies on how to deal with it. It is a good thing to research and make up your own mind about. For now I just log variables I can't find so I can make up my mind whether this is intentional or indicates a fault in my program. Especially when you have multiple shaders you may not want to custom make different loaders but simply call the same code to load the shaders and just assume common variables to be there.

Our shader loader code has only slightly been changed, the only noteworthy change is the addition of getting our uniform for invmvp, our inverse model-view-projection matrix.

In our render function we then see that we calculate the inverse of our matrix and set it in our shader:

    // set our model-view-projection matrix first
    mat4Copy(&mvp, &projection);
    mat4Multiply(&mvp, &view);

    if (mvpId >= 0) {
      glUniformMatrix4fv(mvpId, 1, false, (const GLfloat *) mvp.m);      
    };
    if (invMvpId >= 0) {
      // also want our inverse..
      mat4Inverse(&invmvp, &mvp);
      glUniformMatrix4fv(invMvpId, 1, false, (const GLfloat *) invmvp.m);      
    };

A little further down we also see that our call to glDrawArrays now tells OpenGL to only draw 2 triangles.

Our inverse shaders

This is due to our main change that we are going to draw each pixel on screen once. As a result we need to draw a single square, thus two triangles, that encompass the entire screen. In OpenGL we're dealing with a coordinate system that has (1.0, 1.0) in the top right and (-1.0, -1.0) so that is what we're drawing in our vertex shader:

#version 330

uniform mat4 mvp;
uniform mat4 invmvp;

out vec2 T;

void main() {
  // our triangle primitive
  // 2--------1/5
  // |        /|
  // |      /  |
  // |    /    |
  // |  /      |
  // |/        |
  //0/3--------4

  const vec2 vertices[] = vec2[](
    vec2(-1.0, -1.0),
    vec2( 1.0,  1.0),
    vec2(-1.0,  1.0),
    vec2(-1.0, -1.0),
    vec2( 1.0, -1.0),
    vec2( 1.0,  1.0)
  );

  // Get our vertice
  vec4 V = vec4(vertices[gl_VertexID], 0.0, 1.0);
  
  // and project it as is
  gl_Position = V;
  
  // now apply the inverse of our projection and use the x/y 
  T = (invmvp * V).xy;
}

Notice also that we apply our inverse model-view-projection matrix but only store the x/y into a 2D vector, that is all we're interested in here. As mentioned before, OpenGL will nicely interpolate this value for us.

The real work now happens in our fragment shader so we'll handle that in parts:

#version 330

uniform sampler2D mapdata;
uniform sampler2D tiles;

in vec2 T;
out vec4 fragcolor;

Nothing much special in our header, we now have both texture maps here, our T input from our vertex shader and our fragcolor output.

void main() {
  vec2 to, ti;
  
  // our tiles are 100.0 x 100.0 sized, need to map that
  to = T / 100.0;
  ti = vec2(floor(to.x), floor(to.y));
  to = to - ti;

Here we've defined two variables, "to" which will be our coordinate in our tilemap and "ti" which will be our coordinate in our map data. You may recall from our original solution we created our tiles as 1.0 x 1.0 tiles and multiplied them by 100 to get 100.0 x 100.0 tiles. Here we need to divide them by 100.
We floor "ti" to get integer values and than subtract "ti" from "to" so "to" contains offsets within a single tile.

  // our bitmaps are 32.0 x 32.0 within a 256x256 bitmap:
  to = 31.0 * to / 256.0;

As our tiles are 32x32 tiles within a 256x256 bitmap, just like in our original solution we need to adjust our offset accordingly

  // now add an offset for our tile
  ti += 20.0;
  int tileidx = int(texture(mapdata, (ti + 0.5) / 40.0).r * 256.0);
  int s = tileidx % 8;
  int t = (tileidx - s) / 8;
  to = to + vec2((float(s * 32) + 0.5) / 256.0, (float(t * 32) + 0.5) / 256.0);

And now we use our "ti" value to figure out which tile we need to draw at our pixel. Note that this is pretty much what we originally did in our vertex shader.

  
  // and get out color
  fragcolor = texture(tiles, to);  
}

And voila, we've got the same result as before we started but using a very different way to get there.

So where from here?

There is much less to say about this then the previous technique.

For one, if you want to overlay multiple layers of maps it would be good to look into retrieving the pixel values for each layer in one fragment shader and either picking the right color or blending them. It would be much more effective then rendering each layer separately and having OpenGL blending it for you.

This technique does not lend itself well initially when you start looking at projecting the map using a 3D projection however using the inverse of a 3D projection opens up an entirely different door. Look around on shadertoy.com and you'll find legions of effects that use this approach as a starting point to apply raycasting type techniques. That however is an entirely different subject for another day.

On a related subject, and this applies to the previous example as well, it will not have escaped you that allowing the user to rotate our map isn't exactly looking nice with the map we are using. That option really only works if we have a pure top down map. I just wanted to show what we can do with our view matrix even if it may not be something you wish to use in a real game environment.

What's next?

I'm not sure yet. I've been going back and forth on what type of mini game to use to get to the next stage. I want to start looking into the OpenGL equivalent of sprites. In its simplest forms we'll just be rendering textured quads but it will allow us to go into rendering with blending turned on at one end, and at GLFW and control input on the other.

It may thus take awhile before I make the next blog as I'll be experimenting with a few ideas before I get something worth blogging about.