Degenerate Triangles
I’ve been working on optimising some areas of Sir Lamorak’s Quest. Most recently this has been reviewing the Tiled class. I was until this week only rendering the tiles of the map that were visible on the screen thereby trying to reduce the amount of work the GPU was being asked to do.
During the iPhone conference I had a great conversation with Eric Buck after his talk “OpenGL ES in iPhone Games”. It turns out that I’m trying to compensate for something that the GPU can actually handle all on its own. Eric described the GPU in the iPhone as a “number crunching monster” that can actually process data over 100x faster than the CPU for certain tasks.
I described to him what I was doing for my tile map class and his response was that if I were using Quartz then the approach is valid i.e. reduce the amount of drawing work that needs to be done. For OpenGL ES its very different. OpenGL ES is very very good at being able to identify pixels that are not going to be visible very early on in the graphics pipeline. This allows it to drop them and not have to worry about them.
Based on this info I came home and changed the Tiled class. I now always draw the entire map everyf rame and not worry about what is visible and what is not. I then simple perform a glTranslate on the world coordinates to move my player around the map. Having done this I can report that it works a treat. I have actually seen an increase in performance making these changes and its also simplified my code, which is always a bonus.
The other change I made was to also move from an Interleaved Vertex Array to an Interleaved Vertex Buffer Object to store my vertex, color and texture info for the tiles in the map. As I’m not translating the tile vertices now I’ve been able to set up VBOs for each layer of my map using GL_DRAW_STATIC i.e.
glBufferData(GL_ARRAY_BUFFER, sizeof(TexturedColoredVertex) * verticesCounter, texturedVertices, GL_STATIC_DRAW);
This tells OpenGL ES that I’m going to load the VBO with data and never change it. This helps OpenGL ES optimise the location of that data so that it can feed the GPU, number crunching moster, as fast as possible. It all works really well and I’ve seen a good performance increase at the same time.
I did spend time trying to take it a few steps further by rendering the map using GL_TRIANGLE_STRIP rather than GL_TRIANGLES. This introduced some interesting challenges. Firstly I need to get from the end of a line of tiles to the start of the next line WITHOUT drawing triangles. Hmmm, using a strip I didn’t think this would be possible, but then I came across degenerate triangles. This is a mechanism where you can specify triangles that have two vertices that are the same. OpenGL ES is then able to work out that the triangle will have no volume and doesn’t draw one.
This basically allows you to translate to a new location without drawing triangles. It really messes with your head :o) but I was seeing the most amazing performance increase from doing this. My renderer utilization on an iPhone 3G went from 60% to 25% and I was getting a solid 56-60 FPS with the game in full flow.
This all sounds amazing right, well there was a problem I came across that I’ve not been able to solve and its to do with texture coordinates. As a triangle strip shares its vertices with the previous triangle I was getting really odd issues with my textures. I’ve not yet managed to work out how to sort that out, so I’ve stuck with using VBOs and GL_TRIANGLES, but its something I will revisit at a later date as the performance boost from that change was amazing.
There is also another step I could have taken to increase the speed even more, which would have been to use glDrawElements rather than glDrawArrays. Using elements would have allowed me to simply reference vertices already in the buffer object rather than create new ones for the degenerate triangles, meaning even less data being needed. But I’ll leave that to another day :o)
Anyway, I thought I would share as I found the exercise really interesting. I do need to thank Tom Bradley, the author of TBXML, who was up with me until the early hours of the morning exploring degenerate triangles and how to get them working for the tile map. His help stopped me getting a nose bleed from all the thinking I was doing.
Check out GL_TRIANGLE_STRIPS and degenerate triangles. Really clever stuff but it may make your head hurt.
Mike
7 Comments
kingbombs on October 28th, 2009
Ok so i may be completly wrong in what i am about to say. But:
If you have an if statement lets say that checks to see if the object you might want to draw is outside the boundaries of your current view, and if it is it won’t do anything.
If it is in the boundaries of your current view then you will enter the loop and bind the vertex data and draw the vertex’s.
Surley if that if statement isnt there you will be wasting time by binding the vertex data and then drawing the vertex?
Even if the GPU goes through the program and doesn’t draw what isn’t on the screen surley you will have wasted alot more time by binding the vertex data than the time to do one if statement check?
I see you said this is for your tile class, but im just checking because maybe for your tile class your current method would work well where it may be difficult to check an individual tile but for units (creatures, character) where you may know there x,y co-ordinate you could do an if statement on the current view and there position to see if they need to be left out. And i would assume this would be alot faster than what you have currently said.
I’m just saying this incase you turn round and prove me wrong and i learn something :D
But i am expecting you to say “It’s just for the tile class” if so then it’s an awesome technique to use.
mike on October 28th, 2009
Hi Kingbombs
You make an interesting observation and its the same one I had used when I was not rendering tiles that would not be seen. For my entities, I’m also not checking to see if they are visible or not. I was doing this from the start with my entities because of the way I am spawning them.
I wanted the player to always have baddies around him to deal with, but I didn’t want to have to fill my map with baddies. My solution was to get the entities to check how far away they are in tiles from the player. If this exceeds a certain distance then the entity changes state to dead and my spawning code then picks it up again and spawns it again near the player.
This means I can give the player a hard time with only 5 entities in the entire game :o). Imagine the player is walking about surrounded by a swarm of flies moving with him. That is how my entities are working.
This has been working well and means I’ve not been checking if they are on screen or not as if they aren’t on screen, its not for long and with so few entities it does not add any overhead at all really.
At the moment I’m not sure that the method I described in the post would work well for dynamic entities such as baddies as they are changing all the time. But for anything that is static i.e. its location is defined by changing the world coordinates and not its own vertices then the solution works well.
For the tile class, as you say, this is a perfect fit as I’m never changing the tile vertices themselves :o)
I hope that makes sense.
Mike
kingbombs on October 28th, 2009
i found these two links on degenerate triangles useful to understand them:
http://www.gamedev.net/referen.....le1871.asp
http://www.gamedev.net/communi....._id=169988
what were the issues with the textures?
I would assume your texture you are applying to the tile’s will get the one texture stretched across all the tiles at once?
Btw just to note for my above post, I am making quite a different game to your tutorials i more read the code to see the OO approach you take :D
so how i do things may not apply to yor game :)
kingbombs on October 28th, 2009
Just read the post, your reply is pretty much what i thought you might say.
“This means I can give the player a hard time with only 5 entities in the entire game”
Always nice to see a good design approach pay off for a developer :D
Simon on October 28th, 2009
Hi Mike,
Only just got my head round the “Tile Map” tutorial and if you struggled, I’m probably not going to try GL_TRIANGLE_STRIPS… just yet.
Appreciate the update and will definitely check this out on my next project. Thankfully my current game doesn’t use the a Tile map so that performance issue is one I can avoid (for now).
Simon
SeanCP on October 30th, 2009
Hi Mike,
(Tried to find an e-mail for you somewhere but I couldn’t. Please delete this later)
Because too many quality blog entries on development are lost in the vastness of the web, Code Project is bringing together the best to give them the exposure they deserve. Code Project has 6.5 million members browsing 26,200 articles, each article having hundreds of views daily.
I’ve been looking at your blog and there are some phenomenal entries (like this one) that we’d love to have on Code Project.
Just blog away, and a version of whatever entries you choose will appear on Code Project as well with a link back to your entry on your blog.
I’d be happy to give you the details (http://www.codeproject.com/scr.....ogFAQ.aspx), or answer any questions you might have.
Thanks,
Sean Ewington
Content Manager
The Code Project
Tony on October 28th, 2009
This sounds amazing! I’ll have to find time to look into strips and degenerate triangles.
Thanks,
Tony