Viewport physics_object_picking_sort does not always pick the top objects by z-index/scene tree order in an area with more than 64 objects

[ryanabx]

Godot version

4.2 dev 3 [013e8e3]

System information

Godot v4.2.dev3 - Windows 10.0.22621 - GLES3 (Compatibility) - AMD Radeon(TM) Graphics (Advanced Micro Devices, Inc.; 31.0.21023.2010) - AMD Ryzen 9 6900HS with Radeon Graphics (16 Threads), Web Browser: Chrome 116.0.5845.96

Issue description

The physics_object_picking_sort property on viewports does not work 100% of the time when a large amount of physics objects are in the same place.
EDIT: This appears to be due how the raycast to detect pickable physics objects works. Basically, the raycast has a 64 object limit, and the 64 objects it picks could be any random 64 objects in an area, not explicitly the top 64 objects in an area. All the physics_object_picking_sort property does is sort the random 64 objects hit by z-index and scene tree order. I suggest that if physics_object_picking_sort is set to true, the raycast should only call input_event on the top 64 objects hit by the raycast by z-index or scene tree order.

My current project, see how my selection is not always the top most item in the scene tree.
https://github.com/godotengine/godot/assets/56272643/c59ea07d-39a9-4650-b7d5-a10bc33e0eca

My minimal example project (the output is showing the index and name of the first item that has _on_area2d_input_event fired:
https://github.com/godotengine/godot/assets/56272643/dcc8f77e-9907-461a-834c-2613d376cfff

I believe this is happening due to how picking works. I remember hearing that picking uses a raycast to determine overlapping physics objects, and that ray is limited to 64 objects. The problem is, the 64 objects it chooses are not necessarily in scene tree order or z-index order even if physics_object_picking_sort=true.

Steps to reproduce

• Create a project with over 64 overlapping Area2Ds with the pickable property set to on. Set the viewport's physics_object_picking_sort property to true.
• Connect the input_event signal to each Area2D printing identifying info about the Area2D (name perhaps, or index).
• Notice how the topmost object does not always fire an input event when picking.

Minimal reproduction project

godot-bug-report.zip

[Sauermann]

This is currently hardcoded to 64 by design. See

godot/scene/main/viewport.cpp

Line 796 in b51ee8b

int rc = ss2d->intersect_point(point_params, res, 64);

It also affects intersecting when sorting is disabled.

I'm unsure about possible drawbacks, if that number would be increased.

How many elements would be sufficient for your use-case?

[ryanabx]

I imagine the drawbacks would be performance related, if the number were increased. The amount of elements sufficient for my case would just be one, as I need to only pick the top object by draw order (identical to scene tree order / z-index).
The problem is that the ray that is intersected does not pick the top 64 objects by scene tree order / z-index. I believe that if Viewport.physics_object_picking_sort is set to true, then the ray should intersect the top 64 scene tree objects. If the setting is disabled, for performance reasons, the non-deterministic behavior makes sense.

EDIT: In case the current behavior isn't noted,
Let's say there are 65 objects, and I wanted to select the top object in the scene tree (Object65, for this example), the objects the ray intersects in any given time could be any combination of the 65 objects, so objects 1-64 could be picked instead of the top object, Object65.

[Sauermann]

Sorry, it looks like my question was ambiguous. What I actually wanted to know was how many Area2D objects do you have in your scene, that could be hit simultaneously in a single raycast.
Would increasing the number from 64 to128 be enough or are we talking about an order of magnitude more?

[ryanabx]

Sorry, it looks like my question was ambiguous. What I actually wanted to know was how many Area2D objects do you have in your scene, that could be hit simultaneously in a single raycast. Would increasing the number from 64 to128 be enough or are we talking about an order of magnitude more?

My bad, I misunderstood. Probably the max I'd be working with is about 10,000 pickable area2ds in one place, so yes, an order of magnitude more. I'm working on a virtual tabletop, with game pieces stacked on each other. I would like to find the least computationally expensive way to pick the top item off a stack when clicking on the stack.

[Sauermann]

about 10,000 pickable area2ds in one place

With this amount of pickable objects you come in a range where this can no longer be considered a bug, but rather a feature proposal.
I kindly ask you to head over to the Godot Improvement Proposals repository and create a proposal for your use-case.

In the meantime, I would like to suggest, that you consider alternative approaches to your problem. Perhaps you can optimize your algorithms in a way that you reduce the amount of pickable objects.

[Zireael07]

What do you need 10k area2ds in one place for!?

[ryanabx]

In the meantime, I would like to suggest, that you consider alternative approaches to your problem. Perhaps you can optimize your algorithms in a way that you reduce the amount of pickable objects.

I will put in a proposal, thank you very much! :)

What do you need 10k area2ds in one place for!?

The virtual tabletop I am working on has support for stacking pieces, and some stacks can get very large (~10k objects). For performance reasons, I have optimized this and simply put piece information into the stacks themselves and remove the piece nodes. I still need the ability to pick more than 64 objects in a reliable order (I fixed this by doing the intersect_point calculation myself and setting the max_amount to 65535 (which I will realistically never hit).

I will still put in a proposal because I feel that the behavior of physics_object_picking_sort should at least be documented if it's not going to change.

[Sauermann]

Documenting the behavior is a good idea. See #80875.

[Zireael07]

@ryanabx You really have more than 64 unique stacks in one place?

[ryanabx]

@ryanabx You really have more than 64 unique stacks in one place?

Not anymore. I optimized my code and made stacks a singular object with information about the cards inside.

Having the behavior documented is enough for me, just in case anyone runs into the problem in the future :)

[Sauermann]

Closing this issue as indicated in the post above.
Documentation got fixed in #80875.