13 replies to this topic

[tneva82]

Probably there's lot better methods but this should be sufficient for my needs now and be likely lot easier to implement than say octrees. Anyway I have terrain. Camera follows character in point X from upward like this. Terrain is formed of x*y amount of tiles(you can see how many there...Have to figure out a way to remove those edges). Now I would like to know how to limit up area drawn. Preferably simple since this isn't primary concern for now and need to get this thing done fast. So I figured I would simply limit to smallest rectangle possible from camera's terrain piece(which I know) and determine from there bottom-left and top-right corners and draw it in simple for loop. Not perfect but since my graphics aren't state of the art(as the screenshot shows :D I ain't artist!) should ensure there's no FPS issues. ...But how to do that? First attempts with that resulted in total haywire results until I simply gave up and drew out fixed amount to each direction until I got enough but now would like to improve on that. So any pointers how to aproach this? I know screen resolution, viewangle, camera position and terrain piece size. Now I would need to figure out bottom-left and top-right corners based on angle of character(and ergo camera since camera is ATM fixed at following character. I'll worry about moving camera when primary goal is archieved). Also on another issue if I need to determine height of the terrain character is standing(or is moving) that would be collision check right? Darn. Atleast there's only limited number of polygons to compare thanks to ground being formed of smaller pieces. Guess it shouldn't take that much to check it for ~2 dozen or less polygons max.

[Erik Rufelt]

I assume this is OpenGL?
You can use the gluUnproject function to get a 3d-point from a 2d-point, at some distance from the screen. Use this to get 2 points, for each of your 4 corners of the screen, one with a close distance and one with a further distance. Then for each corner you have two points, p0 and p1.
Calculate the vector v = p1 - p0, which will point in the direction of the camera view at that corner pixel. Normalize this vector.
Now you have a direction, which combined with your camera-point 'c' makes a ray. Calculate where this ray hits the ground plane.
You have the following formula for every point in the ray direction:
p = c + v * t, vector math, each component is calculated the same way, so for y:
p.y = c.y + v.y * t
If the ground plane is at y = 0, and we want to know when we hit it, we set the left side to 0, and solve for t
0 = c.y + v.y * t
t = -c.y / v.y
And now you know 't', and can calculate the actual point at which you hit the ground with p = c + v * t, and you get p.x and p.z (p.y is 0 as stated before, since y = 0 is where we hit the plane).
Do this for each of the 4 corners, and you have 4 x/z values. Loop over them and find the minimum and the maximum x and z values.
Once you have those, you have a rectangle which encloses all the tiles you see. Divide this by the tile-size to get a rect in what indexes to draw.
You might want to add 1 or 2 to that in each direction, if you notice you don't see the edges. It depends on how you round the numbers to integers and how exact the calculations are.

Depending on how familiar you are with vector-math, this might be very easy or quite complicated. Reply again if you need more specific help.

[Erik Rufelt]

For your second issue, with the height, the easiest is probably to do a simple bilinear interpolation of the height values. If you have a 2D heightmap with the heights for each point, take the 4 corner points at the tile the character center is, and then bilinear filter between those points.
This is also very easy if you know how, check http://en.wikipedia.org/wiki/Bilinear_interpolation for example. The explanation there is not too good though.. but Google for bilinear interpolation and you will find a lot of information. Post again if you need more help with that too. =)

[tneva82]

Quote:

Original post by Erik Rufelt I assume this is OpenGL?

Yup. OpenGL.

Quote:

Depending on how familiar you are with vector-math, this might be very easy or quite complicated. Reply again if you need more specific help.

Very complicated but I'll try to mul over this and see if I can make it work!

[tneva82]

Quote:

Original post by Erik Rufelt For your second issue, with the height, the easiest is probably to do a simple bilinear interpolation of the height values. If you have a 2D heightmap with the heights for each point, take the 4 corner points at the tile the character center is, and then bilinear filter between those points.

No I don't have heightmap since I ran into tons of errors and in the end decided that with my artistic skills getting anywhere near decent heightmaps is beyond my abilities anyway. What I have is basicly library of terrain tiles and then map composed of terrain pieces which have a) object ID(refers to the tile library. Essentially pointer to object in code) b) texture ID(again we have whole bunch of textures which are shared by multiple terrain pieces) c) height(refering to height terrain is rendered at. Allows same piece used for several different heights. Say top of hill) d) direction(so one can use same terrain piece/texture for 4 different directions).

More akin to 2d tile based game but works for me. Top of these I will be adding objects(buildings, trees etc). So all I know from each terrain piece is the polygons it's composed of. Good thing is that the small piece isn't likely to be polygon heavy so there's only limited number of them.

[Erik Rufelt]

I decided to make some images for you, to explain what I was talking about in my first reply. Might help someone else too, I've seen this come up before, and realize it can be hard to visualize unless one is experienced in 3D.
Consider the following view of a tiled ground plane:


If we pick the 4 corner-pixels at the edges of that image, and draw lines out from the camera in those directions it will look something like below, the gray box is the camera, the lines are the very furthest out corners of what the camera can see:


If we trace these lines to the ground-plane, they will hit and form a shape as follows:


Now mark the tiles where the corners hit:


Then create the smallest rectangle that contains all those 4 corner tiles. It can be done by checking each of those 4 tiles, and taking the minimum of the tile-coordinates as left/top of the rect, and the maximum as right/bottom.


Then draw only those tiles.

In order to perform these steps, you need to calculate the 4 points where the corner-lines hit the ground plane. This can be done as follows:

First you need to get some information from OpenGL. You need to know your camera and projection matrices, to calculate what directions the lines go in, and you need to know the size of the view-port to use the gluUnProject function to obtain those lines. The information is obtained from OpenGL like this:

GLdouble model[16];
GLdouble proj[16];
GLint view[4];

glGetDoublev(GL_MODELVIEW_MATRIX, model);
glGetDoublev(GL_PROJECTION_MATRIX, proj);
glGetIntegerv(GL_VIEWPORT, view);

'model' and 'proj' will contain the matrices. 'view' will contain the screen coordinates of the view area. view[0] is left, view[1] is top, view[2] is width, view[3] is height.

The gluUnProject function calculates a point in 3D, at one pixel on the screen, by moving a certain specified distance in the direction of that pixel. To get our actual lines, we take one such point at a close distance, and another point on the same pixel, but further away. The line between these two points now point away from the camera, in the direction of that pixel.

You do this in code like this, for the direction of the top/left corner pixel:

vec3d p0, p1;
gluUnProject(view[0], view[1], 0.1, model, proj, view, &p0.x, &p0.y, &p0.z);
gluUnProject(view[0], view[1], 0.5, model, proj, view, &p1.x, &p1.y, &p1.z);

p0 and p1 are now our two points, p1 is further away.

Now to calculate the point where this line hits the ground-plane. This is written with vector math. If you don't have a vector class, you can calculate the x/y/z coordinates each on it's own instead, but it's shorter like this:

vec3d c = vec3d(cameraX, cameraY, cameraZ);
vec3d v = normalize(p1 - p0);
double t = -c.y / v.y;
vec3d p = c + (v * t);

'p' is now the point where this line hits the ground-plane. Then you do the same for each of the four corners. The pixel-positions for gluUnProject are:
Top-left: view[0], view[1]
Top-right: view[0]+view[2]-1, view[1]
Bottom-left: view[0], view[1]+view[3]-1
Bottom-right: view[0]+view[2]-1, view[1]+view[3]-1

That should be everything.. =)

[tneva82]

Quote:

Original post by Erik Rufelt That should be everything.. =)

