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
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.
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.)
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 HelpersP.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.)