Hey, played with it some more and made some minor changes. Still it performs worse than the beta version and breaks completely for larger spreadcounts and I really don’t get were the differences come from.
Don’t know it the ticks displayed in gamma and beta can be compared directly:
Perf
Graph Update
beta:
public void Update()
{
var edgeCount = FEdges.Count;
var nodeCount = FNodes.Count;
//attraction along edges
for(int i=0; i<edgeCount; i++)
{
FEdges[i].Update();
}
var nodeCountRep = 1.0/nodeCount;
//repulsion of the nodes
for(int i=0; i<nodeCount; i++)
{
var n = FNodes[i];
n.Velocity += CalcRepulsion(n);
n.Velocity *= Speed;
}
//update position
for(int i=0; i<nodeCount; i++)
{
var n = FNodes[i];
n.Update(GetTime());
}
}
gamma:
CalcRepulsion
beta:
private Vector3D CalcRepulsion(FDNode n)
{
var rep = new Vector3D(0);
if(n.Parent.Count == 0) return rep;
var oCount = FNodes.Count;
for(int i=0; i<oCount; i++)
{
var o = FNodes[i];
if (o != n)
{
var diff = n.Position - o.Position;
rep += Forces.Repulse(diff);
}
}
return rep/oCount;
}
gamma:
Fruchterman Reingold repulsion
beta:
private static Vector3D RepulseFR(Vector3D diff)
{
var l = !diff;
diff /= l;
return diff * ((ConstantsFR.y*ConstantsFR.y) / l);
}
The ticks can be compared directly - both represent µs. Just did a quick comparison and for N = 200, it’s ~900µs in beta vs ~2200µs in gamma. Reason is that the emitted code when running inside the editor is not as good as it could be. To name a few things which are different:
A class in VL comes with one level of indirection (proxy and target) in order to quickly exchange them in the object graph (hotswap) - in this case we pay for that one a lot I wager as it affects the inequality check, the position and model access.
The root patch carries the actual implementation of the Attract and Repulse methods (at least in the patch I posted they were implemented using the adaptive mechanism). But since it gets emitted in debug mode, also the JIT compilation of those generic methods will happen in debug → certain optimizations won’t apply. With a little workaround I was able to avoid this an the timings dropped to 1700µs.
Therefor a fair comparison would be to do an export and see how that performs compared to the plugin. I must admit it would be nice to have some sort of switch in the settings to enforce that everything tries to run as fast as possible (obviously losing any debugging features).
But all that being said, I’d say that for high spread counts this algorithm will perform poorly since it’s O(N²). Much better results would probably be achieved using Barnes-Hut algorithm for example The Barnes-Hut Galaxy Simulator
the first one for testing while developing the latter if you want to start a project in the runtime. Both should be connected to the same property, so one’s able to start with the command-line-flag but has the possibility to escape it later without restarting the HDE.
Out of curiosity I’ve tried to adapt a “textual version” of the Force Directed graph from the beta version.
Seemed pretty straight forward. But I am running into an issue I really can’t wrap my head around.
The graph has a List of Edges and a List of Nodes. When building the graph these lists are cleared and then Edges added. When an Edge is added it checks if the Nodes making up the Edge (From, To) already exist, if so fetch the existing Node, otherwise create a new one with random Position and an ID and add it to the nodes list. So far so good.
But when I add multiple Edges/Nodes at once the resulting nodes all have the same Position even though their IDs are correct.
When I do the same in Debug mode in Visual Studio, stepping through the Process of adding, the resulting Positions are also distinct. It also works when adding the Edges one after the other (frame by frame).
Any ideas?
I think both helppatches would be nice to include. one that shows the basic components and one that demonstrate how to spawn and render multiple viruses.
@schlonzo That’s the patched version we discussed further up. Björn replaced it with one written in C#, so I guess that error can be ignored as it’s not used anymore anyways.
The c# version now has an UpdateParallel method using Parallel.For loops to calculate the forces.
While minimum effort, this already gives a nice performance boost.
Hey, gave Barnes-Hut a shot. Not sure I got it quite right, though.
There is a speed-up for greater spread counts (starting at about 1000 particles on my machine).
I guess up to that, rebuilding the octree every frame eats up all gains.
Visually the results of both versions look quite similar, which can be observed in the HowTo create a simple Force Directed Graph patch when setting lower spreadcounts. This patch also has an option to show the subdivision of space.
And again: Any feedback and ideas for improvement very much appreciated.
This doesn’t look correct:
You certainly have a race condition here. You’d need to take the overload which gives you a thread local state, so you calculate for each thread and then at the end again the min and max for all the mins and maxes produced by the different threads.
Shouldn’t the node.Update happen after all forces have been calculated?
And not sure if the tree allocations are an issue - if yes, there’s probably room for improvement by using an object pool.
It was that way before. One loop to calculate the repulsion and then another to update the nodes. Out of curiosity I then changed it to the way it is now and couldn’t spot any siginificant differences so I left it. But I guess the performace gained from one loop less is negligible (if any)? Will go back to the initial way then.
I did spot gen2 garbage collections. But wasn’t sure if they come from re-generating the tree (alone). In the version I posted the spread for the positions is generated in the patch using a foreach iteraring over all nodes, for higher spreadcounts this could also be a problem I guess?
In the meantime I did this:
And get the positions in patch from the array. Is this a viable way? Also thought abount calculating transforms directly in code.
Concerning the Objectpool: Since the octree is splitting itself recursively into smaller octrees is it enough to just get the root-tree from the pool and return it, or do the children also to be from the pool?
Also is the object automatically “reset” when returned? Couldn’t glean that from the docu and the examples I found seemed to be either ASP or Unity specific.
