Generalized Bezier Patch Generation in GDScript

bezier_sample

@tool
extends Node

@export var inputs: Array[Marker3D]
@export_range(0, 1, 1, "or_greater") var resolution: int = 0
@export_range(1, 50, 1, "or_greater") var process_tick: int = 25

@export var build: bool

@export var show_only_inputs := true
@export var mi: MeshInstance3D

func _process(delta: float) -> void:
	if !build || Engine.get_process_frames() % process_tick:
		return
		
	
	var im := mi.mesh as ImmediateMesh
	if !im || !inputs:
		return
	
	var control_points: Array[Array] = [[], [], []]
	for i in inputs.size():
		control_points[i/3].append(inputs[i].global_position)

	im.clear_surfaces()
	im.surface_begin(Mesh.PRIMITIVE_TRIANGLES)
	#im.surface_begin(Mesh.PRIMITIVE_POINTS)
	
	if show_only_inputs:
		for row in control_points:
			for col in row:
				im.surface_add_vertex(col)
				
	else:
		var _r := resolution + 1
		var vertices: Array = []
			
		for u in range(_r):
			var current_strip: Array = []
			for v in range(_r):
				var _u = u / float(_r - 1)
				var _v = v / float(_r - 1)
				var vertex_data = get_bezier_vertex_data(control_points, _u, _v)
				vertices.append(vertex_data)
			
		#var indices: Array = [ ]
		#var i_count: int = 0
		#indices.resize((vertices.size() - 2) * 3)
		#for i in range(vertices.size() - 2):
			#indices[i_count] = 0
			#indices[i_count + 1] = i + 1
			#indices[i_count + 2] = i + 2
			#i_count += 3

		var indices := get_triangle_indices(_r, _r)

		for vertex_id in indices:
			im.surface_set_normal(vertices[vertex_id][1])
			im.surface_set_tangent(vertices[vertex_id][4])
			im.surface_add_vertex(vertices[vertex_id][0])

	im.surface_end()
	return

func bernstein_derivative(n: int, i: int, t: float) -> float:
	if !n: return 0
	return n * (bernstein_poly(n - 1, i - 1, t) - bernstein_poly(n - 1, i, t))

func get_binomial_coefficient(n: int, k: int) -> int:
	if k > n: return 0
	var _r : int = 1
	
	# Pascal's Triangle is symmetric, so we can mirror it
	if k > n - k:
		k = n - k
	
	# Recursively add
	for i in range(1, k + 1):
		_r = _r * (n - i + 1) / i
	
	return _r


func bernstein_poly(n: int, i: int, t: float) -> float: 
	return get_binomial_coefficient(n, i) * (t ** i) * ((1 - t) ** (n-i))
	
	
func get_bezier_vertex_data(control_points: Array[Array], u: float, v: float) -> Array:
	var p := Vector3.ZERO
	var tangent_u := Vector3.ZERO
	var tangent_v := Vector3.ZERO
	var m: int = control_points.size()
	var n: int = control_points[0].size()

	for i in m:
		for j in n:
			var b_u: float = bernstein_poly(m - 1, i, u)
			var b_v: float = bernstein_poly(n - 1, j, v)
			var db_u: float = bernstein_derivative(m - 1, i, u)
			var db_v: float = bernstein_derivative(n - 1, j, v)
			
			# These begin at Vector3() before this loop
			p += control_points[i][j] * b_u * b_v
			tangent_u += control_points[i][j] * db_u * b_v
			tangent_v += control_points[i][j] * b_u * db_v

	var normal := tangent_u.cross(tangent_v).normalized()
	
	#if normal.is_zero_approx() || !normal.is_finite():
		#normal = Vector3.UP
	
	var w := signf(normal.cross(tangent_u).normalized().dot(tangent_v))
	var tangent_plane := Plane(tangent_u.x, tangent_u.y, tangent_u.z, w)
	
	return [p, normal, tangent_u.normalized(), tangent_v.normalized(), tangent_plane]


func get_triangle_indices(width: int, height: int) -> Array[int]:
	var indices := [] as Array[int]
	# Ensure the grid has more than one row and column
	if width < 2 or height < 2:
		print("Grid size too small to form triangles.")
		return indices
	
	# Generate indices for each square in the grid
	for row in range(height - 1):
		for col in range(width - 1):
			# First triangle of the square
			indices.append(col + row * width)             # Top-left
			indices.append((col + 1) + row * width)       # Top-right
			indices.append(col + (row + 1) * width)       # Bottom-left
			
			# Second triangle of the square
			indices.append((col + 1) + row * width)       # Top-right
			indices.append((col + 1) + (row + 1) * width) # Bottom-right
			indices.append(col + (row + 1) * width)       # Bottom-left
	return indices