Add `Shape2D::collide_and_get_intersections()`

Describe the project you are working on

Action platformer that makes ample use of hit box collision. Need to know how exactly hit boxes and hurt boxes collide for various scenarios such as adding hit effects at the correct position. The hit/hurt boxes are Area2D nodes, and the shapes inside the hit/hurt boxes can be any Shape2D sub-class.

Describe the problem or limitation you are having in your project

I was expecting Shape2D::collide_and_get_contacts() to give me the yellow dots in this picture. Apparently it does not, and isn't designed to do so.

There doesn't appear to be a built-in method for obtaining all intersection points between two arbitrary Shape2D.

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

Add a new method Shape2D::collide_and_get_intersections() that takes the same arguments as Shape2D::collide_and_get_contacts(), but returns all intersection points instead.

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

This is basic intersection detection. Many methods in the Geometry class help with this, but for a general use case there's a lot of work to be done for detecting intersections between any two arbitrary Shape2D.

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

No, this is a prohibitively long solution due to all of the different types of shapes that can interact. A simplified, inefficient solution such as converting all shapes to a common format first (like PoolVector2Array of segments), then detecting intersections based on segments may be sufficient for many games where Shape2D::collide_and_get_intersections() is only used once on a contact frame, but even this simplified solution couldn't support Line2D without some sort of hack like just making the segment extremely long.

A limited example:

static func convert_shape_to_segment_array(shape: Shape2D):
    var segments = []
    if shape is ConcavePolygonShape2D:
        segments = shape.segments
    elif shape is ConvexPolygonShape2D:
        for i in shape.points.size():
            if i == 0:
                segments.push_back(shape.points[shape.points.size() - 1])
                segments.push_back(shape.points[i])
            else:
                segments.push_back(shape.points[i - 1])
                segments.push_back(shape.points[i])
    elif shape is RectangleShape2D:
        segments = [
            Vector2(-shape.extents.x, -shape.extents.y),
            Vector2(shape.extents.x, -shape.extents.y),
            Vector2(shape.extents.x, -shape.extents.y),
            Vector2(shape.extents.x, shape.extents.y),
            Vector2(shape.extents.x, shape.extents.y),
            Vector2(-shape.extents.x, shape.extents.y),
            Vector2(-shape.extents.x, shape.extents.y),
            Vector2(-shape.extents.x, -shape.extents.y)
        ]
    elif shape is SegmentShape2D:
        segments = [
            shape.a,
            shape.b
        ]
    return PoolVector2Array(segments)

static func collide_and_get_intersections(shape1: Shape2D, shape1_transform: Transform2D, shape2: Shape2D, shape2_transform: Transform2D):
    var intersections = []
    var shape1_segments = shape1_transform.xform(convert_shape_to_segment_array(shape1))
    var shape2_segments = shape2_transform.xform(convert_shape_to_segment_array(shape2))
    for i in range(0, shape1_segments.size(), 2):
        var segment1_from = shape1_segments[i]
        var segment1_to = shape1_segments[i + 1]

        for j in range(0, shape2_segments.size(), 2):
            var segment2_from = shape2_segments[j]
            var segment2_to = shape2_segments[j + 1]

            var intersection = Geometry.segment_intersects_segment_2d(segment1_from, segment1_to, segment2_from, segment2_to)
            if intersection != null:
                intersections.push_back(intersection)

    return intersections

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

I don't see why the engine that already detects shape intersection internally wouldn't be able to expose this functionality.

It appears to me that Shape2D API is geared more towards physics use cases. The way how Shape2D::collide_and_get_contacts() works might be related to SAT algorithm used by Godot's collision detection (for solving interpenetration constraints). In general, this is a collision detection problem more than a physics problem, and that's a field in and of itself.

That said, perhaps this is something to be exposed/implemented via Goost in GoostGeometry2D class. As a workaround, the singleton provides an ability to generate some polygon primitives such as rectangle(), circle() and capsule(), so segment vs. segment intersections could be approximated this way already via script.

Of course, it would be much more efficient to have dedicated function for each type of shape intersection. For instance, see the table at Object/Object intersection page (both static and dynamic intersections). To note, dynamic intersections (with motion) are not easy to generalize according to my research, but this is probably something that will be considered too corner case to be exposed in Godot anyways.

It appears to me that Shape2D API is geared more towards physics use cases.

Nevertheless, everyone creates either Shape or Shape2D objects in editor. I don't think there's a more fitting place to add this method right now. Geometry class is more low level.

It appears to me that Shape2D API is geared more towards physics use cases.

Nevertheless, everyone creates either Shape or Shape2D objects in editor. I don't think there's a more fitting place to add this method right now. Geometry class is more low level.

I agree, I think there's no need to introduce potential cyclic dependency between Geometry singleton and Shape classes. I'm saying that the scope largely depends on what kind of use cases Godot chooses to solve in core, because a lot of features in Godot are implemented pragmatically, due to this some features may be missing even if they're already there in Godot core somewhere...

But something tells me that Godot does not have those routines implemented due to SAT algorithm I mentioned. So it's a question of whether Godot would be willing to implement and maintain those new collision detection methods in core.

Hopefully @pouleyKetchoupp could work on this!

I'm actually fairly interested in this subject myself, that's why I created GoostGeometry2D singleton in https://github.com/goostengine/goost (which provides methods that might never be implemented in Godot, as those might be considered specific). But that's ok, because not everything should be implemented in core. Nonetheless, this is something which could make current API more complete.

In my view, Shape2D is the most basic shape class, and thus would be a good class to use for the detection of intersections. There is already a CollisionShape2D node which is more specific purpose, and from its name, Shape2D seems like a very basic shape class. If it is really intended just for physics calculations, then it should be named as such (like CollisionShape2D is). I thought the collide_* functions were simply included in the Shape2D class mostly for convenience, rather than having them in a separate physics-specific singleton.

I think it would be good to either add an interdect_with(Shape2D) function to Shape2D, or perhaps a Geometry.intersect_shapes(Shape2D, Shape2D) method, to keep all geometry functions together. These would need to include transforms for the shapes too.

Alternatively, perhaps we could have a GeometryShape2D class similar to CollisionShape2D, which would contain the transform and Shape2D, and provide an intersect_with(GeometryShape2D) function.

This definitely needs more discussion, but I like the idea of having a GeometryShape2D class. Perhaps I should create a separate request for adding that specifically?

godotengine / godot-proposals