Yeah, because if the simulation slows down when there are several collisions, it’s bad too…
Someone posted a link to a paper (http://www.peroxide.dk/papers/collision/collision.pdf) which is very interesting.
They do collisions between ellipsoids and tri meshes. To simplify the process, they create a specific ellipsoid vector space (where the ellipsoid is an unit sphere) and they transform the trimeshes coordinates to this space. It simplify a lot the computations and it’s much faster. We could combinate this with AABB auto-generated trees (with adjustable depth) and it would be a very good starting point.
Yes we should use a tree to split up regions.
I did this once for a 2D application, where circles were flying onto a mass of other circles. I was able to create 1 000 000 circles in this way in 1 minute using a quadtree, where other contestants (it was for a contest) only were able to do 100 000 in some hours, not using a quadtree, but c++. The tree ofcourse had some other advantages (because I didn’t really simulate)
For a tree I’d suggest an octree with variable depth, a simple 3-dimensional array would probably also an alternative, but I think it’ll take too much memory.
Hmm… what about a 3-dimensional linked list? Objects normally only move from one field to another (done in constant time in linked list) - But then we also have to think about: should the fields in the linked list of the same size, or should they have dynamic changing sizes, or - do we even want to link the objects directly?
Sparsely populated arrays can be effeciently replaced with HashMaps, which I beleive is exactly what HashSpace does. HashSpace is also multi resolution in the ODE implementation.
As for Oct Trees I think I have mentioned this. ODE has QuadTrees which don’t really make sense for a 3D environment, although I spose are applicable to landscape shaped worlds like battlefeilds. However I have never been able to work out from the ODE docs what way round the QuadTrees are orientated so using them is not immediatly obvious.
I would not worry too much about Spaces yet. We will have enough on our plate getting a basic system using a SimpleSpace going.
I’d think that if this project goes ahead, that putting off triangular mesh collision to later is likely a bad idea. Namely because colliding with triangular meshes is the main thing anyone will want to use a collision engine for. While spheres and boxes would be faster to implement and get the engine working early, putting meshes off too long might paint the project into a corner where adding triangular mesh support is difficult. If this happens, JOODE won’t have much use beyond simple demo programs.
Mark McKay
I think kitfox is just right.
About octrees, spaces and all that stuff, here’s my ideas :
-
Why doing different kind of spaces ? One is suffisant. The distinction between simple shapes and trees could be done at the Geom level. It’s each Geom that is responsible to check if it collides with each other.
-
For trees, imagine a tri-mesh object. We first check if the object we handle collide with an AABB of the tri-mesh object. If not, there’s no collision. If yes, then we subdivide the AABB into 2, 4 or 8 AABB more precise. Then we check collision again. And so on, we stop at a defined step were we check triangles individually.
-
How do we do about the relationship between BodyS and GeomS ? Can have a Body multiple GeomS ?
That’s true… but then you just discarded one of the best ways to optimize calculations.
You have to subdivide your space, to prevent checking everything against everything else.
It’s standard algorithm (a - 1) *(a/2)
so for 5 objects you have 4 + 3 + 2 + 1 tests. It completely kills performance for 10000 objects.
Yeah, but the Geom has to find the Geoms it could collide with. The geom could do this over a space. A always good thing is to use an interface for space, and simply implement the space, we think fit’s best. This way we’re still open to use other spaces.
Yes. This is a very nice and probably also efficient way of doing collisions. As example, if we first specify a bounding sphere that contains the terrain as a whole. Only if another Object collides with the Sphere, it can collide with terrain, so we split up to get more detail. If it still can collide with one (or several) of the subspheres, we have to check there also until we’re at triangle level. If in one step we don’t find any Sphere’s it could collide with, we’re finished and no collision happened.
This is a hard one. If it could gain us some performance we should implement it. (Static joints didn’t seem to work that well for Odejava)
So with that you start onto a new crutial section of ODE: Joints. I’d say we should keep with how it’s done in ode (answering the question above 
) But we tried to do that with the collisions also and now we’ve got a full scaled discussion going of how to do collisions 
- so this can change.
[quote]It’s standard algorithm (a - 1) *(a/2)
so for 5 objects you have 4 + 3 + 2 + 1 tests. It completely kills performance for 10000 objects.
[/quote]
yep it’s O(n²) vs O(n log n), but is there a faster way? That’s Question, are we able to get O(n) ?
I already mentioned a LinkedSpace, where every Object knows it’s neighbors (with whom it might collide). If implemented correctly it could get O(n).
But thats Space discussion - if we do a good interface, we should also afterwards be able to implement such stuff.
ODE allready has spaces kind of hidden like interfaces. I think in the convertion we will end up with abstract classes for the geom supertype and the space supertype. Space division is important, thats allready handled well in ODE with HashSpace. An OctTree space would be really handy in addition.
I dunno what is best for trimeshes. I am not going to worry about it until the other parts of the system are done. Like the LCP solver.
BTW, I have got my development platform setup now. I have translated the skeletal structure of ODE into Java, however the process has lost many attributes. I have put the reverse engineered model in its own package. I do not beleive working off that directly is a good idea, but its nice to have it there for reference and cutting and pasting the bits that are correct. I would say as we implement bits we build up code in other packages. That way we know which bits really are implemented.
The hanging moss algorithm can be extended to 3D to greatly reduce the amount of geometry you have to search through for a collision. Similar to a progressive refinement on an octree collision detection method.
Im sure there is already on in ODE too…But you have to give it the extents of the quadtree, which makes things hard for free flow environments…
Doesn’t ODE/Odejava already have that? Compound objects? IIRC, its even covered in the ode docs…
Dont think that would work arne. Imagine a high speed moving thing over lots of little boxes (the boxes being the terrain). The moving thing would have to recalculate its list everytime it updates because its moving. Which again boils down to an O(n*n) solution (or the 3d hanging moss). Unless I understood you wrong?
BlueSky, you still haven’t told me the difference between the integrators. I can’t find it anywhere on the internet…
D{
heck! I used that hanging moss algorithm (even if extended it a bit) for that contest work and I didn’t know it :o Add a Tree above it (in our case a octtree), and it will also work very well for not evenly distributed points. (The hanging moss has a worst case of O(nn) 1, but with a tree above, it should only have O(n log n) as a worst case) - @Darkprophet: Ofcourse only if the objects don’t move too fast. If things start to move fast you’ll always get O(nn) no matter what - see below.
Ok it will be O(nn) if all objects move fast (that’s independent of the datastructure, cos it could collide with any, so I can’t ignore any objects to test (which is the only performance boost)) and seem to be everywhere, but that’s (should be) very rare. Normally objects keep their position more or less. And then it would be O(n) ! Maybe if we add a speed factor, (O(nspeed). List copying wouldn’t take that long, because the object simply has to ask it’s neighbors for their neighbors. 
Arne
Edit: 1 Maybe it’s not exactly O(n*n), even if the worst case for finding the closest of one object might be O(n), but then the others can’t have O(n) … so it’s probably better - or there is only a factor… doesn’t matter…
Heh, just thought of another scenario for your LinkedSpace. Slow moving spaceship along a plane full of boxes over a long time. This is the same as moving fast in a short time.
From my understanding, the Hanging Moss algorithm divides the world into n number of boxes with t occupants. The t’s are linked together and to find the neighbour, you find which box it is in first, then loop through the LinkedList to see which is its closest neighbour. Similar to hanging moss through a guass filter 
What im thinking at the moment is a scenegraph heirarchy with the heirarchy being dynamically sorted on distance. I’l let you know how that goes…
DP
Yes I know, but it’s not because it is in ODEJava that we can implement it simply.
Hmm… I don’t know exactly, but the one Newton Dynamics pretend to use seems to be more stable.
I think it’s a stuff regarding steps. The bigger steps you have, the bigger error you have. Integrators are stable when they detect collisions between steps, for example (IMHO)
Going back to basics which is essential to this port. I have found that ODE stores its Matrix3 as a a 3 by 4 matrix. This means there is no Vecmath equivelant. It also is very difficult to translate the ODE matrix multiplications as is with type checking on vecmath classes. Look at this:-
/*
* set a 3x3 submatrix of A to a matrix such that submatrix(A)*b = a x b.
* A is stored by rows, and has `skip' elements per row. the matrix is
* assumed to be already zero, so this does not write zero elements!
* if (plus,minus) is (+,-) then a positive version will be written.
* if (plus,minus) is (-,+) then a negative version will be written.
*/
#define dCROSSMAT(A,a,skip,plus,minus) \
do { \
(A)[1] = minus (a)[2]; \
(A)[2] = plus (a)[1]; \
(A)[(skip)+0] = plus (a)[2]; \
(A)[(skip)+2] = minus (a)[0]; \
(A)[2*(skip)+0] = minus (a)[1]; \
(A)[2*(skip)+1] = plus (a)[0]; \
} while(0)
This function is used all over ODE. It is very difficult to translate nicely unless we use exactly the same underlying array structure of floats to store our matrix data. I think therfore we are gonna need our own custom matrix and possible vector datatypes. To make it easy for the user to still use the API then I suggest we supply adapters to our custom classes.
Holy crap !! I don’t understand that code, it looks so crude. Where is it located?
Yep it seems to be a very crude hack. We’d better at least get a basic idea of how and why that works (at least I don’t have any idea) But, yes - if it gains performance, we could use it, but I think it’s not an argument to say: “it’s used everywhere, so we’ll use it also”. If we use this method, we should put it into a nice OO-Design.
And what’s so difficult to change dCROSSMAT(A,a,skip,plus,minus) to A.crossmat(a,skip,plus,minus) Err… plus, minus are that Arrays or Functions (I believe in C you were able to have Functions as Parameters) ???
Well the code itself is just for matrix multiplication, with a hack to make it go in different directions (I beleive thats what inverting the +,- means but I might be wrong)
The difficultiy of porting it though into a typed system where each matrix dimention is its onwn type is that this system more or less can handle the general case of an nxm matrix being mutiplies by a mxq sized matrix. This is not actually possible in the vecmath library.
Since posting I am getting screwed over even more by the way they manipulate the pointers. If you rememebr than in ODE matrices are really pointers to arrays of floats, then look at this function (again with no vecmath equivalent):-
the tricky like is dReal sum,*a,*b,*aa,*bb,*cc,*recip;
meaning sum is jsut storing a float. The others are pointign to floats so in a way are acting as indexes.
thought the actualy memory storage is done to recip. So recip is being used differently to a,b,aa,bb and cc.
Its actually ok to unravle this one. But only becuase I am storing matrices and vectors as arrays of floats now. In vecmath each slot in a matrix is a distinct attribute, the only way to incremenet things is via the getElement(x,y) kind of way. As you can imagine I would have to introduce counters etc. and convert from the single dimentioned scale ODE uses to a 2D scale like the onyl way Vecmath ones can be handled. Not pretty and it would make the job 100x harder.
Hohum. No worries though. I seem to be able to translate this stuff at a reasonable pace. Our project should up for voting today.
Maybe we should really make our own Matrix class that supports nxm Matrices with any n and m. Then we wouldn’t also need extra Vector classes, because a Vector is then simply a 1xn Matrix.
I axtually also don’t really like vecmath, espacially with the distinction between points and Vectors.
Hrmpf. Shouldn’t it be in the voting section by now?
Yeah I know. I will post directly to it 2morrow if it is not up. I emailed them last Sat and again this morning. The actual project space has been setup on the server so everything has been done.
OK. I have taken matters into my own hands. I sent an email a week last Thurs, the Sat after (and setup the actual project on the Sat) and yesterday(Fri) without the project proposal boards being affected.
POST YOUR VOTES EVERYONE!