Java-Gaming.org Hi !
 Featured games (90) games approved by the League of Dukes Games in Showcase (753) Games in Android Showcase (228) games submitted by our members Games in WIP (842) games currently in development
 News: Read the Java Gaming Resources, or peek at the official Java tutorials
Pages: [1]
 ignore  |  Print
 Axis-aligned cylinder-triangle collisions  (Read 3382 times) 0 Members and 1 Guest are viewing this topic.
theagentd
 « Posted 2014-04-22 00:10:40 »

Hello.

I'm trying to implement collisions for my player object with arbitrary static triangle-based terrain. The player is approximated with an axis-aligned cylinder.

h = height

The idea is to implement simple collision detection with arbitrary triangles. I had this idea of finding out how much the cylinder needs to be pushed away along the normal of the triangle to stop it from intersecting the triangle which seems simple enough, but I can't figure out how to do this, which got me wondering if I'm approaching this problem from the right direction. Does anyone have any good resources for this?

Myomyomyo.
matheus23

JGO Kernel

Medals: 138
Projects: 3

You think about my Avatar right now!

 « Reply #1 - Posted 2014-04-22 10:09:26 »

I'd try it with SAT. SAT should give you the minimum translation vector, MTV, maybe that helps

See my:
My development Blog:     | Or look at my RPG | Or simply my coding
http://matheusdev.tumblr.comRuins of Revenge  |      On Github
cylab

JGO Kernel

Medals: 174

 « Reply #2 - Posted 2014-04-22 11:39:54 »

I have no resource at hand, but try googling capsule collision instead of cylinder.

Mathias - I Know What [you] Did Last Summer!
loom_weaver

JGO Coder

Medals: 17

 « Reply #3 - Posted 2014-04-22 11:51:58 »

Why not start with the center point of the base and determine whether or not that point is above or below the terrain?

Can you approximate by comparing against the vertices instead of the triangle plane?

Due to the cylinder being axis-aligned, you can get away with several optimizations.

 If you need supreme accuracy, could you shift the center point of the base in the opposite direction of the normal for the distance of your cylinder radius and then do collision detection?
theagentd
 « Reply #4 - Posted 2014-04-22 13:36:09 »

Ah, capsules sound much more convenient then! I was under the impression that capsules would be more difficult to implement compared to cylinders.

I guess that the only thing I have to do then is calculate the distance from the capsule to the triangle.
http://www.java-gaming.org/index.php?topic=30375.0
This stuff looks useful for finding the closest point on a triangle, but it doesn't solve everything for me. A capsule is pretty much a line segment with a radius, so what I need to find is the closest distance between a triangle and a line segment, not a point. My Google fu is failing... ._.

Myomyomyo.
Roquen

JGO Kernel

Medals: 517

 « Reply #5 - Posted 2014-04-22 14:39:49 »

AABox the cylinder and/or cap.  Normal of tri gives you which subset of points to test.  Win.

EDIT: A ray vs. AABB description can be found here - http://graphics.tu-bs.de/publications/Eisemann07FRA/
Riven

« JGO Overlord »

Medals: 1336
Projects: 4
Exp: 16 years

 « Reply #6 - Posted 2014-04-22 14:48:36 »

If the cilinder is not a requirement, and you're open to a capsule, why not go all the way to an ellipsoid? That's how I did it 10 years ago, as back then I read that other games used that strategy too.

You transform the nearby geometry, by scaling it along the UP axis (renormalize the normals), using the center as the ellipsoid as the origin. Then your intersection math becomes SPHERE <=> TRI, which is trivial.

Once you found the intersection point, scale everything back, including the normals (renormalize again).

Hi, appreciate more people! Σ ♥ = ¾
Learn how to award medals... and work your way up the social rankings!
theagentd
 « Reply #7 - Posted 2014-04-22 18:23:39 »

As I was just looking for a simple and fast solution I ended up going with Riven's solution, and it seems to work well. I'm still missing an efficient data structure for the triangles (currently brute-forcing) and have yet to test this with more complex triangle meshes, but it seems to be working well at the moment.

