CesiumGS
Improve Clipping Polygon Performance
Feature
https://github.com/CesiumGS/cesium/pull/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.
Also reported in https://github.com/CesiumGS/cesium/pull/11750#issuecomment-2416350404
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...
This was also reported in https://github.com/CesiumGS/cesium/issues/12177 (and I think that one could be closed as a duplicate of this one)
Just to keep track of that:
The underlying issue here is that ~"a few very costly things are re-computed in each frame, even though nothing changed" (with details elaborated above).
It is not yet clear where and how this will be addressed exactly. But it will likely boil down to some form of
if (somethingChanged()) recomputeCostlyStuff();
else dont();
And in terms of the implementation of that somethingChanged, it may be worth noting that the ClippingPolygon.equals function currently implements a concept of "equality" that may not be perfectly suitable for this. Details described in https://github.com/CesiumGS/cesium/issues/12389#issuecomment-2561985063
As javagl said, PolygonGeometry.computeRectangleFromPositions cosumes too much performance, ClippingPolygon.prototype.computeRectangle will call it, and
Cesium.ClippingPolygon.prototype.computeRectangle is called from ClippingPolygon.prototype.computeSphericalExtents and ClippingPolygonCollection.prototype.computeIntersectionWithBoundingVolume, so I override Cesium.ClippingPolygon.prototype.computeRectangle as follow :
Cesium.ClippingPolygon.prototype.computeRectangle = function (result) {
if (!Cesium.defined(this._cachedRectangle)) {
this._cachedRectangle = Cesium.PolygonGeometry.computeRectangleFromPositions(
this.positions,
this.ellipsoid,
undefined,
);
}
if (Cesium.defined(result)) {
Cesium.Rectangle.clone(this._cachedRectangle, result);
return result;
}
return this._cachedRectangle;
};
Since the position and ellipsoid of a ClippingPolygon are read-only, we can safely cache its corresponding rectangle instead of calculating it every frame.
In my case, the performance improvement is huge(FPS increased from 3 to 60).
Applying the above code in the AEC Clipping Example also yields performance improvements:
| Before(30FPS) | After(60FPS) |
|---|---|
By the way, the AEC Clipping Example performance loss comes from Google Photorealistic 3D Tiles. If you remove it, the performance will be good engouh
@bbbbx This is similar to the change that I already did, in that ("hacky") branch that I linked to. But when you closely examine that, you'll notice that it is caching the positions. And this is important for the correctness of the result. You said
Since the position and ellipsoid of a ClippingPolygon are read-only, we can safely cache its corresponding rectangle instead of calculating it every frame.
It is true that ClippingPolygon.positions is marked as @readonly. But that does not mean that they cannot change.
(I also mentioned that in my previous comment: Unfortunately, there is something that I'd provocatively call an "anti-pattern that is built into JavaScript", and this is the complete lack of one of the most fundamental and important aspects of software engineering, namely information hiding. It is possible to work around that, and to do proper information hiding. But usually, this is just not happening 🤷♂ )
The point is that you can absolutely write code like this:
const positions = [
new Cartesian3(1,2,3),
new Cartesian3(2,3,4),
new Cartesian3(3,4,5),
new Cartesian3(4,5,6),
];
const polygon = new ClippingPolygon({
positions: positions
});
// Compute the rectangle
const rectangleA = polygon.computeRectangle(new Rectangle());
// --- !!! --- Change the positions --- !!! --
polygon.positions[1].y = 12345;
// Compute the rectangle again
const rectangleB = polygon.computeRectangle(new Rectangle());
The second rectangle should use the new, modified position (with that y-coordinate set to 12345). With simple caching, this will not happen. That's why I stored and compared the positions in my branch, but as I said: That was just an experiment, to illustrate that this might be one approach for a fix. Further details have to be investigated.
For example, you mentioned the ellipsoid as well. It's admittedly not even clear for me whether an Ellipsoid could change, i.e whether it is technically possible to do something like
polygon.ellipsoid.someProperty = newValue;
I think that this should not be possible. It will hardly ever make sense. And preferably, it should not be necessary to consider this. But verifying that requires more thought....
If you're going to the trouble of marking properties as readonly wouldn't it make sense to treat them as readonly and let non-conforming applications suffer the consequences of ignoring those annotations?
@GatorScott One could talk about this on a somewhat theoretical level, differentiating between terms like "readonly", "constant", "immutable", or "unmodifiable", with the further differentiation of whether these terms are meant to be "deep" or "shallow".
But pragmatically: The meaning of the @readonly tag in JS/TSDoc on this level is to convey that you can not do
clippingPolygon.positions = newPositions;
This does not say that you can not do
clippingPolygon.positions[3] = newPosition;
or
clippingPolygon.positions[3].y = 123;
Which of these modifications should be allowed or anticipated has to be decided.
