Add support for defining holes in polygons

[theromis]

Describe the project you are working on

Working on infinite scrolling game and it need enemies chasing main hero.

Describe the problem or limitation you are having in your project

For purpose of enemies following hero I need updating navigation mesh but baking creates a FPS drop. Another option is just generate Navigation mesh manually but 2d polygon should have a holes, I can't find any method to make a runtime holes in polygon other than manually generate squares and fill a navigation mesh with them.

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

goostengine/goost#42
Is it possible to have ability define a hole in the polygon and triangulate it?

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

Just should give a triangulated polygon with holes.

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

It can be generated manually, but it painful.

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

Seems like goostengine have this option but last commit there is 2 yars ago.

[theromis]

I think it related to godotengine/godot#41447

[theromis]

looking on https://www.cs.cmu.edu/~quake/triangle.demo.html from https://github.com/libigl/triangle
I think it might be useful for this purpose

[Calinou]

looking on cs.cmu.edu/~quake/triangle.demo.html from libigl/triangle I think it might be useful for this purpose

We already have Delaunay triangulation support in Godot. Also, the code you linked isn't under an open source license as its license forbids commercial use.

[theromis]

Agreed, don't have other suggestions :( In the example(https://www.cs.cmu.edu/~quake/triangle.defs.html#pslg) they had an symbol "A" example called PSLG which have a hole, Thought this is what godot needed for "holed polygons"

[smix8]

The navigation mesh baking can already do all that. If it is too slow it is a matter of not feeding too much source geometry data to the baking process.

Recent prs like godotengine/godot#87961 help with baking chunk navigation meshes to partion too large game worlds that can not be updated in one piece at runtime without frame drops.

Most of the time it is not really the baking responsible for the frame drop but a too large navigation map or scenetree that requires too much time to be parsed or synced with the update. Or too many agents that all burst forward requesting a path update on a map change at the same time. Creating a navigation mesh manually would do nothing for those performance problems.

A polygon with hole does not exist. Anything with a hole are always 2+ polygons arranged around empty space. The Polygon2D already has the polygons array property for that but it is not made functional. There is no real reason to not add it because with Godot 4 the Polygon2D already started to use a real internal mesh. You can add as many polygons as you want on a real mesh. It is just a matter of updating the Polygon2D API to allow to add multiple polygons to that mesh. I think the biggest roadblock for that is the awkward 2D skeleton and bone API that needs the most update to make this functional.

[theromis]

thank you for good recommendations

my game is 2.5d technically it has a 2d logic but represented in 3d space so NavigationPolygon won't work, it needs NavigationMesh, which I'm producing as 2d polygon and adding third dimension as 0.0.

[smix8]

There is a 3D version with pr godotengine/godot#87378 that works the same as the 2D version except for having slightly different property names (AABB / Rect2).

[theromis]

@smix8 thank you for useful feature, is it part of any godot releases like godot 4.3-dev3?

[Calinou]

@smix8 thank you for useful feature, is it part of any godot releases like godot 4.3-dev3?

The PR was merged just after 4.3.dev3 was tagged, so it'll be available in 4.3.dev4 or 4.3.beta1.

[theromis]

Thank you for clarification, will try to build sources.

Let me show my situation, maybe godot community can recommend better solution than I found.

level contains Chunks 20x8 boxes + CSGBox3D invisible mesh for "baking floor", during init it called like:

extends NavigationRegion3D
class_name Chunk

func init_blah(...):
...
	bake_setup.call_deferred()

func bake_setup():
	await get_tree().physics_frame
	bake_navigation_mesh()

baking relatively fast but stuck for about 0.25 sec, what is reasonable, but during long playing becomes annoying

this is why I finally tried to make a procedural NavigationMesh and it solves an issue, versus baking just build a simple navigation poligon, but it painful to make holes manually:

#var pass_vertices := PackedVector3Array([
	Vector3(10.0, 0.0, -1.25),
	Vector3(10.0, 0.0, 1.25),
	Vector3(-15.0, 0.0, 1.25),
	Vector3(-15.0, 0.0, -1.25),
])

var navmesh_vertices := PackedVector3Array([
	Vector3(-15.0, 0.0, 40.0),
	Vector3(10.0, 0.0, 40.0),
	Vector3(10.0, 0.0, -40.0),
	Vector3(-15.0, 0.0, -40.0),
])

