title: How can I fill the camera's frustum with fix sized cubes?
body: <p>I believe this would be a <a href="https://en.wikipedia.org/wiki/Packing_problems#Packing_of_irregular_objects" rel="nofollow noreferrer">packing problem</a> of a trapezoid (camera's frustum). I want to fill the entire camera's frustum with fix sized cubes or cuboids. I need a set of cubes that fit within the camera's frustum every time the camera is moved. It is <strong>important</strong> that these cubes are axis-aligned in the world space, because otherwise there would be a lot of overlapping and I have to avoid this for my use-case.</p>
  
  <p>My initial thought was to create a considerable high number (higher than the world size) of cubes looping from an initial point <code>p=(0,0,0)</code>, make p the center of a cube and if the size is 2, then place <code>p2=(2,0,0)</code> as the center point for the next cube, <code>p3=(0,2,0)</code> for the third and so on... 
  The problem with this is that I will add to the scene a larger number of cubes than I really need, and every time I move the camera I will have to traverse through all the cubes to check whether they intersect or are contained within the camera's frustum, I believe this approach could be very expensive. </p>
  
  <p>How could I do this, is there a smarter way to do this?. </p>
  
  <p>On a side note, if the packaging problem could be done with variable sized 3D quadrilaterals, would it be an easier problem to solve? And how to do it?</p>
  
  <p><strong>Edit:</strong> I'm having a hard time understanding camera space vs camera world in some cases. I tried your approach but instead of considering the layers I created my own layers "artificially" and instead of transforming the cuboids using the inverse view matrix I'm getting the max/min points of the cuboids to get a bounding box in world space (I believe this is true). </p>
  
  <p><div class="snippet" data-lang="js" data-hide="false" data-console="true" data-babel="false">
  <div class="snippet-code">
  <pre class="snippet-code-html lang-html prettyprint-override"><code>this.createCuboids = (farCamera, xDist, yDist, nearPoints) =&gt; {
    //xDist is the difference of max.x and min.x
    //yDist is the difference of max.y and min.y
    //nearPoints are 4 points that represent the near plane
    const cuboidsCount = 5; //number of layers
    const cuboidThickness = farCamera/cuboidsCount; //depth for each layer
  
    let cuboidList = [];
  
    for (let i=1; i &lt; cuboidsCount+1; i++) {
        const cuboid = [
            new THREE.Vector3(nearPoints[0].x, nearPoints[0].y, nearPoints[0].z),  // nearTopLeft
            new THREE.Vector3(nearPoints[1].x, nearPoints[1].y, nearPoints[1].z),  // nearBottomRight
            new THREE.Vector3(nearPoints[2].x, nearPoints[2].y, nearPoints[2].z),  // nearTopRight
            new THREE.Vector3(nearPoints[3].x, nearPoints[3].y, nearPoints[3].z),  // nearBottomLeft
            new THREE.Vector3(nearPoints[0].x+xDist*i, nearPoints[0].y+yDist*i, nearPoints[0].z+cuboidThickness*i), // farTopLeft
            new THREE.Vector3(nearPoints[1].x+xDist*i, nearPoints[1].y+yDist*i, nearPoints[1].z+cuboidThickness*i), // farBottomRight
            new THREE.Vector3(nearPoints[2].x+xDist*i, nearPoints[2].y+yDist*i, nearPoints[2].z+cuboidThickness*i), // farTopRight
            new THREE.Vector3(nearPoints[3].x+xDist*i, nearPoints[3].y+yDist*i, nearPoints[3].z+cuboidThickness*i), // farBottomLeft
        ];
        cuboidList.push(cuboid);
    }
    //Finally get the X/Y/Z max and min as bounding box for each cuboid</code></pre>
  </div>
  </div>
  </p>
  
  <p>I'm interested to know if my code is equivalent to yours. The thing is that when creating the layers from the camera, and then translating them to the world space, most of them are overlapping when the camera is not aligned with the world axes, and this is not good because I would be querying the database very inefficiently. The next image shows the yellow part of two cuboids overlapping.</p>
  
  <p><a href="https://i.stack.imgur.com/LLZ8d.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/LLZ8d.png" alt="enter image description here"></a></p>
  
  <p>Hence, I'm trying a different approach where I get my initial bounding box of the frustum (in world space) and then start to split the bigger cuboid in 8 smaller ones until a certain number of "mini-cubes" and depth is reached. If a cuboid is inside the frustum we take it as a good cuboid and stop the split. In the same way if the cuboid is outside the frustum we discard it. The next image tries to show this.</p>
  
  <p><a href="https://i.stack.imgur.com/FQmFs.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/FQmFs.png" alt="enter image description here"></a></p>
  
  <p>This would be the piece of code for this approach.</p>
  
  <p><div class="snippet" data-lang="js" data-hide="false" data-console="true" data-babel="false">
  <div class="snippet-code">
  <pre class="snippet-code-html lang-html prettyprint-override"><code>// Given a bounding box of the frustum, create a cuboid mesh of depth d (recursive version)
  this.createCuboidMeshRecursive = (cube, depth) =&gt; {
      // chill, too deep
      if (depth &gt; 3) return;
      // this one is outside, discard it
      else if (!this.frustum.intersectsBox(cube)) return;
      // this one is inside, add it
      else if (this.frustum.intersectsBox(cube)) {
          this.cuboidMeshRecursive.push(cube);
          return;
      }
      else {
          this.auxBounding.set(cube.min,cube.max);
          const manyCubes = this.splitCube();
          manyCubes.forEach(subbox =&gt; {
              this.createCuboidMeshRecursive(subbox, depth+1);
          });
      }
  };</code></pre>
  </div>
  </div>
  </p>
  
  <p><strong>Final edit:</strong> With this recursive function you can create a cuboid mesh that fills the frustum, with a desired depth. <code>frustum.intersectsBox</code> is not enough to decide whether a cuboid should be discarded or not. I had to implement it according to my needs.</p>