1 /* Copyright 2013 Jeff Muizelaar
2 *
3 * Use of this source code is governed by a MIT-style license that can be
4 * found in the LICENSE file.
5 *
6 * Portions Copyright 2006 The Android Open Source Project
7 *
8 * Use of that source code is governed by a BSD-style license that can be
9 * found in the LICENSE.skia file.
10 */
11
12
13 use typed_arena::Arena;
14
15 use crate::{IntRect, Point};
16 use crate::blitter::RasterBlitter;
17 use crate::path_builder::Winding;
18 use crate::geom::intrect;
19
20 use std::ptr::NonNull;
21
22 // One reason to have separate Edge/ActiveEdge is reduce the
23 // memory usage of inactive edges. On the other hand
24 // managing the lifetime of ActiveEdges is a lot
25 // trickier than Edges. Edges can stay alive for the entire
26 // rasterization. ActiveEdges will come and go in a much
27 // less predictable order. On the other hand having the
28 // ActiveEdges close together in memory would help
29 // avoid cache misses. If we did switch to having separate
30 // active edges it might be wise to store the active edges
31 // in an array instead of as a linked list. This will work
32 // well for the bubble sorting, but will cause more problems
33 // for insertion.
34
35 struct Edge {
36 //XXX: it is probably worth renaming this to top and bottom
37 x1: i32,
38 y1: i32,
39 x2: i32,
40 y2: i32,
41 control_x: i32,
42 control_y: i32,
43 }
44
div_fixed16_fixed16(a: i32, b: i32) -> i3245 fn div_fixed16_fixed16(a: i32, b: i32) -> i32 {
46 (((a as i64) << 16) / (b as i64)) as i32
47 }
48
49 // Fixed point representation:
50 // We use 30.2 for the end points and 16.16 for the intermediate
51 // results. I believe this essentially limits us to a 16.16 space.
52 //
53 // Prior Work:
54 // - Cairo used to be 16.16 but switched to 24.8. Cairo converts paths
55 // early to this fixed representation
56 // - Fitz uses different precision depending on the AA settings
57 // and uses the following Bresenham style adjustment in its step function
58 // to avoid having to worry about intermediate precision
59 // edge->x += edge->xmove;
60 // edge->e += edge->adj_up;
61 // if (edge->e > 0) {
62 // edge->x += edge->xdir;
63 // edge->e -= edge->adj_down;
64 // }
65
66
67 // it is possible to fit this into 64 bytes on x86-64
68 // with the following layout:
69 //
70 // 4 x2,y2
71 // 8 next
72 // 6*4 slope_x,fullx,next_x,next_y, old_x,old_y
73 // 4*4 dx,ddx,dy,ddy
74 // 2 cury
75 // 1 count
76 // 1 shift
77 //
78 // some example counts 5704 curves, 1720 lines 7422 edges
79 pub struct ActiveEdge {
80 x2: i32, // 30.2
81 y2: i32, // 30.2
82 next: Option<NonNull<ActiveEdge>>,
83 slope_x: i32,
84 fullx: i32, // 16.16
85 next_x: i32, // 16.16
86 next_y: i32, // 16.16
87
88 dx: i32,
89 ddx: i32,
90 dy: i32,
91 ddy: i32,
92
93 old_x: i32,
94 old_y: i32,
95
96 shift: i32,
97 // we need to use count so that we make sure that we always line the last point up
98 // exactly. i.e. we don't have a great way to know when we're at the end implicitly.
99 count: i32,
100 winding: i8, // the direction of the edge
101 }
102
103 impl ActiveEdge {
new() -> ActiveEdge104 fn new() -> ActiveEdge {
105 ActiveEdge {
106 x2: 0,
107 y2: 0,
108 next: None,
109 slope_x: 0,
110 fullx: 0,
111 next_x: 0,
112 next_y: 0,
113 dx: 0,
114 ddx: 0,
115 dy: 0,
116 ddy: 0,
117 old_x: 0,
118 old_y: 0,
119 shift: 0,
120 count: 0,
121 winding: 0,
122 }
123 }
124
125 // we want this to inline into step_edges() to
126 // avoid the call overhead
step(&mut self, cury: i32)127 fn step(&mut self, cury: i32) {
128 // if we have a shift that means we have a curve
129 if self.shift != 0 {
130 if cury >= (self.next_y >> (16 - SAMPLE_SHIFT)) {
131 self.old_y = self.next_y;
132 self.old_x = self.next_x;
133 self.fullx = self.next_x;
134 // increment until we have a next_y that's greater
135 while self.count > 0 && (cury >= (self.next_y >> (16 - SAMPLE_SHIFT))) {
136 self.next_x += self.dx >> self.shift;
137 self.dx += self.ddx;
138 self.next_y += self.dy >> self.shift;
139 self.dy += self.ddy;
140 self.count -= 1;
141 }
142 if self.count == 0 {
143 // for the last line sgement we can
144 // just set next_y,x to the end point
145 self.next_y = self.y2 << (16 - SAMPLE_SHIFT);
146 self.next_x = self.x2 << (16 - SAMPLE_SHIFT);
147 }
148 // update slope if we're going to be using it
149 // we want to avoid dividing by 0 which can happen if we exited the loop above early
150 if (cury + 1) < self.y2 {
151 self.slope_x = div_fixed16_fixed16(self.next_x - self.old_x, self.next_y - self.old_y) >> 2;
152 }
153 }
154 self.fullx += self.slope_x;
155 } else {
156 // XXX: look into bresenham to control error here
157 self.fullx += self.slope_x;
158 }
159 }
160 }
161
162
163
164 pub struct Rasterizer {
165 edge_starts: Vec<Option<NonNull<ActiveEdge>>>,
166 width: i32,
167 height: i32,
168 cur_y: i32,
169
170 // we use this rect to track the bounds of the added edges
171 bounds_top: i32,
172 bounds_bottom: i32,
173 bounds_left: i32,
174 bounds_right: i32,
175
176 active_edges: Option<NonNull<ActiveEdge>>,
177
178 edge_arena: Arena<ActiveEdge>,
179 }
180
181 impl Rasterizer {
new(width: i32, height: i32) -> Rasterizer182 pub fn new(width: i32, height: i32) -> Rasterizer {
183 let mut edge_starts = Vec::new();
184 for _ in 0..(height * 4) {
185 edge_starts.push(None);
186 }
187 Rasterizer {
188 width: width * 4,
189 height: height * 4,
190 bounds_right: 0,
191 bounds_left: width,
192 bounds_top: height,
193 bounds_bottom: 0,
194 cur_y: 0,
195 edge_starts,
196 edge_arena: Arena::new(),
197 active_edges: None,
198 }
199 }
200 }
201
abs(mut value: i32) -> i32202 fn abs(mut value: i32) -> i32 {
203 if value < 0 {
204 value = -value;
205 }
206 return value;
207 }
208
209 // A cheap version of the "Alpha max plus beta min" algorithm (⍺=1, β=0.5)
cheap_distance(mut dx: i32, mut dy: i32) -> i32210 fn cheap_distance(mut dx: i32, mut dy: i32) -> i32 {
211 dx = abs(dx);
212 dy = abs(dy);
213 // return max + min/2
214 if dx > dy {
215 dx + (dy >> 1)
216 } else {
217 dy + (dx >> 1)
218 }
219 }
220
diff_to_shift(dx: i32, dy: i32) -> i32221 fn diff_to_shift(dx: i32, dy: i32) -> i32 {
222 // cheap calc of distance from center of p0-p2 to the center of the curve
223 let mut dist = cheap_distance(dx, dy);
224
225 // shift down dist (it is currently in dot6)
226 // down by 5 should give us 1/2 pixel accuracy (assuming our dist is accurate...)
227 // this is chosen by heuristic: make it as big as possible (to minimize segments)
228 // ... but small enough so that our curves still look smooth
229 dist = (dist + (1 << 4)) >> 5;
230
231 // each subdivision (shift value) cuts this dist (error) by 1/4
232 return (32 - ((dist as u32).leading_zeros()) as i32) >> 1;
233 }
234
235 // this metric is taken from skia
compute_curve_steps(e: &Edge) -> i32236 fn compute_curve_steps(e: &Edge) -> i32 {
237 let dx = (e.control_x << 1) - e.x1 - e.x2;
238 let dy = (e.control_y << 1) - e.y1 - e.y2;
239 let shift = diff_to_shift(dx << 4, dy << 4);
240 assert!(shift >= 0);
241 return shift;
242 }
243
244 const SAMPLE_SIZE: f32 = (1 << SAMPLE_SHIFT) as f32;
245 pub const SAMPLE_SHIFT: i32 = 2;
246
247 /* We store 1<<shift in a (signed) byte, so its maximum value is 1<<6 == 64.
248 Note that this limits the number of lines we use to approximate a curve.
249 If we need to increase this, we need to store fCurveCount in something
250 larger than int8_t.
251 */
252 const MAX_COEFF_SHIFT: i32 = 6;
253
254 // An example number of edges is 7422 but
255 // can go as high as edge count: 374640
256 // with curve count: 67680
257 impl Rasterizer {
258
259 // Overflow:
260 // cairo just does _cairo_fixed_from_double (x) which ends up having some
261 // weird behaviour around overflow because of the double to fixed conversion trick that it does.
262
263 // Fitz clips edges to the bounding box
264 #[allow(non_snake_case)]
add_edge(&mut self, mut start: Point, mut end: Point, curve: bool, control: Point)265 pub fn add_edge(&mut self, mut start: Point, mut end: Point, curve: bool, control: Point) {
266 if curve {
267 //println!("add_edge {}, {} - {}, {} - {}, {}", start.x, start.y, control.x, control.y, end.x, end.y);
268 } else {
269 //println!("add_edge {}, {} - {}, {}", start.x, start.y, end.x, end.y);
270 }
271 // order the points from top to bottom
272
273 // how do we deal with edges to the right and left of the canvas?
274 let e = self.edge_arena.alloc(ActiveEdge::new());
275 if end.y < start.y {
276 std::mem::swap(&mut start, &mut end);
277 e.winding = -1;
278 } else {
279 e.winding = 1;
280 }
281 let edge = Edge {
282 x1: (start.x * SAMPLE_SIZE) as i32,
283 y1: (start.y * SAMPLE_SIZE) as i32,
284 control_x: (control.x * SAMPLE_SIZE) as i32,
285 control_y: (control.y * SAMPLE_SIZE) as i32,
286 x2: (end.x * SAMPLE_SIZE) as i32,
287 y2: (end.y * SAMPLE_SIZE) as i32,
288 };
289 e.x2 = edge.x2;
290 e.y2 = edge.y2;
291
292 e.next = None;
293 //e.curx = e.edge.x1;
294 let mut cury = edge.y1;
295 e.fullx = edge.x1 << (16 - SAMPLE_SHIFT);
296
297 // if the edge is completely above or completely below we can drop it
298 if edge.y2 < 0 || edge.y1 >= self.height {
299 return;
300 }
301
302 // drop horizontal edges
303 if cury >= e.y2 {
304 return;
305 }
306
307 self.bounds_top = self.bounds_top.min(edge.y1 >> SAMPLE_SHIFT);
308 self.bounds_bottom = self.bounds_bottom.max((edge.y2 + 3) >> SAMPLE_SHIFT);
309
310 self.bounds_left = self.bounds_left.min(edge.x1 >> SAMPLE_SHIFT);
311 self.bounds_left = self.bounds_left.min(edge.x2 >> SAMPLE_SHIFT);
312
313 self.bounds_right = self.bounds_right.max((edge.x1 + 3) >> SAMPLE_SHIFT);
314 self.bounds_right = self.bounds_right.max((edge.x2 + 3) >> SAMPLE_SHIFT);
315
316 if curve {
317 self.bounds_left = self.bounds_left.min(edge.control_x >> SAMPLE_SHIFT);
318 self.bounds_right = self.bounds_right.max((edge.control_x + 3) >> SAMPLE_SHIFT);
319
320 // Based on Skia
321 // we'll iterate t from 0..1 (0-256)
322 // range of A is 4 times coordinate-range
323 // we can get more accuracy here by using the input points instead of the rounded versions
324 let mut A = (edge.x1 - edge.control_x - edge.control_x + edge.x2) << (15 - SAMPLE_SHIFT);
325 let mut B = edge.control_x - edge.x1;
326 //let mut C = edge.x1;
327 let mut shift = compute_curve_steps(&edge);
328
329 if shift == 0 {
330 shift = 1;
331 } else if shift > MAX_COEFF_SHIFT {
332 shift = MAX_COEFF_SHIFT;
333 }
334 e.shift = shift;
335 e.count = 1 << shift;
336 e.dx = 2 * (A >> shift) + 2 * B * (1 << (16 - SAMPLE_SHIFT));
337 e.ddx = 2 * (A >> (shift - 1));
338
339 A = (edge.y1 - edge.control_y - edge.control_y + edge.y2) << (15 - SAMPLE_SHIFT);
340 B = edge.control_y - edge.y1;
341 //C = edge.y1;
342 e.dy = 2 * (A >> shift) + 2 * B * (1 << (16 - SAMPLE_SHIFT));
343 e.ddy = 2 * (A >> (shift - 1));
344
345 // compute the first next_x,y
346 e.count -= 1;
347 e.next_x = (e.fullx) + (e.dx >> e.shift);
348 e.next_y = (cury * (1 << (16 - SAMPLE_SHIFT))) + (e.dy >> e.shift);
349 e.dx += e.ddx;
350 e.dy += e.ddy;
351
352 // skia does this part in UpdateQuad. unfortunately we duplicate it
353 while e.count > 0 && cury >= (e.next_y >> (16 - SAMPLE_SHIFT)) {
354 e.next_x += e.dx >> shift;
355 e.dx += e.ddx;
356 e.next_y += e.dy >> shift;
357 e.dy += e.ddy;
358 e.count -= 1;
359 }
360 if e.count == 0 {
361 e.next_y = edge.y2 << (16 - SAMPLE_SHIFT);
362 e.next_x = edge.x2 << (16 - SAMPLE_SHIFT);
363 }
364 e.slope_x = ((e.next_x - (e.fullx)) << 0) / ((e.next_y - (cury << (16 - SAMPLE_SHIFT))) >> 14);
365 } else {
366 e.shift = 0;
367 e.slope_x = ((edge.x2 - edge.x1) * (1 << (16 - SAMPLE_SHIFT))) / (edge.y2 - edge.y1);
368 }
369
370 if cury < 0 {
371 // XXX: we could compute an intersection with the top and bottom so we don't need to step them into view
372 // for curves we can just step them into place.
373 while cury < 0 {
374 e.step(cury);
375 cury += 1;
376 }
377
378 // cury was adjusted so check again for horizontal edges
379 if cury >= e.y2 {
380 return;
381 }
382 }
383
384 // add to the begining of the edge start list
385 // if edges are added from left to right
386 // the'll be in this list from right to left
387 // this works out later during insertion
388 e.next = self.edge_starts[cury as usize];
389 self.edge_starts[cury as usize] = Some(NonNull::from(e));
390 }
391
step_edges(&mut self)392 fn step_edges(&mut self) {
393 let mut prev_ptr = &mut self.active_edges as *mut _;
394 let mut edge = self.active_edges;
395 let cury = self.cur_y; // avoid any aliasing problems
396 while let Some(mut e_ptr) = edge {
397 let e = unsafe { e_ptr.as_mut() };
398 e.step(cury);
399 // avoid aliasing between edge->next and prev_ptr so that we can reuse next
400 let next = e.next;
401 // remove any finished edges
402 if (cury + 1) >= e.y2 {
403 // remove from active list
404 unsafe { *prev_ptr = next };
405 } else {
406 prev_ptr = &mut e.next;
407 }
408 edge = next;
409 }
410 }
411 /*
412 int comparisons;
413 static inline void dump_edges(ActiveEdge *e)
414 {
415 while (e) {
416 printf("%d ", e.fullx);
417 e = e.next;
418 }
419 printf("\n");
420 }
421 */
422 // Insertion sort the new edges into the active list
423 // The new edges could be showing up at any x coordinate
424 // but existing active edges will be sorted.
425 //
426 // Merge in the new edges. Since both lists are sorted we can do
427 // this in a single pass.
428 // Note: we could do just O(1) append the list of new active edges
429 // to the existing active edge list, but then we'd have to sort
430 // the entire resulting list
insert_starting_edges(&mut self)431 fn insert_starting_edges(&mut self) {
432 let mut new_edges: Option<NonNull<ActiveEdge>> = None;
433 let mut edge = self.edge_starts[self.cur_y as usize];
434 // insertion sort all of the new edges
435 while let Some(mut e_ptr) = edge {
436 let e = unsafe { e_ptr.as_mut() };
437 let mut prev_ptr = &mut new_edges as *mut _;
438 let mut new = new_edges;
439 while let Some(mut new_ptr) = new {
440 let a = unsafe { new_ptr.as_mut() };
441 if e.fullx <= a.fullx {
442 break;
443 }
444 // comparisons++;
445 prev_ptr = &mut a.next;
446 new = a.next;
447 }
448 edge = e.next;
449 e.next = new;
450 unsafe { *prev_ptr = Some(e_ptr) };
451 }
452
453 // merge the sorted new_edges into active_edges
454 let mut prev_ptr = &mut self.active_edges as *mut _;
455 let mut active = self.active_edges;
456 let mut edge = new_edges;
457 while let Some(mut e_ptr) = edge {
458 let e = unsafe { e_ptr.as_mut() };
459 while let Some(mut a_ptr) = active {
460 let a = unsafe { a_ptr.as_mut() };
461 if e.fullx <= a.fullx {
462 break;
463 }
464
465 // comparisons++;
466 prev_ptr = &mut a.next;
467 active = a.next;
468 }
469 edge = e.next;
470 e.next = active;
471 let next_prev_ptr = &mut e.next as *mut _;
472 unsafe { *prev_ptr = Some(e_ptr) };
473 prev_ptr = next_prev_ptr;
474 }
475 }
476
477 // Skia does stepping and scanning of edges in a single
478 // pass over the edge list.
scan_edges(&mut self, blitter: &mut dyn RasterBlitter, winding_mode: Winding)479 fn scan_edges(&mut self, blitter: &mut dyn RasterBlitter, winding_mode: Winding) {
480 let mut edge = self.active_edges;
481 let mut winding = 0;
482
483 // handle edges that begin to the left of the bitmap
484 while let Some(mut e_ptr) = edge {
485 let e = unsafe { e_ptr.as_mut() };
486 if e.fullx >= 0 {
487 break;
488 }
489 winding += e.winding as i32;
490 edge = e.next;
491 }
492
493 let mut prevx = 0;
494 while let Some(mut e_ptr) = edge {
495 let e = unsafe { e_ptr.as_mut() };
496
497 let inside = match winding_mode {
498 Winding::EvenOdd => winding & 1 != 0,
499 Winding::NonZero => winding != 0,
500 };
501
502 if inside {
503 blitter.blit_span(
504 self.cur_y,
505 (prevx + (1 << (15 - SAMPLE_SHIFT))) >> (16 - SAMPLE_SHIFT),
506 (e.fullx + (1 << (15 - SAMPLE_SHIFT))) >> (16 - SAMPLE_SHIFT),
507 );
508 }
509
510 if (e.fullx >> (16 - SAMPLE_SHIFT)) >= self.width {
511 break;
512 }
513 winding += e.winding as i32;
514 prevx = e.fullx;
515 edge = e.next;
516 }
517
518 // we don't need to worry about any edges beyond width
519 }
520
521 // You may have heard that one should never use a bubble sort.
522 // However in our situation a bubble sort is actually a good choice.
523 // The input list will be mostly sorted except for a couple of lines
524 // that have need to be swapped. Further it is common that our edges are
525 // already sorted and bubble sort lets us avoid doing any memory writes.
526
527 // Some statistics from using a bubble sort on an
528 // example scene. You can see that bubble sort does
529 // noticably better than O (n lg n).
530 // summary(edges*bubble_sort_iterations)
531 // Min. 1st Qu. Median Mean 3rd Qu. Max.
532 // 0.0 9.0 69.0 131.5 206.0 1278.0
533 // summary(edges*log2(edges))
534 // Min. 1st Qu. Median Mean 3rd Qu. Max. NA's
535 // 0.00 28.53 347.10 427.60 787.20 1286.00 2.00
sort_edges(&mut self)536 fn sort_edges(&mut self) {
537 if self.active_edges.is_none() {
538 return;
539 }
540
541 let mut swapped;
542 loop {
543 swapped = false;
544 let mut edge = self.active_edges.unwrap();
545 let mut next_edge = unsafe { edge.as_mut() }.next;
546 let mut prev = &mut self.active_edges as *mut _;
547 while let Some(mut next_ptr) = next_edge {
548 let next = unsafe { next_ptr.as_mut() };
549 if unsafe { edge.as_mut() }.fullx > next.fullx {
550 // swap edge and next
551 unsafe { edge.as_mut() }.next = next.next;
552 next.next = Some(edge);
553 unsafe { (*prev) = Some(next_ptr) };
554 swapped = true;
555 }
556 prev = (&mut unsafe { edge.as_mut() }.next) as *mut _;
557 edge = next_ptr;
558 next_edge = unsafe { edge.as_mut() }.next;
559 }
560 if !swapped {
561 break;
562 }
563 }
564 }
565
rasterize(&mut self, blitter: &mut dyn RasterBlitter, winding_mode: Winding)566 pub fn rasterize(&mut self, blitter: &mut dyn RasterBlitter, winding_mode: Winding) {
567 self.cur_y = 0;
568 while self.cur_y < self.height {
569 // we do 4x4 super-sampling so we need
570 // to scan 4 times before painting a line of pixels
571 for _ in 0..4 {
572 // insert the new edges into the sorted list
573 self.insert_starting_edges();
574 // scan over the edge list producing a list of spans
575 self.scan_edges(blitter, winding_mode);
576 // step all of the edges to the next scanline
577 // dropping the ones that end
578 self.step_edges();
579 // sort the remaning edges
580 self.sort_edges();
581 self.cur_y += 1;
582 }
583 }
584 }
585
get_bounds(&self) -> IntRect586 pub fn get_bounds(&self) -> IntRect {
587 intrect(self.bounds_left.max(0),
588 self.bounds_top.max(0),
589 self.bounds_right.min(self.width >> SAMPLE_SHIFT),
590 self.bounds_bottom.min(self.height >> SAMPLE_SHIFT))
591 }
592
reset(&mut self)593 pub fn reset(&mut self) {
594 self.active_edges = None;
595 for e in &mut self.edge_starts {
596 *e = None;
597 }
598 self.edge_arena = Arena::new();
599 self.bounds_bottom = 0;
600 self.bounds_right = 0;
601 self.bounds_top = self.height >> SAMPLE_SHIFT;
602 self.bounds_left = self.width >> SAMPLE_SHIFT;
603 }
604 }
605