I have a feeling that I will end up with a similar problem to Bullet, namely that seemingly flat surfaces can end up being really jumpy due to internal triangle edges in the terrain geometry. Imagine a flat terrain which consists of 1x1 meter floor quads (each quad being two triangles) and a player body sliding along this terrain. If the body happens to end up so that it intersects a triangle edge (the object is being pushed downwards due to gravity), it can generate some forces in extremely weird directions due to hitting an internal edge. The result is a VERY bumpy ride where the player is occasionally thrown high up in the air. My current idea for solving this is to group together connected triangles with the same normal, find the closest point off all grouped triangles and only use the closest point found. The problem is implementing a decent grouping algorithm, although I think I'll manage.

Myomyomyo.
Riven

« JGO Overlord »

Medals: 1336
Projects: 4
Exp: 16 years

 « Reply #8 - Posted 2014-04-22 18:40:27 »

You can ignore triangle edges if these edges are connected to other triangles.

If the ellipsoid/sphere touches a triangle, just push it out or 'reflect' it off. We're dealing with a surface (with surface normals) here, not with sharp edges of broken glass. A flat terrain comprised of quads (or tris) will only have normals pointing UP, regardless of how and where you bump into it. Grouping isn't really needed: you know ahead of time that your terrain is 'one group', some other model is one group too. They key to performance is specialization, not generalization: don't feed your algorithm a list of arbitrary tris, it is stripped of information that is very hard to reconstruct in a timely manner.

Hi, appreciate more people! Σ ♥ = ¾
Learn how to award medals... and work your way up the social rankings!
theagentd
 « Reply #9 - Posted 2014-04-22 21:33:56 »

Oh, the "terrain mesh" is actually made of arbitrary triangles, not a height map-based mesh.

Myomyomyo.
EgonOlsen
 « Reply #10 - Posted 2014-04-22 21:42:36 »

This works pretty well: http://www.peroxide.dk/papers/collision/collision.pdf

Roquen

JGO Kernel

Medals: 517

 « Reply #11 - Posted 2014-04-23 05:51:53 »

Assuming it works for your game I'd suggest you use a navigation mesh and open source it.
Riven

« JGO Overlord »

Medals: 1336
Projects: 4
Exp: 16 years

 « Reply #12 - Posted 2014-04-23 05:52:54 »

How does one use a navigation mesh for collision detection and response?

Or do you happen to need it, and try to piggy back? (that would be an odd, offtopic request..)

Hi, appreciate more people! Σ ♥ = ¾
Learn how to award medals... and work your way up the social rankings!
Pages: [1]
 ignore  |  Print

 ivj94 (581 views) 2018-03-24 14:47:39 ivj94 (45 views) 2018-03-24 14:46:31 ivj94 (372 views) 2018-03-24 14:43:53 Solater (60 views) 2018-03-17 05:04:08 nelsongames (107 views) 2018-03-05 17:56:34 Gornova (147 views) 2018-03-02 22:15:33 buddyBro (690 views) 2018-02-28 16:59:18 buddyBro (90 views) 2018-02-28 16:45:17 xxMrPHDxx (492 views) 2017-12-31 17:17:51 xxMrPHDxx (728 views) 2017-12-31 17:15:51
 SHC 10x NuclearPixels 10x Zemlaynin 10x KaiHH 10x ByerN 7x Spasi 6x Guerra2442 6x philfrei 5x VaTTeRGeR 5x orangepascal 4x ags1 4x princec 3x ndnwarrior15 3x Trilarion 3x mesterh 3x Phased 2x
 Java Gaming Resourcesby philfrei2017-12-05 19:38:37Java Gaming Resourcesby philfrei2017-12-05 19:37:39Java Gaming Resourcesby philfrei2017-12-05 19:36:10Java Gaming Resourcesby philfrei2017-12-05 19:33:10List of Learning Resourcesby elect2017-03-13 14:05:44List of Learning Resourcesby elect2017-03-13 14:04:45SF/X Librariesby philfrei2017-03-02 08:45:19SF/X Librariesby philfrei2017-03-02 08:44:05
 java-gaming.org is not responsible for the content posted by its members, including references to external websites, and other references that may or may not have a relation with our primarily gaming and game production oriented community. inquiries and complaints can be sent via email to the info‑account of the company managing the website of java‑gaming.org