• Advertisement
Sign in to follow this  

3D Model Terrain Collision

This topic is 689 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

I tried to search on Google about 3D model terrain collision but I still don't get the answer I want. I'd like to ask what method usually used to achieve this collision.

 

I have terrain (it has cave), let say it is an OBJ file and my entity will use collision box to detect the terrain collision. Is the collision basic different with terrain height collision?

 

Lot of people recommend to use a library, but I don't want to, I'd like to try to implement the collision myself.

If you guys have better advice, I'd really appreciate it.

Thank you before.

Share this post


Link to post
Share on other sites
Advertisement

Collision detection is a bit harder than it seems to be. This is why people recomend using 3rd pary libraries for collision and physics.

The main problem is that collision detection requieres a lot of code and a bit more math skills
. If you simply want to collide something with a mesh yourself, the simples thing is to use
sphere/ellipsoid vs mesh collision detection. There are few papers on the internet (all of them has few mistakes in them in my opinion) on that topic.

If you are interested specifically in collision detection I can't give you an educated advice.

Edited by imoogiBG

Share this post


Link to post
Share on other sites

While imoogiBG is right that most opt for using libraries, if you are only interested in collision detection not including correct collision handling then it is a bit easier.

 

In my experience detecting collisions is the easy bit... resolving them is hard.

 

By "easy" though take that with a pinch of salt... it takes time and a decent knowledge of math helps.

 

You can write a sphere vs triangle mesh routine that returns a boolean easy enough - less than a days fiddling.

Box vs mesh, probably a bit more work, you have corners and edges to consider - getting tricky now.

 

Now to to do those things in realtime and in a highly optimised fashion will take even more time.

Even more time still to resolve those collisions in a suitable way (and things can get very tricky here)

 

So depending on your use case, simple detection and resolution may be enough, but if you want robust and fast results then I recommend using a library.

 

(still trying these things is fun if you have the time)

Share this post


Link to post
Share on other sites


I have terrain (it has cave),
If you have caves and overhangs (more formally: if you have at least one point in which your terrain has multiple elevations) then you are out of luck.

Most of the time, terrain comes in "height-map terrain" flavor. That is: no caves, no overhangs.

 

There are a few alternatives... but I see you want to do the collision yourself... then you should be knowing what you're going to do.

Share this post


Link to post
Share on other sites

Life will be a lot easier for you if your terrain is just a height map. Collision detection is relatively easy but dealing with it is hard, search for "collide and slide". Stopping an entity from going through your terrain is easy enough and with a height map sliding along it is reasonably easy too (you just set the entity height to that of the terrain). Doing this with more generic meshes (as you have) is a lot more difficult, particularly getting an entity to slide along the surface.

 

A long time ago I implemented collision detection and response for a character moving using this paper: http://www.peroxide.dk/papers/collision/collision.pdf.

 

If you want caves and over hangs you can still do so with a height map and a mix of meshes. The height map will be just the normal terrain and you can mask off an area where the cave needs to be. In this area you don't use the normal terrain so it allows the entity to go through and beneath the terrain. Then you would have your actual cave mesh which covers the hole and makes it look normal and with no gaps. for the normal terrain then if the entity is above the height map just set them to it and if they are below do nothing. Overhangs will be similar to a degree.

 

This is involved, I switched and used PhysX. I would only implement this yourself for the reason of actually implementing it yourself (leaving/interest).

Edited by Nanoha

Share this post


Link to post
Share on other sites
Thank you guys for all of your replies. I see some choices here. First, to use height map. The reason I use model as terrain because I read height map technique requires random terrain, am I right? Second, to use collision library Third, as I read somewhere I can bake height map from model. Seems the easiest and the best is to use heightmap.

Share this post


Link to post
Share on other sites

Just as a sort of aside, is your player character going to be 'grounded'? That is, will it walk on the ground, or can it fly? I ask, because if grounded then there are alternatives to always performing a collision check against the world geometry. For example, constructing a navigation mesh from the world geometry, a la Recast. Such a library will analyze the world geometry and construct a mesh, such that the mesh represents all areas of the world that an agent of the specified height/radius could possibly be located without colliding with any of the bounding geometry. If a point is located on the mesh (and the Recast library provides functions to test this) then you know that the agent can be placed at that point without colliding. Given the other benefits of a nav mesh (path-finding) this is the technique I use the most for grounded characters.

Share this post


Link to post
Share on other sites

About the only thing you'll find that describes how to do it (mostly) is the peroxide.dk link provided above. However it does have a few errors. Depending on the geometry you use you might not run into them. I've actually been been writing a new (and hopefully improved) guide to what you want, but it won't be ready for a couple of weeks still I'd say. So for now, Fauerby's guide (the peroxide link) is the best I've been able to find. I don't really like recommending it because of a few misunderstandings it creates, but yeah it's the best I've seen so he deserves credit for that.

 

