Pure Java Port of ODE - planning/feasibility

Game Mechanics
#221

Here is the webpage from the collision paper I was trying to replicate:-
It features a presentation almost identical to my own! Haha.
http://www.cs.unc.edu/~geom/DEEP/
I have realized a better what though to solve the problem. Um, Instead of projecting the guass representations onto a planar subdivision, represent the guass map as a 3D sphere cut by planes. Use these planes as the deliminators of a BSP tree and assign the guass representation’s features within the BSP tree, this can all be done upfront once. Then, when it comes to comparing the two representations you can use the BSP to quickly lookup opposite features by spacial positions. The main bulk of the algorithm remains the same (i.e. walk along the features until you can’t get an improvement in your penetration depth) but it cuts out the planar subdivision part which has degeneracies associated (and its also quite hard to implement a fast planar subdivision algorithm as I have found out).

Thats what I was thinking currently. I have not got time to do it though :frowning:

#222

Im interested, how can the simplex algorithm work for collision detection? Its meant to find the optimum solution to a problem given a set of constraints. If you imagine two lines in a graph, it finds the intersection point, put 3 lines, it will find the point that is the highest, similarly with 4…etc…

Unless theres something im missing ?

DP

#223

Have a look at the abstract of this:-

[quote]http://portal.acm.org/citation.cfm?id=285860
[/quote]
It kind of estimates the collision point by refining an bounding polyhedra between the objects or something. I have not looked into it all that much becuase I feel all those algorithms are

  1. hard to understand (but thats global to all these algorithms :))
  2. inprecise
  3. can go into infinite loops
  4. not that fast … compared to the latest methods

But if Arne thinks he could implement one of them then cool. It would immediatly be the defact method for JOODE.

#224

The article seems to be very promising :slight_smile: They very mentioning a constant complexity, I actually can’t think how this should work … hmm they were mentioning s.th. about a good heuristic for a starting point - hmm if they use the point, that was the deepest last step, it really can work pretty fast.
it seems they are also able to calculate the penetration direction - nice :slight_smile:

My idea with the simplex algorithm was to use it to find the closest point (better: plane going through that point) to the other object (or an optimum if you want it that way :wink: ) and then do the same with the other object. And then calculate the distance between the two planes - and voila you would get some kind of penetration distance.
But I’ve realized, that there are situations, where it would return a penetration distance, where the objects don’t even intersect!
So it’s probably not so wise to use this approach :-\

#225

Yeah the DEEP algorithm is super fly. Its starts with a guess and then tries to improve upon it until it cannot. Really it will only get stuck on a local minimum if the guess is on the wrong side of the polyhedras. So taking the average of their center points or something will yeild pretty good results if the objects have never met, otherwise caching the last calculated penetration direction will also yeaild really good results. Even for stuff like Box Box collisions the algorithm could save on the number of tests. Whether that will translate to faster box box collisions all depends on the algorithms overhead, I suspect it probably won’t but not by much.
For the advanced reader I suggest imagining what happens if you only partially represent the gauss representation. This will mean objects will only have a penetration depth for a certain orientation … This essentailly means you could represent things like planes or terrain using the same system.
the only problem I have with the algiorithm, and what nailed me last time when I tried to implement it was the planar subdivision bit. Projecting the gauss representation onto a plane. There are lots of special cases you need to deal with. Also note that a curved surface does not map onto straight lines when projected (which could cause errors). I have a solution though that I think simplifies the algorithm somewhat. Instead of projection you can deal with the gauss representations directly. Cut the gauss representation (recall a unit sphere with edges on its surface) into spacial divisions using a BSP tree. This will allow fast lookup for features. Then to do the comparison between gauss representations you can take a feature from object A, translate its coords representing the relative orientation between the 2 objects + 180 degrees, then pass it into the BSP tree for B. As it decends the tree you can be testing it with the important features it encounters, most of the BSP functionality will be replicated from the contruction code. So from that you will have a set of features that interest that feature on the opposite side. I really can’t see any real computational penalty from doing it this way, and I think it will be more accurate and without special cases to consider. Anyway this is yet again a rable by me. Although I said I could not afford any time at the moment the gravitaion pull of JOODe has sucked me in again so I am writing the BSP code at the moment :frowning: