Skip to content

Commit f79c204

Browse files
YomguitherealYomguithereal
committed
Starting low-level Barnes-Hut
1 parent 6db6317 commit f79c204

File tree

2 files changed

+66
-242
lines changed

2 files changed

+66
-242
lines changed

‎examples/transferables.html

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -117,7 +117,7 @@
117117
});
118118
}
119119
}
120-
sigma.renderers.def = sigma.renderers.canvas;
120+
121121
s = new sigma({
122122
graph: g,
123123
container: 'graph-container',

‎plugins/sigma.layout.forceAtlas2/worker.js

Lines changed: 65 additions & 241 deletions
Original file line numberDiff line numberDiff line change
@@ -31,10 +31,10 @@
3131
// Properties
3232
ppn: 10,
3333
ppe: 3,
34+
ppq: 2,
3435
maxForce: 10,
3536
iterations: 0,
3637
converged: false,
37-
barnesHutDepthLimit: 20,
3838

3939
// Possible to change through config
4040
settings: {
@@ -46,7 +46,8 @@
4646
strongGravityMode: false,
4747
gravity: 1,
4848
barnesHutOptimize: false,
49-
barnesHutTheta: 1.2
49+
barnesHutTheta: 1.2,
50+
barnesHutDepthLimit: 4
5051
}
5152
};
5253

@@ -125,230 +126,6 @@
125126
throw 'NaN alert!';
126127
}
127128

