Pompi Pompi – A Gamers and Developers blog for indie games

Performance is a strange beast.
I was just profiling a section in Labyrinthica that was responsible of drawing the walls sprites. The function had a loop that iterates about 200 times and each iteration calls a sprite draw call. Inside the loop there was the following code:

ostringstream OStr;
OStr<<"Not 1 or 2("<<i<<")";
Error::Assert (i==1 || i==2, OStr.str());

With this code the walls drawing function took 7% of a specific time. Then I changed this part of code to:

ostringstream OStr;
OStr<<"Not 1 or 2";
Error::Assert (i==1 || i==2, OStr.str());

After this change I got 4%. I then changed it to:

Error::Assert (i==1 || i==2, "Not 1 or 2");

And I got down to 2%. The conclusion is that performance can be very tricky. What might seem innocent(A simple string handling) might turn to be big CPU usage when performed inside a loop.
I found that there is quite an imagination between profiling and debugging. Maybe there is a way to reduce the time of profiling and avoid from these kind of pitfalls? I hope to figure this out in the future. I think there is something that might help.

In a previous blog post, I talked about bug negative verification. I also said that debugging should be avoided as much as possible.
That is true, debugging is mostly a waste of time. You spend a lot of hours trying to figure out why what you yourself wrote doesn’t work as it should. After you solve the bug, you don’t have a new feature, there is no prevention that you will make the same mistake in the future and you might have to redo the same wasteful debugging process you just did. Right? Well, not exactly.
A good philosophy to adopt is, can I do something so the same kind of bugs won’t reappear in the future? If you invest some time, after solving the bug, to figure out how to prevent future similar bugs from happening you might learn or gain something from the bug. That is why a bug is an opportunity to learn how to prevent similar bugs in the future.
For instance, a buffer overflow is when you are accessing an array beyond its allocated size. In c++ it would be doing something like this:
int a[4];
a[10] = 12;
If your program is doing weird things, you might eventually capture this bug. But its obvious it is better to use an array that is safe. Such as, an array that check if the index provided for cell access is within the boundaries of the array. If its not, it will report a run time error and let you know you did something wrong.
However, things are not always as simple as in the case of the array. Sometimes its not clear how you can prevent certain bugs. Lets say you have a game with medieval weapons such as swords and daggers. You want to give the dagger a power of 2 and the sword a power of 3. You gave the sword a power of 3, but you accidentally gave the dagger a power of 4. This is a bug, even though nothing will crash. It would be very difficult to prevent this kind of bug, but I can think of ways that would help catching this bug early.
Another concrete example is GPU shaders. You can write a shader in some high level language such as HLSL for directX. These shaders often have global parameters you can set through your program. I had a bug in a shader that it didn’t draw what I meant for it to draw. I then began debugging. First I checked if the color texture was really passed to the shader. Then I checked the normals in the vertex data and etc. I finally found that I forgot to set one of the global parameters of the shader. I wasted an hour or two to figure out this bug. A way to prevent this bug is to keep track of which parameters are set before each draw call, and report an error if not all the parameters were set.
However, you sometimes don’t want to set all the parameters in a shader, so what is the right choice?

I would say its a good habit to do some thinking after solving a bug, and not immediately move on to the next task. Why this bug happened? How I solved it? Did I really solve it? How can I prevent similar bugs from happening in the future? Should I prevent similar bugs in the future or is it not cost effective and having this kind of bug from time to time is acceptable?

Last but not least, you need to take what I said with a grain of salt. This is something that worked for me, from my own experience under certain conditions, but you don’t have to do exactly the same. Its not formal anyway, because you can’t 100% formalize programming. Its an advice, not rules or a recipe to follow blindly.

Abstract
Suggesting a technique of implementing a Geometry based Anti Alias(GAA), instead of using the built in 3D graphics AA. This technique has the potential to improve performance and quality of the AA under certain conditions. In short, I am using a geometry based or fins geometry outline technique, and use it to draw translucent smooth edges with the same color of the original 3D model.

Pre Requirements
In order to implement this algorithm, one need to have a geometry based or fins geometry Non Photo Realistic outline shaders implemented. 
This type of shader use a mesh of fins. For every edge or intersection between two triangles in the original mesh, there is a fin in the fins mesh. When rendering this fins mesh, we select in the shader which fins will be visible and which will not. The fins that are visible are those that one of the two triangles the fin belongs to is facing the camera and the other doesn’t. This cause that the viewable fins are the outline fins of the projected mesh on the screen space.
Some articles explaining how to do this, can be found here:
Single Pass GPU Stylized Edges
NPR with Pixel and Vertex Shader

