godotengine
Add a method to get points of intersection between camera frustum and a plane
Closes godotengine/godot-proposals#6015
Implements Camera3D::get_frustum_plane_intersection() that returns the points of intersection between camera frustum and a plane. The function can be used to find an approximation of an area the camera sees (RTS games for example). The points are returned in a clockwise order*[^1] from cameras perspective in global coordinates.
This could arguably also belong to either Geometry3D or Projection but Camera3D was chosen due discoverability and maintainability (feel free to disagree).
I also reordered the order of endpoints in Projection.get_endpoints() to make it easier to iterate them and match the Projection.get_frustum() (near before far, sides in clockwise order). The function isn't exposed and the order was only relevant for Camera3D.get_pyramid_shape_rid(), so this won't affect end-user.
Also seemingly the projection differs for XR so I tried to take that into account but cannot ensure it works as intended.
@Chaosus Anything to add/change? [^1]: If the plane intersects both near- and far-plane this might not be the case; This could be taken into account but since intersecting both is rare (within the use-cases described in the proposal) and there's a likelihood the result is reordered anyway, it is better to keep the function simple.
@Chaosus Anything to add/change?
Nothing, I think it's fine in its state. Thanks for implementing this!
@Lielay9 Seems like you overrode the commit name - please make it meaningful (like Add a function Camera3D::get_frustum_plane_intersection()).
I'm now using this patch in a project of mine and it's working great. Thank you! Thumbs-up for it being merged into the core engine.
@Lielay9 Sorry if I wrongly thought that you abandoned this PR, if you will to continue I will close mine and reopen this.
@Chaosus I don't have much time during the week, so I've only worked on this on the weekends. I apologize, I wasn't aware that there was a hurry. You can best contact me by commenting or pinging me as those will give me a notification.
I hadn't taken a look at the pr since first authoring it but knew that it was at the very least outdated. After the first weekend and basic testing I realized it's not only that but also fundamentally flawed. Hence I converted it to a draft.
From the perspective of the proposal the problems of this pr are multipronged. In short, it is slower and just as complicated and error prone as copying the implementation from a tutorial you needed regardless. In long:
Doing an intersection between a plane and the edges of a hexahedron isn't quite as simple as this pr makes it out to be. Firstly this approach may over-count the intersections if the plane aligns with a corner, edge or a side. Secondly:
The points are returned in a clockwise order*
That asterisk is doing a lot of work trying to hide in just how many cases that is not true. In fact, most intersection don't follow that rule. Furthermore, ordering the points from the cameras perspective is nonsensical as they'll never be used from that perspective. Instead, they should be ordered clockwise on the plane (rotation direction based on the normal). That way the result can be used for a valid polygon.
Both problems are fixable either by running a convex-hull algorithm (same as sorting if corners are explicitly handled) or by solving the orientation from a binary decision diagram of the intersections. At that point though the function might as well be made generic for all convex shapes; similar to Geometry3D.compute_convex_mesh_points(). That would also allow easier testing.
All that said that's mostly irrelevant, since it is not solving the problems of complexity and error-handling the proposal had. For a RTS camera, you're only interested in the intersection result of the side-planes of the camera-frustum and a flat plane. Anything else is an error in practice, but the function will spit out a valid intersection regardless of your intentions. Trying to separate the valid results from invalid ones is impractical, since it leads to doing more "manual" work than just calculating the needed intersections yourself. In fact, even if one were omit all the laborious checks, they wouldn't save a single line of code.
As a fun challenge I encourage giving writing an implementation a try. There's a reference implementation in the spoiler, which may or may not work (written for this version of pr).
Reference implementation:
var frustum: Array[Plane] = get_frustum() # Cache frustum; expensive to fetch.
var points3D: PackedVector3Array = get_frustum_plane_intersection(Plane.PLANE_XZ)
var points2D: PackedVector2Array = []
for point3D: Vector3 in points3D:
# Check to not append if the point3D is on the near or the far plane.
if not frustum[0].has_point(p3) and not frustum[1].has_point(p3):
points2D.append(Vector2(point3D.x, point3D.z))
# Convex hull will organize the points for creating a polygon, except if we are using XR-camera, then idk.
points2D = Geometry2D.convex_hull(points2D)
# There might've not been 4 intersections, but since we need convex_hull to get rid of duplicates (in case
# the plane intersected a corner, which sometimes is valid) we can only check for it now.
if points2D.size() == 4 + 1: # +1 Because the convex_hull() adds a point to the end.
# You're ready to construct the polygon; remember to remove last point if not needed.
I'm quite convinced it won't be as fun for a someone who was struggling to create a rts camera and told to just use get_frustum_plane_intersection() which unfortunately still requires understanding what a frustum is and how it needs to intersect the plane.
More so this might not even be the correct approah at all. I was mistaken in the comments of the proposal. Starcraft 2 doesn't use a frustum plane intersection in their minimap-camera-quadrilateral. In the game, there are multiple height levels and the quadrilateral reflects that:
Screen capture from this video: https://www.youtube.com/watch?v=Qp1wr-ds3-o
It more likely uses raycasts for the camera corners on their own collision layer... or something similar.
I omitted quite many details (such as XR) and small nitpicks, but that's the gist of it. Had this pr not been closed, I probably would've suggested doing so come weekend. In it's place I suggest adding an example project that shows how one would create RTS minimap, quadrilateral included, in a couple different ways. The project can go much more in depth, for example actually include the latter part where the quadrilateral is created, than a vaguely related function description can.
As I said I'm quite busy so I can't dedicate much time for a pr/example project, I hope you understand. In that vein feel free to continue the work in the way you find best suitable.
I wasn't aware that there was a hurry
That was my bad, nothing was cost a real hurry, it's just mine impatience (at least it is targeted to 4.4 which is a long way time ahead). I've checked your activity on GitHub and wrongly thought you've abandoned the PR.
So I've just copy-paste your PR to https://github.com/godotengine/godot/pull/91702 and apply the fixes suggested by @AThousandShips and me.
And now I realize how complex the original proposal is and began to think that I cannot handle it to the finish... At least finding the intersection with a simple plane is working since I've tested it myself, and finding the intersection with a complex geometry with different heights (like in Starcraft2) may be a subject for another proposal/PR.
If you feel to accomplish this completely, you can create an another PR without problem...