Extreme Tux Racer

Since nobody seems to be interested in using the forum I'm going to give you some background information. Some people were surprised of the low fps rate of ETR/Tuxracer compared with other games. Working on the core functions I found some of the performance killers:

- The quadtree for rendering the terrains (of course). I'll try to solve this problem later, at the moment I've not time enough.

- The method of shaping Tux. Tux is composed of 34 (!) spheres, each with dozens or hundreds of polygons.

- The particles when braking or turning. It's quite expensive to calculate the params (velocity and motion) of the particles.

- The trackmarks. The entire track is stored and drawn when repeating a race. The trackmarks are not applied to the terrain polygons, they are special quads calculated in respekt to Tux's motion and orientation and overlayed on the terrain - really complex and complicated.

All these options work nice as long as there are no other enhancements like 3D models or real collision detection. I'm afraid they can't be kept completely in a rewrite. Fortunately commercial Tuxracer gives us some hints for a compromise:

- Tux can be shaped with less polygons by using a 3D program. The Tux of commercial Tuxracer looks less nice than the classic Tux but that seems to be unavoidable.


- The trackmarks are only stored for the current race. That reduces the number of marks.

- There might be less particles but the particels might appear with larger size.

- Last but not least: the visual range on the course should be reduced. That can be done by changing the fog planes. It's not a problem to scroll the upper edge of the fog plane upward (carefully) but perhaps the skybox images have to be adapted to the more foggy view (less detailed, coarser contours).

Thanks for an extremely informative post. I'm stuck in France until the New Year, that is why I haven't been present recently.

I'm stuck in France until the New Year

Nice, I've discovered that french people like Tuxracer exceptionally. Most readers of my website are french.

All the best for the new year, and let's hope that the project gets some impulses in 2009.

Thanks Erin !

So Christian, you were in France for the New Year ? Where exactly ?

I am in France now, to see my parents a bit. But for the New year I was in Stockholm...

Erin,

I dont understand what you say about the trackmarks. The fact that they are stored in a fix array means that they always occupy the same space in memory, so I don't think that it impacts the performances.
When you repeat a race, thce track mark counter is reset anyway, which means that the previous track marks will still be present in memory, but ignored and erased as Tux races, because the previous trak marks and the current race's marks reside in the same, unique, array.
The only exception is when you repeat a race because you have failed it, in Event mode. Then the trackmark counter is not reset, and all the previous track marks are drawn again. In that case, it is a desired behavior : I was the one who submitted it, to reproduce old TuxRacer's behavior. It was my first contribution to ETR, I still remember it as if it was yesterday *holding his cane and shaking a bit*

Regarding the quadtree, what type of algorithm is it ? I know nothing about quad trees... so i am not gonna start looking into the code without some theoretical background

The fact that they are stored in a fix array means that they always occupy the same space in memory, so I don't think that it impacts the performances.

Yes and no. You're right, during a race the marks are collected and stored in an array only once, so this array can be used again when repeating a race. Most effort seems to be the calculation of the current trackmarks since the terrain weights have to be taken in consideration (see find_barycentric_coords). Drawing the few trackmarks between the viewer position and Tux' position shouldn't be very expensive.

But when you repeat a game the complete track in the visible area must be drawn. The trackmarks don't replace the normal terrain polygons. First the terrain is completely drawn, then the trackmarks are overlayed in an additional step with blending (very nice, the alpha value is reduced when Tux starts a jump or touches the surface again).

Regarding the quadtree, what type of algorithm is it ? I know nothing about quad trees... so i am not gonna start looking into the code without some theoretical background

The quadtree is a very elaborate algorithm for optimizing the terrain rendering or finding objects in a scenerie. It's 2-dimensional, the 3-dimensional variant is the octree. The quadtree uses the dynamic LOD (level of detail) method: farther triangles are larger and drawn with less details. A great problem is that there might be holes in the terrain when a larger triangle adjoins two smaller triangles. At those positions, auxiliary triangles must be computed. The quadtree is a typical tree algorithm, it works recursively.

The other way is to render all visible triangles with full details and same size (brute force). It avoids the complex quadtree calculation but there are much more triangles to be drawn (brute force: ~4000 - 6000, quadtree ~500 - 1000). We can say, the quadtree burdens the CPU, the brute force burdens the graphic card. I can't say yet what better.

