--- libgender/oct.C	2004/10/02 15:54:43	1.1
+++ libgender/oct.C	2004/10/09 16:37:31	1.39
@@ -1,14 +1,185 @@
 #include <cstdlib>
 
+#include <vector>
+
+using namespace std;
+
+#include <GL/gl.h>
+
 #include "oct.h"
+#include "view.h"
+#include "entity.h"
+
+octant world(0, sector (SOFFS_MIN, SOFFS_MIN, SOFFS_MIN), MAXEXTENT);
 
-void octant::remove (entity_base *e)
+octant::octant (octant *parent, const sector &orig, uoffs extent)
+: parent(parent), orig(orig), extent(extent)
 {
-  abort ();
+  for (fill = 8; fill--; )
+    sub[fill] = 0;
 }
 
 octant::~octant ()
 {
+  for (fill = 8; fill--; )
+    delete sub[fill];
+}
+
+static bool overlap (const sector &o1, uoffs ea, const sector &a, const sector &b)
+{
+  ea /= 2;
+
+  sector center_1 = o1 + ea;
+  sector size_2   = b - a;
+  sector center_2 = a + size_2 / 2;
+
+  return abs (center_1 - center_2) <= ea + size_2;
+}
+
+void octant::add (entity *e)
+{
+  const sector &a = e->a;
+  const sector &b = e->b;
+
+  if (overlap (orig, extent, a, b))
+    {
+      uoffs extent2 = extent / 2;
+      uoffs size = max (abs (b - a));
+
+      if (size > extent2 || !extent2)
+        {
+          push_back (e);
+          e->o.push_back (this);
+          return;
+        }
+
+      for (int i = 8; i--; )
+        {
+          sector s = orig;
+          s.offset (i, extent2);
+
+          if (overlap (s, extent2, a, b))
+            {
+              if (!sub[i])
+                sub[i] = new octant (this, s, extent2);
+
+              sub[i]->add (e);
+            }
+        }
+    }
+}
+
+void octant::remove (entity *e)
+{
+}
+
+void octant::detect_visibility (view &ctx)
+{
+  visibility_state &vs = ctx.vismap[this];
+
+  if (vs.generation != ctx.generation)
+    vs.visibility = visibility_state::UNKNOWN;
+
+  if (orig <= ctx.orig && ctx.orig <= orig + extent)
+    {
+      vs.visibility = visibility_state::PARTIAL;
+      vs.generation = ctx.generation;
+    }
+  else
+    {
+      GLfloat extent2 = 0.5F * (GLfloat)extent;
+      point center = point (orig) + extent2 - point (ctx.orig);
+
+      GLfloat rad = ctx.diagfact * extent2;
+
+      if (ctx.frustum.t.distance (center) < -rad) return;
+      if (ctx.frustum.b.distance (center) < -rad) return;
+      if (ctx.frustum.l.distance (center) < -rad) return;
+      if (ctx.frustum.r.distance (center) < -rad) return;
+      if (ctx.frustum.n.distance (center) < -rad) return;
+
+      GLfloat fd = ctx.frustum.f.distance (center);
+
+      if (fd < -rad)
+        {
+          if (fd < -rad * 3.F)
+            return;
+
+          ctx.farlist.push_back (this);
+          return;
+        }
+    }
+
+  if (vs.visibility == visibility_state::UNKNOWN)
+    vs.visibility = visibility_state::FULL;
+
+  if (size ())
+    ctx.vislist.push_back (this);
+
+  // node to start with
+  unsigned char si = ctx.d.x < 0 ? 1 : 0
+                   | ctx.d.y < 0 ? 2 : 0
+                   | ctx.d.z < 0 ? 4 : 0;
+
+  // bit-toggle to find next child for front-to-back order
+  static unsigned char next[8]
+    = { 0,  0^1, 1^2, 2^4,  4^3, 3^5, 5^6,  6^7 };
+
+  for (int i = 0; i < 8; i++)
+    {
+      si ^= next[i];
+
+      if (sub[si])
+        sub[si]->detect_visibility (ctx);
+    }
+
+  vs.generation = ctx.generation;
+}
+
+void octant::display (view &ctx)
+{
+#if 0
+  glBegin (GL_LINES);
+  sector s = orig - ctx.orig;
+  vec3 clr(0, 0.8, 0);
+  glMaterialfv (GL_FRONT_AND_BACK, GL_DIFFUSE, (const GLfloat*)&clr);
+
   for (int i = 8; i--; )
-    delete sub[i];
+    for (int ji = 3; ji--; )
+      {
+        int j = i | (1 << ji);
+        if (i != j)
+          {
+            glVertex3i (s.x + !!(i & 1) * extent,
+                        s.y + !!(i & 2) * extent,
+                        s.z + !!(i & 4) * extent);
+            glVertex3i (s.x + !!(j & 1) * extent,
+                        s.y + !!(j & 2) * extent,
+                        s.z + !!(j & 4) * extent);
+          }
+      }
+  
+  glEnd ();
+#endif
+
+  for (iterator i = end (); i != begin (); )
+    (*--i)->display (ctx);
+}
+
+void octant::draw_bbox (view &ctx)
+{
+  sector s = orig - ctx.orig;
+
+  gl::draw_box (ctx, s, s + extent);
+}
+
+void octant::event (occ_query &ev)
+{
+  if (ev.r <= 5)
+    return;
+
+  //ev.v.vismap[this].visibility = visibility_state::FULL;
+  ev.v.far = ev.v.near + ev.v.frustum.n.distance (orig);
+  printf ("OCT(%x,%x,%x+%x) samples %d\n", orig.x, orig.y, orig.z, extent, ev.r);
 }
+