Open michaelkirk opened 2 years ago
Do you have any strong feelings on whether abstreet::geom::Polygon.points should be closed?
The intention is for them to be. But a flat list of points for a polygon with holes is meaningless -- to be more clear, Polygon.rings
are all closed. The storage tries to be clever and avoid repetition right now -- per https://github.com/a-b-street/abstreet/blob/193672f19f4c288b4f8df0d3045c02f6ed8c0265/geom/src/polygon.rs#L66, if the polygon only has an exterior ring, then rings
will be None
and the points
should be closed. If there are holes, then the points
field is meaningless (it'll be all the points in the exterior ring, then each hole's points appended). The points() method should only return the exterior points, and they generally should be closed.
But all of the guarantees depend on how the Polygon
is constructed. The "good" cases are with_holes
, from_geojson
, etc. There are a handful of callers of buggy_new where all we try to do is render. What's probably happening here is precomputed, where that guarantee breaks down. This code path uses usvg
and then lyon
to tesellate polygons. Last I checked, the order of points it hands back aren't usually closed -- probably SVGs we render often have holes, so we'd have to figure out how to get that out of lyon
anyway.
Full disclosure is that more broadly I'm interested in making abstreet/geom more semantically consistent with georust/geo
Awesome! That's what I'd love to see too. A next (big) step would be to try to make geom::Polygon
just store geo::Polygon
and wrap APIs over it. Only rendering needs the triangulation, so the one caller of raw_for_rendering
could do something different. There are probably smaller intermediate steps.
In an ideal world, we can make sure every single construction of a polygon happens from closed rings. But in case all we can get out of lyon is a triangulated mesh, I wonder what we should do otherwise.
Also related: the other big geom
structure to rethink is PolyLine
. It's effectively a geo::LineString
that tries to enforce extra invariants, but that validation has been causing more and more problems lately. I've been working with GPS trajectory data lately where the points double back on themselves in all sorts of ways, but still being able to do some PolyLine
operations would be nice.
My unverified hunch is that this some problem with one or more of:
To test the theory that the problem is usvg + lyon feeding into Polygon::precomputed
and not giving points in order or where first=last, try running A/B Street and looking at lanes/roads. That uses PolyLine::make_polygons
, which also calls Polygon::precomputed
, but there the points definitely are in order and closed
Ah! So the points returned from lyon are likely not even in any particular ordering WRT the winding of the polygon - it's basically just a bag of points
that can be triangulated with indices
.
It seems pretty unlikely that we'd be able to safely roundtrip that representation with geo.
Maybe GeomBatch
should have a way to store pretriangulated polygons, and not allow anything to access the Polygon
. These cases from lyon should directly use that, and not use geom::Polygon
at all. They likely break many of the methods in there now, and there shouldn't be many (any?) callers of those anyway. get_bounds
is one of the few valid things to do, and scale/translate transformations.
That sounds plausible! I may (may!) have a go at this tomorrow.
Maybe GeomBatch should have a way to store pretriangulated polygons, and not allow anything to access the Polygon.
I think I'm having a go at something along these lines.
My basic idea was to have two types:
Polygon
for a topologically conventional geometry (something that could feasibly be replaced by geo::Polygon)Tessellation
for a pre-triangulated entity suitable for renderingIt's going OK, but I think seeing it through could be a very large change. Here's my hack-and-slash WIP if you're curious: https://github.com/michaelkirk/abstreet/tree/mkirk/tessellation
I think at the end of it, Polygon wouldn't have an indices
field at all. And only at the point that you wanted to render the polygon (which you might not always want to), would you use earcutr to turn the Polygon into a Tessellation.
GeomBatch then, is a collection of Tessellations, not Polygons. I haven't gotten far enough to know if there will be any show stoppers with this approach, but it does seem like it's going to have far reaching implications that I might not have time to see through.
Does this approach seem reasonable?
Approach sounds perfectly reasonable to me! The difficulties I would anticipate...
GeomBatch::consume
... actually, scratch that. At a glance, all of them don't need a Polygon
rotate_around_batch_center
currently calls Polygon::rotate_around
, which is some pretty simple math that lives outside of geo
. Tesselation
will need to keep thisPolygon::buggy_new
callers remain awkward, because some of them aren't just rendering. For example, convert_osm/src/osm_geom.rs
tries to get Polygons
to store for areas and buildings. (Mostly those are just rendered later, so you could maybe argue map_model
could just store that instead?) But also, it might be fine to just start failing here if the multipolygons we're scraping from OSM aren't valid rings. I don't entirely remember what motivated adding this in; it's likely some more fundamental bug handling multipolygons.So actually this hopefully shouldn't be too bad...
If it's OK, I'm going to pick up your branch and try to push through. I think the migration steps could be:
1) Introduce Tessellation
, convert Polygon
to it, use it for rendering
2) Replace current uses of Polygon::buggy_new
and Polygon::precomputed
with it
3) Make geom::Polygon
just wrap geo
In your branch you were very carefully changing the API for places that directly construct a tessellation, but I won't attempt that until maybe a step 4. It's a huge refactor.
I got too ambitious as usual! https://github.com/a-b-street/abstreet/tree/geo_polygon_too_quickly is a start, but I realized some more complications:
earcutr
. Need to think through this, and also measure to see if it's actually going to be a problem.geo::Polygon
. geo::Polygon
kind of pretends multipolygons are single polygons sometimes, which is weird.I do see a few smaller steps to peel off first, to make the migration easier. I'll see if I can get rid of a few places that construct geo::Polygons
in strange ways.
geo::Polygon kind of pretends multipolygons are single polygons sometimes, which is weird.
Can you expound on this? I'm not sure what you mean.
I've got a few steps to remove callers that construct "bad" polygons. Then we can switch to tessellations for rendering, and consider step 3.
Can you expound on this? I'm not sure what you mean.
I'm mistaken. We always transform a geo::MultiPolygon
into Vec<geom::Polygon>
. I was thinking of geom::Polygon::union, which is just doing something bizarre. I'll whittle away the callers of this one too.
Remaining work before the polygon cleanup can be considered done:
Polygon
with an outer and inner ring, then clean up tessellation -> geojsonpolygon.center
change probably
I wanted to test out some new georust/geo features in the context of abstreet, and consequently I've been spelunking in abstreet::geom.
I ran into some inconsistencies while trying to roundtrip some abstreet::geom::Polygyon to/from geo::Polygon - it resulted in some corrupt rendering like this:
My unverified hunch is that this some problem with one or more of:
points
array and the precomputed triangulationindices
While digging into that, I noticed that some (but not all) of the abstreet:geom::Polygon.points are closed. Do you have any strong feelings on whether abstreet::geom::Polygon.points should be closed?
Full disclosure is that more broadly I'm interested in making abstreet/geom more semantically consistent with georust/geo, in hopes of make future inter-op easier, but I'm also aware that these are the kinds of changes with no immediate benefit that could have a long tail of bugs in a system which is more or less currently working.