# Non-Physical collision detection problem

Hello all,

Just getting started porting an older 2d simulation to 3d. I’m very new to jMonkeyEngine. I’m looking at simulating a bunch of entities wandering around, kind of like fish swimming around in a fish tank. Since there may be >100 entities, I figure that physical collision detection is probably a bad idea. Is this correct?

I don’t really need physical interactions like gravity and such, I just need them to bounce off of each other, and also off the walls of the tank.

So far, I’ve successfully implemented a single box bouncing around in a cage using CollisionResults. But i’m running into a few problems:

1. Is there an easy way to get things to bounce off a surface? I’m thinking that you have to reflect the velocity vector over the normal vector of the surface. Is there an easy way to get the normal vector of what it collides with?
2. I’m getting some stuttering during collisions, where the box gets momentarily “glued” to the walls. I suspect this is due to the bullet passing through paper problem, where it collides with the surface and reflects, but the next update, it doesn’t move far enough out (still colliding), so it reflects once more back inside. In my 2D program, I had it test its motion before moving to see if it intersected, but I suspect in 3d space this would be too processor intensive. Is there a non-physical way to do this? I found the SweepTest method, but it appears it only works on physical objects. Since the only physical process I need to simulate are motion and collisions, I still feel that a non-physical method is the way to go.

Thanks so much for the help, sorry if this is a noob question.

If you are using ray casting, the normal is returned in the collision. I can’t remember if this is the case for the physics ray casting or not.

CollisionResult.getContactNormal();

As for 2, the physics is stepped the same way the 2d physics is, perhaps you can bypass the bullet app state and control this yourself? Not sure if JME allows for this or not by default, but if it being done there, I assume you should be able to as well. Maybe @normen can answer this.

If I understand correctly, ray casting will miss “glancing” collisions, won’t it? Right now i’m just testing to see if the two objects are colliding, but I think what I probably need to do is check if it WILL collide before it actually moves. Is there a way to do that rather than brute force geometry? or is that the best way? in the 2d version i had, my graphics consisted of simple circles bouncing around, making brute force very easy to calculate. The whole point of 3D, was to try to make it a bit nicer on the eye, so hopefully I can move away from circles, and go towards models.

Thanks so much for your time,

Spheres will still be a lot easier and faster if you find you can get away with it. The math is simple enough that you technically don’t even have to involve a real physics engine.

Complex mesh collision is officially “hard”. (There are entire books written on just that subject.) So down that route there will always be tradeoffs between accuracy and performance… and you should definitely not write your own. You will be pretty tied to bullet for sure that way.

Actually, you should be able to get the contact normal from the physics collision result anyways. So ray casting is really not necessary, Originally, I was thinking you were talking about objects colliding with non-moving objects, but I doubt this is exclusively the case.

Do you need to be able to change the outcome of projected collisions? Or just know about them before hand?

Maybe it would help if I went into more detail. I want the entities to wander around on a relatively flat world, and maybe a little bit in 3D above the surface of the world. I want them to detect collisions with the edge of the world and turn around when they get right to the edge. I also want entities to be able to detect collisions with other entities, because that will be considered an interaction and I will need to update some of the entities’ fields at that point. Other than that I really don’t need any complex physics.

So from what you guys are saying avoiding physical stuff would probably be ideal, and keeping the colliding shapes as spheres sounds like the best idea, which I think would be fine.

But then I’m left with my initial problem of it detecting collisions too late. I need some way of detecting a collision right before it actually happens, so I can alter the speed vector to “bounce off” before it actually crosses the boundaries of the other object, and potentially gets stuck inside. So I guess I do need to alter them beforehand.

Thanks again for all your replies.

Just to add, what I’m doing currently in 2d, all by brute force, is the following

1. If the speed vector makes it travel more than its own radius, divide the motion into steps no greater than the radius
2. do a virtual move one step forward, test with all other entities in the vicinity if radii will be overlapping, or if radius will extend beyond my world bounds
3. if there is an overlap, reflect speed vector along either y or x axis, or both (depending on what is appropriate).

This method actually misses grazing collisions with other entities (but not with walls) that are much smaller than the radius of the entities in question, but that’s not a huge problem in my simulation.

I have every single entity do this for each move. As I mentioned above, there will be more than 100 entities moving at any given time, the greater the number the better. All entities might have different sizes. I can probably approximate its main shape as a sphere for simplicity.

I don’t understand why objects would get “stuck inside” others.

Be that as it may, it’s definitely possible to calculate where and when two spheres moving at constant velocities will first come into contact, if that’s what you want. Start with the equations which describe the motion of their centers, compute the distance between those centers as a function of time, and solve for when the distance equals the sum of their radii. If there are multiple solutions, pick the smallest positive one. You’ll need the Quadratic Formula.

Hmm that sounds pretty good. The mathematics are definitely not super difficult, but I was hoping to be able to implement a nicer solution. But it’s ok, I guess I was just hoping I could get away with being lazy and using a built in way of doing it.

I Think objects are getting stuck to others, because of variable update speeds. Here’s a simplified explanation of what I think is happening:

Wall at x=0 entity moving at y=-1t
one update happens a full 1s, it moves -1 unit into the wall, it reflects like I told it to when it detects a collision.
next update happens faster, only .5s goes by, so it only moves 0.5 units out of the wall, so it still detects a collision, and reflects back towards the wall
it now goes deeper into the wall, and then reflects, and once it gets stuck has a difficult time ever getting out.

that’s why I think I need to pre-calculate the collision. If that’s not the case, please let me know!

Thanks so much for the pointers,

The built in way of doing it would be to use Bullet Physics. You can set gravity to zero and give each object a spherical collision shape with a high restitution. You can clamp the Y coordinates to zero. Without trying it, I can’t predict whether this would work with 100s of objects or not.

If it’s only the walls that you are getting stuck in then it’s because you are treating them as thin sheets. Treat them as divided space instead… so if you are on the wrong side of the wall, you always go back into the “world” instead of oscillating.

Not sure I’m explaining that well. The math is actually much easier, though. Setup a plane then just see what side of the plane you are on and at what distance.

ah… that is very smart! ok I’ll get coding, and see what happens. Thanks so much to everyone.

@sgold, I read that restitution is a pretty intensive property, so I think I will try to avoid that, so my simulation can have as much speed and possible entities as possible.

I really appreciate the feedback!

well speed is not that much of a issue with the ccd setting.
And object count is usualy also not, the physics can usually handle around as much as the graficcard in distinctive objects.

Just to update, I’ve implemented a brute force collision detection algorithm.

I have it split into two parts. One for entities colliding with each other using a 2D quadtree, and one for entities ray-colliding with terrain to keep them at the level of the terrain. Entities also check that they reflect off the bounds of my world, which i’ve set to be slightly smaller than the terrain.

All collisions between moving entities other moving entities, as well as all collisions between moving entities and stationary entities are detected.

I did a stress test:
On my computer at 1920x1080, 16bpp, 60hz, 4x, fullscreen, vsync
with 1000 moving entities and 1000 stationary entities,

I’m getting pretty manageable FPS (around 30), and I think it’s the graphics slowing it down because when I look up at the sky (nothing), the FPS climbs to 60fps.