## Searching for vertexes...

Member
Posts: 281
Joined: 2009.04
Post: #1
Well, as you may or may not know, I am working on a 3D OpenGL game written in C. I am currently trying to include physics function(s) [Basically keeping the character on the floor].

What I would do is check every vertex against the players vertex by rounding to the nearest 10, and if the two answers are equal, then checking if this is the closest vertex to the player we have found so far. Right? Once we have been through all the vertexes the one closest is the one used to set the player's height to.

Here's my code:

Code:
```float getFloor(Mesh * mesh , float  x, float y, float z ) {     float closestDistance = 10000;     int counter;          float x1; //     float y1; //  The three coordinates of  our current vertex...     float z1; //          int cd;               // first, work out the border verts of the squares which the map's divided.     // obj coords are  + = up and to the left               printf("x %i, y %i",x,y);               counter  = 1; // First vertex in the array          while ((mesh->verts[counter+3]))     {         x1 = mesh->verts[counter];         y1 = mesh->verts[counter+1];         z1 = mesh->verts[counter+2];  // ^^ The mesh is in an array of verts in the order of x1,y1,z1,x2,y2,z2,x3...                  printf("x1 = %f\n",x1);         printf("y1 = %f\n",y1);         printf("z1 = %f\n",z1);                                        if (  roundtox(x1,0.2) == roundtox(x,0.2) &&   roundtox(y1,0.2) == roundtox(y,0.2) ) // I use this formula: answer = round(startnumber/roundtothenearest)*roundtothenearest         {             printf("Calculating Distance...");             cd = sqrt(pow((x - x1) , 2)  + pow ((y - y1) , 2)); // the distance between the player's point and the vertex currently checking...                                                                 if (cd < closestDistance)             {                 closestDistance = cd;             }                          else             {                 counter += 3;             }                      }         else         {             counter += 3;         }              }     printf("getfloor returning %f\n", y1);     return y1;      }```

Now, the code works perfectly, but very very slowly.

What should I do?
And, what do commercial games do?

~ Bring a Pen ~
Sage
Posts: 1,487
Joined: 2002.09
Post: #2
You need to use some sort of spatial partitioning to find the closest vertexes.

By rounding to the nearest 10, you are on the right thought track. Use a cheap check to find if the two things are close, then do a more expensive check if they are. The problem is that you still end up having to do a ton of those cheap checks, one for each vertex. Even if the cheap check is 2x faster than the more expensive one, the best you will get is 2x faster.

What you really want to do is use some sort of spatial partitioning data structure so that you can ask it for things near a point and it will give you a small list of things.

The simplest of such structures would be a simple 2D or 3D array. You basically put a grid over the entire world. Each square in the grid has a list of the vertexes that are in the square (much like your rounding to the nearest 10). When you want to find the vertexes near a certain point, you just need to check all the points in the grid cells within a certain range of the point. For a large grid and a small sample area, you will probably only be checking a tiny fraction of the total number of vertexes. Doing this will probably get you a speed improvement of 50x or more.

http://en.wikipedia.org/wiki/Space_partitioning

Scott Lembcke - Howling Moon Software
Author of Chipmunk Physics - A fast and simple rigid body physics library in C.
Member
Posts: 281
Joined: 2009.04
Post: #3
Well, I've added a check like this:

Code:
```int findposition(int x, int y) {     int pos;                    if ( (x > 0) && (y >= 0)) // TR     {         if (x > 1 && y > 1)             pos = 16;         if (x < 1 && y > 1)             pos = 15;         if (x < 1 && y < 1)             pos = 11;         if (x > 1 && y < 1)             pos = 12;     }               if ( (x <= 0) && (y > 0)) // TL     {         if (x > -1 && y > 1)             pos = 14;         if (x > -1 && y < 1)             pos = 10;         if (x < -1 && y > 1)             pos = 13;         if (x < -1 && y < 1)             pos = 9;              }```
etc, etc...

But even that doesn't speed it up enough.

~ Bring a Pen ~
Member
Posts: 281
Joined: 2009.04
Post: #4
OK, If I were to use BSP trees, how would I store that?

~ Bring a Pen ~
Sage
Posts: 1,487
Joined: 2002.09
Post: #5
I'm not exactly certain what that code snippet is trying to achieve exactly, but that is a lot of comparisons to compute. Comparisons are a pretty expensive thing to do because of pipelining. Branch prediction helps, but probably only when the outcome reliably chooses one path or the other. Some CPUs don't have branch prediction at all, I remember people complaining about the lack of it in the PS3 and XBox 360 CPUs, and I wouldn't be surprised if it was missing from the ARM CPUs in the iPhone.

You could probably reduce the code you have to doing something like this:
Code:
```int ix = (int)(x/cellsize); int iy = (int)(y/cellsize); Vertex vertexes_in_cell[ix][iy];```