128-
/**
129-
* Barnes-Hut function
130-
*/
131-
function BarnesHut(nodes, depth) {
132-
var i, j, n, l, mass, size, distance;
133-
134-
// Region
135-
var r = {
136-
size: 0,
137-
nodes: nodes,
138-
subregions: [],
139-
depth: depth,
140-
mass: 0,
141-
massCenterX: 0,
142-
massCenterY: 0,
143-
massSumX: 0,
144-
massSumY: 0
145-
};
146-
147-
// Updating mass and geometry
148-
if (r.nodes.length > 1) {
149-
150-
// Iterating through nodes
151-
for (i = 0, l = r.nodes.length; i < l; i++) {
152-
n = r.nodes[i];
153-
154-
mass = W.nodeMatrix[np(n, 'mass')];
155-
r.mass += mass;
156-
r.massSumX += W.nodeMatrix[np(n, 'x')] * mass;
157-
r.massSumY += W.nodeMatrix[np(n, 'y')] * mass;
158-
}
159-
160-
var massCenterX = r.massSumX / r.mass,
161-
massCenterY = r.massSumY / r.mass;
162-
163-
// Computing size
164-
// MATH: something is amiss in the max thingy under here
165-
for (i = 0, l = r.nodes.length; i < l; i++) {
166-
n = r.nodes[i];
167-
168-
distance = 2 * Math.sqrt(
169-
Math.pow((W.nodeMatrix[np(n, 'x')] - r.massCenterX), 2) +
170-
Math.pow((W.nodeMatrix[np(n, 'y')] - r.massCenterY), 2)
171-
);
172-
size = (size === undefined) ?
173-
distance :
174-
Math.max(size, distance);
175-
}
176-
}
177-
178-
// Updating region
179-
r.massCenterX = massCenterX;
180-
r.massCenterY = massCenterY;
181-
r.size = size;
182-
183-
// Build subregions
184-
if (r.nodes.length > 1) {
185-
var subareas = [[], [], [], []],
186-
nextDepth = r.depth + 1;
187-
188-
// TODO: write this better. this is a scandal.
189-
for (i = 0, l = r.nodes.length; i < l; i++) {
190-
n = r.nodes[i];
191-
192-
if (W.nodeMatrix[np(n, 'x')] < r.massCenterX) {
193-
194-
// Left
195-
if ((W.nodeMatrix[np(n, 'y')] < r.massCenterY))
196-
subareas[0].push(n);
197-
else
198-
subareas[1].push(n);
199-
}
200-
else {
201-
202-
// Right
203-
if ((W.nodeMatrix[np(n, 'y')] < r.massCenterY))
204-
subareas[2].push(n);
205-
else
206-
subareas[3].push(n);
207-
}
208-
}
209-
210-
for (i = 0; i < 4; i++) {
211-
if (subareas[i].length > 0) {
212-
if (nextDepth <= W.barnesHutDepthLimit &&
213-
subareas[i].length < r.nodes.length) {
214-
r.subregions.push(BarnesHut(subareas[i], nextDepth));
215-
}
216-
else {
217-
for (j = 0, l = subareas[i].length; j < l; j++)
218-
r.subregions.push(
219-
BarnesHut([subareas[i][j]], nextDepth)
220-
);
221-
}
222-
}
223-
}
224-
}
225-
226-
// Forces application
227-
r.applyForce = function(n) {
228-
var coefficient = W.settings.scalingRatio,
229-
xDist,
230-
yDist,
231-
distance,
232-
factor,
233-
n1,
234-
n2,
235-
i,
236-
l;
237-
238-
if (this.nodes.length < 2) {
239-
n1 = n;
240-
n2 = this.nodes[0];
241-
242-
// Apply the force node to node
243-
// Common to both methods
244-
xDist = W.nodeMatrix[np(n1, 'x')] - W.nodeMatrix[np(n2, 'x')];
245-
yDist = W.nodeMatrix[np(n1, 'y')] - W.nodeMatrix[np(n2, 'y')];
246-
247-
if (W.settings.adjustSize) {
248-
249-
//-- Anticollision Linear Repulsion
250-
distance = Math.sqrt(xDist * xDist + yDist * yDist) -
251-
W.nodeMatrix[np(n1, 'size')] -
252-
W.nodeMatrix[np(n2, 'size')];
253-
254-
if (distance > 0) {
255-
factor = coefficient *
256-
W.nodeMatrix[np(n1, 'mass')] *
257-
W.nodeMatrix[np(n2, 'mass')] /
258-
distance / distance;
259-
260-
// Updating nodes' dx and dy
261-
W.nodeMatrix[np(n1, 'dx')] += xDist * factor;
262-
W.nodeMatrix[np(n1, 'dy')] += yDist * factor;
263-
264-
W.nodeMatrix[np(n2, 'dx')] += xDist * factor;
265-
W.nodeMatrix[np(n2, 'dy')] += yDist * factor;
266-
}
267-
else if (distance < 0) {
268-
factor = 100 * coefficient *
269-
W.nodeMatrix[np(n1, 'mass')] *
270-
W.nodeMatrix[np(n2, 'mass')];
271-
272-
// Updating nodes' dx and dy
273-
W.nodeMatrix[np(n1, 'dx')] += xDist * factor;
274-
W.nodeMatrix[np(n1, 'dy')] += yDist * factor;
275-
276-
W.nodeMatrix[np(n2, 'dx')] -= xDist * factor;
277-
W.nodeMatrix[np(n2, 'dy')] -= yDist * factor;
278-
}
279-
}
280-
else {
281-
282-
//-- Linear Repulsion
283-
distance = Math.sqrt(xDist * xDist + yDist * yDist);
284-
285-
if (distance > 0) {
286-
factor = W.settings.scalingRatio *
287-
W.nodeMatrix[np(n1, 'mass')] *
288-
W.nodeMatrix[np(n2, 'mass')] /
289-
distance / distance;
290-
291-
// Updating nodes' dx and dy
292-
W.nodeMatrix[np(n1, 'dx')] += xDist * factor;
293-
W.nodeMatrix[np(n1, 'dy')] += yDist * factor;
294-
295-
W.nodeMatrix[np(n2, 'dx')] -= xDist * factor;
296-
W.nodeMatrix[np(n2, 'dy')] -= yDist * factor;
297-
}
298-
}
299-
}
300-
else {
301-
distance = Math.sqrt(
302-
(Math.pow(W.nodeMatrix[np(n, 'x')], 2)) +
303-
(Math.pow(W.nodeMatrix[np(n, 'y')], 2))
304-
);
305-
306-
if (distance * W.settings.barnesHutTheta > this.size) {
307-
xDist = W.nodeMatrix[np(n, 'x')] - this.massCenterX;
308-
yDist = W.nodeMatrix[np(n, 'y')] - this.massCenterY;
309-
310-
if (W.settings.adjustSize) {
311-
312-
//-- Linear Anti-collision Repulsion
313-
if (distance > 0) {
314-
factor = coefficient * W.nodeMatrix[np(n, 'mass')] *
315-
this.mass / distance / distance;
316-
317-
W.nodeMatrix[np(n, 'dx')] += xDist * factor;
318-
W.nodeMatrix[np(n, 'dy')] += yDist * factor;
319-
}
320-
else if (distance < 0) {
321-
factor = -coefficient * W.nodeMatrix[np(n, 'mass')] *
322-
this.mass /distance;
323-
324-
W.nodeMatrix[np(n, 'dx')] += xDist * factor;
325-
W.nodeMatrix[np(n, 'dy')] += yDist * factor;
326-
}
327-
}
328-
else {
329-
330-
//-- Linear Repulsion
331-
if (distance > 0) {
332-
factor = coefficient * W.nodeMatrix[np(n, 'mass')] *
333-
this.mass / distance / distance;
334-
335-
W.nodeMatrix[np(n, 'dx')] += xDist * factor;
336-
W.nodeMatrix[np(n, 'dy')] += yDist * factor;
337-
}
338-
}
339-
}
340-
else {
341-
for (i = 0, l = this.subregions.length; i < l; i++) {
342-
this.subregions[i].applyForce(n);
343-
}
344-
}
345-
}
346-
}
347-
348-
// Returning the object
349-
return r;
350-
}
351-
352129
/**
353130
* Algorithm initialization
354131
*/
@@ -372,7 +149,7 @@
372149

