/**
* 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)
{
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;
}
/****************
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;
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);
}
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)
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
/* 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)
{
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)
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);
}
/**************
};
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]],
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);
{
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)
}
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)