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

Improve performance of the visibility sweep #4642

Conversation

kwvanderlinde
Copy link
Collaborator

@kwvanderlinde kwvanderlinde commented Jan 16, 2024

Identify the Bug or Feature request

Final piece of #4506

Description of the Change

A number of changes were made to the visibility sweep to improve performance:

  • Avoiding JTS Geometry where it isn't needed. Often we weren't even relying on the general Geometry behaviour but were still paying a cost for it.
  • The algorithm more closely follows the original idea, prefering cheap comparisons between walls and endpoints rather than heavy intersection checks.
  • An improved graph representation where VisibilitySweepEndpoint is the nodes, and edges are merely references to other VisibilitySweepEndpoint.
  • Skipping over blocking segments that are hidden by other segments and so cannot contribute to the result.

Altogether this brought the test case in #4506 down from ~15.5 seconds to ~2 seconds on my test machine.

Possible Drawbacks

Should be none.

Release Notes

  • Improved fog-of-war exposure performance for long paths and complex MBL

This change is Reviewable

The sweep is now based on `LineSegment` instead of `LineString` as it is a bit easer to work with and avoids some of the
cost associated with `Geometry`.

The intersection check for whether to include a blocking segments is now against the vision bounding box rather than the
precise vision geometry. There is a tradeoff here as more segments can be excluded the more precise we are, but in
practice the extra precision does not gain us nearly as much as it costs.

`VisibilityProblem` is now responsible for collecting and organizing segments. `VisionBlockingAccumulator` only decides
how to treat each topology type, but otherwise forwards to `VisibilityProblem`. This avoids some expense around building
large lists of segments.
A new `EndpointSet` class is responsible for maintaining the endpoints and walls for the visibility sweep. It avoids any
use of endpoint hashing in favour of retroactively merging the few duplicated endpoints we
receive. `VisibilitySweepEndpoint` now references other `VisibilitySweepEndpoint` to define walls instead of using
`LineSegment`, which saves on some redundancy and make it really easy to validate the graph.
This change moves much closer to Asano's original algorithm as described in section 3.2 of "Efficient Computation of
Visibility Polygons" ([arXiv:1403.3905](https://arxiv.org/abs/1403.3905)). The critical difference is in how we find the
nearest wall, in particular:
1. Keeping the open walls ordered by distance to the origin, so that the nearest one is always at the front.
2. Using a cheaper orientation-based comparator for the open walls that does not depend on any finding any
   intersections.

Since we don't have to intersect walls in order to find the nearest one, we can now limit ourselves to a single nearest
wall check per iteration, as opposed to the two that used to be used. Intersections are only calculated when we need to
add a point to the result that does not lie on one of the input endpoints.
There are plenty of cases where a wall is completely hidden behind other open walls and therefore cannot contribute to
the result. Instead of marking these as open, we can skip them completely and avoid a lot of expense during the sweep.

In order to keep the check cheap, walls are only checked against the nearest wall, not against all open walls that might
hide them.
A lot of things have been documented, names improved, and `VisibilityProblem` has been rearraanged to keep the core
public stuff first. There are also fewer assumptions and `assert` checks made in several places, instead opting for
being able to handle a wider variety of situations. If the sweep ever fails, an exception is thrown rather than
returning a null (no blocking) result - `FogUtil` handles this and simply does not expose any area in this case while
logging the error.
The new comparator is based on point orientation around the origin rather than directly depending on angle. This is much
cheaper, and means we don't have to cache calculations on `VisibilitySweepEndpoint` thus making it simpler.

`EndpointSet` also buckets endpoints according to which eighth of the plane the point is in. Sorting can be done on one
bucket at a time which reduces the number of comparisons needed. The buckets also remove the need for some special cases
in the comparator, further streamlining the sort.
@cwisniew cwisniew added this pull request to the merge queue Jan 17, 2024
@cwisniew cwisniew added the performance A performance or quality of life improvement label Jan 17, 2024
Merged via the queue into RPTools:develop with commit 77af361 Jan 17, 2024
4 checks passed
@kwvanderlinde kwvanderlinde deleted the refactor/4506-visibility-sweep-performance branch January 17, 2024 01:17
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
performance A performance or quality of life improvement
Projects
Development

Successfully merging this pull request may close these issues.

None yet

2 participants