var navmesh_vertices_polygons := [
	PackedInt32Array([0, 1, 2, 3]),
]
func init_blah2(...):
...
		for v in pass_vertices:
			navmesh_vertices.append(v)
		navmesh_vertices_polygons.append(
			PackedInt32Array([navmesh_vertices_next_index, navmesh_vertices_next_index+1, avmesh_vertices_next_index+2, navmesh_vertices_next_index+3])
		)
		navmesh_vertices_next_index+=4

func bake_setup():
	navmesh_setup()

func navmesh_setup():
	var new_navigation_mesh = NavigationMesh.new()

	new_navigation_mesh.vertices = navmesh_vertices

	for p in navmesh_vertices_polygons:
		new_navigation_mesh.add_polygon(
			p
		)

	navigation_mesh = new_navigation_mesh

Non baking navmesh generation will be ideal by speed if possible do somesthing like:

	var vertices, var polygons = Geometry.create_holed_polygon(edges_vertices, array_of_holes)
	var new_navigation_mesh = NavigationMesh.new()
	new_navigation_mesh.vertices = vertices
	for p in polygons:
		new_navigation_mesh.add_polygon(
			p
		)
	navigation_mesh = new_navigation_mesh

[smix8]

I suspect the reason for the performance drop with the "normal" navigation mesh bake is that CSG meshes are slow to parse and stall the RenderingServer. CSG and rendering meshes are ok-ish for baking in the editor but not really functional in terms of performance to be parsed at runtime. Try to use and parse (physics) collision shapes instaed. They are a lot faster because they are ready-available on the CPU.

[Necronomicron]

A polygon with hole does not exist.

@smix8
What is this?

[theromis]

@Necronomicron I think means on your image you can see multiple triangles without holes connected to form plane with a hole.
@smix8 Thank you for quick reply I tried your approach, same fps drop but now it even not shows navigation map in debug.

[theromis]

@smix8 Found my problem, just not switched parsed_geometry_types to static_colliders now it works without lags, seems like mesh baking slow by itself. Thank you for a great advice.

In a mean time ability to set navigation mesh with holes for avoidance is a great option, because baking not always provides perfect results.

BTW: let me ask side question about navigation baking. If my nav_mesh should be not in XZ plane but vertical, for instance XY, can I change baking settings to make UP direction Vector3(0, 0, 1)?

[smix8]

seems like mesh baking slow by itself

The problem with any visual mesh is that its geometry data is not available by default on the CPU, it is GPU stored. So everytime anything needs to read geometry from a mesh the RenderingServer needs to receive all those data from the GPU and that is super-slow.

an I change baking settings to make UP direction Vector3(0, 0, 1)?

No, the baking always oriented towards Vector3.UP. You would need to bake your mesh and rotate it later, e.g. with the NavigationRegion3D transform. Note that you can not rotate a navigation mesh 90° or more away from the navigation map up orientation.

[theromis]

@smix8 Thank you for detailed explanation, now I have better feeling how godot baking works. For baking orientation seems like was right by rotating whole game 90 degrees and making Y axis UP. Btw: if geometry baking so slow may be better to make static_colliders make default baking settings?

[smix8]

Can not change the default without breaking compatibility for existing projects. For performance it would make more sense but also new user expectation is to just hit bake and consider everything. That is why the newer 2D baking parses both visual and collision by default.

[aXu-AP]

My suggestion as to how this proposal could be implemented:

PackedInt32Array Geometry2D.triangulate_polygons (PackedVector2Array[] polygons)

