Okay, but you may agree it’s better if others can actually understand what you’re doing and help you, isn’t it ? I hope you don’t want to be the one and only developer…
So which ways are you going about arbitrary detection collision ?
I never heard about Cholesky decomposition, how useful is it ?
Yeah agreed. I do not want to be the sole developer.
I do not know exactly what a Cholsky decomposition and factorization is. From what I know the decomposition is a reograganization of matrices into a form that lends them to be solved with a Cholsky factorization. Its a 2 step process basically and the end result is that a set of simulataneous equations is solved.
When you look at MathWorld and things, Cholsky stuff is always said to be useful in engineering applications. They are used in ODE to to the stepping in the world. I think perhaps though that they might blow up to be a NP hard problem or something, becuase by defualt in ODE the LCP algorithm is used instead to do the stepping. The LCP algorithm does not allways succeed, you sometimes get the s < 0.0 error when it fails. This does not necissarily mean the system is broke, just the LCP algorithm can’t solve that particular situation. Thus I would like the Cholsky stuff to be working becuase I think it might be more relaiable.
By the way the code reads in ODE I think the cholsky way was the first way that ODE was coded. So it doesn’t seem to take enough parameters to implement all the features the LCP algorithm does, like all the joint feeback and things.
As for arbitary collision detection … well the OBB tree stuff does not provide enough information for the collision system to work. It just provides a boolean collision or no collision answer. So the first thing to try and do is to develop a system that can return the collision point, collision normal and penetration depth.
So I tried reading up on these things, but the latest algorithms are pretty tough to decipher. I found a nice middle ground though I thought I would try to implement that seemed reasonably effecient. It works for convex-convex geometries.
Basically one of the key concepts in all collision algorithms these days is the Gauss representaion of a convex polyhedra. To build this representation you take the face normals (vectors) and project them onto a sphere. So a face in normal space is an area, but this is represented in the Gauss representation as a point on the surface of a unit sphere. Faces in normal space are bordered with other faces by an edge. So you represent this in the gauss representation by joining the points on the unit shpere with edges. Verteces in normal space are points, but in the gauss representaion the become areas on the unit shpere. What ends up happening, is the gauss representation represents orthoganal planes that can touch the features. (it hard to explain 
) Think about a face in normal space. Only one plane or a certain conjugate gradient can be put against it. So on the uni sphere guass representaion the tangetical plane to the vertex representing that face is that same plane. Vertexes in normal space can have a range of planes touching them, and that range is defined by the area they take up on the unit sphere in guass space.
So these planes are really important for collision detection. If two obects are near each other, it is only features that are on opposite sides of the objects need to be compared. You do not need to compare the right side of the box A with the top part of box B. The seperating distance (or penetration distance) is defined by two planes that touch anti-podal (opposite) features. The planes are the links to the guass representaion.
So to compare opposite feates you take the guass representaion of the two objects, giving you two unit spheres. You cut each sphere into halves. You then need to compare the one half of one object with the other half of the other object (twice for each combination of halves).
In order to compare the halves what you can do is project the details of the semisphere onto a plane. i.e. squash the semisphere flat. This gives you a load of lines drawn on a plane. This is known as a planar subdivision. You need to compare two planar subdivisions. So you overlay one subdivision with another and find all the intersections of details. This is a red green algorithm. An edge may cross with another edge at a point. This point represents a plane. So you need to lookup those two edges on each object in real space and work out how far away they are from each other using the plane as the seperating plane. Evertime a vertex is seen in each planar subdivision you need to lookup what area it lies in on the other plane subdivision. This gives you a vertex and a face to measure the seperation distance in real space using the face normal as the seperating distance. You also need to consider face-face distances (which are vertex-vertex situations on the planar subdivisions).
Anyways. The guass map stuff is pretty easy to implement becuase it basically just involves taking the face normals and joining them up. I have not implemented this yet. The hard bit is the planar subdivision comparisons. A naive approach would take n^2 to run. I decided to use a planar sweep algorithm to do it faster. This involves sweeping a line from left to right over the planar subdivisions. You keep all the details ordered by x and … it ends up midly faster. I say midly beucase I think worse case it is still n^2. There are heaps of degenerate cases to consider though which have swamped me. Vertical liines are awkward. Working out which area of a division a vertex is in is hard. Really hard for the first vertex encountered becuase no information is present from the other panar division at that point. To help with that kind of degeneracies I had to extend the planar subdivision concept. If you think about what a planar subdivision looks like for a semisphere it ends up as a load of lines within a unit circle. Now what happens to edges that spanned the two hemisheres when you cut it? Really you need some detail to be found right on the edge of the unit circle. So to make sure that all details on the very edge of the cirlce are considered special (including the left most edges) I actually made extra edges start at the edge of the circle and extend to +/- infinity for each coord (cutting the circle into quadrants). This meant all the left hand details would be considered by the sweep algorithm first for both planar subdivisions. As these were considered first I could then extract region information. (Erm, I know this is really hard to follow, I dunno how to say it better.) Basically it meant that when the sweepline hit the first real vertex I allready had the information about at least two infinite edges from the other planar subdivision available. Its jsut a mannor of working out what face they have in common then to be able to assign a vertex, region. The real point is that this sweep algorithm seemed like a peice of cake to implement but turned out to be really difficult. Its not even that good at performing its job. So I might switch to the naive red green algorithm jsut to get something working reliably. i.e. compare every edge to every other …
The real hardcore algorithms don’t compute the gauss representaions and planar subdivisions upfront. You provide them with an estimate of which plane is likely to be the seperator (the one directly between their centers for example). From this point they measure the distance and lazily and greedy expand the representaions until the find no imrovement on their distance measure. The perform a walk along the features of the two objects (still only comparing opposite features). By giving good estimates you can reduce the time complexity to constant time :o. Cachine the results of collisions between time frames is also a very good stratergy. I think it is even optimal still!
So I think I might chuch the sweep algorithm and go for naive algorithm. Then maybe greedy search as am getting into my search algorithms of late. (Orbital library?)
I have not bothered submitting my collision work so far becuase it does not do anything yet. I could do with some advice on a good way of stitching together edge, vertex and face onformation into a datastructure. Everything really needs to be ordered …
Tom
To continue…
So the current state of JOODE is pretty good. The Sphere demo looks realistic so we have one route of physics working. The fact that box box collisions don’t work I don’t think is a major problem and should be worried about too much. If we get a good convex convex algorithm working we can forget about box-box special case and run it faster by caching results.
The joint infrastructure is working by the fact Contacts work, they are implemented as joints. Joints themselves are really simple, just entries in a jacobian matrix so porting them is a no brainer but I think doing that next is the best idea becuase they really add value to the package.
The space infrastructure is working, we have simple space. So porting the other types would be a good idea, though it does not add as much value as joints until someone want to do real performance with them.
Testing objects can be destoyed cleanly has not been tested. That needs doing.but fingers crossed it might work :-\
Okay, after having read 10 times what you said, here’s some things I believe I’ve understand, please correct me if I’m wrong :
- Cholesky decomposition/factorization is just another way to solve differential equations needed in kinematics
- Gauss representation is just a sort of optimizations that avoid to test polygons that aren’t opposed
- Creating a Gauss map is just moving the face’s normals to a unit sphere
One thing I didn’t understand is : your face is represented only by its normal on the unit sphere, but where are the edges ? You say you just have to “join the points on the unit shpere with edges”, but you only would be joining polygons center, heh ?
After that trick I just can’t understand the continuation. Where do all these planes come from ? Do you divide your unit sphere in halves or in quarters ?
I would be really glad if I somebody could explain me in a way I can understand, maybe with figures. Thanks.
(Note : I’m not completely lazy, and have googled “Gauss map”, but these big equations don’t explain anything… :-\ )
[quote](Note : I’m not completely lazy, and have googled “Gauss map”, but these big equations don’t explain anything… )
[/quote]
Yeah I know what you mean. Its taken me ages to understand it to this point
[quote]Cholesky decomposition/factorization is just another way to solve differential equations needed in kinematics
[/quote]
Yes
[quote]Gauss representation is just a sort of optimizations that avoid to test polygons that aren’t opposed
[/quote]
Yes pretty much. Gauss representaions summerize tangital plane information.
[quote]your face is represented only by its normal on the unit sphere, but where are the edges ? You say you just have to “join the points on the unit shpere with edges”, but you only would be joining polygons center, heh ?
[/quote]
Yes yes yes! This is the key. Once you get your head round this you enter the matrix…
So imagine you have a convex object infront of you and you need to measure its shortest width. To measure a width, you create two parrallel planes that just graze the object, and measure the distance between them. Now if your object has parrallel faces, like a box, then you can see that to measure the width the parralell planes will be orthoganal to the face normals. i.e. there is only one sensical grazing plane for a face. Now think about edges. Edges are found between two faces. There is a range of sensical “just touching” planes for that type of feature. The exact range is defined by the interpolation of the two face normals. With a vertex, which borders n faces, there is a region of “just touching” planes that are applicable.
So this is what the gauss representaion summerizes. Face -> points on the surface. Edges ->edges joining up the points (that represent faces), this means edges kind of go in the opposite direction to how you see them in object space (kinda) Vertics -> Regions.
So if you wanted to find the smallest width of an object you would first create the gauss representaion. Then you would compare opposite features of the gauss sphere.
- Where there was a point (representing a face) you need to find what region (representing a vertex) it is lies within on the opposite side.
- To quantify the actual distance between the vertex and face you would need to go back to the original representation. Then you would use the plane orthogonal to that face, and measure the distance to the vertex on the opposite side. That will be the shortest distance possible between those two features.
3n. Repeat for all opposite features (including edge-edge distances, the seperating planes to use are their intersections) until you can say which is the smallest distance.
Finding the width is very strongly related to penetration depth. To find penetration depth between two objects you have to compare features on one guass sphere with features on the opposite side of the other gauss sphere. That is why we chop them into halves. So you can compare one hemisphere with the other himisphere on the opposite side.
The planar subdivision algorithms are the details by which we compare the two gauss representations. see http://www.lupinho.de/gishur/html/Sweeps.html
I do actually have some lush diagrams… let me go find them…
yes … the link was on the previous page of this thread ( who says they were not lazy? :P>
(only kidding, it was cryptically advertised)
http://homepages.inf.ed.ac.uk/s0570397/planar.sxi
(oh damn, its an open office doc. Can you read that?)
EDIT: Tada! Dia to the rescue for windows, file size 25kb! (though try to look at the open O presentation, its got proper 3D rendered pictures!)
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 :
- Gauss and all that stuff give you opposite features
- Then you just have to compute the distance between all these features
- And then you just have to do some magic that gives you the smallest OBB possible.
(I guess it’s pretty slow and there are better algorithms around there to do that)
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