That's what I was describing above, converting the floating point position to a low resolution grid cell coordinate. You would need to check the surrounding grid cells within the range that you wanted to check of course too.

As for other spatial indexes: BSPs work well for indoor environments as they are easy to implement by picking walls as the splitting planes. Quadtrees and octtrees are similar, but you are just splitting areas in quaters or eights at each level using axis aligned planes. Spatial hashes are like the grid thing above, but are more memory efficient for large and sparse areas. There are also a number of other tree based indexes that use bounding volume (boxes, spheres, etc) hierarchies or just other unique ways of subdividing the space given to them. Depending on what you are trying to accomplish, different structures will fit your problem better. You will have to read up on a bunch of different types before you can really make that decision.

Scott Lembcke - Howling Moon Software
Author of Chipmunk Physics - A fast and simple rigid body physics library in C.
Member
Posts: 281
Joined: 2009.04
Post: #6
Quote:int ix = (int)(x/cellsize);
int iy = (int)(y/cellsize);
Vertex vertexes_in_cell[ix][iy];

I don't understand. My maps are all desert/moor but I don't see what the code is. I see how ix and iy are the grid coordinates, but what is Vertex vertexes_in_cell[]?

~ Bring a Pen ~
Sage
Posts: 1,487
Joined: 2002.09
Post: #7
Oh, whoops. I meant this:
Code:
`Vertex *vertexes_in_cell = cells[ix][iy];`
So you get an array of vertexes in a certain cell.

Scott Lembcke - Howling Moon Software
Author of Chipmunk Physics - A fast and simple rigid body physics library in C.
Member
Posts: 281
Joined: 2009.04
Post: #8
So basically I should compile a list of vertexes in cells before the game runs, then at loop time check to find which cell the player is in, then find the nearest vert in the cell? But how would I store the grid with the vertexes?

grid[x][y] can only store one vertex' index... e.g. int grid[x][y] = 1;
not 1 2 4 45 26

~ Bring a Pen ~
Sage
Posts: 1,487
Joined: 2002.09
Post: #9
You would have to store a pointer to a list or array of vertexes in each slot in the 2D or 3D array that you are using.

Scott Lembcke - Howling Moon Software
Author of Chipmunk Physics - A fast and simple rigid body physics library in C.
Member
Posts: 281
Joined: 2009.04
Post: #10
That's a lot of memory, having lots of arrays inside a normal array. Maybe a 4D array:

Grid[x][y][index] ?

I still don't see though...

~ Bring a Pen ~
Sage
Posts: 1,199
Joined: 2004.10
Post: #11
Try doing it, it may not actually be that much memory. Another option which may be a memory win ( and may not ) would be to use a hash table instead of a 2D array.

The hashtaable may use more memory, and may use less, depending on the size of your environment/cellsize.

Also, I hate to say stuff like this, but memory's just a lot more abundant these days. Even the iPhone has a lot of memory compared to the machines I learned to program on. You should try to see if what Skorche is suggesting really is a lot of memory compared to what you have available.
Sage
Posts: 1,487
Joined: 2002.09
Post: #12
Using a hash table instead of a 2D or 3D array of cells is what spatial hashing, and it's two advantages are lower memory consumption and that it can extend (nearly) infinitely in all directions without needing explicit bounds.

If your mesh is fairly flat, a 2D array will probably do, and depending on how dense your mesh is you can get away with a fairly small array. A spatial hash would still probably end up being better, but is much more difficult to implement.

Scott Lembcke - Howling Moon Software
Author of Chipmunk Physics - A fast and simple rigid body physics library in C.
Member
Posts: 281
Joined: 2009.04
Post: #13
OK, what's a spatial hash? And I still don't see how to include more than one item in an item of a 2D array. 3D arrays are an option, but still... How about a char array with a space:

grid[x][y] = "1 0 2 34 24"?

~ Bring a Pen ~
Sage
Posts: 1,487
Joined: 2002.09
Post: #14
A spatial hash uses a hashing function to convert 2D or 3D cell coordinates into a hash value. You use the hash value as an index in a 1D array. It's more memory efficient for sparsely populated regions.

You don't need to store more than one item in each cell of your 2D array if what you are storing is a pointer to another array or a linked list. You will have to use dynamic memory though. (malloc and free)

Scott Lembcke - Howling Moon Software
Author of Chipmunk Physics - A fast and simple rigid body physics library in C.
Member
Posts: 281
Joined: 2009.04
Post: #15
So I have my grid[x][y] indexes pointing to an index in a 1D hash array?

Code:
```grid[x][y] = 2; hash[2] = //what?```

Sorry if I'm being stupid, but I'm still kinda new .

~ Bring a Pen ~