I am trying to recreate something like this:

http://threejs.org/examples/#webgl_buffergeometry_drawcalls

So I need to calculate distance between all particles and then draw a line between those that are close enough together. At the moment I am only thinking about how to approach this but I can not think of any reasonable method how to calculate a distance between all particles. Since I am working with 500x500 particles in 3D space I need some inexpensive solution.

http://threejs.org/examples/#webgl_buffergeometry_drawcalls 

So I need to calculate distance between all particles and then draw a line between those that are close enough together. At the moment I am only thinking about how to approach this but I can not think of any reasonable method how to calculate a distance between all particles. Since I am working with 500x500 particles in 3D space I need some inexpensive solution. 

drawing-lines-only-between-points-that-are-closer-than-the-distance-specified

i would just grab the source directly from that site, plug it into a js object, and start converting to jitter. you can draw both the points and lines with jit.gl.mesh, so the task would be simply to change their source to something that fills matrices for jit.gl.mesh.

check here for js examples on both gl scenes and filling matrices: /Users/Shared/Max 7/Examples/jitter-examples/javascript/

In the meantime one subquestion. I did a version where only one point is being compared to the rest of the particles (see the patch below) so only one point gets connected to the surrounding ones. If I specify each connection and feed the messages to jit.gl.sketch then of course everything works as expected. When I feed the matrix into jit.gl.mesh, which is the way I want to do it, I get this "random" connections (both examples are demonstrated in the patch below). So my question is how to bring some order into that "random connection" chaos. Edge flag matrix? Index matrix? Anything else? I want the jit.gl.mesh example to work exactly as jit.gl.sketch.

I just want to make sure that it is doable with jit.gl.mesh before I go into js.

I made a js version using matrices. There is twice as much calculation going on as needed (each vertex is compared with another one twice: "A" to "B" and then again "B" to "A"). I though it might be faster due to using matrices instead of getcell and doing all the cells individually. However the performance is far below expectations so I will make another "getcell" & "arrays" version in hope of better frame rate. This version runs smooth and sexy on my macbook pro for 200 vertices (60fps), a bit slower for 500 (cca 30 fps), 1000 at cca 10 fps and so on.

PS: you need xray.jit.cellcoords to run this patch and hence also 32bit version of Max.

I would also like to know if using jit.gl.sketch is slower then using jit.gl.mesh. In case the mesh option is a better one: how to define which vertices to connect in jit.gl.mesh and which not?

var sketch = new JitterObject("jit.gl.sketch","okno"); // jit.sketch draw to render context okno

var cellcoords = new JitterObject ("xray.jit.cellcoords");

// create [jit.expr] object for the bang() function

var myexpr = new JitterObject("jit.expr");

myexpr.expr = "in[0].p[0]+in[0].p[1]+in[0].p[2]"; // expression: sum all the planes in the input matrix

// create the Jitter matrices we need to store our data

var particlemat = new JitterMatrix("jitnoise");

// number of particles defined by "incoming" matrix

var distmat = new JitterMatrix(3, "float32", PARTICLE_COUNT);

// temporary matrix for the bang_op() function

var tempmat = new JitterMatrix(3, "float32", PARTICLE_COUNT);

// temporary summing matrix for the bang_op() function

var summat = new JitterMatrix(1, "float32", PARTICLE_COUNT);

// matrix of cell coordinates wanted (distances

var celcordmat = new JitterMatrix(1, "float32", PARTICLE_COUNT);

// a scalar matrix to store the current particle that is being compared with the others