Works in similiar manner as triangulate_polygon but instead of expecting single polygon, it takes multiple. Polygons must abide by following rules: renderable polygons must be defined in counterclockwise order. Holes are clockwise polygons. No polygons should intersect with themselves or other polygons (these are easy check/fix manually via utilities in Geometry2D class). I think this algorithm would be reasonable to implement (altough I did notice a small mistake that the author has there, but it's easy to fix).
Triangulate_polygons would be nicely compatible with other methods from Geometry2D class as the boolean operations already result in counterclockwise and clockwise polygons.

As a bonus the method would make fixing godotengine/godot#91068 relatively easy. Actually something like this is required to fix the bug anyway, and it would be beneficial to expose it for scripting also.

Optionally add support for holes in Polygon2D with property cut_clockwise_polygons which would enable triangulation with the method above (default would be current behavior for simplicity and backwards compatibility).

[Necronomicron]

Polygons must abide by following rules: renderable polygons must be defined in counterclockwise order. Holes are counterclockwise polygons.

I think holes should be in the opposite direction.

[aXu-AP]

I think holes should be in the opposite direction.

Good catch, I'll fix it 👍

[JestemStefan]

What is the status of this proposal?

[jamesresend]

My issue also regards the creation of holes inside polygons and workaround saves the day.

Since Geometry2D.clip_polygons() does not clip if polygon B is completely inside polygon A, I had the idea to simply move the closest point of B regarding A, outside of A (and also create 2 auxiliary points to minimize impact). After this is done, clip_polygons() worked.

polygons.mp4

This works for my use case (draw a line and create a collision polygon for that line) and that was the target of it. Hopefully this helps someone find their own custom solution in the mean time.

extends Node

const OFFSET_DISTANCE: float = -5.0  # Displacement of the closest point of inner polygon
const VERTICES_DISTANCE: float = 0.1 # Distance of the new points added to the original displaced point

##polygons: Array[PackedVector2Array] == [[Main polygon], [Inner poly 1], [Inner poly 2], ..., [Inner poly n]]


func get_polygon_with_holes(polygons: Array[PackedVector2Array]) -> PackedVector2Array:
	if polygons.size() == 0:
		return PackedVector2Array()
	elif polygons.size() == 1:
		return polygons[0]

	
	var main_polygon: PackedVector2Array = polygons[0]
	var result_polygon: PackedVector2Array = main_polygon.duplicate()
	
	for i in range(1, polygons.size()):
		var current_polygon: PackedVector2Array = polygons[i]
		if is_polygon_inside(current_polygon, main_polygon):
			move_closest_vertex(current_polygon, main_polygon)
		var temp: Array  = Geometry2D.clip_polygons(result_polygon, current_polygon)
		result_polygon = temp[0]
	
	return result_polygon

func is_polygon_inside(inner_polygon: PackedVector2Array, outer_polygon: PackedVector2Array) -> bool:
	for point: Vector2 in inner_polygon:
		if not Geometry2D.is_point_in_polygon(point, outer_polygon):
			return false
	return true

func move_closest_vertex(polygon: PackedVector2Array, main_polygon: PackedVector2Array):
	var closest_distance = INF
	var closest_vertex_index = -1
	var closest_point_on_main: Vector2
	
	for i in range(polygon.size()):
		var vertex: Vector2  = polygon[i]
		for j in range(main_polygon.size()):
			var next_j: int  = (j + 1) % main_polygon.size()
			var point_on_segment: Vector2 = Geometry2D.get_closest_point_to_segment(vertex, main_polygon[j], main_polygon[next_j])
			var distance: float = vertex.distance_to(point_on_segment)
			if distance < closest_distance:
				closest_distance = distance
				closest_vertex_index = i
				closest_point_on_main = point_on_segment
	
	if closest_vertex_index != -1:
		var apex_point: Vector2 = polygon[closest_vertex_index]
		# Move apex_point just outside of main_polygon
		var move_direction: Vector2 = (apex_point - closest_point_on_main).normalized()
		var new_position: Vector2 = closest_point_on_main + move_direction * OFFSET_DISTANCE
		polygon[closest_vertex_index] = new_position
		
		
		# Get adjacent points
		var next_index: int = (closest_vertex_index + 1) % polygon.size()
		var prev_index: int = (closest_vertex_index - 1 + polygon.size()) % polygon.size()
		var next_point: Vector2 = polygon[next_index]
		var prev_point: Vector2 = polygon[prev_index]

		# Add first_new_point as close as possible to apex_point and between apex_point and next_point

		var first_lineVector: Vector2 = (next_point - apex_point).normalized()
		var first_new_point: Vector2  = apex_point + (VERTICES_DISTANCE * first_lineVector)

		# Add second_new_point as close as possible to apex_point and between apex_point and prev_point
		var second_lineVector: Vector2 = (prev_point - apex_point).normalized()
		var second_new_point: Vector2  = apex_point + (VERTICES_DISTANCE * second_lineVector)
		
		polygon.insert(closest_vertex_index + 1, first_new_point)
		polygon.insert(closest_vertex_index, second_new_point)

[DeniZka]

Thanks!
there are some glitches when try crossed multiple cutouts
looks fine when:
if is_polygon_inside(current_polygon, result_polygon): in get_polygon_with_holes