[libgis] Give extra weight to "edge" triangles when splitting

[Andy Spencer <andys src gnome org>]

commit 907e81475ed6b87e2a2a918aa32836345005074a
Author: Andy Spencer <andy753421 gmail com>
Date:   Mon Nov 1 03:37:53 2010 +0000

    Give extra weight to "edge" triangles when splitting
    
    "Edge" triangles are triangles where one of the edges of the triangle
    makes up an edge off the mesh. For example, the triangle E below is an
    edge triangle due to the top edge.
    
    This helps prevent jagged "edges" on the tops of mountains, etc. It also
    helps round out the edges of the globe  when viewed from far away.
    
      ________________
      \    ______    /
       \  /\ E  /\  /
        \/__\  /__\/
             \/

 src/roam.c |   26 +++++++++++++++++++++++++-
 1 files changed, 25 insertions(+), 1 deletions(-)
---
diff --git a/src/roam.c b/src/roam.c
index 21b1393..0f4995e 100644
--- a/src/roam.c
+++ b/src/roam.c
@@ -319,7 +319,6 @@ static void roam_triangle_sync_neighbors(RoamTriangle *neigh, RoamTriangle *old,
 	if      (neigh->t.l == old) neigh->t.l = new;
 	else if (neigh->t.b == old) neigh->t.b = new;
 	else if (neigh->t.r == old) neigh->t.r = new;
-	else g_assert_not_reached();
 }
 
 static gboolean roam_triangle_visible(RoamTriangle *triangle, RoamSphere *sphere)
@@ -338,6 +337,20 @@ static gboolean roam_triangle_visible(RoamTriangle *triangle, RoamSphere *sphere
 	         l->pz < 1 && m->pz < 1 && r->pz < 1;
 }
 
+static gboolean roam_triangle_backface(RoamTriangle *triangle, RoamSphere *sphere)
+{
+	RoamPoint *l = triangle->p.l;
+	RoamPoint *m = triangle->p.m;
+	RoamPoint *r = triangle->p.r;
+	roam_point_update_projection(l, sphere->view);
+	roam_point_update_projection(m, sphere->view);
+	roam_point_update_projection(r, sphere->view);
+	double size = -( l->px * (m->py - r->py) +
+			 m->px * (r->py - l->py) +
+			 r->px * (l->py - m->py) ) / 2.0;
+	return size < 0;
+}
+
 /**
  * roam_triangle_update_errors:
  * @triangle: the triangle
@@ -375,6 +388,12 @@ void roam_triangle_update_errors(RoamTriangle *triangle, RoamSphere *sphere)
 
 		/* Size < 0 == backface */
 		triangle->error *= size;
+
+		/* Give some preference to "edge" faces */
+		if (roam_triangle_backface(triangle->t.l, sphere) ||
+		    roam_triangle_backface(triangle->t.b, sphere) ||
+		    roam_triangle_backface(triangle->t.r, sphere))
+			triangle->error *= 500;
 	}
 }
 
@@ -554,6 +573,11 @@ void roam_diamond_merge(RoamDiamond *diamond, RoamSphere *sphere)
 	b->kids[0] = b->kids[1] = NULL;
 
 	/* Add original triangles */
+	roam_triangle_sync_neighbors(s->t.l, sl, s);
+	roam_triangle_sync_neighbors(s->t.r, sr, s);
+	roam_triangle_sync_neighbors(b->t.l, bl, b);
+	roam_triangle_sync_neighbors(b->t.r, br, b);
+
 	roam_triangle_add(s, sl->t.b, b, sr->t.b, sphere);
 	roam_triangle_add(b, bl->t.b, s, br->t.b, sphere);