Re: GdkSpan

[Alexander Larsson <alla lysator liu se>]

On 20 Nov 2000, Owen Taylor wrote:

> I agree that generating spans and clipping them is the right thing to
> do. My doubts come from the fact that there the possibility of very
> significant optimization from having a routine that takes an array of
> spans in banded order and does the clipping on all of them at once,
> rather than clipping them one by one.

Ok, this is a slight optimization in the case of sorted spans. How about
this. It's even got docs.

/ Alex

Index: gdk/gdktypes.h
===================================================================
RCS file: /cvs/gnome/gtk+/gdk/gdktypes.h,v
retrieving revision 1.56
diff -u -p -r1.56 gdktypes.h
--- gdk/gdktypes.h	2000/09/07 18:07:59	1.56
+++ gdk/gdktypes.h	2000/11/21 14:05:59
@@ -67,6 +67,7 @@ extern "C" {
 typedef struct _GdkPoint	      GdkPoint;
 typedef struct _GdkRectangle	      GdkRectangle;
 typedef struct _GdkSegment	      GdkSegment;
+typedef struct _GdkSpan	              GdkSpan;
 
 /*
  * Note that on some platforms the wchar_t type
@@ -182,6 +183,13 @@ struct _GdkSegment
   gint y1;
   gint x2;
   gint y2;
+};
+
+struct _GdkSpan
+{
+  gint x;
+  gint y;
+  gint width;
 };
 
 #ifdef __cplusplus
Index: gdk/gdkregion.h
===================================================================
RCS file: /cvs/gnome/gtk+/gdk/gdkregion.h,v
retrieving revision 1.2
diff -u -p -r1.2 gdkregion.h
--- gdk/gdkregion.h	2000/03/28 01:24:42	1.2
+++ gdk/gdkregion.h	2000/11/21 14:05:59
@@ -29,6 +29,9 @@ typedef enum
   GDK_OVERLAP_RECTANGLE_PART
 } GdkOverlapType;
 
+typedef void (*GdkSpanFunc) (GdkSpan *span,
+			     gpointer data);
+
 GdkRegion *gdk_region_new       (void);
 GdkRegion *gdk_region_polygon   (GdkPoint     *points,
 				 gint          npoints,
@@ -65,6 +68,18 @@ void gdk_region_subtract        (GdkRegi
 				 GdkRegion    *source2);
 void gdk_region_xor             (GdkRegion    *source1,
 				 GdkRegion    *source2);
+
+void gdk_region_spans_intersect_foreach        (GdkRegion   *region,
+						GdkSpan     *spans,
+						int          n_spans,
+						GdkSpanFunc  function,
+						gpointer     data);
+void gdk_region_sorted_spans_intersect_foreach (GdkRegion   *region,
+						GdkSpan     *spans,
+						int          n_spans,
+						GdkSpanFunc  function,
+						gpointer     data);
+
 
 #ifdef __cplusplus
 }
Index: gdk/gdkregion-generic.c
===================================================================
RCS file: /cvs/gnome/gtk+/gdk/gdkregion-generic.c,v
retrieving revision 1.4
diff -u -p -r1.4 gdkregion-generic.c
--- gdk/gdkregion-generic.c	2000/08/09 02:56:13	1.4
+++ gdk/gdkregion-generic.c	2000/11/21 14:05:59
@@ -1505,3 +1505,142 @@ gdk_region_rect_in (GdkRegion    *region
 	      GDK_OVERLAP_RECTANGLE_PART : GDK_OVERLAP_RECTANGLE_IN) : 
 	  GDK_OVERLAP_RECTANGLE_OUT);
 }
+
+
+void
+gdk_region_spans_intersect_foreach (GdkRegion *region,
+				    GdkSpan   *spans,
+				    int        n_spans,
+				    GdkSpanFunc function,
+				    gpointer data)
+{
+  gint i, left, right, y;
+  gint clipped_left, clipped_right;
+  GdkRegionBox *pbox;
+  GdkRegionBox *pboxEnd;
+  GdkSpan out_span;
+
+  if (!region->numRects)
+    return;
+
+  for (i=0;i<n_spans;i++)
+    {
+      y = spans[i].y;
+      left = spans[i].x;
+      right = left + spans[i].width; /* right is not in the span! */
+    
+      if (! ((region->extents.y1 <= y) &&
+	     (region->extents.y2 > y) &&
+	     (region->extents.x1 < right) &&
+	     (region->extents.x2 > left)) ) 
+	continue;
+
+      /* can stop when we passed y */
+      for (pbox = region->rects, pboxEnd = pbox + region->numRects;
+	   pbox < pboxEnd;
+	   pbox++)
+	{
+	  if (pbox->y2 <= y)
+	    continue; /* Not quite there yet */
+	  
+	  if (pbox->y1 > y)
+	    break; /* passed the spanline */
+	  
+	  if ((right > pbox->x1) && (left < pbox->x2)) 
+	    {
+	      clipped_left = MAX (left, pbox->x1);
+	      clipped_right = MIN (right, pbox->x2);
+	      
+	      out_span.y = y;
+	      out_span.x = clipped_left;
+	      out_span.width = clipped_right - clipped_left;
+	      (*function) (&out_span, data);
+	    }
+	}
+    }
+}
+
+
+void
+gdk_region_sorted_spans_intersect_foreach (GdkRegion  *region,
+					   GdkSpan    *spans,
+					   int         n_spans,
+					   GdkSpanFunc function,
+					   gpointer    data)
+{
+  gint left, right, y;
+  gint clipped_left, clipped_right;
+  GdkRegionBox *pbox;
+  GdkRegionBox *pboxEnd;
+  GdkSpan *span, *tmpspan;
+  GdkSpan *end_span;
+  GdkSpan out_span;
+
+  if ((!region->numRects) || (n_spans == 0))
+    return;
+
+  y = span->y;
+  left = span->x;
+  right = span->x + span->width; /* right is not in the span! */
+
+  /* The main method here is to step along the
+   * sorted rectangles and spans in lock step, and
+   * clipping the spans that are in the current
+   * rectangle before going on to the next rectangle.
+   */
+
+  span = spans;
+  end_span = spans + n_spans;
+  pbox = region->rects;
+  pboxEnd = pbox + region->numRects;
+  while (pbox < pboxEnd)
+    {
+      while ((pbox->y2 < span->y) || (span->y < pbox->y1))
+	{
+	  /* Skip any rectangles that are above the current span */
+	  if (pbox->y2 < span->y)
+	    {
+	      pbox++;
+	      if (pbox == pboxEnd)
+		return;
+	    }
+	  /* Skip any spans that are above the current rectangle */
+	  if (span->y < pbox->y1)
+	    {
+	      span++;
+	      if (span == end_span)
+		return;
+	    }
+	}
+      
+      /* Ok, we got at least one span that might intersect this rectangle. */
+      tmpspan = span;
+      while ((tmpspan < end_span) &&
+	     (tmpspan->y < pbox->y2))
+	{
+	  y = tmpspan->y;
+	  left = tmpspan->x;
+	  right = left + tmpspan->width; /* right is not in the span! */
+	  
+	  if ((right > pbox->x1) && (left < pbox->x2))
+	    {
+	      clipped_left = MAX (left, pbox->x1);
+	      clipped_right = MIN (right, pbox->x2);
+	      
+	      out_span.y = y;
+	      out_span.x = clipped_left;
+	      out_span.width = clipped_right - clipped_left;
+	      (*function) (&out_span, data);
+	    }
+	  
+	  tmpspan++;
+	}
+
+      /* Finished this rectangle.
+       * The spans could still intersect the next one
+       */
+      pbox++;
+    }
+  
+  return spans;
+}
Index: docs/reference/gdk/gdk-sections.txt
===================================================================
RCS file: /cvs/gnome/gtk+/docs/reference/gdk/gdk-sections.txt,v
retrieving revision 1.10
diff -u -p -r1.10 gdk-sections.txt
--- docs/reference/gdk/gdk-sections.txt	2000/11/14 16:36:15	1.10
+++ docs/reference/gdk/gdk-sections.txt	2000/11/21 14:05:57
@@ -620,6 +620,13 @@ gdk_region_intersect
 gdk_region_union
 gdk_region_subtract
 gdk_region_xor
