--- libgender/oct.C 2004/10/03 20:14:33 1.5 +++ libgender/oct.C 2004/10/06 00:55:37 1.19 @@ -1,27 +1,53 @@ #include +#include + +using namespace std; + +#define GL_GLEXT_PROTOTYPES +#include + #include "oct.h" +#include "view.h" #include "entity.h" -octant world(0, 0); +vector occ_query_objects; -octant::octant (octant *parent, int subindex) -: parent(parent) +static GLuint begin_occ_query () { - for (fill = 8; fill--; ) - sub[fill] = 0; + GLuint id; - if (parent) + if (occ_query_objects.size ()) { - extent = (parent->extent + 1) >> 1; - orig = parent->orig; - orig.offset (subindex, extent); + id = *(occ_query_objects.end () - 1); + occ_query_objects.pop_back (); } else - { - extent = MAXEXTENT; - orig.x = orig.y = orig.z = SOFFS_MIN; - } + glGenQueries (1, &id); + + glBeginQuery (GL_SAMPLES_PASSED, id); + return id; +} + +#define end_occ_query() glEndQuery (GL_SAMPLES_PASSED); + +static GLuint occ_query_result (GLuint id) +{ + GLuint count; + + glGetQueryObjectuiv (id, GL_QUERY_RESULT, &count); + occ_query_objects.push_back (id); + + return count; +} + +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) +{ + for (fill = 8; fill--; ) + sub[fill] = 0; } octant::~octant () @@ -30,9 +56,9 @@ delete sub[fill]; } -static bool overlap (const sector &o1, uoffs ea, const sector &o2, const box &bbox) +static bool overlap (const sector &o1, uoffs ea, const box &bbox) { - sector a2; + sector a2, b2; ea /= 2; @@ -40,58 +66,142 @@ a2.y = o1.y + ea; a2.z = o1.z + ea; - sector b2; - sector eb; - - b2.x = o2.x + (soffs)bbox.a.x; - b2.y = o2.y + (soffs)bbox.a.y; - b2.z = o2.z + (soffs)bbox.a.z; + 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; - eb.x = (soffs)(bbox.b.x - bbox.a.x) / 2; - eb.y = (soffs)(bbox.b.y - bbox.a.y) / 2; - eb.z = (soffs)(bbox.b.z - bbox.a.z) / 2; - - b2.x += eb.x; - b2.y += eb.y; - b2.z += eb.z; - - return abs (a2.x - b2.x) <= ea + eb.x - && abs (a2.y - b2.y) <= ea + eb.y - && abs (a2.z - b2.z) <= ea + eb.z; + 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); } -void octant::add (const sector &sec, entity_base *e) +void octant::add (entity_base *e) { - printf ("OCTANT %d,%d,%d+%d\n", orig.x, orig.y, orig.z, extent); + box bbox = translate (e->bbox, e->orig, sector (0, 0, 0)); - if (overlap (orig, extent, sec, e->bbox)) - { - printf ("overlap, add\n"); - push_back (e); - e->o.push_back (this); + 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 0 + if (overlap (orig, extent, bbox)) + { uoffs extent2 = extent / 2; - for (int si = 8; i--; ) + + if (size > extent2 || !extent2) { - sector sub = orig; - sub.offset (si, extent2); - if (overlap (sub, extent2, sec, e->bbox)) + 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, bbox)) { + if (!sub[i]) + sub[i] = new octant (this, s, extent2); + + sub[i]->add (e); } -#endif + } } - else - printf ("no overlap\n"); } void octant::remove (entity_base *e) { } -void octant::draw (draw_context &ctx) +void octant::detect_visibility (view &ctx) { - for (iterator i = end (); i-- != begin (); ) - (*i)->display (ctx); + visibility_state &vs = ctx.vismap[this]; + + if (vs.generation != ctx.generation) + vs.visibility = visibility_state::UNKNOWN; + + 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) + { + vs.visibility = visibility_state::PARTIAL; + vs.generation = ctx.generation; + } + else + { + 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); + + // 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; + + // 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 }; + + for (int i = 0; i < 8; i++) + { + si ^= next[i]; + + if (sub[si]) + sub[si]->detect_visibility (ctx); + } + + vs.generation = ctx.generation; } +void octant::display (view &ctx) +{ +#if 0 + 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); + + 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 (); + glDisable(GL_COLOR_MATERIAL); +#endif + + for (iterator i = end (); i != begin (); ) + (*--i)->display (ctx); +} + + +