Add ShapeCast3D node for collision sweep and immediate overlap queries (already implemented in 2D)

[Xrayez]

See the 3D version of this proposal at #2896.
Aims to supercede #72, #709.
Helps #740, #2577.

Describe the project you are working on:

Goost - Godot Engine extension

Describe the problem or limitation you are having in your project:

Ray casting is not as flexible or robust when it comes to detecting collision bodies along the ray cast area/volume (can easily miss objects, for example beam weapons which has a notion of width of a beam, which raycast doesn't have). For that one needs to cast multiple ray cast in the same direction, which is a hacky thing to do.

It's also difficult to get collision overlaps with Area2D/3D and often requires waiting a couple of frames before collision information is available to these nodes, when immediate information is preferable. One can use signals for that, but that mostly leads to inconveniences because you have to ensure that no duplicate bodies is detected within the signal callback, and you need to collect a list of overlapped bodies manually. Using the low-level direct space state API is the only way to fetch immediate overlap information which is robust (with or without shape sweep test), but again it's quite cumbersome to use for most users.

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

Creating ShapeCast2D and ShapeCast3D analogously to RayCast2D and RayCast3D nodes. Ability to assign any existing Shape2D or Shape3D is enough for this to overcome limitations of ray casting.

Describe how your proposal will work, with code, pseudocode, mockups, and/or diagrams:

I've managed to implement this via C++ modules in Goost, and replaced some GDScript classes already with it in my own projects.

Editor view

Inspector

API

The implementation is based on RayCast2D (copy-pasted and adapted), uses PhysicsDirectSpaceState.cast_motion along with PhysicsDirectSpaceState.get_rest_info internally, so in most cases it reflects RayCast2D API, with the following differences:

• obviously you need to assign any Shape2D resource before using. For 2D, CircleShape2D can be possibly instantiated by default.
• ability to configure collision margin for shapes.
• casting can work with cast_to == Vector2(). In this case, such node can be used as a general-purpose, (continuous) collision detection area which can overcome limitations of Area2D. Immediate information can be forced with force_shapecast_update. Quite similar to PhysX Overlaps. Can also help workaround CCD issues: Continuous CD not working godot#9071.
• can return multiple results (the number of results is limited by max_results property for performance reasons). get_closest_* methods should be used instead if you come from RayCast2D. See also PhysX closest hit.
• exposed collision_result as a property so that if there's a need to fetch more collision information not provided by the API by default (collider's linear_velocity, metadata etc).
• get_closest_collision_safe/unsafe_distance used for querying the intersections exactly outside/inside collision. You can move the shapecast along safe distance to repeat the process from that point without the node being stuck inside the collider, for instance.
• the ShapeCast node's own transform can be modified to alter the shape in any way by translating, rotating and scaling.

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

Cannot be worked around with a few lines of script.

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

There's no particular reason why this should be part of the core. This can be implemented via plugin/module. Performance is the only reason why this might be needed for core. Some engines like Unity already provide similar functionality though, also the mentioned PhysX library.

In fact, given the same logic, the existing RayCast nodes can also be re-implemented via script.

If you think it's worth adding an entire ShapeCast2D/3D to Godot core and you feel like the described implementation is logical/fits the requirements, I can make a PR, but additional work is needed to port this to 3D.

[notverymoe]

This is definitely a feature I've missed in Godot when migrating from other engines. I'm happy to lend my hand if/where/when it's wanted.

My use-case for this feature is primarily for the implementation of reactive character controllers, which requires scanning the environment to identify features, and then using the contact information to react to the feature. This requires management of multiple shape objects and the use of cast_motion and get_rest_info methods together in a non-intuitive manner, with unclear guarantees.

I wanted to suggest that the exclude api of the Raycasting nodes should be matched too (add_exception, add_exception_rid, remove_exception etc.), unless it's inclusion was already implied.

Might not be worth talking about yet, but I think that a dedicated path (ie. intersect_motion) in the direct space state classes may be also worth looking at? There seems to be a lot of repeated work done between both cast_motion and rest_info, and in repeated calls to them to discover up to 'x' collisions along a path. Edit2: Misunderstanding on my part, only casting to the first hit along the path solves a lot of my concerns. Edit1: Additionally it'll provide clear and strong-guarantees on results. I also haven't delved that deep into godot's physics implementation yet, so, I'm not sure what the cost/benefit actually is on that.

[Xrayez]

I wanted to suggest that the exclude api of the Raycasting nodes should be matched too (add_exception, add_exception_rid, remove_exception etc.), unless it's inclusion was already implied.

