Allow convex collision shape creation from array of planes

[jitspoe]

Describe the project you are working on

Retro FPS game.

Describe the problem or limitation you are having in your project

I'm working on creating a Quake BSP importer for building levels. The collision is all stored as planes in a BSP tree. I can gather the planes necessary to create a convex shape, however there is no means to go from an array of planes to a ConvexPolygonShape3D. The ConvexPolygonShape3D requires an array of points.

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

This feature would allow an easy method to go from an array of planes to a convex collision shape. Interestingly, there are some helper functions in Geometry3D that build arrays of planes for manual collision tests. Would be useful to, at the very least have some functions to go back and forth between an array of planes and an array of points as well as maybe allow ConvexPolygonShape3D to be passed an array of planes.

Being able to create collision from planes would make it much easier to create optimal collision from various level formats and also make it more consistent with the helper functions that already exist. Being able to pull the planes from convex collision could also be useful for custom physics solutions. It might even make more sense to store the collision data as planes, depending on how the collision algorithm works.

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

Option 1:

var points = Geometry3D.convex_planes_to_points(planes_array)
collision_shape.shape = ConvexPolygonShape3D.new()
collision_shape.shape.points = points

Option 2:

collision_shape.shape = ConvexPolygonShape3D.new()
collision_shape.shape.planes = planes_array

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

Trying to calculate this in script is not exactly idea for performance reasons.

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

Seems like a small addition that would be good to have for consistency's sake.

[MewPurPur]

The ConvexPolygonShape3D requires an array of points.

Does this trust you to give it points in a convex hull? I don't think we have an exposed implementation of the 3D convex hull algorithm.

[jitspoe]

Does this trust you to give it points in a convex hull? I don't think we have an exposed implementation of the 3D convex hull algorithm.

I believe you can have any arbitrary points and it will create a convex shape out of them. If points are inside of the hull (ex: convex shape), they will just be ignored, though it may not be optimal.

[MewPurPur]

I checked it out, this isn't really a 3D hull, it's a 3D prism with its bases being convex polygons.

[jitspoe]

Seems there's a function compute_convex_mesh_points() already in Geometry3D, but it's not exposed to GDScript. Could simply expose that.

[gongpha]

Just realized there are other people who want this feature too.

I don't think the array of planes that will clip the 3d area (to half spaces) is always done as a convex shape. Because they may leave some infinite side. Imagine intersecting only planes on the side to be a prism without 2 planes in the front and back. Or, in the case that all the planes have a normal vector pointing to the inside. That will make anything outside the convex collided. (The interior maps have the planes like this) But this can be solved by specifying a bound to limit the infinite sides.

I also rather suggest having a new collision shape to handle these directly. For Example, ClippingPlanesShape3D, only needs an array of planes to determine either a front-side or back-side of the convex that consider to be collided. Or BSPTreeShape3D, needs literally a BSP tree. May do the same as a BSP tree in lightmap data do. But I'm really not sure if this will implement easily in the physics engine . . .

Btw, I've implemented a workaround for getting convex points from a Quake BSP file in my pending PR, gongpha/gdQmapbsp#20. ( 100% GDScript, extremely hardcoded for performance U//<" )

[jitspoe]

Haha, you're making a BSP importer as well? Here's what I've got, just using triangle collision: https://github.com/jitspoe/godot_bsp_importer

By the way, the way you work around the infinite planes is to create planes for the bounds of the map, so there's effectively a giant box that catches any unbounded collision planes and always generates closed shapes. You can take a look at the ericw decompiler tool to see how that's done in practice: https://github.com/ericwa/ericw-tools/blob/brushbsp/common/decompile.cc

Also, I think the clip nodes are to give a rough estimate for collision before doing more detailed stuff, as an optimization, so it's not super precise.

[gongpha]

Well, I can't say my plugin is a BSP importer entirely because it uses benefits from both MAP and BSP files. A BSP file gave map meshes and entity data. And a MAP file gave brush data for making collision shapes. ( I've also planned to try to remake Quake 1 in Godot. Currently having troubles with QuakeC -. - )

Also, I agree that the clip nodes are not precise for checking an accurate collision like gunshot impacts or rigid bodies. So the BSP tree would be used. But the downside is it's not included clip brushes.

So, I'm curious if you choose to use the BSP tree for collision, What do you think about the clip brushes that aren't being included in the BSP tree ?

[jitspoe]

Going to respond here: gongpha/gdQmapbsp#20 as this is getting a little off topic.