comm-central/third_party/rust/aa-stroke/src/lib.rs

Revision control

Copy as Markdown

Other Tools

use std::default::Default;
use bezierflattener::CBezierFlattener;
use tri_rasterize::rasterize_to_mask;
use crate::{bezierflattener::{CFlatteningSink, GpPointR, HRESULT, S_OK, CBezier}};
mod bezierflattener;
pub mod tri_rasterize;
#[cfg(feature = "c_bindings")]
pub mod c_bindings;
#[derive(Clone, Copy, PartialEq, Debug)]
pub enum Winding {
EvenOdd,
NonZero,
}
#[derive(Clone, Copy, Debug)]
pub enum PathOp {
MoveTo(Point),
LineTo(Point),
QuadTo(Point, Point),
CubicTo(Point, Point, Point),
Close,
}
/// Represents a complete path usable for filling or stroking.
#[derive(Clone, Debug)]
pub struct Path {
pub ops: Vec<PathOp>,
pub winding: Winding,
}
pub type Point = euclid::default::Point2D<f32>;
pub type Transform = euclid::default::Transform2D<f32>;
pub type Vector = euclid::default::Vector2D<f32>;
#[derive(Clone, Copy, PartialEq, Debug)]
#[repr(C)]
pub enum LineCap {
Round,
Square,
Butt,
}
#[derive(Clone, Copy, PartialEq, Debug)]
#[repr(C)]
pub enum LineJoin {
Round,
Miter,
Bevel,
}
#[derive(Clone, PartialEq, Debug)]
#[repr(C)]
pub struct StrokeStyle {
pub width: f32,
pub cap: LineCap,
pub join: LineJoin,
pub miter_limit: f32,
}
impl Default for StrokeStyle {
fn default() -> Self {
StrokeStyle {
width: 1.,
cap: LineCap::Butt,
join: LineJoin::Miter,
miter_limit: 10.,
}
}
}
#[derive(Debug)]
pub struct Vertex {
pub x: f32,
pub y: f32,
pub coverage: f32
}
/// A helper struct used for constructing a `Path`.
pub struct PathBuilder<'z> {
output_buffer: Option<&'z mut [Vertex]>,
output_buffer_offset: usize,
vertices: Vec<Vertex>,
coverage: f32,
aa: bool
}
impl<'z> PathBuilder<'z> {
pub fn new(coverage: f32) -> PathBuilder<'z> {
PathBuilder {
output_buffer: None,
output_buffer_offset: 0,
vertices: Vec::new(),
coverage,
aa: true
}
}
pub fn set_output_buffer(&mut self, output_buffer: &'z mut [Vertex]) {
assert!(self.output_buffer.is_none());
self.output_buffer = Some(output_buffer);
}
pub fn push_tri_with_coverage(&mut self, x1: f32, y1: f32, c1: f32, x2: f32, y2: f32, c2: f32, x3: f32, y3: f32, c3: f32) {
let v1 = Vertex { x: x1, y: y1, coverage: c1 };
let v2 = Vertex { x: x2, y: y2, coverage: c2 };
let v3 = Vertex { x: x3, y: y3, coverage: c3 };
if let Some(output_buffer) = &mut self.output_buffer {
let offset = self.output_buffer_offset;
if offset + 3 <= output_buffer.len() {
output_buffer[offset] = v1;
output_buffer[offset + 1] = v2;
output_buffer[offset + 2] = v3;
}
self.output_buffer_offset = offset + 3;
} else {
self.vertices.push(v1);
self.vertices.push(v2);
self.vertices.push(v3);
}
}
pub fn push_tri(&mut self, x1: f32, y1: f32, x2: f32, y2: f32, x3: f32, y3: f32) {
self.push_tri_with_coverage(x1, y1, self.coverage, x2, y2, self.coverage, x3, y3, self.coverage);
}
// x3, y3 is the full coverage vert
pub fn tri_ramp(&mut self, x1: f32, y1: f32, x2: f32, y2: f32, x3: f32, y3: f32) {
self.push_tri_with_coverage(x1, y1, 0., x2, y2, 0., x3, y3, self.coverage);
}
pub fn quad(&mut self, x1: f32, y1: f32, x2: f32, y2: f32, x3: f32, y3: f32, x4: f32, y4: f32) {
self.push_tri(x1, y1, x2, y2, x3, y3);
self.push_tri(x3, y3, x4, y4, x1, y1);
}
pub fn ramp(&mut self, x1: f32, y1: f32, x2: f32, y2: f32, x3: f32, y3: f32, x4: f32, y4: f32) {
self.push_tri_with_coverage(x1, y1, self.coverage, x2, y2, 0., x3, y3, 0.);
self.push_tri_with_coverage(x3, y3, 0., x4, y4, self.coverage, x1, y1, self.coverage);
}
// first edge is outside
pub fn tri(&mut self, x1: f32, y1: f32, x2: f32, y2: f32, x3: f32, y3: f32) {
self.push_tri(x1, y1, x2, y2, x3, y3);
}
pub fn arc_wedge(&mut self, c: Point, radius: f32, a: Vector, b: Vector) {
arc(self, c.x, c.y, radius, a, b);
}
/// Completes the current path
pub fn finish(self) -> Box<[Vertex]> {
self.vertices.into_boxed_slice()
}
pub fn get_output_buffer_size(&self) -> Option<usize> {
if self.output_buffer.is_some() {
Some(self.output_buffer_offset)
} else {
None
}
}
}
fn compute_normal(p0: Point, p1: Point) -> Option<Vector> {
let ux = p1.x - p0.x;
let uy = p1.y - p0.y;
// this could overflow f32. Skia checks for this and
// uses a double in that situation
let ulen = ux.hypot(uy);
if ulen == 0. {
return None;
}
// the normal is perpendicular to the *unit* vector
Some(Vector::new(-uy / ulen, ux / ulen))
}
fn flip(v: Vector) -> Vector {
Vector::new(-v.x, -v.y)
}
/* Compute a spline approximation of the arc
centered at xc, yc from the angle a to the angle b
The angle between a and b should not be more than a
quarter circle (pi/2)
The approximation is similar to an approximation given in:
"Approximation of a cubic bezier curve by circular arcs and vice versa"
by Alekas Riškus. However that approximation becomes unstable when the
angle of the arc approaches 0.
This approximation is inspired by a discusion with Boris Zbarsky
and essentially just computes:
h = 4.0/3.0 * tan ((angle_B - angle_A) / 4.0);
without converting to polar coordinates.
A different way to do this is covered in "Approximation of a cubic bezier
curve by circular arcs and vice versa" by Alekas Riškus. However, the method
presented there doesn't handle arcs with angles close to 0 because it
divides by the perp dot product of the two angle vectors.
*/
fn arc_segment_tri(path: &mut PathBuilder, xc: f32, yc: f32, radius: f32, a: Vector, b: Vector) {
let r_sin_a = radius * a.y;
let r_cos_a = radius * a.x;
let r_sin_b = radius * b.y;
let r_cos_b = radius * b.x;
/* bisect the angle between 'a' and 'b' with 'mid' */
let mut mid = a + b;
mid /= mid.length();
/* bisect the angle between 'a' and 'mid' with 'mid2' this is parallel to a
* line with angle (B - A)/4 */
let mid2 = a + mid;
let h = (4. / 3.) * dot(perp(a), mid2) / dot(a, mid2);
let last_point = GpPointR { x: (xc + r_cos_a), y: (yc + r_sin_a) };
let initial_normal = GpPointR { x: a.x, y: a.y };
struct Target<'a, 'b> { last_point: GpPointR, last_normal: GpPointR, xc: f32, yc: f32, path: &'a mut PathBuilder<'b> }
impl<'a, 'b> CFlatteningSink for Target<'a, 'b> {
fn AcceptPointAndTangent(&mut self,
pt: &GpPointR,
// The point
vec: &GpPointR,
// The tangent there
_last: bool
// Is this the last point on the curve?
) -> HRESULT {
if self.path.aa {
let len = vec.Norm();
let normal = *vec/len;
let normal = GpPointR { x: -normal.y, y: normal.x };
// FIXME: we probably need more width here because
// the normals are not perpendicular with the edge
let width = 0.5;
self.path.ramp(
pt.x - normal.x * width,
pt.y - normal.y * width,
pt.x + normal.x * width,
pt.y + normal.y * width,
self.last_point.x + self.last_normal.x * width,
self.last_point.y + self.last_normal.y * width,
self.last_point.x - self.last_normal.x * width,
self.last_point.y - self.last_normal.y * width, );
self.path.push_tri(
self.last_point.x - self.last_normal.x * 0.5,
self.last_point.y - self.last_normal.y * 0.5,
pt.x - normal.x * 0.5,
pt.y - normal.y * 0.5,
self.xc, self.yc);
self.last_normal = normal;
} else {
self.path.push_tri(self.last_point.x, self.last_point.y, pt.x, pt.y, self.xc, self.yc);
}
self.last_point = pt.clone();
return S_OK;
}
fn AcceptPoint(&mut self,
pt: &GpPointR,
// The point
_t: f32,
// Parameter we're at
_aborted: &mut bool,
_last_point: bool) -> HRESULT {
self.path.push_tri(self.last_point.x, self.last_point.y, pt.x, pt.y, self.xc, self.yc);
self.last_point = pt.clone();
return S_OK;
}
fn FirstTangent(&mut self, _: Option<GpPointR>) { }
}
let bezier = CBezier::new([GpPointR { x: (xc + r_cos_a), y: (yc + r_sin_a), },
GpPointR { x: (xc + r_cos_a - h * r_sin_a), y: (yc + r_sin_a + h * r_cos_a), },
GpPointR { x: (xc + r_cos_b + h * r_sin_b), y: (yc + r_sin_b - h * r_cos_b), },
GpPointR { x: (xc + r_cos_b), y: (yc + r_sin_b), }]);
if bezier.is_degenerate() {
return;
}
let mut t = Target{ last_point, last_normal: initial_normal, xc, yc, path };
let mut f = CBezierFlattener::new(&bezier, &mut t, 0.25);
if f.GetFirstTangent().is_none() {
// the curve is not completely degenerate but degenerate enough that we can't flatten it
// draw a single triangle for the curve
let width = 0.5;
let next_point = GpPointR { x: (xc + r_cos_b), y: (yc + r_sin_b) };
if path.aa {
// XXX: This code will potentially run into trouble if the radius is very small
// but the general case suffers the same problem.
path.ramp(
next_point.x - b.x * width,
next_point.y - b.y * width,
next_point.x + b.x * width,
next_point.y + b.y * width,
last_point.x + a.x * width,
last_point.y + a.y * width,
last_point.x - a.x * width,
last_point.y - a.y * width);
path.push_tri(
last_point.x - a.x * 0.5,
last_point.y - a.y * 0.5,
next_point.x - b.x * 0.5,
next_point.y - b.y * 0.5,
xc, yc);
} else {
path.push_tri(last_point.x, last_point.y, next_point.x, next_point.y, xc, yc);
}
} else {
f.Flatten(true);
}
}
/* The angle between the vectors must be <= pi */
fn bisect(a: Vector, b: Vector) -> Vector {
let mut mid;
if dot(a, b) >= 0. {
/* if the angle between a and b is accute, then we can
* just add the vectors and normalize */
mid = a + b;
} else {
/* otherwise, we can flip a, add it
* and then use the perpendicular of the result */
mid = flip(a) + b;
mid = perp(mid);
}
/* normalize */
/* because we assume that 'a' and 'b' are normalized, we can use
* sqrt instead of hypot because the range of mid is limited */
let mid_len = mid.x * mid.x + mid.y * mid.y;
let len = mid_len.sqrt();
return mid / len;
}
/* The angle between the vectors must be <= 180 degrees */
fn arc(path: &mut PathBuilder, xc: f32, yc: f32, radius: f32, a: Vector, b: Vector) {
// Depending on the magnitude of the angle use 0, 1 or 2 arc segments.
if dot(a, b) == 1.0 {
// the angle is 0 degrees, do nothing
} else if dot(a, b) >= 0. {
// the angle is less than 90 degrees
arc_segment_tri(path, xc, yc, radius, a, b);
} else {
/* find a vector that bisects the angle between a and b */
let mid_v = bisect(a, b);
/* construct the arc using two curve segments */
arc_segment_tri(path, xc, yc, radius, a, mid_v);
arc_segment_tri(path, xc, yc, radius, mid_v, b);
}
}
/*
fn join_round(path: &mut PathBuilder, center: Point, a: Vector, b: Vector, radius: f32) {
/*
int ccw = dot (perp (b), a) >= 0; // XXX: is this always true?
yes, otherwise we have an interior angle.
assert (ccw);
*/
arc(path, center.x, center.y, radius, a, b);
}*/
fn cap_line(dest: &mut PathBuilder, style: &StrokeStyle, pt: Point, normal: Vector) {
let offset = style.width / 2.;
match style.cap {
LineCap::Butt => {
if dest.aa {
let half_width = offset;
let end = pt;
let v = Vector::new(normal.y, -normal.x);
// end
dest.ramp(
end.x - normal.x * (half_width - 0.5),
end.y - normal.y * (half_width - 0.5),
end.x + v.x - normal.x * (half_width - 0.5),
end.y + v.y - normal.y * (half_width - 0.5),
end.x + v.x + normal.x * (half_width - 0.5),
end.y + v.y + normal.y * (half_width - 0.5),
end.x + normal.x * (half_width - 0.5),
end.y + normal.y * (half_width - 0.5),
);
dest.tri_ramp(
end.x + v.x - normal.x * (half_width - 0.5),
end.y + v.y - normal.y * (half_width - 0.5),
end.x - normal.x * (half_width + 0.5),
end.y - normal.y * (half_width + 0.5),
end.x - normal.x * (half_width - 0.5),
end.y - normal.y * (half_width - 0.5));
dest.tri_ramp(
end.x + v.x + normal.x * (half_width - 0.5),
end.y + v.y + normal.y * (half_width - 0.5),
end.x + normal.x * (half_width + 0.5),
end.y + normal.y * (half_width + 0.5),
end.x + normal.x * (half_width - 0.5),
end.y + normal.y * (half_width - 0.5));
}
}
LineCap::Round => {
dest.arc_wedge(pt, offset, normal, flip(normal));
}
LineCap::Square => {
// parallel vector
let v = Vector::new(normal.y, -normal.x);
let end = pt + v * offset;
if dest.aa {
let half_width = offset;
let offset = offset - 0.5;
dest.ramp(
end.x + normal.x * (half_width - 0.5),
end.y + normal.y * (half_width - 0.5),
end.x + normal.x * (half_width + 0.5),
end.y + normal.y * (half_width + 0.5),
pt.x + normal.x * (half_width + 0.5),
pt.y + normal.y * (half_width + 0.5),
pt.x + normal.x * (half_width - 0.5),
pt.y + normal.y * (half_width - 0.5),
);
dest.quad(pt.x + normal.x * offset, pt.y + normal.y * offset,
end.x + normal.x * offset, end.y + normal.y * offset,
end.x + -normal.x * offset, end.y + -normal.y * offset,
pt.x - normal.x * offset, pt.y - normal.y * offset);
dest.ramp(
pt.x - normal.x * (half_width - 0.5),
pt.y - normal.y * (half_width - 0.5),
pt.x - normal.x * (half_width + 0.5),
pt.y - normal.y * (half_width + 0.5),
end.x - normal.x * (half_width + 0.5),
end.y - normal.y * (half_width + 0.5),
end.x - normal.x * (half_width - 0.5),
end.y - normal.y * (half_width - 0.5));
// end
dest.ramp(
end.x - normal.x * (half_width - 0.5),
end.y - normal.y * (half_width - 0.5),
end.x + v.x - normal.x * (half_width - 0.5),
end.y + v.y - normal.y * (half_width - 0.5),
end.x + v.x + normal.x * (half_width - 0.5),
end.y + v.y + normal.y * (half_width - 0.5),
end.x + normal.x * (half_width - 0.5),
end.y + normal.y * (half_width - 0.5),
);
// corners
dest.tri_ramp(
end.x + v.x - normal.x * (half_width - 0.5),
end.y + v.y - normal.y * (half_width - 0.5),
end.x - normal.x * (half_width + 0.5),
end.y - normal.y * (half_width + 0.5),
end.x - normal.x * (half_width - 0.5),
end.y - normal.y * (half_width - 0.5));
dest.tri_ramp(
end.x + v.x + normal.x * (half_width - 0.5),
end.y + v.y + normal.y * (half_width - 0.5),
end.x + normal.x * (half_width + 0.5),
end.y + normal.y * (half_width + 0.5),
end.x + normal.x * (half_width - 0.5),
end.y + normal.y * (half_width - 0.5));
} else {
dest.quad(pt.x + normal.x * offset, pt.y + normal.y * offset,
end.x + normal.x * offset, end.y + normal.y * offset,
end.x + -normal.x * offset, end.y + -normal.y * offset,
pt.x - normal.x * offset, pt.y - normal.y * offset);
}
}
}
}
fn bevel(
dest: &mut PathBuilder,
style: &StrokeStyle,
pt: Point,
s1_normal: Vector,
s2_normal: Vector,
) {
let offset = style.width / 2.;
if dest.aa {
let width = 1.;
let offset = offset - width / 2.;
//XXX: we should be able to just bisect the two norms to get this
let diff = match (s2_normal - s1_normal).try_normalize() {
Some(diff) => diff,
None => return,
};
let edge_normal = perp(diff);
dest.tri(pt.x + s1_normal.x * offset, pt.y + s1_normal.y * offset,
pt.x + s2_normal.x * offset, pt.y + s2_normal.y * offset,
pt.x, pt.y);
dest.tri_ramp(pt.x + s1_normal.x * (offset + width), pt.y + s1_normal.y * (offset + width),
pt.x + s1_normal.x * offset + edge_normal.x, pt.y + s1_normal.y * offset + edge_normal.y,
pt.x + s1_normal.x * offset, pt.y + s1_normal.y * offset);
dest.ramp(
pt.x + s2_normal.x * offset, pt.y + s2_normal.y * offset,
pt.x + s2_normal.x * offset + edge_normal.x, pt.y + s2_normal.y * offset + edge_normal.y,
pt.x + s1_normal.x * offset + edge_normal.x, pt.y + s1_normal.y * offset + edge_normal.y,
pt.x + s1_normal.x * offset, pt.y + s1_normal.y * offset,
);
dest.tri_ramp(pt.x + s2_normal.x * (offset + width), pt.y + s2_normal.y * (offset + width),
pt.x + s2_normal.x * offset + edge_normal.x, pt.y + s2_normal.y * offset + edge_normal.y,
pt.x + s2_normal.x * offset, pt.y + s2_normal.y * offset);
} else {
dest.tri(pt.x + s1_normal.x * offset, pt.y + s1_normal.y * offset,
pt.x + s2_normal.x * offset, pt.y + s2_normal.y * offset,
pt.x, pt.y);
}
}
/* given a normal rotate the vector 90 degrees to the right clockwise
* This function has a period of 4. e.g. swap(swap(swap(swap(x) == x */
fn swap(a: Vector) -> Vector {
/* one of these needs to be negative. We choose a.x so that we rotate to the right instead of negating */
Vector::new(a.y, -a.x)
}
fn unperp(a: Vector) -> Vector {
swap(a)
}
/* rotate a vector 90 degrees to the left */
fn perp(v: Vector) -> Vector {
Vector::new(-v.y, v.x)
}
fn dot(a: Vector, b: Vector) -> f32 {
a.x * b.x + a.y * b.y
}
fn cross(a: Vector, b: Vector) -> f32 {
return a.x * b.y - a.y * b.x;
}
/* Finds the intersection of two lines each defined by a point and a normal.
From "Example 2: Find the intersection of two lines" of
"The Pleasures of "Perp Dot" Products"
F. S. Hill, Jr. */
fn line_intersection(a: Point, a_perp: Vector, b: Point, b_perp: Vector) -> Option<Point> {
let a_parallel = unperp(a_perp);
let c = b - a;
let denom = dot(b_perp, a_parallel);
if denom == 0.0 {
return None;
}
let t = dot(b_perp, c) / denom;
let intersection = Point::new(a.x + t * (a_parallel.x), a.y + t * (a_parallel.y));
Some(intersection)
}
fn is_interior_angle(a: Vector, b: Vector) -> bool {
/* angles of 180 and 0 degress will evaluate to 0, however
* we to treat 0 as an interior angle and 180 as an exterior angle */
dot(perp(a), b) > 0. || a == b /* 0 degrees is interior */
}
fn join_line(
dest: &mut PathBuilder,
style: &StrokeStyle,
pt: Point,
mut s1_normal: Vector,
mut s2_normal: Vector,
) {
if is_interior_angle(s1_normal, s2_normal) {
s2_normal = flip(s2_normal);
s1_normal = flip(s1_normal);
std::mem::swap(&mut s1_normal, &mut s2_normal);
}
// XXX: joining uses `pt` which can cause seams because it lies halfway on a line and the
// rasterizer may not find exactly the same spot
let mut offset = style.width / 2.;
match style.join {
LineJoin::Round => {
dest.arc_wedge(pt, offset, s1_normal, s2_normal);
}
LineJoin::Miter => {
if dest.aa {
offset -= 0.5;
}
let in_dot_out = -s1_normal.x * s2_normal.x + -s1_normal.y * s2_normal.y;
if 2. <= style.miter_limit * style.miter_limit * (1. - in_dot_out) {
let start = pt + s1_normal * offset;
let end = pt + s2_normal * offset;
if let Some(intersection) = line_intersection(start, s1_normal, end, s2_normal) {
// We won't have an intersection if the segments are parallel
if dest.aa {
let ramp_start = pt + s1_normal * (offset + 1.);
let ramp_end = pt + s2_normal * (offset + 1.);
// The following diagram is inspired by the DoLimitedMiter code
// from WpfGfx. Their math doesn't make sense to me so
// there's an original derivation from jgilbert below:
//
// offset point
// --*---------------------- offset line
// | *
// |*
// * clip point
// *|s a spine
// *-- offset ................
// q| point .
// | .
// | .
// | .
// | - r - . -------
// | . |
// | . |
//
// b = a/2
// r/(q+r) = cos b => q + r = r/cos b => q = r/cos b - r
// q/s = sin b/cos b => s = q cos b/sin b
// s = (r/cos b - r) * cos b/sin b = (r - r cos b)/sin b
// sub in r = 1
// s = (1 - cos b)/sin b
//
// rearrange so that we don't have denominator of 0 when b = 0 (parallel lines)
// this prevents numerical instability in that case
//
// (1 - cos b)/sin b => (1 - cos b)(1 + cos b)/(sin b * (1 + cos b))
// => (1 - cos^2 b) / (sin b * (1 + cos b)
// => sin^2 b / sin b * (1 + cos b)
// => sin b / (1 + cos b)
let mid = bisect(s1_normal, s2_normal);
// cross = sin, dot = cos
let cos = dot(s1_normal, mid);
let s = cross(mid, s1_normal)/(1. + cos);
// compute the intersection in a more stable way
let intersection = pt + mid * (offset / cos);
let ramp_s1 = intersection + s1_normal * 1. + unperp(s1_normal) * s;
let ramp_s2 = intersection + s2_normal * 1. + perp(s2_normal) * s;
dest.ramp(intersection.x, intersection.y,
ramp_s1.x, ramp_s1.y,
ramp_start.x, ramp_start.y,
pt.x + s1_normal.x * offset, pt.y + s1_normal.y * offset,
);
dest.ramp(pt.x + s2_normal.x * offset, pt.y + s2_normal.y * offset,
ramp_end.x, ramp_end.y,
ramp_s2.x, ramp_s2.y,
intersection.x, intersection.y);
// put a flat cap on the end
dest.tri_ramp(ramp_s1.x, ramp_s1.y, ramp_s2.x, ramp_s2.y, intersection.x, intersection.y);
dest.quad(pt.x + s1_normal.x * offset, pt.y + s1_normal.y * offset,
intersection.x, intersection.y,
pt.x + s2_normal.x * offset, pt.y + s2_normal.y * offset,
pt.x, pt.y);
} else {
dest.quad(pt.x + s1_normal.x * offset, pt.y + s1_normal.y * offset,
intersection.x, intersection.y,
pt.x + s2_normal.x * offset, pt.y + s2_normal.y * offset,
pt.x, pt.y);
}
}
} else {
bevel(dest, style, pt, s1_normal, s2_normal);
}
}
LineJoin::Bevel => {
bevel(dest, style, pt, s1_normal, s2_normal);
}
}
}
pub struct Stroker<'z> {
stroked_path: PathBuilder<'z>,
cur_pt: Option<Point>,
last_normal: Vector,
half_width: f32,
start_point: Option<(Point, Vector)>,
style: StrokeStyle,
closed_subpath: bool
}
impl<'z> Stroker<'z> {
pub fn new(style: &StrokeStyle) -> Self {
let mut style = style.clone();
let mut coverage = 1.;
if style.width < 1. {
coverage = style.width;
style.width = 1.;
}
Stroker {
stroked_path: PathBuilder::new(coverage),
cur_pt: None,
last_normal: Vector::zero(),
half_width: style.width / 2.,
start_point: None,
style,
closed_subpath: false,
}
}
pub fn set_output_buffer(&mut self, output_buffer: &'z mut [Vertex]) {
self.stroked_path.set_output_buffer(output_buffer);
}
pub fn line_to_capped(&mut self, pt: Point) {
if let Some(cur_pt) = self.cur_pt {
let normal = compute_normal(cur_pt, pt).unwrap_or(self.last_normal);
// if we have a butt cap end the line half a pixel early so we have room to put the cap.
// XXX: this will probably mess things up if the line is shorter than 1/2 pixel long
self.line_to(if self.stroked_path.aa && self.style.cap == LineCap::Butt { pt + perp(normal) * 0.5} else { pt });
if let (Some(cur_pt), Some((_point, _normal))) = (self.cur_pt, self.start_point) {
// cap end
cap_line(&mut self.stroked_path, &self.style, cur_pt, self.last_normal);
}
}
self.start_point = None;
}
pub fn move_to(&mut self, pt: Point, closed_subpath: bool) {
//eprintln!("stroker.move_to(Point::new({}, {}), {});", pt.x, pt.y, closed_subpath);
self.start_point = None;
self.cur_pt = Some(pt);
self.closed_subpath = closed_subpath;
}
pub fn line_to(&mut self, pt: Point) {
//eprintln!("stroker.line_to(Point::new({}, {}));", pt.x, pt.y);
let cur_pt = self.cur_pt;
let stroked_path = &mut self.stroked_path;
let half_width = self.half_width;
if cur_pt.is_none() {
self.start_point = None;
} else if let Some(cur_pt) = cur_pt {
if let Some(normal) = compute_normal(cur_pt, pt) {
if self.start_point.is_none() {
if !self.closed_subpath {
// cap beginning
let mut cur_pt = cur_pt;
if stroked_path.aa && self.style.cap == LineCap::Butt {
// adjust the starting point to make room for the cap
// XXX: this will probably mess things up if the line is shorter than 1/2 pixel long
cur_pt += perp(flip(normal)) * 0.5;
}
cap_line(stroked_path, &self.style, cur_pt, flip(normal));
}
self.start_point = Some((cur_pt, normal));
} else {
join_line(stroked_path, &self.style, cur_pt, self.last_normal, normal);
}
if stroked_path.aa {
stroked_path.ramp(
pt.x + normal.x * (half_width - 0.5),
pt.y + normal.y * (half_width - 0.5),
pt.x + normal.x * (half_width + 0.5),
pt.y + normal.y * (half_width + 0.5),
cur_pt.x + normal.x * (half_width + 0.5),
cur_pt.y + normal.y * (half_width + 0.5),
cur_pt.x + normal.x * (half_width - 0.5),
cur_pt.y + normal.y * (half_width - 0.5),
);
stroked_path.quad(
cur_pt.x + normal.x * (half_width - 0.5),
cur_pt.y + normal.y * (half_width - 0.5),
pt.x + normal.x * (half_width - 0.5), pt.y + normal.y * (half_width - 0.5),
pt.x + -normal.x * (half_width - 0.5), pt.y + -normal.y * (half_width - 0.5),
cur_pt.x - normal.x * (half_width - 0.5),
cur_pt.y - normal.y * (half_width - 0.5),
);
stroked_path.ramp(
cur_pt.x - normal.x * (half_width - 0.5),
cur_pt.y - normal.y * (half_width - 0.5),
cur_pt.x - normal.x * (half_width + 0.5),
cur_pt.y - normal.y * (half_width + 0.5),
pt.x - normal.x * (half_width + 0.5),
pt.y - normal.y * (half_width + 0.5),
pt.x - normal.x * (half_width - 0.5),
pt.y - normal.y * (half_width - 0.5),
);
} else {
stroked_path.quad(
cur_pt.x + normal.x * half_width,
cur_pt.y + normal.y * half_width,
pt.x + normal.x * half_width, pt.y + normal.y * half_width,
pt.x + -normal.x * half_width, pt.y + -normal.y * half_width,
cur_pt.x - normal.x * half_width,
cur_pt.y - normal.y * half_width,
);
}
self.last_normal = normal;
}
}
self.cur_pt = Some(pt);
}
pub fn curve_to(&mut self, cx1: Point, cx2: Point, pt: Point) {
//eprintln!("stroker.curve_to(Point::new({}, {}), Point::new({}, {}), Point::new({}, {}));", cx1.x, cx1.y, cx2.x, cx2.y, pt.x, pt.y);
self.curve_to_direct(cx1, cx2, pt, false);
}
pub fn curve_to_capped(&mut self, cx1: Point, cx2: Point, pt: Point) {
self.curve_to_direct(cx1, cx2, pt, true);
}
pub fn curve_to_internal(&mut self, cx1: Point, cx2: Point, pt: Point, end: bool) {
struct Target<'a, 'b> { stroker: &'a mut Stroker<'b>, end: bool }
impl<'a, 'b> CFlatteningSink for Target<'a, 'b> {
fn AcceptPointAndTangent(&mut self, _: &GpPointR, _: &GpPointR, _: bool ) -> HRESULT {
panic!()
}
fn FirstTangent(&mut self, _tangent: Option<GpPointR>) { }
fn AcceptPoint(&mut self,
pt: &GpPointR,
// The point
_t: f32,
// Parameter we're at
_aborted: &mut bool,
last_point: bool) -> HRESULT {
if last_point && self.end {
self.stroker.line_to_capped(Point::new(pt.x, pt.y));
} else {
self.stroker.line_to(Point::new(pt.x, pt.y));
}
return S_OK;
}
}
let cur_pt = self.cur_pt.unwrap_or(cx1);
let bezier = CBezier::new([GpPointR { x: cur_pt.x, y: cur_pt.y, },
GpPointR { x: cx1.x, y: cx1.y, },
GpPointR { x: cx2.x, y: cx2.y, },
GpPointR { x: pt.x, y: pt.y, }]);
let mut t = Target{ stroker: self, end };
let mut f = CBezierFlattener::new(&bezier, &mut t, 0.25);
f.Flatten(false);
}
// Stroke a curve by flattening to trapezoids insteads instead of rectangles.
// This lets us make sure that the normal of the stroked path matches the normal
// of the curve and we also avoid having to join the segments
pub fn curve_to_direct(&mut self, cx1: Point, cx2: Point, pt: Point, end: bool) {
struct Target<'a, 'b> { stroker: &'a mut Stroker<'b>, _end: bool, last_normal: Vector, last_point: GpPointR}
impl<'a, 'b> CFlatteningSink for Target<'a, 'b> {
fn FirstTangent(&mut self, tangent: Option<GpPointR>) {
let tangent = tangent.unwrap();
let last_normal = flip(Vector::new(tangent.y, -tangent.x).normalize());
let stroked_path = &mut self.stroker.stroked_path;
if self.stroker.start_point.is_some() {
if let Some(cur_pt) = self.stroker.cur_pt {
join_line(stroked_path, &self.stroker.style, cur_pt, self.stroker.last_normal, last_normal);
}
}
self.last_normal = last_normal;
}
fn AcceptPointAndTangent(&mut self, pt: &GpPointR, tangent: &GpPointR, _last: bool) -> HRESULT {
let normal = flip(Vector::new(tangent.y, -tangent.x).normalize());
let last_normal = self.last_normal;
let cur_pt = Point::new(self.last_point.x, self.last_point.y);
let half_width = self.stroker.half_width;
let stroked_path = &mut self.stroker.stroked_path;
if self.stroker.start_point.is_none() {
if !self.stroker.closed_subpath {
// cap beginning
let mut cur_pt = cur_pt;
if stroked_path.aa && self.stroker.style.cap == LineCap::Butt {
// adjust the starting point to make room for the cap
// XXX: this will probably mess things up if the line is shorter than 1/2 pixel long
cur_pt += perp(flip(last_normal)) * 0.5;
}
cap_line(stroked_path, &self.stroker.style, cur_pt, flip(last_normal));
}
// last_normal will have been set by FirstTangent
self.stroker.start_point = Some((cur_pt, last_normal));
} else {
// we don't need to join the segments because the quads are sharing normals
}
if stroked_path.aa {
stroked_path.ramp(
pt.x + normal.x * (half_width - 0.5),
pt.y + normal.y * (half_width - 0.5),
pt.x + normal.x * (half_width + 0.5),
pt.y + normal.y * (half_width + 0.5),
cur_pt.x + last_normal.x * (half_width + 0.5),
cur_pt.y + last_normal.y * (half_width + 0.5),
cur_pt.x + last_normal.x * (half_width - 0.5),
cur_pt.y + last_normal.y * (half_width - 0.5),
);
stroked_path.quad(
cur_pt.x + last_normal.x * (half_width - 0.5),
cur_pt.y + last_normal.y * (half_width - 0.5),
pt.x + normal.x * (half_width - 0.5), pt.y + normal.y * (half_width - 0.5),
pt.x + -normal.x * (half_width - 0.5), pt.y + -normal.y * (half_width - 0.5),
cur_pt.x - last_normal.x * (half_width - 0.5),
cur_pt.y - last_normal.y * (half_width - 0.5),
);
stroked_path.ramp(
cur_pt.x - last_normal.x * (half_width - 0.5),
cur_pt.y - last_normal.y * (half_width - 0.5),
cur_pt.x - last_normal.x * (half_width + 0.5),
cur_pt.y - last_normal.y * (half_width + 0.5),
pt.x - normal.x * (half_width + 0.5),
pt.y - normal.y * (half_width + 0.5),
pt.x - normal.x * (half_width - 0.5),
pt.y - normal.y * (half_width - 0.5),
);
} else {
self.stroker.stroked_path.quad(
cur_pt.x + last_normal.x * half_width,
cur_pt.y + last_normal.y * half_width,
pt.x + normal.x * half_width, pt.y + normal.y * half_width,
pt.x + -normal.x * half_width, pt.y + -normal.y * half_width,
cur_pt.x - last_normal.x * half_width,
cur_pt.y - last_normal.y * half_width,
);
}
self.last_normal = normal;
self.last_point = *pt;
return S_OK;
}
fn AcceptPoint(&mut self, _p: &GpPointR,
_: f32, _: &mut bool, _: bool) -> HRESULT {
panic!();
}
}
let cur_pt = self.cur_pt.unwrap_or(cx1);
let bezier = CBezier::new([GpPointR { x: cur_pt.x, y: cur_pt.y, },
GpPointR { x: cx1.x, y: cx1.y, },
GpPointR { x: cx2.x, y: cx2.y, },
GpPointR { x: pt.x, y: pt.y, }]);
let mut t = Target{ stroker: self, _end: end,
last_normal: Vector::new(0., 0.),
last_point: GpPointR { x: cur_pt.x, y: cur_pt.y }
};
let mut f = CBezierFlattener::new(&bezier, &mut t, 0.25);
if f.GetFirstTangent().is_none() {
// the bezier is degnerate
return if end { self.line_to_capped(pt) } else { self.line_to(pt) };
}
f.Flatten(true);
self.last_normal = t.last_normal;
self.cur_pt = Some(pt);
}
pub fn close(&mut self) {
let stroked_path = &mut self.stroked_path;
let half_width = self.half_width;
if let (Some(cur_pt), Some((end_point, start_normal))) = (self.cur_pt, self.start_point) {
if let Some(normal) = compute_normal(cur_pt, end_point) {
join_line(stroked_path, &self.style, cur_pt, self.last_normal, normal);
if stroked_path.aa {
stroked_path.ramp(
end_point.x + normal.x * (half_width - 0.5),
end_point.y + normal.y * (half_width - 0.5),
end_point.x + normal.x * (half_width + 0.5),
end_point.y + normal.y * (half_width + 0.5),
cur_pt.x + normal.x * (half_width + 0.5),
cur_pt.y + normal.y * (half_width + 0.5),
cur_pt.x + normal.x * (half_width - 0.5),
cur_pt.y + normal.y * (half_width - 0.5),
);
stroked_path.quad(
cur_pt.x + normal.x * (half_width - 0.5),
cur_pt.y + normal.y * (half_width - 0.5),
end_point.x + normal.x * (half_width - 0.5), end_point.y + normal.y * (half_width - 0.5),
end_point.x + -normal.x * (half_width - 0.5), end_point.y + -normal.y * (half_width - 0.5),
cur_pt.x - normal.x * (half_width - 0.5),
cur_pt.y - normal.y * (half_width - 0.5),
);
stroked_path.ramp(
cur_pt.x - normal.x * (half_width - 0.5),
cur_pt.y - normal.y * (half_width - 0.5),
cur_pt.x - normal.x * (half_width + 0.5),
cur_pt.y - normal.y * (half_width + 0.5),
end_point.x - normal.x * (half_width + 0.5),
end_point.y - normal.y * (half_width + 0.5),
end_point.x - normal.x * (half_width - 0.5),
end_point.y - normal.y * (half_width - 0.5),
);
} else {
stroked_path.quad(
cur_pt.x + normal.x * half_width,
cur_pt.y + normal.y * half_width,
end_point.x + normal.x * half_width, end_point.y + normal.y * half_width,
end_point.x + -normal.x * half_width, end_point.y + -normal.y * half_width,
cur_pt.x - normal.x * half_width,
cur_pt.y - normal.y * half_width,
);
}
join_line(stroked_path, &self.style, end_point, normal, start_normal);
} else {
join_line(stroked_path, &self.style, end_point, self.last_normal, start_normal);
}
}
self.cur_pt = self.start_point.map(|x| x.0);
self.start_point = None;
}
pub fn get_stroked_path(&mut self) -> PathBuilder<'z> {
let mut stroked_path = std::mem::replace(&mut self.stroked_path, PathBuilder::new(1.));
if let (Some(cur_pt), Some((point, normal))) = (self.cur_pt, self.start_point) {
// cap end
cap_line(&mut stroked_path, &self.style, cur_pt, self.last_normal);
// cap beginning
cap_line(&mut stroked_path, &self.style, point, flip(normal));
}
stroked_path
}
pub fn finish(&mut self) -> Box<[Vertex]> {
self.get_stroked_path().finish()
}
}
fn filled_circle_with_path_builder(mut path_builder: &mut PathBuilder, center: Point, radius: f32) {
arc(&mut path_builder, center.x, center.y, radius, Vector::new(1., 0.), Vector::new(-1., 0.));
arc(&mut path_builder, center.x, center.y, radius, Vector::new(-1., 0.), Vector::new(1., 0.));
}
/// Returns an anti-aliased triangle mesh for a filled circle.
pub fn filled_circle(center: Point, radius: f32) -> Box<[Vertex]> {
let mut path_builder = PathBuilder::new(1.);
filled_circle_with_path_builder(&mut path_builder, center, radius);
path_builder.finish()
}
#[test]
fn filled_circle_test() {
let center = Point::new(100., 100.);
let radius = 33.;
let result = filled_circle(center, radius);
let min_x = result.iter().map(|v: &Vertex| v.x).reduce(|a, b| a.min(b)).unwrap();
let max_x = result.iter().map(|v: &Vertex| v.x).reduce(|a, b| a.max(b)).unwrap();
let min_y = result.iter().map(|v: &Vertex| v.y).reduce(|a, b| a.min(b)).unwrap();
let max_y = result.iter().map(|v: &Vertex| v.y).reduce(|a, b| a.max(b)).unwrap();
assert_eq!(min_x, center.x - (radius + 0.5));
assert_eq!(max_x, center.x + (radius + 0.5));
assert_eq!(min_y, center.y - (radius + 0.5));
assert_eq!(max_y, center.y + (radius + 0.5));
}
#[test]
fn simple() {
let mut stroker = Stroker::new(&StrokeStyle{
cap: LineCap::Round,
join: LineJoin::Bevel,
width: 20.,
..Default::default()});
stroker.move_to(Point::new(20., 20.), false);
stroker.line_to(Point::new(100., 100.));
stroker.line_to_capped(Point::new(110., 20.));
stroker.move_to(Point::new(120., 20.), true);
stroker.line_to(Point::new(120., 50.));
stroker.line_to(Point::new(140., 50.));
stroker.close();
let stroked = stroker.finish();
assert_eq!(stroked.len(), 330);
}
#[test]
fn curve() {
let mut stroker = Stroker::new(&StrokeStyle{
cap: LineCap::Round,
join: LineJoin::Bevel,
width: 20.,
..Default::default()});
stroker.move_to(Point::new(20., 160.), true);
stroker.curve_to(Point::new(100., 160.), Point::new(100., 180.), Point::new(20., 180.));
stroker.close();
let stroked = stroker.finish();
assert_eq!(stroked.len(), 624);
}
#[test]
fn butt_cap() {
let mut stroker = Stroker::new(&StrokeStyle{
cap: LineCap::Butt,
join: LineJoin::Bevel,
width: 1.,
..Default::default()});
stroker.move_to(Point::new(20., 20.5), false);
stroker.line_to_capped(Point::new(40., 20.5));
let result = stroker.finish();
for v in result.iter() {
assert!(v.y == 20.5 || v.y == 19.5 || v.y == 21.5);
}
}
#[test]
fn width_one_radius_arc() {
// previously this caused us to try to flatten an arc with radius 0
let mut stroker = Stroker::new(&StrokeStyle{
cap: LineCap::Round,
join: LineJoin::Round,
width: 1.,
..Default::default()});
stroker.move_to(Point::new(20., 20.), false);
stroker.line_to(Point::new(30., 160.));
stroker.line_to_capped(Point::new(40., 20.));
stroker.finish();
}
#[test]
fn round_join_less_than_90deg() {
let mut stroker = Stroker::new(&StrokeStyle{
cap: LineCap::Round,
join: LineJoin::Round,
width: 1.,
..Default::default()});
stroker.move_to(Point::new(20., 20.), false);
stroker.line_to(Point::new(20., 40.));
stroker.line_to_capped(Point::new(30., 50.));
assert_eq!(stroker.finish().len(), 81);
}
#[test]
fn small_arc() {
let mut path = PathBuilder::new(1.);
let start = 0_f32;
let end = 0.001_f32;
arc(&mut path, 0., 0., 0.5, Vector::new(start.cos(), start.sin()), Vector::new(end.cos(), end.sin()));
}
#[test]
fn parallel_line_join() {
// ensure line joins of almost parallel lines don't cause math to fail
for join in [LineJoin::Bevel, LineJoin::Round, LineJoin::Miter] {
let mut stroker = Stroker::new(&StrokeStyle{
cap: LineCap::Butt,
join,
width: 1.0,
..Default::default()});
stroker.move_to(Point::new(19.812500, 71.625000), true);
stroker.line_to(Point::new(19.250000, 72.000000));
stroker.line_to(Point::new(19.062500, 72.125000));
stroker.close();
stroker.finish();
}
}
#[test]
fn degenerate_miter_join() {
let mut stroker = Stroker::new(&StrokeStyle{
cap: LineCap::Square,
join: LineJoin::Miter,
width: 1.0,
..Default::default()});
stroker.move_to(Point::new(-204.48355, 528.4429), false);
stroker.line_to(Point::new(-203.89037, 529.0532));
stroker.line_to(Point::new(-202.58539, 530.396,));
stroker.line_to(Point::new(-201.2804, 531.73883,));
stroker.line_to(Point::new(-200.68721, 532.3492,));
let result = stroker.finish();
// make sure none of the verticies are wildly out of place
for v in result.iter() {
assert!(v.y >= 527.);
}
let mut stroker = Stroker::new(&StrokeStyle{
cap: LineCap::Square,
join: LineJoin::Miter,
width: 40.0,
..Default::default()});
fn distance_from_line(p1: Point, p2: Point, x: Point) -> f32 {
((p2.x - p1.x)*(p1.y - x.y) - (p1.x - x.x)*(p2.y - p1.y)).abs() /
((p2.x - p1.x).powi(2) + (p2.y - p1.y).powi(2)).sqrt()
}
let start = Point::new(512., 599.);
let end = Point::new(513.51666, 597.47736);
stroker.move_to(start, false);
stroker.line_to(Point::new(512.3874, 598.6111));
stroker.line_to_capped(end);
let result = stroker.finish();
for v in result.iter() {
assert!(distance_from_line(start, end, Point::new(v.x, v.y)) <= 21.);
}
fn minimum_distance(v: Point, w: Point, p: Point) -> f32 {
// Return minimum distance between line segment vw and point p
let l2 = (v-w).length().powi(2); // i.e. |w-v|^2 - avoid a sqrt
if l2 == 0.0 { return (p - v).length(); } // v == w case
// Consider the line extending the segment, parameterized as v + t (w - v).
// We find projection of point p onto the line.
// It falls where t = [(p-v) . (w-v)] / |w-v|^2
// We clamp t from [0,1] to handle points outside the segment vw.
let t = 0_f32.max(1_f32.min(dot(p - v, w - v) / l2));
let projection = v + (w - v) * t; // Projection falls on the segment
(p - projection).length()
}
let mut stroker = Stroker::new(&StrokeStyle{
cap: LineCap::Square,
join: LineJoin::Miter,
width: 40.0,
miter_limit: 10.0,
..Default::default()});
let start = Point::new(689.3504, 434.5446);
let end = Point::new(671.83203, 422.61914);
stroker.move_to(Point::new(689.3504, 434.5446), false);
stroker.line_to(Point::new(681.04254, 428.8891));
stroker.line_to_capped(Point::new(671.83203, 422.61914));
let result = stroker.finish();
let max_distance = (21_f32.powi(2) * 2.).sqrt();
for v in result.iter() {
assert!(minimum_distance(start, end, Point::new(v.x, v.y)) <= max_distance);
}
}
#[test]
fn nearly_degenerate_bezier() {
let mut stroker = Stroker::new(&StrokeStyle{
cap: LineCap::Square,
join: LineJoin::Miter,
width: 1.0,
..Default::default()});
stroker.move_to(Point::new(0., 0.0005), false);
stroker.curve_to(Point::new(0., 0.0005), Point::new(0., 0.), Point::new(0., 0.));
stroker.finish();
}
#[test]
fn joins_between_curves() {
let mut stroker = Stroker::new(&StrokeStyle{
cap: LineCap::Square,
join: LineJoin::Miter,
width: 40.0,
..Default::default()});
stroker.move_to(Point::new(-80., 20.), false);
stroker.curve_to(Point::new(-80., 20.), Point::new(-5., 20.), Point::new(-5., 20.));
stroker.curve_to(Point::new(-5., 20.), Point::new(-5., 90.), Point::new(-5., 90.));
let vertices = stroker.finish();
let result = rasterize_to_mask(&vertices, 1, 1);
assert_eq!(result[0], 255);
}