Yeah it's just not visible on the screenshot.

Might not be worth talking about yet, but I think that a dedicated path (ie. intersect_motion) in the direct space state classes may be also worth looking at?

Yeah with the current implementation I take the all bodies and do the intersections by excluding them one-by-one. This is also related to godotengine/godot#25695 I guess.

[Xrayez]

I've created a PhysicsTools module Goost containing the ShapeCast2D implementation for people to check out. As you see it's perfectly possible to maintain this outside of Godot. Of course if the proposal is approved, I could likely implement this already (2D only...). I'm not sure whether the implementation could also be backported to Godot 3.2, so the module will always be available there to support it.

[esd-o]

Shapecasting is the only way I know of to create collision-perfect shape projectiles, especially if they interact differently with different kinds of objects. If you try to scan the projectiles' path with a intersect_shape, it's impossible to know what thing was hit first. If you just leave it to areas, the collision detection is very laggy in motions above 300 (my testing is done @ 60fps), causing ghosting. Using normal physics can also lead to problems, because if you need the bullet to penetrate something, you'll need to use something else (like areas).

What i've been doing is doing a cast_motion to see when the collision occurs. Since this method won't tell me what the shape is colliding with I then need to do a intersect_shape to check that. Once the collision is processed, the colliding body is added to exception list, and the cast motion is done again. This repeats til there are no collisions reported in cast_motion. So it's way more complicated than it needs to be, and it just looks clunky but its what I've been able to pull off.

tldr Adding shapecasting would be dope, its very useful.

[golddotasksquestions]

Is there a reason why this should be core and not an add-on in the asset library?:
There's no particular reason why this should be part of the core.

I'm aware the direction we are heading is to take as much as possible out of the core to make the core lenient and accessible as possible (which is great) and have all the additional functionality as modules/plugins, but I'm always confused whether this means a particular feature we are discussing will only be available through additional download, or if it comes build into the official binaries.

This here, imho, should be a feature that comes with the official binaries as it would be used very often and is very much needed in a wide range of genres and usecases.

[Xrayez]

Well I'm not sure about this either. There seems to be no clear criteria for what goes into core/first-party. This is why I've raised #575 because I really see no boundaries for Godot development due to the absence of well-defined feature scope for Godot. reduz says it's based on pragmatism and practical use cases, but then even under those requirements Godot will likely bloat in the future.

Due to this, it's likely that the development may shift towards first-party plugins/modules, like with https://github.com/godotengine/godot-git-plugin, yet Godot will have to first solve the many usability issues with GDNative and whatnot.

On topic, I've said it's possible to implement this feature via script, but because I also think that this feature is quite important to physics, I've decided to implement it in C++ so this can have higher chances to get approved and eventually merged almost without hassle in Godot. At the very least, people stumbling upon this proposal will figure out that there are already available solutions to this problem, the only difference is that they're not necessarily solved by Godot core developers (like 20 people there who really decide what goes into the engine).

[eon-s]

Well, I would like this in core because it is just an extension of RayCast usability, and can use all the optimizations of being in core.
On #2896 I was thinking more of directly replacing RayCast node and let the user pick a shape type (we can default to ray but give more options).

[yosoyfreeman]

I think all tracing related stuff should be core as is one of the base elements of an engine.

[Xrayez]

I was thinking more of directly replacing RayCast node and let the user pick a shape type (we can default to ray but give more options).

See my opinion on this in #2577 (comment).

Even though it's possible to use a ray shape for casting, it would still be treated as a shape (imagine casting ray shape sidewise instead of along the line), which is less performant than pure ray casting.

Shape casts also have a notion of safe/unsafe distance when computing collisions (moving the shape along the unsafe distance means that colliders will intersect), at least that's what I've noticed in Godot's internal API.

However, combining both ray casting and shape casting into a single class is possible in any case, but then it would likely make the API not so clear.

I'm talking from the standpoint of someone who uses the Godot's physics API, I don't exclude the possibility that the physics backends could be consolidated this way, but this is likely a lot more work to do.

[Wolfe2x7]

It's about time I stumbled upon this proposal.

