use crate::event_queue::*;
use crate::math::*;
use crate::geom::LineSegment;
use crate::monotone::*;
use crate::path::polygon::Polygon;
use crate::path::{
AttributeStore, EndpointId, FillRule, IdEvent, PathEvent, PathSlice, PositionStore, Winding
};
use crate::path::traits::{PathBuilder, Build};
use crate::{FillGeometryBuilder, Orientation, VertexId};
use crate::{
FillOptions, InternalError, Side, TessellationError, TessellationResult, VertexSource,
};
use std::cmp::Ordering;
use std::f32;
use std::ops::Range;
use std::mem;
#[cfg(debug_assertions)]
use std::env;
type SpanIdx = i32;
type ActiveEdgeIdx = usize;
#[inline(always)]
fn fmax(a: f32, b: f32) -> f32 {
if a > b { a } else { b }
}
fn slope(v: Vector) -> f32 {
v.x / (v.y.max(std::f32::MIN))
}
#[cfg(debug_assertions)]
macro_rules! tess_log {
($obj:ident, $fmt:expr) => (
if $obj.log {
println!($fmt);
}
);
($obj:ident, $fmt:expr, $($arg:tt)*) => (
if $obj.log {
println!($fmt, $($arg)*);
}
);
}
#[cfg(not(debug_assertions))]
macro_rules! tess_log {
($obj:ident, $fmt:expr) => {};
($obj:ident, $fmt:expr, $($arg:tt)*) => {};
}
#[derive(Copy, Clone, Debug)]
struct WindingState {
span_index: SpanIdx,
number: i16,
is_in: bool,
}
impl WindingState {
fn new() -> Self {
WindingState {
span_index: -1,
number: 0,
is_in: false,
}
}
fn update(&mut self, fill_rule: FillRule, edge_winding: i16) {
self.number += edge_winding;
self.is_in = fill_rule.is_in(self.number);
if self.is_in {
self.span_index += 1;
}
}
}
struct ActiveEdgeScan {
vertex_events: Vec<(SpanIdx, Side)>,
edges_to_split: Vec<ActiveEdgeIdx>,
spans_to_end: Vec<SpanIdx>,
merge_event: bool,
split_event: bool,
merge_split_event: bool,
above: Range<ActiveEdgeIdx>,
winding_before_point: WindingState,
}
impl ActiveEdgeScan {
fn new() -> Self {
ActiveEdgeScan {
vertex_events: Vec::new(),
edges_to_split: Vec::new(),
spans_to_end: Vec::new(),
merge_event: false,
split_event: false,
merge_split_event: false,
above: 0..0,
winding_before_point: WindingState::new(),
}
}
fn reset(&mut self) {
self.vertex_events.clear();
self.edges_to_split.clear();
self.spans_to_end.clear();
self.merge_event = false;
self.split_event = false;
self.merge_split_event = false;
self.above = 0..0;
self.winding_before_point = WindingState::new();
}
}
#[derive(Copy, Clone, Debug)]
struct ActiveEdge {
from: Point,
to: Point,
winding: i16,
is_merge: bool,
from_id: VertexId,
src_edge: TessEventId,
range_end: f32,
}
#[test]
fn active_edge_size() {
assert_eq!(std::mem::size_of::<ActiveEdge>(), 32);
}
impl ActiveEdge {
#[inline(always)]
fn min_x(&self) -> f32 {
self.from.x.min(self.to.x)
}
#[inline(always)]
fn max_x(&self) -> f32 {
fmax(self.from.x, self.to.x)
}
}
impl ActiveEdge {
fn solve_x_for_y(&self, y: f32) -> f32 {
LineSegment {
from: self.from,
to: self.to,
}
.solve_x_for_y(y)
.max(self.min_x())
.min(self.max_x())
}
}
struct ActiveEdges {
edges: Vec<ActiveEdge>,
}
struct Span {
tess: Option<Box<MonotoneTessellator>>,
}
impl Span {
fn tess(&mut self) -> &mut Box<MonotoneTessellator> {
match self.tess.as_mut() {
None => {
debug_assert!(false);
unreachable!();
},
Some(tess) => tess
}
}
}
struct Spans {
spans: Vec<Span>,
pool: Vec<Box<MonotoneTessellator>>,
}
impl Spans {
fn begin_span(&mut self, span_idx: SpanIdx, position: &Point, vertex: VertexId) {
let mut tess = self.pool.pop()
.unwrap_or_else(|| Box::new(MonotoneTessellator::new()));
tess.begin(*position, vertex);
self.spans.insert(
span_idx as usize,
Span { tess: Some(tess), }
);
}
fn end_span(
&mut self,
span_idx: SpanIdx,
position: &Point,
id: VertexId,
output: &mut dyn FillGeometryBuilder,
) {
let idx = span_idx as usize;
let span = &mut self.spans[idx];
if let Some(mut tess) = span.tess.take() {
tess.end(*position, id);
tess.flush(output);
self.pool.push(tess);
} else {
debug_assert!(false);
unreachable!();
}
}
fn merge_spans(
&mut self,
left_span_idx: SpanIdx,
current_position: &Point,
current_vertex: VertexId,
merge_position: &Point,
merge_vertex: VertexId,
output: &mut dyn FillGeometryBuilder,
) {
let right_span_idx = left_span_idx + 1;
self.spans[left_span_idx as usize]
.tess()
.vertex(*merge_position, merge_vertex, Side::Right);
self.spans[right_span_idx as usize]
.tess()
.vertex(*merge_position, merge_vertex, Side::Left);
self.end_span(left_span_idx, current_position, current_vertex, output);
}
fn cleanup_spans(&mut self) {
self.spans.retain(|span| !span.tess.is_none());
}
}
#[derive(Copy, Clone, Debug)]
struct PendingEdge {
to: Point,
sort_key: f32,
src_edge: TessEventId,
winding: i16,
range_end: f32,
}
pub struct FillTessellator {
current_position: Point,
current_vertex: VertexId,
current_event_id: TessEventId,
active: ActiveEdges,
edges_below: Vec<PendingEdge>,
fill_rule: FillRule,
orientation: Orientation,
tolerance: f32,
fill: Spans,
log: bool,
assume_no_intersection: bool,
attrib_buffer: Vec<f32>,
scan: ActiveEdgeScan,
events: EventQueue,
}
impl FillTessellator {
pub fn new() -> Self {
#[cfg(debug_assertions)]
let log = env::var("LYON_FORCE_LOGGING").is_ok();
#[cfg(not(debug_assertions))]
let log = false;
FillTessellator {
current_position: point(f32::MIN, f32::MIN),
current_vertex: VertexId::INVALID,
current_event_id: INVALID_EVENT_ID,
active: ActiveEdges { edges: Vec::new() },
edges_below: Vec::new(),
fill_rule: FillRule::EvenOdd,
orientation: Orientation::Vertical,
tolerance: FillOptions::DEFAULT_TOLERANCE,
fill: Spans { spans: Vec::new(), pool: Vec::new() },
log,
assume_no_intersection: false,
attrib_buffer: Vec::new(),
scan: ActiveEdgeScan::new(),
events: EventQueue::new(),
}
}
pub fn tessellate(
&mut self,
path: impl IntoIterator<Item = PathEvent>,
options: &FillOptions,
output: &mut dyn FillGeometryBuilder,
) -> TessellationResult {
let event_queue = std::mem::replace(&mut self.events, EventQueue::new());
let mut queue_builder = event_queue.into_builder();
queue_builder.set_path(
options.tolerance,
options.sweep_orientation,
path.into_iter(),
);
self.events = queue_builder.build();
self.tessellate_impl(options, None, output)
}
pub fn tessellate_with_ids(
&mut self,
path: impl IntoIterator<Item = IdEvent>,
positions: &impl PositionStore,
custom_attributes: Option<&dyn AttributeStore>,
options: &FillOptions,
output: &mut dyn FillGeometryBuilder,
) -> TessellationResult {
let event_queue = std::mem::replace(&mut self.events, EventQueue::new());
let mut queue_builder = event_queue.into_builder();
queue_builder.set_path_with_ids(
options.tolerance,
options.sweep_orientation,
path.into_iter(),
positions,
);
self.events = queue_builder.build();
self.tessellate_impl(options, custom_attributes, output)
}
pub fn tessellate_path<'l>(
&'l mut self,
path: impl Into<PathSlice<'l>>,
options: &'l FillOptions,
builder: &'l mut dyn FillGeometryBuilder,
) -> TessellationResult {
let path = path.into();
if path.num_attributes() > 0 {
self.tessellate_with_ids(path.id_iter(), &path, Some(&path), options, builder)
} else {
self.tessellate(path.iter(), options, builder)
}
}
pub fn tessellate_polygon(
&mut self,
polygon: Polygon<Point>,
options: &FillOptions,
output: &mut dyn FillGeometryBuilder,
) -> TessellationResult {
self.tessellate(
polygon.path_events(),
options,
output,
)
}
pub fn tessellate_rectangle(
&mut self,
rect: &Rect,
options: &FillOptions,
output: &mut dyn FillGeometryBuilder,
) -> TessellationResult {
let mut builder = self.builder(options, output);
builder.add_rectangle(rect, Winding::Positive);
builder.build()
}
pub fn tessellate_circle(
&mut self,
center: Point,
radius: f32,
options: &FillOptions,
output: &mut dyn FillGeometryBuilder,
) -> TessellationResult {
let mut builder = self.builder(options, output);
builder.add_circle(center, radius, Winding::Positive);
builder.build()
}
pub fn tessellate_ellipse(
&mut self,
center: Point,
radii: Vector,
x_rotation: Angle,
winding: Winding,
options: &FillOptions,
output: &mut dyn FillGeometryBuilder,
) -> TessellationResult {
let mut builder = self.builder(options, output);
builder.add_ellipse(center, radii, x_rotation, winding);
builder.build()
}
pub fn builder<'l>(
&'l mut self,
options: &'l FillOptions,
output: &'l mut dyn FillGeometryBuilder,
) -> FillBuilder<'l> {
FillBuilder::new(self, options, output)
}
fn tessellate_impl(
&mut self,
options: &FillOptions,
attrib_store: Option<&dyn AttributeStore>,
builder: &mut dyn FillGeometryBuilder,
) -> TessellationResult {
if options.tolerance.is_nan() || options.tolerance <= 0.0 {
return Err(TessellationError::UnsupportedParamater);
}
self.reset();
if let Some(store) = attrib_store {
self.attrib_buffer.resize(store.num_attributes(), 0.0);
} else {
self.attrib_buffer.clear();
}
self.fill_rule = options.fill_rule;
self.orientation = options.sweep_orientation;
self.tolerance = options.tolerance * 0.5;
self.assume_no_intersection = !options.handle_intersections;
builder.begin_geometry();
let mut scan = mem::replace(&mut self.scan, ActiveEdgeScan::new());
let result = self.tessellator_loop(attrib_store, &mut scan, builder);
mem::swap(&mut self.scan, &mut scan);
if let Err(e) = result {
tess_log!(self, "Tessellation failed with error: {:?}.", e);
builder.abort_geometry();
return Err(e);
}
if !self.assume_no_intersection {
debug_assert!(self.active.edges.is_empty());
debug_assert!(self.fill.spans.is_empty());
}
for span in &mut self.fill.spans {
if let Some(tess) = span.tess.as_mut() {
tess.flush(builder);
}
}
self.fill.spans.clear();
Ok(builder.end_geometry())
}
pub fn set_logging(&mut self, is_enabled: bool) {
#[cfg(debug_assertions)]
let forced = env::var("LYON_FORCE_LOGGING").is_ok();
#[cfg(not(debug_assertions))]
let forced = false;
self.log = is_enabled || forced;
}
#[cfg_attr(feature = "profiling", inline(never))]
fn tessellator_loop(
&mut self,
attrib_store: Option<&dyn AttributeStore>,
scan: &mut ActiveEdgeScan,
output: &mut dyn FillGeometryBuilder,
) -> Result<(), TessellationError> {
log_svg_preamble(self);
let mut _prev_position = point(std::f32::MIN, std::f32::MIN);
self.current_event_id = self.events.first_id();
while self.events.valid_id(self.current_event_id) {
self.initialize_events(attrib_store, output)?;
debug_assert!(is_after(self.current_position, _prev_position));
_prev_position = self.current_position;
if let Err(e) = self.process_events(scan, output) {
self.recover_from_error(e, output);
self.process_events(scan, output)?
}
#[cfg(debug_assertions)]
self.check_active_edges();
self.current_event_id = self.events.next_id(self.current_event_id);
}
Ok(())
}
fn initialize_events(
&mut self,
attrib_store: Option<&dyn AttributeStore>,
output: &mut dyn FillGeometryBuilder,
) -> Result<(), TessellationError> {
let current_event = self.current_event_id;
tess_log!(
self,
"\n\n<!-- event #{} -->",
current_event
);
self.current_position = self.events.position(current_event);
if self.current_position.x.is_nan() || self.current_position.y.is_nan() {
return Err(TessellationError::UnsupportedParamater);
}
let position = match self.orientation {
Orientation::Vertical => self.current_position,
Orientation::Horizontal => reorient(self.current_position),
};
self.current_vertex = output.add_fill_vertex(
FillVertex {
position,
events: &self.events,
current_event,
attrib_store,
attrib_buffer: &mut self.attrib_buffer,
},
)?;
let mut current_sibling = current_event;
while self.events.valid_id(current_sibling) {
let edge = &self.events.edge_data[current_sibling as usize];
if edge.is_edge {
let to = edge.to;
debug_assert!(is_after(to, self.current_position));
self.edges_below.push(PendingEdge {
to,
sort_key: slope(to - self.current_position),
src_edge: current_sibling,
winding: edge.winding,
range_end: edge.range.end,
});
}
current_sibling = self.events.next_sibling_id(current_sibling);
}
Ok(())
}
#[cfg_attr(feature = "profiling", inline(never))]
fn process_events(
&mut self,
scan: &mut ActiveEdgeScan,
output: &mut dyn FillGeometryBuilder,
) -> Result<(), InternalError> {
tess_log!(self, "<!--");
tess_log!(
self,
" events at {:?} {:?} {} edges below",
self.current_position,
self.current_vertex,
self.edges_below.len(),
);
tess_log!(self, "edges below (initially): {:#?}", self.edges_below);
self.scan_active_edges(scan)?;
self.process_edges_above(scan, output);
self.process_edges_below(scan);
self.update_active_edges(scan);
tess_log!(self, "-->");
#[cfg(debug_assertions)]
self.log_active_edges();
Ok(())
}
#[cfg(debug_assertions)]
fn log_active_edges(&self) {
tess_log!(self, r#"<g class="active-edges">"#);
tess_log!(
self,
r#"<path d="M 0 {} L 1000 {}" class="sweep-line"/>"#,
self.current_position.y,
self.current_position.y
);
tess_log!(self, "<!-- active edges: -->");
for e in &self.active.edges {
if e.is_merge {
tess_log!(
self,
r#" <circle cx="{}" cy="{}" r="3px" class="merge"/>"#,
e.from.x,
e.from.y
);
} else {
tess_log!(
self,
r#" <path d="M {:.5?} {:.5?} L {:.5?} {:.5?}" class="edge", winding="{:>2}"/>"#,
e.from.x,
e.from.y,
e.to.x,
e.to.y,
e.winding,
);
}
}
tess_log!(self, "<!-- spans: {}-->", self.fill.spans.len());
tess_log!(self, "</g>");
}
#[cfg(debug_assertions)]
fn check_active_edges(&self) {
let mut winding = WindingState::new();
for (idx, edge) in self.active.edges.iter().enumerate() {
winding.update(self.fill_rule, edge.winding);
if edge.is_merge {
assert!(self.fill_rule.is_in(winding.number));
} else {
assert!(!is_after(self.current_position, edge.to), "error at edge {}, position {:?}", idx, edge.to);
}
}
assert_eq!(winding.number, 0);
let expected_span_count = (winding.span_index + 1) as usize;
assert_eq!(self.fill.spans.len(), expected_span_count);
}
#[cfg_attr(feature = "profiling", inline(never))]
fn scan_active_edges(&self, scan: &mut ActiveEdgeScan) -> Result<(), InternalError> {
scan.reset();
let current_x = self.current_position.x;
let mut connecting_edges = false;
let mut active_edge_idx = 0;
let mut winding = WindingState::new();
let mut previous_was_merge = false;
for active_edge in &self.active.edges {
if active_edge.is_merge {
winding.span_index += 1;
active_edge_idx += 1;
previous_was_merge = true;
continue;
}
let egde_is_before_current_point =
if points_are_equal(self.current_position, active_edge.to) {
connecting_edges = true;
false
} else if active_edge.max_x() < current_x {
true
} else if active_edge.min_x() > current_x {
tess_log!(
self,
"min_x({:?}) > current_x({:?})",
active_edge.min_x(),
current_x
);
false
} else if active_edge.from.y == active_edge.to.y {
connecting_edges = true;
false
} else {
let ex = active_edge.solve_x_for_y(self.current_position.y);
if (ex - current_x).abs() <= self.tolerance {
connecting_edges = true;
false
} else if ex > current_x {
tess_log!(self, "ex({:?}) > current_x({:?})", ex, current_x);
false
} else {
true
}
};
if !egde_is_before_current_point {
break;
}
winding.update(self.fill_rule, active_edge.winding);
previous_was_merge = false;
active_edge_idx += 1;
tess_log!(
self,
" > span: {}, in: {}",
winding.span_index,
winding.is_in
);
}
scan.above.start = active_edge_idx;
scan.winding_before_point = winding.clone();
if previous_was_merge {
scan.winding_before_point.span_index -= 1;
scan.above.start -= 1;
if !connecting_edges {
scan.vertex_events
.push((winding.span_index - 1, Side::Right));
scan.vertex_events.push((winding.span_index, Side::Left));
scan.merge_split_event = true;
tess_log!(self, "split+merge");
}
}
scan.split_event = !connecting_edges && winding.is_in && !scan.merge_split_event;
tess_log!(
self,
"connecting_edges {} | edge {} | span {}",
connecting_edges,
active_edge_idx,
winding.span_index
);
if connecting_edges {
let in_before_vertex = winding.is_in;
let mut first_connecting_edge = !previous_was_merge;
for active_edge in &self.active.edges[active_edge_idx..] {
if active_edge.is_merge {
if !winding.is_in {
return Err(InternalError::MergeVertexOutside);
}
scan.spans_to_end.push(winding.span_index);
winding.span_index += 1;
active_edge_idx += 1;
first_connecting_edge = false;
continue;
}
if !self.is_edge_connecting(active_edge, active_edge_idx, scan)? {
break;
}
if !first_connecting_edge && winding.is_in {
scan.spans_to_end.push(winding.span_index);
}
winding.update(self.fill_rule, active_edge.winding);
tess_log!(
self,
" x span: {} in: {}",
winding.span_index,
winding.is_in
);
if winding.is_in && winding.span_index >= self.fill.spans.len() as i32 {
return Err(InternalError::InsufficientNumberOfSpans);
}
active_edge_idx += 1;
first_connecting_edge = false;
}
let in_after_vertex = winding.is_in;
let vertex_is_merge_event = in_before_vertex
&& in_after_vertex
&& self.edges_below.is_empty()
&& scan.edges_to_split.is_empty();
if vertex_is_merge_event {
scan.merge_event = true;
}
if in_before_vertex {
let first_span_index = scan.winding_before_point.span_index;
scan.vertex_events.push((first_span_index, Side::Right));
}
if in_after_vertex {
scan.vertex_events.push((winding.span_index, Side::Left));
}
}
tess_log!(self, "edges after | {}", active_edge_idx);
scan.above.end = active_edge_idx;
self.check_remaining_edges(active_edge_idx, current_x)
}
#[cfg_attr(feature = "profiling", inline(never))]
#[cfg_attr(not(feature = "profiling"), inline(always))]
fn check_remaining_edges(&self, active_edge_idx: usize, current_x: f32) -> Result<(), InternalError> {
for active_edge in &self.active.edges[active_edge_idx..] {
if active_edge.is_merge {
continue;
}
if active_edge.max_x() < current_x {
return Err(InternalError::IncorrectActiveEdgeOrder(1));
}
if points_are_equal(self.current_position, active_edge.to) {
return Err(InternalError::IncorrectActiveEdgeOrder(2));
}
if active_edge.min_x() < current_x
&& active_edge.solve_x_for_y(self.current_position.y) < current_x
{
return Err(InternalError::IncorrectActiveEdgeOrder(3));
}
}
Ok(())
}
fn is_edge_connecting(
&self,
active_edge: &ActiveEdge,
active_edge_idx: usize,
scan: &mut ActiveEdgeScan,
) -> Result<bool, InternalError> {
if points_are_equal(self.current_position, active_edge.to) {
return Ok(true);
}
let current_x = self.current_position.x;
let threshold = self.tolerance;
let min_x = active_edge.min_x();
let max_x = active_edge.max_x();
if max_x + threshold < current_x || active_edge.to.y < self.current_position.y {
return Err(InternalError::IncorrectActiveEdgeOrder(4));
}
if min_x > current_x {
return Ok(false);
}
let ex = if active_edge.from.y != active_edge.to.y {
active_edge.solve_x_for_y(self.current_position.y)
} else if max_x >= current_x && min_x <= current_x {
current_x
} else {
active_edge.to.y
};
if (ex - current_x).abs() <= threshold {
tess_log!(
self,
"vertex on an edge! {:?} -> {:?}",
active_edge.from,
active_edge.to
);
scan.edges_to_split.push(active_edge_idx);
return Ok(true);
}
if ex < current_x {
return Err(InternalError::IncorrectActiveEdgeOrder(5));
}
tess_log!(self, "ex = {:?} (diff={})", ex, ex - current_x);
Ok(false)
}
#[cfg_attr(feature = "profiling", inline(never))]
fn process_edges_above(
&mut self,
scan: &mut ActiveEdgeScan,
output: &mut dyn FillGeometryBuilder,
) {
for &(span_index, side) in &scan.vertex_events {
tess_log!(
self,
" -> Vertex event, span: {:?} / {:?} / id: {:?}",
span_index,
side,
self.current_vertex
);
self.fill.spans[span_index as usize].tess().vertex(
self.current_position,
self.current_vertex,
side,
);
}
for &span_index in &scan.spans_to_end {
tess_log!(self, " -> End span {:?}", span_index);
self.fill.end_span(
span_index,
&self.current_position,
self.current_vertex,
output,
);
}
self.fill.cleanup_spans();
for &edge_idx in &scan.edges_to_split {
let active_edge = &mut self.active.edges[edge_idx];
let to = active_edge.to;
self.edges_below.push(PendingEdge {
to,
sort_key: slope(to - self.current_position),
src_edge: active_edge.src_edge,
winding: active_edge.winding,
range_end: active_edge.range_end,
});
tess_log!(
self,
"split {:?}, add edge below {:?} -> {:?} ({:?})",
edge_idx,
self.current_position,
self.edges_below.last().unwrap().to,
active_edge.winding,
);
active_edge.to = self.current_position;
}
if scan.merge_event {
let edge = &mut self.active.edges[scan.above.start];
edge.is_merge = true;
edge.from = edge.to;
edge.winding = 0;
edge.from_id = self.current_vertex;
scan.above.start += 1;
}
}
#[cfg_attr(feature = "profiling", inline(never))]
fn process_edges_below(&mut self, scan: &mut ActiveEdgeScan) {
let mut winding = scan.winding_before_point.clone();
tess_log!(
self,
"connecting edges: {}..{} in: {:?}",
scan.above.start,
scan.above.end,
winding.is_in
);
tess_log!(self, "winding state before point: {:?}", winding);
tess_log!(self, "edges below: {:#?}", self.edges_below);
self.sort_edges_below();
self.handle_coincident_edges_below();
if scan.split_event {
tess_log!(self, "split event");
let left_enclosing_edge_idx = scan.above.start - 1;
self.split_event(left_enclosing_edge_idx, winding.span_index);
}
let mut first_pending_edge = true;
for pending_edge in &self.edges_below {
if !first_pending_edge && winding.is_in {
tess_log!(
self,
" begin span {} ({})",
winding.span_index,
self.fill.spans.len()
);
self.fill.begin_span(
winding.span_index,
&self.current_position,
self.current_vertex,
);
}
winding.update(self.fill_rule, pending_edge.winding);
tess_log!(
self,
"edge below: span: {}, in: {}",
winding.span_index,
winding.is_in
);
first_pending_edge = false;
}
}
#[cfg_attr(feature = "profiling", inline(never))]
fn update_active_edges(&mut self, scan: &ActiveEdgeScan) {
let above = scan.above.start..scan.above.end;
tess_log!(
self,
" remove {} edges ({}..{})",
above.end - above.start,
above.start,
above.end
);
if !self.assume_no_intersection {
self.handle_intersections(above.clone());
}
#[cfg(debug_assertions)]
for active_edge in &self.active.edges[above.clone()] {
debug_assert!(
active_edge.is_merge || !is_after(self.current_position, active_edge.to)
);
}
let from = self.current_position;
let from_id = self.current_vertex;
self.active.edges.splice(
above,
self.edges_below.iter().map(|edge| {
ActiveEdge {
from,
to: edge.to,
winding: edge.winding,
is_merge: false,
from_id,
src_edge: edge.src_edge,
range_end: edge.range_end,
}
}),
);
self.edges_below.clear();
}
fn split_event(&mut self, left_enclosing_edge_idx: ActiveEdgeIdx, left_span_idx: SpanIdx) {
let right_enclosing_edge_idx = left_enclosing_edge_idx + 1;
let upper_left = self.active.edges[left_enclosing_edge_idx].from;
let upper_right = self.active.edges[right_enclosing_edge_idx].from;
let right_span_idx = left_span_idx + 1;
let (upper_position, upper_id, new_span_idx) = if is_after(upper_left, upper_right) {
(
upper_left,
self.active.edges[left_enclosing_edge_idx].from_id,
left_span_idx,
)
} else {
(
upper_right,
self.active.edges[right_enclosing_edge_idx].from_id,
right_span_idx,
)
};
self.fill.begin_span(new_span_idx, &upper_position, upper_id);
self.fill.spans[left_span_idx as usize].tess().vertex(
self.current_position,
self.current_vertex,
Side::Right,
);
self.fill.spans[right_span_idx as usize].tess().vertex(
self.current_position,
self.current_vertex,
Side::Left,
);
}
#[cfg_attr(feature = "profiling", inline(never))]
fn handle_intersections(&mut self, skip_range: Range<usize>) {
let mut edges_below = mem::replace(&mut self.edges_below, Vec::new());
for edge_below in &mut edges_below {
let below_min_x = self.current_position.x.min(edge_below.to.x);
let below_max_x = fmax(self.current_position.x, edge_below.to.x);
let below_segment = LineSegment {
from: self.current_position.to_f64(),
to: edge_below.to.to_f64(),
};
let mut tb_min = 1.0;
let mut intersection = None;
for (i, active_edge) in self.active.edges.iter().enumerate() {
if skip_range.contains(&i) {
continue;
}
if active_edge.is_merge || below_min_x > active_edge.max_x() {
continue;
}
if below_max_x < active_edge.min_x() {
continue;
}
let active_segment = LineSegment {
from: active_edge.from.to_f64(),
to: active_edge.to.to_f64(),
};
if let Some((ta, tb)) = active_segment.intersection_t(&below_segment) {
if tb < tb_min && tb > 0.0 && ta > 0.0 && ta <= 1.0 {
tb_min = tb;
intersection = Some((ta, tb, i));
}
}
}
if let Some((ta, tb, active_edge_idx)) = intersection {
self.process_intersection(ta, tb, active_edge_idx, edge_below, &below_segment);
}
}
self.edges_below = edges_below;
}
#[inline(never)]
fn process_intersection(
&mut self,
ta: f64,
tb: f64,
active_edge_idx: usize,
edge_below: &mut PendingEdge,
below_segment: &LineSegment<f64>
) {
let mut intersection_position = below_segment.sample(tb).to_f32();
tess_log!(self, "-> intersection at: {:?} t={:?}|{:?}", intersection_position, ta, tb);
tess_log!(
self,
" from {:?}->{:?} and {:?}->{:?}",
self.active.edges[active_edge_idx].from,
self.active.edges[active_edge_idx].to,
self.current_position,
edge_below.to,
);
let active_edge = &mut self.active.edges[active_edge_idx];
if self.current_position == intersection_position {
active_edge.from = intersection_position;
let src_range = &mut self.events.edge_data[active_edge.src_edge as usize].range;
let remapped_ta =
remap_t_in_range(ta as f32, src_range.start..active_edge.range_end);
src_range.start = remapped_ta;
return;
}
if intersection_position.y < self.current_position.y {
tess_log!(self, "fixup the intersection because of y coordinate");
intersection_position.y = self.current_position.y + 0.0001;
} else if intersection_position.y == self.current_position.y
&& intersection_position.x < self.current_position.x
{
tess_log!(self, "fixup the intersection because of x coordinate");
intersection_position.y = self.current_position.y + 0.0001;
}
if is_near(intersection_position, edge_below.to) {
tess_log!(self, "intersection near below.to");
intersection_position = edge_below.to;
} else if is_near(intersection_position, active_edge.to) {
tess_log!(self, "intersection near active_edge.to");
intersection_position = active_edge.to;
}
let a_src_edge_data = self.events.edge_data[active_edge.src_edge as usize].clone();
let b_src_edge_data = self.events.edge_data[edge_below.src_edge as usize].clone();
let mut inserted_evt = None;
let mut flipped_active = false;
if active_edge.to != intersection_position
&& active_edge.from != intersection_position
{
let remapped_ta = remap_t_in_range(
ta as f32,
a_src_edge_data.range.start..active_edge.range_end,
);
if is_after(active_edge.to, intersection_position) {
inserted_evt = Some(self.events.insert_sorted(
intersection_position,
EdgeData {
range: remapped_ta as f32..active_edge.range_end,
winding: active_edge.winding,
to: active_edge.to,
is_edge: true,
..a_src_edge_data
},
self.current_event_id,
));
} else {
tess_log!(self, "flip active edge after intersection");
flipped_active = true;
self.events.insert_sorted(
active_edge.to,
EdgeData {
range: active_edge.range_end..remapped_ta as f32,
winding: -active_edge.winding,
to: intersection_position,
is_edge: true,
..a_src_edge_data
},
self.current_event_id,
);
}
active_edge.to = intersection_position;
active_edge.range_end = remapped_ta;
}
if edge_below.to != intersection_position
&& self.current_position != intersection_position
{
let remapped_tb = remap_t_in_range(
tb as f32,
b_src_edge_data.range.start..edge_below.range_end,
);
if is_after(edge_below.to, intersection_position) {
let edge_data = EdgeData {
range: remapped_tb as f32..edge_below.range_end,
winding: edge_below.winding,
to: edge_below.to,
is_edge: true,
..b_src_edge_data
};
if let Some(idx) = inserted_evt {
self.events
.insert_sibling(idx, intersection_position, edge_data);
} else {
self.events.insert_sorted(
intersection_position,
edge_data,
self.current_event_id,
);
}
} else {
tess_log!(self, "flip edge below after intersection");
self.events.insert_sorted(
edge_below.to,
EdgeData {
range: edge_below.range_end..remapped_tb as f32,
winding: -edge_below.winding,
to: intersection_position,
is_edge: true,
..b_src_edge_data
},
self.current_event_id,
);
if flipped_active {
self.events.vertex_event_sorted(
intersection_position,
b_src_edge_data.to_id,
self.current_event_id,
);
}
}
edge_below.to = intersection_position;
edge_below.range_end = remapped_tb;
}
}
fn sort_active_edges(&mut self) {
let y = self.current_position.y;
let mut keys = Vec::with_capacity(self.active.edges.len());
let mut has_merge_vertex = false;
let mut prev_x = f32::NAN;
for (i, edge) in self.active.edges.iter().enumerate() {
if edge.is_merge {
debug_assert!(!prev_x.is_nan());
has_merge_vertex = true;
keys.push((prev_x, i));
} else {
debug_assert!(!is_after(self.current_position, edge.to));
let eq_to = edge.to.y == y;
let eq_from = edge.from.y == y;
let x = if eq_to && eq_from {
let current_x = self.current_position.x;
if edge.max_x() >= current_x && edge.min_x() <= current_x {
self.current_position.x
} else {
edge.min_x()
}
} else if eq_from {
edge.from.x
} else if eq_to {
edge.to.x
} else {
edge.solve_x_for_y(y)
};
keys.push((fmax(x, edge.min_x()), i));
prev_x = x;
}
}
keys.sort_by(|a, b| match a.0.partial_cmp(&b.0).unwrap() {
Ordering::Less => Ordering::Less,
Ordering::Greater => Ordering::Greater,
Ordering::Equal => {
let a = &self.active.edges[a.1];
let b = &self.active.edges[b.1];
match (a.is_merge, b.is_merge) {
(false, false) => {
let slope_a = slope(a.to - a.from);
let slope_b = slope(b.to - b.from);
slope_b.partial_cmp(&slope_a).unwrap_or(Ordering::Equal)
}
(true, false) => Ordering::Greater,
(false, true) => Ordering::Less,
(true, true) => Ordering::Equal,
}
},
});
let mut new_active_edges = Vec::with_capacity(self.active.edges.len());
for &(_, idx) in &keys {
new_active_edges.push(self.active.edges[idx]);
}
self.active.edges = new_active_edges;
if !has_merge_vertex {
return;
}
let mut winding_number = 0;
for i in 0..self.active.edges.len() {
let needs_swap = {
let edge = &self.active.edges[i];
if edge.is_merge {
!self.fill_rule.is_in(winding_number)
} else {
winding_number += edge.winding;
false
}
};
if needs_swap {
let mut w = winding_number;
tess_log!(self, "Fixing up merge vertex after sort.");
let mut idx = i;
loop {
w -= self.active.edges[idx - 1].winding;
self.active.edges.swap(idx, idx - 1);
if self.fill_rule.is_in(w) {
break;
}
idx -= 1;
}
}
}
}
#[inline(never)]
fn recover_from_error(&mut self, _error: InternalError, output: &mut dyn FillGeometryBuilder) {
tess_log!(self, "Attempt to recover error {:?}", _error);
self.sort_active_edges();
debug_assert!(self
.active
.edges
.first()
.map(|e| !e.is_merge)
.unwrap_or(true));
let len = self.active.edges.len();
if len > 1 && self.active.edges[len - 1].is_merge {
self.active.edges.swap(len - 1, len - 2);
}
let mut winding = WindingState::new();
for edge in &self.active.edges {
if edge.is_merge {
winding.span_index += 1;
} else {
winding.update(self.fill_rule, edge.winding);
}
if winding.span_index >= self.fill.spans.len() as i32 {
self.fill
.begin_span(winding.span_index, &edge.from, edge.from_id);
}
}
while self.fill.spans.len() > (winding.span_index + 1) as usize {
self.fill.spans.last_mut().unwrap().tess().flush(output);
self.fill.spans.pop();
}
tess_log!(self, "-->");
#[cfg(debug_assertions)]
self.log_active_edges();
}
#[cfg_attr(feature = "profiling", inline(never))]
fn sort_edges_below(&mut self) {
self.edges_below.sort_unstable_by(
|a, b| a.sort_key.partial_cmp(&b.sort_key).unwrap()
);
}
#[cfg_attr(feature = "profiling", inline(never))]
fn handle_coincident_edges_below(&mut self) {
if self.edges_below.len() < 2 {
return;
}
for idx in (0..(self.edges_below.len() - 1)).rev() {
let a_idx = idx;
let b_idx = idx + 1;
let a_slope = self.edges_below[a_idx].sort_key;
let b_slope = self.edges_below[b_idx].sort_key;
const THRESHOLD: f32 = 0.00005;
let angle_is_close = if a_slope.abs() <= 1.0 {
(a_slope - b_slope).abs() < THRESHOLD
} else {
(1.0 / a_slope - 1.0 / b_slope).abs() < THRESHOLD
};
if angle_is_close {
self.merge_coincident_edges(a_idx, b_idx);
}
}
}
#[cold]
fn merge_coincident_edges(&mut self, a_idx: usize, b_idx: usize) {
let a_to = self.edges_below[a_idx].to;
let b_to = self.edges_below[b_idx].to;
let (lower_idx, upper_idx, split) = match compare_positions(a_to, b_to) {
Ordering::Greater => (a_idx, b_idx, true),
Ordering::Less => (b_idx, a_idx, true),
Ordering::Equal => (a_idx, b_idx, false),
};
tess_log!(self, "coincident edges {:?} -> {:?} / {:?}", self.current_position, a_to, b_to);
tess_log!(self, "update winding: {:?} -> {:?}", self.edges_below[upper_idx].winding, self.edges_below[upper_idx].winding + self.edges_below[lower_idx].winding);
self.edges_below[upper_idx].winding += self.edges_below[lower_idx].winding;
let split_point = self.edges_below[upper_idx].to;
tess_log!(self, "remove coincident edge {:?}, split:{:?}", a_idx, split);
let edge = self.edges_below.remove(lower_idx);
if !split {
return;
}
let src_edge_data = self.events.edge_data[edge.src_edge as usize].clone();
let t = LineSegment {
from: self.current_position,
to: edge.to,
}.solve_t_for_y(split_point.y);
let src_range = src_edge_data.range.start..edge.range_end;
let t_remapped = remap_t_in_range(t, src_range);
let edge_data = EdgeData {
range: t_remapped..edge.range_end,
winding: edge.winding,
to: edge.to,
is_edge: true,
..src_edge_data
};
self.events.insert_sorted(
split_point,
edge_data,
self.current_event_id,
);
}
fn reset(&mut self) {
self.current_position = point(f32::MIN, f32::MIN);
self.current_vertex = VertexId::INVALID;
self.current_event_id = INVALID_EVENT_ID;
self.active.edges.clear();
self.edges_below.clear();
self.fill.spans.clear();
}
}
pub(crate) fn points_are_equal(a: Point, b: Point) -> bool {
a == b
}
pub(crate) fn compare_positions(a: Point, b: Point) -> Ordering {
if a.y > b.y {
return Ordering::Greater;
}
if a.y < b.y {
return Ordering::Less;
}
if a.x > b.x {
return Ordering::Greater;
}
if a.x < b.x {
return Ordering::Less;
}
return Ordering::Equal;
}
#[inline]
pub(crate) fn is_after(a: Point, b: Point) -> bool {
a.y > b.y || (a.y == b.y && a.x > b.x)
}
#[inline]
pub(crate) fn is_near(a: Point, b: Point) -> bool {
(a - b).square_length() < 0.000000001
}
#[inline]
fn reorient(p: Point) -> Point {
point(p.y, -p.x)
}
pub struct FillVertex<'l> {
position: Point,
events: &'l EventQueue,
current_event: TessEventId,
attrib_buffer: &'l mut [f32],
attrib_store: Option<&'l dyn AttributeStore>,
}
impl<'l> FillVertex<'l> {
pub fn position(&self) -> Point {
self.position
}
pub fn sources(&self) -> VertexSourceIterator {
VertexSourceIterator {
events: self.events,
id: self.current_event,
prev: None,
}
}
pub fn as_endpoint_id(&self) -> Option<EndpointId> {
let mut current = self.current_event;
while self.events.valid_id(current) {
let edge = &self.events.edge_data[current as usize];
let t = edge.range.start;
if t == 0.0 {
return Some(edge.from_id);
}
if t == 1.0 {
return Some(edge.to_id);
}
current = self.events.next_sibling_id(current)
}
None
}
pub fn interpolated_attributes(&mut self) -> &[f32] {
if self.attrib_store.is_none() {
return &[];
}
let store = self.attrib_store.unwrap();
let mut sources = VertexSourceIterator {
events: self.events,
id: self.current_event,
prev: None,
};
let num_attributes = store.num_attributes();
let first = sources.next().unwrap();
let mut next = sources.next();
if next.is_none() {
if let VertexSource::Endpoint { id } = first {
return store.get(id);
}
}
match first {
VertexSource::Endpoint { id } => {
let a = store.get(id);
assert!(a.len() == num_attributes);
assert!(self.attrib_buffer.len() == num_attributes);
for i in 0..num_attributes {
self.attrib_buffer[i] = a[i];
}
}
VertexSource::Edge { from, to, t } => {
let a = store.get(from);
let b = store.get(to);
assert!(a.len() == num_attributes);
assert!(b.len() == num_attributes);
assert!(self.attrib_buffer.len() == num_attributes);
for i in 0..num_attributes {
self.attrib_buffer[i] = a[i] * (1.0 - t) + b[i] * t;
}
}
}
let mut div = 1.0;
loop {
match next {
Some(VertexSource::Endpoint { id }) => {
let a = store.get(id);
assert!(a.len() == num_attributes);
assert!(self.attrib_buffer.len() == num_attributes);
for i in 0..num_attributes {
self.attrib_buffer[i] += a[i];
}
}
Some(VertexSource::Edge { from, to, t }) => {
let a = store.get(from);
let b = store.get(to);
assert!(a.len() == num_attributes);
assert!(b.len() == num_attributes);
assert!(self.attrib_buffer.len() == num_attributes);
for i in 0..num_attributes {
self.attrib_buffer[i] += a[i] * (1.0 - t) + b[i] * t;
}
}
None => {
break;
}
}
div += 1.0;
next = sources.next();
}
if div > 1.0 {
for attribute in &mut self.attrib_buffer[..] {
*attribute /= div;
}
}
self.attrib_buffer
}
}
#[derive(Clone)]
pub struct VertexSourceIterator<'l> {
events: &'l EventQueue,
id: TessEventId,
prev: Option<VertexSource>,
}
impl<'l> Iterator for VertexSourceIterator<'l> {
type Item = VertexSource;
#[inline]
fn next(&mut self) -> Option<VertexSource> {
let mut src;
loop {
if self.id == INVALID_EVENT_ID {
return None;
}
let edge = &self.events.edge_data[self.id as usize];
self.id = self.events.next_sibling_id(self.id);
let t = edge.range.start;
src = if t == 0.0 {
Some(VertexSource::Endpoint { id: edge.from_id })
} else if t == 1.0 {
Some(VertexSource::Endpoint { id: edge.to_id })
} else {
Some(VertexSource::Edge {
from: edge.from_id,
to: edge.to_id,
t,
})
};
if src != self.prev {
break;
}
}
self.prev = src;
src
}
}
fn remap_t_in_range(val: f32, range: Range<f32>) -> f32 {
if range.end > range.start {
let d = range.end - range.start;
range.start + val * d
} else {
let d = range.start - range.end;
range.end + (1.0 - val) * d
}
}
pub struct FillBuilder<'l> {
events: EventQueueBuilder,
next_id: EndpointId,
first_id: EndpointId,
first_position: Point,
horizontal_sweep: bool,
tessellator: &'l mut FillTessellator,
output: &'l mut dyn FillGeometryBuilder,
options: &'l FillOptions,
}
impl<'l> FillBuilder<'l> {
fn new(
tessellator: &'l mut FillTessellator,
options: &'l FillOptions,
output: &'l mut dyn FillGeometryBuilder,
) -> Self {
let event_queue = std::mem::replace(&mut tessellator.events, EventQueue::new());
FillBuilder {
events: event_queue.into_builder(),
next_id: EndpointId(0),
first_id: EndpointId(0),
horizontal_sweep: options.sweep_orientation == Orientation::Horizontal,
first_position: point(0.0, 0.0),
tessellator,
options,
output
}
}
#[inline]
fn position(&self, p: Point) -> Point {
if self.horizontal_sweep {
point(-p.y, p.x)
} else {
p
}
}
pub fn build(self) -> TessellationResult {
let mut event_queue = self.events.build();
std::mem::swap(&mut self.tessellator.events, &mut event_queue);
self.tessellator.tessellate_impl(self.options, None, self.output)
}
}
impl<'l> PathBuilder for FillBuilder<'l> {
fn begin(&mut self, at: Point) -> EndpointId {
let at = self.position(at);
let id = self.next_id;
self.next_id.0 += 1;
self.first_id = id;
self.first_position = at;
self.events.begin(at, id);
id
}
fn end(&mut self, _close: bool) {
self.events.end(self.first_position, self.first_id);
}
fn line_to(&mut self, to: Point) -> EndpointId {
let to = self.position(to);
let id = self.next_id;
self.next_id.0 += 1;
self.events.line_segment(to, id, 0.0, 1.0);
id
}
fn quadratic_bezier_to(&mut self, ctrl: Point, to: Point) -> EndpointId {
let ctrl = self.position(ctrl);
let to = self.position(to);
let id = self.next_id;
self.next_id.0 += 1;
self.events.quadratic_bezier_segment(ctrl, to, id);
id
}
fn cubic_bezier_to(&mut self, ctrl1: Point, ctrl2: Point, to: Point) -> EndpointId {
let ctrl1 = self.position(ctrl1);
let ctrl2 = self.position(ctrl2);
let to = self.position(to);
let id = self.next_id;
self.next_id.0 += 1;
self.events.cubic_bezier_segment(ctrl1, ctrl2, to, id);
id
}
fn reserve(&mut self, endpoints: usize, ctrl_points: usize) {
self.events.reserve(endpoints + ctrl_points * 2);
}
fn add_circle(
&mut self,
center: Point,
radius: f32,
winding: Winding,
) {
let radius = radius.abs();
let dir = match winding {
Winding::Positive => 1.0,
Winding::Negative => -1.0,
};
self.reserve(16, 8);
let tan_pi_over_8 = 0.41421356237;
let cos_pi_over_4 = 0.70710678118;
let d = radius * tan_pi_over_8;
let start = center + vector(-radius, 0.0);
self.begin(start);
let ctrl_0 = center + vector(-radius, -d * dir);
let mid_0 = center + vector(-1.0, -dir) * radius * cos_pi_over_4;
let ctrl_1 = center + vector(-d, -radius * dir);
let mid_1 = center + vector(0.0, -radius * dir);
self.quadratic_bezier_to(ctrl_0, mid_0);
self.end(false);
self.begin(mid_0);
self.quadratic_bezier_to(ctrl_1, mid_1);
self.end(false);
self.begin(mid_1);
let ctrl_0 = center + vector(d, -radius * dir);
let mid_2 = center + vector(1.0, -dir) * radius * cos_pi_over_4;
let ctrl_1 = center + vector(radius, -d * dir);
let mid_3 = center + vector(radius, 0.0);
self.quadratic_bezier_to(ctrl_0, mid_2);
self.end(false);
self.begin(mid_2);
self.quadratic_bezier_to(ctrl_1, mid_3);
self.end(false);
self.begin(mid_3);
let ctrl_0 = center + vector(radius, d * dir);
let mid_4 = center + vector(1.0, dir) * radius * cos_pi_over_4;
let ctrl_1 = center + vector(d, radius * dir);
let mid_5 = center + vector(0.0, radius * dir);
self.quadratic_bezier_to(ctrl_0, mid_4);
self.end(false);
self.begin(mid_4);
self.quadratic_bezier_to(ctrl_1, mid_5);
self.end(false);
self.begin(mid_5);
let ctrl_0 = center + vector(-d, radius * dir);
let mid_6 = center + vector(-1.0, dir) * radius * cos_pi_over_4;
let ctrl_1 = center + vector(-radius, d * dir);
self.quadratic_bezier_to(ctrl_0, mid_6);
self.end(false);
self.begin(mid_6);
self.quadratic_bezier_to(ctrl_1, start);
self.end(false);
self.begin(start);
self.line_to(mid_0);
self.line_to(mid_1);
self.line_to(mid_2);
self.line_to(mid_3);
self.line_to(mid_4);
self.line_to(mid_5);
self.line_to(mid_6);
self.close();
}
}
impl<'l> Build for FillBuilder<'l> {
type PathType = TessellationResult;
#[inline]
fn build(self) -> TessellationResult {
self.build()
}
}
fn log_svg_preamble(_tess: &FillTessellator) {
tess_log!(
_tess,
r#"
<svg viewBox="0 0 1000 1000">
<style type="text/css">
<![CDATA[
path.sweep-line {{
stroke: red;
fill: none;
}}
path.edge {{
stroke: blue;
fill: none;
}}
path.edge.select {{
stroke: green;
fill: none;
}}
circle.merge {{
fill: yellow;
stroke: orange;
fill-opacity: 1;
}}
circle.current {{
fill: white;
stroke: grey;
fill-opacity: 1;
}}
g.active-edges {{
opacity: 0;
}}
g.active-edges.select {{
opacity: 1;
}}
]]>
</style>
"#
);
}
#[cfg(test)]
use crate::geometry_builder::*;
#[cfg(test)]
fn eq(a: Point, b: Point) -> bool {
(a.x - b.x).abs() < 0.00001 && (a.y - b.y).abs() < 0.00001
}
#[cfg(test)]
fn at_endpoint(src: &VertexSource, endpoint: EndpointId) -> bool {
match src {
VertexSource::Edge { .. } => false,
VertexSource::Endpoint { id } => *id == endpoint,
}
}
#[cfg(test)]
fn on_edge(src: &VertexSource, from_id: EndpointId, to_id: EndpointId, d: f32) -> bool {
match src {
VertexSource::Edge { t, from, to, .. } => {
*from == from_id
&& *to == to_id
&& ((d - *t).abs() < 0.00001 || (1.0 - d - *t).abs() <= 0.00001)
}
VertexSource::Endpoint { .. } => false,
}
}
#[test]
fn fill_vertex_source_01() {
use crate::path::commands::PathCommands;
use crate::path::AttributeSlice;
let endpoints: &[Point] = &[point(0.0, 0.0), point(1.0, 1.0), point(0.0, 2.0)];
let attributes = &[1.0, 0.0, 0.0, 0.0, 1.0, 0.0, 0.0, 0.0, 1.0];
let mut cmds = PathCommands::builder();
cmds.begin(EndpointId(0));
cmds.line_to(EndpointId(1));
cmds.line_to(EndpointId(2));
cmds.end(true);
let cmds = cmds.build();
let mut tess = FillTessellator::new();
tess.tessellate_with_ids(
cmds.iter(),
&(endpoints, endpoints),
Some(&AttributeSlice::new(attributes, 3)),
&FillOptions::default(),
&mut CheckVertexSources { next_vertex: 0 },
)
.unwrap();
struct CheckVertexSources {
next_vertex: u32,
}
impl GeometryBuilder for CheckVertexSources {
fn begin_geometry(&mut self) {}
fn end_geometry(&mut self) -> Count {
Count {
vertices: self.next_vertex,
indices: 0,
}
}
fn abort_geometry(&mut self) {}
fn add_triangle(&mut self, _: VertexId, _: VertexId, _: VertexId) {}
}
impl FillGeometryBuilder for CheckVertexSources {
fn add_fill_vertex(
&mut self,
mut vertex: FillVertex,
) -> Result<VertexId, GeometryBuilderError> {
let pos = vertex.position();
for src in vertex.sources() {
if eq(pos, point(0.0, 0.0)) {
assert!(at_endpoint(&src, EndpointId(0)))
} else if eq(pos, point(1.0, 1.0)) {
assert!(at_endpoint(&src, EndpointId(1)))
} else if eq(pos, point(0.0, 2.0)) {
assert!(at_endpoint(&src, EndpointId(2)))
} else {
panic!()
}
}
if eq(pos, point(0.0, 0.0)) {
assert_eq!(vertex.interpolated_attributes(), &[1.0, 0.0, 0.0])
} else if eq(pos, point(1.0, 1.0)) {
assert_eq!(vertex.interpolated_attributes(), &[0.0, 1.0, 0.0])
} else if eq(pos, point(0.0, 2.0)) {
assert_eq!(vertex.interpolated_attributes(), &[0.0, 0.0, 1.0])
}
let id = self.next_vertex;
self.next_vertex += 1;
Ok(VertexId(id))
}
}
}
#[test]
fn fill_vertex_source_02() {
let mut path = crate::path::Path::builder_with_attributes(3);
let a = path.begin(point(1.0, 0.0), &[1.0, 0.0, 1.0]);
let b = path.line_to(point(2.0, 0.0), &[2.0, 0.0, 1.0]);
let c = path.line_to(point(2.0, 4.0), &[3.0, 0.0, 1.0]);
let d = path.line_to(point(1.0, 4.0), &[4.0, 0.0, 1.0]);
path.end(true);
let e = path.begin(point(0.0, 1.0), &[0.0, 1.0, 2.0]);
let f = path.line_to(point(0.0, 3.0), &[0.0, 2.0, 2.0]);
let g = path.line_to(point(3.0, 3.0), &[0.0, 3.0, 2.0]);
let h = path.line_to(point(3.0, 1.0), &[0.0, 4.0, 2.0]);
path.end(true);
let path = path.build();
let mut tess = FillTessellator::new();
tess.tessellate_with_ids(
path.id_iter(),
&path,
Some(&path),
&FillOptions::default(),
&mut CheckVertexSources {
next_vertex: 0,
a,
b,
c,
d,
e,
f,
g,
h,
},
)
.unwrap();
struct CheckVertexSources {
next_vertex: u32,
a: EndpointId,
b: EndpointId,
c: EndpointId,
d: EndpointId,
e: EndpointId,
f: EndpointId,
g: EndpointId,
h: EndpointId,
}
impl GeometryBuilder for CheckVertexSources {
fn begin_geometry(&mut self) {}
fn end_geometry(&mut self) -> Count {
Count {
vertices: self.next_vertex,
indices: 0,
}
}
fn abort_geometry(&mut self) {}
fn add_triangle(&mut self, _: VertexId, _: VertexId, _: VertexId) {}
}
impl FillGeometryBuilder for CheckVertexSources {
fn add_fill_vertex(
&mut self,
mut vertex: FillVertex,
) -> Result<VertexId, GeometryBuilderError> {
let pos = vertex.position();
for src in vertex.sources() {
if eq(pos, point(1.0, 0.0)) {
assert!(at_endpoint(&src, self.a));
} else if eq(pos, point(2.0, 0.0)) {
assert!(at_endpoint(&src, self.b));
} else if eq(pos, point(2.0, 4.0)) {
assert!(at_endpoint(&src, self.c));
} else if eq(pos, point(1.0, 4.0)) {
assert!(at_endpoint(&src, self.d));
} else if eq(pos, point(0.0, 1.0)) {
assert!(at_endpoint(&src, self.e));
} else if eq(pos, point(0.0, 3.0)) {
assert!(at_endpoint(&src, self.f));
} else if eq(pos, point(3.0, 3.0)) {
assert!(at_endpoint(&src, self.g));
} else if eq(pos, point(3.0, 1.0)) {
assert!(at_endpoint(&src, self.h));
} else if eq(pos, point(1.0, 1.0)) {
assert!(
on_edge(&src, self.h, self.e, 2.0 / 3.0)
|| on_edge(&src, self.d, self.a, 3.0 / 4.0)
);
} else if eq(pos, point(2.0, 1.0)) {
assert!(
on_edge(&src, self.h, self.e, 1.0 / 3.0)
|| on_edge(&src, self.b, self.c, 1.0 / 4.0)
);
} else if eq(pos, point(1.0, 3.0)) {
assert!(
on_edge(&src, self.f, self.g, 1.0 / 3.0)
|| on_edge(&src, self.d, self.a, 1.0 / 4.0)
);
} else if eq(pos, point(2.0, 3.0)) {
assert!(
on_edge(&src, self.f, self.g, 2.0 / 3.0)
|| on_edge(&src, self.b, self.c, 3.0 / 4.0)
);
} else {
panic!()
}
}
fn assert_attr(a: &[f32], b: &[f32]) {
for i in 0..a.len() {
let are_equal = (a[i] - b[i]).abs() < 0.001;
if !are_equal {
println!("{:?} != {:?}", a, b);
}
assert!(are_equal);
}
assert_eq!(a.len(), b.len());
}
let pos = vertex.position();
let attribs = vertex.interpolated_attributes();
if eq(pos, point(1.0, 0.0)) {
assert_attr(attribs, &[1.0, 0.0, 1.0]);
} else if eq(pos, point(2.0, 0.0)) {
assert_attr(attribs, &[2.0, 0.0, 1.0]);
} else if eq(pos, point(2.0, 4.0)) {
assert_attr(attribs, &[3.0, 0.0, 1.0]);
} else if eq(pos, point(1.0, 4.0)) {
assert_attr(attribs, &[4.0, 0.0, 1.0]);
} else if eq(pos, point(0.0, 1.0)) {
assert_attr(attribs, &[0.0, 1.0, 2.0]);
} else if eq(pos, point(0.0, 3.0)) {
assert_attr(attribs, &[0.0, 2.0, 2.0]);
} else if eq(pos, point(3.0, 3.0)) {
assert_attr(attribs, &[0.0, 3.0, 2.0]);
} else if eq(pos, point(3.0, 1.0)) {
assert_attr(attribs, &[0.0, 4.0, 2.0]);
} else if eq(pos, point(1.0, 1.0)) {
assert_attr(attribs, &[0.875, 1.0, 1.5]);
} else if eq(pos, point(2.0, 1.0)) {
assert_attr(attribs, &[1.125, 1.5, 1.5]);
} else if eq(pos, point(1.0, 3.0)) {
assert_attr(attribs, &[1.625, 1.16666, 1.5]);
} else if eq(pos, point(2.0, 3.0)) {
assert_attr(attribs, &[1.375, 1.33333, 1.5]);
}
let id = self.next_vertex;
self.next_vertex += 1;
Ok(VertexId(id))
}
}
}
#[test]
fn fill_vertex_source_03() {
use crate::path::commands::PathCommands;
use crate::path::AttributeSlice;
let endpoints: &[Point] = &[
point(0.0, 0.0),
point(2.0, 0.0),
point(1.0, 1.0),
point(0.0, 2.0),
point(2.0, 2.0),
point(1.0, 1.0),
];
let attributes = &[0.0, 0.0, 1.0, 0.0, 0.0, 2.0];
let mut cmds = PathCommands::builder();
cmds.begin(EndpointId(0));
cmds.line_to(EndpointId(1));
cmds.line_to(EndpointId(2));
cmds.end(true);
cmds.begin(EndpointId(3));
cmds.line_to(EndpointId(4));
cmds.line_to(EndpointId(5));
cmds.end(true);
let cmds = cmds.build();
let mut tess = FillTessellator::new();
tess.tessellate_with_ids(
cmds.iter(),
&(endpoints, endpoints),
Some(&AttributeSlice::new(attributes, 1)),
&FillOptions::default(),
&mut CheckVertexSources { next_vertex: 0 },
)
.unwrap();
struct CheckVertexSources {
next_vertex: u32,
}
impl GeometryBuilder for CheckVertexSources {
fn begin_geometry(&mut self) {}
fn end_geometry(&mut self) -> Count {
Count {
vertices: self.next_vertex,
indices: 0,
}
}
fn abort_geometry(&mut self) {}
fn add_triangle(&mut self, _: VertexId, _: VertexId, _: VertexId) {}
}
impl FillGeometryBuilder for CheckVertexSources {
fn add_fill_vertex(&mut self, mut vertex: FillVertex) -> Result<VertexId, GeometryBuilderError> {
if eq(vertex.position(), point(1.0, 1.0)) {
assert_eq!(vertex.interpolated_attributes(), &[1.5]);
assert_eq!(vertex.sources().count(), 2);
} else {
assert_eq!(vertex.interpolated_attributes(), &[0.0]);
assert_eq!(vertex.sources().count(), 1);
}
let id = self.next_vertex;
self.next_vertex += 1;
Ok(VertexId(id))
}
}
}
#[test]
fn fill_builder_vertex_source() {
let mut tess = FillTessellator::new();
let options = FillOptions::default();
let mut check = CheckVertexSources { next_vertex: 0 };
let mut builder = tess.builder(&options, &mut check);
assert_eq!(builder.begin(point(0.0, 0.0)), EndpointId(0));
assert_eq!(builder.line_to(point(1.0, 1.0)), EndpointId(1));
assert_eq!(builder.line_to(point(0.0, 2.0)), EndpointId(2));
builder.end(true);
builder.build().unwrap();
struct CheckVertexSources {
next_vertex: u32,
}
impl GeometryBuilder for CheckVertexSources {
fn begin_geometry(&mut self) {}
fn end_geometry(&mut self) -> Count {
Count {
vertices: self.next_vertex,
indices: 0,
}
}
fn abort_geometry(&mut self) {}
fn add_triangle(&mut self, _: VertexId, _: VertexId, _: VertexId) {}
}
impl FillGeometryBuilder for CheckVertexSources {
fn add_fill_vertex(&mut self, vertex: FillVertex) -> Result<VertexId, GeometryBuilderError> {
let pos = vertex.position();
for src in vertex.sources() {
if eq(pos, point(0.0, 0.0)) {
assert!(at_endpoint(&src, EndpointId(0)))
} else if eq(pos, point(1.0, 1.0)) {
assert!(at_endpoint(&src, EndpointId(1)))
} else if eq(pos, point(0.0, 2.0)) {
assert!(at_endpoint(&src, EndpointId(2)))
} else {
panic!()
}
}
let id = self.next_vertex;
self.next_vertex += 1;
Ok(VertexId(id))
}
}
}