# Pixel Art Algorithm: Removing Jaggies by Sorting Monotonic Curve by Segment Slope

Xprite is a new program I am developing on and off(mostly off). It is an innovative pixel art editor with a bunch of cool algorithms. Most functionalities are unimplemented but the algorithms are done.

# Removing jaggies

Jaggies are the out of place pixels in a curve.

Currently, in order to draw a perfect curve, a pixel artist has to put in the herculean effort of planning the slope of each segments and painstakingly brush them in one by one.

My algorithm basically sorts the curve segments by slope during the rasterization step. Note this only applies to monotonically increasing/decreasing curves. So a more complex curve shape(sine wave) is destructured into a bunch of monotonic cubic beziers that share adjacent control points.

I am including the algorithm in its entirety. Please share it around if you find it useful.

```
/// concavity of a monotonic curve
pub fn get_concavity(path: &[Pixel]) -> bool {
let p1 = path[0];
let p2 = path[path.len() / 2];
let p3 = path[path.len() - 1];
let Point2D {x: x1, y: y1} = p1.point.as_i32();
let Point2D {x: x2, y: y2} = p2.point.as_i32();
let Point2D {x: x3, y: y3} = p3.point.as_i32();
if (x2 == x1) || (x2 == x3) {
false
} else {
let m1 = (y2 - y1) / (x2 - x1);
let m2 = (y3 - y2) / (x3 - x2);
if m1 < m2 {
false
} else {
true
}
}
}
/// monotonic curve sorter
pub fn sort_path(path: &mut [Pixel]) -> Option<Vec<Pixel>> {
let up = path.iter().last()?.point.y < path.get(0)?.point.y;
let mut dir = if up { -1 } else { 1 };
// if the path is drawn from right to left
let right_to_left = path.iter().last()?.point.x < path[0].point.x;
if right_to_left {
dir *= -1;
path.reverse();
};
let is_concave_up = get_concavity(path);
// console!(log, format!("concavity: {}\nup: {}", is_concave_up, up));
let mut segs = Vec::new();
let p0 = path[0].point;
let mut p0 = p0;
let mut d = (1,1);
// convert pixel path into a vec of segments
for Pixel {point: pi, ..} in path.iter() {
let p0_ = p0.as_i32();
let pi_ = pi.as_i32();
if pi.x == p0.x || pi.y == p0.y {
d = (
d.0 + pi_.x - p0_.x,
d.1 + dir * (pi_.y - p0_.y),
);
} else {
while d.0 > 1 && d.1 > 1 {
segs.push(((1,1), 1.));
d.0 -= 1;
d.1 -= 1;
}
segs.push(
(d, d.1 as f32 / d.0 as f32)
);
d = (1,1);
}
p0 = *pi;
}
segs.push((d, d.1 as f32 / d.0 as f32));
// sort by slope
segs.sort_by(|a, b| {
let r = a.1 - b.1;
if r < 0. { Ordering::Less }
else if r == 0. { Ordering::Equal }
else { Ordering::Greater }
});
if (is_concave_up && !up)
|| (!is_concave_up && up) {
segs.reverse();
}
// rrf in dihedral group
if right_to_left {
segs.reverse();
}
let mut ret = Vec::new();
let mut p0 = path[0];
// offset
if (right_to_left && up)
|| (!right_to_left && !up){
p0.point.x -= 1.;
p0.point.y -= 1.;
} else if !right_to_left && up {
p0.point.x -= 1.;
p0.point.y += 1.;
} else if right_to_left && !up {
p0.point.x -= 1.;
p0.point.y += 1.;
}
for &((dx, dy), _) in segs.iter() {
if dx == 1 {
p0.point.x += 1.;
for _ in 0..dy {
if dir == 1 {
p0.point.y += 1.;
} else {
p0.point.y -= 1.;
}
ret.push(p0);
}
} else if dy == 1 {
if dir == 1 {
p0.point.y += 1.;
} else {
p0.point.y -= 1.;
}
for _ in 0..dx {
p0.point.x += 1.;
ret.push(p0);
}
}
}
Some(ret)
}
```

I originally used WebAssembly + HTML canvas for frontend which is a terrible choice since the browser just can’t up with the mouse movements. Recently, I ditched the web part and rewrote the UI in Dear ImGui and it’s about 1000x faster. However, I separated out the renderer into its own trait so hopefully web support is still a possibility once the native app is done.