extends RefCounted
class_name FaceKit
## FACE PRIMITIVES (#120 F6, docs/node-tree-and-stacks.md §7): how a mesh-style edit
## becomes convex brushes. A face of a brush is one of its planes, and its polygon is
## convex, so an inset, an extrude, a panel or a cable segment is a NEW convex solid
## built over face polygons — never a deformed brush.
##
## Pure and static, like ShapeKit: a generator, the fold and a gate call them the same
## way, with no live brush. Planes are add_brush's shape, 4 floats per plane
## (n.x n.y n.z d), inside where n · x <= d — the same convention Godot's
## compute_convex_mesh_points keeps (geometry_3d.cpp: a point is dropped when
## n · x - d > epsilon).
## A vertex lies on a plane within this (metres). Planes are float32.
const ON_PLANE := 1.0e-3
## The planes of a flat array, as Godot Planes.
static func to_planes(planes: PackedFloat32Array) -> Array[Plane]:
var out: Array[Plane] = []
for i in planes.size() / 4:
out.append(Plane(Vector3(planes[i * 4], planes[i * 4 + 1], planes[i * 4 + 2]), planes[i * 4 + 3]))
return out
## The corners of the solid the planes bound, without duplicates.
static func corners(planes: PackedFloat32Array) -> PackedVector3Array:
var raw: PackedVector3Array = Geometry3D.compute_convex_mesh_points(to_planes(planes))
var out := PackedVector3Array()
for v: Vector3 in raw:
var seen := false
for u: Vector3 in out:
if u.distance_to(v) < ON_PLANE:
seen = true
break
if not seen:
out.append(v)
return out
## The convex polygon of face `i`, counter-clockwise seen from outside (right-handed
## about the face's outward normal). Starts at the corner with the smallest
## (x, y, z), so the same planes always give the same first vertex. Empty if the face
## is degenerate (fewer than three corners: the plane only touches the solid).
static func face_polygon(planes: PackedFloat32Array, i: int) -> PackedVector3Array:
var n := Vector3(planes[i * 4], planes[i * 4 + 1], planes[i * 4 + 2])
var d := planes[i * 4 + 3]
var nl := n.length()
if nl < 1.0e-9:
return PackedVector3Array()
n /= nl
d /= nl
var on: Array = []
for v: Vector3 in corners(planes):
if absf(n.dot(v) - d) < ON_PLANE:
on.append(v)
if on.size() < 3:
return PackedVector3Array()
var c := Vector3.ZERO
for v: Vector3 in on:
c += v
c /= float(on.size())
var u: Vector3 = ((on[0] as Vector3) - c).normalized()
var w := n.cross(u)
on.sort_custom(func(a: Vector3, b: Vector3) -> bool:
return atan2((a - c).dot(w), (a - c).dot(u)) < atan2((b - c).dot(w), (b - c).dot(u)))
var first := 0
for k in on.size():
if _before(on[k], on[first]):
first = k
var out := PackedVector3Array()
for k in on.size():
out.append(on[(first + k) % on.size()])
return out
static func _before(a: Vector3, b: Vector3) -> bool:
if absf(a.x - b.x) > ON_PLANE:
return a.x < b.x
if absf(a.y - b.y) > ON_PLANE:
return a.y < b.y
return a.z < b.z
## A prism over a convex polygon (counter-clockwise about `normal`), from the polygon's
## plane to `depth` along the normal. Negative depth goes inward, which is a recess's
## cutter; positive is an extrude, a plate. Built plane by plane — two caps, one side
## per edge — so no hull is needed and the polygon's plane is reproduced EXACTLY.
static func prism(poly: PackedVector3Array, normal: Vector3, depth: float) -> PackedFloat32Array:
var out := PackedFloat32Array()
if poly.size() < 3 or absf(depth) < 1.0e-6:
return out
var n := normal.normalized()
var d0 := n.dot(poly[0])
var lo := minf(0.0, depth)
var hi := maxf(0.0, depth)
_push(out, n, d0 + hi) # outer cap
_push(out, -n, -(d0 + lo)) # inner cap
for k in poly.size():
var a := poly[k]
var b := poly[(k + 1) % poly.size()]
var s := (b - a).cross(n)
if s.length() < 1.0e-9:
continue # repeated vertex
s = s.normalized()
_push(out, s, s.dot(a))
return out
static func _push(out: PackedFloat32Array, n: Vector3, d: float) -> void:
out.append(n.x)
out.append(n.y)
out.append(n.z)
out.append(d)
## The convex hull of two cross-sections (a cable segment, a sweep step) as planes,
## by the STATIC DCLevel.hull_of — the same hull merge_brushes uses, one hull rule, and
## no DCLevel needed (a fold, a gate, a headless peer). Empty when the two are coplanar.
static func hull_sections(a: PackedVector3Array, b: PackedVector3Array) -> PackedFloat32Array:
var pts := PackedVector3Array(a)
pts.append_array(b)
return DCLevel.hull_of(pts)
## Rectangles covering a union of grid cells exactly, no overlaps (Random Flow's panels:
## a random walk claims cells, each rectangle becomes one prism). Greedy and
## deterministic: from the first free cell in (y, x) order, run right, then grow down
## while the whole run below is free.
static func split_rects(cells: Array) -> Array[Rect2i]:
var free := {}
for c: Vector2i in cells:
free[c] = true
var order: Array = free.keys()
order.sort_custom(func(a: Vector2i, b: Vector2i) -> bool: return a.y < b.y or (a.y == b.y and a.x < b.x))
var out: Array[Rect2i] = []
for c: Vector2i in order:
if not free.has(c):
continue
var w := 1
while free.has(Vector2i(c.x + w, c.y)):
w += 1
var h := 1
while true:
var row_free := true
for x in w:
if not free.has(Vector2i(c.x + x, c.y + h)):
row_free = false
break
if not row_free:
break
h += 1
for y in h:
for x in w:
free.erase(Vector2i(c.x + x, c.y + y))
out.append(Rect2i(c, Vector2i(w, h)))
return out