Expose an API for spatial queries (such as BVH)

[donn-xx]

Describe the project you are working on

1. A 3D game where you swim and the environment and life reacts to you in a dynamic way.
2. A scattering addon where I need to avoid overlapping meshes.

Describe the problem or limitation you are having in your project

Right now, I have a few choices:

1. Search through the entire multimesh.instance_count...
2. Hacking a spatial dictionary thing in gdscript (turns out it runs very slow).
3. Adapting some octtree or other algo from the net into gdscript.
4. Hoping someone writes an addon—so far have not seen one.
5. Somehow scattering thousands of Area3Ds with box collider shapes, which sounds insane.

There should be an API to some kind of spatial partitioning/querying algorithm for scripts to use.

Describe the feature / enhancement and how it helps to overcome the problem or limitation

(All in global space) First case I have a player and their bbox. I have a multimesh instance 3d node with a thousand meshes (transform instances) scattered. As the player moves through the multimesh I want to know which meshes are near (some sphere around the player) to them, so they can 'react'. A spatial API would let me query player's transform vs multimesh instance transform.

Another case I am writing a scatter addon. I want to scatter a cylinder and a sphere. I do not want them to overlap. A spatial API would let me query the candidate with what is already (maybe) in the same space.

Describe how your proposal will work, with code, pseudo-code, mock-ups, and/or diagrams

Here's a toy API:

spatialMagic.add(vec3pointA, mynode3D)
spatialMagic.add(vec3pointA2, someTransform)

if spatialMagic.seek( some_later_point, mynode3D ): print ("Yay we found mynode3D")
if spatialMagic.seek_anything( vec3pointA2 ): print("Oh dear, someTranform is already here.")

# toy scattering e.g.
for target_transform in potential_targets
  if spatialMagic.seek_anything( target_transform ):
     continue # already have something at or within that space
  # okay, add it my multimesh and the spatial magic thingum
  multimesh.add_instance(target_transform)
  spatialMagic.add(target_transform)

The objects should take up space (like a bbox size) and position in the spatialMagic structure. Think a spatial hash using a dict, but done in c++ with voodo. If this BVH thing can do that, then please expose it to gdscript!

If this enhancement will not be used often, can it be worked around with a few lines of script?

No idea.

Is there a reason why this should be core and not an add-on in the asset library?

My line of reasoning goes that if core needs BVH (and needed Octtrees in the past) then why would users of the engine not have similar needs?

If it becomes a plugin/addon that would be fine, but make it an 'official' one perhaps. The fear that plugins give is that they are frozen in time and may not work in 2 versions hence.

[lawnjelly]

I wrote all this below, but do suspect in your case, for the scatter addon you may be able to just use the existing VisualServer / RenderingServer functions ("instancescull*") that cause a stall, as a stall doesn't matter much in the editor. Also for in a game, there may be alternative way using areas to adjust to the Godot paradigm, which avoids the stall. Never-the-less have included the rest of this:

SPS

I'll just call these structures "spatial partitioning structures" (SPS for short) just because we have several of these available (3.x: my BVH in physics & rendering, 4.x: my BVH physics, Juan's rendering), and they could in theory change in future.

There's a massive load of considerations here and I can't pretend I've thought of them all, this is just a stream of some initial thought on the subject:

Physics & Rendering

The physics and rendering already use SPS, but there are two potential snags with using these for a general purpose: 1) They are highly specific to physics or rendering, so the information you get back as a user may not be so useful, or hard to make sense of 2) They are both in their own server, thus querying them in realtime from the client code is not possible (or at the least discouraged except in editor) because it will cause a stall as the servers have to sync with the client code. It breaks the order of operations and multithreading especially.

This is the reason these functions in 3.x in VisualServer (and RenderingServer in 4.x) are marked not to be used, because they cause a stall:

    // don't use these in a game!
    virtual Vector<ObjectID> instances_cull_aabb(const AABB &p_aabb, RID p_scenario = RID()) const = 0;
    virtual Vector<ObjectID> instances_cull_ray(const Vector3 &p_from, const Vector3 &p_to, RID p_scenario = RID()) const = 0;
    virtual Vector<ObjectID> instances_cull_convex(const Vector<Plane> &p_convex, RID p_scenario = RID()) const = 0;

Other Considerations

However there are some other considerations: 1) Maintaining a SPS is potentially expensive, and the cost has already been paid for physics and rendering, so any system for testing them is essentially "free" until use. 2) Conversely, adding an extra SPS client side for user testing adds extra housekeeping. 3) The server SPS can be used without causing a stall, but would require a deferred mechanism, which would likely be very difficult for client code (i.e. there would be a delay of a frame between issuing a query and getting a result).

There are probably existing workarounds to get this info with physics (Areas etc) but they may require working in a different mindset because of the delay.

Client side SPS

There are 2 obvious potential ways of exposing another SPS (if we decided to do it): 1) Have a default client side SPS that is generic and useful for all use cases. Always keep up to date if e.g. a project setting is switched on, and the project wants to use it. 2) All the user to create an SPS object directly from user code. They would then be responsible for filling it, updating it and querying it.

(1) would hide most of the complexity, but be an added cost, and would have to be carefully thought out to cover all use cases. (2) would be pretty simple to implement and future proof, but the burden of effort would be on the user to fill / maintain it (which is relatively advanced).

Just to mention also that you can reduce the maintenance cost of an SPS by just making it a flat list of objects, and using raw CPU to test the objects. The physics and rendering use tree structures (which are more expensive to update) as a trade off, so they will in turn be faster for the types of tests required. Testing in some cases does not require a tree structure, just that the tests are done efficiently (e.g. using SIMD etc).

