Java-Gaming.org    
Featured games (81)
games approved by the League of Dukes
Games in Showcase (487)
Games in Android Showcase (112)
games submitted by our members
Games in WIP (553)
games currently in development
News: Read the Java Gaming Resources, or peek at the official Java tutorials
 
    Home     Help   Search   Login   Register   
Pages: [1]
  ignore  |  Print  
  Axis-aligned cylinder-triangle collisions  (Read 689 times)
0 Members and 1 Guest are viewing this topic.
Offline 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.
Click to Play

r = radius
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.
Offline matheus23

JGO Kernel


Medals: 106
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 Smiley

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

JGO Ninja


Medals: 43



« 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!
Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline 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.

[edit] 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?
Offline 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.
Online 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/
Online Riven
« League of Dukes »

JGO Overlord


Medals: 783
Projects: 4
Exp: 16 years


Hand over your head.


« 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
Offline 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.
Online Riven
« League of Dukes »

JGO Overlord


Medals: 783
Projects: 4
Exp: 16 years


Hand over your head.


« 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
Offline 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.
Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline EgonOlsen
« Reply #10 - Posted 2014-04-22 21:42:36 »

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

Online 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. Wink
Online Riven
« League of Dukes »

JGO Overlord


Medals: 783
Projects: 4
Exp: 16 years


Hand over your head.


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

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

Or do you happen to need it, and try to piggy back? Smiley (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  
 
 

 

Add your game by posting it in the WIP section,
or publish it in Showcase.

The first screenshot will be displayed as a thumbnail.

TehJavaDev (13 views)
2014-08-28 18:26:30

CopyableCougar4 (25 views)
2014-08-22 19:31:30

atombrot (38 views)
2014-08-19 09:29:53

Tekkerue (31 views)
2014-08-16 06:45:27

Tekkerue (30 views)
2014-08-16 06:22:17

Tekkerue (19 views)
2014-08-16 06:20:21

Tekkerue (29 views)
2014-08-16 06:12:11

Rayexar (66 views)
2014-08-11 02:49:23

BurntPizza (42 views)
2014-08-09 21:09:32

BurntPizza (34 views)
2014-08-08 02:01:56
List of Learning Resources
by Longor1996
2014-08-16 10:40:00

List of Learning Resources
by SilverTiger
2014-08-05 19:33:27

Resources for WIP games
by CogWheelz
2014-08-01 16:20:17

Resources for WIP games
by CogWheelz
2014-08-01 16:19:50

List of Learning Resources
by SilverTiger
2014-07-31 16:29:50

List of Learning Resources
by SilverTiger
2014-07-31 16:26:06

List of Learning Resources
by SilverTiger
2014-07-31 11:54:12

HotSpot Options
by dleskov
2014-07-08 01:59:08
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
Powered by MySQL Powered by PHP Powered by SMF 1.1.18 | SMF © 2013, Simple Machines | Managed by Enhanced Four Valid XHTML 1.0! Valid CSS!