use crate::fill::{compare_positions, is_after};
use crate::geom::{CubicBezierSegment, LineSegment, QuadraticBezierSegment};
use crate::math::{point, Point};
use crate::path::private::DebugValidator;
use crate::path::{EndpointId, IdEvent, PathEvent, PositionStore};
use crate::Orientation;
use core::cmp::Ordering;
use core::mem::swap;
use core::ops::Range;
use alloc::vec::Vec;
#[inline]
fn reorient(p: Point) -> Point {
point(-p.y, p.x)
}
pub(crate) type TessEventId = u32;
pub(crate) const INVALID_EVENT_ID: TessEventId = u32::MAX;
pub(crate) struct Event {
pub next_sibling: TessEventId,
pub next_event: TessEventId,
pub position: Point,
}
#[derive(Clone, Debug)]
pub(crate) struct EdgeData {
pub to: Point,
pub range: core::ops::Range<f32>,
pub winding: i16,
pub is_edge: bool,
pub from_id: EndpointId,
pub to_id: EndpointId,
}
#[doc(hidden)]
pub struct EventQueue {
pub(crate) events: Vec<Event>,
pub(crate) edge_data: Vec<EdgeData>,
first: TessEventId,
sorted: bool,
}
impl Default for EventQueue {
fn default() -> Self {
Self::new()
}
}
impl EventQueue {
pub fn new() -> Self {
EventQueue {
events: Vec::new(),
edge_data: Vec::new(),
first: INVALID_EVENT_ID,
sorted: false,
}
}
pub fn with_capacity(cap: usize) -> Self {
EventQueue {
events: Vec::with_capacity(cap),
edge_data: Vec::with_capacity(cap),
first: 0,
sorted: false,
}
}
pub fn reset(&mut self) {
self.events.clear();
self.edge_data.clear();
self.first = INVALID_EVENT_ID;
self.sorted = false;
}
pub fn from_path(tolerance: f32, path: impl IntoIterator<Item = PathEvent>) -> Self {
let path = path.into_iter();
let (min, max) = path.size_hint();
let capacity = max.unwrap_or(min);
let mut builder = EventQueueBuilder::with_capacity(capacity, tolerance);
builder.set_path(tolerance, Orientation::Vertical, path);
builder.build()
}
pub fn from_path_with_ids(
tolerance: f32,
sweep_orientation: Orientation,
path: impl IntoIterator<Item = IdEvent>,
positions: &impl PositionStore,
) -> Self {
let path = path.into_iter();
let (min, max) = path.size_hint();
let capacity = max.unwrap_or(min);
let mut builder = EventQueueBuilder::with_capacity(capacity, tolerance);
builder.set_path_with_ids(tolerance, sweep_orientation, path, positions);
builder.build()
}
pub fn into_builder(mut self, tolerance: f32) -> EventQueueBuilder {
self.reset();
EventQueueBuilder {
queue: self,
current: point(f32::NAN, f32::NAN),
prev: point(f32::NAN, f32::NAN),
second: point(f32::NAN, f32::NAN),
nth: 0,
tolerance,
prev_endpoint_id: EndpointId(u32::MAX),
validator: DebugValidator::new(),
}
}
pub fn reserve(&mut self, n: usize) {
self.events.reserve(n);
}
fn push_unsorted(&mut self, position: Point) {
self.events.push(Event {
position,
next_sibling: INVALID_EVENT_ID,
next_event: INVALID_EVENT_ID,
});
}
fn push_sorted(&mut self, position: Point) {
self.events.push(Event {
position,
next_sibling: u32::MAX,
next_event: u32::MAX,
});
let id = (self.events.len() - 1) as u32;
let mut current = self.first_id();
let mut prev = current;
while self.valid_id(current) {
let evt_pos = self.events[current as usize].position;
match compare_positions(position, evt_pos) {
Ordering::Greater => {}
Ordering::Equal => {
let mut current_sibling = current;
let mut next_sibling = self.next_sibling_id(current);
while self.valid_id(next_sibling) {
current_sibling = next_sibling;
next_sibling = self.next_sibling_id(current_sibling);
}
self.events[current_sibling as usize].next_sibling = id;
return;
}
Ordering::Less => {
if prev != current {
self.events[prev as usize].next_event = id;
} else {
self.first = id;
}
self.events[id as usize].next_event = current;
return;
}
}
prev = current;
current = self.next_id(current);
}
self.events[prev as usize].next_event = id;
}
pub(crate) fn insert_sorted(
&mut self,
position: Point,
data: EdgeData,
after: TessEventId,
) -> TessEventId {
debug_assert!(self.sorted);
debug_assert!(
is_after(data.to, position),
"{:?} should be after {:?}",
data.to,
position
);
let idx = self.events.len() as TessEventId;
self.events.push(Event {
position,
next_sibling: INVALID_EVENT_ID,
next_event: INVALID_EVENT_ID,
});
self.edge_data.push(data);
self.insert_into_sorted_list(idx, position, after);
idx
}
pub(crate) fn insert_sibling(&mut self, sibling: TessEventId, position: Point, data: EdgeData) {
debug_assert!(is_after(data.to, position));
let idx = self.events.len() as TessEventId;
let next_sibling = self.events[sibling as usize].next_sibling;
self.events.push(Event {
position,
next_event: INVALID_EVENT_ID,
next_sibling,
});
self.edge_data.push(data);
self.events[sibling as usize].next_sibling = idx;
}
pub(crate) fn vertex_event_sorted(
&mut self,
position: Point,
endpoint_id: EndpointId,
after: TessEventId,
) {
let idx = self.events.len() as TessEventId;
self.push_unsorted(position);
self.edge_data.push(EdgeData {
to: point(f32::NAN, f32::NAN),
range: 0.0..0.0,
winding: 0,
is_edge: false,
from_id: endpoint_id,
to_id: endpoint_id,
});
self.insert_into_sorted_list(idx, position, after);
}
fn insert_into_sorted_list(&mut self, idx: TessEventId, position: Point, after: TessEventId) {
let mut prev = after;
let mut current = after;
while self.valid_id(current) {
let pos = self.events[current as usize].position;
if pos == position {
debug_assert!(prev != current);
self.events[idx as usize].next_sibling = self.events[current as usize].next_sibling;
self.events[current as usize].next_sibling = idx;
return;
} else if is_after(pos, position) {
self.events[prev as usize].next_event = idx;
self.events[idx as usize].next_event = current;
return;
}
prev = current;
current = self.next_id(current);
}
self.events[prev as usize].next_event = idx;
}
pub(crate) fn clear(&mut self) {
self.events.clear();
self.first = INVALID_EVENT_ID;
self.sorted = false;
}
pub(crate) fn first_id(&self) -> TessEventId {
self.first
}
pub(crate) fn next_id(&self, id: TessEventId) -> TessEventId {
self.events[id as usize].next_event
}
pub(crate) fn next_sibling_id(&self, id: TessEventId) -> TessEventId {
self.events[id as usize].next_sibling
}
pub(crate) fn valid_id(&self, id: TessEventId) -> bool {
id != INVALID_EVENT_ID
}
pub(crate) fn position(&self, id: TessEventId) -> Point {
self.events[id as usize].position
}
fn sort(&mut self) {
self.sorted = true;
if self.events.is_empty() {
return;
}
let range = 0..self.events.len();
self.first = self.merge_sort(range);
}
fn merge_sort(&mut self, range: Range<usize>) -> TessEventId {
let split = (range.start + range.end) / 2;
if split == range.start {
return range.start as TessEventId;
}
let a_head = self.merge_sort(range.start..split);
let b_head = self.merge_sort(split..range.end);
self.merge(a_head, b_head)
}
fn merge(&mut self, mut a: TessEventId, mut b: TessEventId) -> TessEventId {
if a == INVALID_EVENT_ID {
return b;
}
if b == INVALID_EVENT_ID {
return a;
}
debug_assert!(a != b);
let mut first = true;
let mut sorted_head = INVALID_EVENT_ID;
let mut prev = INVALID_EVENT_ID;
loop {
if a == INVALID_EVENT_ID {
if !first {
self.events[prev as usize].next_event = b;
}
break;
}
if b == INVALID_EVENT_ID {
if !first {
self.events[prev as usize].next_event = a;
}
break;
}
let node;
match compare_positions(
self.events[a as usize].position,
self.events[b as usize].position,
) {
Ordering::Less => {
node = a;
a = self.events[a as usize].next_event;
}
Ordering::Greater => {
node = b;
b = self.events[b as usize].next_event;
}
Ordering::Equal => {
let a_sib = self.find_last_sibling(a) as usize;
self.events[a_sib].next_sibling = b;
b = self.events[b as usize].next_event;
continue;
}
}
if first {
first = false;
sorted_head = node;
} else {
self.events[prev as usize].next_event = node;
}
prev = node;
}
if sorted_head == INVALID_EVENT_ID {
sorted_head = a;
}
sorted_head
}
fn find_last_sibling(&self, id: TessEventId) -> TessEventId {
let mut current_sibling = id;
let mut next_sibling = self.next_sibling_id(id);
while self.valid_id(next_sibling) {
current_sibling = next_sibling;
next_sibling = self.next_sibling_id(current_sibling);
}
current_sibling
}
#[cfg(all(debug_assertions, feature = "std"))]
fn log(&self) {
let mut iter_count = self.events.len() * self.events.len();
std::println!("--");
let mut current = self.first;
while (current as usize) < self.events.len() {
assert!(iter_count > 0);
iter_count -= 1;
std::print!("[");
let mut current_sibling = current;
while (current_sibling as usize) < self.events.len() {
std::print!("{:?},", self.events[current_sibling as usize].position);
current_sibling = self.events[current_sibling as usize].next_sibling;
}
std::print!("] ");
current = self.events[current as usize].next_event;
}
std::println!("\n--");
}
fn assert_sorted(&self) {
let mut current = self.first;
let mut pos = point(f32::MIN, f32::MIN);
let mut n = 0;
while self.valid_id(current) {
assert!(is_after(self.events[current as usize].position, pos));
pos = self.events[current as usize].position;
let mut current_sibling = current;
while self.valid_id(current_sibling) {
n += 1;
assert_eq!(self.events[current_sibling as usize].position, pos);
current_sibling = self.next_sibling_id(current_sibling);
}
current = self.next_id(current);
}
assert_eq!(n, self.events.len());
}
}
pub struct EventQueueBuilder {
current: Point,
prev: Point,
second: Point,
nth: u32,
queue: EventQueue,
tolerance: f32,
prev_endpoint_id: EndpointId,
validator: DebugValidator,
}
impl EventQueueBuilder {
pub fn new(tolerance: f32) -> Self {
EventQueue::new().into_builder(tolerance)
}
pub fn with_capacity(cap: usize, tolerance: f32) -> Self {
EventQueue::with_capacity(cap).into_builder(tolerance)
}
pub fn set_tolerance(&mut self, tolerance: f32) {
self.tolerance = tolerance;
}
pub fn build(mut self) -> EventQueue {
self.validator.build();
self.queue.sort();
self.queue
}
pub fn set_path(
&mut self,
tolerance: f32,
sweep_orientation: Orientation,
path: impl IntoIterator<Item = PathEvent>,
) {
self.reset();
self.tolerance = tolerance;
let endpoint_id = EndpointId(u32::MAX);
match sweep_orientation {
Orientation::Vertical => {
for evt in path {
match evt {
PathEvent::Begin { at } => {
self.begin(at, endpoint_id);
}
PathEvent::Line { to, .. } => {
self.line_segment(to, endpoint_id, 0.0, 1.0);
}
PathEvent::Quadratic { ctrl, to, .. } => {
self.quadratic_bezier_segment(ctrl, to, endpoint_id);
}
PathEvent::Cubic {
ctrl1, ctrl2, to, ..
} => {
self.cubic_bezier_segment(ctrl1, ctrl2, to, endpoint_id);
}
PathEvent::End { first, .. } => {
self.end(first, endpoint_id);
}
}
}
}
Orientation::Horizontal => {
for evt in path {
match evt {
PathEvent::Begin { at } => {
self.begin(reorient(at), endpoint_id);
}
PathEvent::Line { to, .. } => {
self.line_segment(reorient(to), endpoint_id, 0.0, 1.0);
}
PathEvent::Quadratic { ctrl, to, .. } => {
self.quadratic_bezier_segment(
reorient(ctrl),
reorient(to),
endpoint_id,
);
}
PathEvent::Cubic {
ctrl1, ctrl2, to, ..
} => {
self.cubic_bezier_segment(
reorient(ctrl1),
reorient(ctrl2),
reorient(to),
endpoint_id,
);
}
PathEvent::End { first, .. } => {
self.end(reorient(first), endpoint_id);
}
}
}
}
}
}
pub fn set_path_with_ids(
&mut self,
tolerance: f32,
sweep_orientation: Orientation,
path_events: impl IntoIterator<Item = IdEvent>,
points: &impl PositionStore,
) {
self.reset();
self.tolerance = tolerance;
match sweep_orientation {
Orientation::Vertical => {
for evt in path_events {
match evt {
IdEvent::Begin { at } => {
self.begin(points.get_endpoint(at), at);
}
IdEvent::Line { to, .. } => {
self.line_segment(points.get_endpoint(to), to, 0.0, 1.0);
}
IdEvent::Quadratic { ctrl, to, .. } => {
self.quadratic_bezier_segment(
points.get_control_point(ctrl),
points.get_endpoint(to),
to,
);
}
IdEvent::Cubic {
ctrl1, ctrl2, to, ..
} => {
self.cubic_bezier_segment(
points.get_control_point(ctrl1),
points.get_control_point(ctrl2),
points.get_endpoint(to),
to,
);
}
IdEvent::End { first, .. } => {
self.end(points.get_endpoint(first), first);
}
}
}
}
Orientation::Horizontal => {
for evt in path_events {
match evt {
IdEvent::Begin { at } => {
self.begin(reorient(points.get_endpoint(at)), at);
}
IdEvent::Line { to, .. } => {
self.line_segment(reorient(points.get_endpoint(to)), to, 0.0, 1.0);
}
IdEvent::Quadratic { ctrl, to, .. } => {
self.quadratic_bezier_segment(
reorient(points.get_control_point(ctrl)),
reorient(points.get_endpoint(to)),
to,
);
}
IdEvent::Cubic {
ctrl1, ctrl2, to, ..
} => {
self.cubic_bezier_segment(
reorient(points.get_control_point(ctrl1)),
reorient(points.get_control_point(ctrl2)),
reorient(points.get_endpoint(to)),
to,
);
}
IdEvent::End { first, .. } => {
self.end(reorient(points.get_endpoint(first)), first);
}
}
}
}
}
}
fn reset(&mut self) {
self.queue.reset();
self.nth = 0;
}
fn vertex_event(&mut self, at: Point, endpoint_id: EndpointId) {
self.queue.push_unsorted(at);
self.queue.edge_data.push(EdgeData {
to: point(f32::NAN, f32::NAN),
range: 0.0..0.0,
winding: 0,
is_edge: false,
from_id: endpoint_id,
to_id: endpoint_id,
});
}
fn vertex_event_on_curve(&mut self, at: Point, t: f32, from_id: EndpointId, to_id: EndpointId) {
self.queue.push_unsorted(at);
self.queue.edge_data.push(EdgeData {
to: point(f32::NAN, f32::NAN),
range: t..t,
winding: 0,
is_edge: false,
from_id,
to_id,
});
}
pub fn end(&mut self, first: Point, first_endpoint_id: EndpointId) {
if self.nth == 0 {
self.validator.end();
return;
}
self.line_segment(first, first_endpoint_id, 0.0, 1.0);
if is_after(first, self.prev) && is_after(first, self.second) {
self.vertex_event(first, first_endpoint_id);
}
self.validator.end();
self.prev_endpoint_id = first_endpoint_id;
self.nth = 0;
}
pub fn begin(&mut self, to: Point, to_id: EndpointId) {
self.validator.begin();
self.nth = 0;
self.current = to;
self.prev_endpoint_id = to_id;
}
#[allow(clippy::too_many_arguments)]
fn add_edge(
&mut self,
edge: &LineSegment<f32>,
mut winding: i16,
from_id: EndpointId,
to_id: EndpointId,
mut t0: f32,
mut t1: f32,
) {
if edge.from == edge.to {
return;
}
let mut evt_pos = edge.from;
let mut evt_to = edge.to;
if is_after(evt_pos, edge.to) {
evt_to = evt_pos;
evt_pos = edge.to;
swap(&mut t0, &mut t1);
winding *= -1;
}
self.queue.push_unsorted(evt_pos);
self.queue.edge_data.push(EdgeData {
to: evt_to,
range: t0..t1,
winding,
is_edge: true,
from_id,
to_id,
});
self.nth += 1;
}
pub fn line_segment(&mut self, to: Point, to_id: EndpointId, t0: f32, t1: f32) {
self.validator.edge();
let from = self.current;
if from == to {
return;
}
if is_after(from, to) && self.nth > 0 && is_after(from, self.prev) {
self.vertex_event(from, self.prev_endpoint_id);
}
if self.nth == 0 {
self.second = to;
}
self.add_edge(
&LineSegment { from, to },
1,
self.prev_endpoint_id,
to_id,
t0,
t1,
);
self.prev = self.current;
self.prev_endpoint_id = to_id;
self.current = to;
}
pub fn quadratic_bezier_segment(&mut self, ctrl: Point, to: Point, to_id: EndpointId) {
self.validator.edge();
let original = QuadraticBezierSegment {
from: self.current,
ctrl,
to,
};
let needs_swap = is_after(original.from, original.to);
let mut segment = original;
let mut winding = 1;
if needs_swap {
swap(&mut segment.from, &mut segment.to);
winding = -1;
}
let mut prev = segment.from;
let mut first = None;
let is_first_edge = self.nth == 0;
segment.for_each_flattened_with_t(self.tolerance, &mut |line, t| {
if line.from == line.to {
return;
}
if first.is_none() {
first = Some(line.to)
} else if is_after(line.from, line.to) && is_after(line.from, prev) {
self.vertex_event_on_curve(line.from, t.start, self.prev_endpoint_id, to_id);
}
self.add_edge(line, winding, self.prev_endpoint_id, to_id, t.start, t.end);
prev = line.from;
});
if let Some(first) = first {
let (second, previous) = if needs_swap {
(prev, first)
} else {
(first, prev)
};
if is_first_edge {
self.second = second;
} else if is_after(original.from, self.prev) && is_after(original.from, second) {
self.vertex_event(original.from, self.prev_endpoint_id);
}
self.prev = previous;
self.current = original.to;
self.prev_endpoint_id = to_id;
}
}
pub fn cubic_bezier_segment(
&mut self,
ctrl1: Point,
ctrl2: Point,
to: Point,
to_id: EndpointId,
) {
self.validator.edge();
let original = CubicBezierSegment {
from: self.current,
ctrl1,
ctrl2,
to,
};
let needs_swap = is_after(original.from, original.to);
let mut segment = original;
let mut winding = 1;
if needs_swap {
swap(&mut segment.from, &mut segment.to);
swap(&mut segment.ctrl1, &mut segment.ctrl2);
winding = -1;
}
let mut prev = segment.from;
let mut first = None;
let is_first_edge = self.nth == 0;
segment.for_each_flattened_with_t(self.tolerance, &mut |line, t| {
if line.from == line.to {
return;
}
if first.is_none() {
first = Some(line.to)
} else if is_after(line.from, line.to) && is_after(line.from, prev) {
self.vertex_event_on_curve(line.from, t.start, self.prev_endpoint_id, to_id);
}
self.add_edge(line, winding, self.prev_endpoint_id, to_id, t.start, t.end);
prev = line.from;
});
if let Some(first) = first {
let (second, previous) = if needs_swap {
(prev, first)
} else {
(first, prev)
};
if is_first_edge {
self.second = second;
} else if is_after(original.from, self.prev) && is_after(original.from, second) {
self.vertex_event(original.from, self.prev_endpoint_id);
}
self.prev = previous;
self.current = original.to;
self.prev_endpoint_id = to_id;
}
}
pub fn reserve(&mut self, n: usize) {
self.queue.reserve(n);
}
}
#[test]
fn test_event_queue_sort_1() {
let mut queue = EventQueue::new();
queue.push_unsorted(point(0.0, 0.0));
queue.push_unsorted(point(4.0, 0.0));
queue.push_unsorted(point(2.0, 0.0));
queue.push_unsorted(point(3.0, 0.0));
queue.push_unsorted(point(4.0, 0.0));
queue.push_unsorted(point(0.0, 0.0));
queue.push_unsorted(point(6.0, 0.0));
queue.sort();
queue.assert_sorted();
}
#[test]
fn test_event_queue_sort_2() {
let mut queue = EventQueue::new();
queue.push_unsorted(point(0.0, 0.0));
queue.push_unsorted(point(0.0, 0.0));
queue.push_unsorted(point(0.0, 0.0));
queue.push_unsorted(point(0.0, 0.0));
queue.sort();
queue.assert_sorted();
}
#[test]
fn test_event_queue_sort_3() {
let mut queue = EventQueue::new();
queue.push_unsorted(point(0.0, 0.0));
queue.push_unsorted(point(1.0, 0.0));
queue.push_unsorted(point(2.0, 0.0));
queue.push_unsorted(point(3.0, 0.0));
queue.push_unsorted(point(4.0, 0.0));
queue.push_unsorted(point(5.0, 0.0));
queue.sort();
queue.assert_sorted();
}
#[test]
fn test_event_queue_sort_4() {
let mut queue = EventQueue::new();
queue.push_unsorted(point(5.0, 0.0));
queue.push_unsorted(point(4.0, 0.0));
queue.push_unsorted(point(3.0, 0.0));
queue.push_unsorted(point(2.0, 0.0));
queue.push_unsorted(point(1.0, 0.0));
queue.push_unsorted(point(0.0, 0.0));
queue.sort();
queue.assert_sorted();
}
#[test]
fn test_event_queue_sort_5() {
let mut queue = EventQueue::new();
queue.push_unsorted(point(5.0, 0.0));
queue.push_unsorted(point(5.0, 0.0));
queue.push_unsorted(point(4.0, 0.0));
queue.push_unsorted(point(4.0, 0.0));
queue.push_unsorted(point(3.0, 0.0));
queue.push_unsorted(point(3.0, 0.0));
queue.push_unsorted(point(2.0, 0.0));
queue.push_unsorted(point(2.0, 0.0));
queue.push_unsorted(point(1.0, 0.0));
queue.push_unsorted(point(1.0, 0.0));
queue.push_unsorted(point(0.0, 0.0));
queue.push_unsorted(point(0.0, 0.0));
queue.sort();
queue.assert_sorted();
}
#[test]
fn test_event_queue_push_sorted() {
let mut queue = EventQueue::new();
queue.push_unsorted(point(5.0, 0.0));
queue.push_unsorted(point(4.0, 0.0));
queue.push_unsorted(point(3.0, 0.0));
queue.push_unsorted(point(2.0, 0.0));
queue.push_unsorted(point(1.0, 0.0));
queue.push_unsorted(point(0.0, 0.0));
queue.sort();
queue.push_sorted(point(1.5, 0.0));
queue.assert_sorted();
queue.push_sorted(point(2.5, 0.0));
queue.assert_sorted();
queue.push_sorted(point(2.5, 0.0));
queue.assert_sorted();
queue.push_sorted(point(6.5, 0.0));
queue.assert_sorted();
}
#[test]
fn test_logo() {
use crate::path::Path;
let mut path = Path::builder().with_svg();
crate::extra::rust_logo::build_logo_path(&mut path);
let path = path.build();
crate::extra::debugging::find_reduced_test_case(path.as_slice(), &|path: Path| {
let _ = EventQueue::from_path(0.05, path.iter());
true
});
}