Re: GdkSpan

[Owen Taylor <otaylor redhat com>]

Alexander Larsson <alla lysator liu se> writes:

> For my next checkin to GtkFB i need to do some generic Gdk changes. I
> added a new type GdkSpan, and two functions that handle intersection these
> with regions.
> 
> Is this patch ok? I'd also be very glad if someone (owen?) reviewed the
> intersection functions, since these kind of functions are very sensitive
> to boundary condition errors, and quite hard to test.

Hmmm, I'm basically OK with the addition, but some questions about the interface
details:

 - How are you going to use these functions?

   It worries me a bit since the typical case is taking a graphics
   primitive and breaking it into a set of spans. Taking those spans
   and intersecting them one-by-one with a clip region is 
   going to be _slow_ ...

 - Would the 'GList *' return for gdk_region_span_intersect() better
   be done as a func/data foreach? [ again, a question of usage pattern ]

 - It seems a bit inelegant/inefficient to have to do the walk through
   the entire region again in the case of complex intersection, though
   I suppose it is a pretty uncommon case.

 - gdk_region_span_simple_intersect () should take two GdkSpans - one the 
   input; one the output, and then work properly if they are the 
   same.
  
   This is more simimlar to the way, say, gdk_rectangle_intersect() works.

 - The names aren't very natural sounding - while writing the above
   I kept having to refer to the patch again for the names - how about:

    gdk_region_get_span_intersection_simple ()
    gdk_region_get_span_intersection_list ()

 - Since these are new public API entry points, they need documentation
   comments.

 - I'd add the optimizations to the non-simple functions as well - 
   not having them there creates a confusing dependency between
   the two functions, and if you are taking the approach of calling
   first intersect_simple() and then intersect(), you are resigned 
   to the fact that the full intersect() is going to be the slow
   case, so a few more checks won't hurt.

The math all checks out by me (though I won't guarantee I couldn't
have made a mistake as well reading it over.)

> +      if ((right > pbox->x1) && (left < pbox->x2))
> +	{
> +	  /* Span partially intersected pbox */
> +	  clipped_left = left;
> +	  clipped_right = right;
> +	  
> +	  if (left < pbox->x1)
> +	    clipped_left = pbox->x1;
> +	  
> +	  if (right > pbox->x2)
> +	    clipped_right = pbox->x2;

 I'd generally right this as 

   clipped_left = MAX (left, pbox->x1);
   clipped_right = MIN (right, pbox->x2);
 
Same instructions but more compact and thus easier to read.

> +	  clipped_span = g_new (GdkSpan, 1);
> +	  clipped_span->y = y;
> +	  clipped_span->x = clipped_left;
> +	  clipped_span->width = clipped_right - clipped_left;
> +	  spans = g_list_append (spans, clipped_span);

Always prepend and reverse at the end; it should never be
slower and can occasionally be _much_ faster. (Or, do it as
a foreach() which avoids the issue.)

Regards,
                                        Owen