373150
// MATH: get distances stuff and power 2 issues
374151
function pass() {
375-
var n, n1, n2, e, w, g;
152+
var a, i, j, l, n, n1, n2, q, e, w, g;
376153

377154
var barnesHutNodes = [],
378155
rootRegion,
@@ -388,23 +165,14 @@
388165
// 1) Initializing layout data
389166
//-----------------------------
390167

391-
// Resetting positions
168+
// Resetting positions & computing max values
392169
for (n = 0; n < W.nodesLength; n += W.ppn) {
393170
W.nodeMatrix[np(n, 'old_dx')] = W.nodeMatrix[np(n, 'dx')];
394171
W.nodeMatrix[np(n, 'old_dy')] = W.nodeMatrix[np(n, 'dy')];
395172
W.nodeMatrix[np(n, 'dx')] = 0;
396173
W.nodeMatrix[np(n, 'dy')] = 0;
397174
}
398175

399-
// Barnes-Hut root region
400-
if (W.settings.barnesHutOptimize) {
401-
402-
for (n = 0; n < W.nodesLength; n += W.ppn) {
403-
barnesHutNodes.push(n);
404-
}
405-
rootRegion = BarnesHut(barnesHutNodes)
406-
}
407-
408176
// If outbound attraction distribution, compensate
409177
if (W.settings.outboundAttractionDistribution) {
410178
outboundAttCompensation = 0;
@@ -416,16 +184,72 @@
416184
}
417185

418186

187+
// 1.bis) Barnes-Hut computation
188+
//------------------------------
189+
if (W.settings.barnesHutOptimize) {
190+
191+
// Necessary variables
192+
// UInt16 should be enough, if not, switch to UInt32
193+
var quadNb = Math.pow(2, 2 * W.settings.barnesHutDepthLimit),
194+
quadRowNb = Math.pow(2, W.settings.barnesHutDepthLimit),
195+
quads = new UInt16Array(quadNb),
196+
quadsProperties = new Float32Array(quadNb * W.ppq),
197+
quadsSteps = new UInt16Array(quadNb),
198+
quadsAcc = new UInt16Array(quadNb),
199+
nodesQuads = new UInt16Array(W.nodesLength),
200+
quadsNodes = new UInt16Array(W.nodesLength),
201+
maxX = 0,
202+
maxY = 0,
203+
minX = 0,
204+
minY = 0,
205+
xIndex,
206+
yIndex;
207+
208+
// Retrieving max values
209+
// OPTIMIZE: this could be computed on the n loop preceding this one
210+
// but at the cost of doing it even when Barnes-Hut is disabled
211+
for (n = 0; n < W.nodesLength; n += W.ppn) {
212+
maxX = Math.max(maxX, W.nodeMatrix[np(n, 'x')]);
213+
minX = Math.min(minX, W.nodeMatrix[np(n, 'x')]);
214+
maxY = Math.max(maxY, W.nodeMatrix[np(n, 'y')]);
215+
minY = Math.min(minY, W.nodeMatrix[np(n, 'y')]);
216+
}
217+
218+
// Adding epsilon to max values
219+
maxX += 0.0001 * (maxX - minX);
220+
maxY += 0.0001 * (maxY - minY);
221+
222+
// Assigning nodes to quads
223+
for (n = 0, i = 0; n < W.nodesLength; n += W.ppn, i++) {
224+
xIndex = ((W.nodeMatrix[np(n, 'x')] - minX) / (maxX - minX) *
225+
Math.pow(2, W.settings.barnesHutDepthLimit)) | 0;
226+
227+
yIndex = ((W.nodeMatrix[np(n, 'y')] - minY) / (maxY - minY) *
228+
Math.pow(2, W.settings.barnesHutDepthLimit)) | 0;
229+
230+
// OPTIMIZE: possible to gain some really little time here
231+
quads[xIndex * quadRowNb + yIndex] += 1;
232+
nodesQuads[i] = xIndex * quadRowNb + yIndex;
233+
}
234+
235+
// Computing quad steps
236+
// ALEXIS: here we need to build the second array containing nodes ids
237+
// in order for the quads iteration in force applications later.
238+
for (a = 0, i = 0; i < quadNb; i++) {
239+
a += quads[i];
240+
quadsSteps[i] = a;
241+
}
242+
}
243+
244+
419245
// 2) Repulsion
420246
//--------------
421247
// NOTES: adjustSize = antiCollision & scalingRatio = coefficient
422248

423249
if (W.settings.barnesHutOptimize) {
424250

425-
// Applying repulsion through regions
426-
for (n = 0; n < W.nodesLength; n += W.ppn) {
427-
rootRegion.applyForce(n);
428-
}
251+
// Applying forces through Barnes-Hut
252+
// TODO
429253
}
430254
else {
431255

0 commit comments

Comments
 (0)