title: Frustum Culling, implementation
body: <p>I am currently trying to implement frustum culling (again) for my world. My world consists of chunks with the size 16x256x16 (x, y, z):</p>
  
  <pre><code>Frustum frustum = Frustum(engine.proj * engine.view);
  
  foreach(chunkc, chunk; chunks) {
      vec3i w_chunkc = vec3i(chunkc.x*16, chunkc.y*256, chunkc.z*16);
  
      AABB aabb = AABB(vec3(w_chunkc), vec3(w_chunkc.x+16, w_chunkc.y+256, w_chunkc.z+16));
      if(aabb in frustum) {
          bind(engine, chunk);
  
          glDrawArrays(GL_TRIANGLES, 0, cast(uint)chunk.vbo_vcount);
      }
  }
  </code></pre>
  
  <p><code>chunkc</code> holds the coordinates of the whole <code>chunk</code> e.g. <code>[0, 0, -2]</code>. So to get the chunks bounding box, I have to multiply these coordinates by the size of each chunk to get the minimal position of the AABB and add the size to each component to get the max. position of the AABB. Then I check this AABB against the frustum.</p>
  
  <p>Frustum implementation:</p>
  
  <pre><code>struct Frustum {
      enum {
          LEFT, /// Used to access the planes array.
          RIGHT, /// ditto
          BOTTOM, /// ditto
          TOP, /// ditto
          NEAR, /// ditto
          FAR /// ditto
      }
  
      Plane[6] planes; /// Holds all 6 planes of the frustum.
  
      @safe pure nothrow:
  
      @property ref Plane left() { return planes[LEFT]; }
      @property ref Plane right() { return planes[RIGHT]; }
      @property ref Plane bottom() { return planes[BOTTOM]; }
      @property ref Plane top() { return planes[TOP]; }
      @property ref Plane near() { return planes[NEAR]; }
      @property ref Plane far() { return planes[FAR]; }
  
      /// Constructs the frustum from a model-view-projection matrix.
      /// Params:
      /// mvp = a model-view-projection matrix
      this(mat4 mvp) {
          planes = [
              // left
              Plane(mvp[0][3] + mvp[0][0], // note: matrices are row-major
                  mvp[1][3] + mvp[1][0],
                  mvp[2][3] + mvp[2][0],
                  mvp[3][3] + mvp[3][0]),
  
              // right
              Plane(mvp[0][3] - mvp[0][0],
                  mvp[1][3] - mvp[1][0],
                  mvp[2][3] - mvp[2][0],
                  mvp[3][3] - mvp[3][0]),
  
              // bottom
              Plane(mvp[0][3] + mvp[0][1],
                  mvp[1][3] + mvp[1][1],
                  mvp[2][3] + mvp[2][1],
                  mvp[3][3] + mvp[3][1]),
              // top
              Plane(mvp[0][3] - mvp[0][1],
                  mvp[1][3] - mvp[1][1],
                  mvp[2][3] - mvp[2][1],
                  mvp[3][3] - mvp[3][1]),
              // near
              Plane(mvp[0][3] + mvp[0][2],
                  mvp[1][3] + mvp[1][2],
                  mvp[2][3] + mvp[2][2],
                  mvp[3][3] + mvp[3][2]),
              // far
              Plane(mvp[0][3] - mvp[0][2],
                  mvp[1][3] - mvp[1][2],
                  mvp[2][3] - mvp[2][2],
                  mvp[3][3] - mvp[3][2])
          ];
  
          normalize();
      }
  
      /// Constructs the frustum from 6 planes.
      /// Params:
      /// planes = the 6 frustum planes in the order: left, right, bottom, top, near, far.
      this(Plane[6] planes) {
          this.planes = planes;
          normalize();
      }
  
      private void normalize() {
          foreach(ref e; planes) {
              e.normalize();
          }
      }
  
      /// Checks if the $(I aabb) intersects with the frustum.
      /// Returns OUTSIDE (= 0), INSIDE (= 1) or INTERSECT (= 2).
      int intersects(AABB aabb) {
          vec3 hextent = aabb.half_extent;
          vec3 center = aabb.center;
  
          int result = INSIDE;
          foreach(plane; planes) {
              float d = dot(center, plane.normal);
              float r = dot(hextent, abs(plane.normal));
  
              if(d + r &lt; -plane.d) {
                  // outside
                  return OUTSIDE;
              }
              if(d - r &lt; -plane.d) {
              result = INTERSECT;
              }
          }
  
          return result;
      }
  
      /// Returns true if the $(I aabb) intersects with the frustum or is inside it.
      bool opBinaryRight(string s : "in")(AABB aabb) {
          return intersects(aabb) &gt; 0;
      }
  }
  </code></pre>
  
  <p>And the AABB implementation:</p>
  
  <pre><code>struct AABBT(type) {
          alias type at; /// Holds the internal type of the AABB.
          alias Vector!(at, 3) vec3; /// Convenience alias to the corresponding vector type.
  
          vec3 min = vec3(0.0f, 0.0f, 0.0f); /// The minimum of the AABB (e.g. vec3(0, 0, 0)).
          vec3 max = vec3(0.0f, 0.0f, 0.0f); /// The maximum of the AABB (e.g. vec3(1, 1, 1)).
  
          @safe pure nothrow:
  
          /// Constructs the AABB.
          /// Params:
          /// min = minimum of the AABB
          /// max = maximum of the AABB
          this(vec3 min, vec3 max) {
              this.min = min;
              this.max = max;
          }
  
          /// Constructs the AABB around N points (all points will be part of the AABB).
          static AABBT from_points(vec3[] points) {
              AABBT res;
  
              foreach(v; points) {
                  res.expand(v);
              }
  
              return res;
          }
  
          /// Expands the AABB by another AABB.
          void expand(AABBT b) {
              if (min.x &gt; b.min.x) min.x = b.min.x;
              if (min.y &gt; b.min.y) min.y = b.min.y;
              if (min.z &gt; b.min.z) min.z = b.min.z;
              if (max.x &lt; b.max.x) max.x = b.max.x;
              if (max.y &lt; b.max.y) max.y = b.max.y;
              if (max.z &lt; b.max.z) max.z = b.max.z;
          }
  
          /// Expands the AABB, so that $(I v) is part of the AABB.
          void expand(vec3 v) {
              if (v.x &gt; max.x) max.x = v.x;
              if (v.y &gt; max.y) max.y = v.y;
              if (v.z &gt; max.z) max.z = v.z;
              if (v.x &lt; min.x) min.x = v.x;
              if (v.y &lt; min.y) min.y = v.y;
              if (v.z &lt; min.z) min.z = v.z;
          }
  
  
          /// Returns true if the AABBs intersect.
          /// This also returns true if one AABB lies inside another.
          bool intersects(AABBT box) const {
              return (min.x &lt; box.max.x &amp;&amp; max.x &gt; box.min.x) &amp;&amp;
                  (min.y &lt; box.max.y &amp;&amp; max.y &gt; box.min.y) &amp;&amp;
                  (min.z &lt; box.max.z &amp;&amp; max.z &gt; box.min.z);
          }
  
          /// Returns the extent of the AABB (also sometimes called size).
          @property vec3 extent() const {
              return max - min;
          }
  
          /// Returns the half extent.
          @property vec3 half_extent() const {
              return 0.5 * (max - min);
          }
  
          /// Returns the area of the AABB.
          @property at area() const {
              vec3 e = extent;
              return 2.0 * (e.x * e.y + e.x * e.z + e.y * e.z);
          }
  
          /// Returns the center of the AABB.
          @property vec3 center() const {
              return 0.5 * (max + min);
          }
  
          /// Returns all vertices of the AABB, basically one vec3 per corner.
          @property vec3[] vertices() const {
              return [
                  vec3(min.x, min.y, min.z),
                  vec3(min.x, min.y, max.z),
                  vec3(min.x, max.y, min.z),
                  vec3(min.x, max.y, max.z),
                  vec3(max.x, min.y, min.z),
                  vec3(max.x, min.y, max.z),
                  vec3(max.x, max.y, min.z),
                  vec3(max.x, max.y, max.z),
              ];
          }
  
          bool opEquals(AABBT other) const {
              return other.min == min &amp;&amp; other.max == max;
          }
      }
  
      alias AABBT!(float) AABB;
  </code></pre>
  
  <p>So far in theory, unfortunatly I get completly wrong results, in certain dirctions (<code>z-</code> and <code>x+</code>) the whole world disappears and in all other directions nothing is culled.</p>
  
  <p>I hope anyone of you has an idea why this doesn't work.</p>
  
  <p><strong>EDIT (different method of checking AABB agains Frustum):</strong></p>
  
  <pre><code>bool intersects2(AABB aabb) {
      foreach(plane; planes) {
          if(plane.a * aabb.min.x + plane.b * aabb.min.y + plane.c * aabb.min.z + plane.d &gt; 0 )
              continue;
          if(plane.a * aabb.max.x + plane.b * aabb.min.y + plane.c * aabb.min.z + plane.d &gt; 0 )
              continue;
          if(plane.a * aabb.min.x + plane.b * aabb.max.y + plane.c * aabb.min.z + plane.d &gt; 0 )
              continue;
          if(plane.a * aabb.max.x + plane.b * aabb.max.y + plane.c * aabb.min.z + plane.d &gt; 0 )
              continue;
          if(plane.a * aabb.min.x + plane.b * aabb.min.y + plane.c * aabb.max.z + plane.d &gt; 0 )
              continue;
          if(plane.a * aabb.max.x + plane.b * aabb.min.y + plane.c * aabb.max.z + plane.d &gt; 0 )
              continue;
          if(plane.a * aabb.min.x + plane.b * aabb.max.y + plane.c * aabb.max.z + plane.d &gt; 0 )
              continue;
          if(plane.a * aabb.max.x + plane.b * aabb.max.y + plane.c * aabb.max.z + plane.d &gt; 0 )
              continue;
          return false;
      }
      return true;
  }
  </code></pre>
  
  <p><strong>Edit 2 (Example input):</strong></p>
  
  <p>Here is a MVP:</p>
  
  <p><code>[[1.18424,0,0.31849,-331.577],
      [0.111198,1.51016,-0.413468,-88.5585],
      [0.251117,-0.274135,-0.933724,214.897],
      [0.249864,-0.272768,-0.929067,215.82]]</code></p>
  
  <p>And a possible failing AABB:
  <code>min: (14*16, 0, 13*16)
     max: (14*16+16, 256, 13*16+16)
  </code></p>