var scalarmat = new JitterMatrix(3, "float32", PARTICLE_COUNT);

    for(var i = 0; i < PARTICLE_COUNT; i++)

    // do one iteration per each particle point

        // choose a particle and call it a probe

        probe = particlemat.getcell(i);

        // create a scalar matrix out of the current probe:

        // subtract our particle positions from the current probe

        // and store in a temporary matrix (x,y,z):

        tempmat.op("-", scalarmat, particlemat);

        // square to create a cartesian distance matrix (x*x, y*y, z*z):

        distmat.op("*", tempmat, tempmat);

        // sum the planes of the distance matrix (x*x+y*y+z*z) and output a 1 plane matrix sumat that represent distance

        // "in[0].p[0]+in[0].p[1]+in[0].p[2]" :

        myexpr.matrixcalc(distmat, summat);

     //output a matrix of 0s and 1s. if 1, that cell needs to be connected to probe

        //find coordinates of cells with value 1 and output them in a matrix celcordmat

        cellcoords.matrixcalc(summat, celcordmat);

        //get the size of the celcordmat matrix

        currentdim = celcordmat.dim;

        //get values from all the celcordmat matrix cells, call them targets and connect them with probes with jit.gl.sketch

        for (n = 0; n < currentdim; n++)

     target = celcordmat.getcell (n);

     targetvalue = particlemat.getcell(target);

     sketch.linesegment(probe, targetvalue);

var sketch = new JitterObject("jit.gl.sketch","okno"); // jit.sketch draw to render context okno
sketch.lighting_enable = 0;
sketch.cull_face = 0;
sketch.antialias = 1;
sketch.blend_enable = 1;
sketch.depth_enable = 1;

// create [jit.expr] object for the bang() function
var myexpr = new JitterObject("jit.expr");
myexpr.expr = "in[0].p[0]+in[0].p[1]+in[0].p[2]"; // expression: sum all the planes in the input matrix 

// matrix of x,y,z particle vertices
var particlemat = new JitterMatrix("jitnoise");
// number of particles defined by "incoming" matrix
var PARTICLE_COUNT = particlemat.dim;
// matrix for aggregate distances
var distmat = new JitterMatrix(3, "float32", PARTICLE_COUNT);
// temporary matrix for the bang_op() function
var tempmat = new JitterMatrix(3, "float32", PARTICLE_COUNT);
// temporary summing matrix for the bang_op() function
var summat = new JitterMatrix(1, "float32", PARTICLE_COUNT);
// matrix of cell coordinates wanted (distances
var celcordmat = new JitterMatrix(1, "float32", PARTICLE_COUNT);
// a scalar matrix to store the current particle that is being compared with the others
var scalarmat = new JitterMatrix(3, "float32", PARTICLE_COUNT); 

function min_dist(value)
{
min_distance = value;
}

PS: And if there is anything in the js code that I should change to get a better performance please let me know (having in mind that it is a matrix version)...although most of the code is taken and adapted from js tutorial 46.

my guess is jit.gl.mesh will be faster, but hard to say. you can use the index matrix to change the ordering of the vertices. you will get one line for every two indices you provide. here's a very basic example of how to use the index matrix:

Thanks a lot Rob for your example, finally I understand index matrix!

I have some js&Max related questions since I realised that the framerate in my patch increases for 20fps if I use a number in the for loop instead of global variable. Since I have two such variables the framerate goes from 30 to almost 60 if use actual numbers. And of course I want to use variables so I can control them from the patcher. Here is the new code (and a patch) that gives me so far the best results:

// code made with the great help of Frédéric Dufeu

var sketch = new JitterObject("jit.gl.sketch","okno");

var noiseMatrix = new JitterMatrix("jitnoise");

     var cell = noiseMatrix.getcell(i);

if (((diffx * diffx) + (diffy * diffy) + (diffz * diffz)) < 0.05)

sketch.linesegment (point_o.x, point_o.y, point_o.z, point_d.x, point_d.y, point_d.z);

===========================================================

So as you can see I have two variable commented out: nrOfPartic and min_distance. If you replace 0.05 with min_distance in the code you loose 20 fps and then another 10 for changing 600 to nrOfPartic.

And I also have another question. Here is the code that I thought that it would perform better as the one above. The reason for that is that I am not moving all data from matrix into a new array for each bang but I am just taking the values from the matrix. However the framarate is around 15 times slower as in the js code posted above:

     var cell_B = noiseMatrix.getcell(j);

     var diffx = cell_B[0]-cell_A[0];

     var diffy = cell_B[1]-cell_A[1];

     var diffz = cell_B[2]-cell_A[2];