The quadtree algorithm of Tuxracer is a special problem. It was written by Ulrich Fleischer, one of the quadtree pioneers. It's difficult to overlook the code though it is commented amply. And the Tuxracer team has modified it superficially. In my opinion it's not a good idea to study the quadtree by reading the Tuxracer code. It seems to be easier to read one of the articles which can be found on the web. BTW: I'm sure that commercial Tuxracer 1.1 uses another quadtree algorithm.

erin wrote:

The fact that they are stored in a fix array means that they always occupy the same space in memory, so I don't think that it impacts the performances.

Yes and no. You're right, during a race the marks are collected and stored in an array only once, so this array can be used again when repeating a race. Most effort seems to be the calculation of the current trackmarks since the terrain weights have to be taken in consideration (see find_barycentric_coords). Drawing the few trackmarks between the viewer position and Tux' position shouldn't be very expensive.

But when you repeat a game the complete track in the visible area must be drawn. The trackmarks don't replace the normal terrain polygons. First the terrain is completely drawn, then the trackmarks are overlayed in an additional step with blending (very nice, the alpha value is reduced when Tux starts a jump or touches the surface again).

So... do you mean that the track marks become more transparent to "fade out" as Tux jumps off the ground ?

And what do you think is inefficient in the trackmarks rendering ?

Having marks overlaying the surface quads beneath ?
I agree that storing surface triangles and trackmarks separately is inefficient when you repeat a race. It would make more sense to store directly triangles with a texture that is the alpha blending of surface_texture + trackmark. But then, you would have to store special textures, which would be surface_tex + trackmark... besides, for each surface type you would need several of these textures, each of them with different alpha values, to render the "fade out" effect that happens when Tux jumps.

How would you improve the track marks rendering ? In theory, of course...

So... do you mean that the track marks become more transparent to "fade out" as Tux jumps off the ground ?

Yes, a simple trick.The alpha value depends on the distance to the surface.

Having marks overlaying the surface quads beneath ?

Trackmarks quads and surface quads are different things. The surface quads are the result of the mesh triangulation, the trackmarks follow the track. They don't fit to the regular surface grid. See the pic:



I admit, most effort is not to draw the trackmars but to calculate the params. See the single mark on the right. Each mark consists of 12 main params: 4 texture coords (no problem), 4 normals (can be read from an existing array) and 4 vertices. You see that they are on 4 different triangles. The height of each trackmark vertex has to be computed by interpolating the 3 triangle vertices (with barycentrics). All that takes time, much time.

The trackmarks are overlapped, the more the lower the speed. Reason: The textures can't be stretched or compressed at will, that won't look nice. At low speed the marks appear as stripes, and there are gaps between the marks when the speed is very high. Normally, the latter you can't watch because the speed on ground is limited.

Woa.

Thanks Erin, you seem to know a lot about computer graphics, and you still spend time sharing this knowledge with us. I am so grateful.

So... I see now. Then I guess there is not much to do about the track marks...
Just a question : the baricentric elevation of the trackmark vertices is calculated only once, right ? When the track mark is created... since the elevation will depend on the terrain, which is a constant.

I'm back now! (that means i should be able to get this thing released ASAP) I was in Tours, visiting my extended family.

So... I see now. Then I guess there is not much to do about the track marks...

No, at the moment there is nothing to do on the basic code. I've cleaned up the trackmarks code a bit and saw no way to do it better or faster. Nevertheless the code is not perfect, especially the head and tail marks appear not correct. But you don't notice that when racing.

Just a question : the baricentric elevation of the trackmark vertices is calculated only once, right ? When the track mark is created... since the elevation will depend on the terrain, which is a constant.

Yes, only once. In each frame the function add_trackmarks checks if a new mark has to be calculated and stored. There are some conditions for dropout, in this case break_trackmarks () is called. Perhaps this is a starting point for better adjustment to the speed. At the moment it's not important for me. More important is to enable trackmarks for other textures (e.g. mud). That's what I'm working on currently.

But I have some ideas for future development. It's an advantage that the marks are independent from the surface polygons. That allows to store the complete track (or more tracks) of a course in a file. Then the tracks can be reloaded anytime - or not.

