Using the output of Geometry2D.clip_polygons in a mesh

Help Programming
, ,
1

Godot Version

4.4.stable.official.4c311cbee

Question

I’m trying to implement something like CSGPolygon3D on a single flat 3D polygon where making a manifold and using actual CSG nodes and then removing the extra geometry added as placeholder would be massive overkill.

As a simplifying assumption, the polygon being subtracted from is always located between the parallel polygonal faces of the volume being subtracted from it, so this can be done in 2D and then mapped back to 3D.

(Except for the case where the source polygon is perpendicular to the subtractive polygon, which will take a bit more fiddling but is outside the scope of this question because it’s impossible to cut out the “inside” of a line segment.)

In gdscript:

func carve_polygon(original: PackedVector3Array) -> void:
	var carved_pieces: Array[PackedVector3Array] = [original]
	for p: CarvePolygon in _carve_polygons:
		var next_carved_pieces: Array[PackedVector3Array] = []
		for piece in carved_pieces:
			var carve_positions := p.transform.xform_inv(piece)
			for pos in carve_positions:
				assert(pos.z < 0 and pos.z > -p.depth)

			var carve_positions_2d: PackedVector2Array = []
			carve_positions_2d.resize(len(carve_positions))
			for i in len(carve_positions):
				carve_positions_2d[i] = Vector2(carve_positions[i].x, carve_positions[i].y)

			# TODO: handle cases where carve_positions_2d describes a polygon with 0 area (outside the scope of this question)

			var original_clockwise := Geometry2D.is_polygon_clockwise(carve_positions_2d)
			var clipped := Geometry2D.clip_polygons(carve_positions_2d, p.polygon)

			##########################################
			# QUESTION: how do I modify "clipped" so
			# that it contains no holes? (that is, cut
			# any polygon that contains a hole so the
			# hole becomes part of the "outside" of
			# the polygon)
			##########################################

			assert(not clipped.any(Geometry2D.is_polygon_clockwise))

			# convert vertices back to 3D by interpolating using barycentric coordinates in projection space (not part of the question)
			next_carved_pieces.append_array(...)
		carved_pieces = next_carved_pieces

	for polygon in carved_pieces:
		var indices := Geometry2D.triangulate_polygon(polygon)
		# interpolate the UVs using Geometry3D.get_triangle_barycentric_coords (not shown here because it's irrelevant to the question)
		# pass off the resulting triangles to the mesh builder

Edit: I realize some of this might be weird because my original code operates on triangles and I said “source polygon”, so if it’s easier to just triangulate the source polygon first, assume I said that.