#include <cstdlib>

#include <vector>

using namespace std;

#include "opengl.h"

#include "oct.h"
#include "view.h"
#include "entity.h"
#include "material.h" //DEBUG

struct oct_visibility : visibility_base
{
  bool subvis, evis;
  int occ_res;

  void clear ()
  {
    occ_res = -1;
    evis = true;
    subvis = true;
  }

  oct_visibility (octant &oct)
  {
    clear ();
  }
};

octant world(0, sector (0, 0, 0), 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)->clear ();
}

octant::~octant ()
{
  for (fill = 8; fill--; )
    delete sub[fill];
}

static bool overlap (const sector &orig, uoffs extent, const sector &a, const sector &b)
{
  sector size   = (b - a + 1) >> 1;
  sector center = a + size;

  return abs (orig - center) <= extent + size;
}

static sector offset (const sector &s, int subindex, uoffs extent)
{
  return sector (
    s.x + (subindex & 1 ? extent : -extent),
    s.y + (subindex & 2 ? extent : -extent),
    s.z + (subindex & 4 ? extent : -extent)
  );
}

void octant::add (entity *e)
{
  const sector &a = e->a;
  const sector &b = e->b;

  uoffs size = max (abs (b - a));

  if (size >= extent >> 4)
    {
      if (overlap (orig, extent, a, b))
        {
          push_back (e);
          e->o.push_back (this);
        }
    }
  else
    {
      uoffs extent2 = extent >> 1;

      for (int i = 8; i--; )
        {
          sector s = offset (orig, 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) //, bool fully_visible)
{
  sector centeri = orig - ctx.orig;
  point centerf = point (centeri);

  GLfloat rad = ctx.diagfact * extent;

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

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

  if (max (centeri) < extent)
    {
      vs.evis = true;
      vs.occ_res = -1;
    }
  else if (distance (ctx.frustum.t, centerf) < -rad
           || distance (ctx.frustum.b, centerf) < -rad
           || distance (ctx.frustum.l, centerf) < -rad
           || distance (ctx.frustum.r, centerf) < -rad
           || distance (ctx.frustum.n, centerf) < -rad)
    {
      vs.clear ();
      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

  // very important, optimize?
  GLfloat z = length (ctx.p - centerf) + rad;
  if (z < 0.F || ctx.perspfact * extent / z < 10.) // very crude "too small to see" check
    {
      vs.clear ();//D
      return false;
    }

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

  if (vs.occ_res > 0)
    ;//vs.occ_res = -1;
  else if (!(vs.subvis || vs.evis))
    {
      ctx.postdepthlist.push_back (this);
      return false;
    }
  else if (!vs.occ_res)
    {
      ctx.postdepthlist.push_back (this);
      return false;
    }
 
  bool subvis = 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 };

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

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

  vs.subvis = subvis;

  if (subvis)
    {
      if (size ())
        {
          ctx.postdepthlist.push_back (this);
          ctx.vislist.push_back (this);
        }

      return true;
    }
  else
    {
      ctx.postdepthlist.push_back (this);
      ctx.vislist.push_back (this);

      return vs.evis || vs.occ_res > 0;
    }
}

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

  if (!(vs.subvis || vs.evis))
    return;

  for (int i = 0; i < size (); ++i)
    {
      entity *e = (*this)[i];

      entity_visibility &evis = *(entity_visibility *)e->get_visibility (ctx);

      if (evis.occ_res)
        {
          if (!ctx.may_draw (e))
            continue;

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

          e->draw (ctx);
        }
    }
}

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

  if (!vs.evis)
    {
      ctx.begin_occ_query (vs.occ_res);
      sector s = orig - ctx.orig;
      gl::draw_bbox (s - extent, s + extent);
      ctx.end_occ_query ();
    }
  else
    {
      vs.evis = false;

      for (int i = 0; i < size (); ++i)
        {
          entity *e = (*this)[i];
          entity_visibility &evis = *(entity_visibility *)e->get_visibility (ctx);

          if (evis.occ_res)
            vs.evis = true;
          else
            {
              if (!ctx.may_draw (e))
                continue;

              ctx.stat1++;
              ctx.begin_occ_query (evis.occ_res);
              gl::draw_bbox (e->a - ctx.orig, e->b - ctx.orig);
              ctx.end_occ_query ();
            }
        }
    }
}

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

#if 0
  if (vs.state == FULL || vs.state == OCCLUDED)
   {
    sector s = orig - ctx.orig;
    debugmat->enable (ctx);
  if (max (s) >= extent)
    gl::draw_bbox (s - extent, s + extent);
    debugmat->disable (ctx);
    //printf ("DLP %ld %ld %ld (%ld)\n", orig.x, orig.y, orig.z, extent);//D
   }
#endif

  for (int i = 0; i < size (); ++i)
    {
      entity *e = (*this)[i];
      entity_visibility &evis = *(entity_visibility *)e->get_visibility (ctx);

      if (evis.occ_res)
        {
          if (!ctx.may_draw (e))
            continue;

          sector center = ((e->a + e->b) >> 1) - ctx.orig;
          GLfloat z = length (vec3 (center));
          ctx.pixfact = ctx.perspfact / z;

          if (!ctx.first_lighted
              || evis.next > timer.now)
            e->draw (ctx);
          else
            {
              evis.next = timer.now + 0.2;
              ctx.begin_occ_query (evis.occ_res);
              e->draw (ctx);
              ctx.end_occ_query ();
            }
        }
    }
}