X-Git-Url: http://pileus.org/git/?p=aweather;a=blobdiff_plain;f=src%2Fgis%2Froam.c;h=a95c69705f738ac66f94a39a77878403966fc828;hp=1a7b4f8a17ab350e700e5155151f7b7d2dba5304;hb=5b0d4a3f91c424a06365c1c90c4e1c9bc4767b90;hpb=c7c4b00e13af89cb7ed88de9b7a48115e5fce1b6 diff --git a/src/gis/roam.c b/src/gis/roam.c index 1a7b4f8..a95c697 100644 --- a/src/gis/roam.c +++ b/src/gis/roam.c @@ -26,13 +26,21 @@ /** * TODO: - * - Remove/free unused memory * - Optimize for memory consumption * - Profile for computation speed - * - Implement good error algorithm * - Target polygon count/detail */ +/* Misc */ +RoamView *roam_view_get() +{ + RoamView *view = g_new0(RoamView, 1); + glGetDoublev (GL_MODELVIEW_MATRIX, view->model); + glGetDoublev (GL_PROJECTION_MATRIX, view->proj); + glGetIntegerv(GL_VIEWPORT, view->view); + return view; +} + /* For GPQueue comparators */ static gint tri_cmp(RoamTriangle *a, RoamTriangle *b, gpointer data) { @@ -58,25 +66,50 @@ RoamPoint *roam_point_new(double x, double y, double z) self->z = z; return self; } +RoamPoint *roam_point_dup(RoamPoint *self) +{ + RoamPoint *new = g_memdup(self, sizeof(RoamPoint)); + new->tris = 0; + return new; +} void roam_point_add_triangle(RoamPoint *self, RoamTriangle *triangle) { for (int i = 0; i < 3; i++) { - self->norm[i] *= self->refs; + self->norm[i] *= self->tris; self->norm[i] += triangle->norm[i]; } - self->refs++; + self->tris++; for (int i = 0; i < 3; i++) - self->norm[i] /= self->refs; + self->norm[i] /= self->tris; } void roam_point_remove_triangle(RoamPoint *self, RoamTriangle *triangle) { for (int i = 0; i < 3; i++) { - self->norm[i] *= self->refs; + self->norm[i] *= self->tris; self->norm[i] -= triangle->norm[i]; } - self->refs--; + self->tris--; for (int i = 0; i < 3; i++) - self->norm[i] /= self->refs; + self->norm[i] /= self->tris; +} +void roam_point_update(RoamPoint *self, RoamSphere *sphere, gboolean do_height) +{ + if (!self->cached) { + /* Cache height */ + if (do_height) + sphere->height_func(self, sphere->user_data); + + /* Cache projection */ + gluProject(self->x, self->y, self->z, + sphere->view->model, sphere->view->proj, sphere->view->view, + &self->px, &self->py, &self->pz); + + self->cached = TRUE; + } +} +void roam_point_clear(RoamPoint *self) +{ + self->cached = FALSE; } /**************** @@ -108,8 +141,8 @@ RoamTriangle *roam_triangle_new(RoamPoint *l, RoamPoint *m, RoamPoint *r) self->norm[2] = pa[0] * pb[1] - pa[1] * pb[0]; double total = sqrt(self->norm[0] * self->norm[0] + - self->norm[1] * self->norm[1] + - self->norm[2] * self->norm[2]); + self->norm[1] * self->norm[1] + + self->norm[2] * self->norm[2]); self->norm[0] /= total; self->norm[1] /= total; @@ -131,7 +164,8 @@ void roam_triangle_add(RoamTriangle *self, roam_point_add_triangle(self->p.m, self); roam_point_add_triangle(self->p.r, self); - roam_triangle_update_error(self, sphere, NULL); + if (sphere->view) + roam_triangle_update(self, sphere); self->handle = g_pqueue_push(sphere->triangles, self); } @@ -154,73 +188,71 @@ void roam_triangle_sync_neighbors(RoamTriangle *new, RoamTriangle *old, RoamTria else g_assert_not_reached(); } -gboolean roam_triangle_update_error_visible(RoamPoint *point, double *model, double *proj) +gboolean roam_point_visible(RoamPoint *self, RoamSphere *sphere) { - double x, y, z; - int view[4] = {0,0,1,1}; - if (!gluProject(point->x, point->y, point->z, model, proj, view, &x, &y, &z)) { - g_warning("RoamTriangle: update_error_visible - gluProject failed"); - return TRUE; - } - return !(x < 0 || x > 1 || - y < 0 || y > 1 || - z < 0 || z > 1); + gint *view = sphere->view->view; + return self->px > view[0] && self->px < view[2] && + self->py > view[1] && self->py < view[3] && + self->pz > 0 && self->pz < 1; + //double x, y, z; + //int view[4] = {0,0,1,1}; + //gluProject(self->x, self->y, self->z, + // sphere->view->model, sphere->view->proj, view, + // &x, &y, &z); + //return !(x < 0 || x > 1 || + // y < 0 || y > 1 || + // z < 0 || z > 1); } - -void roam_triangle_update_error(RoamTriangle *self, RoamSphere *sphere, GPQueue *triangles) +gboolean roam_triangle_visible(RoamTriangle *self, RoamSphere *sphere) { - RoamPoint cur = { - (self->p.l->x + self->p.r->x)/2, - (self->p.l->y + self->p.r->y)/2, - (self->p.l->z + self->p.r->z)/2, - }; - RoamPoint good = cur; - roam_sphere_update_point(sphere, &good); - - //g_message("cur = (%+5.2f %+5.2f %+5.2f) good = (%+5.2f %+5.2f %+5.2f)", - // cur[0], cur[1], cur[2], good[0], good[1], good[2]); - - double model[16], proj[16]; - int view[4]; - glGetError(); - glGetDoublev(GL_MODELVIEW_MATRIX, model); - glGetDoublev(GL_PROJECTION_MATRIX, proj); - glGetIntegerv(GL_VIEWPORT, view); - if (glGetError() != GL_NO_ERROR) { - g_warning("RoamTriangle: update_error - glGet failed"); - return; - } + /* Do this with a bounding box */ + return roam_point_visible(self->p.l, sphere) || + roam_point_visible(self->p.m, sphere) || + roam_point_visible(self->p.r, sphere); +} - double scur[3], sgood[3]; - gluProject( cur.x, cur.y, cur.z, model,proj,view, &scur[0], &scur[1], &scur[2]); - gluProject(good.x,good.y,good.z, model,proj,view, &sgood[0],&sgood[1],&sgood[2]); +void roam_triangle_update(RoamTriangle *self, RoamSphere *sphere) +{ + /* Update points */ + roam_point_update(self->p.l, sphere, TRUE); + roam_point_update(self->p.m, sphere, TRUE); + roam_point_update(self->p.r, sphere, TRUE); /* Not exactly correct, could be out on both sides (middle in) */ - if (!roam_triangle_update_error_visible(self->p.l, model, proj) && - !roam_triangle_update_error_visible(self->p.m, model, proj) && - !roam_triangle_update_error_visible(self->p.r, model, proj) && - !roam_triangle_update_error_visible(&good, model, proj)) { + if (!roam_triangle_visible(self, sphere)) { self->error = -1; } else { - self->error = sqrt((scur[0]-sgood[0])*(scur[0]-sgood[0]) + - (scur[1]-sgood[1])*(scur[1]-sgood[1])); - - /* Multiply by size of triangle (todo, do this in screen space) */ - double sa[3], sb[3], sc[3]; - double *a = (double*)self->p.l; - double *b = (double*)self->p.m; - double *c = (double*)self->p.r; - gluProject(a[0],a[1],a[2], model,proj,view, &sa[0],&sa[1],&sa[2]); - gluProject(b[0],b[1],b[2], model,proj,view, &sb[0],&sb[1],&sb[2]); - gluProject(c[0],c[1],c[2], model,proj,view, &sc[0],&sc[1],&sc[2]); - double size = -( sa[0]*(sb[1]-sc[1]) + sb[0]*(sc[1]-sa[1]) + sc[0]*(sa[1]-sb[1]) ) / 2.0; - //g_message("%f * %f = %f", self->error, size, self->error * size); + RoamPoint *l = self->p.l; + RoamPoint *m = self->p.m; + RoamPoint *r = self->p.r; + + /* TODO: share this with the base */ + RoamPoint base = { (l->x + r->x)/2, + (l->y + r->y)/2, + (l->z + r->z)/2 }; + RoamPoint good = base; + roam_point_update(&base, sphere, FALSE); + roam_point_update(&good, sphere, TRUE); + + self->error = sqrt((base.px - good.px) * (base.px - good.px) + + (base.py - good.py) * (base.py - good.py)); + + /* Multiply by size of triangle */ + double size = -( l->px * (m->py - r->py) + + m->px * (r->py - l->py) + + r->px * (l->py - m->py) ) / 2.0; + /* Size < 0 == backface */ self->error *= size; } +} - if (triangles) - g_pqueue_priority_changed(triangles, self->handle); +void roam_triangle_clear(RoamTriangle *self) +{ + /* Clear points */ + roam_point_clear(self->p.l); + roam_point_clear(self->p.m); + roam_point_clear(self->p.r); } void roam_triangle_split(RoamTriangle *self, RoamSphere *sphere) @@ -234,13 +266,12 @@ void roam_triangle_split(RoamTriangle *self, RoamSphere *sphere) RoamTriangle *base = self->t.b; - /* Calculate midpoint */ + /* Duplicate midpoint */ RoamPoint *mid = roam_point_new( - (self->p.l->x + self->p.r->x)/2, - (self->p.l->y + self->p.r->y)/2, - (self->p.l->z + self->p.r->z)/2 - ); - roam_sphere_update_point(sphere, mid); + (self->p.l->x + self->p.r->x)/2, + (self->p.l->y + self->p.r->y)/2, + (self->p.l->z + self->p.r->z)/2); + roam_point_update(mid, sphere, TRUE); /* Add new triangles */ RoamTriangle *sl = roam_triangle_new(self->p.m, mid, self->p.l); // Self Left @@ -265,9 +296,10 @@ void roam_triangle_split(RoamTriangle *self, RoamSphere *sphere) /* Add/Remove diamonds */ RoamDiamond *diamond = roam_diamond_new(self, base, sl, sr, bl, br); + roam_diamond_update(diamond, sphere); roam_diamond_add(diamond, sphere); - roam_diamond_remove(self->diamond, sphere); - roam_diamond_remove(base->diamond, sphere); + roam_diamond_remove(self->parent, sphere); + roam_diamond_remove(base->parent, sphere); } void roam_triangle_draw_normal(RoamTriangle *self) @@ -298,25 +330,25 @@ RoamDiamond *roam_diamond_new( { RoamDiamond *self = g_new0(RoamDiamond, 1); - self->kid[0] = kid0; - self->kid[1] = kid1; - self->kid[2] = kid2; - self->kid[3] = kid3; + self->kids[0] = kid0; + self->kids[1] = kid1; + self->kids[2] = kid2; + self->kids[3] = kid3; - kid0->diamond = self; - kid1->diamond = self; - kid2->diamond = self; - kid3->diamond = self; + kid0->parent = self; + kid1->parent = self; + kid2->parent = self; + kid3->parent = self; - self->parent[0] = parent0; - self->parent[1] = parent1; + self->parents[0] = parent0; + self->parents[1] = parent1; return self; } void roam_diamond_add(RoamDiamond *self, RoamSphere *sphere) { self->active = TRUE; - roam_diamond_update_error(self, sphere, NULL); + self->error = MAX(self->parents[0]->error, self->parents[1]->error); self->handle = g_pqueue_push(sphere->diamonds, self); } void roam_diamond_remove(RoamDiamond *self, RoamSphere *sphere) @@ -333,55 +365,57 @@ void roam_diamond_merge(RoamDiamond *self, RoamSphere *sphere) sphere->polys -= 2; /* TODO: pick the best split */ - RoamTriangle **kid = self->kid; + RoamTriangle **kids = self->kids; /* Create triangles */ - RoamTriangle *tri = self->parent[0]; - RoamTriangle *base = self->parent[1]; + RoamTriangle *tri = self->parents[0]; + RoamTriangle *base = self->parents[1]; - roam_triangle_add(tri, kid[0]->t.b, base, kid[1]->t.b, sphere); - roam_triangle_add(base, kid[2]->t.b, tri, kid[3]->t.b, sphere); + roam_triangle_add(tri, kids[0]->t.b, base, kids[1]->t.b, sphere); + roam_triangle_add(base, kids[2]->t.b, tri, kids[3]->t.b, sphere); - roam_triangle_sync_neighbors(tri, kid[0], kid[0]->t.b); - roam_triangle_sync_neighbors(tri, kid[1], kid[1]->t.b); - roam_triangle_sync_neighbors(base, kid[2], kid[2]->t.b); - roam_triangle_sync_neighbors(base, kid[3], kid[3]->t.b); + roam_triangle_sync_neighbors(tri, kids[0], kids[0]->t.b); + roam_triangle_sync_neighbors(tri, kids[1], kids[1]->t.b); + roam_triangle_sync_neighbors(base, kids[2], kids[2]->t.b); + roam_triangle_sync_neighbors(base, kids[3], kids[3]->t.b); /* Remove triangles */ - roam_triangle_remove(kid[0], sphere); - roam_triangle_remove(kid[1], sphere); - roam_triangle_remove(kid[2], sphere); - roam_triangle_remove(kid[3], sphere); + roam_triangle_remove(kids[0], sphere); + roam_triangle_remove(kids[1], sphere); + roam_triangle_remove(kids[2], sphere); + roam_triangle_remove(kids[3], sphere); /* Add/Remove triangles */ if (tri->t.l->t.l == tri->t.r->t.r && - tri->t.l->t.l != tri && tri->diamond) - roam_diamond_add(tri->diamond, sphere); + tri->t.l->t.l != tri && tri->parent) { + roam_diamond_update(tri->parent, sphere); + roam_diamond_add(tri->parent, sphere); + } if (base->t.l->t.l == base->t.r->t.r && - base->t.l->t.l != base && base->diamond) - roam_diamond_add(base->diamond, sphere); + base->t.l->t.l != base && base->parent) { + roam_diamond_update(base->parent, sphere); + roam_diamond_add(base->parent, sphere); + } /* Remove and free diamond and child triangles */ roam_diamond_remove(self, sphere); - g_assert(self->kid[0]->p.m == self->kid[1]->p.m && - self->kid[1]->p.m == self->kid[2]->p.m && - self->kid[2]->p.m == self->kid[3]->p.m); - g_assert(self->kid[0]->p.m->refs == 0); - g_free(self->kid[0]->p.m); - g_free(self->kid[0]); - g_free(self->kid[1]); - g_free(self->kid[2]); - g_free(self->kid[3]); + g_assert(self->kids[0]->p.m == self->kids[1]->p.m && + self->kids[1]->p.m == self->kids[2]->p.m && + self->kids[2]->p.m == self->kids[3]->p.m); + g_assert(self->kids[0]->p.m->tris == 0); + g_free(self->kids[0]->p.m); + g_free(self->kids[0]); + g_free(self->kids[1]); + g_free(self->kids[2]); + g_free(self->kids[3]); g_free(self); } -void roam_diamond_update_error(RoamDiamond *self, RoamSphere *sphere, GPQueue *diamonds) +void roam_diamond_update(RoamDiamond *self, RoamSphere *sphere) { - roam_triangle_update_error(self->parent[0], sphere, NULL); - roam_triangle_update_error(self->parent[1], sphere, NULL); - self->error = MAX(self->parent[0]->error, self->parent[1]->error); - if (diamonds) - g_pqueue_priority_changed(diamonds, self->handle); + roam_triangle_update(self->parents[0], sphere); + roam_triangle_update(self->parents[1], sphere); + self->error = MAX(self->parents[0]->error, self->parents[1]->error); } /************** @@ -424,8 +458,6 @@ RoamSphere *roam_sphere_new(RoamTriFunc tri_func, RoamHeightFunc height_func, gp }; RoamTriangle *triangles[12]; - for (int i = 0; i < 8; i++) - roam_sphere_update_point(self, vertexes[i]); for (int i = 0; i < 12; i++) triangles[i] = roam_triangle_new( vertexes[_triangles[i][0][0]], @@ -440,29 +472,33 @@ RoamSphere *roam_sphere_new(RoamTriFunc tri_func, RoamHeightFunc height_func, gp return self; } -static void roam_sphere_update_errors_cb(gpointer obj, GPtrArray *ptrs) +void roam_sphere_update(RoamSphere *self) { - g_ptr_array_add(ptrs, obj); -} -void roam_sphere_update_errors(RoamSphere *self) -{ - g_debug("RoamSphere: update_errors - polys=%d", self->polys); - GPtrArray *ptrs = g_ptr_array_new(); - g_pqueue_foreach(self->triangles, (GFunc)roam_sphere_update_errors_cb, ptrs); - for (int i = 0; i < ptrs->len; i++) - roam_triangle_update_error(ptrs->pdata[i], self, self->triangles); - g_ptr_array_free(ptrs, TRUE); + g_debug("RoamSphere: update - polys=%d", self->polys); + if (self->view) g_free(self->view); + self->view = roam_view_get(); + + GPtrArray *tris = g_pqueue_get_array(self->triangles); + GPtrArray *dias = g_pqueue_get_array(self->diamonds); + + for (int i = 0; i < tris->len; i++) { + /* Note: this also updates points */ + RoamTriangle *tri = tris->pdata[i]; + roam_triangle_clear(tri); + roam_triangle_update(tri, self); + g_pqueue_priority_changed(self->triangles, tri->handle); + } - ptrs = g_ptr_array_new(); - g_pqueue_foreach(self->diamonds, (GFunc)roam_sphere_update_errors_cb, ptrs); - for (int i = 0; i < ptrs->len; i++) - roam_diamond_update_error(ptrs->pdata[i], self, self->diamonds); - g_ptr_array_free(ptrs, TRUE); -} -void roam_sphere_update_point(RoamSphere *self, RoamPoint *point) -{ - self->height_func(point, self->user_data); + for (int i = 0; i < dias->len; i++) { + RoamDiamond *dia = dias->pdata[i]; + roam_diamond_update(dia, self); + g_pqueue_priority_changed(self->diamonds, dia->handle); + } + + g_ptr_array_free(tris, TRUE); + g_ptr_array_free(dias, TRUE); } + void roam_sphere_split_one(RoamSphere *self) { RoamTriangle *to_split = g_pqueue_peek(self->triangles); @@ -479,18 +515,25 @@ gint roam_sphere_split_merge(RoamSphere *self) { gint iters = 0, max_iters = 500; gint target = 2000; - while (self->polys < target && iters++ < max_iters) - roam_sphere_split_one(self); - while (self->polys > target && iters++ < max_iters) - roam_sphere_merge_one(self); + + if (!self->view) + return 0; + + if (target - self->polys > 100) + while (self->polys < target && iters++ < max_iters) + roam_sphere_split_one(self); + + if (self->polys - target > 100) + while (self->polys > target && iters++ < max_iters) + roam_sphere_merge_one(self); + while (((RoamTriangle*)g_pqueue_peek(self->triangles))->error > ((RoamDiamond *)g_pqueue_peek(self->diamonds ))->error && iters++ < max_iters) { + roam_sphere_merge_one(self); roam_sphere_split_one(self); - if (((RoamTriangle*)g_pqueue_peek(self->triangles))->error > - ((RoamDiamond *)g_pqueue_peek(self->diamonds ))->error) - roam_sphere_merge_one(self); } + return iters; } void roam_sphere_draw(RoamSphere *self) @@ -503,9 +546,9 @@ void roam_sphere_draw_normals(RoamSphere *self) } static void roam_sphere_free_tri(RoamTriangle *tri) { - if (--tri->p.l->refs == 0) g_free(tri->p.l); - if (--tri->p.m->refs == 0) g_free(tri->p.m); - if (--tri->p.r->refs == 0) g_free(tri->p.r); + if (--tri->p.l->tris == 0) g_free(tri->p.l); + if (--tri->p.m->tris == 0) g_free(tri->p.m); + if (--tri->p.r->tris == 0) g_free(tri->p.r); g_free(tri); } void roam_sphere_free(RoamSphere *self)