If you do use it, things to look out for:

 

* While it does ignore back-facing collisions, it doesn't actually handle back-facing entering of triangles.It only ignores back-facing collisions as a performance boost, and *not* for practical application. If you actually apply it practically and push your sphere into a triangle from its back face and then move it around, the resulting behaviour is not something you'll want.

* If you intend to know the character's resulting velocity at the end of each frame, that code won't let you (the velocity vector isn't actually velocity, it's displacement).

* You might notice the logic for padding a sphere away from a triangle it has collided with isn't quite right. Leave it as is.

* You might notice the sliding plane isn't calculated correctly when the sphere gets too close to a triangle. Leave it as is. These last 2 issues actually combine to dodge a problem.

 

The document includes code at the bottom. You definitely can whack that code straight into your project and it will work well enough. Just do not try to use one-way collisions at all, and if you want to keep a record of inertia, you'll have to find another way.

 

 

I believe I know the process inside out so I'll answer questions if I see them.

Share this post


Link to post
Share on other sites

Never programmed a 3D game but I do have an idea. Would it be possible to pick the closest point on a 3D object to a character and check the distant between that point and the character?

Share this post


Link to post
Share on other sites

LAURENT*, this question is off-topic but the answer is yes. For the distance GJK can be used, and it is basically used by every physics engine currently.

 

OP, you can use height-map or a collision library that supports mesh-convex collision. For terrains treated as a triangle soup, make sure the library handles correctly the cases when there are collisions between the other shapes and the internal edges of the mesh. Otherwise there will be some artifacts that may affect gameplay for a coplanar mesh with a large density of triangles and let's say, a sphere sliding on it. I guess Bullet physics library handle this case correctly, although I can't answer if there is a recent game that was shipped succesfully with this library. (Don't ask here about those things please it could be too off-topic.) 

Edited by Irlan Robson

Share this post


Link to post
Share on other sites

As Defend said, the Kasper Fauerby paper has some issues. This paper presents some improvements: http://arxiv.org/pdf/1211.0059.pdf

 

For continuous collision detection between general polygon meshes I recommend the following paper by J.M.P. van Waveren: http://mrelusive.com/publications/papers/Robust-Continuous-Collision-Detection.pdf. This method was used for collision detection in Doom 3. I successfully implemented it for linear movement of my character controller, although without Plücker coordinates. Combined with the method of removing a degree of freedom with every iteration as discussed in the above arxiv.org paper, it works very well.

Edited by D956

Share this post


Link to post
Share on other sites

I actually disliked that 'remove degrees of freedom' approach in Linahan's article. I disliked the article on the whole, finding issues with it almost as much as I found with Fauerby's. I rambled with displeasure here: http://www.gamedev.net/topic/674540-annoying-things-about-fauerbys-and-nettles-sphere-mesh-collision-detection-guides/

 

Since you say it was used in Doom, perhaps I simply didn't recognise the proper application for the restricting degrees of freedom approach. Perhaps what I had in mind was something it didn't cater to. I can't remember why I was whining about that particular thing. I'm sure I look stupid in my other thread hehe. 

 

I believe Fauerby's quadratic coefficients for detecting edge intersections are wrong also. This is because they are a straight copy of Schroeder's coefficients (found in the August 2001 copy of GDmag, at http://www.gdcvault.com/gdmag - you're welcome, people on the internet trying to source that). And Schroeder's coefficients are likely wrong, because Akenine-Moller says they are (in Real Time Rendering), and Akenine-Moller's coefficients are definitely correct.

 

Since Akenine-Moller used the exact same equations but got different results, and since none of these authors ever show how they get from equations to coefficients, Schroeder's are most likely wrong, which means Fauerby's are too.

 

The reason I say AK's coefficients are definitely correct is because Ericson (Real Time Collision Detection) produces the same coefficients as Akenine-Moller, and while Ericson - like every other author - doesn't show how he reached from equations to coefficients, Ericson's approach actually can be proven on paper. I believe the others required Mathematica; at least, Schroeder did. But Ericson's coefficients are definitely legit, and Akenine-Moller's are the same, even though Ericson uses a different approach (no simultaneous equations, no dot product = 0 trick).

 

 

So Nettle's guide = big mistakes, Fauerby's guide = several mistakes, Schroeder's guide = wrong coefficients.

 

Interestingly, these 3 authors are the 3 who wrote guides. Ericson and Akenine-Moller didn't write guides, they wrote books. Says something, doesn't it?

BUT having said that, Ericson also totally supports Nettle's completely incorrect approach, now listed as such on his website. Ericson also oddly describes his approach as "the one suggested in Schroeder with corrections in Akenine", when it simply isn't. The difference is the only reason I was able to work it out and confirm it as correct.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement