aboutsummaryrefslogtreecommitdiff
path: root/src/rasterizer
diff options
context:
space:
mode:
Diffstat (limited to 'src/rasterizer')
-rw-r--r--src/rasterizer/circle.rs342
-rw-r--r--src/rasterizer/line.rs123
-rw-r--r--src/rasterizer/mod.rs32
-rw-r--r--src/rasterizer/path.rs115
-rw-r--r--src/rasterizer/polygon.rs242
-rw-r--r--src/rasterizer/rect.rs57
6 files changed, 911 insertions, 0 deletions
diff --git a/src/rasterizer/circle.rs b/src/rasterizer/circle.rs
new file mode 100644
index 0000000..779f095
--- /dev/null
+++ b/src/rasterizer/circle.rs
@@ -0,0 +1,342 @@
+use crate::{BackendCoord, BackendStyle, DrawingBackend, DrawingErrorKind};
+
+fn draw_part_a<
+ B: DrawingBackend,
+ Draw: FnMut(i32, (f64, f64)) -> Result<(), DrawingErrorKind<B::ErrorType>>,
+>(
+ height: f64,
+ radius: u32,
+ mut draw: Draw,
+) -> Result<(), DrawingErrorKind<B::ErrorType>> {
+ let half_width = (radius as f64 * radius as f64
+ - (radius as f64 - height) * (radius as f64 - height))
+ .sqrt();
+
+ let x0 = (-half_width).ceil() as i32;
+ let x1 = half_width.floor() as i32;
+
+ let y0 = (radius as f64 - height).ceil();
+
+ for x in x0..=x1 {
+ let y1 = (radius as f64 * radius as f64 - x as f64 * x as f64).sqrt();
+ check_result!(draw(x, (y0, y1)));
+ }
+
+ Ok(())
+}
+
+fn draw_part_b<
+ B: DrawingBackend,
+ Draw: FnMut(i32, (f64, f64)) -> Result<(), DrawingErrorKind<B::ErrorType>>,
+>(
+ from: f64,
+ size: f64,
+ mut draw: Draw,
+) -> Result<(), DrawingErrorKind<B::ErrorType>> {
+ let from = from.floor();
+ for x in (from - size).floor() as i32..=from as i32 {
+ check_result!(draw(x, (-x as f64, x as f64)));
+ }
+ Ok(())
+}
+
+fn draw_part_c<
+ B: DrawingBackend,
+ Draw: FnMut(i32, (f64, f64)) -> Result<(), DrawingErrorKind<B::ErrorType>>,
+>(
+ r: i32,
+ r_limit: i32,
+ mut draw: Draw,
+) -> Result<(), DrawingErrorKind<B::ErrorType>> {
+ let half_size = r as f64 / (2f64).sqrt();
+
+ let (x0, x1) = ((-half_size).ceil() as i32, half_size.floor() as i32);
+
+ for x in x0..x1 {
+ let outter_y0 = ((r_limit as f64) * (r_limit as f64) - x as f64 * x as f64).sqrt();
+ let inner_y0 = r as f64 - 1.0;
+ let mut y1 = outter_y0.min(inner_y0);
+ let y0 = ((r as f64) * (r as f64) - x as f64 * x as f64).sqrt();
+
+ if y0 > y1 {
+ y1 = y0.ceil();
+ if y1 >= r as f64 {
+ continue;
+ }
+ }
+
+ check_result!(draw(x, (y0, y1)));
+ }
+
+ for x in x1 + 1..r {
+ let outter_y0 = ((r_limit as f64) * (r_limit as f64) - x as f64 * x as f64).sqrt();
+ let inner_y0 = r as f64 - 1.0;
+ let y0 = outter_y0.min(inner_y0);
+ let y1 = x as f64;
+
+ if y1 < y0 {
+ check_result!(draw(x, (y0, y1 + 1.0)));
+ check_result!(draw(-x, (y0, y1 + 1.0)));
+ }
+ }
+
+ Ok(())
+}
+
+fn draw_sweep_line<B: DrawingBackend, S: BackendStyle>(
+ b: &mut B,
+ style: &S,
+ (x0, y0): BackendCoord,
+ (dx, dy): (i32, i32),
+ p0: i32,
+ (s, e): (f64, f64),
+) -> Result<(), DrawingErrorKind<B::ErrorType>> {
+ let mut s = if dx < 0 || dy < 0 { -s } else { s };
+ let mut e = if dx < 0 || dy < 0 { -e } else { e };
+ if s > e {
+ std::mem::swap(&mut s, &mut e);
+ }
+
+ let vs = s.ceil() - s;
+ let ve = e - e.floor();
+
+ if dx == 0 {
+ check_result!(b.draw_line(
+ (p0 + x0, s.ceil() as i32 + y0),
+ (p0 + x0, e.floor() as i32 + y0),
+ &style.color()
+ ));
+ check_result!(b.draw_pixel((p0 + x0, s.ceil() as i32 + y0 - 1), style.color().mix(vs)));
+ check_result!(b.draw_pixel((p0 + x0, e.floor() as i32 + y0 + 1), style.color().mix(ve)));
+ } else {
+ check_result!(b.draw_line(
+ (s.ceil() as i32 + x0, p0 + y0),
+ (e.floor() as i32 + x0, p0 + y0),
+ &style.color()
+ ));
+ check_result!(b.draw_pixel((s.ceil() as i32 + x0 - 1, p0 + y0), style.color().mix(vs)));
+ check_result!(b.draw_pixel((e.floor() as i32 + x0 + 1, p0 + y0), style.color().mix(ve)));
+ }
+
+ Ok(())
+}
+
+fn draw_annulus<B: DrawingBackend, S: BackendStyle>(
+ b: &mut B,
+ center: BackendCoord,
+ radius: (u32, u32),
+ style: &S,
+) -> Result<(), DrawingErrorKind<B::ErrorType>> {
+ let a0 = ((radius.0 - radius.1) as f64).min(radius.0 as f64 * (1.0 - 1.0 / (2f64).sqrt()));
+ let a1 = (radius.0 as f64 - a0 - radius.1 as f64).max(0.0);
+
+ check_result!(draw_part_a::<B, _>(a0, radius.0, |p, r| draw_sweep_line(
+ b,
+ style,
+ center,
+ (0, 1),
+ p,
+ r
+ )));
+ check_result!(draw_part_a::<B, _>(a0, radius.0, |p, r| draw_sweep_line(
+ b,
+ style,
+ center,
+ (0, -1),
+ p,
+ r
+ )));
+ check_result!(draw_part_a::<B, _>(a0, radius.0, |p, r| draw_sweep_line(
+ b,
+ style,
+ center,
+ (1, 0),
+ p,
+ r
+ )));
+ check_result!(draw_part_a::<B, _>(a0, radius.0, |p, r| draw_sweep_line(
+ b,
+ style,
+ center,
+ (-1, 0),
+ p,
+ r
+ )));
+
+ if a1 > 0.0 {
+ check_result!(draw_part_b::<B, _>(
+ radius.0 as f64 - a0,
+ a1.floor(),
+ |h, (f, t)| {
+ let h = h as i32;
+ let f = f as i32;
+ let t = t as i32;
+ check_result!(b.draw_line(
+ (center.0 + h, center.1 + f),
+ (center.0 + h, center.1 + t),
+ &style.color()
+ ));
+ check_result!(b.draw_line(
+ (center.0 - h, center.1 + f),
+ (center.0 - h, center.1 + t),
+ &style.color()
+ ));
+
+ check_result!(b.draw_line(
+ (center.0 + f + 1, center.1 + h),
+ (center.0 + t - 1, center.1 + h),
+ &style.color()
+ ));
+ check_result!(b.draw_line(
+ (center.0 + f + 1, center.1 - h),
+ (center.0 + t - 1, center.1 - h),
+ &style.color()
+ ));
+
+ Ok(())
+ }
+ ));
+ }
+
+ check_result!(draw_part_c::<B, _>(
+ radius.1 as i32,
+ radius.0 as i32,
+ |p, r| draw_sweep_line(b, style, center, (0, 1), p, r)
+ ));
+ check_result!(draw_part_c::<B, _>(
+ radius.1 as i32,
+ radius.0 as i32,
+ |p, r| draw_sweep_line(b, style, center, (0, -1), p, r)
+ ));
+ check_result!(draw_part_c::<B, _>(
+ radius.1 as i32,
+ radius.0 as i32,
+ |p, r| draw_sweep_line(b, style, center, (1, 0), p, r)
+ ));
+ check_result!(draw_part_c::<B, _>(
+ radius.1 as i32,
+ radius.0 as i32,
+ |p, r| draw_sweep_line(b, style, center, (-1, 0), p, r)
+ ));
+
+ let d_inner = ((radius.1 as f64) / (2f64).sqrt()) as i32;
+ let d_outter = (((radius.0 as f64) / (2f64).sqrt()) as i32).min(radius.1 as i32 - 1);
+ let d_outter_actually = (radius.1 as i32).min(
+ (radius.0 as f64 * radius.0 as f64 - radius.1 as f64 * radius.1 as f64 / 2.0)
+ .sqrt()
+ .ceil() as i32,
+ );
+
+ check_result!(b.draw_line(
+ (center.0 - d_inner, center.1 - d_inner),
+ (center.0 - d_outter, center.1 - d_outter),
+ &style.color()
+ ));
+ check_result!(b.draw_line(
+ (center.0 + d_inner, center.1 - d_inner),
+ (center.0 + d_outter, center.1 - d_outter),
+ &style.color()
+ ));
+ check_result!(b.draw_line(
+ (center.0 - d_inner, center.1 + d_inner),
+ (center.0 - d_outter, center.1 + d_outter),
+ &style.color()
+ ));
+ check_result!(b.draw_line(
+ (center.0 + d_inner, center.1 + d_inner),
+ (center.0 + d_outter, center.1 + d_outter),
+ &style.color()
+ ));
+
+ check_result!(b.draw_line(
+ (center.0 - d_inner, center.1 + d_inner),
+ (center.0 - d_outter_actually, center.1 + d_inner),
+ &style.color()
+ ));
+ check_result!(b.draw_line(
+ (center.0 + d_inner, center.1 - d_inner),
+ (center.0 + d_inner, center.1 - d_outter_actually),
+ &style.color()
+ ));
+ check_result!(b.draw_line(
+ (center.0 + d_inner, center.1 + d_inner),
+ (center.0 + d_inner, center.1 + d_outter_actually),
+ &style.color()
+ ));
+ check_result!(b.draw_line(
+ (center.0 + d_inner, center.1 + d_inner),
+ (center.0 + d_outter_actually, center.1 + d_inner),
+ &style.color()
+ ));
+
+ Ok(())
+}
+
+pub fn draw_circle<B: DrawingBackend, S: BackendStyle>(
+ b: &mut B,
+ center: BackendCoord,
+ mut radius: u32,
+ style: &S,
+ mut fill: bool,
+) -> Result<(), DrawingErrorKind<B::ErrorType>> {
+ if style.color().alpha == 0.0 {
+ return Ok(());
+ }
+
+ if !fill && style.stroke_width() != 1 {
+ let inner_radius = radius - (style.stroke_width() / 2).min(radius);
+ radius += style.stroke_width() / 2;
+ if inner_radius > 0 {
+ return draw_annulus(b, center, (radius, inner_radius), style);
+ } else {
+ fill = true;
+ }
+ }
+
+ let min = (f64::from(radius) * (1.0 - (2f64).sqrt() / 2.0)).ceil() as i32;
+ let max = (f64::from(radius) * (1.0 + (2f64).sqrt() / 2.0)).floor() as i32;
+
+ let range = min..=max;
+
+ let (up, down) = (
+ range.start() + center.1 - radius as i32,
+ range.end() + center.1 - radius as i32,
+ );
+
+ for dy in range {
+ let dy = dy - radius as i32;
+ let y = center.1 + dy;
+
+ let lx = (f64::from(radius) * f64::from(radius)
+ - (f64::from(dy) * f64::from(dy)).max(1e-5))
+ .sqrt();
+
+ let left = center.0 - lx.floor() as i32;
+ let right = center.0 + lx.floor() as i32;
+
+ let v = lx - lx.floor();
+
+ let x = center.0 + dy;
+ let top = center.1 - lx.floor() as i32;
+ let bottom = center.1 + lx.floor() as i32;
+
+ if fill {
+ check_result!(b.draw_line((left, y), (right, y), &style.color()));
+ check_result!(b.draw_line((x, top), (x, up), &style.color()));
+ check_result!(b.draw_line((x, down), (x, bottom), &style.color()));
+ } else {
+ check_result!(b.draw_pixel((left, y), style.color().mix(1.0 - v)));
+ check_result!(b.draw_pixel((right, y), style.color().mix(1.0 - v)));
+
+ check_result!(b.draw_pixel((x, top), style.color().mix(1.0 - v)));
+ check_result!(b.draw_pixel((x, bottom), style.color().mix(1.0 - v)));
+ }
+
+ check_result!(b.draw_pixel((left - 1, y), style.color().mix(v)));
+ check_result!(b.draw_pixel((right + 1, y), style.color().mix(v)));
+ check_result!(b.draw_pixel((x, top - 1), style.color().mix(v)));
+ check_result!(b.draw_pixel((x, bottom + 1), style.color().mix(v)));
+ }
+
+ Ok(())
+}
diff --git a/src/rasterizer/line.rs b/src/rasterizer/line.rs
new file mode 100644
index 0000000..0f24b0a
--- /dev/null
+++ b/src/rasterizer/line.rs
@@ -0,0 +1,123 @@
+use crate::{BackendCoord, BackendStyle, DrawingBackend, DrawingErrorKind};
+
+pub fn draw_line<DB: DrawingBackend, S: BackendStyle>(
+ back: &mut DB,
+ mut from: BackendCoord,
+ mut to: BackendCoord,
+ style: &S,
+) -> Result<(), DrawingErrorKind<DB::ErrorType>> {
+ if style.color().alpha == 0.0 {
+ return Ok(());
+ }
+
+ if style.stroke_width() != 1 {
+ // If the line is wider than 1px, then we need to make it a polygon
+ let v = (i64::from(to.0 - from.0), i64::from(to.1 - from.1));
+ let l = ((v.0 * v.0 + v.1 * v.1) as f64).sqrt();
+
+ if l < 1e-5 {
+ return Ok(());
+ }
+
+ let v = (v.0 as f64 / l, v.1 as f64 / l);
+
+ let r = f64::from(style.stroke_width()) / 2.0;
+ let mut trans = [(v.1 * r, -v.0 * r), (-v.1 * r, v.0 * r)];
+ let mut vertices = vec![];
+
+ for point in [from, to].iter() {
+ for t in trans.iter() {
+ vertices.push((
+ (f64::from(point.0) + t.0) as i32,
+ (f64::from(point.1) + t.1) as i32,
+ ))
+ }
+
+ trans.swap(0, 1);
+ }
+
+ return back.fill_polygon(vertices, style);
+ }
+
+ if from.0 == to.0 {
+ if from.1 > to.1 {
+ std::mem::swap(&mut from, &mut to);
+ }
+ for y in from.1..=to.1 {
+ check_result!(back.draw_pixel((from.0, y), style.color()));
+ }
+ return Ok(());
+ }
+
+ if from.1 == to.1 {
+ if from.0 > to.0 {
+ std::mem::swap(&mut from, &mut to);
+ }
+ for x in from.0..=to.0 {
+ check_result!(back.draw_pixel((x, from.1), style.color()));
+ }
+ return Ok(());
+ }
+
+ let steep = (from.0 - to.0).abs() < (from.1 - to.1).abs();
+
+ if steep {
+ from = (from.1, from.0);
+ to = (to.1, to.0);
+ }
+
+ let (from, to) = if from.0 > to.0 {
+ (to, from)
+ } else {
+ (from, to)
+ };
+
+ let mut size_limit = back.get_size();
+
+ if steep {
+ size_limit = (size_limit.1, size_limit.0);
+ }
+
+ let grad = f64::from(to.1 - from.1) / f64::from(to.0 - from.0);
+
+ let mut put_pixel = |(x, y): BackendCoord, b: f64| {
+ if steep {
+ back.draw_pixel((y, x), style.color().mix(b))
+ } else {
+ back.draw_pixel((x, y), style.color().mix(b))
+ }
+ };
+
+ let y_step_limit =
+ (f64::from(to.1.min(size_limit.1 as i32 - 1).max(0) - from.1) / grad).floor() as i32;
+
+ let batch_start = (f64::from(from.1.min(size_limit.1 as i32 - 2).max(0) - from.1) / grad)
+ .abs()
+ .ceil() as i32
+ + from.0;
+
+ let batch_limit =
+ to.0.min(size_limit.0 as i32 - 2)
+ .min(from.0 + y_step_limit - 1);
+
+ let mut y = f64::from(from.1) + f64::from(batch_start - from.0) * grad;
+
+ for x in batch_start..=batch_limit {
+ check_result!(put_pixel((x, y as i32), 1.0 + y.floor() - y));
+ check_result!(put_pixel((x, y as i32 + 1), y - y.floor()));
+
+ y += grad;
+ }
+
+ if to.0 >= batch_limit + 1 && y < f64::from(to.1) {
+ let x = batch_limit as i32 + 1;
+ if 1.0 + y.floor() - y > 1e-5 {
+ check_result!(put_pixel((x, y as i32), 1.0 + y.floor() - y));
+ }
+ if y - y.floor() > 1e-5 && y + 1.0 < f64::from(to.1) {
+ check_result!(put_pixel((x, y as i32 + 1), y - y.floor()));
+ }
+ }
+
+ Ok(())
+}
diff --git a/src/rasterizer/mod.rs b/src/rasterizer/mod.rs
new file mode 100644
index 0000000..11835f4
--- /dev/null
+++ b/src/rasterizer/mod.rs
@@ -0,0 +1,32 @@
+/*! # The built-in rasterizers.
+
+ Plotters make a minimal backend ability assumption - which is drawing a pixel on
+ backend. And this is the rasterizer that utilize this minimal ability to build a
+ fully functioning backend.
+
+*/
+
+// TODO: ? operator is very slow. See issue #58 for details
+macro_rules! check_result {
+ ($e:expr) => {
+ let result = $e;
+ if result.is_err() {
+ return result;
+ }
+ };
+}
+
+mod line;
+pub use line::draw_line;
+
+mod rect;
+pub use rect::draw_rect;
+
+mod circle;
+pub use circle::draw_circle;
+
+mod polygon;
+pub use polygon::fill_polygon;
+
+mod path;
+pub use path::polygonize;
diff --git a/src/rasterizer/path.rs b/src/rasterizer/path.rs
new file mode 100644
index 0000000..b2db356
--- /dev/null
+++ b/src/rasterizer/path.rs
@@ -0,0 +1,115 @@
+use crate::BackendCoord;
+
+fn get_dir_vector(from: BackendCoord, to: BackendCoord, flag: bool) -> ((f64, f64), (f64, f64)) {
+ let v = (i64::from(to.0 - from.0), i64::from(to.1 - from.1));
+ let l = ((v.0 * v.0 + v.1 * v.1) as f64).sqrt();
+
+ let v = (v.0 as f64 / l, v.1 as f64 / l);
+
+ if flag {
+ (v, (v.1, -v.0))
+ } else {
+ (v, (-v.1, v.0))
+ }
+}
+
+fn compute_polygon_vertex(triple: &[BackendCoord; 3], d: f64) -> BackendCoord {
+ let (a_t, a_n) = get_dir_vector(triple[0], triple[1], false);
+ let (b_t, b_n) = get_dir_vector(triple[2], triple[1], true);
+
+ let a_p = (
+ f64::from(triple[1].0) + d * a_n.0,
+ f64::from(triple[1].1) + d * a_n.1,
+ );
+ let b_p = (
+ f64::from(triple[1].0) + d * b_n.0,
+ f64::from(triple[1].1) + d * b_n.1,
+ );
+
+ // u * a_t + a_p = v * b_t + b_p
+ // u * a_t.0 - v * b_t.0 = b_p.0 - a_p.0
+ // u * a_t.1 - v * b_t.1 = b_p.1 - a_p.1
+ if a_p.0 as i32 == b_p.0 as i32 && a_p.1 as i32 == b_p.1 as i32 {
+ return (a_p.0 as i32, a_p.1 as i32);
+ }
+
+ let a0 = a_t.0;
+ let b0 = -b_t.0;
+ let c0 = b_p.0 - a_p.0;
+ let a1 = a_t.1;
+ let b1 = -b_t.1;
+ let c1 = b_p.1 - a_p.1;
+
+ // This is the coner case that
+ if (a0 * b1 - a1 * b0).abs() < 1e-10 {
+ return (a_p.0 as i32, a_p.1 as i32);
+ }
+
+ let u = (c0 * b1 - c1 * b0) / (a0 * b1 - a1 * b0);
+
+ let x = a_p.0 + u * a_t.0;
+ let y = a_p.1 + u * a_t.1;
+
+ (x.round() as i32, y.round() as i32)
+}
+
+fn traverse_vertices<'a>(
+ mut vertices: impl Iterator<Item = &'a BackendCoord>,
+ width: u32,
+ mut op: impl FnMut(BackendCoord),
+) {
+ let mut a = vertices.next().unwrap();
+ let mut b = vertices.next().unwrap();
+
+ while a == b {
+ a = b;
+ if let Some(new_b) = vertices.next() {
+ b = new_b;
+ } else {
+ return;
+ }
+ }
+
+ let (_, n) = get_dir_vector(*a, *b, false);
+
+ op((
+ (f64::from(a.0) + n.0 * f64::from(width) / 2.0).round() as i32,
+ (f64::from(a.1) + n.1 * f64::from(width) / 2.0).round() as i32,
+ ));
+
+ let mut recent = [(0, 0), *a, *b];
+
+ for p in vertices {
+ if *p == recent[2] {
+ continue;
+ }
+ recent.swap(0, 1);
+ recent.swap(1, 2);
+ recent[2] = *p;
+ op(compute_polygon_vertex(&recent, f64::from(width) / 2.0));
+ }
+
+ let b = recent[1];
+ let a = recent[2];
+
+ let (_, n) = get_dir_vector(a, b, true);
+
+ op((
+ (f64::from(a.0) + n.0 * f64::from(width) / 2.0).round() as i32,
+ (f64::from(a.1) + n.1 * f64::from(width) / 2.0).round() as i32,
+ ));
+}
+
+/// Covert a path with >1px stroke width into polygon.
+pub fn polygonize(vertices: &[BackendCoord], stroke_width: u32) -> Vec<BackendCoord> {
+ if vertices.len() < 2 {
+ return vec![];
+ }
+
+ let mut ret = vec![];
+
+ traverse_vertices(vertices.iter(), stroke_width, |v| ret.push(v));
+ traverse_vertices(vertices.iter().rev(), stroke_width, |v| ret.push(v));
+
+ ret
+}
diff --git a/src/rasterizer/polygon.rs b/src/rasterizer/polygon.rs
new file mode 100644
index 0000000..ce33c5c
--- /dev/null
+++ b/src/rasterizer/polygon.rs
@@ -0,0 +1,242 @@
+use crate::{BackendCoord, BackendStyle, DrawingBackend, DrawingErrorKind};
+
+use std::cmp::{Ord, Ordering, PartialOrd};
+
+#[derive(Clone, Debug)]
+struct Edge {
+ epoch: u32,
+ total_epoch: u32,
+ slave_begin: i32,
+ slave_end: i32,
+}
+
+impl Edge {
+ fn horizontal_sweep(mut from: BackendCoord, mut to: BackendCoord) -> Option<Edge> {
+ if from.0 == to.0 {
+ return None;
+ }
+
+ if from.0 > to.0 {
+ std::mem::swap(&mut from, &mut to);
+ }
+
+ Some(Edge {
+ epoch: 0,
+ total_epoch: (to.0 - from.0) as u32,
+ slave_begin: from.1,
+ slave_end: to.1,
+ })
+ }
+
+ fn vertical_sweep(from: BackendCoord, to: BackendCoord) -> Option<Edge> {
+ Edge::horizontal_sweep((from.1, from.0), (to.1, to.0))
+ }
+
+ fn get_master_pos(&self) -> i32 {
+ (self.total_epoch - self.epoch) as i32
+ }
+
+ fn inc_epoch(&mut self) {
+ self.epoch += 1;
+ }
+
+ fn get_slave_pos(&self) -> f64 {
+ f64::from(self.slave_begin)
+ + (i64::from(self.slave_end - self.slave_begin) * i64::from(self.epoch)) as f64
+ / f64::from(self.total_epoch)
+ }
+}
+
+impl PartialOrd for Edge {
+ fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
+ self.get_slave_pos().partial_cmp(&other.get_slave_pos())
+ }
+}
+
+impl PartialEq for Edge {
+ fn eq(&self, other: &Self) -> bool {
+ self.get_slave_pos() == other.get_slave_pos()
+ }
+}
+
+impl Eq for Edge {}
+
+impl Ord for Edge {
+ fn cmp(&self, other: &Self) -> Ordering {
+ self.get_slave_pos()
+ .partial_cmp(&other.get_slave_pos())
+ .unwrap()
+ }
+}
+
+pub fn fill_polygon<DB: DrawingBackend, S: BackendStyle>(
+ back: &mut DB,
+ vertices: &[BackendCoord],
+ style: &S,
+) -> Result<(), DrawingErrorKind<DB::ErrorType>> {
+ if let Some((x_span, y_span)) =
+ vertices
+ .iter()
+ .fold(None, |res: Option<((i32, i32), (i32, i32))>, (x, y)| {
+ Some(
+ res.map(|((min_x, max_x), (min_y, max_y))| {
+ (
+ (min_x.min(*x), max_x.max(*x)),
+ (min_y.min(*y), max_y.max(*y)),
+ )
+ })
+ .unwrap_or(((*x, *x), (*y, *y))),
+ )
+ })
+ {
+ // First of all, let's handle the case that all the points is in a same vertical or
+ // horizontal line
+ if x_span.0 == x_span.1 || y_span.0 == y_span.1 {
+ return back.draw_line((x_span.0, y_span.0), (x_span.1, y_span.1), style);
+ }
+
+ let horizontal_sweep = x_span.1 - x_span.0 > y_span.1 - y_span.0;
+
+ let mut edges: Vec<_> = vertices
+ .iter()
+ .zip(vertices.iter().skip(1))
+ .map(|(a, b)| (*a, *b))
+ .collect();
+ edges.push((vertices[vertices.len() - 1], vertices[0]));
+ edges.sort_by_key(|((x1, y1), (x2, y2))| {
+ if horizontal_sweep {
+ *x1.min(x2)
+ } else {
+ *y1.min(y2)
+ }
+ });
+
+ for edge in &mut edges.iter_mut() {
+ if horizontal_sweep {
+ if (edge.0).0 > (edge.1).0 {
+ std::mem::swap(&mut edge.0, &mut edge.1);
+ }
+ } else if (edge.0).1 > (edge.1).1 {
+ std::mem::swap(&mut edge.0, &mut edge.1);
+ }
+ }
+
+ let (low, high) = if horizontal_sweep { x_span } else { y_span };
+
+ let mut idx = 0;
+
+ let mut active_edge: Vec<Edge> = vec![];
+
+ for sweep_line in low..=high {
+ let mut new_vec = vec![];
+
+ for mut e in active_edge {
+ if e.get_master_pos() > 0 {
+ e.inc_epoch();
+ new_vec.push(e);
+ }
+ }
+
+ active_edge = new_vec;
+
+ loop {
+ if idx >= edges.len() {
+ break;
+ }
+ let line = if horizontal_sweep {
+ (edges[idx].0).0
+ } else {
+ (edges[idx].0).1
+ };
+ if line > sweep_line {
+ break;
+ }
+
+ let edge_obj = if horizontal_sweep {
+ Edge::horizontal_sweep(edges[idx].0, edges[idx].1)
+ } else {
+ Edge::vertical_sweep(edges[idx].0, edges[idx].1)
+ };
+
+ if let Some(edge_obj) = edge_obj {
+ active_edge.push(edge_obj);
+ }
+
+ idx += 1;
+ }
+
+ active_edge.sort();
+
+ let mut first = None;
+ let mut second = None;
+
+ for edge in active_edge.iter() {
+ if first.is_none() {
+ first = Some(edge.clone())
+ } else if second.is_none() {
+ second = Some(edge.clone())
+ }
+
+ if let Some(a) = first.clone() {
+ if let Some(b) = second.clone() {
+ if a.get_master_pos() == 0 && b.get_master_pos() != 0 {
+ first = Some(b);
+ second = None;
+ continue;
+ }
+
+ if a.get_master_pos() != 0 && b.get_master_pos() == 0 {
+ first = Some(a);
+ second = None;
+ continue;
+ }
+
+ let from = a.get_slave_pos();
+ let to = b.get_slave_pos();
+
+ if a.get_master_pos() == 0 && b.get_master_pos() == 0 && to - from > 1.0 {
+ first = None;
+ second = None;
+ continue;
+ }
+
+ if horizontal_sweep {
+ check_result!(back.draw_line(
+ (sweep_line, from.ceil() as i32),
+ (sweep_line, to.floor() as i32),
+ &style.color(),
+ ));
+ check_result!(back.draw_pixel(
+ (sweep_line, from.floor() as i32),
+ style.color().mix(from.ceil() - from),
+ ));
+ check_result!(back.draw_pixel(
+ (sweep_line, to.ceil() as i32),
+ style.color().mix(to - to.floor()),
+ ));
+ } else {
+ check_result!(back.draw_line(
+ (from.ceil() as i32, sweep_line),
+ (to.floor() as i32, sweep_line),
+ &style.color(),
+ ));
+ check_result!(back.draw_pixel(
+ (from.floor() as i32, sweep_line),
+ style.color().mix(from.ceil() - from),
+ ));
+ check_result!(back.draw_pixel(
+ (to.ceil() as i32, sweep_line),
+ style.color().mix(to.floor() - to),
+ ));
+ }
+
+ first = None;
+ second = None;
+ }
+ }
+ }
+ }
+ }
+
+ Ok(())
+}
diff --git a/src/rasterizer/rect.rs b/src/rasterizer/rect.rs
new file mode 100644
index 0000000..cd6c774
--- /dev/null
+++ b/src/rasterizer/rect.rs
@@ -0,0 +1,57 @@
+use crate::{BackendCoord, BackendStyle, DrawingBackend, DrawingErrorKind};
+
+pub fn draw_rect<B: DrawingBackend, S: BackendStyle>(
+ b: &mut B,
+ upper_left: BackendCoord,
+ bottom_right: BackendCoord,
+ style: &S,
+ fill: bool,
+) -> Result<(), DrawingErrorKind<B::ErrorType>> {
+ if style.color().alpha == 0.0 {
+ return Ok(());
+ }
+ let (upper_left, bottom_right) = (
+ (
+ upper_left.0.min(bottom_right.0),
+ upper_left.1.min(bottom_right.1),
+ ),
+ (
+ upper_left.0.max(bottom_right.0),
+ upper_left.1.max(bottom_right.1),
+ ),
+ );
+
+ if fill {
+ if bottom_right.0 - upper_left.0 < bottom_right.1 - upper_left.1 {
+ for x in upper_left.0..=bottom_right.0 {
+ check_result!(b.draw_line((x, upper_left.1), (x, bottom_right.1), style));
+ }
+ } else {
+ for y in upper_left.1..=bottom_right.1 {
+ check_result!(b.draw_line((upper_left.0, y), (bottom_right.0, y), style));
+ }
+ }
+ } else {
+ b.draw_line(
+ (upper_left.0, upper_left.1),
+ (upper_left.0, bottom_right.1),
+ style,
+ )?;
+ b.draw_line(
+ (upper_left.0, upper_left.1),
+ (bottom_right.0, upper_left.1),
+ style,
+ )?;
+ b.draw_line(
+ (bottom_right.0, bottom_right.1),
+ (upper_left.0, bottom_right.1),
+ style,
+ )?;
+ b.draw_line(
+ (bottom_right.0, bottom_right.1),
+ (bottom_right.0, upper_left.1),
+ style,
+ )?;
+ }
+ Ok(())
+}
generated by cgit v1.2.3 (git 2.25.1) at 2024-07-04 19:48:30 +0000