Pure Java Port of ODE - planning/feasibility

[darkprophet]

And then you just have to do some magic that gives you the smallest OBB possible.

If  you can do that in real-time with competitive fps, i'l give you all my money. 

DP

[Amos Wenger]

Oh..
By "with competitive FPS", you mean, a Quake 3 level running with 60+ characters at 100 FPS ? 
If I had time to lose, I would have tried that, since I'm sure there's a mean to do that. (That mean would probably be to buy a quadri-core workstation with two ATi X800 in parallel, but.. if I succed with that I'll be refunded, heh ?)

[t_larkworthy]

And about OBB trees I think it's really possible to use it in JOODE, why not ? If the algorithm you had just give you if there's a collision or not, then you can test the two geoms and actually find the collision point, the depth, and the normal, heh ? You just need to adjust the algorithm a little bit.

Oh yeah. The OBB algorithm is just the first step to determine quickly whether there was a collision or not. Then you have to run another algorithm to get the proper information. The OBB algorithm does provide with some helpful information though. It does give a worthwhile guess to where the proper collision might be, which can be used in a feature walking algorithm as the initial conditions.


Right! Lets implements some joints..........

Games published by our own members! Check 'em out!

[t_larkworthy]

.... Hmmmmm.  Joints are not going so well......
I have implemented Ball and Hinge joints but neither works. Both seemed very straight forward to port, so I doubt I made two catastopic errors. This makes me think something is broken deeper down .... curses!

[t_larkworthy]

OK. Well to give me something to try the joints out on I am gonna intergrate JAMA with the project so we can use their cholesky code as the alternative intergrator

[t_larkworthy]

see seperate threads for updates....

but I am leaving for a few days now. Back to coding Sat.

[t_larkworthy]

OK I think Joints are essentially working now. I think all fundamental areas of JOODE are working. We just need to fill out the project with more functionality lifted from ODE.

[arne]

OK I think Joints are essentially working now. I think all fundamental areas of JOODE are working. We just need to fill out the project with more functionality lifted from ODE.

Nice

I start to have more time now (holidays ), so I think I'm going to take the OctSpace on again. We also should focus on implementing Geoms and Collisions  - do we have there already a good way of dealing with that? I am still thinking on a more general way of dealing with that then implementing all combinations of collision-scenaries.
Box-Box Collisions still don't work, right?

And also Ask_Hjorth_Larsen seemed to be interesting in doing some stuff (he wanted to do some math again)

[t_larkworthy]

Oh cool Arne. Yeah getting OctSpace would be great, maybe you should try porting QuadSpace first though as it is a similar problem and at least you have reference code for that. But its entirely up to you.

I am still thinking on a more general way of dealing with that then implementing all combinations of collision-scenaries.

I agree. Getting convex polyhedra colliding would be the best way. I have decided the route I was persuing last time is not the best way. I have a new idea. I do not have time at the moment though now. I was lucky to have a few hours spare last night. I might have another few again tonight but I have to do an assignment first .. damn uni, it doesn't half get in the way of learning.

[arne]

I just remembered the simplex algorithm and I think it could also be used for collision detection - maybe for the trimesh stuff. I believe it could help for the convex polyhedra colliding.

And yes I think I will look into the code of the Quad-Space - but I don't think it's implemented as I want to implement my octtree space, but lets see

Games published by our own members! Check 'em out!

[t_larkworthy]

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 :-(

[darkprophet]

I just remembered the simplex algorithm and I think it could also be used for collision detection - maybe f....

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

[t_larkworthy]

Have a look at the abstract of this:-

http://portal.acm.org/citation.cfm?id=285860

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.

[arne]

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 :-(

The article seems to be very promising 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

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 ) 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 

[t_larkworthy]

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 :-(