Archived

This topic is now archived and is closed to further replies.

Outworlder

Optimizing 3D tile engine

Recommended Posts

I''ve started coding the 3D engine and I''ve need of some optimizations, because it''s running too slow. I guess the main slowdown is that it is drawing unnecessary tiles, so I think what I need is some hidden surface removal algorithm, though I do not know which one to use in this case. The terrain can be rotated(almost exclusively on the Y axis). Another question: I''m using a glPush(), glPop() pair for each of the "tiles"(they are actually cubes) and a translation. Is it the best approach or should I just change vertex coordinates? Here''s one screenshot(Fog removed; those bright dot''s are supposed to be rain ) The terrain is randomly generated: http://www.gaiomard.hpg.ig.com.br/map2.jpg And there''s a screenshot before I added height: http://www.gaiomard.hpg.ig.com.br/map.jpg Gaiomard Dragon -===(UDIC)===-

Share this post


Link to post
Share on other sites
Are you using any 2D arrays? Try changing them to 1D, then use pointer incrementing. Here''s an example:
  
// Unoptimized

something **Tiles = ...;
for(int x=0; x<width; x++) {
for(int y=0; y<height; y++) {
render(&Tiles[x][y]);
}
}
// Somewhat Optimized

something *Tiles = ...;
something *Cur = &Tile[0];
int max = width*height;
for(int a=0; a<max; a++, Cur++) {
render(Cur);
}
// More optimized

something *Tiles = ...;
something *Cur = &Tile[0];
for(something *Last = &Tile[width * height]; (unsigned)Cur<(unsigned)Last; Cur++) {
render(Cur);
}

But, in the end, the loop style makes only a TINY difference compared to other things you''re doing (or not doing), like occlusion.

quote:

Another question: I''m using a glPush(), glPop() pair for each of the "tiles"(they are actually cubes) and a translation. Is it the best approach or should I just change vertex coordinates?


Think of it this way: Is it easier to do (a) ~24 floating point additions or (b) 2 stack changes and one matrix multiplication? If you''re still unsure, prove the answer to yourself through a test.

[Resist Windows XP''s Invasive Production Activation Technology!]

Share this post


Link to post
Share on other sites
Yes, I am. As matter of fact, the data structure is a little more complicated than that. Any given X,Y position in the map can have any number of tiles stacked on top of it.

So:

  
class MapTile {
public:
int Terrain;
int Object;
int NPC;
MapTile * Next;
void DisplayTile(CMap* map);
inline MapTile();
inline ~MapTile();
};

class CMap: public CRendered {
private:
MapTile** MapArray;
CTextureNode* Textures;
int NumTextures;
int Resolutionx,Resolutiony;
int TamX,TamY;
public:
void InitMap();
void DrawMap();
inline CMap(int tamx, int tamy);
inline ~CMap();
int GetTamX() { return TamX;}
int GetTamY() { return TamY;}
void InitTextureTable(int num);
void AddTexture(int num, char* name);
bool IsLoaded(int num);
TextureImage* GetTexture(int num);
void CreateRandomMap();
void Update(float Delta) {};
void Draw() {
DrawMap();
}
};



This linked list on each map position is probably slowing things down a bit. But I believe the slowdown is caused by not using occlusion, for example. The problem is, I''m not sure how to implement them, and what algorithm to use.

Gaiomard Dragon
-===(UDIC)===-

Share this post


Link to post
Share on other sites
Well, an octree or quadtree is most often used in a position like yours (I''d go with the octree), but it only helps if a majority of the tiles are offscreen. Are you sure you really need to render every tile that is stacked like that? Maybe you should do it highmap-ish and only use the top tile?

[Resist Windows XP''s Invasive Production Activation Technology!]

Share this post


Link to post
Share on other sites
Hmm... good suggestion. I was thinking about doing a heightmap myself. Those stacked tiles are used in Final Fantasy Tactics, Ogre Tactics and some similar titles(and lego toys ). Since the engine will be for a similar game, they came into mind first. But, if I can generate all the types of terrain I want, using only heighmaps, I''ll go with them.

Time for some serious testing...

Gaiomard Dragon
-===(UDIC)===-

Share this post


Link to post
Share on other sites
As your map gets bigger than one screen, you will need to cull out sthe stuff that's not in the view frustrum.

A suggested way to go about it.

I am assuming that the map is made up of regular tiles in the X & Z axis

After creating or loading the map, run a routine that creates a quad tree structure for the map.

Now, in each quadtree node, store a cube (just 2 3d points) that represent the smallest cube that contains all the map tiles inside it. I.e., the max and min x, y, z coords for all the geometry inside it. Recurse this down to a 2x2 or 1x2 tile size for the smalles nodes in the quadtree.

Now, note that we are storing 3d cubes inside of a 2d- quad tree.. this is a convience because we know the map is mostly concerned with spawling in the 2d sense.


Now what you have to do this: Create a function that takes one of these cubes stored in the quadtree, creates the 6 rectangular faces of the cube from the 2 actual coordinates, and then tests to see if each cube poly is fully in the current view frusturm, partially in (clipped by) the view frustrum, or completely outside the view frustrum.

This tells you if the tiles inside that cube are to be always drawn (fully inside), not drawn at all (fully outside), or if you need to check the next lower level of quad tree because some are inside and some are not.

  
enum {cOutsideFrustrum = 0, cPartiallyInside, cFullyInside};

void MyRenderer::renderWorld()
{

MapQuadTreeNode* currentNode = world->getBoundingQuadtree()->GetRootNode;
long RootClipHint = ClipCubeToFrustrum(currentNode);

if (RootClipHint == cOutsideFrustrum) // Nothing to Draw at all?

return;

if (RootClipHint == cFullyInside) // Everything visible?

{
DrawAllTilesInNode(currentNode);
return;
}

// Hmm, only part of the map can been seen.. let's find out

// which parts we want to draw


RenderWorldChildNodes(currentNode)

}

void MyRenderer::RenderWorldChildNodes(MapQuadTreeNode *parentNode)
{

// Is this the bottom node?? then we render it because

// we are only called if we know that some of the tiles

// we contained are visible on the screen


if (parentNode->hasChildNodes == false)
{
DrawAllTilesInNode(parentNode);
return;
}

MapQuadTreeNode *ChildNode;
long ClipHint;

// ----------------------------------

// Process the upper left child node


ChildNode = parentNode->getUpperLeftChild();
ClipHint = ClipCubeToFrustrum(ChildNode);

// Is everything on screen?


if (ClipHint == cFullyInside) // Everything visible?

{
DrawAllTilesInNode(ChildNode);
}

// Is it only partially on screen?

// The recurse down and check its sub nodes


if (ClipHint == cPartiallyInside)
{
RenderWorldChildNodes(currentNode);
}

// If it is not visible (cOutsideFrustrum), then

// We do nothing :-)


// ----------------------------------

// Process the upper right child node


ChildNode = parentNode->getUpperRightChild();
ClipHint = ClipCubeToFrustrum(ChildNode);

// Is everything on screen?


if (ClipHint == cFullyInside) // Everything visible?

{
DrawAllTilesInNode(ChildNode);
}

// Is it only partially on screen?

// The recurse down and check its sub nodes


if (ClipHint == cPartiallyInside)
{
RenderWorldChildNodes(currentNode);
}

// If it is not visible (cOutsideFrustrum), then

// We do nothing :-)


// ----------------------------------

// And repeat for lower left and right nodes...


... code goes here ... exercuise for the reader ...

}


The end result is that quadtree lets you quickly determine which portions of the map are "on screen" by testing large portions of the map first to see if they are visible, then drilling down wherever the answer is "partially visible".


-Matt P
Developer AoE/AoK/???







Edited by - The Optimizer on October 20, 2001 12:37:53 AM

Share this post


Link to post
Share on other sites