Collision free instance painting

[Bird]

Hi Julio,

Congrats on getting a stable 4.0 out! It's really come a long way and looks fantastic. I'm hoping to add more and more of Newton's features to my app in the coming months.

I'm starting to try to implement collision free instance painting now, like I have done in Newton 3 I have added a class like your ndContactCallback() that inherits from ndContactNotify() and I do get contact notification in OnAabbOverlap() when the engine is running. But I need to get contact info while the engine is not running like in this video. Is it possible in Newton 4? Basically I need to drag a body around the scene and be informed when it comes in contact with another body.

https://youtu.be/Hl4yIwr6DFk

[Julio Jerez]

Ah yes.

One of the new flexibility of newton 4 is that the collision and the dynamic are fully independent,
I have not tested in a while, but I will check tomorrow.

As I remember in 3.xx we has a collision. Only update.

I will add the function for executing a collision only update.
This way you can set the transforms, of the bodies you want to manipulate. And them before you what the update, you call a collision update.

It was designed for that fu tonality, it is now time to test it.

Also on this hollysay break, I am now resuming the fluid simulation, so by the time you get the next update, you could try the fluid.

I am trying with 32k particle, and that reach the limit of my cpu, an icore7 7700. It only has 8 Meg of cache, and 32 k particles generater two buffer of 4 megbytes each, so it trash the cache and the multicore does not make any faster.
So is this mysterious thing that an 8 Meg buffer make multicore equal or marginally slower, but if cut by half then is can have the entire buffer in cache and is very fast.

But for people with newer cpu, like 12 or 20 Meg of cache, them is very fast.

After I get the basic code I will make an optimization. That will cut the buffer in half, so the target of 32 can be real time.
Right now, building the structure is about 6 ms.
But anyway, that's a different issue.

[Julio Jerez]

ok the function is
void ndWorld::CollisionUpdate();

it is an update level function, only update the broad phase collision system
it does the ndContactNotify but none of the other dynamics callbacks.

just as if you call Update from inside an update, it will dead lock if you do it.

when you sync, you will see the start of the particle iso surface reconstruction.
so far, a disappointing result.
a solid block of 16 x 16 x 16 points = 4096 particles takes from 10 to 16 ms in my system.
a solid block of 32 x 32 x 32 points = 32k particles takes from 100 to 120 ms in my system.

the code is not really optimized, since is try to process all the cell,
but is hard to make an optimization that will make more than 10 time faster.

I will finish the code, to see how far is goes, but it seems that using splat rendering will a more practical solution.

[Bird]

I can't seem to get ndWorld::CollisionUpdate() to work.

When I'm dragging a body around in the scene I call this function below. But OnAabbOverlap() never gets called in my ContactHandler class that inherits from ndContactNotify(). Do I need to make this call from Newton's thread?

Code: Select all

void NewtonEngine::updatePoseAndScale (RenderableNode& node)
{
    ndBodyDynamic* const body = static_cast<ndBodyDynamic*> (node->getUserdata());
    if (!body) return;

    ndMatrix currentPose;
    eigenToNewton (node->getSpaceTime().worldTransform, currentPose);
    body->SetMatrix (currentPose);

    ndShapeInstance& shape = body->GetCollisionShape();
   
    Eigen::Vector3f s = node->getSpaceTime().scale;
    ndVector scale = ndVector (s.x(), s.y(), s.z(), 0.0f);
    shape.SetScale (scale);

    LOG (DBUG) << "update collision";
    state->world->CollisionUpdate();
}

[Julio Jerez]

oh I see, there is a problem.
It is one of the way Newton 4 does the collision.
basically newton 4 does not has narrow phase collision, instead is uses the distance test between two shapes. this is the function:
void ndScene::CalculateContacts(ndInt32 threadIndex, ndContact* const contact)

you can see that when two bodies are close enough, the engine calculates the minimum distance between the two collision shapes. if the distance is small, it means they are colliding.

is not, them in each subsequent update, in does an upper bound calculation of how much that distance will be reduced in each step.
them, is the reduction is below some critical values, it recalculates the distance again.
it keeps doing that until the bodies move far apart, in which case the broad phase will destroy the contact joint, or they move closer that they are colliding.
this algorithm trade more pairs, for more parallel execution and few fewer expensive low level calls to collision that will report not contacts.

for this to work, the update needs tow thing:
1-the update needs a time step.
2-the bodies should have velocity.

both are easy to solve.

the first one, all we need to do is to make CollisionUpdate() take a time step.

the secund, we need the bodies to have a velocity.
but that is very easy, in your side, when you are going to teleport a body.
you can calculate the velocity of that body as follows.

Code: Select all

body->veloc = (body->posit - desired position) / timestep

them the call to update with the time step like CollisionUpdate(timestep)
should do the trick.

right now, what is happing is that the code that decreases the time step, is not decreasing the distance, the code below. as you can see if m_timestep is zero, the distant is never reduced.

Code: Select all

