Help Get separate particles parts

[Zavhoz]

Hi!

How can you determine that in one emitter the particles are divided into several separate parts. And is it possible to obtain these groups of individual particles?

Regards!

[josemendez]

Hi!

How can you determine that in one emitter the particles are divided into several separate parts. And is it possible to obtain these groups of individual particles?

Regards!

Hi,

What do you mean? particles are not divisible, each particle remains a single entity throughout the simulation.

If you are referring to drops or blob-like formations, these emerge automatically from physical laws. There's no explicit tracking of those in Obi (or any existing fluid simulation engine that I'm aware of), pressure, viscosity and surface tension regulate how much the fluid tends to form drops. However there's no "list" of drops/blobs that you could access anywhere in the code, since the simulation does not need it for any purpose.

If you want to get a list of drops/blobs/isolated particles for gameplay reasons, you'll need to first determine what you consider to be a "drop" in your game, then create this list yourself.

kind regards,

[Zavhoz]

Hi,

What do you mean? particles are not divisible, each particle remains a single entity throughout the simulation.

If you are referring to drops or blob-like formations, these emerge automatically from physical laws. There's no explicit tracking of those in Obi (or any existing fluid simulation engine that I'm aware of), pressure, viscosity and surface tension regulate how much the fluid tends to form drops. However there's no "list" of drops/blobs that you could access anywhere in the code, since the simulation does not need it for any purpose.

If you want to get a list of drops/blobs/isolated particles for gameplay reasons, you'll need to first determine what you consider to be a "drop" in your game, then create this list yourself.

kind regards,

I understand that all particles remain one with the emitter that produced them. But I wanted to know if I can determine the particles of the compound at the moment, or if there are separate formations, as in the picture

   

[josemendez]

I understand that all particles remain one with the emitter that produced them. But I wanted to know if I can determine the particles of the compound at the moment, or if there are separate formations, as in the picture

Hi Zavhoz,

There's no built-in way to do this. The engine doesn't work in terms of "formations", these emerge automatically from the simulation and are not explicitly tracked. You'll have to find these yourself.

A simple algorithm that comes to mind is to keep a set of "formations", and initially assign each particle no formation. Iterate trough all particles, for each one find its neighbors and:

- If the neighbor is not part of any formation, add it to the current particle's formation - if any. If neither are part of a formation, create a new formation and assign them both to it.
- If the current particle and its neighbor are part of different formations, merge both formations.

This is similar to the algorithm used to count connected components in a graph. Once you're done iterating trough all particles, your set will contain the individual formations you're looking for.

kind regards

[Zavhoz]

Hi Zavhoz,

There's no built-in way to do this. The engine doesn't work in terms of "formations", these emerge automatically from the simulation and are not explicitly tracked. You'll have to find these yourself.

A simple algorithm that comes to mind is to keep a set of "formations", and initially assign each particle no formation. Iterate trough all particles, for each one find its neighbors and:

- If the neighbor is not part of any formation, add it to the current particle's formation - if any. If neither are part of a formation, create a new formation and assign them both to it.
- If the current particle and its neighbor are part of different formations, merge both formations.

This is similar to the algorithm used to count connected components in a graph. Once you're done iterating trough all particles, your set will contain the individual formations you're looking for.

kind regards

I heard you, thanks for the quick reply.

Sorry for my English.

[slimedev]

Hi!

How can you determine that in one emitter the particles are divided into several separate parts. And is it possible to obtain these groups of individual particles?

Regards!

Hello. I looked into this a while ago and, because Obi works by applying forces to particles that are near eachother, it conveniently has a queue of "fluidInteractions" which we can process to gather contiguous particles in the solver

Here is the basics, showing that for every pair that is "really" interacting, we run TryMergeRoots() on the two solver indices. This uses a Union Find algorithm on the disjoint set of solver particles. Importantly, the root index of any two or more particles is decided to be the -lowest- of any of the solver indices, because this ensures stability for which particles point to others.

Code:

