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

Speed up scan-line rendering using "Active Edge Table" #90

Closed
antonfirsov opened this issue Sep 18, 2020 · 2 comments · Fixed by #96
Closed

Speed up scan-line rendering using "Active Edge Table" #90

antonfirsov opened this issue Sep 18, 2020 · 2 comments · Fixed by #96

Comments

@antonfirsov
Copy link
Member

antonfirsov commented Sep 18, 2020

Currently, brute force search is being used when calculating intersections, the scanline is being tested against all lines in the polygon for each row. This means O(h*n) intersection tests where h is the number of horizontal edges and n is the number of lines.

The fastest way to achieve significant improvement with a (relatively) scoped change is to refactor the intersection detection logic to use an "Active Edge Table". In short this means:

  • Sorting edges by both minimum y and maximum y
  • Maintaining a list of edges which are currently intersected ("active") while iterating the scanlines
  • .. so intersection tests are no longer needed, it's enough to calculate intersection points only for edges which are active.

This should reduce the number of intersection calculations to O(n*log(n) + h*p), where p is the highest number of intersection points in a row during the scan.

Some sources describing the algorithm:

Not in scope

Improving accuracy further (aka #5 and #15) is not my main goal here, the only criteria is to not regress. But I hope I can achieve better results, or at least get some insights.

Plan

  1. Expose an API on IPath returning tessellation results to be consumed by a horizontal scanline rasterizer. These should be stored in a memory-efficient, cache friendly form. A data structure equivalent to (PointF, Orientation)[][] could probably do the job, where Orientation is always assuming a horizontal scanline crossing the point.
  2. Introduce a separate ScanlineIterator class that takes the tessellation, and exposes an API to iterate the horizontal scanlines.
  3. Utilize ScanlineIterator in drawing code where we currently use FindIntersections, particularly: FillRegionProcessor<T>, DrawTextProcessor<T>
@tocsoft
Copy link
Member

tocsoft commented Sep 18, 2020

Yeah that sounds good to me... I am assuming implementation wise most Path implementations will be forwarding to a common helper for generating the tessellation results from the Flattened representation? if that's the case I think we should instead introduce a new interface ITesellationAwarePath (name?) that we try casting to first (for thing like Rectangle I think) and if it doesn't implement it then use the shared helper instead. Its all then just mostly an implementation detail of the renders then and we don't have to expose it to most users.

@antonfirsov
Copy link
Member Author

Yeah, being very conservative about public API-s, I had the same thought. ITesellationAwarePath (or whatever) and the resulting Tessellation shall be internals.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
Development

Successfully merging a pull request may close this issue.

2 participants