Ray/polygon collision

Started by Musurca, May 09, 2004, 10:29:59 AM

Previous topic - Next topic

Musurca

Hey,

First of all, thanks a ton for adding that PolygonManager class in the latest release. That was a huge help.

On to the next problem, unfortunately: it seems that the ray/polygon collision methods (Object3D.checkForCollision(SimpleVector, float)) work very inconsistently. Collisions occur very rarely, and there doesn't seem to be any way of predicting when the method will work.

For instance, I can fire a projectile at a wall, calling checkForCollision each frame with the projectile's direction vector and the amount by which it moves during that frame. However, the collision is hardly ever registered. The sphere and ellipse collision methods work perfectly, but clearly I don't want to be doing full ellipsoid collision detection for a hundred small projectiles flying around the screen. Do you have any suggestions?

Thanks,

-Nick

EgonOlsen

I recently discovered two bugs in 1.00. On in the CollisionListener and one in the ray-polygon-collision itself. I'm not sure if they may cause the behaviour you describe, but it could be worth a try to use this version:

*Link removed*

It's a pre-1.01 with both bugs fixed. If it's still not working, try to adjust collideOffset in Config. Personally, i'm using the ray-polygon detection for exactly the same thing ATM (have a look at the "new example" thread in the news-section) and it works fine.

Edit: Docs for this version can be found here: *Link removed*

EgonOlsen


Musurca

Quote from: "EgonOlsen"Does it work now?

Yeah, it works very well. Thanks a lot. There are still some problems when projectiles are fired at an object from close range, but I suspect the problem is that I'm spawning the projectiles inside of said object. A collision won't be registered if the ray starts inside of an object's bounding-box, right?

Here's what I've been working on, by the way. It's playable right now, but I wouldn't want to show it to the public. I'll post it up in the Projects area as soon as we put together a Web Start-able demo.

EgonOlsen

Quote from: "Musurca"There are still some problems when projectiles are fired at an object from close range, but I suspect the problem is that I'm spawning the projectiles inside of said object. A collision won't be registered if the ray starts inside of an object's bounding-box, right?
No, it's not a problem if it starts inside a bounding box. If it were, no projectile could collide with a large landscape if fired on the landscape's surface. The "problem" (actually it's a feature... :wink: ) is, that polygons are backface culled in respect to the position/direction of the projectile before they are checked for collision. And if you fire your shot "inside" an object, almost all polygons of your object will be culled and therefor, no collision is detected. If you really want to cover this case, i suggest to do a simple distance check between the objects or "abuse" rayIntersectsAABB(...) in Object3D somehow...

Musurca

Okay, thanks. I think I can fix this by simply spawning the projectile closer to the emitter, but it's useful to know exactly how the algorithm works.

One final question about collision: I was using the ellipsoid method to collide my cars against objects in the scene (terrain is not taken into account during these kinds of collisions). I wasn't sure initially if the ellipsoid used in the Object3D.checkForCollisionEllipsoid() method was object-oriented, but my latest tests have indicated that it is not. The trouble is that the car is a lot longer than it is wide, so sphere or shortened ellipsoid collision detection are both going to cause problems when collisions occur against the car's front or rear (objects will appear to pass through the car shortly before the collision is registered).

I'm planning on calculating the OOBB for each object and running this sort of collision algorithm on my own, but it might be useful to contain this functionality in the engine itself. Would you be willing to add an Object3D.checkForCollisionOOBB() method to the next release? Or is there a way to approximate this with existing methods?

Thanks again, and sorry to be such a continual pest.

EgonOlsen

You are right: The ellipsoid doesn't get transformed like the object. It always remains "axis aligned". It's on my to-do list to see, if i can do something about it. Currently, the algorithm basically works like this:

The camera/object that should be checked for a collision is transformed into the collider's (the "target" of the collision) object space. The collision detection itself is taking place in ellipsoid space, which is a scaled variant of the collider's object space in which the ellipsoid is a unit sphere.
This translation from object into ellipsoid space is the problem. It happens for a lot of vertices of the collider multiple times (depending on the recursion depth of the collision) and therefor, it has to be fast. With the "axis aligned" ellipsoid, this is easy. It requires 3 divisions/vertex. If the ellipsoid should be tranformed too, it's no longer that simple.

However, i'll look into it and see what i can do. For the time being, can't you simply use some smaller spheres placed at the car's front and back (like one left and one right) to approximate it? I'm not sure how well this will work though...

Musurca

Actually, using some information here, I put together an implementation of the oriented bounding box collision algorithm that handles both dynamic and static collisions. I use the spherical collision detection method in jPCT to eliminate trivial cases, and then switch to my algorithm when there's a potential collision. I haven't tested it exhaustively, but it seems to work pretty well in my game.

Basically, each Object3D is associated with a corresponding OBB object, which consists of three axes and extents along them. Transforms applied to the Object3D are also applied to the OBB's axes and center. When a potential collision occurs, the target's bounding box checks for intersection with the source's bounding box. The velocity vector of the source is also taken into account.

The actual collision algorithm, which consists of a gauntlet of tests for potential separating axes, isn't terribly difficult to understand (although I'd never be able to derive it), but it is kind of tedious to implement. If you're thinking about adding this kind of functionality to jPCT, feel free to use as much of my code as you'd like: [link removed] (that link should only be good for a day or so).

EgonOlsen

Cooool...i'll have a look at your code for sure. The funny things is, that jPCT already has an OBB (i.e. the tranformed AABB) for each object. It's just not public. Maybe it should be...

Currently, it's used for collision detection in a way that rays/spheres/ellipsoids are checked against it before work starts on the polygon level (if it has to, i.e. if there is an intersection).

Anyway, i got the oriented ellipsoid stuff working too. At least i think i did...it requires some more testing. However, i think that your OBB-approach is very well suited for cars, because they are just boxes...basically... :wink:

EgonOlsen

Quote from: "Musurca"Here's what I've been working on, by the way. It's playable right now, but I wouldn't want to show it to the public. I'll post it up in the Projects area as soon as we put together a Web Start-able demo.
Still no public version?  :cry:

Musurca

Well . . . it's still a work-in-progress, but I guess I could put up a single-level demo. I'll try to make something available before July 4th.