search

mapbox / earcut.hpp

Fast, header-only polygon triangulation
ISC License
858 stars 133 forks source link

Use Node pointers plus object pool, eliminate separate vertices array #10

Closed jfirebaugh closed 9 years ago

jfirebaugh commented 9 years ago

This brings the code closer to the JS implementation, and ensures that it is usable by mapbox-gl-native per #9.

It turned out that discarding unused vertices was not the only way that the indices generated by earcut.hpp were out of sync with input order indices. There were two other sources of desynchronization:

@mourner This implements an optimization I think we should try for the JS implementation: f4b0a71df0863bc495cae66170dafc492f489c8f.

Before

+----------------+--------------------+--------------------+
| Polygon        | earcut             | libtess2           |
+----------------+--------------------+--------------------+
| bad_hole       |      236,350 ops/s |       45,378 ops/s |
| building       |    1,368,602 ops/s |       95,842 ops/s |
| degenerate     |    6,521,502 ops/s |      140,091 ops/s |
| dude           |       57,436 ops/s |       26,954 ops/s |
| empty_square   |    2,388,727 ops/s |      128,094 ops/s |
| water_huge     |          198 ops/s |           56 ops/s |
| water_huge2    |          121 ops/s |           76 ops/s |
| water          |          984 ops/s |          157 ops/s |
| water2         |          895 ops/s |        1,059 ops/s |
| water3         |       19,759 ops/s |       12,212 ops/s |
| water3b        |      324,605 ops/s |       70,983 ops/s |
| water4         |        3,580 ops/s |        2,139 ops/s |
+----------------+--------------------+--------------------+

After

+----------------+--------------------+--------------------+
| Polygon        | earcut             | libtess2           |
+----------------+--------------------+--------------------+
| bad_hole       |      269,340 ops/s |       50,289 ops/s |
| building       |    1,371,622 ops/s |       92,864 ops/s |
| degenerate     |    3,121,045 ops/s |      133,643 ops/s |
| dude           |       62,258 ops/s |       26,381 ops/s |
| empty_square   |    1,526,363 ops/s |      124,834 ops/s |
| water_huge     |          181 ops/s |           57 ops/s |
| water_huge2    |          106 ops/s |           73 ops/s |
| water          |          949 ops/s |          164 ops/s |
| water2         |          985 ops/s |        1,065 ops/s |
| water3         |       22,098 ops/s |       11,823 ops/s |
| water3b        |      355,213 ops/s |       70,583 ops/s |
| water4         |        3,775 ops/s |        2,129 ops/s |
+----------------+--------------------+--------------------+

So the degenerate results are slower, but they are super fast anyway. Real-world cases are a wash.

cc @kkaefer

mourner commented 9 years ago

This implements an optimization I think we should try for the JS implementation: f4b0a71.

Interesting! So you suggest storing x and y in Node instances instead of using data[node.i], data[node.i + 1] for all calculations, right?

Why would this be faster? Better memory access, or shorter path to data?

jfirebaugh commented 9 years ago

Yeah, I don't know for sure that it would be faster, but intuitively, since you usually already have a node reference available, it should be faster because it avoids two memory accesses and may also improve cache locality.

jfirebaugh commented 9 years ago

I would like to eliminate the boost::pool dependency from this PR and instead use a simple preallocated std::unique_ptr<Node[]> with one Node for each input vertex. This would depend on eliminating the second place that Nodes are created:

https://github.com/mapbox/earcut.hpp/blob/bfbe17d74dd68207219c8c63d6338d116741799d/include/earcut.hpp#L761-L762

@mourner @kkaefer Is it somehow possible to reuse the existing Nodes in splitPolygon rather than creating new ones?

mourner commented 9 years ago

@jfirebaugh I believe not since new nodes have different prev/next/prevZ/nextZ pointers. However, polygon split is a relatively rare occurrence — once for each hole and a few more times in case of bad data, so maybe you could do some manual dynamic allocation magic specifically for these.

mourner commented 9 years ago

:+1: for merging, @kkaefer said :+1: in Slack too.