New triangulator
kind: incompletearea: graphics
Commit 4d5fd47045a18752b63dc0a48ee55d9e300738f2 adds a new polygon triangulation algorithm which intrinsically avoids T-junctions, but is not yet complete or efficient. It is disabled so as not to cause problems.
Bugs to fix:
* [X] The big one: Holes in polygons are often incorrectly half-covered. Fixing this will require either some angle/winding order tests (not sure if that's robust) or a different scheduling of the vertex processing (that might be too much slower). (Done in 8b13d5f24113f035d68745c5867df90db2059f9e.)
* [X] Texture clamp coordinates are not computed per-triangle, which causes cracks. I’d like to figure out a way to fix this on the shader side (check the alpha of the interpolated value?), ~~but if not, we’ll need to split currently shared vertices.~~ (Done in 9a20e3cb116845a9b94522d3fbc62c3ba0a6705f.)
* [x] Completely disregards transparent surfaces meeting opaque ones when using `TransparencyFormat::Surfaces`, and panics as a result. Plan for that: run the triangulator twice, once for `opaque` bits and once for `renderable & !opaque` (transparent) bits. (Started in 940fe0af9cd0e847a1aad4086af8edf0202eeeb4; finished in eff87edff0c036bb763bd52e2fd197b4427705e5.)
* [ ] Depth sorting assumes triangles are always paired as quads. It needs to handle individual triangles. (As an optimization, keep track of whether we have any non-quads and use both versions.) (Started in 7b5fedbe237887b5d99aa39ef76659b1a4aa5cf1.)
Non-bug work:
* [x] Reuse allocations for efficiency. (Done in 94e2f1d659005ddd4413b6b9e0798417551d11c0, 46eb8d4dbf3ea504b6a98f92a9c0049b121ceaa1.)
* [ ] Seek further optimizations
* ~~Smaller integer types?~~ Doesn't seem to help.
* What if we refrain from ever copying vertices and always borrow/index them?
* [ ] This triangulator takes only vertices as input rather than scanning voxels, so it has no use for the PlaneBoxes, only for knowing which planes are nonempty. ~~Currently, we use those boxes to compute clamp rects, but that might be going away.~~ If the boxes end up unused, remove them.
* [ ] Tidy up which code is in compute.rs vs. in planar.rs.
4 条评论