Thanks. More than I bargained! Only one issue. Maybe error in my attempt but atleast in some occasions v.y seems to be 0 which results in divide by 0. What should t be in that case? 1? 0? Infinite isn't precicely good idea.

I'll play around with some numbers but if that fails maybe you could answer that part still.

edit: urgh. I'm just plain stupid! Forget that. Thanks for the help. Now I have the co-ordinates. Now I just need to sort it out + extend drawing graphics past sector I'm in(map is split into multiple sectors of which only part is in memory at the same time. ATM I just draw the sector character starts with. I need to extend drawing past that if required + add code for character moving between sector and dropping and loading of sectors).

Hmm. Still not sure of results. corners are:

x1: -16 z1: -28
x2: 12 z2: -28
x3: 12 z3: 25
x4: -16 z4: 25

and camera is located at -1, -1, What's the area I would need to draw? It couldn't be -16->13 in X angle and -28->26 in Z angle now can it? That would be area of 29*54 which seems "bit" weird and there's certainly not room for that many pieces in the screen. I count that 22*22 in that angle that should cover with. Maybe I'm not understanding quite right what those corner numbers mean...

Edit: What's the reference point regarding those corners? Ie what's the 0,0 point? Or even more specifically how are these related to terrain piece camera stands(or alternatively where character stands)?

