Hi - great library as always. 👍

One question - in the readme you mention it could be used for polygon clipping. Can you give a hint to how that might work? Or did that refer testing whether polygons overlap a clipping area, as opposed to actually doing the clipping?

(My motivation here is wondering whether box-intersect could be useful in frustum-culling a 3D scene, faster than with octrees.)

Thanks!

I got this:

Uncaught EvalError: Refused to evaluate a string as JavaScript because 'unsafe-eval' is not an allowed source of script in the following Content Security Policy directive: "script-src 'self' 'nonce-iEsD2if45rrVbpVQzGD2Cw=='".

I'd love to use this module for spatial partitioning in a simulation I'm working on.

@mikolalysenko One challenge in my case is many boxes are created/destroyed at simulation time, and the api accepts a fixed list of boxes.

I worry inserting/splicing many array items will create a lot of memory gc pressure.

Would it be better to keep a fixed list of boxes, and just set some to empty? This would effectively be a pool I suppose.

Can you help me by persisting the data structure (streaming segment tree), so it can be used for bounds checks ("Find all boxes overlapping a point") later?

Or is it a completely stupid question?

looking at boxEmpty(d, box) function here https://github.com/mikolalysenko/box-intersect/blob/master/index.js#L9

I'm wondering what the format is for declaring a box empty, so that it's not included in intersection tests.

Is it simply passing an empty array [] ?

Or do we 0 out the box dimensions as in[0, 0, 0, 0] ?

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))
}