Improve Clipping Polygon Performance

[ggetz]

Feature

#11750 added an initial implementation of clipping polygons. However, some users are seeing performance hits depending on usage.

The performance hit is not directly correlated with the number of polygon positions. The geographic extent, concavity, and number of polygons also factor in. For example, the AEC Clipping Example is a particularly concave polygon with many positions shows this performance hit.

[ggetz]

Also reported in #11750 (comment)

[javagl]

The performance hit is not directly correlated with the number of polygon positions.

Certain aspects of the polygon shape may have an additional impact here. (For example, a polygon with 100 points that covers a pole and the IDL may have a larger impact than one that does not). But the performance hit is definitely correlated with the number of polygon points.

I created a sandcastle where you can crank up the number of polygon points from 4 to 500 (and it's a circle - i.e. as convex as it can be). And one can clearly see the performance hit:

The sandcastle:

https://sandcastle.cesium.com/index.html#c=hVZbU9s4FP4rmrzUWVwlFNi2ITA7DQvtTrswDdsXwoMiK7EGWfJIcqjb4b/vkeRrMG0eYl3O9dO5USWNRTvOHplGZ0iyR7RghhcZ/ubPotWI+v1CSUu4ZHo1itHPlUTI8owJOJmhDRGGxe6MSJ4Ry5XsHhrKJPuiEnbD6QPT3as1MewzKZl+frUVat2R/TQ+XcmVDJZiLxInbF1sl6l6vNQkY+aG6SWjSibgiNUF8wzUO2i5YIZZuCCPhNvaR6oZsexKqa1gN6myCvaCG8vp0cVtYImc3p7WXPOMW75jBpMkiSrRwbxNIalzHwXJC64pSFZcWhMBs2X6s5IxqpbExkiThBcmRrLIAt04oBvszv0RmH13f+pON0qjSIAjHM6mp/CZt5ywPTio2GsBBOg4mnSIurcCLD1DjWHoAH0hNsWGy4igP8Lm5hOs3ozhL5jaF0BsKwDWlQCqzG8FBNdwXpg0uhMOFRB2P/a3T+5PM1toWdHB8dMAwLfM2AtiSZQ/x85Wd2BgBYktc4io1egSWAvNFkoI5qVBTAcKCXHkKBxvc0i1mdUiWiGOtCEBd7TKmbacOdpGDjgwU1s6S9hm5sRcXy1mh/hotvi6fHe8GqGnir/+boJlIOOuFtwofmZ/RzukC1MZs7qcdRlali+FsPxGiXLb8Tb8qFI64RLQdGrvApL39x2ap2Zdr8Lt02nnnWq465dyUUoLrSE23PFSFZq6lBw8X6YkD/lKTCkpap65yBOXR4LnOZfbygETDWWLEgwLtYWK9Z9nQo/cpm3gnwHcB50089oQ4hsUVdUAHgnKWRI9s27cJFVVCJLmymDNMrVjA0x1ouxfQDwWstLVRvtevg/Uj9dvT/DhyZvj6bsYHb3H74//fP/2JEZTfBj33RrW2St8V0z9Y5RsCQA5kkR1vA+llrsL0gdAcIVwEIFBa/xrOyf3LzDsuMshvCOigA+AlESRPy3H6Ow8GLj3XuEa5yE4OobWmBruYglgfeFFvD01P04500TTtMRbZr85O6IxboR0BNO9qOz3z72YbYtN9LMugIGtk+svs0edrG5smbXLNkPH/RQNSFRNCg+YvH9U52+Ilxfy73jcaa4Uip0m15tN6LAdJz4yqPjAxi1NvxK5ZT7CqkvfHKz6CiQERE7xNJg+fP36+KQmOJnCD09XstOafyiV3apo+Gnjnold0x23m0xE3SSaRJqhYzx1c8fLVckzXmqVuVEp6vWeRgzI/bfI1jBINarwXrL+EugerX+XCp4HqeiDKiy2mtCHVrqjq/qfUmJN3FSXKFpkAIsL6L8Fc8sP5SdI91FFsxo5tn3JJM9F+QEyEAwyrYa4lux4/EBS+QwYIy5bTCtEXIVtnU+JuX6UN6FblpFjasvrngV1TDu7r9eG6R1ZC9a1xLM3ZKZYG6r5mkUDD9RMFh7FJZEJJcZCz4Dadau2MAF+KKyFTHNkq9GFQjaFiSYFdEuIH5oCChjjqnkOZyn21ItA7OmakIloymDETfZ9/ZUEl52BK9geh5BfyVE8mhtbCuYL4l88y5WGENIiwnhiWZYL180n6wJ4IemNj575pGaZJ3yHeHI2MNtDOSDG9cpNIcSS/4Ah43w+Afoem2sWYN/1jmlBSkeSHp5/DoeA0XwC2+dcTbB5q+fWPWZV0ed2rZLyvH7JudXnbb2b2+Q8JBFSm6pFzidw2CfpzjRzLvPC+ukHFGtXesC3jEvYubkrI99hBYUE1sayHDaHsHQt7fUaIh72vgPN2kyOkT8Js8UMvfIaXlXODOu17Lt1CgBGp+03Cnqiev7BpsYDlg1SsK4gDFj/Dw

Looking at a performance trace reveals (some of) the (potential) culprit(s):

Apparently, computing that rectangle for the clipping polygon takes a lot of time.

There are a few places where one could consider performance improvements. Computing this rectangle in each and every frame is certainly wasteful: I think that the positions of such a polygon will rarely change dynamically. But it is really important to be able to change them dynamically: We want the possibility to interactively drag around the points and update the clipping (...to eventually hit "Confirm" somewhere, and write some clipped result into a file or so...).

As an experiment, I just created a (hacky!!!) branch that just caches this rectangle, based on the positions.

(Yeah, storing the positions twice is also wasteful, in terms of memory - that's the usual trade-off. There are no fine-grained access controls (as in "information hiding") that would allow detecting modifications of the positions. Throwing in some function like clippingPolygon.updateThatStuff() that the user has to call after updating the positions wouldn't be ideal either. This is just an experiment, and clearly marked as such...)

The main point of this experiment is shown at the end of the GIF above: When using the check box to set that ClippingPolygon.hackyCaching flag (that is used in that branch to enable the caching), the FPS goes back to 60.

Maybe there's a "good" way to avoid recomputing that rectangle in each frame...