--- libgender/oct.C 2004/10/18 12:24:29 1.60 +++ libgender/oct.C 2005/01/06 03:09:24 1.87 @@ -9,28 +9,51 @@ #include "view.h" #include "entity.h" -enum visibility_state { FULL, PARTIAL, SMALL, OCCLUDED }; +enum visibility_state { FULL, PARTIAL, OCCLUDED }; struct evis { + entity *e; visibility_state state; double last; // time of last check - evis () : last(0.), state(FULL) { }; + + void clear () + { + last = 0.; + state = FULL; + } + + evis () + { + clear (); + } }; struct oct_visibility : visibility_base { - typedef map evismap; - evismap vismap; + 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 (SOFFS_MIN, SOFFS_MIN, SOFFS_MIN), MAXEXTENT); +octant world(0, sector (0, 0, 0), MAXEXTENT); octant::octant (octant *parent, const sector &orig, uoffs extent) : parent(parent) @@ -49,22 +72,30 @@ void octant::clear_visibility (visibility_base *vs) { ((oct_visibility *)vs)->vismap.clear (); + ((oct_visibility *)vs)->state = FULL; } + octant::~octant () { for (fill = 8; fill--; ) delete sub[fill]; } -static bool overlap (const sector &o1, uoffs ea, const sector &a, const sector &b) +static bool overlap (const sector &orig, uoffs extent, const sector &a, const sector &b) { - ea /= 2; + sector size = (b - a + 1) >> 1; + sector center = a + size; - sector center_1 = o1 + ea; - sector size_2 = b - a; - sector center_2 = a + (size_2 >> 1); + return abs (orig - center) <= extent + size; +} - return abs (center_1 - center_2) <= ea + size_2; +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) @@ -72,22 +103,23 @@ 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)); + uoffs size = max (abs (b - a)); - if (size >= extent2 >> 1) + if (size >= extent >> 4) + { + if (overlap (orig, extent, a, b)) { push_back (e); e->o.push_back (this); - return; } + } + else + { + uoffs extent2 = extent >> 1; for (int i = 8; i--; ) { - sector s = orig; - s.offset (i, extent2); + sector s = offset (orig, i, extent2); if (overlap (s, extent2, a, b)) { @@ -107,28 +139,34 @@ { } -bool octant::depth_pass (view &ctx) +bool octant::detect_visibility (view &ctx) //, bool fully_visible) { - oct_visibility &vs = *(oct_visibility *)get_visibility (ctx); + ctx.stat1++;//D - GLfloat extent2 = 0.5F * (GLfloat)extent; - sector centeri = orig + (extent >> 1) - ctx.orig; - point centerf = point (centeri) + ((extent & 1) ? 0.5F : 0.F); + sector centeri = orig - ctx.orig; + point centerf = point (centeri); - GLfloat rad = ctx.diagfact * extent2; + GLfloat rad = ctx.diagfact * extent; if (!overlap (ctx.frustum.c, sphere (centerf, rad))) return false; - if (orig <= ctx.orig && ctx.orig <= orig + extent) - vs.state = PARTIAL; + oct_visibility &vs = *(oct_visibility *)get_visibility (ctx); + + //vs.state = FULL;//D + +#if 0 + if (max (abs (centeri)) <= extent) + ; 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; +#endif + + //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); @@ -136,28 +174,39 @@ if (fd < -(ctx.c_far - ctx.z_far) -rad * 3.F) return false; #endif - } - if (vs.state == OCCLUDED) + // 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 return false; - 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 == OCCLUDED) + { +#if 0 + if (extent < ctx.z_far) + { +#endif + ctx.postdepthlist.push_back (this); + return false; +#if 0 + } + else + vs.state == PARTIAL; +#endif + } + + bool visible = size () && 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; - //printf ("si %d C %Ld,%Ld,%Ld\n", si, centeri.x, centeri.y, centeri.z); - // 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 }; @@ -168,114 +217,183 @@ si ^= *next; if (sub[si]) - sub[si]->depth_pass (ctx); + visible = visible | sub[si]->detect_visibility (ctx); } while (*++next); - if (size () - && (vs.state == PARTIAL || vs.state == FULL)) + if (visible) { - display (ctx); - ctx.vislist.push_back (this); + if (size ()) + ctx.vislist.push_back (this); + + ctx.postdepthlist.push_back (this); + } + else + { + //vs.state = OCCLUDED; + ctx.postdepthlist.push_back (this); } - return true; + return visible; } -void octant::display (view &ctx) +void octant::draw_depth (view &ctx) { -#if 0 - sector s = orig - ctx.orig; + oct_visibility &vs = *(oct_visibility *)get_visibility (ctx); - glBegin (GL_LINES); - vec3 clr(0, 0.8, 0); - glMaterialfv (GL_FRONT_AND_BACK, GL_DIFFUSE, (const GLfloat*)&clr); + vs.vismap.resize (size ()); - for (int i = 8; 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 - oct_visibility &vs = *(oct_visibility *)get_visibility (ctx); + if (vs.state == PARTIAL || vs.state == OCCLUDED) + return; - if (vs.state == OCCLUDED) + for (int i = 0; i < size (); ++i) { - abort (); - if (ctx.pass == view::POSTDEPTH) + entity *e = (*this)[i]; + const evis &evs = vs.get_visibility (i, e); + + if (evs.state != OCCLUDED) { - ctx.begin_occ_query (*this, 0); - sector s = orig - ctx.orig; - gl::draw_bbox (vb_bbox, s, s + extent); - ctx.end_occ_query (); + 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.state == PARTIAL || vs.state == OCCLUDED) + { + ctx.begin_occ_query (*this, 0); + sector s = orig - ctx.orig; + gl::draw_bbox (s - extent, s + extent); + ctx.end_occ_query (); + } else { - for (iterator i = begin (); i != end (); ) - { - entity *e = *i++; - - if (!ctx.may_draw (e)) - continue; + int nvis = 0; - evis &evs = vs.vismap[e]; + for (int i = 0; i < size (); ++i) + { + entity *e = (*this)[i]; + const evis &evs = vs.get_visibility (i, e); - if (ctx.pass == view::POSTDEPTH) + if (evs.state == OCCLUDED) { - if (evs.state == OCCLUDED) - { - ctx.begin_occ_query (*this, e); - gl::draw_bbox (vb_bbox, e->a - ctx.orig, e->b - ctx.orig); - ctx.end_occ_query (); - } + 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 - { - 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 == view::DEPTH || evs.last + 1. > timer.now) - e->draw (ctx); - else - { - evs.last = timer.now; - ctx.begin_occ_query (*this, e); - e->draw (ctx); - ctx.end_occ_query (); - } - } - } + nvis++; } + +#if 0 + if (nvis == 0 && size ()) + vs.state = PARTIAL; +#endif } } -#if 0 -void octant::draw_bbox (view &ctx) +void octant::draw_lighted (view &ctx) { - sector s = orig - ctx.orig; + oct_visibility &vs = *(oct_visibility *)get_visibility (ctx); - gl::draw_bbox (ctx, s, s + extent); -} +#if 0 + if (vs.state == PARTIAL || vs.state == OCCLUDED) + { + sector s = orig - ctx.orig; + gl::draw_bbox (s - extent, s + extent); + printf ("DLP %p\n", this);//D + } +#endif + + if (vs.state == PARTIAL || vs.state == OCCLUDED) + return; + +#if 0 + { + static vertex_buffer vb; + static index_buffer ib; + + sector s = orig - ctx.orig; + sector a = s - extent, b = s + extent; + + vertex_v3f vd[] = { + point (a.x, a.y, a.z), + point (b.x, a.y, a.z), + point (a.x, b.y, a.z), + point (b.x, b.y, a.z), + point (a.x, a.y, b.z), + point (b.x, a.y, b.z), + point (a.x, b.y, b.z), + point (b.x, b.y, b.z), + }; + + if (!ib) + { + static GLushort verts[4*6] = { + 0, 4, 6, 2, // -x + 1, 3, 7, 5, // +x + 0, 1, 5, 4, // -y + 7, 3, 2, 6, // +y + 0, 2, 3, 1, // -z + 4, 5, 7, 6, // +z + }; + + ib.set (verts, 4*6, GL_STATIC_DRAW_ARB); + } + + vb.set (vd, 8, GL_STREAM_DRAW_ARB); + vb.bind (); + for (int i = 0; i < 6; i++) + ib.draw (GL_LINE_LOOP, i*4, 4); + + } #endif + 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 + 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::event (occ_query &ev) { oct_visibility &vs = *(oct_visibility *)get_visibility (ev.ctx); @@ -283,22 +401,17 @@ if (e) { - evis &evs = vs.vismap[e]; - evs.state = ev.count ? FULL : OCCLUDED; + 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; - } - -#if 0 - visibility_state &vs = ev.v.vismap[this]; - - vs.last = timer.now; - vs.state = ev.r <= 0 - ? visibility_state::OCCLUDED - : visibility_state::FULL; -#endif + vs.state = ev.count ? (vs.state == PARTIAL ? PARTIAL : FULL) : OCCLUDED; }