Edit: Now I'm running into problems with drawing pieces of terrain from other sectors that happen to lie inside camera view. Problem is that on one side there's sector from each corner that isn't drawn. Pretty strange since I don't think it should even be possible for more than 4 sectors be drawn(atleast with current drawn area) and it loops through 4 sectors allright(standing in corner as it does).

Here's bit of code:

void sector::draw(int index, int leftX, int rightX, int bottomZ, int topZ, float xOffSet, float zOffSet, vector<sector*> *sectorMap) {
  printf("index: %i\n", index);
  printf("draw area: leftX: %i rightX: %i bottomZ: %i topZ: %i\n", leftX, rightX, bottomZ, topZ);
  int cutLeftX=leftX, cutRightX=rightX, cutBottomZ=bottomZ, cutTopZ=topZ;

  if(rightX>width) {
    int newIndex=index+1;
    if(sectorMap->at(newIndex)!=NULL) {
      sectorMap->at(newIndex)->draw(newIndex, 0, rightX-width, bottomZ, topZ, width*BLOCK_LENGHT, 0, sectorMap);
    } else printf("oops! NULL sector about to be drawn!\n");
    cutRightX=width;
  }

  if(leftX<0) {
    int newIndex=index-1;
    if(sectorMap->at(newIndex)!=NULL) {
      sectorMap->at(newIndex)->draw(newIndex, leftX+width, width, bottomZ, topZ, -width*BLOCK_LENGHT, 0, sectorMap);
    } else printf("oops! NULL sector about to be drawn!\n");
    cutLeftX=0;
  }

  if(topZ>height) {
    int newIndex=index+BLOCKS_IN_MEMORY;
    if(sectorMap->at(newIndex)!=NULL) {
      sectorMap->at(newIndex)->draw(newIndex, cutLeftX, cutRightX, 0, topZ-height, 0, height*BLOCK_LENGHT, sectorMap);
    } else printf("oops! NULL sector about to be drawn!\n");
    cutTopZ=height;
  }

  if(bottomZ<0) {
    int newIndex=index-BLOCKS_IN_MEMORY;

    if(sectorMap->at(newIndex)!=NULL) {
    
      sectorMap->at(newIndex)->draw(newIndex, cutLeftX, cutRightX, bottomZ+height, height, 0, -height*BLOCK_LENGHT, sectorMap);
    } else printf("oops! NULL sector about to be drawn!\n");
    cutBottomZ=0;
  }


  glPushMatrix();
  glTranslatef(xOffSet, 0, zOffSet);

  for(int z=cutBottomZ;z<cutTopZ;z++) {
    for(int x=cutLeftX;x<cutRightX;x++) {
      pieces[x+z*width]->draw();

    }
  }

  glPopMatrix();
}