void ndScene::CalculateContacts(ndInt32 threadIndex, ndContact* const contact)
{
   const ndUnsigned32 lru = m_lru - D_CONTACT_DELAY_FRAMES;

   ndVector deltaTime(m_timestep);
   ndBodyKinematic* const body0 = contact->GetBody0();
   ndBodyKinematic* const body1 = contact->GetBody1();

   dAssert(!contact->m_isDead);
   if (!(body0->m_equilibrium & body1->m_equilibrium))
   {
      bool active = contact->IsActive();
      if (ValidateContactCache(contact, deltaTime))
      {
         contact->m_sceneLru = m_lru;
         contact->m_timeOfImpact = ndFloat32(1.0e10f);
      }
      else
      {
         contact->SetActive(false);
         contact->m_positAcc = ndVector::m_zero;
         contact->m_rotationAcc = ndQuaternion();

         ndFloat32 distance = contact->m_separationDistance;
         if (distance >= D_NARROW_PHASE_DIST)
         {
[color=#FF0040]            const ndVector veloc0(body0->GetVelocity());
            const ndVector veloc1(body1->GetVelocity());
            
            const ndVector veloc(veloc1 - veloc0);
            const ndVector omega0(body0->GetOmega());
            const ndVector omega1(body1->GetOmega());
            const ndShapeInstance* const collision0 = &body0->GetCollisionShape();
            const ndShapeInstance* const collision1 = &body1->GetCollisionShape();
            const ndVector scale(ndFloat32(1.0f), ndFloat32(3.5f) * collision0->GetBoxMaxRadius(), ndFloat32(3.5f) * collision1->GetBoxMaxRadius(), ndFloat32(0.0f));
            const ndVector velocMag2(veloc.DotProduct(veloc).GetScalar(), omega0.DotProduct(omega0).GetScalar(), omega1.DotProduct(omega1).GetScalar(), ndFloat32(0.0f));
            const ndVector velocMag(velocMag2.GetMax(ndVector::m_epsilon).InvSqrt() * velocMag2 * scale);
            const ndFloat32 speed = velocMag.AddHorizontal().GetScalar() + ndFloat32(0.5f);
            
            distance -= speed * m_timestep;
            contact->m_separationDistance = distance;
         }
         if (distance < D_NARROW_PHASE_DIST)
[/color]         {
            CalculateJointContacts(threadIndex, contact);


as you can see, you can see that this new algorithm is very cost effective, is we have a scene when the objects are slow moving, then distance reduces very slowly and very few collisions call are made.
but if we have fast moving bodies, them they do more collisions as they should.
basically, it adapts to the scene, and is also deal naturally with continue collisions.

but as I expect there will be some tunning.

let us do this, you do the step two, setting the body velocities when teleporting, and I will do the Collision Update. for this I need to check in few places where the time step is use.

[Bird]

Okay, I have calculated the teleported distance but I'm not sure what to use for timestep. I'm trying to run at 60 fps so should I just make timestep 1.0f/60f?

If the engine is running, I don't need to calculate the velocity myself. Is that correct?

Thanks!

[Julio Jerez]

Yes, you have right.

Every time you set the new position. You also set the velocity. Just make sure that the last position set the vomits to zero, if not the when you start updating the physic again the body will remember the velocity.

I will do the secund part tomorrow.

[Bird]

Wow, the fluid surface reconstruction is looking pretty fast. On my machine physics time is about 11 ms.

I tried creating the same fluid volume mesh you made with 32,768 particles using OpenVDB and it's taking about 450 ms.

[Julio Jerez]

Ah, thanks for that test.
Yes that 11 ms include the the some part of the simulation.

There are few things that can be still improved, and I will complete that today.

The one thing is that the reconstruction is not multithtreaded, I intentionally leave it like that, because my plan is to place it on a background worker thread.

That's the motivation of separating it from the simulation.
By making it, a client side utity function, this achieve two immidiate goals.
The first one, the particle visualization is on the client, and they can use any method they like. Be splat, or thier prefer library. we just provide that basic functionality.

The second goal is that as long as the reconstruction takes less than a frame time, by making async, it will appear free from that app point of view. So those 11 ms, will be reduced to about 1. Or 2.

a third distance goal, is that my algorithm for making the is surface, is truly data parallel, so in can be made part if a gpu compute shader, and now we taking some serious volume, we can be taking of the order of million of particle at real time simulation.
But let us keep it quite for now.

The one thing I will look at is the actual marching cube, it is too branchy, I need a better one that can be parallizable, I think that now I understand it better, I can come up with a better itemization of the original version I Got from Wikipedia.

Any way, still some more work, by thank up very much for that check, it is quite encouraging to for continue the work



BTW I just removed the legacy octree base builder, and I also made to use two different hash using a define.

the small hash is a 64 bit is size, which use half the memory, this reduce the memory bandwidth for legacy system like mine which only has 8 meg of level 3 cache which mean the operation keep blow the cache. with the change in my system, I when from 16 to 18 ms, to about 12 ms.
if you have time please test it again. I am curious to see if it makes a difference.

the small size hash reduces the max volume a flid can cover
which assuming particle size of 0.01 unit that will be 65000k/100 = about 650 meters, assuming a unit is a meter. but the buffer sizes are about half the size,
in the case of a 32k volume that an 8 meg worth of working buffers.

[Bird]

if you have time please test it again. I am curious to see if it makes a difference.

It did make some difference here. The older version was around 11.2 ms average and the latest version runs around 10.7 ms on my machine.

Processor Intel(R) Core(TM) i7-9700K CPU @ 3.60GHz 3.60 GHz 8 cores
Installed RAM 32.0 GB

[Julio Jerez]

Ok my friend, is you sync be ready for be surprised.
but before you fall off your chair; it is not magic. Basically, this is just hiding the latency of the mesh reconstruction using a background worker thread.
this is how it looks like in a profile capture

Untitled.png (70.32 KiB) Viewed 10750 times

as you can see as long as build the mesh take less than a sim frame.
to the end app, it appears as if the effect comes for free.

the top line is the render frame, and the middle traces is the physics.
you can see that reconstructing a mesh take on average 12 ms, but goes over several frames.

because these days most computer have cores to spear, we can extend that to multiple volumes.
Plus in the next few days, I see that the physics simulation is also very taxing the same concept apply.

ok I will add that time step to the collision update now.

[JoeJ]

Just wanted to try it too, but this time CMake gives me a real problem. I have VC2019 installed, highest option was VC17, and using that it says:

CMake Error at CMakeLists.txt:29 (project):
Generator

Visual Studio 17 2022

could not find any instance of Visual Studio.

I have multi threaded iso surface extraction too. But i need manifold guarantee, so i made my own algorithm and ingored existing papers. Without a need for manifolds it would be very fast i think. Basically i generate a voxelization by comparing density values on the faces of each dimension. Then for each vertex of the resulting mesh calculate density gradient and project vertices to the surface. The resulting mesh is a smooth quadmesh and not that bad. Could post an image if you're interested. Maybe my stuff is similar to Dual Contouring or Surface Nets.

Why do you need the mesh? For collision detection? For rendering i guess some meshless reconstruction in screenspace would be faster, but users can do this anyway.

BTW, seems AVX-512 is pretty much dead for next gen Intel: https://www.hardwareluxx.de/index.php/news/hardware/prozessoren/57783-alder-lake-avx-512-soll-per-bios-update-deaktiviert-werden.html
German source.
They say Low Power cores have no AVX-512, but tasks need ability to be switchable to any core.
Solution: Disable AVX-512 completely.
PC platform is at a ridiculous state. Overpowered and overpriced HW, with big die areas wasted on stuff we don't need (Tensor Cores) or can't use (now AVX-512).
Some low power chips following Apple M1 might soon replace our big towers with something more efficient, eventually on another platform if they don't react quickly.

Started to continue work on ragdolls as a side project. But i'll focus on IK and some procedural animation, before i get back to simulation. Will use Newton first for procedural generation of destructed city scape.

[Julio Jerez]

can you just update cmake?
I have 2.21.3 and goes to VS-2022

and yes is a good thing I did no invested on avx512
.
I think it is a mistake they dropped it, the one thing avx512 has for it is the gather and scatter load and store,
that brings in part with GPU. and without it is very hard to auto vectorize code. But I guess they know better and have better reasons not to support it.

on this

Why do you need the mesh? For collision detection? For rendering i guess some meshless reconstruction in screenspace would be faster, but users can do this anyway.

my method does generates manifolds, which mean it can be used for real time procedural mesh.

for example It can have a density function that define a mesh, for example a wall, and by calling to generate only the surface on a small bound volume, this can be pass to the engine just like the terrain does.
but that not the whole story. that will take care of the physics for the visual it needs a way to make incremental reconstruction.
If has not try that, but I do see a lot of potential.

[Bird]

have VC2019 installed, highest option was VC17, and using that it says:

Yeah, they couldn't make it more confusing.
VC2019 is actually Visual Studio 16 so VC16 is what you want

[Julio Jerez]

I was looking at the code I am using generate the iso surface.
http://paulbourke.net/geometry/polygonise/
the version I am using has some optimization already by nothing especial.

this code seems very old and try to be very clever by making a vert list index list, the requires
a way to cache vertex duplication and index hash. the original code was using hash map, I am using the engine redback tree. however, this make is quite slow, as is stan now those are the slower part.
for what I can see this mak ethe algorith run in O(k * m * log(m) * log(n)) where
m in the nomber of triangle, n is the number of vertices, and k in a high constant.

I believe that is we make so that is only generate a triangle list. them no hash mao is needed but it will generate lot of vertices duplicate so by the time complexity will be O(k * m)
where k now will be very small, and m in the number of triangles.
then and pass of 0(m) will generate vert list index list from the mesh.
this I think cane make the algorithm order of magnitude faster.

unfortunately, by my break is up, so I am back to weekend sit downs again.
but I will try that next weekend.