Bodies not detecting collision with my player

[Julio Jerez]

well I am crossing my fingers and I hope that will work.

The tetrahedral is an ideal building, because satisfy many conditions that can be all deduce from the geometry, for example for example you can impose a condition that the perturbed the volume can never be less than some positive value. also the tetrahedral only have on local minimal, this means that as long is does not flip the shape will tend to recover it zero energy position. This si no the case for a box, which has many local minimal of zero energy.

The think is that any convex volume can be represent by a set of N tetrahedral, and any close manifold shape can be decomposed into a series of voronoid convex volume, so any close mesh can be easily converted to a tetrahedral mesh by doin those two steps.
The cool thing is that the algorithm extend to user specified resolution. so we do no have to worry about that too much, the important part now if to have a robust solver.

Her is an example how to do a Box as a series of joint tetra.
one is the systematic generic, which is good for the algorithm I described above.

https://www.ics.uci.edu/~eppstein/projects/tetra/

the second is a hand code special case that does with only five Tetra of more regular side.
This is the method use by a technique called Marching Tetrahedra algorithm,

This is actually very, very interesting because this one allow for much lower representation of a mesh.
and then use ISO surface reconstruction for calculate weights for higher resolution mesh.
This is the technique I am going for.

but I am getting too ahead her, now I am going to make a demo that show a simple cube made of tetra and another that represent a beam of cubes. see how that goes and see if all my asumptions and expectation are justified.

[JoeJ]

Just spotted a indexing bug in my Vulkan async compute setup.
It works now and it works great.

Queue1 has 100 x 1 wavefront dispatches with memory barriers in between.
Queue2 does the same but on another memory buffer.
Execution time exactly one half of doing it serially. Yeah!

[Julio Jerez]

Ok now I added a small routing that take a rectangular box and make on five tetrakedras.
I also add all the background work for making a functionality. Later when everything is working this routing will be the at the core of the function that will approximate a mesh by tetras (marching tetrahedral algorithm) for now I just render the boxes.

on this.

So if the volume comes close to zero the tetrahedron knows it is in trouble, and fliped if negative.
I think this can work, but i'm still worried what would happen if some tetras in a body get fliped, some planar, some ok... In the worst case can this cause some chain reaction of chaos?

I remember i tried to make a tetra constraint too and how i failed on this.
I did not find a equation that resolved it to it's initial state without causing the effect of an unwanted external force.
I've spent months on this, got crazy

Oh but is not that trivial, but at the same time it is when you use Calculus of Variations.
There is not check or hack or anything like that, a volume preservation forces is a natural force that will always make the shape preserve its volume and shape.

I am not sure how familiar you are with Lagragian dynamics, but using that technique you can come up with any constraint force that you want, realistic or fake, depend on how correct you model of the object you are simulation is.

In the case of a solid represented by a tetrahedron, you can say this: when the solid is a rest, its volume is also a rest, but if it goes under some small deformation, then you can assume that the will be a change on the potential energy that opposes the deformation. Here is where lagrange equation comes handy.
Lagrange dynamics says that the conservative forces acting on a particle are the negative of the gradient of the potential energy of that particle. So if we can come up with and equation that model the potential energy of the particle that's all we need.

I propose we use this criteria, the volumetric potential energy of a particle is proportional to the squared of the different of its volume and its rest volume.
for a given tetrahedrum, V (p0, p1, p2, p3) the volume is given by:

Code: Select all

V = (p1 - p0) x (p2 - p0) . (p3 - p0)

the potential energy would be ;

Code: Select all

E = K * (V - V0) ^ 2

the force acting one each particle is then given by.

Code: Select all

d (E)/dx = sum (K ((V - V0) ^ 2) / d(x, y, z))

we place that on Mathematica to get the expression and the result of that, is the restoring force that will always try to make each tetra to come back to its original shape.
even if the volume becomes negative, this restoring force will force the volume to keep its shape.
I have not added that yet because there is still lot to do, but thrust me tetra flipping is not a problem at all.

[JoeJ]

I am not sure how familiar you are with Lagragian dynamics

