[Commit] tess ChangeLog, 1.16, 1.17 bentley.5c, 1.14, 1.15 kbentley.5c, 1.2, 1.3

[Carl Worth]

Committed by: cworth

Update of /local/src/CVS/tess
In directory home.keithp.com:/tmp/cvs-serv3743

Modified Files:
	ChangeLog bentley.5c kbentley.5c 
Log Message:

        * bentley.5c (intersect_lines): Add some explanatory comments
        about necessary bit depths.
        (edge_greater): Start fixing currently unused integer version of
        edge_greater.


Index: ChangeLog
===================================================================
RCS file: /local/src/CVS/tess/ChangeLog,v
retrieving revision 1.16
retrieving revision 1.17
diff -u -d -r1.16 -r1.17
--- ChangeLog	11 Jul 2004 07:18:43 -0000	1.16
+++ ChangeLog	24 Jul 2004 06:26:16 -0000	1.17
@@ -1,3 +1,10 @@
+2004-07-24  Carl Worth  <cworth at isi.edu>
+
+	* bentley.5c (intersect_lines): Add some explanatory comments
+	about necessary bit depths.
+	(edge_greater): Start fixing currently unused integer version of
+	edge_greater.
+
 2004-07-11  Keith Packard  <keithp at keithp.com>
 
 	* kbentley.5c:

Index: bentley.5c
===================================================================
RCS file: /local/src/CVS/tess/bentley.5c,v
retrieving revision 1.14
retrieving revision 1.15
diff -u -d -r1.14 -r1.15
--- bentley.5c	9 Jul 2004 19:19:15 -0000	1.14
+++ bentley.5c	24 Jul 2004 06:26:16 -0000	1.15
@@ -153,7 +153,7 @@
 
     /* At this stage we are looking at two events of the same type at
      * the same point. The final sort key is a slope comparison. We
-     * need a difference sens for start and stop events based on the
+     * need a difference sense for start and stop events based on the
      * shortening rule.
      *
      * NOTE: Fortunately, we get to ignore errors in the relative
@@ -189,27 +189,34 @@
 	return a * d - b * c;
     }
 
-    int dx1 = a.top.x - a.bottom.x;
-    int dy1 = a.top.y - a.bottom.y;
+    int dx1 = a.top.x - a.bottom.x; /* 32 */
+    int dy1 = a.top.y - a.bottom.y; /* 32 */
 	
-    int dx2 = b.top.x - b.bottom.x;
-    int dy2 = b.top.y - b.bottom.y;
+    int dx2 = b.top.x - b.bottom.x; /* 32 */
+    int dy2 = b.top.y - b.bottom.y; /* 32 */
 
-    int den_det = det (dx1, dy1, dx2, dy2);
+    int den_det = det (dx1, dy1, dx2, dy2); /* 64 */
 
     if (den_det == 0)
 	raise parallel ();
 
     int a_det = det (a.top.x, a.top.y,
-		     a.bottom.x, a.bottom.y);
+		     a.bottom.x, a.bottom.y); /* 64 */
     int b_det = det (b.top.x, b.top.y,
-		     b.bottom.x, b.bottom.y);
-	    
+		     b.bottom.x, b.bottom.y); /* 64 */
+
+    /* We could get a result here with up to 96 bits, but anything
+     * outside the range of 32 bits is infinity so we can throw it
+     * away. So we have a 32-bit result. But then, we also need 2 more
+     * bits of precision so that we can compare correctly with
+     * tolerance square edges lying half-way between grid
+     * positions. This involves being careful with the remainder from
+     * the division. Keith will help me get that part right. */
     return (RationalPoint) {
 	x = det (a_det, dx1,
-		 b_det, dx2) / den_det,
+		 b_det, dx2) / den_det, /* 96 / 64 => 96 */
 	y = det (a_det, dy1,
-		 b_det, dy2) / den_det
+		 b_det, dy2) / den_det /* 96 / 64 => 96 */
     };
 }
 
@@ -507,8 +514,15 @@
 	int ady = a.elt->bottom.y - a.elt->top.y;
 	int bdy = b.elt->bottom.y - b.elt->top.y;
 