How it works
Once you have the fins geometry, either by precalculating or using the geometry shader, you need to add additional information to the vertexes of the fin. If you are drawing a black fading outline using the fin geometry, you already have a V coordinate that is 0 where the fin is touching the 3D model and 1 at the farest point of the fin from the 3D model. For the faded black outline, we use this V coordinate to determine what alpha value we want the fin to have in the pixel.

The additional information we need to add, is all the information we have in the 3D model vertex where the fin come out from, which is used to calculate the final color of the correspondent triangles. For instance, if the vertex keeps a normal to calculate diffuse lighting, we need to keep this normal in the correspondent fin vertex as well.
We pass this information from the fin vertex to the pixel shader and on the pixel shader we calculate the color just like we would calculate the color in the pixel shader of the 3D model.
The next step is to multiply the fin color with an alpha, much like we did with the faded black alpha, and we get the anti aliased edge.
The results are shown in the following images of a ball and a scene from the game Labyrinthica: The quest of lima. For comparison I have included a render with no AA and a render with AA from an NVIDIA Geforce 8600 GTS set at 16Q.
Also a render of GAA outline without the 3D model.

Aliased ball

Built in Anti Alias

GAA ball

GAA only

Performance, quality and issues
GAA might prove to have better or worse performance than the built in AA of the graphics card.
The main bottlenecks of GAA are the vertex shader, in case no geometry shader is available, and part of the bottlenecks that the 3D model suffer from depending on the shader it use to calculate color. For instance, a use of texture might cause a memory bus bottleneck. On the other hand, GAA will most likely be calculated for only small part of the pixels on the screen, unlike the graphics card AA which is calculated for all the pixels in the screen.
In terms of quality, GAA has several differences from built in AA. You can control the fin’s thickness, making it possible for smoother and more pleasing AA. It does not make textures or models’ surfaces blurred or smoothed. And you can add a black outline for NPR rendering almost for free.

GAA might not work for edges with very high curvature or surface with unsmooth normals or unsmooth parameters used for calculating the color. Problems may arise due to the fact that the color on a specific vertex of a mesh is not the same color as the pixel next to it. Because the data at the pixel is the interpolation of 3 vertexes and not the exact data in the closest vertex. This might cause problems such as back facing normals on the fin.

Bugs and debugging are a big issue for a programmer. Mostly because he\she should avoid them as much as possible.
I would like to share my thoughts about what I decided to call ”Bug negative verification”.

When fixing a bug, there are three important questions(or more) that a programmer should ask himself:
1) Did I really fix the bug?
2) Do I know why the bug happened?
3) How can I prevent similar bugs to appear in the future?
I want to talk mostly about the first question.

After finishing working on the last level of Labyrinthica: The quest of lima, I have been play testing to find problems. One major problem was that in the boss level, sometimes the walls were not drawn.
However, the physics worked and the mini map worked as if the walls were there. This led me to suspect that the class that made draw calls for the walls’ sprites was part of the problematic code.
The code who made the sprite draw calls was a bit difficult to figure out how it will behave. I think that after profiling I tried to make it more optimized, but I am not sure.
So I wrote a simple and naive(KISS: Keep It Simple Stupid ) code that suppose to have the same functionality.
At this point I wasn’t really sure if the bug or part of the bug was in the code I rewrote. I play tested and saw the bug did not appear, but since the bug sometime appear and sometime do not, I wasn’t really sure.

Then it occurred to me that if this code was not the problematic code, the old code should not performed any less than the new code. To check this, I have made both the old and new code run together with the same data(conditions) parallel to each other, and compare their performance.
The result of this check was that the new code was sometimes out performing the old code, but was never under performing the old code.
This is sort of the opposite of verification, I tried to verify that the old code was buggy.
Now I know there is a difference between the results of the new code and the old code, and that the points where there are differences, the new code performed better.
The conclusion is that the old code must be buggy. The new code might be buggy as well, but for now it can enjoy the benefit of the doubt that it outperformed the old code.

The next screenshot captures the bug symptom.
Billboard is the number of trees in the new code, Bug is the number of trees in the old code and Max is an upper bound of the number of trees in the old code.
You can see on the top right the mini map still works even though the trees are not drawn in the game itself.

Bug negative verification (Click image)

We sort of answered the question of “Did I really fix the bug?”
Trying to answer this question can help us answer the second question. But answering these two questions consumes a lot of time in debugging.
Debugging is a kind of a waste of time. Because you spend a lot of time trying to make things work, and not adding anything new to the program.
Is there a solution to this time consuming problem?
There is a partial solution. If we could learn enough from the bug, we could use this knowledge to figure out how to prevent similar bugs in the future, by taking certain design decisions and solutions.
I hope to talk more about how to prevent bugs in the future.