Totally not. I don't even have any reasonable background on linear algebra, never learned how to solve a set of linear equations in schools, etc.
Today matrices are still just the typical transformation stuff to me, but i never used them to do anything else.
So, if i read some article like this: https://www.toptal.com/game/video-game-physics-part-iii-constrained-rigid-body-simulation
It makes sense to me but there is just too much stuff i'm not familiar with and i would get stuck early if i'd try to implement.

What i should do is to make a very simple simulator by setting up constraint equations manually (3 point masses chained by 2 distance constraints in 1D).
Then bring it to 'common' shape by turning it into matrix form, use a simple solver like gaussian elimination to get the same solution like my handcrafted solutions.
Then start to see if this already contains concepts like lagrange / jacobians, or how i can modify things to use them as an alternative.
Finally increase dimensions, add some more constraints, ...
At this point i'd probably have a basic understanding, start to see the advantages of those things, be able to utilize some fruits from thousands of years of math research.

And i would be able to understand your 3rd equation But it makes some sense and see it should work this way.

[Julio Jerez]

last night I plug that equation I wrote in Mathematica, and what do you know.
The expression for the volume force come out to be a very intuitive one.

It turns out that the force asserted by the volume deformation is proportional to the volume changes time the area of the face opposite to the each particle on the tetra. That make so much sense that is embarrassing no to figure out earlier. In fact this is so much more robust that it may not even need the springs but I leave as options. and yet the Tetras will never even flip.
I started to write but is not ready yet.

I am still no sure how to come up with a dissipative energy function for volume deformation, but is sure seem that as a volume deforms the speed at with deform should act as a friction force. but still do no see how to relate the particle speed to volume deformation, I am sure there should be a chain rule derivative, but for now I use eh particle velocity a s the damping force and se how that goes.

[Julio Jerez]

Hey Joe, check it out, I added the volumetric force, and is all as I envisioned.
please check it out and see if you can get any tetra to flip. (I put to yo it is no possible )

the cube look unimpressive, because this is a simple cube with no tessellation, but even there you can see the potential already.

Once I add a function to calculate the Linear Blend Weight for a higher resolution mesh using the barycenter coordinate of the vertex inside each tethehedra and the weights coefficients that weight the vertex of the tetra. then is would be more impressive. we will be able to draw any irregular mesh as soft body.
There are some more advanced algorithm to calculate weights, all base on least square approximation, but I will try the naïve the Bari centric linear blend first and see ho that goes. maybe that will be enough.

for the user point of view the set up is as follows:

-Approximate the mesh with marching tetahedra using NetwonMesh.
-Calculate the skin weight for the visual mesh.
-Build a finite element solid model by creation a solid NetwonSolidDeformable collision
-Make a dynamics body
-run the simulation

next I need to do two things:
-a coulomb friction model.
-complete the force build up, to make rock solid stable.

[JoeJ]

Behaves very nicely
No flipping, but spinning / jitter if you drag it slightly down. Probably caused by picking force distribution?

Need to think about usecases. Low resolution models like that cube appear yery interesting to me.
Bending can be refined by graphics, performance is no issue and still should be good for most related gameplay ideas.

What can we set per vertex / edge / tetra?
Static, mass, density?

[Julio Jerez]

the picking does is completely invalid, erroneously apply a force to the whole body instead of a force the point, this is why jitter if you pressed down. you can ignore it for now until I get a better pick force.
At the moment I am using hard coded values, but yes we will be able to set stiffness and damping per edges and per tetras volume. The mass is set in the body just like other dynamics bodies.
The box will be the building block for voxelizing arbitraries continues, I have not worked on that yet but I have some ideas that will try this weekend. The visual representation is important.
But yes you get it, a discrete tetra approximation is a good way to work out the performance issues that are typical of tool that do voronid tetrahedralization, because has very little control the size.

tonight I will add the second part of the volumetric force with is the internal friction.
this is a force proportional to the change of the volume of the tetrahedral. you can think of a force that general internal heat and oppose the movement.

wit that force we will have any kind of behavior, for very stiff but very plastic, to very elastic and jumpy, so very soft and malleable.

[Julio Jerez]

Joe I committed a test with a collision of boxes, and 18 x 2 x 2 column, I am no going to say anything that , just check it out dude.
Ha, I forget check out how the beam bulges naturally as an emergent behavior.

