r5704 - developers/werner/cncmap/zmap

[werner at docs.openmoko.org]

Author: werner
Date: 2009-10-23 01:27:55 +0200 (Fri, 23 Oct 2009)
New Revision: 5704

Modified:
   developers/werner/cncmap/zmap/zline.c
   developers/werner/cncmap/zmap/zmap.c
Log:
More algorithm fixes. We should now be good, except for some corner cases.

- zmap/zmap.c (zmap_point): treat this as a linear equation with two unknowns.
  The previous algorithm only worked if the points formed a triangle with a
  right angle and the first point was at that angle.
- zmap/zline.c (zline): we still have to consider "old" points, as they may 
  replace different points as we crawl the line



Modified: developers/werner/cncmap/zmap/zline.c
===================================================================
--- developers/werner/cncmap/zmap/zline.c	2009-10-22 21:23:05 UTC (rev 5703)
+++ developers/werner/cncmap/zmap/zline.c	2009-10-22 23:27:55 UTC (rev 5704)
@@ -123,7 +123,6 @@
     void (*point)(void *user, double x, double y, double z), void *user)
 {
 	double t;
-	int n;
 	double best_t, tmp_t;
 	int best_next, best_old;
 	int i, tmp_i;
@@ -135,13 +134,13 @@
 	point(user, xa, ya, zmap_point(map[0], map[1], map[2], xa, ya));
 
 	t = 0;
-	n = map_n;
-	while (n > 3) {
+	while (1) {
 		best_t = 1;
 		best_next = best_old = -1;
 		for (i = 0; i != 3; i++) {
 			tmp_t = t;
-			tmp_i = next_closest(xa, ya, xb, yb, i, 3, n, &tmp_t);
+			tmp_i = next_closest(xa, ya, xb, yb, i, 3, map_n,
+			    &tmp_t);
 			DEBUG("%d: i = %d t = %g (@%g)\n", i, tmp_i, tmp_t, t);
 			if (tmp_t < best_t) {
 				best_t = tmp_t;
@@ -151,11 +150,8 @@
 		}
 		if (best_next == -1)
 			break;
-		DEBUG("swap %d vs. %d of %d\n", best_old, best_next, n);
-		swap(best_old, n-1);
-		if (best_next != n-1)
-			swap(best_old, best_next);
-		n--;
+		DEBUG("swap %d vs. %d\n", best_old, best_next);
+		swap(best_old, best_next);
 		t = best_t;
 		x = xa+(xb-xa)*t;
 		y = ya+(yb-ya)*t;

Modified: developers/werner/cncmap/zmap/zmap.c
===================================================================
--- developers/werner/cncmap/zmap/zmap.c	2009-10-22 21:23:05 UTC (rev 5703)
+++ developers/werner/cncmap/zmap/zmap.c	2009-10-22 23:27:55 UTC (rev 5704)
@@ -120,9 +120,9 @@
 double zmap_point(struct xyz a, struct xyz b, struct xyz c, double x, double y)
 {
 	double xp, yp;
-	double xu, yu, zu, u;
-	double xv, yv, zv, v;
-	double s, t;
+	double xu, yu, zu;
+	double xv, yv, zv;
+	double det, s, t;
 
 	DEBUG("point (%g, %g) -> (%g, %g) (%g, %g) (%g, %g)\n",
 	    x, y, a.x, a.y, b.x, b.y, c.x, c.y);
@@ -132,15 +132,14 @@
 	xu = b.x-a.x;
 	yu = b.y-a.y;
 	zu = b.z-a.z;
-	u = hypot(xu, yu);
 
 	xv = c.x-a.x;
 	yv = c.y-a.y;
 	zv = c.z-a.z;
-	v = hypot(xv, yv);
 
-	s = (xp*xu+yp*yu)/u/u;
-	t = (xp*xv+yp*yv)/v/v;
+	det = xu*yv-yu*xv;
+	s = (xp*yv-yp*xv)/det;
+	t = (xu*yp-yu*xp)/det;
 
 	return a.z+s*zu+t*zv;
 }