From 4051ed328b618e28cf1df276899eefa225225c76 Mon Sep 17 00:00:00 2001 From: Chris Wilson Date: Tue, 25 Aug 2009 20:51:06 +0100 Subject: [tessellator] Special case rectilinear tessellation For the frequent cases where we know in advance that we are dealing with a rectilinear path, but can not use the simple region code, implement a variant of the Bentley-Ottmann tessellator. The advantages here are that edge comparison is very simple (we only have vertical edges) and there are no intersection, though possible overlaps. The idea is the same, maintain a y-x sorted queue of start/stop events that demarcate traps and sweep through the active edges at each event, looking for completed traps. The motivation for this was noticing a performance regression in box-fill-outline with the self-intersection work: 1.9.2 to HEAD^: 3.66x slowdown HEAD^ to HEAD: 5.38x speedup 1.9.2 to HEAD: 1.57x speedup The cause of which was choosing to use spans instead of the region handling code, as the complex polygon was no longer being tessellated. --- test/ft-text-vertical-layout-type1.ref.png | Bin 3647 -> 3644 bytes test/ft-text-vertical-layout-type3.ref.png | Bin 3607 -> 3608 bytes 2 files changed, 0 insertions(+), 0 deletions(-) (limited to 'test') diff --git a/test/ft-text-vertical-layout-type1.ref.png b/test/ft-text-vertical-layout-type1.ref.png index 6f0df7b34..f1c12a9f3 100644 Binary files a/test/ft-text-vertical-layout-type1.ref.png and b/test/ft-text-vertical-layout-type1.ref.png differ diff --git a/test/ft-text-vertical-layout-type3.ref.png b/test/ft-text-vertical-layout-type3.ref.png index 94048f1c4..1bda421c4 100644 Binary files a/test/ft-text-vertical-layout-type3.ref.png and b/test/ft-text-vertical-layout-type3.ref.png differ -- cgit v1.2.3