Scene#drillPick performance scales poorly

[thw0rted]

Sandcastle example: Open, then click anywhere on the map to select between the top-left corner of the canvas and the clicked location. The console tab will log the number of pins included (to make sure the correct point was used) and the time in milliseconds spent in the call to drillPick.

Browser: Chrome stable, latest

Operating System: Win10 latest

---

There are 2 related problems here.

First, try zooming and scrolling such that you have a few pins (say 3x3 to 5x5 square) in the top left corner (say 200x200 px or so). On my machine I can pick 9 pins in a 150x150px region in 70ms. Now, without moving the camera, click close to the bottom right corner. On my machine that was a 900x600px region with 228 pins -- and the call locked the main thread for a full 8 seconds (!). By contrast a pick with the same region (900x600px) only takes 50ms if there are no pins in it.

Second, zoom way out so that most of the pins are huddled in the top-left corner. I'm able to get all 400 pins in a 150x150px region, and it "only" takes 1400ms -- a lot longer than 9 pins in the same region, but a lot shorter than the same number of pins in a much larger region.

So, it seems that drillPick runtime scales by both the size of the region being considered, and the number of entities in the region, but neither relationship is linear. I'm hoping somebody has some bright ideas to improve performance, but I'd also welcome suggestions for going about this another way. I've seen suggestions to derive a Rectangle representing the selected region, then check the Entity position using contains, but that scales poorly compared to drillPick if most of your Entities are offscreen, and also doesn't handle the case of Entities that don't need a position e.g. because they just use non-relative Graphics like polygon / polyLine / etc.

[thw0rted]

I found a few similar posts about Globe#pick but nothing specific to drillPick. Is #630 related?

I also found #1592 , from 7 years ago (!), where people have been asking for a way to mark entities as "unpickable". In my actual use case I do have some entities that are marked for "never-select". These are filtered out after drillPick runs, which is how that issue suggests handling things, but maybe if there were a core property that implemented this, drillPick could avoid doing some work? Anyway that issue had a ton of interest and a PR at #4410 but never actually got implemented.

[ebogo1]

@thw0rted Thanks for the detailed write-up. I'd say this is related to #630 but since this is specific to drillPick I think it should remain open. We'll take a closer look at this when we get the chance.

[Huyston]

I'm also having this problem. In my case, there are thousands of Polygons, but selecting a region with about 100 takes 5 seconds. If I select more than 400, the page gets unresponsive and sometimes it crashes. I also have a warning saying :
Canvas2D: Multiple readback operations using getImageData are faster with the willReadFrequently attribute set to true
I don't know if that might affect the performance, but I can see in the profiler that readPixels gets called several times.
I also noted this comment:

cesium/packages/engine/Source/Scene/Picking.js

Line 488 in 27abb99

// PERFORMANCE_IDEA: This function calls each primitive's update for each pass. Instead

I didn't understand why it toggles the visibility for this feature to work yet. But maybe this is slowing the process down.
Changing the material of the whole dataSource in a for loop takes about 3 seconds more than selecting only a small part (less than 0.001%) with drillPick.
If anyone has a hint on what needs to be done, please let me know.