I think it's worth mentioning that I have been taking advantage of built-in shapecasting for my project...using the SpringArm node. It isn't a complete solution because it does not provide all the information that a RayCast node can (and it's 3D only), but it's an existing solution and I think it's a shame that it does not get more recognition outside of being used for a camera.

The SpringArm node can already suit a number of use cases for 3D shapecasting. In my case, I am using it for a RayCast-style vehicle model with a round SphereShape, making for smoother and more realistic wheel-surface interaction (someone else's example) while being simpler (and more efficient?) than firing a whole series of rays.

A more complete ShapeCast node that provides the information I currently have to collect from a complementary RayCast node would be great. :)

[fire]

I asked @pouleyKetchoupp, the physics maintainer, and he said the proposal to support a direct shape cast node in the engine makes sense. The only thing he's not too sure about how to draw it without possible confusion with actual shapes.

[eon-s]

Can be done by drawing the arrow for direction and outlines for the shapes (dotted lines on 3D), maybe the debug draw can be configurable to draw X amount of shapes distributed evenly, with a default of 3 (start, middle/contact, end/contact).

[Xrayez]

I think outline could be computed via Geometry2D::convex hull(points) of individual shape vertices to draw. The arrow is already drawn on the screenshot as seen this proposal in 2D, the amount of shapes being drawn is heuristically computed as well.

[pouleyKetchoupp]

I think outline could be computed via Geometry2D::convex hull(points) of individual shape vertices to draw.

Ah yes, if it can be cached to avoid slowing things down too much, building a convex hull to display the whole path would work well.

[pouleyKetchoupp]

@eon-s I'm not sure about the dotted lines in 3D, might be too much specific code to write. But maybe transparent shapes with a specific color would be ok.

[eon-s]

I was thinking on some magical thing like the old gl stipple, but thin/semitransparent shapes will be fine, most people will turn these on in the editor just to see if are pointing correctly, then off again, I guess.

[djrain]

Status on this? Seems like the bulk of the work is done for 2D, would be great to see this make it into core soon.

[fire]

As far as I know adding a ShapeCast node is still un-claimed meaning anyone can work on it.

[Xrayez]

While anyone can work on this, I don't quite see an explicit approval for implementing this proposal.

I could work on porting ShapeCast2D to Godot 4.0 I guess, but I need to be sure that this proposal is actually approved (in a way which represents consensus). This is the reason why we have GIP, as far as I know, so we don't waste time implementing something that may be rejected.

And I think there are still some design issues with ShapeCast3D node to be discussed.

But at the same time, I'm fine if pouleyKetchoupp would like to implement both ShapeCast2D and ShapeCast3D.

[djrain]

@Xrayez do you happen to have a GDScript version of ShapeCast2D? I'm looking at the Goost implementation and I don't quite understand how the process_intersections loop works.

[pouleyKetchoupp]

@Xrayez You can consider the proposal approved. Feel free to start with adding the 2D version to core if you want. For 3D it's also approved on principle but it will need a bit more testing to decide how to render the shape.

[Xrayez]

@djrain I have no GDScript code for this, because I went straight on implementing it in C++, since RayCast2D was already there, so API is based on it.

I don't recall exact reason for current logic, but I think it had something to do with how cast_motion() worked... 😮

[djrain]

I don't recall exact reason for current logic, but I think it had something to do with how cast_motion() worked... 😮

hmm, I thought you'd need to call cast_motion() repeatedly to get the next safe distance to move... in any event, since it's not obvious it might be worth adding a few explanatory comments 😄

[Xrayez]

I don't recall exact reason for current logic, but I think it had something to do with how cast_motion() worked... 😮

hmm, I thought you'd need to call cast_motion() repeatedly to get the next safe distance to move... in any event, since it's not obvious it might be worth adding a few explanatory comments 😄

Yes, I think that logic was due to me testing moving the shape cast along safe/unsafe distance via C++ during development... I think it's not needed, godotengine/godot#54803 has simplified code now, seems to work fine.

[djrain]

So the cast_motion() is only for getting the safe/unsafe distance? In terms of the intersections, I don't understand how the loop "steps" along the cast. Does rest_info() somehow update the transform?

[Xrayez]

So the cast_motion() is only for getting the safe/unsafe distance? In terms of the intersections, I don't understand how the loop "steps" along the cast. Does rest_info() somehow update the transform?

This appears to be an implementation detail in Godot's physics. Both cast_motion() and rest_info() take into account relative motion, and shapes are transformed in discrete steps by interpolating with motion, in such a way so that the collision result converges to expected collision.

I'd say cast_motion() is used for "boolean" results (as seen in C++, along with safe/unsafe distance), while rest_info() provides complete information (similarly to boolean collision results which are more efficient to compute, and getting complete contact manifold, for instance).

I think the rest_info() is not particularly intuitive name in the first place.

[djrain]

Both cast_motion() and rest_info() take into account relative motion, and shapes are transformed in discrete steps by interpolating with motion, in such a way so that the collision result converges to expected collision.

So the documentation note about get_rest_info() is wrong?

"Note: This method does not take into account the motion property of the object"
https://docs.godotengine.org/en/stable/classes/class_physics2ddirectspacestate.html#class-physics2ddirectspacestate-method-get-rest-info

I've tested this in GDScript and the motion property does in fact affect the result. 🧐

[pouleyKetchoupp]

@djrain Yes, the documentation for get_rest_info() is wrong indeed, the motion is taken into account.

I've made a fix for intersect_shape() in godotengine/godot#54607 but I missed that, I'll make a separate fix for the doc of get_rest_info().

[djrain]

I'm not sure about the transform of the ShapeCast2D affecting both the shape and the "ray". These are two separate concepts, the shape and where I want to cast it. What if I want to use a scaled, rotated shape but keep the cast direction and length the same?

[pouleyKetchoupp]

I'm not sure about the transform of the ShapeCast2D affecting both the shape and the "ray". These are two separate concepts, the shape and where I want to cast it. What if I want to use a scaled, rotated shape but keep the cast direction and length the same?

It probably makes sense for the ShapeCast2D transform to affect both, so that if you rotate the direction around, the shape rotates too and you cast it facing the same way (if it's a cube or polygon).
Although it does sound like a good idea to add an extra shape transform so you can rotate or scale the shape without affecting the cast direction itself.

[Xrayez]

I've been thinking what to reply, and yes, I think shape transform could be added to achieve what @djrain describes, so there's actually three separate concepts: node transform, shape transform, and direction. But that's probably something that requires physics backend changes, what I propose with godotengine/godot#54803 is just a frontend for something which is already there in Godot.

[Xrayez]

godotengine/godot#54803 is now merged!

---

I think outline could be computed via Geometry2D::convex hull(points) of individual shape vertices to draw.

Ah yes, if it can be cached to avoid slowing things down too much, building a convex hull to display the whole path would work well.

What if drawing could be done with motion parameter in base Shape2D class?

Current:

virtual void draw(const RID &p_to_rid, const Color &p_color) override;

Proposed:

virtual void draw(const RID &p_to_rid, const Vector2 &p_motion,  const Color &p_color) override;

We'd then add Shape2D::get_motion_hull(points) and call it after point generation for each shape if motion != Vector2(). Note that some classes are not that easy to generalize (like SeparationRayShape2D), because some shapes' visual representation is not always equal to actual collision geometry.

[elvisish]

Is shapecasting basicly implemented yet or is it planned to be backported for 3.5?

[Xrayez]

Is shapecasting basicly implemented yet or is it planned to be backported for 3.5?

It's implemented in 4.0, but it's not backported to 3.5. If Godot maintainers are fine with backporting this feature to 3.5, I can do this, but I need an explicit approval in order to do this.

Note that current implementation merged in Godot 4.0 is in alignment with the implementation you see in Goost, currently available in Goost 1.1.

[elvisish]

Is shapecasting basicly implemented yet or is it planned to be backported for 3.5?

It's implemented in 4.0, but it's not backported to 3.5. If Godot maintainers are fine with backporting this feature to 3.5, I can do this, but I need an explicit approval in order to do this.

Note that current implementation merged in Godot 4.0 is in alignment with the implementation you see in Goost, currently available in Goost 1.1.

Ah I should probably ask if this would be available for 3D, or is it just 2D right now?

[Xrayez]

Ah I should probably ask if this would be available for 3D, or is it just 2D right now?

I think @pouleyKetchoupp plans to work on implementing the same feature in 3D. I don't specialize in 3D unfortunately. The lack of 3D counterpart may also be the blocking reason for not backporting ShapeCast2D to 3.5, because mostly features are either implemented for both 2D and 3D, or not at all.

But the implementation will likely diverge in 4.0, therefore I think it's very unlikely for ShapeCast2D to be backported to 3.5, since ShapeCast3D would also need to be implemented.

[fire]

@Xrayez Can you help me sketch a design?

What variables and methods do you imagine is needed?

[Xrayez]

What variables and methods do you imagine is needed?

Not sure what you mean. ShapeCast3D should be mostly similar to already merged godotengine/godot#54803 ShapeCast2D.

[akien-mga]

Implemented by godotengine/godot#63161.