As can be seen it's recursive function initialised by world class containing all of sectors. It starts up with sector player is in and checks wether drawn area(in terms of terrain pieces) goes over sectors boundaries. If it does it calls adjacent sector(which is why I give out pointer to the sector list. Alternative would be to give each sector pointers to neighbour sectors but would become nightmare as sectors get loaded and dropped from memory). Plan is to send to left or right everything that is past them and then for bottom or up cut the x-area to be within limits of sector. This should(if I haven't gone totally off with my logic) take care of situation where we are in corner.

However this goes haywire. Note that it isn't because of being on the edge of world(ie 0,0 sector) as it loads in that case sector from opposite edge(so essentially once I have sector loading/unloading I can run in circles. Not realistic if you think world as a globe but what the heck. Sufficient for me). There is block in that black area since I haven't moved(since the sector loading/unloading isn't done).

So basicly: If I have X*Y array of sectors each composed of width*height terrain pieces and I have draw area of leftX, rightX, bottomZ, topZ how to draw that draw area from those sectors. My attempt above works almost but not quite.

[Edited by - tneva82 on April 14, 2009 7:03:15 AM]

[Erik Rufelt]

Do you divide corner coordinates by sector-dimensions?

Since you use the camera-position and view matrix in the calculations, the coordinates will be 'global', that is relative (0,0,0). You don't need to consider the camera position after the calculations, it will be factored in.

Do you need to have your areas recursive?
If you load all the areas into memory at the same time, it would probably be easier to have a 2d-array of them, like this:

array2d mapSectors(width, height);
float sectorWidth, sectorHeight;

Then you calculate your corner points, and get the minimum/maximum of x and z, and continue like this:

int xfirst = minx / sectorWidth;
int xlast = maxx / sectorWidth;
int yfirst = miny / sectorHeight;
int ylast = maxy / sectorHeight;

xfirst = max(0, xfirst);
yfirst = max(0, yfirst);
xlast = min(width-1, xlast);
ylast = min(height-1, ylast);

for(int i=yfirst;i<=ylast;i++) {
 for(int j=xfirst;j<=xlast;j++) {
  mapSectors(j, i).draw();
 }
}

It should work the same way with your drawing method though, if you just keep track of the x/z index of every sector. Is this what you are doing?

This is assuming that the map starts at (0,0,0). If it doesn't, you also need to subtract the global 'mapLeft' and 'mapTop' from the coordinates first, to have them relative the point where map-sector 0,0 starts. Then you can just clamp (xfirst,yfirst) to (0,0), and (xlast,ylast) to (width-1,height-1), thus ensuring you will never try to draw outside your array of sectors.

[tneva82]

Quote:

Original post by Erik Rufelt Do you divide corner coordinates by sector-dimensions?

Um sector dimensions? Or terrain piece dimension? Sector is 32x32 tiles each 2 openGL unit's long(both width and height). Do I divide it by 32, 2 or 64 then? (actually I think 2 is only thing sensible. ATM it gives area of ~50x53 or since I have divided by 2 ~100*100. Divide it by 32 and there's definetly not enough terrain pieces...But now it's giving me way too high results. No way I need to draw -16, -28->12, 25 area! That's way too big! ATM I'm drawing 22*22 area and it doesn't run too low).

x1: -16 z1: -28
x2: 12 z2: -28
x3: 12 z3: 25
x4: -16 z4: 25

Quote:

Since you use the camera-position and view matrix in the calculations, the coordinates will be 'global', that is relative (0,0,0). You don't need to consider the camera position after the calculations, it will be factored in.

So if I have character in tile X*Y in sector Z from where to where I would be dividing it?

Quote:

Do you need to have your areas recursive? If you load all the areas into memory at the same time, it would probably be easier to have a 2d-array of them, like this: array2d mapSectors(width, height); float sectorWidth, sectorHeight;

How to replace parts of terrain as new sectors are loaded though? That would be tons of variables to be shifted. Guess I could do that but seems it would be slower(=smaller FPS) than altering sector array(~25 sectors in 5x5 grid here).

Quote:

This is assuming that the map starts at (0,0,0).

