Author Topic: Collisions  (Read 5898 times)

Offline Kernle 32DLL

  • byte
  • *
  • Posts: 20
    • View Profile
Collisions
« on: April 21, 2011, 02:00:28 am »
Hi there,

Short question, how to check for collisions in jPCT-AE? I only found Sphere/Ellipsoid to Polygon checking. Is there any chance of Polygon to Polygon checking, e.g. simple mesh intersecting routines, or in worst case, a simple Box to Polygon method? Didn't find any, and Sphere/Ellipsoid to Polygon checking could get a bit tricky with my game approach.

So long,
Kernle

Offline EgonOlsen

  • Administrator
  • quad
  • *****
  • Posts: 12295
    • View Profile
    • http://www.jpct.net
Re: Collisions
« Reply #1 on: April 21, 2011, 10:32:31 am »
No, there isn't such thing in jPCT(-AE). Box2Polygon (or even Poylgon2Polygon) isn't simple...it's actually more complicated and slower then Ellipsoid2Polygon. If you really need it, consider to use a third party library like JBullet. The wiki contains some information on how to combine jPCT and JBullet.

Offline Kernle 32DLL

  • byte
  • *
  • Posts: 20
    • View Profile
Re: Collisions
« Reply #2 on: April 21, 2011, 05:01:21 pm »
Mh, not really a friend of bullet. Also, it seems a bit overkill for some simple intersection tests. Isn't there some other lightweight method for collision detection? I don't need any real physics stuff, since I only want to detect if the player has collided with the wall, to reset him onto the right track :/

Well, any suggestions?

So long,
Kernle

Offline EgonOlsen

  • Administrator
  • quad
  • *****
  • Posts: 12295
    • View Profile
    • http://www.jpct.net
Re: Collisions
« Reply #3 on: April 21, 2011, 09:51:15 pm »
Well, any suggestions?
Yes, use ellipsoid collision detection. What's the exact problem with it?

Offline Kernle 32DLL

  • byte
  • *
  • Posts: 20
    • View Profile
Re: Collisions
« Reply #4 on: April 22, 2011, 01:14:17 pm »
What's the exact problem with it?

That an ellipsoid is not a submarine :D No seriously, the problem is that using an ellipsoid (or a sphere, same matter) is not percise enough to make for a collision tester for a submarine. I could of course kind of rebuild the sub with ellipsoids for collision testing, but that would be an enormous performance waste.

I attached a picture for further explaination.

So long,
Kernle

[attachment deleted by admin]

Offline EgonOlsen

  • Administrator
  • quad
  • *****
  • Posts: 12295
    • View Profile
    • http://www.jpct.net
Re: Collisions
« Reply #5 on: April 22, 2011, 01:38:37 pm »
I fail to see a real issue with that. Looks like a pretty good fit to me. Another option might be to use two spheres instead. Or maybe you can create something out of ray/polygon collisions.

Offline Kernle 32DLL

  • byte
  • *
  • Posts: 20
    • View Profile
Re: Collisions
« Reply #6 on: April 22, 2011, 01:53:20 pm »
The issues are the areas marked red. There are areas which would be handled as collided, but there was no actual collision, and areas where geometry would not be tested for collision. Two spheres would create the same problem.

However, you gave me a good hint with ray/polygon collisions. I think I'll try that, and report back. Thanks =)

So long,
Kernle

Offline Kernle 32DLL

  • byte
  • *
  • Posts: 20
    • View Profile
Re: Collisions
« Reply #7 on: April 24, 2011, 05:42:19 pm »
Well, that didn't work out as I planed :-/

I developed the following approach, but using this drops my fps to near 30-40 on a Galaxy S, this means unplayable on slower devices:

I use a simplefied, 2D version of my mesh, and take the bounding vertex lines. Interpreting this lines a vectors, I use them via calcMinDistance using my world Mesh. So basically, I'm moving that "shape" around, and check if this shape collides with my map.



The code looks like this:
(mCollisionShapeX and mCollisionShapeY are arrays containing the X/Y Points for my "collisionshape", see picture)

Code: [Select]
final public static SimpleVector sCollisionOrg = new SimpleVector();
final public static SimpleVector sCollisionDir = new SimpleVector();

public void checkCollisions()
{
for (int i = 0; i < mCollisionShapeX.length; i++)
{
int i2 = (i+1) % mCollisionShapeX.length;

sCollisionOrg.set(mPlayerPos.x + mCollisionShapeX[i], mPlayerPos.y - mCollisionShapeY[i], 0);
sCollisionDir.set(mPlayerPos.x + mCollisionShapeX[i2], mPlayerPos.y - mCollisionShapeY[i2], 0);

sCollisionDir.sub(sCollisionOrg);

// Normalizing without creating a new vector
float length = sCollisionDir.length();
sCollisionDir.x /= length;
sCollisionDir.y /= length;

float distance = mWorldObject.calcMinDistance(sCollisionOrg, sCollisionDir);

if (distance != Object3D.COLLISION_NONE && distance <= length)
{
resetPlayerPosition();
break;
}
}
}