// Use interaction pairs to detect contiguous Fluid Bodies of Obi particles
private void Merge_Fluids(ObiNativeIntList rootSolverIndices)
{
    Debug.Assert(solver.implementation != null, $"{nameof(solver.implementation)} is null, is ObiSolver not yet inited?");
    Debug.Assert(rootSolverIndices.count == solver.positions.count, $"Length of UnionFind roots must match solver Positions  couns\n{rootSolverIndices.count} != {solver.positions.count}");

    float distanceThreshold = Mathf.Pow(solverHandler.m_gamebodyMergeMaxDist, 2);
    NativeArray<FluidInteraction> fluidSimplexInteractions = (solver.implementation as BurstSolverImpl).fluidInteractions;                  // Fluids Only
    foreach (var interaction in fluidSimplexInteractions)
    {
        // Fluid Interactions contain Solver Indices
        if (interaction.particleA >= solver.positions.count || interaction.particleB >= solver.positions.count)
        {
            Debug.LogError($"Solver Particle(s) interaction invalid: {interaction.particleA} {interaction.particleB} for solver positions count {solver.positions.count}");
            continue;
        }

        // ensure that particles are active in actors
        var actorinfoA = solver.particleToActor[interaction.particleA];
        var actorinfoB = solver.particleToActor[interaction.particleB];
        bool isactiveA = actorinfoA.indexInActor < actorinfoA.actor.activeParticleCount;
        bool isactiveB = actorinfoB.indexInActor < actorinfoB.actor.activeParticleCount;
        if (isactiveA == false || isactiveB == false)
        {
            //Debug.LogWarning($"Interaction ignored, one or both is inactive");
            continue;
        }

        // quick distance check with sqrMagnitude
        Vector3 posA = solver.positions[interaction.particleA];
        Vector3 posB = solver.positions[interaction.particleB];
        float sqrDist = (posA - posB).sqrMagnitude;
        if (sqrDist > distanceThreshold)
            continue;

        // We are now positive that particles A and B have interacted, and can thus be assumed to be in the same contiguous fluid body
        // Therefore, re-direct the upper index to the lower index
        // So that the lowest index of any fluidbody is the root index of all particles in that body
        TryMergeRoots(rootSolverIndices, interaction.particleA, interaction.particleB);
    }
}

I can post the UnionFind functions later, but here is the general idea. Point all solverIndices to themselves in m_perParticle_RootSolverIndex, and then in Merge, take interacting pairs and re-direct the higher index from itself to the lower. 
Once you have "rootSolverIndices", every solver index who points to itself defines a new body. Again, each root will be the lowest index of any particles in its own contiguous body.
Then, you can iterate each body and calculate centermass positions, etc

Code:

ResetUnionFindElements(m_perParticle_RootSolverIndex);
Merge_NonFluids(m_perParticle_RootSolverIndex);
Merge_Fluids(m_perParticle_RootSolverIndex);

List<int> rootSolverIndices = null;
UnionFind_GetRoots(m_perParticle_RootSolverIndex, out rootSolverIndices);
Unionfind_SanityCheckRoots(m_perParticle_RootSolverIndex);

[slimedev]

You will first need to modify the ObiFixedUpdater.cs component attached to your ObiSolver
so we can do ObiFixedUpdater.PostFixedUpdate += ComputeUnionFind;
You will also need to manage list sizes by subscribing to ObiSolver.OnEnsureParticleArrayCapacity

Code:

public System.Action PreFixedUpdate;
public System.Action PostFixedUpdate;

private void FixedUpdate()
{
    ObiProfiler.EnableProfiler();

    PrepareFrame();

    BeginStep(Time.fixedDeltaTime);
    PreFixedUpdate?.Invoke();           // nice option to have

    float substepDelta = Time.fixedDeltaTime / (float)substeps;

    // Divide the step into multiple smaller substeps:
    for (int i = 0; i < substeps; ++i)
        Substep(Time.fixedDeltaTime, substepDelta, substeps-i);

    EndStep(substepDelta);
    PostFixedUpdate?.Invoke();        // do Union Find after particle simulation

    ObiProfiler.DisableProfiler();

    accumulatedTime -= Time.fixedDeltaTime;
}

Here is the rest of the code for managing the UnionFind.

It's quite error-prone, so includes lots of debugging, but it ought to get you most of the way towards getting the particle groups you were looking for. Just create one "group" (i call it a Gamebody) for each in rootSolverIndices, and iterate the rest of the particles to see which all reference that root by using m_perParticle_RootSolverIndex.

Code:

ObiNativeIntList m_perParticle_RootSolverIndex;    // count should always match ObiSolver.positions
ObiNativeBoolList m_solverIndexActive;      // see ObiSolver.OnSetActiveParticles and ObiSolver.activeIndices

