[Commit]
tess ALGORITHM, NONE, 1.1 ChangeLog, 1.22, 1.23 bentley.5c,
1.18, 1.19
Carl Worth
commit at keithp.com
Sat Jul 31 15:01:52 PDT 2004
- Previous message: [Commit] tess ChangeLog, 1.21, 1.22 bentley.5c, 1.17,
1.18 sortlist.5c, 1.3, 1.4
- Next message: [Commit] tess ChangeLog,1.23,1.24 bentley.5c,1.19,1.20
- Messages sorted by:
[ date ]
[ thread ]
[ subject ]
[ author ]
Committed by: cworth
Update of /local/src/CVS/tess
In directory home.keithp.com:/tmp/cvs-serv32475
Modified Files:
ChangeLog bentley.5c
Added Files:
ALGORITHM
Log Message:
* ALGORITHM: Add John Hooby's pseudo-code description of the
algorithm, (with X/Y switched to match cairo convention for sweep
line direction).
* bentley.5c (bend_at_tolerance_squares): More infrastructure.
We're actually creating, sorting, and merging tolerance square
edges with the sweep_line, (at least at one point in the
algorithm). Now we just need to use those tolerance squares to
insert points into the edges, and update their position after the
edges move.
--- NEW FILE: ALGORITHM ---
This algorithm is from John Hobby's paper:
[Hobby93c] John D. Hobby, Practical Segment Intersection with
Finite Precision Output, Computation Geometry Theory and
Applications, 13(4), 1999.
http://cm.bell-labs.com/cm/cs/doc/93/2-27.ps.gz
I've rewritten here with the minor change of switching X/Y as
appropriate, (since Hobby' paper describes a vertical sweep line
moving left to right, while cairo has a horizontal sweep line moving
from top to bottom).
Algorithm 1 (The Pass 2 algorithm)
----------------------------------
For processing batch i. Main active list is initially valid for
Y = i - 1/2 - e for some inifinitesimal positive e.
1. Collect events E from pass 1 where the Y coordinate of the
starting, stopping, or intersection point rounds to i.
2. Create vertical edges for the left and right of the tolerance
squares for events E and sort them by X values. Then locate the X
values in the main active list. For each j where there are left and
right edges at X = j +/- 1/2 and the main active list has segments
between X = j - 1/2 and X = j + 1/2, insert (j,i) into each such
segment.
3. Update the main active list so it is valid for Y = i - e.
4. Relocate the X values for the horizontal tolerance edges in the
main active list using Y = i, and deduce which segments must have
crossed through or into tolerance squares. For each such crossing,
insert the point at the center of the tolerance square into the
segment.
5. Update the main active list so it is valid for Y = i + 1/2 - e.
When encountering a horizontal segment, immediately walk through
the tolerance edge list and insert vertices on the horizontal segment
for the squares it passes through.
6. Repeat step 4 with Y = i + 1/2.
Index: ChangeLog
===================================================================
RCS file: /local/src/CVS/tess/ChangeLog,v
retrieving revision 1.22
retrieving revision 1.23
diff -u -d -r1.22 -r1.23
--- ChangeLog 31 Jul 2004 17:31:10 -0000 1.22
+++ ChangeLog 31 Jul 2004 22:01:49 -0000 1.23
@@ -1,5 +1,16 @@
2004-07-31 Carl Worth <cworth at isi.edu>
+ * ALGORITHM: Add John Hooby's pseudo-code description of the
+ algorithm, (with X/Y switched to match cairo convention for sweep
+ line direction).
+
+ * bentley.5c (bend_at_tolerance_squares): More infrastructure.
+ We're actually creating, sorting, and merging tolerance square
+ edges with the sweep_line, (at least at one point in the
+ algorithm). Now we just need to use those tolerance squares to
+ insert points into the edges, and update their position after the
+ edges move.
+
* bentley.5c (bend_at_tolerance_squares): Replace potentially
unbounded iteration of Bentley-Ottman with a single second
pass. The second pass isn't yet computing intersections with
Index: bentley.5c
===================================================================
RCS file: /local/src/CVS/tess/bentley.5c,v
retrieving revision 1.18
retrieving revision 1.19
diff -u -d -r1.18 -r1.19
--- bentley.5c 31 Jul 2004 17:31:10 -0000 1.18
+++ bentley.5c 31 Jul 2004 22:01:49 -0000 1.19
@@ -39,25 +39,8 @@
Point bottom;
} Edge;
-typedef Sortlist::List EventQueue;
-typedef Sortlist::ElementPtr EventPtr;
-
*Edge ElementEdge(EdgePtr e) = e.element->value;
-typedef enum {
- Start, Intersect, Stop
-} EventType;
-
-typedef struct {
- EventType type;
- EdgePtr e1;
- EdgePtr e2;
- Point point;
- RationalPoint rational_point;
-} Event;
-
-*Event ElementEvent(EventPtr e) = e.element->value;
-
bool slope_greater (&Edge a, &Edge b)
{
int adx = a.bottom.x - a.top.x;
@@ -80,6 +63,90 @@
return adx * bdy == ady * bdx;
}
+rational edge_x_for_y (*Edge e, int y)
+{
+ int dx = e->bottom.x - e->top.x;
+ int dy = e->bottom.y - e->top.y;
+
+ if (dy == 0)
+ return e->top.x;
+
+ return e->top.x + (y - e->top.y) * dx / dy;
+}
+
+bool edge_greater_at_y (*Edge a, *Edge b, int y)
+{
+ rational ax = edge_x_for_y (a, y);
+ rational bx = edge_x_for_y (b, y);
+
+ if (ax != bx)
+ return ax > bx;
+
+ /* Slope comparison */
+ return slope_greater (a, b);
+}
+/*
+ bool edge_greater (*Edge a, *Edge b) {
+ int adx = a->bottom.x - a->top.x;
+ int bdx = b->bottom.x - b->top.x;
+
+ int ady = a->bottom.y - a->top.y;
+ int bdy = b->bottom.y - b->top.y;
+
+ 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;
+
+ if (ax != bx)
+ return ax > bx;
+
+ return slope_greater (a, b);
+ }
+*/
+
+/* Tolerance-square edges get their own datatype: squedge */
+
+typedef Sortlist::List TSquareList;
+typedef Sortlist::ElementPtr TSquarePtr;
+
+typedef struct {
+ /* XXX: We may want to make this X value implicit at some point */
+ rational x;
+ EdgePtr next_edge;
+} Squedge;
+
+typedef struct {
+ int x;
+ Squedge left;
+ Squedge right;
+} TSquare;
+
+*TSquare ElementTSquare(TSquarePtr t) = t.element->value;
+
+bool tsquare_greater (&TSquare a, &TSquare b) = a.x > b.x;
+
+typedef Sortlist::List EventQueue;
+typedef Sortlist::ElementPtr EventPtr;
+
+typedef enum {
+ Start, Intersect, Stop
+} EventType;
+
+typedef struct {
+ EventType type;
+ EdgePtr e1;
+ EdgePtr e2;
+ Point point;
+ RationalPoint rational_point;
+} Event;
+
+*Event ElementEvent(EventPtr e) = e.element->value;
+
bool event_greater (&Event a, &Event b)
{
/* The major motion of the sweep line is vertical
@@ -410,52 +477,7 @@
int current_y;
- bool edge_greater (*Edge a, *Edge b) {
-
- rational edge_x_for_y (*Edge e, int y) {
- int dx = e->bottom.x - e->top.x;
- int dy = e->bottom.y - e->top.y;
-
- if (dy == 0)
- return e->top.x;
-
- return e->top.x + (y - e->top.y) * dx / dy;
- }
-
- rational ax = edge_x_for_y (a, current_y);
- rational bx = edge_x_for_y (b, current_y);
-
- if (ax != bx)
- return ax > bx;
-
- /* Slope comparison */
- return slope_greater (a, b);
- }
-/*
- bool edge_greater (*Edge a, *Edge b) {
- int adx = a->bottom.x - a->top.x;
- int bdx = b->bottom.x - b->top.x;
-
- int ady = a->bottom.y - a->top.y;
- int bdy = b->bottom.y - b->top.y;
-
- 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;
-
- if (ax != bx)
- return ax > bx;
-
- return slope_greater (a, b);
- }
-*/
-
- EdgeList sweep_line = Sortlist::new (edge_greater);
+ EdgeList sweep_line = Sortlist::new (bool func (*Edge a, *Edge b) = edge_greater_at_y (a, b, current_y) );
void insert_event_if_intersect_below_current_y (EdgePtr left, EdgePtr right) {
@@ -590,7 +612,17 @@
Edge[*]
bend_at_tolerance_squares (Event[*] events)
{
- int current_y;
+ int batch_y;
+
+ /* XXX: We're currently using another skiplist for sweepline here,
+ * just like we did in the Bentley-Ottman pass. But, we should
+ * optimize this by saving the insert position from the first
+ * pass. Then we could use a doubly-linked list for the sweepline
+ * in the second pass (with O(1) insert instead of O(log n) */
+ EdgeList sweep_line = Sortlist::new (
+ bool func (*Edge a, *Edge b) = edge_greater_at_y (a, b, batch_y));
+
+ TSquareList tsquares;
bool edge_greater (*Edge a, *Edge b) {
@@ -604,8 +636,8 @@
return e->top.x + (y - e->top.y) * dx / dy;
}
- rational ax = edge_x_for_y (a, current_y);
- rational bx = edge_x_for_y (b, current_y);
+ rational ax = edge_x_for_y (a, batch_y);
+ rational bx = edge_x_for_y (b, batch_y);
if (ax != bx)
return ax > bx;
@@ -614,75 +646,136 @@
return slope_greater (a, b);
}
- EdgeList sweep_line = Sortlist::new (edge_greater);
+ bool squedge_greater_than_edge (Squedge s, EdgePtr e) {
+ if (e == EdgePtr.nil)
+ return false;
+ rational ex = edge_x_for_y(ElementEdge(e), batch_y);
+ return s.x > ex;
+ }
+
+ void merge_tsquares_with_sweep_line () {
+ TSquarePtr tp;
+ EdgePtr e;
+
+ for (tp = Sortlist::first (tsquares), e = Sortlist::first (sweep_line);
+ tp != TSquarePtr.nil;
+ tp = Sortlist::next (tsquares, tp))
+ {
+ *TSquare t = ElementTSquare (tp);
+ while (squedge_greater_than_edge (t->left, e))
+ e = Sortlist::next (sweep_line, e);
+ t->left.next_edge = e;
+ while (squedge_greater_than_edge (t->right, e))
+ e = Sortlist::next (sweep_line, e);
+ t->right.next_edge = e;
+ }
+ }
+
Edge[...] result = {};
- /* XXX: We're currently using another skiplist for sweepline here,
- * just like we did in the Bentley-Ottman pass. But, we should
- * optimize this by saving the insert position from the first
- * pass. Then we could use a doubly-linked list for the sweepline
- * in the second pass (with O(1) insert instead of O(log n) */
if (dim(events) == 0)
return result;
- current_y = events[0].point.y;
- for (int i=0; i < dim(events); i++) {
- *Event event = &events[i];
+ int batch_stop;
+ for (int batch_start = 0; batch_start < dim(events); batch_start = batch_stop) {
- current_y = event->point.y;
-
- enum switch (event->type) {
- case Start:
+ batch_y = events[batch_start].point.y;
+ batch_stop = batch_start + 1;
+ while (batch_stop < dim(events) && events[batch_stop].point.y == batch_y)
+ batch_stop++;
+
+ /* XXX: I haven't given much thought to what data structure we
+ * want for the sorted list of tolerance squares. We might
+ * want just an array. But, I'm getting used to using
+ * skiplists now, so for the moment I'll use it for
+ * convenience. */
+ tsquares = Sortlist::new (tsquare_greater);
+
+ for (int i=batch_start; i < batch_stop; i++) {
+ *Event event = &events[i];
- EdgePtr edge = event->e1;
-
if (VALIDATE_SORT)
- Sortlist::validate (sweep_line);
+ Sortlist::validate (tsquares);
- Sortlist::insert (sweep_line, edge);
+ TSquarePtr tsquare = Sortlist::element (& (TSquare) {
+ x = event->point.x,
+ left = {
+ x = event->point.x - 1/2,
+ next_edge = EdgePtr.nil
+ },
+ right = {
+ x = event->point.x + 1/2,
+ next_edge = EdgePtr.nil
+ }
+ });
+
+ /* XXX: We should probably provide a way to prune
+ * duplicates on insert. */
+
+ Sortlist::insert (tsquares, tsquare);
if (VALIDATE_SORT)
- Sortlist::validate (sweep_line);
-
- break;
- case Stop:
+ Sortlist::validate (tsquares);
+ }
- EdgePtr edge = event->e1;
-
- result[dim(result)] = (Edge) {
- top = ElementEdge(edge)->middle,
- bottom = event->point
- };
+ merge_tsquares_with_sweep_line ();
+
+ for (int i=batch_start; i < batch_stop; i++) {
+ *Event event = &events[i];
+
+ enum switch (event->type) {
+ case Start:
+
+ EdgePtr edge = event->e1;
- Sortlist::delete (sweep_line, edge);
+ if (VALIDATE_SORT)
+ Sortlist::validate (sweep_line);
- break;
- case Intersect:
+ Sortlist::insert (sweep_line, edge);
- EdgePtr e1 = event->e1;
- EdgePtr e2 = event->e2;
+ if (VALIDATE_SORT)
+ Sortlist::validate (sweep_line);
+
+ break;
+ case Stop:
- /* Avoid emitting a degenerate edge if this edge has already
- * been used for a previous intersection at exactly the
- * same point. */
- if (ElementEdge(e1)->middle != event->point)
- result[dim(result)] = (Edge) {
- top = ElementEdge(e1)->middle,
- bottom = event->point
- };
+ EdgePtr edge = event->e1;
- if (ElementEdge(e2)->middle != event->point)
result[dim(result)] = (Edge) {
- top = ElementEdge(e2)->middle,
+ top = ElementEdge(edge)->middle,
bottom = event->point
};
- ElementEdge(e1)->middle = event->point;
- ElementEdge(e2)->middle = event->point;
+ Sortlist::delete (sweep_line, edge);
+
+ break;
+ case Intersect:
+
+ EdgePtr e1 = event->e1;
+ EdgePtr e2 = event->e2;
+
+ /* Avoid emitting a degenerate edge if this edge has already
+ * been used for a previous intersection at exactly the
+ * same point. */
+ if (ElementEdge(e1)->middle != event->point)
+ result[dim(result)] = (Edge) {
+ top = ElementEdge(e1)->middle,
+ bottom = event->point
+ };
- Sortlist::swap (sweep_line, e1);
+ if (ElementEdge(e2)->middle != event->point)
+ result[dim(result)] = (Edge) {
+ top = ElementEdge(e2)->middle,
+ bottom = event->point
+ };
- break;
+ ElementEdge(e1)->middle = event->point;
+ ElementEdge(e2)->middle = event->point;
+
+ Sortlist::swap (sweep_line, e1);
+
+ break;
+ }
}
}
- Previous message: [Commit] tess ChangeLog, 1.21, 1.22 bentley.5c, 1.17,
1.18 sortlist.5c, 1.3, 1.4
- Next message: [Commit] tess ChangeLog,1.23,1.24 bentley.5c,1.19,1.20
- Messages sorted by:
[ date ]
[ thread ]
[ subject ]
[ author ]
More information about the Commit
mailing list