# Moving Aabb Vs Tri/aabb/sphere Code

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

## Recommended Posts

After some search on the web i didn't really found any satisfying solution. So decided to ask here directly.

The problem - i need a collison shape for a character which can be swept to find the earlierst collision (so the point/delta and the normal) against an AABB (potentialy also moving but this can be reduced to moving vs static afaik by subtracting the velocity, but maybe i am wrong here), Sphere (also moving) and Triangle (always static).

Right now i have everything working with sphere and tris (swept sphere vs sphere and vs tri), but sphere is too limited to represent a character. One way right now is to use a "capsule" compound shape out of several spheres stacked on top of each other... but i think this will have issues when the collision will be in the gap between spheres and i don't really want this (it will be rare but may occur) especially some forced cases where character will stuck in tris between 2 spheres... so i thought maybe to use AABB to represent a character (it would do what i need) but now the more important question, isn't it too complex? and computation heavy? Is maybe a AA cylinder a simpler shape for this? But afaik it isn't. The whole swept shape subject is bit shady (hard to find good material on the web)

So what's the best way to breakdown and solve this task? And ofcourse some code samples are highly appreciated. (not that good with math)

##### Share on other sites

AABB for character is not a good idea. Like you were saying a capsule would work well. Maybe you can try figuring out or writing capsule vs triangle code. If the capsule cannot rotate this makes the code much easier to implement. Perhaps a binary search would work well, rather than a more complicated time of impact solver.

##### Share on other sites
Perhaps a binary search would work well, rather than a more complicated time of impact solver.

TOI is crucial imo, i may have objects moving with very high speed

well in case of AA capsule, 2 sphere and a line segment (deflated cylinder) sweeps are required? I can do spheres but what about line segment sweep?

and this kind a become this topic

http://www.gamedev.net/topic/288963-swept-capsule-capsule-intersection-3d/

hmmm

Putting all together, it's intersection of capped cylinder with polygon, can be done by finding closest distance between segment and polygon...

so i need swept line segment algorithm against sphere/tri/line segment? sorry for noob questions... and if yes any reference with source?

##### Share on other sites

A binary search can be used to find time of impact. It's a way to implement a time of impact solver without anything particularly fancy or complicated.

Yes you can do a line segment sweep with a radius, or a cylinder sweep with two spheres attached. There are a lot of ways. If you want to implement this yourself you will have to learn about vectors, linear transformations, affine transformations, and this might be a lot of new topics to cover. Just a heads up! Maybe you can find some open source code somewhere or commission someone to write a function for you.

##### Share on other sites

AABB for character is not a good idea.

Care to elaborate on this? In my view having a flat bottom is definitely desirable. I'm using an AABB for player collision and it works great.

My implementation is based on some of the concepts laid out in the following paper about the collision detection in Doom 3 (although I don't use Plücker coordinates):

And I combine it with removing a degree of freedom with every iteration as described in this paper:

##### Share on other sites

would you mind to share any sources? cause it's really not simple to find something on the web. such information is always valuable.

and thank you for the papers!

##### Share on other sites

AABB for character is not a good idea.

Care to elaborate on this? In my view having a flat bottom is definitely desirable. I'm using an AABB for player collision and it works great.

If you can get it to work more power to you. It can just be simpler to avoid internal edge collisions and unwanted collision normals by using a curved surface, like a round hull or sphere. There can also be nice benefits like using the smooth edges to let the player glide around corners or into doorways. It's mostly a style difference. So for forum answers generally I try to recommend not using an AABB since a lot of hard problems can be avoided without requiring extremely solid code.

##### Share on other sites
Avoiding collisions between a segment and internal edges or unwanted normals requires almost the same work as if we replace a segment by a hull because SAT must be modified for this to be solved correctly in both shape combinations, and the triangle structure should be modified as well with adjacency information (e.g. storing tagged vertices/edges), otherwise there can be undesired behaviours like in the Bullet demos (see PEEL). However, for spheres this is easy since the triangle normal is chosen if the sphere is penetrating the triangle or its center hits a flat edge. Obviously a flat AABB bottom is not desired in comparison with an axis-aligned capsule if this problem is handled correctly because there will be smoother movements along convex triangle vertices and edges as Randy pointed out correctly. If you go a level deeper and pick an OBB then you have a hull. And we know hull vs. triangle tests are not cheaper than capsule vs. hull tests.

I recommend capsules as well because this is the shape that most physics engines pick for a character controller. The controller obviously must not suffer any of the problems mentioned before independently of which shape it uses.

Code or resources for character controllers are indeed difficult to find. You might get a physically accurate solution in the Bullet forums I think.
Edited by Irlan Robson

##### Share on other sites

Avoiding collisions between a segment and internal edges or unwanted normals requires almost the same work as if we replace a segment by a hull because SAT must be modified for this to be solved correctly in both shape combinations, and the triangle structure should be modified as well with adjacency information (e.g. storing tagged vertices/edges), otherwise there can be undesired behaviours like in the Bullet demos (see PEEL). However, for spheres this is easy since the triangle normal is chosen if the sphere is penetrating the triangle or its center hits a flat edge. Obviously a flat AABB bottom is not desired in comparison with an axis-aligned capsule if this problem is handled correctly because there will be smoother movements along convex triangle vertices and edges as Randy pointed out correctly. If you go a level deeper and pick an OBB then you have a hull. And we know hull vs. triangle tests are not cheaper than capsule vs. hull tests.

We're talking about continuous collision detection here. And the reason I don't like capsules is because of this:

I recommend capsules as well because this is the shape that most physics engines pick for a character controller.

This is a terrible argument.

Would you mind to share any sources?

Here's Doom3's source code: https://github.com/id-Software/DOOM-3-BFG

The collision detection stuff is all in "neo/cm" and the player physics code can be found in "neo/d3xp/physics/"

Edited by D956

##### Share on other sites

Sorry, I kind of skip over and read only the last post. I wanted to add to what Randy said. Said phrase shouldn't be present in this discussion as the OP mentioned a single and static triangle (a kind of rare case). (This might be a small help if the OP wants to extend the algorithm for general triangle meshes.) D956 is correct, these things are a bit off-topic so lets keep it for another discussion.

The capsule choice was personal and I believe that if you're considering the problems we mentioned and have a solution then an AABB should work correctly as well.

Edited by Irlan Robson

1. 1
2. 2
Rutin
20
3. 3
khawk
17
4. 4
A4L
14
5. 5

• 12
• 16
• 26
• 10
• 11
• ### Forum Statistics

• Total Topics
633757
• Total Posts
3013711
×