1. why using numbers instead of variables affects performance so dramatically?

2. why is second js code around 15 times slower then the first one although is much shorter and with less operations.

Thanks a lot Rob for your example,  finally I understand index matrix! 

// code made with the great help of Frédéric Dufeu  

var sketch = new JitterObject("jit.gl.sketch","okno");
sketch.lighting_enable = 0;
sketch.cull_face = 1;
sketch.antialias = 1;
sketch.blend_enable= 1;
sketch.depth_enable = 1;

//var nrOfPartic = 600;
//var min_distance = 0.05;

function bang()
{
    sketch.reset();
    var i;
    points = [];
    for (i = 0; i < 600; i++)
    {
        var point = {};
	    var cell = noiseMatrix.getcell(i);
        point.x = cell[0];
        point.y = cell[1];
        point.z = cell[2];
        points.push(point);
    }

    for (i = 0; i < 600; i++)
    {
        var point_o = points[i];
        var j=i;
        for (j ; j < 600; j++)
        {
            var point_d = points[j];
            var diffx = point_d.x - point_o.x;
            var diffy = point_d.y - point_o.y;
            var diffz = point_d.z - point_o.z;
            if (((diffx * diffx) + (diffy * diffy) + (diffz * diffz)) < 0.05)
            {
             sketch.linesegment (point_o.x, point_o.y, point_o.z, point_d.x, point_d.y, point_d.z);
            }

===========================================================
===========================================================

So as you can see I have two variable commented out:  nrOfPartic and min_distance.  If you replace 0.05 with min_distance in the code you loose 20 fps and then another 10 for changing 600 to nrOfPartic. 

inlets = 1;
var sketch = new JitterObject("jit.gl.sketch","okno");
var noiseMatrix = new JitterMatrix("jitnoise");

function bang()
{
    sketch.reset();
    var i;
    for (i = 0; i < 600; i++)
    {
        var cell_A = noiseMatrix.getcell(i);
        var j=i;
        for (j ; j < 600; j++)
        {
	        var cell_B = noiseMatrix.getcell(j);
	        var diffx = cell_B[0]-cell_A[0];
	        var diffy = cell_B[1]-cell_A[1];
	        var diffz = cell_B[2]-cell_A[2];
            if (((diffx * diffx) + (diffy * diffy) + (diffz * diffz)) < 0.05)
            {
             sketch.linesegment (cell_A, cell_B);
            }

1. why using numbers instead of variables affects performance so dramatically?
2. why is second js code around 15 times slower then the first one although is much shorter and with less operations.


PS: question 3: I am just learning Java to in order to make a Java version that will hopefully perform better. Anything I should know so I won't make similar mistakes as here with js? For instance should I move all matrix data to Java arrays for each bang or should I just reference matrix cells? I don't know, any hints are very wellcome.

i'm no jiter-java expert, but i'm pretty sure you'd be much better off moving the matrix into a java array and then doing all your array-accessing (the for loop) from inside java, otherwise you are crossing the java-max bridge many more times than necessary, which is apparently very expensive

Thank you Floating Point. I see, getcell message is expensive then. So basically only if I would be using C the bridge between Max patcher and my external would not be expensive because I would remain in the "C world"?

What would be the fastest way to move a 1D 3plane matrix into Java and prepare it to be ready for the fastest work on cell to cell basis? Should I create lists in Max (jit.unpack & jit.spill), create 3 inputs (or rather one?) and go from there? Or would it be better using getcell message (or equivalent in Java) and make arrays inside Java?

i highly doubt that java will be faster than doing the calculations all in max.

what could help is to optimize the algorithm a bit.

for example i would really not like to compare the position of 500 points against 499 other points, then get all distances in realtime, and that every frame.

mabye you can divide your coordinate system up into 16 smaller spaces, and first operate _within these parts.

because _within each of these frames the _maximum possible distance between all points is known, isnt it? so that you can, for example, exclude all combinations within these spaces already.

for example i would really not like to compare the position of 500 points against 499 other points, then get all distances in realtime, and that every frame. 

mabye you can divide your coordinate system up into 16 smaller spaces, and first operate _within these parts. 

because _within each of these frames the _maximum possible distance between all points is known, isnt it? so that you can, for example, exclude all combinations within these spaces already.


Hey Roman thanks for your advice. I tried creating a Max version and is much slower then even js one although the algorithm is very different (see the patch below). I was using matrices while changing the dimension of the matrix for each iteration (using submatrix and dim and offset attributes)....I thought that this should be the fastest Max version. So instead of two uzi-s I have only one...the patch algorithm goes like this:

- compare particle 1 with all the rest (getcell 0 and create 2 matrices of size N-1; first matrix has all cells set to the value of cell 0, the second matrix are remaining particles)

- do distance calculation with matrices using jit.op and jit.expr

- use jit.op @op < min_distance to find critical distances

- jit.spill ---> zl.sub to get positions of cells that have distances less then min_distance

and then for each iteration the matrices are getting smaller for 1 cell so that at the last iteration only 2 cells are being compared

About splitting the space in 16 smaller spaces. First I need to find a way that will be the fastest and then I will think more about your suggestion. Although I think it shouldn't make much difference. Because if a point is near the vertex of rectangle space I need to check in all 7 surrounding spaces. Also I intend to feed different "particle systems" in this patch so the particles would sometimes be only in one space and move around as a flock, and min_distance will be dynamic, also the particles will go "out of frame" and camera after them so I would need to make dynamic rectangular spaces which I reckon would at the end consume even more power.

- N particles
- compare particle 1 with all the rest (getcell 0 and create 2 matrices of size N-1; first matrix has all cells set to the value of cell 0, the second matrix are remaining particles)
- do distance calculation with matrices using jit.op and jit.expr
- use jit.op @op < min_distance to find critical distances
- jit.spill ---> zl.sub to get positions of cells that have distances less then min_distance
- zl.sub --> getcell

About splitting the space in 16 smaller spaces. First I need to find a way that will be the fastest and then I will think more about your suggestion. Although I think it shouldn't make much difference. Because if a point is near the vertex of rectangle space I need to check in all 7 surrounding spaces. Also I intend to feed different "particle systems" in this patch so the particles would sometimes be only in one space and move around as a flock, and min_distance will be dynamic, also the particles will go "out of frame" and camera after them so I would need to make dynamic rectangular spaces which I reckon would at the end consume even more power.


if you want to convert the js code to java here is a starting point:

https://docs.cycling74.com/max7/tutorials/jitterchapter51

I've never done any jitter processing in java so this is where I'd start...

as far as efficiency I would certainly not convert the matrices to lists in max before importing into java or anything like that... just use the copyVectorToArray() method -- once in java-land, stay in there until you've got your required matrix to output... having said that you really need the advice of someone who's done this kind of thing before.

having a quick look at the js code it looks inefficient (brute force approach), as the nested loops check every particle's distance from every other, so it could be optimized, but you'd probably have to be well-versed in graph theory to do that-- Roman's divide and conquer suggestion might work inside java if you can get your head around it...

I've never done any jitter processing in java so this is where I'd start...
as far as efficiency I would certainly not convert the matrices to lists in max before importing into java or anything like that... just use the copyVectorToArray() method -- once in java-land, stay in there until you've got your required matrix to output... having said that you really need the advice of someone who's done this kind of thing before.
having a quick look at the js code it looks inefficient (brute force approach), as the nested loops check every particle's distance from every other, so it could be optimized, but you'd probably have to be well-versed in graph theory to do that-- Roman's divide and conquer suggestion might work inside java if you can get your head around it...


drawing lines only between points that are closer than the distance specified