--- libgender/oct.C 2004/10/03 03:51:51 1.3 +++ libgender/oct.C 2004/11/23 18:32:39 1.79 @@ -1,59 +1,346 @@ #include +#include +using namespace std; + +#include "opengl.h" + #include "oct.h" +#include "view.h" #include "entity.h" -octant world(0, 0); +enum visibility_state { FULL, PARTIAL, SMALL, OCCLUDED, SUBTREE_OCCLUDED }; + +struct evis { + entity *e; + visibility_state state; + double last; // time of last check + + void clear () + { + last = 0.; + state = FULL; + } + + evis () + { + clear (); + } +}; + +struct oct_visibility : visibility_base +{ + vector vismap; + + visibility_state state; + + evis &get_visibility (int i, entity *e) + { + evis &evs = vismap [i]; + + if (evs.e != e) + { + evs.clear (); + evs.e = e; + } + + return evs; + } + + oct_visibility (octant &oct) + : state(FULL) + { + } +}; + +octant world(0, sector (0, 0, 0), MAXEXTENT); -octant::octant (octant *parent, int subindex) +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); +} - if (parent) +void octant::clear_visibility (visibility_base *vs) +{ + ((oct_visibility *)vs)->vismap.clear (); + ((oct_visibility *)vs)->state = FULL; + ((oct_visibility *)vs)->state = OCCLUDED;//D +} + +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; + + if (overlap (orig, extent, a, b)) { - extent = (parent->extent + 1) >> 1; - orig = parent->orig; - orig.offset (subindex, extent); + uoffs extent2 = extent >> 1; + uoffs size = max (abs (b - a)); + + if (size >= extent2) + { + push_back (e); + e->o.push_back (this); + return; + } + + 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) +{ + ctx.stat1++;//D + + 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 (abs (centeri)) <= extent) + vs.state = PARTIAL; else { - extent = MAXEXTENT; - orig.x = orig.y = orig.z = SOFFS_MIN; + 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 + } + + // very important, optimize? + 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; + +#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; + } + + bool visible = size () && (vs.state == PARTIAL || vs.state == FULL); + + // 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]) + visible = visible | sub[si]->detect_visibility (ctx); } + while (*++next); + + if (visible) + { + if (size ()) + ctx.vislist.push_back (this); + } + else + vs.state = SUBTREE_OCCLUDED; + + return visible; } -octant::~octant () +void octant::draw_depth (view &ctx) { - for (fill = 8; fill--; ) - delete sub[fill]; + oct_visibility &vs = *(oct_visibility *)get_visibility (ctx); + + vs.vismap.resize (size ()); + + if (vs.state == OCCLUDED || vs.state == SUBTREE_OCCLUDED) + return; + + for (int i = 0; i < size (); ++i) + { + entity *e = (*this)[i]; + const evis &evs = vs.get_visibility (i, e); + + if (evs.state != OCCLUDED) + { + 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::add (const sector &sec, entity_base *e) +void octant::draw_postdepth (view &ctx) { - sector orig2; - sector extent2; + oct_visibility &vs = *(oct_visibility *)get_visibility (ctx); - orig2.x = sec.x + (soffs)e->bbox.a.x; - orig2.y = sec.y + (soffs)e->bbox.a.y; - orig2.z = sec.z + (soffs)e->bbox.a.z; + if (vs.state == OCCLUDED || vs.state == SUBTREE_OCCLUDED) + { + ctx.begin_occ_query (*this, 0); + sector s = orig - ctx.orig; + gl::draw_bbox (s - extent, s + extent); + ctx.end_occ_query (); + } + else + { + int nvis = 0; - extent2.x = sec.x + (soffs)e->bbox.b.x - orig2.x; - extent2.x = sec.y + (soffs)e->bbox.b.y - orig2.y; - extent2.x = sec.z + (soffs)e->bbox.b.z - orig2.z; + for (int i = 0; i < size (); ++i) + { + entity *e = (*this)[i]; + const evis &evs = vs.get_visibility (i, e); + + if (evs.state == OCCLUDED) + { + if (!ctx.may_draw (e)) + continue; + + ctx.begin_occ_query (*this, e); + gl::draw_bbox (e->a - ctx.orig, e->b - ctx.orig); + ctx.end_occ_query (); + } + else + nvis++; + } - push_back (e); - e->o.push_back (this); + if (nvis == 0 && size ()) + vs.state = OCCLUDED; + } } -void octant::remove (entity_base *e) +void octant::draw_lighted (view &ctx) { + oct_visibility &vs = *(oct_visibility *)get_visibility (ctx); + + if (vs.state == OCCLUDED || vs.state == SUBTREE_OCCLUDED) + return; + + for (int i = 0; i < size (); ++i) + { + entity *e = (*this)[i]; + evis &evs = vs.get_visibility (i, e); + + if (evs.state != OCCLUDED) + { + 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.pass->type != LIGHTED + || !ctx.first_lighted + || 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 (); + } + } + } } -void octant::draw (const draw_context &ctx) +void octant::event (occ_query &ev) { - for (iterator i = end (); i-- != begin (); ) - (*i)->draw (ctx); + oct_visibility &vs = *(oct_visibility *)get_visibility (ev.ctx); + entity *e = (entity *)ev.id; + + if (e) + { + for (vector::iterator i = vs.vismap.begin (); + i != vs.vismap.end (); + ++i) + if (i->e == e) + { + i->state = ev.count ? FULL : OCCLUDED; + return; + } + } + else + vs.state = ev.count ? FULL : OCCLUDED; } +