--- libgender/oct.C 2004/10/06 02:04:03 1.22 +++ libgender/oct.C 2004/10/28 22:30:30 1.68 @@ -1,93 +1,84 @@ #include #include - using namespace std; -#define GL_GLEXT_PROTOTYPES -#include +#include "opengl.h" #include "oct.h" #include "view.h" #include "entity.h" -vector occ_query_objects; - -static GLuint begin_occ_query () -{ - GLuint id; - - if (occ_query_objects.size ()) - { - id = *(occ_query_objects.end () - 1); - occ_query_objects.pop_back (); - } - else - glGenQueriesARB (1, &id); - - glBeginQueryARB (GL_SAMPLES_PASSED, id); - return id; -} +enum visibility_state { FULL, PARTIAL, SMALL, OCCLUDED }; -#define end_occ_query() glEndQueryARB (GL_SAMPLES_PASSED); +struct evis { + visibility_state state; + double last; // time of last check + evis () : last(0.), state(FULL) { }; +}; -static GLuint occ_query_result (GLuint id) +struct oct_visibility : visibility_base { - GLuint count; + typedef map evismap; + evismap vismap; - glGetQueryObjectuivARB (id, GL_QUERY_RESULT, &count); - occ_query_objects.push_back (id); + visibility_state state; - return count; -} + 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) +: 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 box &bbox) +static bool overlap (const sector &o1, uoffs ea, const sector &a, const sector &b) { - sector a2, b2; - ea /= 2; - a2.x = o1.x + ea; - a2.y = o1.y + ea; - a2.z = o1.z + ea; - - b2.x = (bbox.a.x + bbox.b.x) / 2; - b2.y = (bbox.a.y + bbox.b.y) / 2; - b2.z = (bbox.a.z + bbox.b.z) / 2; + sector center_1 = o1 + ea; + sector size_2 = b - a; + sector center_2 = a + (size_2 >> 1); - return abs (a2.x - b2.x) <= ea + (bbox.b.x - bbox.a.x) - && abs (a2.y - b2.y) <= ea + (bbox.b.y - bbox.a.y) - && abs (a2.z - b2.z) <= ea + (bbox.b.z - bbox.a.z); + return abs (center_1 - center_2) <= ea + size_2; } -void octant::add (entity_base *e) +void octant::add (entity *e) { - box bbox = translate (e->bbox, e->orig, sector (0, 0, 0)); + const sector &a = e->a; + const sector &b = e->b; - uoffs size = max (abs (bbox.b.x - bbox.a.x), - max (abs (bbox.b.y - bbox.a.y), - abs (bbox.b.z - bbox.a.z))); - - if (overlap (orig, extent, bbox)) + if (overlap (orig, extent, a, b)) { - uoffs extent2 = extent / 2; + uoffs extent2 = extent >> 1; + uoffs size = max (abs (b - a)); - if (size > extent2 || !extent2) + if (size >= extent2 >> 1) { push_back (e); e->o.push_back (this); @@ -98,10 +89,14 @@ { sector s = orig; s.offset (i, extent2); - if (overlap (s, extent2, bbox)) + + if (overlap (s, extent2, a, b)) { if (!sub[i]) - sub[i] = new octant (this, s, extent2); + { + sub[i] = new octant (this, s, extent2); + fill++; + } sub[i]->add (e); } @@ -109,74 +104,92 @@ } } -void octant::remove (entity_base *e) +void octant::remove (entity *e) { } -void octant::detect_visibility (view &ctx) +bool octant::detect_visibility (view &ctx) { - visibility_state &vs = ctx.vismap[this]; + GLfloat extent2 = 0.5F * (GLfloat)extent; + sector centeri = orig + (extent >> 1) - ctx.orig; + point centerf = point (centeri) + ((extent & 1) ? 0.5F : 0.F); - if (vs.generation != ctx.generation) - vs.visibility = visibility_state::UNKNOWN; + GLfloat rad = ctx.diagfact * extent2; - const sector &cam = ctx.orig; - if (cam.x >= orig.x && cam.x <= orig.x + extent - && cam.y >= orig.y && cam.y <= orig.y + extent - && cam.z >= orig.z && cam.z <= orig.z + extent) + 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 { - vs.visibility = visibility_state::PARTIAL; - vs.generation = ctx.generation; + 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 } - else + +#if 0 + if (vs.state == OCCLUDED) { - point center ( - orig.x + (soffs)extent / 2 - cam.x, - orig.y + (soffs)extent / 2 - cam.y, - orig.z + (soffs)extent / 2 - cam.z - ); - - GLfloat dia = (0.5 * sqrtf (3))*(GLfloat)extent; - - if (ctx.frustum.t.distance (center) < -dia) return; - if (ctx.frustum.b.distance (center) < -dia) return; - if (ctx.frustum.l.distance (center) < -dia) return; - if (ctx.frustum.r.distance (center) < -dia) return; - if (ctx.frustum.n.distance (center) < -dia) return; - if (ctx.frustum.f.distance (center) < -dia) return; + if (size ()) + ctx.vislist.push_back (this); + //return false; } +#endif - if (size ()) - ctx.vislist.push_back (this); + 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 = ctx.d.x < 0 ? 1 : 0 - | ctx.d.y < 0 ? 2 : 0 - | ctx.d.z < 0 ? 4 : 0; + 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 next[8] - = { 0, 0^1, 1^2, 2^4, 4^3, 3^5, 5^6, 6^7 }; + static unsigned char toggle[8+1] + = { 0, 0^1, 1^2, 2^4, 4^3, 3^5, 5^6, 6^7, 0 }; - for (int i = 0; i < 8; i++) + unsigned char *next = toggle; + do { - si ^= next[i]; + si ^= *next; if (sub[si]) sub[si]->detect_visibility (ctx); } + while (*++next); + + if (size () + && (vs.state == PARTIAL || vs.state == FULL || vs.state == OCCLUDED)) + ctx.vislist.push_back (this); - vs.generation = ctx.generation; + return true; } void octant::display (view &ctx) { #if 0 + sector s = orig - ctx.orig; + glBegin (GL_LINES); - sector s = orig; - s.x -= ctx.orig.x; - s.y -= ctx.orig.y; - s.z -= ctx.orig.z; vec3 clr(0, 0.8, 0); glMaterialfv (GL_FRONT_AND_BACK, GL_DIFFUSE, (const GLfloat*)&clr); @@ -184,7 +197,7 @@ for (int ji = 3; ji--; ) { int j = i | (1 << ji); - if (i != j) + if (i < j) { glVertex3i (s.x + !!(i & 1) * extent, s.y + !!(i & 2) * extent, @@ -196,14 +209,87 @@ } glEnd (); - glDisable(GL_COLOR_MATERIAL); #endif + oct_visibility &vs = *(oct_visibility *)get_visibility (ctx); + + if (vs.state == OCCLUDED) + { + if (ctx.pass == 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]; - GLuint i = begin_occ_query (); - for (iterator i = end (); i != begin (); ) - (*--i)->display (ctx); - end_occ_query (); + if (ctx.pass == 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 == 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 == 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; +}