Java-Gaming.org Hi !
 Featured games (83) games approved by the League of Dukes Games in Showcase (583) Games in Android Showcase (163) games submitted by our members Games in WIP (633) 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 1040 times) 0 Members and 1 Guest are viewing this topic.
theagentd

« JGO Bitwise Duke »

Medals: 455
Projects: 2
Exp: 8 years

 « 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: 121
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 Wizard

Medals: 80

 « 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

« JGO Bitwise Duke »

Medals: 455
Projects: 2
Exp: 8 years

 « 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
 « 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
« League of Dukes »

« JGO Overlord »

Medals: 981
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

« JGO Bitwise Duke »

Medals: 455
Projects: 2
Exp: 8 years

 « 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
« League of Dukes »

« JGO Overlord »

Medals: 981
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

« JGO Bitwise Duke »

Medals: 455
Projects: 2
Exp: 8 years

 « 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
 « 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
« League of Dukes »

« JGO Overlord »

Medals: 981
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

You cannot reply to this message, because it is very, very old.

 Ralphanese (22 views) 2015-05-29 13:07:55 Gibbo3771 (18 views) 2015-05-29 06:54:17 Ralphanese (23 views) 2015-05-28 16:52:52 theagentd (31 views) 2015-05-27 22:21:17 theagentd (38 views) 2015-05-27 22:21:08 CopyableCougar4 (27 views) 2015-05-27 19:24:50 MrMapcom (24 views) 2015-05-23 20:26:16 MrMapcom (33 views) 2015-05-23 20:23:34 Waterwolf (39 views) 2015-05-20 15:01:45 chrislo27 (46 views) 2015-05-20 03:42:21
 Riven 27x Rayvolution 25x theagentd 23x BurntPizza 21x Spasi 17x KevinWorkman 17x orangepascal 16x Drenius 15x ra4king 13x princec 12x opiop65 12x DavidBVal 12x Husk 11x EgonOlsen 10x kevglass 9x Zeldar 9x
 Intersection Methodsby Roquen2015-05-29 08:19:33List of Learning Resources2015-05-05 10:20:32How to: JGO Wikiby Mac702015-02-17 20:56:162D Dynamic Lighting2015-01-01 20:25:42How do I start Java Game Development?by gouessej2014-12-27 19:41:21Resources for WIP gamesby kpars2014-12-18 10:26:14Understanding relations between setOrigin, setScale and setPosition in libGdx2014-10-09 22:35:00Definite guide to supporting multiple device resolutions on Android (2014)2014-10-02 22:36:02
 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