3D Tile Rendering

This is a discussion on 3D Tile Rendering within the Game Programming forums, part of the General Programming Boards category; I am thinking about making a game that stores its world map in a 3 dimensional array and it renders ...

  1. #1
    Registered User
    Join Date
    Jun 2011
    Posts
    8

    3D Tile Rendering

    I am thinking about making a game that stores its world map in a 3 dimensional array and it renders the tiles to screen using OpenGL. This is fine, however when I draw things to the screen, I do NOT wish to simply brute force my way through the entire set of tiles and draw each of them on screen.

    The only problem is that there are so many variables involved, I have no idea how I should deal with this.

    1 - Render distance - While obviously rendering as far away as possible would be ideal, it would be highly impractical to simply allow the game to load as much of the world as it likes and render as much as it wants. How should I limit how much of the world I'd like to show? Should it just be an arbitrary preset distance or is there some sort of calculation I should be able to make?

    2 - Running time - Even if I only rendered a simple 10x10x10 area, this would still require me to run a for loop through and draw 1000 blocks. Even if I give them variables that say which sides are definitely hidden by other blocks and stop it from drawing the inside blocks, I still have to iterate through them and this sounds like it could get slow, fast, especially if I want to draw any reasonably far distance. Is there some algorithm I could use that would only iterate through blocks that are actually drawable?

    3 - Blocks that are behind other blocks - Is there any really fast way of determining what blocks are hidden from the camera behind other blocks and not drawing them? Would it be okay to just let OpenGL do this for me? Would it be okay not to worry about it at all?

    Of course I may be looking at this entirely the wrong way, so your people's expertise on this subject would be greatly appreciated.

  2. #2
    Programming Wraith GReaper's Avatar
    Join Date
    Apr 2009
    Location
    Greece
    Posts
    1,624
    What you're suggesting isnot a good idea! 3D arrays can grow very-very much in size, thus eating up your memory very soon and requiring very high-speed CPU to be traversed. Consider a scene renderer using hierarchical placement of data ( World => Continent => Country => City => House => Object etc ).
    Devoted my life to programming...

  3. #3
    Registered User
    Join Date
    Jun 2011
    Posts
    8
    Could that be used to emulate the same thing?

  4. #4
    Super Moderator VirtualAce's Avatar
    Join Date
    Aug 2001
    Posts
    9,596
    Even if I only rendered a simple 10x10x10 area, this would still require me to run a for loop through and draw 1000 blocks
    Then clearly the brute force approach will not work.

    Think about the problem for a second and you will come up with a better approach. I'll give you a few hints as to one approach:

    • Don't draw 1000 blocks but rather width * height primitives textured to appear like individual blocks.
    • Use tiled U,V coords to your advantage
    • A quad-tree for the blocks may work if you only draw 1 level of blocks
    • Think of the world as columns of blocks
    • If all textures in one column are the same then you can draw 1 primitive as tall as the column but make it appear as if there are hundreds of individual blocks
    • Worst case scenario is when all textures of all blocks in one column are different - and this most likely will never happen


    Block occlusion can be minimized by drawing front to back. In this manner any blocks that are in front of other blocks will be rendered first and as such will put Z coords in the zbuffer that will cause the more distant blocks to fail the zbuffer test. This is an optimization at the zbuffer level and may or may not help. A better optimization would be to compute which blocks are occluded by other blocks based on the current view. Having said all that I honestly believe that block occlusion is the least of your worries.

    The trick is not to draw all of the blocks but make it appear as if you did. Here are some screenshots of a very simple and primitive system I built some time ago based on the above premises. It uses Direct3D but the concept is the same. It uses a brute force O(n) algorithm to draw the blocks (which are columns) and a quad-tree approach would certainly speed this up.
    Last edited by VirtualAce; 06-17-2011 at 04:39 PM.

  5. #5
    Registered User
    Join Date
    Jun 2011
    Posts
    8
    Thank you. That is a very interesting idea. How would I deal with things like caverns or floating blocks or if there are two separate kinds of blocks in one column? Would I just simply have each tile not record the height but instead a list of heights indicating where each chunk is?

  6. #6
    Super Moderator VirtualAce's Avatar
    Join Date
    Aug 2001
    Posts
    9,596
    Well if you think as each column as a series of 1's and 0's then caverns become quite simple. It is no different than a 2D tile engine or perhaps a maze program where a 1 represents a filled area of the maze and a 0 represents an empty area. Also if you are on top of the columns then you would not have to draw the entire column since the eye would never be able to see them. You only have to draw down far enough in the column to make it appear as if you are walking on a bunch of blocks.

    One column could be represented like this in memory:

    Bottom -> 1,1,1,1,0,0,0,0,1,1,1,1,0,0,0,1,1,1,1,1,1,0,0,0,1, 1,1,1,1,1,1,1,1,1,1,1 -> Top
    So starting from the top down you would draw a primitive that was 12 blocks high,3 empty slots, etc., etc. To optimize this so you don't have to draw the entire column you only need to check to see if the neighbor columns are higher than or as high as your current block. If all neighbors are then you can safely stop drawing down into the column b/c the camera on the surface will never see the blocks. Likewise if you are in a cavern you only need to draw based on the heights of neighboring columns at the 'depth' of the camera. There is no need to draw and transform all the primitives when you cannot see 95% of them.

    Given the right optimizations and drawing algorithms you could easily draw an entire landscape of blocks with little trouble.

    If you use a quad-tree this will cull out the areas of the block terrain that you cannot see. If you then use the height algorithm there is yet one more optimization. Since you know the position of the camera and you know the position of the block you can create a vector from the camera to the block. Only neighboring columns that fall in line with this vector (given a certain fudge factor) need to be height checked. This means you do not have to check all 8 neighbors when drawing each column.

    To create blocks within a quad-tree:
    • Decide on the total size of the root node
    • Split the node vertically and horizontally until the desired size is reached and save off the world boundaries of the node within the node
    • Add all the columns that are in this node (within the bounds of the node) to a render list in the node and set the node to a leaf node


    During rendering:
    • If any node at any level is completely out of the frustum, then all its children are too and need not be checked
    • If any node at any level is completely within the frustum, then all its children are in to and need not be checked
    • If any node at any level is halfway within the frustum and halfway out, drill down to its children and perform the same frustum test and repeat the tests


    So now given these optimizations you are no longer rendering the entire grid of columns but instead are rendering only the columns that are within the frustum...or within view. If you implement the height optimization to determine how many primitives to draw for each column you are now only drawing a very few number of primitives per column. Given these optimizations your new blocky tiled terrain type system should be blazing fast.

    I achieved a large speed increase by cheating on the columns. I pre-created columns that were from 1 block to 256 blocks high. At run time I simply picked a mesh from the vector based on the height of the current column or current segment in the column and rendered it at the current y position of the 'cursor' that was being used to draw the column. The cursor starts at the top of the column or at y = blockHeight * columnHeight. You may wonder why I chose 0.0f as the base of the column. This was simply to make the height calculations much simpler but you can move the entire system back to being centered around 0.0f,0.0f,0.0f via a simple pre-translation matrix. Note that if you use HLSL or GLSL you should be able to instance blocks and/or change their height within the shader code which means you would only need 1 cube mesh in memory at any one time. Note that you can also instance blocks by creating a frame class that handles orientation and scale. You would create 1 mesh and use different frame scales to create taller columns of blocks. You would need to alter the u,v's to simulate several blocks. Remember that the u coordinate will be from 0.0f to 1.0f but the v coordinate will be equal to the number of blocks in the column and you must set the texture addressing mode to wrap on v. So a column with 5 blocks in it would be a 5 * blockHeight cube with a v coordinate of 5 at the top or bottom end of the cube. Again if you use shaders then you can change the v coordinate in the shader by passing in a float that is the unit height of the column.
    Last edited by VirtualAce; 06-18-2011 at 01:15 AM.

  7. #7
    Super Moderator VirtualAce's Avatar
    Join Date
    Aug 2001
    Posts
    9,596
    So I'm interested to hear what you have done since the last few posts. Any progress on the rendering? Any new tricks you've discovered or new algorithms that will enable you to render as fast as you want, as far as you want, and with the quality you want?

  8. #8
    Registered User
    Join Date
    Jun 2011
    Posts
    8
    Well I have been working on other things atm, right now my ideas are just theoretical, though I plan on actually trying them out in a project soon. But your help has been very much appreciated, and I have bookmarked this thread for future reference.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Super fast tile rendering/scrolling in D3D
    By VirtualAce in forum Game Programming
    Replies: 7
    Last Post: 09-21-2006, 05:53 AM
  2. Tile-map performance
    By VirtualAce in forum Game Programming
    Replies: 41
    Last Post: 04-19-2006, 10:55 PM
  3. Tile help
    By MadCow257 in forum Game Programming
    Replies: 3
    Last Post: 09-10-2005, 08:30 PM
  4. Tile engines
    By Stray_Bullet in forum Game Programming
    Replies: 7
    Last Post: 03-21-2002, 07:12 PM
  5. Tile Editor
    By Nick in forum Linux Programming
    Replies: 3
    Last Post: 08-10-2001, 11:24 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21