[ODE] new trimesh vs trimesh code

Oleh Derevenko oder at eleks.lviv.ua
Fri Sep 14 01:45:16 MST 2007


From: "Jon Watte (ODE)"
To: "Oleh Derevenko"
>> corrections would not cover complete scope of collision related code 
>> then. And I can't fix that because it is impossible to implement reliable 
>> hashing for unlimited data size in fixed size hash table.
> You leave it, or you fix it.
> Merging contacts through hashing is totally possible, although you have to 
> examine 27 (or 8) hash buckets for potential neighbors to merge, rather 
> than just the bucket you find.
> Or, because collision merging is an inexact art anyway, don't merge if two 
> contacts happen to fall in different buckets, even though they are close.
Well, I'd predef doing this way rather than examining the neighbours. First 
of all, examining all the neighbours may spoil all the timing benefits from 
the hashing. Another thing that curently, contact points are groupped by 
rounding the position coordinates to 1e-4 precision - that makes neighbour 
buckets very small (a cube with edge of 1e-4). However including several 
close contacts usually makes final dynamics calculation equation system 
worse, as far as I understand.
Also, similar function in trimesh-box collision merges contacts only when 
both position and normal are close. In trimesh-trimesh the new algorithm 
averages mismatching normals if positions coincide. As to my opinion it must 
be checked if it is legal to do such averaging. If all further operations 
are linear, well the normals might be averaged. However if there are 
nonlinear laws used in calculations this contact with average normal will 
not give the same result as two individual contacts.

> It sounds to me as if the only thing needed to make this code "correct" is 
> to make sure that, when you get a hash collision, only merge if the two 
> contacts are in fact "close" to each other. But I haven't looked at the 
> code; I only go off of your description.
Well, if it is acceptable to have several close contacts occasionally not 
reduced to one, then yes - it is only necessary to check the contacts to be 
close. Another direction is to additionally do an old-style linear scan if a 
hash bucket is full and none of contacts in it match the current one. Also I 
would say that the hashing function itself needs slight improvement because 
now it only uses low 8 bits for table item selection and ignores rest 24 
bits of 32 bit hash value.

Oleh Derevenko
-- ICQ: 36361783

More information about the ODE mailing list