Relationship with ray casting

Worth mentioning as well is this ties in with the whole discussion going on about ray casting. The needs / requirements of a ray casting API are similar to those in this proposal. It would ideally be client side, have an SPS, but be able to additionally optionally go down to the level of ray tracing rather than bounding boxes.

Funnily enough I wrote a ray tracing library 3 years ago for my lightmapping module, and exposed it to gdscript for a test: https://twitter.com/lawnjelly/status/1352602174543552515

I never went anywhere with this, but it shows that efficient ray tracing is possible from user code (i.e. millions of ray tests) as opposed to using the physics API which is really only suitable for small numbers of tests.

This is just a suggestion that the two could be combined. For ray tracing functionality, you'd probably need to maintain a separate copy of the geometry data in accelerated form, so there would be some RAM costs.

[donn-xx]

The SPS need not be BVH. Even an oct/quad tree exposed by API would be enough for a whole lot of useful things. Maybe even a spatial hash/dictionary thing but done by boffins in optimized C++.

I'm not on your brain-level with this stuff, so I'm not sure how to communicate that I (a simple dev) need a simple spatial structure thing to use and be quick. Like FastNoiseLite, perhaps a Resource that provides an SPS could be invented?

[Zireael07]

I concur, just a quad/octree would be enough for most end users.

[thygrrr]

I disagree that a Quadtree is enough. In fact, it rarely is unless for the most boring culling tasks.

Generally, a kd-Tree may be better than just a Quadtree here; but I believe it should just be a part of Space(2D/3D)

However, I would not want this data structure to be exposed (unless to GDExtension), because I believe most users would actually want a spatial query.

So query functions in the same spirit as PhysicsDirectSpaceState(2/3)D.intersect_ray(); (in particular, physics-based), the more the better; but at the very least:

Sorely missing Spatial Queries:

2D and 3D spatial queries, with overloads for: Physics Layers and Masks, as well as Rendering Layers:

• closest_bodies_to_point(...)->Array[...] closest N bodies to point P (used all the time in AI and game logic)
• closest_bodies_to_ray(...)->Array[...] closest N bodies to Ray R (once you have used this in object picking code, you will never want to use pure ray-bodyintersection picking again - the UX is just so much better for the player)
• intersect_halfspace(...)->Array[...] all bodies above plane defined by point and normal P,n (very useful for broad rejections) - this might be done with a WorldBoundaryShape2D/3D, but I have been repeatedly able to push items through a world boundary for whatever reason, so it appears to be incorrectly implemented. It is also noteworthy that while this type of collider is a godsent, most established physics solutions don't have it. (but the spatial query is independent from this)

Already provided by intersect_shape(...), but the API is very clunky:

• all bodies in sphere/circle around point and with radius P,r (used all the time in games, already provided)
• all bodies in AABB A (ditto)

Complex, but nice to have:

• closest_points_and_bodies(...)->Array[...] closest N points on any mask/layer matching body to shape S (very useful for terrain following and collision avoidance)

The first 2 are particularly useful, and would feel in line with Godot's very game-centric architecture, as they are distilled down to a very common use case.

[donn-xx]

As long as the queries can also take Transforms and run them against a custom array of other Transforms or points.

What I require, for example, is to know which Transforms in a multimesh are nearest to my player. It makes sense to have some way to tell this hypothetical query to:

1. Take multiple arrays/whatever from multimesh resources or,
2. Take multiple arrays of custom objects, points, transforms etc.
3. Then let us query against that virtual space.

[donn-xx]

Since this thread and others I have started using the cull methods as described here: class-renderingserver-method-instances-cull-convex

The problem is much clearer to me now

In order to test an AABB against a MultiMeshInstance3D, I must:

1. Step through each transform in the Multimesh array.
2. Calculate the AABB of that sub-mesh
3. Create a MeshInstance3D node and place a mesh within.
4. Add that to the scene
5. Only then, when potentially thousands of cubes are now drawn on the screen, can I deploy the cull_aabb method to seek intersections.

This seems wasteful and slow.

Would not a method something like this be better?

instances_cull_aabb_array (aabb_source, aabb_target, transform_array, scenario) This would do all those steps but not actually bother to draw the aabb cubes. It would create a temporary BVH and populate it and then do the work. All in C++ and not slow gdscript.

var me = $player
var player_aabb = me.mesh.get_aabb()
var mmesh = $field.multimesh
var mmesh_aabb = mmesh.get_aabb()
var sc = self.get_world3d().scenarrio

var hits = RenderingServer.instances_cull_aabb_array(player_aabb, mmesh_aabb, mmesh.transform_array, sc)

if hits:
  explodyboom()

Naturally for rays and convex too, as well as the 3D equivalents.

[shuvit-game]

Godot would absolutely benefit from a tree search that can return x nearest points or all points within y range. Blender's kdtree is exactly what I'm used to and looking for. My personal use cases are mostly for points, so AABB and mesh stuff should be separate, imo, and needs there are beyond my understanding.

The astar algorithm can already return closest point, this just needs to be expanded and exposed to include searches for x nearest or within y distance, I assume. It feels like 95% of it is there already.

I have not been successful in my attempts at doing this in gdscript for personal utilities. Seeing this implemented as a native search would be a huge relief.

[uzkbwza]

I am also running into issues with this because GDScript is just too slow for a quadtree or spatial hash grid with lots of elements.