Projected Gauss Seivel Algorithm

[Richard Baker]

I am using PGS to solve the contact force part of my rigid body simulator (2D for now). It seems to be functional but I can only seem to get a few decimals worth of accuracy.  The algorithm will start cycling between different values.  I realize that due to the lack of uniqueness theorem that there are many solutions to the NCP due to the introduction of friction.  I want to find one solution that works and I feel that this cycling reduces accuracy.  I tried subspace minimization but that doesn't seem to fix the problem. Fingers crossed that someone can help me.  Thank You. 

[fiveworlds]

Floating point numbers generally wind up as heuristics rather than 100% accurate values e.g. there is no way to store 1/3 etc. There are libraries that allow operating on big numbers with higher accuracy  https://docs.oracle.com/javase/8/docs/api/java/math/BigDecimal.html however there is generally a tradeoff between desired accuracy and performance so most 3d software wont implement it instead they run calculations on the GPU. Most GPUs will use double precision floating point rather than floating point leading to more accurate calculations.

[Sensei]

@fiveworlds is right. Read about IEEE 754 resolution. https://en.wikipedia.org/wiki/IEEE_754

Table:

https://en.wikipedia.org/wiki/IEEE_754#Basic_and_interchange_formats

ps. In simple cases, it may help to change the order of operations in the equation. For example, adding/subtracting 1 to 10^-20 will result in truncated fractions..

[Richard Baker]

Thanks for the responses.  As it turns out, I was incorrectly binding dynamic friction to equal zero if there was enough force to break static friction but still zero tangential velocity.  If instead I just let PGS work its magic, the non-zero friction at each vertex cancels out so that an object at rest will continue at rest.

Unfortunately, I don't know much about parallel processing on the GPU.  But that will probably be my next step after extending to 3D.  I suppose in a multi-player online setting the GPU can perform server-side computations such as if a grenade starts to slide or grow after bouncing a few times?

Thanks again. 

[Richard Baker]

I successfully implemented GJK.  It is fast, but narrow phase is a bottleneck because i do GJK many times in the binary search.  I read about the EPA, expanding poly tope algorithm.  

Question:

EPA returns the point on the CSO closest to the origin.  Does this point correspond to the edge/edge or vertex/face to collide first?

[Richard Baker]

I have another question.  It has to do with the interplay of collision detection and contact force. Is it possible to have GJK ignore collision points that are already in contact?  I want to turn off collisions for these points and let Baumgarte correction prevent interpenetration. 

[Richard Baker]

Update:   I am now using Gilbert Johnson Keerthi with margins and expanding polytope algorithm whenever the depth exceeds the sum of the margins.  No narrow phase, no binary search, much better.  My next question is about an optimization I want to use on the contact force side.   A sphere has only one contact point, but a polytope can have many.  For example, a box stacked on another box has up to eight contact points.  I know how to find location, signed distance, and normal vector.  I want to consolidate these contact points into one contact force.  Is it possible?  Thank you.  

[Sensei]

To check whether two objects of any shape have collided, the programmer can treat them as spheres at the first stage, i.e. calculate the min-max bounding box from all points, calculate the center point and the maximum radius. Then, if the distance between two such spheres is greater than the sum of the radii, the objects are too far away to be bothered with. However, if the distance between them is smaller, a less optimal, slower algorithm is performed to check the objects nearby.

Several levels of spheres are used in 3D games. One sphere to cover the entire body. A second set of smaller spheres for all parts of the body. These are checked similarly to the previous step, but instead of comparing triangles with triangles (or polygons with polygons), because they are very slow for the processor, still spheres vs spheres are checked.

People use KD-Tree (3D), Octree (3D) or Quad-tree (2D) to optimize such work.

https://en.wikipedia.org/wiki/K-d_tree

https://en.wikipedia.org/wiki/Octree

https://en.wikipedia.org/wiki/Quadtree

i.e. objects that are close to each other are in the same leaf or in a neighboring leaf.

If an object does not move between frames, it does not need to be removed from the leaf and added to a new one.

With a fixed number of elements, you can use voxels ("volumetric pixels").

https://en.wikipedia.org/wiki/Voxel

 

Remember that in animation up to a certain level, you can reuse calculations from the previous frame(s) in future frames.

 

Edited March 23 by Sensei

[Richard Baker]

Thank you.  More to come.

[Richard Baker]

I am using VSP trees. They also help with painter's algorithm.  My problem is not with collision detection, however, but with contact force. Check out my last post about the optimization I want to use with PGS.  Also, another contact force problem I am having; when I have a force act along a similar line but opposite direction of another force Baumgarte stabilization makes the termination criteria bad because the resulting acceleration is not 0 due to the contact force pushing objects away.  This causes PGS to stall.  

[Richard Baker]

As far as the face-on-face contact problem goes, I realize that I can't remove contact points willy-nilly. But it is important to make sure, each contact normal is facing the same direction. Sometimes they don't due to numerical issues. So, I remove contacts that don't face the same direction, as the normal returned by the GJKEPA.  Sometimes objects will interpenetrate a tiny amount, and pop out on another side, resulting in a bad GJKEPA normal. This is particularly the case for very neat stacks.  Messy stacks don't have this problem. But it seems as long as I used small enough time steps, this doesn't happen.  Is this the correct way to do it? 

My next question: What is the best way to find contact data? When GJKEPA returns a normal end location, that is all I need to feed into my contact force solver, when one of the objects is a sphere. For polytopes this is not the case. I am currently going through all vertex face and edge combinations if a collision was detected. This seems inefficient. 

Also, I want the geometry of the objects to be consistent between collision and contact forces. But because I am using margins with collision detection, all the edges and vertices are beveled.  Is it sufficient for the signed distance of the unenlarged objects to be negative or less than the sum of the margins?

Thank you.  I did not have a computer for a few weeks.