[cairo] Tessellator performance patch

[Baz]

On 12/11/06, chris nuernberger <cnuernber at gmail.com> wrote:
> Now we both might be daft for sure, but if I understand you then it
> should boil down to two if statements, as if the x order of the ends
> of the segments switches.

Well not *that* simple, but certainly less multiplication is required
- after ordering the points, only one cross-product should be needed
to reject segments that cannot cross.

p = leftmost(a,b)
q = rightmost(a,b)
r = leftmost(c,d)
s = rightmost(c,d)
// we already know p.x <= r.x, (from scan order)
// and a.y <= b.y, c.y <= d.y. (a = left.top etc)
if (p.x == r.x) {
   if (p.y < r.y) {
      if (clockwise(r,s,q)) {
         // cannot intersect
      }
   } else if (p.y > r.y) {
      if (clockwise(r,q,s)) {
         // cannot intersect
      }
   }
} else if (clockwise(c, d, q)) {
      // cannot intersect
}
// may intersect.

the 'may intersect' cases here covers actual intersections and
colinear edges etc. Again, I may be wrong - my track record ain't
great so far (see below). So, only 2 multiplications instead of 8, at
the cost of a bunch of branching.

> I honestly was wondering the same thing, it is suggested on at least
> one web page on b-o.  But unlike you I didn't have the courage to ask
> to the entire list, or the time to figure out the code...
>

s/courage/stupidity/

Ok so what I posted last night was *somewhat* daft - changing the
slope comparison broke the code, that'll teach me to run make check
before make perf, and not to code when I'm falling asleep.  Reading
back of Rafael's earlier posts it seems he may have hit this same
problem.

-Baz (feeling a bit sheepish)