Author Topic: Speed difference between two different ways of collision checking  (Read 10908 times)

Offline paulscode

  • double
  • *****
  • Posts: 863
    • View Profile
    • PaulsCode.Com
There are a couple of ways I am considering to interact with a terrain via the mouse:

The first way would be to make each square of the terrain its own individual Object3D, and use the World.checkCollision( SimpleVector, SimpleVector, float ) method to determine which grid square of the terrain that the user clicked on.

The second way would be to place the entire terrain into a single Object3D, and generate an actual collision event, then call the CollisionEvent.getPolygonIDs() method.  This could be used to determine which grid square of the terrain was clicked on by searching all polygons in the terrain for a match.

Is there likely to be a significant performance difference with either method, or is there a different way all-together to accomplish this?

Offline Melssj5

  • double
  • *****
  • Posts: 724
    • View Profile
Re: Speed difference between two different ways of collision checking
« Reply #1 on: October 16, 2008, 12:29:16 am »
I do not know about the performance but there is an issue about precision.

A big terraing gives you a precision of a poligon size, and a lot of small squares gives you a presicion of a whole square size. Which is the idea of this collition listening? I can imagine for example placing a circle under a player on a game like warcraft!
Nada por ahora

Offline paulscode

  • double
  • *****
  • Posts: 863
    • View Profile
    • PaulsCode.Com
Re: Speed difference between two different ways of collision checking
« Reply #2 on: October 16, 2008, 12:45:44 am »
Players, npc's, and objects in my game will all move from square to square, rather than from point to point.  The size of each grid will be about the width of a normal character.  Now, this is not going to be like chess where things hop around from square to square, though.  Movement will be smooth as in any other game.  The only difference between this and, say warcraft, will be that the character will always come to a stop on a grid square, and never between grid squares.  This will reduce the amount of information that I needs to be transferred between client and server, and it will simplify sanity checking server-side.  Also, since each grid square consists of only 2 polygons, I don't see there being a huge precision difference between the two methods, anyway.

--EDIT--
Oh, and I forgot to mention the main reason I came up with this idea in the first place:  To simplify path-finding!  I've already written an algorithm for some of my 2D games, which will translate over to this game with zero changes.
« Last Edit: October 16, 2008, 12:55:57 am by paulscode »

Offline paulscode

  • double
  • *****
  • Posts: 863
    • View Profile
    • PaulsCode.Com
Re: Speed difference between two different ways of collision checking
« Reply #3 on: October 16, 2008, 01:01:20 am »
So I guess what my question really boils down to is this:

Is there a significant performance difference between 1024 Object3Ds with 2 polygons each, vs. 1 Object3D with 2048 polygons?

Offline fireside

  • double
  • *****
  • Posts: 607
    • View Profile
Re: Speed difference between two different ways of collision checking
« Reply #4 on: October 16, 2008, 02:40:47 am »
Have you thought about making the grid theoretical based on x/z distance?  I'm just curious because I'll eventually be doing something like this but I'm wrapped up on an unrelated project right now.  I mean, if you know the point in terms of x,y,z, do you really need to search anything at all?  If you keep objects marked on a table, it doesn't seem like it would be necessary.  I don't even know if you can get the xyz point of a terrain or not, haven't checked into it that far.
« Last Edit: October 16, 2008, 02:46:57 am by fireside »
click here->Fireside 7 Games<-

Offline paulscode

  • double
  • *****
  • Posts: 863
    • View Profile
    • PaulsCode.Com
Re: Speed difference between two different ways of collision checking
« Reply #5 on: October 16, 2008, 02:59:33 am »
Have you thought about making the grid theoretical based on x/z distance? 
That would of course be the ideal translation of a 3D map into a 2D one, but at this point I do not have the required knowledge to do something like that.  It appears that when it comes to collision detection the most precise I can get is down to the polygon level.  Perhaps that isn't the best way to interact with the terrain via the mouse, but it is the only way I have found ATM.

I don't even know if you can get the xyz point of a terrain or not, haven't checked into it that far.
To be honest, I don't either, but just from what I have seen from the JavaDocs about the collision methods (BTW, I have no experience actually using them yet) you can only detect collisions on either an object or a polygon.  I suppose you could do some kind of additional math using whatever ray you had pointing at the terrain, in order to determine the distance at which the intersection occurred (I recall seing a formula related to something like that online).  That could be converted into xyz coordinates (at which time the y coordinate could be disregarded to end up with 2D coordinates).
« Last Edit: October 16, 2008, 03:02:02 am by paulscode »

Offline fireside

  • double
  • *****
  • Posts: 607
    • View Profile
Re: Speed difference between two different ways of collision checking
« Reply #6 on: October 16, 2008, 04:23:15 am »
Looking through the docs, I noticed PolygonManager has a getTransformedVertex, which returns the vertex world coords.  You could possibly take an average of the 3 vertices and then find which square it fell in on a world grid. Might not be accurate enough for my purposes.  I'm not sure.  What might work is to add a higher vertex grid that was invisible when there was a fight.
« Last Edit: October 16, 2008, 04:34:38 am by fireside »
click here->Fireside 7 Games<-

