summaryrefslogtreecommitdiff
path: root/src/cairo-bentley-ottmann.c
Commit message (Collapse)AuthorAgeFilesLines
* Rename cairo_lines_compare_at_y into _cairo_lines_compare_at_y and fix syntaxMarc Jeanmougin2021-04-021-1/+1
| | | | Fixes https://gitlab.freedesktop.org/cairo/cairo/-/issues/467
* bo: Free event_y in case of error to prevent memory leak (CID ##1160682)Bryce Harrington2018-06-131-1/+4
| | | | | | | | | If the call to _cairo_malloc_ab_plus_c() fails, it returns an error without first freeing event_y. Coverity ID: #1160682 Signed-off-by: Bryce Harrington <bryce@bryceharrington.org> Reviewed-By: Uli Schlachter <psychon@znc.in>
* bo: Check null return from _cairo_malloc_ab() (CID #1159556)Bryce Harrington2018-06-131-2/+5
| | | | | | | | | | _cairo_malloc_ab() can return NULL under some circumstances, and all other callers of this routine in the Cairo codebase check its return, so do so here as well. Coverity ID: #1159556 Signed-off-by: Bryce Harrington <bryce@bryceharrington.org> Reviewed-by: Uli Schlachter <psychon@znc.in>
* stroke,traps: Emit join without loss of precisionChris Wilson2014-09-291-225/+7
| | | | | | | | | | | | | | As the target renderers operate at a different sample resolution then we use internally for coordinate representation, there is always a potential for discrepancies in the line gradients when passing around trapezoids. To overcome this, the protocol specification of trapezoids uses the full lines and vertical range as opposed to vertices and so long as we always use the same lines for conjoint trapezoids, they remain abutting in the rasteriser. Bugzilla: https://bugs.freedesktop.org/show_bug.cgi?id=84115 Testcase: bug-84115 Signed-off-by: Chris Wilson <chris@chris-wilson.co.uk>
* bentley-ottmann: Cache the most recent edge colinearity checkChris Wilson2012-08-261-10/+32
| | | | | | | | We frequently compare neighbouring edges for their colinearity (in case we can skip over them in the active list) so we can record the last comparison and reuse the result next time. Signed-off-by: Chris Wilson <chris@chris-wilson.co.uk>
* bentley-ottmann: hint that the insertion compare function should be inlinedChris Wilson2012-08-261-1/+1
| | | | | | | | Albeit it too large for gcc to automatically inline, it is only used from within a single function. Hopefully gcc can optimise better with the hint. Signed-off-by: Chris Wilson <chris@chris-wilson.co.uk>
* bentley-ottmann: Only check the pairs of coordinates for equality.Chris Wilson2012-08-261-1/+1
| | | | Signed-off-by: Chris Wilson <chris@chris-wilson.co.uk>
* bentley-ottman: Remove a few superfluous status propagationChris Wilson2012-08-261-48/+21
| | | | | | | For the traps it is simpler if we report the status at the end, and no-op the accumulation of the trap after hitting the error condition. Signed-off-by: Chris Wilson <chris@chris-wilson.co.uk>
* Split cairo-combsort-privates into struct+inlinesChris Wilson2012-04-191-1/+1
| | | | | References: https://bugs.freedesktop.org/show_bug.cgi?id=48577 Signed-off-by: Chris Wilson <chris@chris-wilson.co.uk>
* bentley-ottmann: Sort by edge bounding boxes before computing xChris Wilson2012-03-101-0/+7
| | | | Signed-off-by: Chris Wilson <chris@chris-wilson.co.uk>
* bentley-ottmann: Skip intersection check if the bounds do not overlapChris Wilson2012-03-101-0/+4
| | | | Signed-off-by: Chris Wilson <chris@chris-wilson.co.uk>
* bentley-ottman: End subsumed colinear trapsChris Wilson2011-09-161-3/+9
| | | | | | | | | I'm not quite sure how we end up with a pair of colinear edges both with a deferred trap... Fixes crash in bug-bo-ricotz Signed-off-by: Chris Wilson <chris@chris-wilson.co.uk>
* Introduce a new compositor architectureChris Wilson2011-09-121-100/+54
| | | | | | | | | | | | | | | | | | Having spent the last dev cycle looking at how we could specialize the compositors for various backends, we once again look for the commonalities in order to reduce the duplication. In part this is motivated by the idea that spans is a good interface for both the existent GL backend and pixman, and so they deserve a dedicated compositor. xcb/xlib target an identical rendering system and so they should be using the same compositor, and it should be possible to run that same compositor locally against pixman to generate reference tests. Signed-off-by: Chris Wilson <chris@chris-wilson.co.uk> P.S. This brings massive upheaval (read breakage) I've tried delaying in order to fix as many things as possible but now this one patch does far, far, far too much. Apologies in advance for breaking your favourite backend, but trust me in that the end result will be much better. :)
* bo: Perform an initial bucket sort on the start eventsChris Wilson2011-08-121-9/+38
| | | | Signed-off-by: Chris Wilson <chris@chris-wilson.co.uk>
* polygon: Merge _cairo_polygon_init and _cairo_polygon_limitAndrea Canciani2010-12-101-2/+1
| | | | | | | _cairo_polygon_limit() had to be called immediately after _cairo_polygon_init() (or never at all). Merging the two calls is a simple way to enforce this rule.
* bo: And disable DEBUG_TRAPS again.Chris Wilson2010-06-091-1/+1
| | | | Meh. I'm going back to bed. Thanks Joonas for catching this.
* bo: Fix debugging for changes in internal traps api.Chris Wilson2010-06-091-3/+7
|
* Update FSF addressAndrea Canciani2010-04-271-1/+1
| | | | | | | | | | | I updated the Free Software Foundation address using the following script. for i in $(git grep Temple | cut -d: -f1 ) do sed -e 's/59 Temple Place[, -]* Suite 330, Boston, MA *02111-1307[, ]* USA/51 Franklin Street, Suite 500, Boston, MA 02110-1335, USA/' -i "$i" done Fixes http://bugs.freedesktop.org/show_bug.cgi?id=21356
* Move _cairo_error() to a standalone headerChris Wilson2010-01-221-0/+1
| | | | | A pending commit will want to include some utility code from cairo and so we need to extricate the error handling from the PLT symbol hiding.
* [clip] Use geometric clipping for unaligned clipsChris Wilson2009-08-291-262/+23
| | | | | | For the simple cases where the clip is an unaligned box (or boxes), apply the clip directly to the geometry and avoid having to use an intermediate clip-mask.
* [tessellator] Special case rectilinear tessellationChris Wilson2009-08-291-2/+3
| | | | | | | | | | | | | | | | | | | | 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.
* [tessellator] Use a priority queue for the eventsChris Wilson2009-08-291-135/+206
| | | | | The skip list was suffering from severe overhead, so though the search was quick, the extra copies during insertion and deletion were slow.
* [tessellator] Remove the skiplist for the active edgesChris Wilson2009-08-291-155/+75
| | | | | | | The active edge list is typically short, and the skiplist adds significant overhead that far outweigh the benefit of the O(n lg n) sort. Instead we track the position of the last insertion edge, knowing that the start events are lexicographically sorted, and begin a linear search from there.
* Eliminate self-intersecting strokes.Chris Wilson2009-08-291-761/+1072
| | | | | | | | | | | | | | | | | | | | We refactor the surface fallbacks to convert full strokes and fills to the intermediate polygon representation (as opposed to before where we returned the trapezoidal representation). This allow greater flexibility to choose how then to rasterize the polygon. Where possible we use the local spans rasteriser for its increased performance, but still have the option to use the tessellator instead (for example, with the current Render protocol which does not yet have a polygon image). In order to accommodate this, the spans interface is tweaked to accept whole polygons instead of a path and the tessellator is tweaked for speed. Performance Impact ================== ... Still measuring, expecting some severe regressions. ...
* [memfault] Manually inject faults when using stack allocationsChris Wilson2009-04-231-0/+3
| | | | | | | | | | Ensure that no assumptions are made that a small allocation will succeed by manually injecting faults when we may be simply allocating from an embedded memory pool. The main advantage in manual fault injection is improved code coverage - from within the test suite most allocations are handled by the embedded memory pools.
* Trivial warning fixes.Chris Wilson2009-01-301-1/+0
| | | | | Cleanup a few compiler warnings about unused variables and mismatching pointer types.
* [skiplist] Provide an initial stack allocated pool.Chris Wilson2009-01-291-23/+10
| | | | | | Since we only need to allocate elts for intersection events and edges, the number of elts in flight at any one time is actually quite small and can usually be accommodated from an embedded pool.
* [tessellator] Memleak on error path.Chris Wilson2009-01-291-1/+3
| | | | | Add a missing _cairo_skip_list_fini() after failure to allocate the events.
* [skiplist] Allocate elements in chunks.Chris Wilson2008-12-121-9/+24
| | | | | Use a pool allocator to preallocate a chunk from which to allocate the skiplist elements (if we failed to reallocate from the freelists).
* Mark allocation failures as unlikely.Chris Wilson2008-11-291-7/+6
| | | | | Use the gcc likelihood annotation to indicate that allocation failures are extremely unlikely.
* [spline] Eliminate intermediate allocations during spline decomposition.Chris Wilson2008-11-161-9/+3
| | | | | | | The spline decomposition code allocates and stores points in a temporary buffer which is immediately consumed by the caller. If the caller supplies a callback that handles each point computed along the spline, then we can use the point immediately and avoid the allocation.
* [tessellator] Refine the math comments.Chris Wilson2008-10-311-15/+15
| | | | | | | | First of a simple substitution for -?-, as they are very confusing in context with other minus signs floating around. Carl has promised to go over these docs with me at the HackFest in order to improve them (and verify them).
* [tessellator] Simplify dequeuing by using a sentinel value.Chris Wilson2008-10-301-16/+16
| | | | | | | Instead of maintaining an index and comparing it to the count, just mark the last startstop event with NULL and stop dequeuing events upon seeing that sentinel value. (Removes an unreadable line, and cachegrind hints that it may be a tiny bit faster.)
* [tessellator] Use a combsort for sorting the event queue.Chris Wilson2008-10-301-19/+20
| | | | | In my experiments using cairo-perf, the inlined combsort is ~20% quicker than the library qsort.
* [tessellator] Perform cheap checks before computing intersect.Chris Wilson2008-10-301-1/+50
| | | | | | | | | | | | | First check if we can reject the intersection without having to perform the full divides, based on analysing: t * (ady*bdx - bdy*adx) = bdy * (ax - bx) - bdx * (ay - by) s * (ady*bdx - bdy*adx) = ady * (ax - bx) - adx * (ay - by) and excluding the result if by inspection we know that (s, t) <= 0 || (s, t) => 1. Doing so virtually eliminates all division and speeds up the strokes (when performing self-intersection elimination using the tessellator) perf cases by about 5%.
* [tessellator] Simplify special cases of edges to compare.Chris Wilson2008-10-301-26/+106
| | | | | | | | | | Use our prior knowledge of the inputs and trivial conditions to simplify the edge equations and in many common conditions, such as vertical edges and common points, reduce the operations down to a just returning the non-degenerate 32 bit value. This adds an overhead of a few conditionals, but on the fast paths we actually generate fewer branches and many fewer arithmetic operations such that it improves performance of the fill performance tests by around 10%.
* [tessellator] Compile fixes for !HAVE_INT64_TChris Wilson2008-10-071-7/+7
| | | | | Fixup a couple of instances of implicit down-casting to 32bits from a 64bit wide integer and add a new is_zero() predicate.
* [tessellator] Avoid implicit promotion to 64bit integer.Chris Wilson2008-10-071-10/+10
| | | | | | Avoid passing a 32bit integer as a cairo_int64_t in case we do not have a 64bit native integral type. As a side-effect this means we can also use a narrower multiply.
* [tessellator] Replace open-coding _cairo_int64_cmp().Chris Wilson2008-10-061-16/+3
| | | | | | | | | | | | | | | We often use the construct: if (_cairo_int64_lt (A, B) return -1; if (_cairo_int64_gt (A, B) return 1; return 0; to compare two large integers (int64, or int128) which does twice the required work on CPUs without large integer support. So replace it with a single wideint function _cairo_int64_cmp() and therefore allow opportunities to both shrink the code size and write a more efficient comparison. (The primarily motivation is to simply replace each block with a single more expressive line.)
* [tessellator] Special case edge comparisons when on either end-point.Chris Wilson2008-10-041-4/+96
| | | | | | | | If the sweep-line is currently on an end-point of a line, then we know its precise x value and can use a cheaper comparator. Considering that we often need to compare events at end-points (for instance on a start event), this happens frequently enough to warrant special casing.
* [tessellator] Direct comparison of result in edges_compare_x_for_y.Chris Wilson2008-10-041-42/+55
| | | | | | | | | | | | | | | | | | | | | We need to compare the x-coordinate of a line at a for a particular y, without loss of precision. The x-coordinate along an edge for a given y is: X = A_x + (Y - A_y) * A_dx / A_dy So the inequality we wish to test is: A_x + (Y - A_y) * A_dx / A_dy -?- B_x + (Y - B_y) * B_dx / B_dy, where -?- is our inequality operator. By construction we know that A_dy and B_dy (and (Y - A_y), (Y - B_y)) are all positive, so we can rearrange it thus without causing a sign change: A_dy * B_dy * (A_x - B_x) -?- (Y - B_y) * B_dx * A_dy - (Y - A_y) * A_dx * B_dy Given the assumption that all the deltas fit within 32 bits, we can compute this comparison directly using 128 bit arithmetic.
* [tessellator] Use abort() instead of exit().Chris Wilson2008-10-041-3/+3
| | | | | More friendly when debugging, as the debug will (by default) catch the SIGTRAP and break at the offending test.
* [tessellator] Skip edges that lie outside the region of interest.M Joonas Pihlaja2008-09-241-0/+11
| | | | | We don't need to tessellate edges strictly above or below the the limits of the traps.
* [tessellator] Only run sweep-line validator when debuggingChris Wilson2008-09-191-7/+10
| | | | | | | | The tessellator is well-proven now. However, the sweep-line validator consumes around 50% of the total time required to draw the fractal Pythagoras tree (the leaves are sub-pixel rectangles, so lots of edges to sweep through). So disable the validator, but keep it available for debugging.
* Simple perf tweaks for a rectilinear Hilbert curve.Chris Wilson2008-09-191-18/+18
| | | | | Some tweaks to avoid stack copies and branches that save ~25% in _cairo_traps_tessellate_convex_quad().
* Bug: tessellator sometimes ends rightmost trapezoids too lateM Joonas Pihlaja2008-06-181-1/+1
| | | | | | | | | | | | | | Reported on the cairo mailing list: http://lists.cairographics.org/archives/cairo/2008-May/014233.html The tessellator would sometimes produce self-intersecting trapezoids because it would skip the last edge in the active list when deciding whether we can continue the current trapezoid or not. The bug never caused a problem with pixman based rasterisation because pixman stops filling in a trapezoid once it detects a self intersection.
* Fix newly detected doc syntax issuesBehdad Esfahbod2008-06-011-1/+1
|
* Add more consts to function signatures and remove stale prototypeBehdad Esfahbod2008-05-091-3/+3
|
* [doc] Replace 'NOTE' by 'Note' and add it to testBehdad Esfahbod2008-01-281-1/+1
|
* [doc] Make sure all type names in docs are prefixed by #Behdad Esfahbod2008-01-281-2/+2
|
View Lorry Controller Status