Pretty much yeah. I have sector 0,0->x,y sectors each of x*y terrain pieces. However when drawing the sector player is in acts as 0,0(y is always 0 for terrain) with x and y offsets being tossed around for glTranslatef command.

[Erik Rufelt]

The corner-coordinates are in world OpenGL coordinates. You never want to cull tiles, just sectors right?
That is, if you draw a sector, you draw a complete sector, you never draw half the tiles in a sector. If that is the case, you divide by 64, the OpenGL coordinate size of the sector (if xOffset is 64.0f for sector index 1 in the x-direction).
That way you get how many sectors from 0 the point is in. If the left point is 45, this will be (int)(45.0 / 64.0), which will be 0. This is correct, you need to draw sector 0 in that case, since the point is within sector 0. If the right coordinate is 65, it will be (int)(65.0 / 64.0), which is 1. This is also correct, since a part of sector 1 will then be visible, and will therefore need to be drawn.
To decide if a sector is drawn you can do the following:

if(leftX <= maxX && topZ <= maxZ && rightX >= minX && bottomZ >= minZ) {
 draw();
}

left/top/right/bottom are the sector-edge coordinates.
Those coordinates have to be in the same coordinate space. Do you use any other matrix operations besides glTranslatef() when drawing?
If you use glScale or something that could mess things up. When calculating the corner points your camera should be positioned and ready in world-space, and you also need to compare the sectors with the same coordinates.

If you look at the third image in my post above, it shows a red area on the ground. This area is the exact area visible by the camera at the position of the gray box. If the camera is moved there, exactly the red area and nothing else is shown on screen. Consider each 'tile' here one 'sector', not one tile within a sector. It is the same thing, if you draw based on sectors. So every sector touched by any of the red area must be drawn, while all others will be invisible anyway.
It is possible to check this exactly, and not have a rectangle draw area, but the easier way, and possibly faster, is to just take the min/max x/z coordinates to get the rectangle that contains all the sectors touched by red. As you see in the last image there are some blue sectors outside of the camera-area seen on the ground. These will be drawn even though they don't need to be, but it simplifies calculations and saves time in that computation instead of the drawing.

[tneva82]

Quote:

Original post by Erik Rufelt The corner-coordinates are in world OpenGL coordinates. You never want to cull tiles, just sectors right?

