#include <cstdlib>

#include <vector>
using namespace std;

#include "opengl.h"

#include "oct.h"
#include "view.h"
#include "entity.h"

enum visibility_state { FULL, PARTIAL, SMALL, OCCLUDED, SUBTREE_OCCLUDED };

struct evis {
  visibility_state state;
  double last; // time of last check
  evis () : last(0.), state(FULL) { };
};

struct oct_visibility : visibility_base
{
  typedef map<entity *, evis> evismap;
  evismap vismap;

  visibility_state state;

  oct_visibility (octant &oct)
  : state(FULL)
  {
  }
};

octant world(0, sector (SOFFS_MIN, SOFFS_MIN, SOFFS_MIN), MAXEXTENT);

octant::octant (octant *parent, const sector &orig, uoffs extent)
: parent(parent)
, orig(orig)
, extent(extent)
{
  for (fill = 8; fill--; )
    sub[fill] = 0;
}

visibility_base *octant::new_visibility ()
{
  return new oct_visibility (*this);
}

void octant::clear_visibility (visibility_base *vs)
{
  ((oct_visibility *)vs)->vismap.clear ();
}

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 >> 1);

  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 >> 1;
      uoffs size = max (abs (b - a));

      if (size >= extent2 >> 1)
        {
          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);
                  fill++;
                }

              sub[i]->add (e);
            }
        }
    }
}

void octant::remove (entity *e)
{
}

bool octant::detect_visibility (view &ctx)
{
  GLfloat extent2 = 0.5F * (GLfloat)extent;
  sector centeri = orig + (extent >> 1) - ctx.orig;
  point centerf = point (centeri) + ((extent & 1) ? 0.5F : 0.F);

  GLfloat rad = ctx.diagfact * extent2;

  if (!overlap (ctx.frustum.c, sphere (centerf, rad)))
    return false;

  oct_visibility &vs = *(oct_visibility *)get_visibility (ctx);

  if (orig <= ctx.orig && ctx.orig <= orig + extent)
    vs.state = PARTIAL;
  else
    {
      if (distance (ctx.frustum.t, centerf) < -rad) return false;
      if (distance (ctx.frustum.b, centerf) < -rad) return false;
      if (distance (ctx.frustum.l, centerf) < -rad) return false;
      if (distance (ctx.frustum.r, centerf) < -rad) return false;
      if (distance (ctx.frustum.n, centerf) < -rad) return false;

#if 0
      GLfloat fd = distance (ctx.frustum.f, centerf);

      if (fd < -(ctx.c_far - ctx.z_far) -rad * 3.F)
        return false;
#endif
    }

#if 0
  if (vs.state == OCCLUDED && size ())
    {
      if (size ())
        ctx.vislist.push_back (this);
      return false;
    }
#endif

  GLfloat z = ctx.z_near + distance (ctx.frustum.n, centerf) + rad;
  if (ctx.perspfact * extent / z < 1.) // very crude "too small to see" check
    return false;
  //printf ("z %f, perspfact %f, z*p %f\n", z, ctx.perspfact, ctx.perspfact / z);

#if 0
  if (vs.state == PARTIAL || vs.state == FULL)
    ctx.nc_far = max (ctx.nc_far, z);
#endif

  if (vs.state == SUBTREE_OCCLUDED)
    {
      ctx.vislist.push_back (this);
      return false;
    }
 
  // node to start with
  unsigned char si = centeri.x > 0 ? 1 : 0
                   | centeri.y > 0 ? 2 : 0
                   | centeri.z > 0 ? 4 : 0;

  // bit-toggle to find next child for front-to-back order
  static unsigned char toggle[8+1]
    = { 0,  0^1, 1^2, 2^4, 4^3, 3^5, 5^6,  6^7, 0 };

  bool visible = size () && (vs.state == PARTIAL || vs.state == FULL);

  unsigned char *next = toggle;
  do
    {
      si ^= *next;

      if (sub[si])
        visible = visible | sub[si]->detect_visibility (ctx);
    }
  while (*++next);

  if (visible)
    {
      if (size ())
        ctx.vislist.push_back (this);
    }
  else
    {
      vs.state = SUBTREE_OCCLUDED;
      ctx.vislist.push_back (this);
    }

  return visible;
}

void octant::display (view &ctx)
{
  oct_visibility &vs = *(oct_visibility *)get_visibility (ctx);

  if (vs.state == OCCLUDED || vs.state == SUBTREE_OCCLUDED)
    {
      if (ctx.pass_type == view::POSTDEPTH)
        {
          ctx.begin_occ_query (*this, 0);
          sector s = orig - ctx.orig;
          gl::draw_bbox (s, s + extent);
          ctx.end_occ_query ();
        }
    }
  else
    {
      int nvis = 0;

      for (iterator i = begin (); i != end (); )
        {
          entity *e = *i++;

          evis &evs = vs.vismap[e];

          if (ctx.pass_type == view::POSTDEPTH)
            {
              if (evs.state == OCCLUDED)
                {
                  ctx.begin_occ_query (*this, e);
                  gl::draw_bbox (e->a - ctx.orig, e->b - ctx.orig);
                  ctx.end_occ_query ();
                }
              else
                nvis++;
            }
          else
            {
          if (!ctx.may_draw (e))
            continue;


              if (evs.state != OCCLUDED)
                {
                  sector center = ((e->a + e->b) >> 1) - ctx.orig;
                  GLfloat z = length (vec3 (center));
                  ctx.pixfact = ctx.perspfact / z;

                  ctx.nz_far  = max (ctx.nz_far,  z + extent);
                  ctx.nz_near = min (ctx.nz_near, z - extent);

                  if (ctx.pass_type == view::DEPTH || evs.last + 0.1 > timer.now)
                    e->draw (ctx);
                  else
                    {
                      evs.last = timer.now;
                      ctx.begin_occ_query (*this, e);
                      e->draw (ctx);
                      ctx.end_occ_query ();
                    }
                }
            }
        }

#if 1
      if (ctx.pass_type == view::POSTDEPTH && nvis == 0 && size ())
        vs.state = OCCLUDED;
#endif
    }
}

void octant::event (occ_query &ev)
{
  oct_visibility &vs = *(oct_visibility *)get_visibility (ev.ctx);
  entity *e = (entity *)ev.id;

  if (e)
    {
      evis &evs = vs.vismap[e];
      evs.state = ev.count ? FULL : OCCLUDED;
    }
  else
    vs.state = ev.count ? FULL : OCCLUDED;
}