gpu.js

[formula1]

I think your Library is amazing. I also think gpu.js is pretty great too. Your library is already incredibly fast, I'm wondering if there's opportunity to make it even faster with GPU.js

Some thoughts

• looks like we could send the abbs as 2 variables as 2 dimensional arrays
  • variable a is red boxes and b is blue boxes
  • dimension one is the boxes
  • dimension two is the individual boxes mins and maxes at each dimension
• the output would be a 1 dimensional array
  • first dimension would be the maximum amount of possible collisions
    • for red vs blue I believe red.length * blue.length
    • for red vs red I believe red.length * (red.length - 1)
  • within that array is a 2 dimensional array featuring box a and box b

A few issues

• I'm not sure how your handling it now but we want to avoid each red box from coloring with itself
  • so perhaps there's two kernels
  • one for red vs red and one for red vs blue
  • this would also decrease the possible collisions to be (red.length * (red.length - 1)) if my brief calculations are correct
• I'm not sure it's possible that this cannot be achieved without brute force.
  • I don't know how your handling the the intersections, your code is pretty clean but my mind doesn't fully understand it.
  • but I imagine there are ways to optimize it by sorting the boxes so you can find them so that you don't have to iterate over each.
  • I'm not confident that's possible. There's a setImmutable function but I'm not sure how you able to achieve the Speeds you get. Perhaps your using something like bucket sort to keep track. But with how many possible values a box can have I'm not confident that is still going to achieve the Speeds you did
• Another issue is that this returns a full list despite not necessarily needing a full list

Some unworking code

V1

const gpu = new GPU();
const kernel = gpu.createKernel(function(red, blue) {
  // We start at red[0]
  // Continue for until we reach blue length - 1
  // We should never reach blue.length unless we go to the next item
  // Then when we reach blue length we should be at red[1]
  // Again until we reach blue.length + blue.length - 1
  // At 2 * bLen we should be at red[2]
  const bLen = this.constants.bLen;
  const rI = Math.floor(this.thread.x/bLen)
  const bI = this.thread.x%bLen
  If(intersects(red[rI], blue[bI])) return [rI, bI]
  return []
  }, { dynamic arguments: true, dynamicOutput: true });

function intersectBoxes(red, blue){
  kernel.setOutput([red.length * blue.length])
  kernal.setConstants({ blen: blue.length })
  // Bad because we reiterate after already iterating
  return kernal(red, blue).filter((boxes)=>(boxes.length))
}

Here's version 2 with maybe less filtering but still concacting and I'm not confident we want to iterate when we are using the GPU. Maybe they are doing some interesting compilation on the other side. In addition I don't know if it's possible to create arrays while in the gpu

const gpu = new GPU();
const kernel = gpu.createKernel(function(red, blue) {
  const intersections = []
  const bLen = this.constants.bLen;
  const rItem = red[this thread.x];
  for(var i = 0; I < bLen; I++){
    If(intersects(red[this.thread.x], blue[i])){
      intersections[intersections length] = [this thread.x, I]
    }
  }
  return intersections
  }, { dynamic arguments: true, dynamicOutput: true });

function intersectBoxes(red, blue){
  kernel.setOutput([red.length])
  kernal.setConstants({ blen: blue.length })
  // Bad because we reiterate after already iterating
  return kernal(red, blue).reduce((a,b)=>(a.concat(b)),[])
}

V3 that tries to do 2 dimensional but ends up just being the same as version 1 so I'm not confident it's much better

const gpu = new GPU();
const kernel = gpu.createKernel(function(red, blue) {
  const rBox = red[this thread.x];
  const bBox = blue[this.thread.y]
  if(intersects(rBox, bBox)) return [this.thread.x, this thread.y]
  return []
  }, { dynamic arguments: true, dynamicOutput: true });

function intersectBoxes(red, blue){
  kernel.setOutput([red.length, blue length])
  kernal.setConstants({ blen: blue.length })
  // Bad because we reiterate after already iterating
  return kernal(red, blue)
  .reduce((a,b)=>(a.concat(b)),[])
  .filter((boxes)=>(boxes.length))
}