--- libgender/oct.C 2004/10/02 15:54:43 1.1 +++ libgender/oct.C 2004/11/07 02:28:18 1.71 @@ -1,14 +1,280 @@ #include +#include +using namespace std; + +#include "opengl.h" + #include "oct.h" +#include "view.h" +#include "entity.h" + +enum visibility_state { FULL, PARTIAL, SMALL, OCCLUDED }; + +struct evis { + visibility_state state; + double last; // time of last check + evis () : last(0.), state(FULL) { }; +}; + +struct oct_visibility : visibility_base +{ + typedef map evismap; + evismap vismap; + + visibility_state state; + + oct_visibility (octant &oct) + : state(FULL) + { + } +}; + +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; +} + +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 (int i = 8; i--; ) - delete sub[i]; + 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 + + // 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 = 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 = 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) + { + 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.3 > 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; } + +