As already said, this slows down the game quite impressively. So, either calcMinDistance is coded very sloppy, or just not suited for this kind of use. Anyway, this leaves me with no choice but to start from scratch. I know the answer is there somewhere, there is just something missing I don't get.

I think my approach with ray detection via the vectors mentioned above is not so bad, but I don't get it connected with jPCT-AE :/

Help?

So long,
Kernle

PS: Oh, speaking of it, there are two things that could be improved within jPCT-AE: Make a function to normalize vectors without creating a new one, and looking into the calcMinDistance variant that takes a maximum distance value. Either I didn't get the point, or it just does not work. Thats why I did a manual check with <= distance (see code).

Offline Nipsting

  • byte
  • *
  • Posts: 2
    • View Profile
Re: Collisions
« Reply #8 on: April 24, 2011, 08:45:39 pm »
Now I'm by no means a programmer, so I might be reading your code wrong.

However what you could do to speed it up is put in a cutoff distance which is equal to the velocity.magnitude of your submarine. if it returns true check if the sub is moving towards or away, if it is moving towards then do a collision check on the nearest point not all of them.

Another way to do it without using rays is use a combination of box, sphere and ellipsoid as a "bounding box" for your sub and do collision checks on those. The math for primitive objects is far simpler to deal with than what you're trying atm.

Offline EgonOlsen

  • Administrator
  • quad
  • *****
  • Posts: 12295
    • View Profile
    • http://www.jpct.net
Re: Collisions
« Reply #9 on: April 25, 2011, 09:11:49 pm »
As already said, this slows down the game quite impressively. So, either calcMinDistance is coded very sloppy, or just not suited for this kind of use. Anyway, this leaves me with no choice but to start from scratch. I know the answer is there somewhere, there is just something missing I don't get.
It's not sloppy. It uses this approach, which is pretty clever: http://portal.acm.org/citation.cfm?id=272315
It's just that you are really stressing it. I still don't see the point why you have to use a kind of exact collision detection that mimics the shape of the submarine. Almost no game does this...almost all are using a simplified model like an ellipsoid of a box to approximate the actual mesh.

PS: Oh, speaking of it, there are two things that could be improved within jPCT-AE: Make a function to normalize vectors without creating a new one, and looking into the calcMinDistance variant that takes a maximum distance value. Either I didn't get the point, or it just does not work. Thats why I did a manual check with <= distance (see code).
You can already do this. Just use the normalize(<SimpleVector>)-method and feed the vector into it that you want to normalize, i.e.
Code: [Select]
nz=nz.normalize(nz);
Looks a bit strange, but works fine.

You can be pretty sure that the calcMinDistance-methods are all fine. What's your exact problem with that particular method?

Offline Kernle 32DLL

  • byte
  • *
  • Posts: 20
    • View Profile
Re: Collisions
« Reply #10 on: May 06, 2011, 06:28:34 pm »
There we go again. With a proper level, my method seems way to slow. Framrates drop to 20fps on my galaxy -> Not good :/
So I'm back to square one again. I'm finally so far to say "screw this all, lets get that ellipsoid rolling".

So far I had no success in getting it to work. As said, I want to check if a given object (now defined as an ellipsoid) collides with the world. I measured out, that a ellipsoid with the radius values 76,22,15 (X,Y,Z respectively) would be the optimal choice. But how do I get the collision check running? My code so far looks like this:

Code: [Select]
if(!mPlayerObject.checkForCollisionEllipsoid(SimpleVector.ORIGIN, sEllipsoid, 1).equals(sEllipsoid))
endGame();

While sEllipsoid is a SimpleVector with x,y,z set to the values above, and SimpleVector.ORIGIN is used to tell that I want to check the collision at the current position (0,0,0 in objectspace), without any moving at all. The if clause always returns true, so what did I do wrong? :/ Oh, by the way, The collision modes are set as

Code: [Select]
mPlayerObject.setCollisionMode(Object3D.COLLISION_CHECK_SELF);
 mWorldObject.setCollisionMode(Object3D.COLLISION_CHECK_OTHERS);

Any ideas? Oh, and may there be a better choice for collision detection, since I only want to check IF a collision is happening at the current position? E.g. I dont need that "moving in direction xxx" stuff, just a simple collision true/false check :/

So long,
Kernle
« Last Edit: May 06, 2011, 06:32:15 pm by Kernle 32DLL »

Offline EgonOlsen

  • Administrator
  • quad
  • *****
  • Posts: 12295
    • View Profile
    • http://www.jpct.net
Re: Collisions
« Reply #11 on: May 07, 2011, 01:15:58 pm »
Ellipsoid collision detection is actually a collision avoidance algorithm. It's not designed to resolve existing collisions. If you don't move at all, the algorithm will Most likely terminate without doing anything. Why don't you do the check on the actual translation that leads to the current position?