Finding the height of a point on a given list of vertexes?

Member
Posts: 281
Joined: 2009.04
Post: #1
Well, sorry if the title sounds confusing, but it's the best way I could think of explaining my problem.

I have been working on a 3D FPS (opengl) and my 'physics' is not working.

The way that the physics (just the part where the player stays on the floor) works is by finding the closest vertex on the map (game level made of verts) and setting the player's height to the height of that vertex.

Although this seems sound to begin with, There is a flaw in the system:

Here is a diagram of the situation.

When the player is at A, the closest vertex is Î©, and the player 'drops' onto the world with the same y coord as Î©, so this works well.

When the player is at D, the closest vertex is ÃŸ, and the player drops onto the world in line with ÃŸ, working again.

But when the player is at B, the closest vertex is Î©, so this doesn't work, as if the player's height is the height of Î©, it falls through. The same happens with ÃŸ, except the player shoots up into the sky.

The only methods of solving the problem that I could think of was using calculus, not an endearing prospect, or finding the normal and/or the face.

( I am using AnotherJake's OBJ loader. )

P.S. I'm sorry if this all seems very complicated but please help me, It is driving me nuts. If you don't understand it would help if you could point me in the right direction of another way of accomplishing this.

~ Bring a Pen ~
⌘-R in Chief
Posts: 1,277
Joined: 2002.05
Post: #2
The thought that immediately popped into my head:

Find the two closest points* and interpolate between their heights based on the distance between the player and that point.

For example: B is closest to Î© and ÃŸ.

p = the distance between B and Î© ignoring the Y component (or Z, whichever way is up/down)

q = distance between B and ÃŸ doing the same

t = p + q

Let's say:
p_h = p / t = 0.30
q_h = q / t = 0.70

Height of Player = Î©.y * p_h + ÃŸ.y * q_h

Try that? It still won't be perfect, but it should be better than what you have. I must disclaim that I just woke up after very little sleep and am leaving imminently so I haven't thought about this much.

* If your points are all equidistantly spaced on a regular grid, then you won't have any problem, but you also need to ensure that the points you pick are on opposite sides of the player. Visually, if you draw a line between the two closest points, and then slide a perpendicular line along that axis, it should hit the player.

Otherwise you could end up with a case like:

Member
Posts: 281
Joined: 2009.04
Post: #3
Hmmm. That sounds like a good idea, but ensuring that the points are on opposite sides of the player...

Ideally one would be able to find out which face the player is on then work out the vertexes, but I have yet to grasp the way the OBJ loader handles these.

~ Bring a Pen ~
Luminary
Posts: 5,143
Joined: 2002.04
Post: #4
one possibility is to grab Newton (or Bullet or ODE, but I like Newton), feed your OBJ straight into its triangle mesh object, and make a capsule or something for the player, and let it handle the heavy lifting
Member
Posts: 281
Joined: 2009.04
Post: #5
Well, I could, but why? I like challenges! And I would like to know how my finished game works too!

Hmmm. To find the two closest points would mean doubling the time taken, using my current methods.

~ Bring a Pen ~
⌘-R in Chief
Posts: 1,277
Joined: 2002.05
Post: #6
Any strategy suggestions would depend on the vertex packing format/layout.
Member
Posts: 749
Joined: 2003.01
Post: #7
This is a fairly messy problem unfortunately. In 3D you need to find the triangle that, viewing from the top-down, encloses the point you are trying to find the height for. Then interpolate the heights of the 3 vertices of this triangle to find the height of your point.

So you need to reason in triangles, not vertices anymore. It may well be that the closest vertex to your point is not part of the triangle that encloses it.

What I would do is make a vector of all the mesh triangles (a struct defining the vertices position), then you need to check one by one which one of these triangles contains your point (it has to satisfy 3 linear inequalities).

And yeah, for this to be not too slow you need to partition the space so that you are not checking all triangles, only the close ones.

Or, my suggestion, use Unity (its free now!) ;-)

Â©hâ‚¬ck Ã¸ut Âµy stuÆ’Æ’ Ã¥t ragdollsoft.com
Moderator
Posts: 3,591
Joined: 2003.06
Post: #8
I don't quite understand what's going on. Are we talking about keeping an arbitrary object on/above a height-mapped terrain? If that's the case, you probably don't care about any of the info from the model itself (the player), just figure out how to interpolate height at any point within any triangle in the terrain. Once you have the height at any point on the terrain you want, positioning the player vertically is trivial.