void ComputeUnionFind()
{
    ResetUnionFindElements(m_perParticle_RootSolverIndex);
    Merge_NonFluids(m_perParticle_RootSolverIndex);
    Merge_Fluids(m_perParticle_RootSolverIndex);

    UnionFind_GetRoots(m_perParticle_RootSolverIndex, out List<int> rootSolverIndices);
    Unionfind_SanityCheckRoots(rootSolverIndices);

    // ... re-iterate all active solver indices to handle the sets of particles
}
void SetActiveParticles(NativeArray<int> actives)
{
    for (int i = 0; i < m_solverIndexActive.count; i++)
        m_solverIndexActive[i] = false;
    foreach (int active in actives)
        m_solverIndexActive[active] = true;
}

#region ObiUnionfind

// Set all solver indices to Self (index) or -1, inactive
// after UnionFind, those that still point to themselves are the roots of their fluid bodies
private void ResetUnionFindElements(ObiNativeIntList solverRoots)
{
    PrepUnionFind_RootIndices prepJob = new PrepUnionFind_RootIndices() {
        solverRoots = solverRoots.AsNativeArray<int>(),
        solverIndexActive = m_solverIndexActive.AsNativeArray<bool>(),
    };
    JobHandle clearHandle = prepJob.Schedule(solver.positions.count, 16);        // Iterate ALL particles, not just active/instanced. do not use allocParticles
    clearHandle.Complete();
}
[BurstCompile]
public struct PrepUnionFind_RootIndices : IJobParallelFor
{
    [WriteOnly] public NativeArray<int> solverRoots;
    [ReadOnly] public NativeArray<bool> solverIndexActive;

    public void Execute(int solverIndex)
    {
        int elementRoot = UnionFindGamebodies.DisabledElement;  // Inactive particles will always point to -1.
        if (solverIndexActive[solverIndex])
            elementRoot = UnionFindGamebodies.SelfElement(solverIndex);  // Initially, all Active Indices are roots - point to self

        solverRoots[solverIndex] = elementRoot;
    }
}

