Thank you for posting all this valuable information (we actually should save that somewhere in the project, so it doesn’t get lost)
I think I’ve understood most of the stuff, but I’ll also look at the links you posted, but not today anymore I think.
When I’ve some time (probably after christmas) I’m going to try to work on the simpler things (spaces, joints).
Cheers
Arne
Looks like this effort is really going well! Sorry I havn’t been of any help, work has taken pretty much all my time.
Is the intention still to combine JOODE with Odejava - i.e. replace the JNI bindings with the new ones (or more to the point, are the people interested in JOODE interested in using JOODE with Odejava when it’s ready?) I am quite interested in doing this, as the Odejava OO design has suited my projects, and I use the XODE parser extensivly. I am pretty certain I will be able to dedicate some time when the time comes to adapting Odejava to use JOODE, hopefully that can be my contribution.
Will.
Okay cool.
(Hey, thomas, don’t you think I’m using Windows, heh… you may not have looked to my avatar…)
So with the Gaussian representation it’s easy to compute an OBB around any convex polyhedra ?
What I didn’t understood is the plane story… What are they used for ? How does it help to compute penetration distance ? Or to detect collisions ? Or are they used only to compute distance between the two polyhedras ?
Is this used when you know that there’s a collision and you want to determine penetration depth, or is it used if there’s actually a collision ?
The planar subdivision algorithm with all these lines is somewhat obscure too… I’ll read one more time your explanations and try to understand that too.
hehe. Glad I am being as clear as mud 
So the important thing when calculating penetration distances is that you only need to consider antipodal features (opposite). So the gauss representation summerizes the direction that is important to each feature.
The planar subdivision stuff comes in as the nitty gritty of actually working out which features are opposite at a reasonable speed. You need to consider one half of a sphere against the opposite half on the other (opposite features). To work with the gauss representations it helps to flatten them. So each hemisphere becomes a planar subdivision. The features on the semisphere of the guass representation become lines and vertices on a planar subdivision. No you just need to work out which features on one planar subdivision intact with the features on the other planar subdivision. Doing this quickly is not trivial. The naive approach is jsut go through every item on the planar subdivision and compare it to the other. Quite slow :-(. So there are all these algorithms for doing it quicker. have a look at the applet I posted for an overview of the sweep algorithm.
So all this fiddling around does is tell you which featers on the objects are opposite to save you computations for the penetration distances. It does not tell you the distances between the objects. From the above stuff you get a list of features that then need to have the distance calculated using the original real space representations. For a distance measure you have to decide what you parralell seperating planes to measure distance orthoganal to. This can be extracted from the gauss representation.
[quote]So with the Gaussian representation it’s easy to compute an OBB around any convex polyhedra ?
[/quote]
The guass representation will not help with OBB calculations becuase it does not contain any kind of distance measures. A really big box will have the same gauss representation as a really small box (that is alligned exactly)
The OBB stuff in general only helps you to find out if a collision occured very quickly but in JOODE you also need to know the details of the collision. Where it happened, the collision normal and the penetration depth. All the stuff I have described so far is part of the story in calculating these quantities QUICKLY.
Have a look at the paper I put up in my collision resources. It is the main paper I have been working from. It starts by going on about minisky sums.
(right I am on holiday at the moment so I can’t really talk too much … I am in an intenet cafe but I will be working on JOODE again very soon)
Tommo
Oh okay. I think I’ve understood everything now. My mistake was to consider Gauss representation as “the solution to all our problems” !
About OBB : If I’m right, yes you can compute an OBB around an object, because :
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.
If you can do that in real-time with competitive fps, i’l give you all my money. 
DP
Oh…
By “with competitive FPS”, you mean, a Quake 3 level running with 60+ characters at 100 FPS ? ;D
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 ?)
[quote]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.
[/quote]
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…
… 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!
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
see seperate threads for updates…
but I am leaving for a few days now. Back to coding Sat.
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)
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.
[quote]I am still thinking on a more general way of dealing with that then implementing all combinations of collision-scenaries.
[/quote]
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.
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
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 
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
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
But if Arne thinks he could implement one of them then cool. It would immediatly be the defact method for JOODE.
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 :-\
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