Tuesday, September 20, 2011

LL3DLGLD – 1 – Brute force

Welcome to LL3DLGLD (Let’s learn 3D like good little dragons) my new (hopefully) short (because I learn fast?) series in which we learn together to create a high performance but probably rudimentary 3D engine capable of displaying a DwarvesH map in real time.

Hopefully I will be able to both demonstrate what issues arise and how to fix them, or at least compromise until we reach something playable.

At first I will be doing my research with pure Irrlicht, with the new nascent engine not being aware of DwarvesH.

In the first phase I’ll create something capable of rendering the complex geometry of a map, but without plants, trees and other decorations. Just the raw shape of a map. I will also be skipping on floors to simplify the initial complexity of the problem. So, our problem in its integrity: given a 3D boolean matrix, where the value true represents the presence of a block, and the value false represents the absence of one, render it using 3D polygons. Performance must be as close as possible realistically to the best performance you would get if you would feed the optimal polygon list to the hardware on each frame, disregarding computation times. We can simplify the problem even more by considering the matrix a set of planes one on top of the other.

A naïve implementation would say: “Cubes? No problem! We’ll just create a cube for each cell in the plane if it is set to true”. But this won’t work for too long.

Without further ado, here is a textured cube without lighting created with its center in the origin of the coordinate system:


This looks like a top down 2D mode, but since it is polygonal and hardware based, there are a few things to consider, like how the texture used is absurdly high (1024x1024), yet the framerate is over 700 and most importantly, one can swing around the camera:


The hardware is also capable of applying textures in a non ugly fashion with different filtering options and does some funky stuff to reduce its workload as the parts of the object are farther away from the camera:


Now that we have one cube, let’s create one for each cell in the plane. For starters, we’ll consider the plane to be 11x11 cells and I’ll show you a few screenshots showing the slab from different angles:


I don’t know about you, but I am starting to get lost. From what angle were these screenshots taken? How does the 3D coordinate system work? Let’s try and create a few helpful markers:


The block with the “-5 -5” texture has the X and Y coordinates of -5, the block with the “5 5” texture has the coordinates of 5 and the one in the middle zero of course, with all Z coordinates being 0. We are using a left-handed Cartesian coordinate system (I don’t know if one can change this to right-handed). Supposing that we are looking exactly at the origin like in the screenshot (point 0, 0, 0), anything to the right of the center has positive coordinates and the same for anything above it. As we get closer to the camera the Z axis decreases and the space between the camera and the origin has negative Z coordinates. It is very important to be extremely comfortable working with this system and to have a good mapping from logical map coordinates into real 3D coordinates. In my case, I will probably have to start at a point in the positives on the Y axis, and decrease it going to the same value in the negative. Now we can add a few extra blocks on top of this plane using a skipping pattern, so we’ll add the cubes at a Z coordinate of -10, using a darker texture:


One thing that is immediately apparent is that the FPS camera from Irrlicht is not facing the way I want it. It would help a lot if I can use this coordinate transformation convention, but the camera is centered on the Z axis and I would like to be along the X or Y axis. I do not know how to fix this yet, but it is not important right now.

So why won’t this approach work? Let’s ramp up the number of cubes by adding 20 cubes to the X and Y dimensions:


Wow, check out that framerate drop. Now let us consider a realistic map of 300x300, but with its height reduced to only 2 (from the default of 60). So not that realistic actually:


The framerate dropped down to 3 and the camera refuses to zoom out even further. This is the core of the problem, the reason you can’t just place object on the scene like you would do in a 3D program: if you have a fair amount of objects, the number of objects becomes a lot more important than the number of polygons. To give an inaccurate example in order to illustrate this system: if your graphics card can run at a smooth frame rate with one object with 100 million polygons, it will have a considerably lower framerate when rendering 100 objects with 1 million polygons each, even though the total number of polygons and their location is identical. One cannot even use normal LOD techniques: the objects I am rendering are cubes! How do you expect to lower the level of detail even more than a cube? The answer is you can’t and you need both to cheat and actually do not render some objects that should be visible and also find ways to recreate the same scene visually, but by using fewer objects.

We’ll ignore the added little darker cubes and try to create a map geometry renderer capable of rendering the entire plane with a good framerate, using only a few objects. This is what we are hoping to get, but with a framerate of at least 400:

1 comment:

  1. Do not render faces that point away from the camera.
    The case of a sparse mesh of evenly spaces cubes is pretty close to worst case.
    Use vbo/drawlist or other forms of pushing the terrain to the gpu and avoid doing work every frame.
    600000 faces for your 300x300x6x2 cube example should work ok.

    ReplyDelete