-
Notifications
You must be signed in to change notification settings - Fork 27
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
Update 2D GWN algorithm to match paper #1407
Conversation
…NL/axom into feature/spainhour/siggraph_2d_updates
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
Thanks @jcs15c !
Before merging, I'd like to check that our winding number example application still works on all the test shapes from our data repo -- https://github.com/LLNL/axom_data/tree/main/contours/svg
(I haven't gotten around to adding automated tests for these yet, but it's on my todo list).
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
Thank you @jcs15c Very nice summary of the changes in the PR.
Thank you, Jacob! |
@kennyweiss I checked against these shapes, and although the results are consistent with the Either way, it'd definitely be worth it to automate those tests somehow, these issues would have stuck out immediately. |
Awesome -- thanks @jcs15c. Now that the issue's resolved, feel free to merge this PR. We'll automate those tests in a follow-up PR. |
for(int i = 2; i < 15; ++i) | ||
{ | ||
// In all cases, the winding number should be *near* 0.5. | ||
// If the tolerances don't match, we would get an "off-by-0.5" error | ||
|
||
double diff = std::pow( 10, -i ); | ||
EXPECT_NEAR(winding_number(Point2D({0, diff}), quartic, 0.5 * diff, EPS), 0.5, 0.1); | ||
EXPECT_NEAR(winding_number(Point2D({0, diff}), quartic, 1.0 * diff, EPS), 0.5, 0.1); | ||
EXPECT_NEAR(winding_number(Point2D({0, diff}), quartic, 2.0 * diff, EPS), 0.5, 0.1); | ||
} |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
This is a great test!
Would it makes sense to also test Point2D({0, -diff})
?
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
Probably! The internal tolerance checks don't care which side of the closure the point is on, but might as well check it here too.
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
It actually made a lot of sense! There was the exact same issue with the BoundingBox
check, since the closure is coincident with an edge. This means it would be counted as "outside" the bounding box but "on" the edge, and therefore give the wrong answer. I'm actually surprised that this didn't come up as an issue in the previous versions of winding_number<Bezier>
, since nothing new to this PR has changed this behavior. Neat!
This one's a lot easier to fix, since it just involves adding the same edge_tol
parameter to the bounding box checks via their .expand()
method.
Summary
This PR is an upgrade of the existing 2D generalized winding number (GWN) algorithm so that the implementation more closely matches the pseudocode in the paper "Robust Containment Queries over Collections of Rational Parametric Curves via Generalized Winding Numbers". The updated algorithm is more analytically tractable and computationally efficient, significantly reducing the number of trigonometric operations needed to compute the GWN for near-field points.
This upgrade does not change the external API for existing GWN methods, but does alter function calls in the
detail
namespace, i.e., replacingcurve_winding_number_recursive
withconstruct_approximating_polygon
.Additionally, two additional functions are added to the interface provided by
winding_number.hpp
:winding_number<axom::Array<BezierCurve>>
winding_number<Polygon>
that has an additional reference parameter to report points located on the polygon boundary.Algorithm Details
Specifically, the current implementation recursively discretizes a Bezier curve into (potentially many) linear segments and computes the GWN for each segment, evaluating an arccosine for each. In contrast, the updated algorithm only evaluates a single GWN value for each point. In this way, the new algorithm more directly decomposes GWN evaluation of Bezier curves into the following sequence of actions:
axom::Polygon
object that provably has the same integer winding number as the closed curve at the point, and evaluate the integer with a point-in-polygon algorithm.Extra bugfix via refactor of
winding_number<polygon>
During review, an additional bug was found relating to the evaluation of the winding number for points that are near to the closing line. Specifically, it was possible for a point to be considered as interior/exterior to the approximating polygon object, but coincident with the closing curve during the computation of it's generalized winding number, causing an incorrect value to be subtracted from the GWN.
This "off-by-0.5" error, unacceptably high for points near the closing curve, is due to a different physical interpretation of numerical tolerances between
winding_number<polygon>
andwinding_number<line>
, where the former checks for colinearity of an edge's endpoints and the point using a determinant formula, and the latter checks for physical distance between the edge and the point.To fix this, the various numerical tolerances in
winding_number<polygon>
(which also includes an Linf distances to vertices) have been replaced with checks for physical distances between the query point and edges. This approach is nominally more costly, but makes the method considerably more usable in conjunction with otherwinding_number
methods. Beyond changing variable names, this change does not alter the interface of the existing method.An additional test has been added to
primal_winding_number
to verify the corrected behavior.