Offline EgonOlsen

  • Administrator
  • quad
  • *****
  • Posts: 12295
    • View Profile
    • http://www.jpct.net
Re: Speed difference between two different ways of collision checking
« Reply #7 on: October 16, 2008, 09:32:19 am »
So I guess what my question really boils down to is this:

Is there a significant performance difference between 1024 Object3Ds with 2 polygons each, vs. 1 Object3D with 2048 polygons?
The latter should be faster especially when using an Octree on that object.

Offline paulscode

  • double
  • *****
  • Posts: 863
    • View Profile
    • PaulsCode.Com
Re: Speed difference between two different ways of collision checking
« Reply #8 on: October 16, 2008, 01:25:17 pm »
The latter should be faster especially when using an Octree on that object.
Thanks.  Yes, I also forgot to consider the fact that a lot of vertices are duplicated when each grid is on a seperate Object3D from all the others.

So what would you recommend is the best way to generate the collision event?  I am starting with a position and direction vector.  Should I create an invisible Object3D and "fire" it into the screen so that it impacts with the terrain, or is there a better way to do this?  (I don't suppose World.checkCollision()  actually generates a collision event, or does it?)
« Last Edit: October 16, 2008, 01:28:35 pm by paulscode »

Offline Melssj5

  • double
  • *****
  • Posts: 724
    • View Profile
Re: Speed difference between two different ways of collision checking
« Reply #9 on: October 16, 2008, 04:15:24 pm »
Is it posible to have an invisible Object3D??? added to the world and built????? Setting the maxium transparency doesnt make invisible objects.?
Nada por ahora

Offline EgonOlsen

  • Administrator
  • quad
  • *****
  • Posts: 12295
    • View Profile
    • http://www.jpct.net
Re: Speed difference between two different ways of collision checking
« Reply #10 on: October 16, 2008, 04:59:58 pm »
(I don't suppose World.checkCollision()  actually generates a collision event, or does it?)
Everything collision related generates a collision event. Even the calcMinDistance-methods do.

Offline EgonOlsen

  • Administrator
  • quad
  • *****
  • Posts: 12295
    • View Profile
    • http://www.jpct.net
Re: Speed difference between two different ways of collision checking
« Reply #11 on: October 16, 2008, 05:00:41 pm »
Is it posible to have an invisible Object3D??? added to the world and built????? Setting the maxium transparency doesnt make invisible objects.?
You can use an empty Object3D in that way. If that is of any use...i'm not sure about this, but you can do it.

Offline paulscode

  • double
  • *****
  • Posts: 863
    • View Profile
    • PaulsCode.Com
Re: Speed difference between two different ways of collision checking
« Reply #12 on: October 16, 2008, 08:38:02 pm »
Is it posible to have an invisible Object3D??? added to the world and built????? Setting the maxium transparency doesnt make invisible objects.?
Color (0, 0, 0) is invisible, so a completely black texture on an Object3D with transparency would make it invisible.  Of course I've never actually tried this, but it seems reasonable.  Looks like I won't need to do this anyway since the collision event will be generated.  Makes things a LOT easier!

Offline paulscode

  • double
  • *****
  • Posts: 863
    • View Profile
    • PaulsCode.Com
Re: Speed difference between two different ways of collision checking
« Reply #13 on: October 16, 2008, 11:46:07 pm »
Looking through the docs, I noticed PolygonManager has a getTransformedVertex, which returns the vertex world coords.  You could possibly take an average of the 3 vertices and then find which square it fell in on a world grid. Might not be accurate enough for my purposes.

That will work nicely for my purposes, since I am not looking for anything more precise than a square.  This would always return the coordinates for the center of a polygon.

--EDIT--
I found that formula I was talking about, which looks like it could be used to get an exact point.  Rather than try to copy and past something I don't understand very well myself, I'll just point you to the web address: http://www.gamedev.net/community/forums/topic.asp?topic_id=511368 (the two posts by oliii are what you want to read)

You could take the vertices of the polygon that was collided with, and use them to define a plane, then plug that into the formula along with your position and direction vectors, to get a distance.  That could then be used to determine the exact 3D coordinates for the collision.
« Last Edit: October 16, 2008, 11:51:01 pm by paulscode »

Offline EgonOlsen

  • Administrator
  • quad
  • *****
  • Posts: 12295
    • View Profile
    • http://www.jpct.net
Re: Speed difference between two different ways of collision checking
« Reply #14 on: October 17, 2008, 08:55:19 am »
You may also use calcMinDistance for this. Just calc the distance from position to the next polygon along the direction vector and multiply the result with the direction vector and you have the intersection point in world space.