// For Rope and Cloth, point the entire actor towards the lowest solver index
private void Merge_NonFluids(ObiNativeIntList rootSolverIndices)
{
    Debug.Assert(rootSolverIndices.count == solver.positions.count, $"Length of UnionFind roots must match solver Posiitions  couns\n{rootSolverIndices.count} != {solver.positions.count}");

    foreach (var actor in solver.actors)
    {
        if (actor is ObiEmitter) // Ignore Fluids
            continue;

        // Merge all Solver Indices
        int lowestSolverIndex = -1;   // Just choose the FIRST index to call Merge() all others. Internally, UnionFind will point everyone to the Lowest.
        for (int actorIndex = 0; actorIndex < actor.activeParticleCount; actorIndex++)  // Actives Only
        {
            int solverIndex = actor.solverIndices[actorIndex];
            if (lowestSolverIndex < 0)
            {
                lowestSolverIndex = solverIndex;
                continue;
            }

            TryMergeRoots(rootSolverIndices, lowestSolverIndex, solverIndex);
        }
    }
}
// Use interaction pairs to detect contiguous Fluid Bodies of Obi particles
private void Merge_Fluids(ObiNativeIntList rootSolverIndices)
{
    // sanity checks
    Debug.Assert(solver.implementation != null, $"{nameof(solver.implementation)} is null, is ObiSolver not yet inited?");
    Debug.Assert(rootSolverIndices.count == solver.positions.count, $"Length of UnionFind roots must match solver Posiitions  couns\n{rootSolverIndices.count} != {solver.positions.count}");

    // Should probably reference your particle size. You are also free to try removing all distance checking, because Obi already said these two particles are "interacting"
    float distanceThreshold = Mathf.Pow(solverHandler.m_gamebodyMergeMaxDist, 2);
    NativeArray<FluidInteraction> fluidSimplexInteractions = (solver.implementation as BurstSolverImpl).fluidInteractions;
    foreach (var interaction in fluidSimplexInteractions)
    {
        // Fluid Interactions contain Solver Indices
        if (interaction.particleA >= solver.positions.count || interaction.particleB >= solver.positions.count)
        {
            Debug.LogError($"Solver Particle(s) interaction invalid: {interaction.particleA} {interaction.particleB} for solver positions count {solver.positions.count}");
            continue;
        }

        // ensure that particles are active in actors
        //     An additional ObiNativeBoolList m_solverIndexActive would allow
        //     bool isactiveA = m_solverIndexActive[interaction.particleA]
        var actorinfoA = solver.particleToActor[interaction.particleA];
        var actorinfoB = solver.particleToActor[interaction.particleB];
        bool isactiveA = actorinfoA.indexInActor < actorinfoA.actor.activeParticleCount;
        bool isactiveB = actorinfoB.indexInActor < actorinfoB.actor.activeParticleCount;
        if (isactiveA == false || isactiveB == false)
        {
            //Debug.LogWarning($"Interaction ignored, one or both is inactive");
            continue;
        }

        // quick distance check with sqrMagnitude
        Vector3 posA = solver.positions[interaction.particleA];
        Vector3 posB = solver.positions[interaction.particleB];
        float sqrDist = (posA - posB).sqrMagnitude;
        if (sqrDist > distanceThreshold)
            continue;

        // We are now positive that particles A and B have interacted, and can thus be assumed to be in the same contiguous fluid body
        // Therefore, re-direct the upper index to the lower index
        // So that the lowest index of any fluidbody is the root index of all particles in that body
        TryMergeRoots(rootSolverIndices, interaction.particleA, interaction.particleB);
    }
}
// After merging, we can find the roots
public void UnionFind_GetRoots(ObiNativeIntList solverRoots, out List<int> rootSolverParticles)
{
    List<string> errors = new();
    List<int> errSolverIndices = new();
    var rootSolverParticlesSet_SolverIndex = new HashSet<int>();
    foreach (var obiActor in solver.actors)
    {
        int actorIndex = 0;

        // For 0..activeCount, (inclusive, exclusive) 
        for (; actorIndex < obiActor.activeParticleCount; actorIndex++)
        {
            int solverIndex = obiActor.solverIndices[actorIndex];
            int solverRoot = solverRoots[solverIndex];

            if (solverRoot == DisabledElement)      // save errors for later
            {
                int iOfActor = solver.actors.IndexOf(obiActor);
                var err = $"Actor{iOfActor} p{actorIndex}<active{obiActor.activeParticleCount} BUT root elem at solver{solverIndex} is DISABLED({solverRoot})!!";
                errors.Add(err); errSolverIndices.Add(solverIndex);
            }

            if (solverRoots[solverIndex] == SelfElement(solverIndex))
                rootSolverParticlesSet_SolverIndex.Add(solverIndex);
        }

        // Continue onwards and double-check the inactive particles
        // For activeCount..allocCount (inclusive, exclusive)
        for (; actorIndex < obiActor.particleCount; actorIndex++)
        {
            int solverIndex = obiActor.solverIndices[actorIndex];
            int solverRoot = solverRoots[solverIndex];

            if (solverRoot != DisabledElement)       // save errors for later
            {
                int iOfActor = solver.actors.IndexOf(obiActor);
                var err = $"Actor{iOfActor} p{actorIndex}>=active{obiActor.activeParticleCount} BUT root elem at solver{solverIndex} is NOT disabled({solverRoot})!!";
                errors.Add(err); errSolverIndices.Add(solverIndex);
            }
        }
    }
    // Done!!
    rootSolverParticles = rootSolverParticlesSet_SolverIndex.ToList();

    // print any errors
    if (errors.Count > 0 && solver.actors.Count > 0)
    {
        ObiActor actor = solver.actors[0];
        List<(int, int)> errSolverAndActor = new();
        foreach (int errSolver in errSolverIndices)
        {
            var iInActor = m_indexSolverToActors[errSolver].iInActor;
            errSolverAndActor.Add((errSolver, iInActor.Int));
        }

        // Print out the tuples for debugging
        string rootsString = string.Join(", ", solverRoots.Select(r => r));
        string actorSolverIndStr = string.Join(", ", actor.solverIndices.Select(s => s));
        string unionString = string.Join(", ", errSolverAndActor.Select(t => $"(s{t.Item1}, a{t.Item2})"));
        string unionErr = string.Join("\n", errors.Select(e => e));
        Debug.LogError($"Bad roots! {rootsString}\n" +
            $"actorSolverIndices: {actorSolverIndStr} numActiveAct0: {actor.activeParticleCount}\n" +
            $"errSolverAndActor: {unionString}\n" +
            $"{unionErr}");
    } // erorr checking
}

