facett-geomap/src/osm2d/clip.rs
//! **Viewport geometry clipping** for the 2D OSM way painter.
//!
//! Why this exists: ways are viewport-culled by *bbox* — a way is kept whenever
//! its bbox crosses the pane, so a long way can be kept while most of its
//! vertices lie far off-screen. At high zoom an off-screen Mercator vertex
//! projects (via `MercatorCamera::to_px`) to an **enormous** pixel coordinate
//! (~1e6–1e9). `painter_at(rect)` clips the *raster*, but egui still
//! *tessellates* the whole shape, and a polyline/polygon that contains a
//! near-infinite vertex produces flicker and "lines springing outside the
//! screen".
//!
//! The fix is to clip the **geometry** (not the raster) to a margin-expanded
//! viewport rect *before* the shape is handed to the painter, so no drawn
//! vertex sits at an extreme coordinate. Clipping (not clamping) preserves
//! slopes — a clamped point would bend the line; a clipped point sits exactly on
//! the rect edge along the original segment.
//!
//! - [`clip_polyline`] — Liang–Barsky per-segment clip. A polyline that leaves
//! and re-enters the rect emits *multiple* sub-polylines.
//! - [`clip_polygon`] — Sutherland–Hodgman ring clip against the (convex) rect;
//! correct for concave OSM polygons too, since the clip window is convex.
use egui::{Pos2, Rect};
/// Liang–Barsky parametric clip of a single segment `(a → b)` against `rect`.
/// Returns the clipped segment `(p0, p1)` (parametric endpoints on `a→b`), or
/// `None` if the segment lies entirely outside the rect.
#[inline]
fn liang_barsky(a: Pos2, b: Pos2, rect: Rect) -> Option<(Pos2, Pos2)> {
let dx = b.x - a.x;
let dy = b.y - a.y;
// Parametric range [t0, t1] along a→b that stays inside the rect.
let mut t0 = 0.0_f32;
let mut t1 = 1.0_f32;
// (p, q) pairs for the four edges: left, right, bottom, top.
let edges = [
(-dx, a.x - rect.min.x), // left: x >= rect.min.x
(dx, rect.max.x - a.x), // right: x <= rect.max.x
(-dy, a.y - rect.min.y), // top: y >= rect.min.y
(dy, rect.max.y - a.y), // bottom:y <= rect.max.y
];
for (p, q) in edges {
if p == 0.0 {
// Segment is parallel to this edge; if it's outside, reject.
if q < 0.0 {
return None;
}
} else {
let r = q / p;
if p < 0.0 {
// Entering: tighten t0.
if r > t1 {
return None;
}
if r > t0 {
t0 = r;
}
} else {
// Leaving: tighten t1.
if r < t0 {
return None;
}
if r < t1 {
t1 = r;
}
}
}
}
let p0 = Pos2::new(a.x + t0 * dx, a.y + t0 * dy);
let p1 = Pos2::new(a.x + t1 * dx, a.y + t1 * dy);
Some((p0, p1))
}
/// **Clip a projected polyline to `rect`.** Walks the input segment-by-segment
/// with Liang–Barsky and appends one or more clipped sub-polylines to `out` (a
/// polyline that leaves and re-enters the rect becomes several runs). `out` is
/// `Vec<Vec<Pos2>>`; cleared first. Each emitted run has ≥ 2 vertices, all of
/// which lie within `rect` (so nothing extreme reaches the tessellator).
///
/// Fully-on-screen polylines emit a single run identical (vertex-for-vertex) to
/// the input, so on-screen geometry is unchanged.
pub fn clip_polyline(pts: &[Pos2], rect: Rect, out: &mut Vec<Vec<Pos2>>) {
out.clear();
if pts.len() < 2 {
return;
}
let mut cur: Vec<Pos2> = Vec::new();
for w in pts.windows(2) {
let (a, b) = (w[0], w[1]);
let Some((c0, c1)) = liang_barsky(a, b, rect) else {
// Segment fully outside → break the run.
if cur.len() >= 2 {
out.push(std::mem::take(&mut cur));
} else {
cur.clear();
}
continue;
};
// Is the clipped segment contiguous with the run we're building?
// It is iff its start equals the original `a` (segment wasn't clipped at
// its head) AND the run's last vertex is that same `a`.
let head_unclipped = c0 == a;
match cur.last() {
Some(&last) if head_unclipped && last == c0 => {
cur.push(c1);
}
_ => {
// Start a new run (flush the previous one if it's drawable).
if cur.len() >= 2 {
out.push(std::mem::take(&mut cur));
} else {
cur.clear();
}
cur.push(c0);
cur.push(c1);
}
}
// If the segment was clipped at its tail (exited the rect), the next
// segment can't continue this run — close it.
if c1 != b {
if cur.len() >= 2 {
out.push(std::mem::take(&mut cur));
} else {
cur.clear();
}
}
}
if cur.len() >= 2 {
out.push(cur);
}
}
// The Sutherland–Hodgman ring clip is the single implementation in
// `facett_core::render::cpu::scissor`; re-exported so `clip::clip_polygon` keeps
// working with one algorithm shared with the CPU painter's triangle scissor
// (audit cluster L). The Liang–Barsky per-segment `clip_polyline` above stays
// local — it is a genuinely different (polyline, multi-segment) clipper.
pub use facett_core::render::cpu::scissor::clip_polygon;
#[cfg(test)]
mod tests {
use super::*;
fn r() -> Rect {
Rect::from_min_max(Pos2::new(0.0, 0.0), Pos2::new(100.0, 100.0))
}
#[test]
fn polyline_fully_inside_is_unchanged() {
let pts = [Pos2::new(10.0, 10.0), Pos2::new(50.0, 60.0), Pos2::new(90.0, 20.0)];
let mut out = Vec::new();
clip_polyline(&pts, r(), &mut out);
assert_eq!(out.len(), 1, "single contiguous run");
assert_eq!(out[0].as_slice(), pts.as_slice(), "on-screen geometry untouched");
}
#[test]
fn polyline_with_extreme_vertex_is_bounded_and_preserved() {
// A segment from inside the rect out to a near-infinite (high-zoom) pixel.
let inside = Pos2::new(50.0, 50.0);
let extreme = Pos2::new(1.0e8, 1.0e8);
let pts = [inside, extreme];
let mut out = Vec::new();
clip_polyline(&pts, r(), &mut out);
assert!(!out.is_empty(), "the on-screen part is preserved");
for run in &out {
for p in run {
assert!(
p.x.abs() <= 100.0 + 1.0 && p.y.abs() <= 100.0 + 1.0,
"no extreme vertex reaches the painter: {p:?}"
);
}
}
// The run still starts at the inside endpoint and exits at the rect edge.
assert_eq!(out[0][0], inside, "kept the in-rect endpoint exactly");
let exit = *out[0].last().unwrap();
assert!(exit.x == 100.0 || exit.y == 100.0, "exits on a rect edge: {exit:?}");
}
#[test]
fn polyline_leaving_and_reentering_makes_two_runs() {
// Crosses the rect, goes way out, comes back and crosses again.
let pts = [
Pos2::new(-50.0, 50.0),
Pos2::new(50.0, 50.0), // inside
Pos2::new(50.0, 1.0e8), // shoots out the bottom
Pos2::new(50.0, -1.0e8), // back from the top
Pos2::new(50.0, 50.0), // inside again
Pos2::new(200.0, 50.0), // out the right
];
let mut out = Vec::new();
clip_polyline(&pts, r(), &mut out);
assert!(out.len() >= 2, "leave+re-enter splits into ≥2 runs, got {}", out.len());
for run in &out {
assert!(run.len() >= 2);
for p in run {
assert!(p.x.abs() <= 101.0 && p.y.abs() <= 101.0, "bounded: {p:?}");
}
}
}
#[test]
fn polygon_fully_inside_is_unchanged() {
let ring = vec![
Pos2::new(10.0, 10.0),
Pos2::new(80.0, 10.0),
Pos2::new(80.0, 80.0),
Pos2::new(10.0, 80.0),
];
let out = clip_polygon(&ring, r());
assert_eq!(out, ring, "on-screen ring untouched");
}
#[test]
fn polygon_with_extreme_vertex_is_bounded() {
// A triangle with one vertex shot out to high-zoom infinity.
let ring = vec![
Pos2::new(20.0, 20.0),
Pos2::new(80.0, 20.0),
Pos2::new(1.0e9, 1.0e9),
];
let out = clip_polygon(&ring, r());
assert!(out.len() >= 3, "still a drawable polygon");
for p in &out {
assert!(
p.x >= -0.01 && p.x <= 100.01 && p.y >= -0.01 && p.y <= 100.01,
"every clipped vertex sits within the rect: {p:?}"
);
}
}
/// **Call-chain coverage (feeds the nornir matrix).** Sweep a family of
/// high-zoom "extreme vertex" inputs through both clippers and assert the
/// RETURN is (a) BOUNDED to the widget rect (no extreme vertex reaches the
/// tessellator) and (b) PRESERVED (the in-rect endpoint kept exactly). This is
/// the `clip` stage of the input→pixel chain, verified as data + one matrix row.
#[test]
fn clip_stage_bounds_extremes_and_preserves_onscreen_matrix() {
let rect = r();
let bound = 101.0_f32;
let mut cases = 0usize;
let mut ok = 0usize;
for &far in &[1.0e5_f32, 1.0e7, 1.0e9] {
for &(ix, iy) in &[(50.0_f32, 50.0_f32), (10.0, 90.0), (90.0, 10.0)] {
// polyline: an in-rect vertex out to an extreme one
let line = [Pos2::new(ix, iy), Pos2::new(far, far)];
let mut runs: Vec<Vec<Pos2>> = Vec::new();
clip_polyline(&line, rect, &mut runs);
assert!(!runs.is_empty(), "on-screen part preserved");
let mut bounded = true;
for run in &runs {
for p in run {
bounded &= p.x.abs() <= bound && p.y.abs() <= bound;
}
}
assert!(bounded, "no extreme vertex reaches the tessellator");
assert_eq!(runs[0][0], line[0], "kept the in-rect endpoint exactly");
// ring: a triangle with one extreme vertex → a bounded polygon
let ring = vec![Pos2::new(ix, iy), Pos2::new((ix + 30.0).min(99.0), iy), Pos2::new(far, far)];
let clipped = clip_polygon(&ring, rect);
assert!(clipped.len() >= 3, "still a drawable polygon");
for p in &clipped {
assert!(p.x >= -0.5 && p.x <= 100.5 && p.y >= -0.5 && p.y <= 100.5, "ring vertex in rect: {p:?}");
}
cases += 1;
if bounded {
ok += 1;
}
}
}
// fully-on-screen geometry is returned unchanged.
let inside = [Pos2::new(10.0, 10.0), Pos2::new(50.0, 60.0), Pos2::new(90.0, 20.0)];
let mut runs = Vec::new();
clip_polyline(&inside, rect, &mut runs);
assert_eq!(runs.len(), 1);
assert_eq!(runs[0].as_slice(), inside.as_slice(), "on-screen polyline untouched");
#[cfg(feature = "testmatrix")]
facett_core::testmatrix::emit(
"facett-geomap.clip",
"bounds_extremes_preserves_onscreen",
ok == cases,
&format!("{ok}/{cases} extreme-vertex clip cases"),
);
assert_eq!(ok, cases, "every extreme-vertex clip case stayed bounded ({ok}/{cases})");
}
}