Antialiasing polygons and trimeshes
- Dominant language
- Python
- Stars
- 3.6k
- Forks
- 376
- Avg merge
- 4h 32m
- Merged PRs (30d)
- 1
Description
So far we only have antialiasing for lines. It would be easy to add it for points. What about polygon and trimeshes?
Consider rendering a triangle at a time, as this is what is effectively done even if it is hidden within the polygon scan-line algorithm. A non-antialiased triangle has a sharp edge, effectively going from an `alpha` of 1 to 0 at the edge. For an antialiased triangle this edge region has a finite width of typically one pixel over which the `alpha` goes from 1 to 0. Half of that edge is inside the triangle, half of it is outside. To render a single antialiased triangle we therefore need to expand the triangle by half the antialiased width, and this always in a direction perpendicular to the edge. Pixels within the edge region need to calculate their `alpha` based on perpendicular distance from the non-antialiased edge, in the same way as `Canvas.line`. Special handling is needed at corners and probably these should be rounded corners as this is simplest to implement (compared to miter or bevel corners) and is what is done with `Canvas.line`.
That is all easy. The complexity comes with multiple triangles. You might be rendering two triangles that meet at a common edge and you might be using a `sum` aggregation of some per-triangle `value`. Care will be needed here with the mathematics that combines contributions from both triangles in the antialiased edge region so that it looks reasonable. If both triangles have the same `value` then after rendering the edge should not be visible, so adding the contribution from one triangle with a particular `alpha` to the contribution from the other triangle with a `(1-alpha)` must be robust. That might involve the distance calculations using points that are sorted in some way so that there is no possibility of `(a-b)` and `(b-a)` having different rounding errors.
There are also potential problems here with very thin triangles. The original edge of the triangle has an `alpha` of 0.5 (because half the antialiased edge is outside and half inside the triangle) so adjacent thin triangles won't necessarily accumulate `alpha` up to the expected value. This could be addressed by a second-stage aggregation. Or alternatively an approach which is not based on individual triangles but is able to answer the question "is this particular x, y point within a triangle/polygon or not". The danger here is that the computation complexity scales very badly with increasing complexity of the geometry.
Contributor guide
No contributing guide indexed for this repository
Research direction
Start by tracing the existing Canvas.line antialiasing behavior and the polygon scan-line algorithm mentioned in the issue. Determine how polygon and trimesh rendering currently handles triangles, then define tests for antialiased edges, shared edges, and very thin triangles. Done means polygons and trimeshes render with consistent antialiasing without visible seams or incorrect aggregation.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- python
- Domain
- computer-graphics, data-visualization
- Issue type
- Feature
- Difficulty
- 5/5
- Estimated time
- Over a week
- Activity status
- Stale
- Clarity
- Mostly clear
- Newbie friendliness
- 32/100