Erin, I'd be curious as to what OpenGL programming experience you have. Your analysis, in my limited experience, seems way off.

Modern GPUs can happily handle 100s of 1000s of on screen polygons. The fact that Tux might be made of ~3000 is not a performance killer on anything other than minimal hardware (software rendering). Admittedly he could be drawn more efficiently, but he certainly doesn't have to look worse and can even look better.

Terrain distance should not be shortened either. That's a weak way to get performance. I mean, they were making games in 1996 (e.g. Terra Nova) with near-infinite view distances. Really you want to look at reducing the amount of detail in far-view terrain. Whilst I concede that improving this will take skill and time, reducing the draw distance is a hack and not a solution and will make the game worse since you can't plan ahead when racing unless you know the track inside out.

The particles I can't comment on but again they should be really cheap to create and the direction should be worked out in the cheapest way possible.

I suspect, and I'm tempted to look next week to see, that the performance issues will come down to expensive loops and misunderstood rendering techniques. The actual amount of detail is simply not great enough for that to be the problem; it's the implementation. The fact that you essentially blame the performance on the detail is a very hard pill to swallow. There have been games with way more detail / glitz than ETR for many years.

I'd be curious as to what OpenGL programming experience you have. Your analysis, in my limited experience, seems way off.

I'm sure that my experience with OpenGL programming is more limited than yours. So your objections are occasion to revise my work. Yes, your explanations seem to be well-founded, and perhaps I've estimated something wrong. First I saw the fps display:

use_trackmarks=false and use_particles= false: 95 fps
use_trackmarks=true and use_particles= false: 75 fps
use_trackmarks=true and use_particles= true: 60 fps

Sure, that's fast enough, but the difference! So I compared with Tuxracer 1.1 and found the mentioned limitations. All that seemed to be plausible. But for real evalution my skills might be not sufficient enough. Thank you for giving the important hints. The ETR project really lacks some competent developers. A lot of suggestions but nobody who realizes them. I've tried to do something at least.

Terrain distance should not be shortened either. That's a weak way to get performance. I mean, they were making games in 1996 (e.g. Terra Nova) with near-infinite view distances. Really you want to look at reducing the amount of detail in far-view terrain.

I agree with you that the terrain should be rendered with a far view by using a good quadtree or another LOD algorithm. The problem is the great amount of 3d objects. Take 2000 3D trees, then you have your hundreds of thousands polygons, only for the trees.

the performance issues will come down to expensive loops and misunderstood rendering techniques. The actual amount of detail is simply not great enough for that to be the problem; it's the implementation.

Maybe. There are some details that bear out your supposition. In the particle code I found that the lifetime of each particle is calculated by checking the height position of the surface, a very expensive function. Really necessary?

However, all these questions seem to be obsolete for me since the work on the code doesn't make sense if the project
goes to end. Now CPicon has disappeared, the last one of the project founders. In addition, working alone is not a good condition for being sucessful, there are too many aspects to overlook.

Thank you again, your message was very expressive and helpful.

Firstly, this is open source, the project doesn't end because a founder disappears. Ideally they'll be contactable or be able to maintain/transfer hosting resources (if this place isn't already hosted on Sourceforge).

LODs can get really simple. I'd suggest that you find out what distance a tree is reduced to a few pixels tall, and have an LOD that is simply a single green triangle facing Tux but pointing upwards. (Some form of billboarding technique.) Or alternatively just 2 intersecting green triangles. They are only a few pixels high so it'll not be obvious how basic they are.

You seem to be on the right track with the particles. Make them cheap to create and cheaper to maintain. I'd just give them a vector, a speed, and a lifespan (or distance span) so, once created, they are self contained.

Be patient, be content working on it on your own, just in case you have to, and don't be afraid to ask in forums like this for advice or help:
http://forum.freegamedev.net/

I'll look at the code but I'm not a C++ dev so don't expect anything.

I'm still here, although my free time has been consumed with other projects for the time being. If only I could count working on ETR as a college course.

The fact that you essentially blame the performance on the detail is a very hard pill to swallow. There have been games with way more detail / glitz than ETR for many years.

A good point. I wonder how much of the speed has to do with texture resolution. ETR has some pretty high resolution textures, and loading/drawing those can be ugly.