[JoeJ]

Nice Jelly brick. And yes the bulge on it's bottom shows it's truly volume based.
How's BigO? You probably mentioned already but i can't find.

[Julio Jerez]

what does this means?

How's BigO

I found out last night that the volume stiff ness is a little problematic the way is defined.

will define as a normalized function like this:

E = - 0.5 * K *( (V - v0) / v0) ^ 2
instead of
E = - 0.5 * K * (V - v0) ^ 2

That way the power will no depend of the size of the mesh of the tetrahedral. as it is now I have to recalibrate it if change the size, and that could be hard of the user.

[JoeJ]

what does this means?

How's BigO

I mean the runtime in relation to vertex count

[Julio Jerez]

I adds an extra loop proportion to the number of tetrahedras.
I am guessing it will add another loop since to make stable I have to uses implicitly derivative, that is usually another space matrix multiply.

all in all it will be about 4 to 5 time slower than a Verlet based system using edge length projection.
But I would no touch a Verlet nonsense even with a ten foot pool. To me any one who even consider a verlet solution, is because is has not idea what the math mathematic. In fact a Verlet energy function can not be used in a lagrangian potential energy, to get the forces, it has to be used as a workless force on the right side of the equation, and that leads to systems that are many time unstable.

This system is physics based therefore it integrates nicely with the rigid body solver, so if we have to limit it to a small number of tetras, so be it, however so far it seem very efficient.
and most importantly is extremity parallelizable, to a point that multiple piece can be resolved using the same kernel. so this will probably be the fist GPU system in newton.

[Julio Jerez]

wow, I already spend three days trying to exposit some useful model form tetgen, and I am quite disappointed for multiple reasons.
1- tetgen licence is AGPL3 which mean I can not really integrate on with a free zlib tool like Netwon.
2-I try to export some simple models and it work grate. however the move I try to export more complex model is crashes all over ether place, and the place are practical irreproducible because the code use randomize algorisms. which to me is a sign of bad algorithm.
I think it crash on the model I submit at input because it expect the input model to be wha they call a PLG mesh, and this is hard to get on free models.

I try to write me own version using the Jonatan Shewchuk algorithm but this is not a simple task, in fact is quite hard. Mayeb I try that later.

I think I will try the iso tetra surface approximation, which seems more attractive because of its simplicity and because is adapt to any kind of mesh, no only close manifolds.
this paper seem very atractive, so I will check it out.
https://people.eecs.berkeley.edu/~jrs/p ... uffing.pdf
anyway I will no spend more time on that. an move on to get the rest of the soft body feature.

[Julio Jerez]

hey Joe, now I have a crude impelemnetion of the algorithm on that paper.
This is only step 1.

basically creation the sub set of tetras that either cross the surface or are inside the surface.
you can see how is start to approximate the surface of the sphere already.
there are tow more steps according to the paper, but I will add an extra one.
the steps are:
1- snap is tetra vertex whos point ouside of the surface but too close to it.
this is more like a hack to reduce the number of cuts but is a very clever one.
2-for eh responding tetras, make a code base of how many vertices are outside vs how many are inside
this code map into at look up table that say how to replace that tetra with a seriues of sub tetras.
this step gives the mush better approximation to the tetra shape because is smoth the pointed corners.
3-this I am adding, since the new tetras are selected from an array of premade tetras, some vertex will still be outside the shape, this suggest that we can run step one again to snap the remaining of the outside vertex and get the exact representation of the shape.

This algorithm will produce a solid mesh made of more or less uniform tetrahedral. so the density could be quiet high. so next I will need to implement the mesh refinement. They call this tetra grading, basically this is running the algorithm is two steps.

1-reject all tetras outside and inside, the surface,
2-run an octree tree version of the grid generation to generate variable size grid that are converted to regular tetras that match the high resolution perimeter tetra mesh.
for this I will wait until I get the full soft body solver operational.

note: soft body solver is now not funtional yet,
I commented out until I get visual quality up to speed. I was a little concerned about that part because we are taking of volumetric data, but this iso surface representation seem to be the solution.