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.

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.

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. =)

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!

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.

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.. =)

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:



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]

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.

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.

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.