// Make sure the mess of indices was handled properly
void Unionfind_SanityCheckRoots(List<int> rootSolverIndices)
{
    if (rootSolverIndices.Count == solver.positions.count)
        Debug.LogWarning($"UnionFind: It appears there is 1 Root particle assigned for every particle in the Solver. {rootSolverIndices.Count}=={solver.positions.count}. This is likely an error. Check particle interaction queue's handling, or UnionFind.");
    // Each root particle must be active
    foreach (int solverIndex in rootSolverIndices)
    {
        if (solverIndex >= solver.positions.count) Debug.LogError($"index {solverIndex} not in count {solver.positions.count}");

        var actorInfo = solver.m_ParticleToActor[solverIndex];
        if (actorInfo.indexInActor < 0 || actorInfo.indexInActor >= actorInfo.actor.activeParticleCount)
            Debug.LogWarning($"Inactive solver particle:{solverIndex} in actor {solver.actors.IndexOf(actorInfo.actor)} iInActor:{actorInfo.indexInActor}");
    }
    // If there are any particles, surely we found some roots!
    if (solver.activeParticles.count > 0 && rootSolverIndices.Count == 0)
    {
        int solverActive = solver.activeParticles.count;
        bool dirtyActive = solver.dirtyActiveParticles;
        List<int> actorActives = new List<int>(); // num active in actor
        List<int> solverActives = new List<int>(); // all solver particles, active in actor?
        foreach (var actor in solver.actors)
        {
            actorActives.Add(actor.activeParticleCount);
            for (int i = 0; i < actor.particleCount; i++)
                solverActives.Add(i < actor.activeParticleCount ? 1 : 0);
        }
        string actorsString = string.Join(",", actorActives);
        string solverString = string.Join(",", solverActives);
        List<int> root = m_perParticle_RootSolverIndex.ToList<int>(); // root particles
        string[] rootStrings = new string[root.Count];
        for (int i = 0; i < root.Count; i++) rootStrings[i] = (root[i] == SelfElement(i)) ? $"{root[i].ToString()}(S)" : root[i].ToString();
        string rootsString = string.Join(",", rootStrings);                                                                                // DEBUGS
        Debug.LogError($"{solver.activeParticles.count} solver particles active, yet 0 union roots! numActiveInActors:[{actorsString}]!\n" + "" +
            $"{"solver roots":d15}: {rootsString}\n" +
            $"{"activeInActor":d15}: {solverString}\n" +
            $"{"NOTE:d15"}: there is a reference to an inactive Solver Index, yes?");
        return;
    }
}

#endregion ObiUnionfind








#region Union-Find Helpers

public static readonly int DisabledElement = -1;
public static int SelfElement(int solverIndex) // Root elements point to self
{
    return solverIndex;
}

private bool TryMergeRoots(ObiNativeIntList particleRoots, int solverIndexA, int solverIndexB)
{
    int rootA = FindRoot(particleRoots, solverIndexA);
    int rootB = FindRoot(particleRoots, solverIndexB);
    if (rootA == rootB)  // Already merged? Great.
        return false;

    MergeRoots(particleRoots, rootA, rootB);
    return true;
}
private int FindRoot(ObiNativeIntList solverRoots, int solverIndex)
{
    // Look for an element that points to itself
    int queryIndex = solverIndex;
    if (queryIndex >= solverRoots.count)
        Debug.LogError($"Query Index {queryIndex} too big for count {solverRoots.count}");

    while (solverRoots[queryIndex] != SelfElement(queryIndex))
    {
        if (solverRoots[queryIndex] == DisabledElement)  // Why does it point to disabled?
            break;
        queryIndex = solverRoots[queryIndex];    // Read
    }

    int rootIndex = queryIndex;
    PathCompress(solverRoots, solverIndex, rootIndex);   // Write
    return rootIndex;
}
void MergeRoots(ObiNativeIntList solverRoots, int rootA, int rootB)
{
    // For fluidbody association, Prefer to point to Smaller root index  roots[b] = a
    // For Single-Thread, this removes Randomness (Camera Jitter for multiple slimes)
    Debug.Assert(rootA != rootB, $"Why does {rootA}=={rootB}?");
    if (rootA > rootB)   // As preferred above, don't want solverRoots[rootB] = rootA; with large A because root should be lower
    {
        int tmp = rootA;
        rootA = rootB;
        rootB = tmp;
    }
    Debug.Assert(rootA < rootB);
    solverRoots[rootB] = rootA;
}

// While associating particle interaction pairs, avoid keeping multiple redirects
// For any particle whose root>...>root is i, point directly to i
void PathCompress(ObiNativeIntList perParticleRootIndex, int solverIndex, int rootIndex)
{
    while (solverIndex != rootIndex)
    {
        int parent = perParticleRootIndex[solverIndex];   // Read
        perParticleRootIndex[solverIndex] = rootIndex;   // Write
        solverIndex = parent;
    }
}

#endregion UnionFind Helpers

P.S. You are free to remove the burst code and native lists, and use a For Loop and Lists. "PrepUnionFind_RootIndices" is the only Burst Job, nothing else is parallelized. (I have no clue how to parallelize UnionFind because atomic locks (neded for multi-threaded read/write to random array positions) in Unity seem impossible. Future work.)