Umm sector is collection of tiles(in my case 32x32 though that's adjustable in settings). World is collection of sectors(currently 6x6 though again adjustable in settings). I wouldn't want to draw every single tile as techicly there's no reason why sector couldn't be 10000x10000 tiles(though obviously that would be getting pretty silly). I specifically would wish to limit number of tiles to not draw any more tiles than absolutly neccessary.

Though I suppose I CAN draw it but that will be lots o' wasted effort drawing stuff that's outside the camera.

Would determining number of tiles in X/Z axis(and starting point) be slower than drawing spare tiles? If I draw complete sectors then in worst case scenario I would be in my example be drawing total of 4096 tiles when only 484 tiles is actually needed(and even that includes tiles off the camera but getting non-rectangle area limited is probably inefficient). Almost 10x as many tiles as is needed! And we aren't even talking about objects yet which would cause similar wasted effort if I would draw full sectors.

And if we assume average vertex count for terrain tile is 8(ATM tile #1 has 6, tile #2 has 12. Polygonwise one of them has 18 and other 2(but then again the 2 is just flat ground)) that's 32000 vertexes to be drawn. Ugh. When 3200 or thereabout would be enough.

Doable and I suppose it wouldn't be issue in my limited needs but sure would hate to do so inefficient engine here.

Edit: Crap. I think I know where the issue might lie. I wonder if the sector co-ordinates are essentially from top-left to bottom right. Ie 0,0 tile is at top-left of sector. This would play havoc of drawing routine...Have to check this.

[Erik Rufelt]

Depends on your target hardware, on most modern hardware you could draw 320,000 vertices without any problems. However I get what you are saying, you want to cull tiles then. It should work the same way.
First you calculate the corner points, and divide by tile-width instead of sector-width, which gives you a rect in global tile-indexes, starting at tile 0,0 in sector 0,0. Then you also calculate sector-indexes by dividing tile-indexes by 32. Then you draw the visible sectors, and within them subtract sector-index*32 from the tile-index, which gives you the relative tile-index within the sector. Then draw only those tiles within the sector.

What I have written so far in all my posts deals with finding the index numbers of the visible tiles and/or sectors. This may or may not be what you need, if you treat the player sector as 0,0. Then you might instead need to simply keep the rectangle world-coordinates directly from the corner points, and compare these to each sector you try to draw. If they fall within the sector, then proceed by calculating the tile-indexes from there.

I'm not sure how you handle everything in your engine, so I can't say the best method to cull geometry. The main method of getting the area of the ground intersected by the camera view-frustum should give correct numbers, as long as the ground is reasonably flat (if not simply use the lowest point on the ground). From there it should not be too hard to calculate which geometry is currently within that area, but how to do it depends on details in how you draw everything.

Usually the camera is set up like the following:

glLoadIdentity();
glRotatef(x, 1.0f, 0.0f, 0.0f);
glRotatef(y, 0.0f, 1.0f, 0.0f);
glTranslatef(-x, -y, -z);

If you do it like that, then find the corner points, then they will be relative 0,0,0 in OpenGL coordinates. If you at a later time do other changes to the matrix, then the coordinates you give OpenGL will of course no longer match the corner point coordinate space, so you have to compensate by subtracting the current coordinate space offset from the old one.

[tneva82]

Thanks. I'll try to get it working.

BTW the black area issue I got fixed. I forgot to carry the x and z offsets into recursive calls so in the end that sector simply got drawn top of already drawn sector. Damn I felt stupid :D

And yeah the camera is set just like that in my game(well except for some reason I have third angle added as well though I don't think I really need it...Leftover from my first 3d-attempts for space flight simulator I suppose :D

Edit: And reason to limit drawing area to tile: Already FPS is ~200 when I draw rectangle whose size I have created by trial and error(problem is that it's not particulary flexible. Change screen resolution and it goes haywire. Change zoom level and it goes haywire. Change block size and it goes haywire). This with vertex arrays and arrays in graphic cards memory. This with pretty darned fast computer.

Actually I'm starting to wonder wether I'm doing something seriously wrong. Afterall there's just simple terrain and one model neither which is particulary detailed and 200FPS? There's not even that much non-drawing stuff done!

Albeit I can divide FPS by 5 and still have it good but sure is dropping scarily fast...

[Edited by - tneva82 on April 14, 2009 1:47:32 PM]

[Erik Rufelt]

I guess you are drawing one tile at a time?
This is why you might only want to cull sectors. If you have 32x32 tiles in a sector, that is 1024 draw() calls when drawing them one at a time. Now say you have two partly visible sectors, and need to draw about 500 tiles, it is very possible that drawing 500 tiles one at a time is slower than drawing 2048 (or even much more) tiles in one call. Especially if the vertex array is in video memory, where the only real overhead is the draw call.

It's insanely fast when you batch geometry up like that, already in video memory. I have an old application where I draw a terrain in one draw call, of size 1024x1024, giving more than two million triangles, and it runs at more than 200 FPS (Nvidia 8800GT). Of course you want to support lower end cards also, but I doubt anything below 100,000 triangles will be a problem.

If you have the memory, I would try building a large vertex array for the whole sector, and draw it in as few draw() calls as possible. You have indicated you already use a technique that allows for dynamic loading of sectors, in which case you don't need to keep very many sectors in video memory at a time.
To limit the number of draw calls, sort the triangles by texture, or better yet make a large texture in which you combine all the textures needed for that sector (put them side by side in a larger image), and just modify the texture coords to match the new texture.

If you do not want to do that then I would continue with the method you use now, and get an exact rectangle enclosing visible tiles, you can't really get much better than that.