==============

For the obj loader, I can at least say that the format it spits out is very simple (I know, that's what they all say, but this is as simple as possible). It's a linked list of arrays of vertices (meshes), each array arranged as: triangle, triangle, triangle, triangle, triangle, etc. Where each triangle is three vertices and each vertex is three GLfloats -- which is the format you need to send to glDrawArrays

You can iterate through each mesh in the linked list of meshes like this:
Code:
```    // print out how many triangles the mesh has, just for fun     unsigned    numTriangles = 0;     Mesh        *mesh = objMesh;     while (mesh != NULL)     {         numTriangles += mesh->numTriangles;         mesh = mesh->next;     }```

If you look at the drawMesh function in SimpleObjLoader.c, you will see that it iterates through the linked list of meshes the same way, but instead of adding up the triangles in each mesh it sets the material properties and submits the geometry to the GL.

Where it says "numTriangles += mesh->numTriangles;" you could instead access the array of vertices with mesh->verts[myVertIndex * 3]. As mentioned above, each vertex consists of three GLfloats and there are three vertices to each triangle, so it'd be 9 floats for each triangle, so do mesh->verts[myTriangleIndex * 9] to iterate through each triangle. It's just simple array math.

Each mesh is for a different material group, as defined in the obj file. So if your obj file only has one material, there's only one mesh in the linked list. A material group could mean that part of the model is using a particular shading, lighting or texture, different than another part of the model, which is why one model can't typically be described and sent to OpenGL in one single group -- hence the linked list of meshes.

I don't know if that makes sense, so let me try one more view of it: Each obj file is a "model" right? Well each model would be nice if it were just one big pile of triangles we could send to OpenGL. Unfortunately, it isn't quite that simple all the time. For example, in the obj loader demo there is a teapot. The teapot has a lid which is white, but untextured, and a pot which is yellow, but untextured. In this case we will have to use two meshes to describe the model to OpenGL: the white lid material mesh and the yellow pot material mesh. If it were just a single simple mesh with one texture and no other material properties we'd only need one mesh and wouldn't require a linked list of multiple meshes, but that's not what you'll usually be working with -- again, hence the linked list of meshes.

Instead of a linked list we could use other things like some kind of dynamic array of meshes or something, but linked lists are simple and well-suited to this so that's what I used. I hope that makes a little more sense.
Moderator
Posts: 3,591
Joined: 2003.06
Post: #9
Reading the thread a little more I think I see that it is indeed just that -- finding the height of a particular point on the terrain. That's what that other thread was about as I recall. Mikey, you've been beating on this problem for a while now!

Everyone else here has already pointed out good directions to solutions. You need to find the triangle that your player is above and interpolate where on that triangle the player stands to find the height. This is a classic problem, and fun too, but certainly not complex.

It sounds like you're using the obj loader for your terrain. I wouldn't recommend that. Instead, I would use a height-mapped terrain so that it's easier to organize the terrain in rows and columns of triangles. The obj loader loads a "soup" of triangles which aren't ordered, which makes searching by position very inefficient -- at least without a spatial hash of some sort. Much easier to use a height-mapped terrain instead.

Either that, and as OSC suggested, start learning to use a physics library. At this point, since you're sticking to C for now, I'd recommend starting with Newton. Bullet is better but it is primarily C++ and its C API is nascent, and the documentation is too sparse for beginners (heck, it's sparse for experienced programmers!). Learning to use a physics library isn't easy, so it's a challenge unto itself. Learning how to use "middleware" like physics libs is what development is all about nowadays, so it's well worth the effort.

All that said, if you want to avoid physics libs for now, I would definitely do a simple height-mapped terrain for this.
Member
Posts: 749
Joined: 2003.01
Post: #10
Quote: Mikey, you've been beating on this problem for a while now!

heh yeah 7 threads and 3 months according to search
Somehow always an interesting topic though.

Â©hâ‚¬ck Ã¸ut Âµy stuÆ’Æ’ Ã¥t ragdollsoft.com
Member
Posts: 281
Joined: 2009.04
Post: #11
Yes, sorry, but the last six were about the method I tried originally.

Even so, sorry for the seven posts

I will maybe try heightmaps. Or maybe not. We will see.

Thankyou anyway for helping.

I will post a demo if/when the physics is finished.

~ Bring a Pen ~