+
+<SUBSECTION>
+GdkSpan
+GdkSpanFunc
+gdk_region_spans_intersect_foreach
+gdk_region_sorted_spans_intersect_foreach
+
 </SECTION>
 
 <SECTION>
Index: docs/reference/gdk/tmpl/regions.sgml
===================================================================
RCS file: /cvs/gnome/gtk+/docs/reference/gdk/tmpl/regions.sgml,v
retrieving revision 1.4
diff -u -p -r1.4 regions.sgml
--- docs/reference/gdk/tmpl/regions.sgml	2000/09/07 18:17:03	1.4
+++ docs/reference/gdk/tmpl/regions.sgml	2000/11/21 14:05:58
@@ -6,8 +6,8 @@ simple graphical data types.
 
 <!-- ##### SECTION Long_Description ##### -->
 <para>
-GDK provides the #GdkPoint, #GdkRectangle and #GdkRegion data types for
-representing pixels and sets of pixels on the screen.
+GDK provides the #GdkPoint, #GdkRectangle, #GdkRegion and #GdkSpan data types
+for representing pixels and sets of pixels on the screen.
 </para>
 <para>
 #GdkPoint is a simple structure containing an x and y coordinate of a point.
@@ -22,6 +22,11 @@ gdk_rectangle_union().
 #GdkRegion is an opaque data type holding a set of arbitrary pixels, and is
 usually used for clipping graphical operations (see gdk_gc_set_clip_region()).
 </para>
+<para>
+#GdkSpan is a structure holding a spanline. A spanline is a horizontal line that
+is one pixel wide. It is mainly used when rasterizing other graphics primitives.
+It can be intersected to regions by using gdk_region_spans_intersect_foreach().
+</para>
 
 <!-- ##### SECTION See_Also ##### -->
 <para>
@@ -259,5 +264,50 @@ Returns the union of a region and a rect
 
 @source1: 
 @source2: 
+
+
+<!-- ##### STRUCT GdkSpan ##### -->
+<para>
+
+</para>
+
+ x: 
+ y: 
+ width: 
+
+<!-- ##### USER_FUNCTION GdkSpanFunc ##### -->
+<para>
+
+</para>
+
+ span: The intersected part of the span.
+ data: Opaque data passed by user.
+
+
+<!-- ##### FUNCTION gdk_region_spans_intersect_foreach ##### -->
+<para>
+Intersects a set of spans with a region and call a user specified
+function for each resulting spanline.
+</para>
+
+ region: The region to intersect against.
+ spans: Array of spans to intersect.
+ n_spans: Number of spans.
+ function: The function to call for each intersected spanline.
+ data: Opaque user data passed to function.
+
+
+<!-- ##### FUNCTION gdk_region_sorted_spans_intersect_foreach ##### -->
+<para>
+Intersects a set of sorted spans with a region and call a user specified
+function for each resulting spanline. This function is a lot more effective
+than gdk_region_spans_intersect_foreach() since the spans are sorted.
+</para>
+
+ region: The region to intersect against.
+ spans: Array of spans to intersect. Must be sorted in increasing y order.
+ n_spans: Number of spans.
+ function: The function to call for each intersected spanline.
+ data: Opaque user data passed to function.