-	int ax = bdy*(adx*(current_y - a.elt->top.y) + a.elt->top.x * ady);
-	int bx = ady*(bdx*(current_y - b.elt->top.y) + b.elt->top.x * bdy);
+	if (ady == 0)
+	    ax = a.elt->top.x;
+	else
+	    ax = a.elt->top.x + (current_y - a.elt->top.y) * adx / ady;
+
+	if (bdy == 0)
+	    bx = b.elt->top.x;
+	else
+	    bx = b.elt->top.x + (current_y - b.elt->top.y) * bdx / bdy;
 
 	return ax > bx;
     }
@@ -645,7 +659,7 @@
 
     int intersections;
     do {
-	iterations++;
+	printf ("%d ", iterations++);
 	old_edges = edges;
 	edges = bentley_ottman(old_edges, &intersections);
     } while (intersections > 0);
@@ -807,8 +821,12 @@
     run_test (tests[i].name, tests[i].edges);
 
 num_random = 30;
+if (dim(argv)>1)
+    num_random = string_to_integer (argv[1]);
 
 PRNG::srandom (0);
+
+printf ("Initializing %d random edges\n", num_random);
 Edge[...] random_edges = {};
 for (int i=0; i < num_random; i++)
 {

Index: kbentley.5c
===================================================================
RCS file: /local/src/CVS/tess/kbentley.5c,v
retrieving revision 1.2
retrieving revision 1.3
diff -u -d -r1.2 -r1.3
--- kbentley.5c	11 Jul 2004 07:18:43 -0000	1.2
+++ kbentley.5c	24 Jul 2004 06:26:16 -0000	1.3
@@ -2,6 +2,8 @@
 
 autoload Skiplist;
 
+const bool VALIDATE_SORT = false;
+
 prefix="skip/";
 
 autoload Sort;
@@ -420,10 +422,10 @@
     }
 
     void initialize_event_queue (Edge[*] segments) {
-	segments = remove_degenerate (segments);
 /*
-	segments = remove_horizontal (segments);
+	segments = remove_degenerate (segments);
 */
+	segments = remove_horizontal (segments);
 
 	for (int i=0; i < dim(segments); i++) {
 	    if (point_greater (segments[i].top, segments[i].bottom)) {
@@ -532,6 +534,9 @@
 	});
 	
 	Sortlist::insert (event_queue, intersect);
+
+	if (VALIDATE_SORT)
+	    Sortlist::validate (event_queue);
     }
 
     while ((EventPtr event_ptr = Sortlist::first (event_queue)) != EventPtr.nil)
@@ -552,7 +557,7 @@
 	    close (svg_file);
 	}
 
-	if (true)
+	if (false)
 	{
 	    printf ("%3d: type %g y %g sweep: ", FRAME_COUNT-1, event->type, current_y);
 	    fprint_sweep_line (stdout, sweep_line);
@@ -564,11 +569,13 @@
 	case Start:
 	    EdgePtr edge = event->e1;
 	    
-	    Sortlist::validate (sweep_line);
+	    if (VALIDATE_SORT)
+		Sortlist::validate (sweep_line);
 
 	    Sortlist::insert (sweep_line, edge);
 	    
-	    Sortlist::validate (sweep_line);
+	    if (VALIDATE_SORT)
+		Sortlist::validate (sweep_line);
 
 	    EdgePtr left = Sortlist::prev (sweep_line, edge);
 	    EdgePtr right = Sortlist::next (sweep_line, edge);
@@ -707,10 +714,14 @@
 
     Edge[*] intersected_edges = bentley_ottman_iterative (edges, &iterations);
 
-    if (edges_have_an_intersection_quadratic (&intersected_edges))
-	printf ("*** FAIL ***");
-    else
-	printf ("PASS");
+    if (true) {
+	if (edges_have_an_intersection_quadratic (&intersected_edges))
+	    printf ("*** FAIL ***");
+	else
+	    printf ("PASS");
+    } else {
+	printf ("NOT_CHECKED");
+    }
 
     printf (" (%d iteration%s)\n", iterations, iterations == 1 ? "" : "s");
 }
@@ -809,10 +820,8 @@
     }
 };
 
-/*
 for (int i=0; i < dim(tests); i++)
     run_test (tests[i].name, tests[i].edges);
- */
 
 num_random = 10;
 if (dim(argv)>1)
@@ -829,5 +838,6 @@
 	bottom = { x = PRNG::randint (10), y = PRNG::randint (10) }
     };
 }
-
+/*
 run_test ("random", random_edges);
+*/