Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Cycle::winding makes assumptions that don't hold for all cycles #2130

Open
hannobraun opened this issue Dec 11, 2023 · 0 comments
Open

Cycle::winding makes assumptions that don't hold for all cycles #2130

hannobraun opened this issue Dec 11, 2023 · 0 comments
Labels
topic: core Issues relating to core geometry, operations, algorithms type: bug Something isn't working

Comments

@hannobraun
Copy link
Owner

Cycle::winding is a method that computes the winding of a cycle (as the name suggests), meaning it determines whether a cycle's half-edges are oriented clockwise or counter-clockwise. The method works well for all cycles made up of straight half-edges (i.e. polygons) and circles. It does not work for all cycles that contain arcs, as it makes some assumptions that don't always hold in the presence of those.

Exhibit A:

let circle = match first.path() {
SurfacePath::Circle(circle) => circle,
SurfacePath::Line(_) => unreachable!(
"Invalid cycle: less than 3 edges, but not all are circles"
),
};

Imagine a half-circle whose end-points are connected by a line segment. Totally valid, but unless the arc happens to be the first half-edge in the cycle, it will trigger this panic.

Exhibit B:

// Now that we got the special case out of the way, we can treat the
// cycle as a polygon:
// https://stackoverflow.com/a/1165943
let mut sum = Scalar::ZERO;
for (a, b) in self.half_edges().pairs() {
let [a, b] = [a, b].map(|edge| edge.start_position());
sum += (b.u - a.u) * (b.v + a.v);
}
if sum > Scalar::ZERO {
return Winding::Cw;
}
if sum < Scalar::ZERO {
return Winding::Ccw;
}
unreachable!("Encountered invalid cycle: {self:#?}");

The comment is wrong! Imagine a crescent shape. This code treat that like two coincident line segments, meaning sum will be zero and we'll run into the panic.


There might be more issues, but those are two that I happened to discover. I believe this once worked as designed, when we were limited to line segments and full circles. Once arcs were introduced, the assumptions here no longer held.

I think it makes sense to hold off on fixing this. Nobody has complained about this so far, and if #2118 works out, fixing it will become trivial.

@hannobraun hannobraun added type: bug Something isn't working topic: core Issues relating to core geometry, operations, algorithms labels Dec 11, 2023
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
topic: core Issues relating to core geometry, operations, algorithms type: bug Something isn't working
Projects
None yet
Development

No branches or pull requests

1 participant