@tool
class_name MCVoxelTerrain extends StaticBody3D
## Marching cubes terrain with 3D noise for caves, overhangs, and arches.
## Replaces heightmap TerrainGenerator for wall climbing tests.
@export var terrain_size: float = 60.0:
set(v):
terrain_size = v
if Engine.is_editor_hint() and is_inside_tree():
_rebuild()
@export var voxel_resolution: int = 48:
set(v):
voxel_resolution = clampi(v, 8, 128)
if Engine.is_editor_hint() and is_inside_tree():
_rebuild()
@export_group("Noise")
@export var noise_seed: int = 42:
set(v):
noise_seed = v
if Engine.is_editor_hint() and is_inside_tree():
_rebuild()
@export var iso_threshold: float = 0.0:
set(v):
iso_threshold = v
if Engine.is_editor_hint() and is_inside_tree():
_rebuild()
@export var flat_center_radius: float = 12.0:
set(v):
flat_center_radius = v
if Engine.is_editor_hint() and is_inside_tree():
_rebuild()
@export_group("Ground")
## Weak ground plane bias — keeps terrain from floating away entirely.
## Low values (0.03-0.06) let 3D noise dominate for caves/overhangs.
@export var ground_bias: float = 0.06:
set(v):
ground_bias = v
if Engine.is_editor_hint() and is_inside_tree():
_rebuild()
## Depth below which terrain becomes unconditionally solid (floor).
@export var solid_floor_depth: float = 30.0:
set(v):
solid_floor_depth = v
if Engine.is_editor_hint() and is_inside_tree():
_rebuild()
## Height above which terrain becomes unconditionally air (sky).
@export var sky_height: float = 25.0:
set(v):
sky_height = v
if Engine.is_editor_hint() and is_inside_tree():
_rebuild()
@export_group("Primary 3D Noise")
## Large-scale 3D noise — creates the dominant terrain shape (big caves, masses).
@export var primary_frequency: float = 0.02:
set(v):
primary_frequency = v
if Engine.is_editor_hint() and is_inside_tree():
_rebuild()
@export var primary_strength: float = 1.2:
set(v):
primary_strength = v
if Engine.is_editor_hint() and is_inside_tree():
_rebuild()
@export_group("Cave Tunnels")
## Worm-tunnel frequency — two perpendicular 3D noises that carve tubes where both cross zero.
@export var tunnel_frequency: float = 0.03:
set(v):
tunnel_frequency = v
if Engine.is_editor_hint() and is_inside_tree():
_rebuild()
## How aggressively tunnels carve into solid matter.
@export var tunnel_strength: float = 1.5:
set(v):
tunnel_strength = v
if Engine.is_editor_hint() and is_inside_tree():
_rebuild()
## Tunnel radius control — lower = wider tunnels (0.1-0.4 typical).
@export var tunnel_radius: float = 0.3:
set(v):
tunnel_radius = v
if Engine.is_editor_hint() and is_inside_tree():
_rebuild()
@export_group("Ridged Noise (Pillars/Arches)")
## Ridged noise creates sharp pillars, arches, and bridge-like formations.
@export var ridge_frequency: float = 0.03:
set(v):
ridge_frequency = v
if Engine.is_editor_hint() and is_inside_tree():
_rebuild()
@export var ridge_strength: float = 0.5:
set(v):
ridge_strength = v
if Engine.is_editor_hint() and is_inside_tree():
_rebuild()
@export_group("Domain Warping")
## Warps noise input coordinates for more organic, less grid-like shapes.
@export var warp_frequency: float = 0.015:
set(v):
warp_frequency = v
if Engine.is_editor_hint() and is_inside_tree():
_rebuild()
@export var warp_strength: float = 4.0:
set(v):
warp_strength = v
if Engine.is_editor_hint() and is_inside_tree():
_rebuild()
@export_group("Detail Noise")
## Small-scale surface detail — roughens surfaces without changing large structure.
@export var detail_frequency: float = 0.06:
set(v):
detail_frequency = v
if Engine.is_editor_hint() and is_inside_tree():
_rebuild()
@export var detail_strength: float = 0.15:
set(v):
detail_strength = v
if Engine.is_editor_hint() and is_inside_tree():
_rebuild()
@export_group("Voronoi Floors")
## Number of Voronoi cells across the terrain (more = smaller rooms)
@export var voronoi_cell_count: int = 6:
set(v):
voronoi_cell_count = clampi(v, 2, 20)
if Engine.is_editor_hint() and is_inside_tree():
_rebuild()
## How strongly floors flatten the terrain (0 = no effect, 1 = completely flat)
@export_range(0.0, 1.0, 0.05) var floor_strength: float = 0.7:
set(v):
floor_strength = v
if Engine.is_editor_hint() and is_inside_tree():
_rebuild()
## Minimum floor height (relative to center)
@export var floor_height_min: float = -15.0:
set(v):
floor_height_min = v
if Engine.is_editor_hint() and is_inside_tree():
_rebuild()
## Maximum floor height (relative to center)
@export var floor_height_max: float = 10.0:
set(v):
floor_height_max = v
if Engine.is_editor_hint() and is_inside_tree():
_rebuild()
## Room height (distance from floor to ceiling)
@export var room_height: float = 8.0:
set(v):
room_height = v
if Engine.is_editor_hint() and is_inside_tree():
_rebuild()
@export_group("Material")
@export var terrain_color: Color = Color(0.35, 0.40, 0.30, 1.0):
set(v):
terrain_color = v
if Engine.is_editor_hint() and is_inside_tree():
_rebuild()
@export var rebuild: bool = false:
set(v):
if v:
_rebuild()
rebuild = false
var _mesh_instance: MeshInstance3D = null
var _collision: CollisionShape3D = null
func _ready() -> void:
call_deferred("_rebuild")
func _rebuild() -> void:
# --- Noise generators ---
# Primary 3D noise: dominant terrain shape (large caves, solid masses)
var primary_noise := FastNoiseLite.new()
primary_noise.seed = noise_seed
primary_noise.noise_type = FastNoiseLite.TYPE_SIMPLEX_SMOOTH
primary_noise.frequency = primary_frequency
primary_noise.fractal_octaves = 3
# Tunnel noise A: first axis of worm-tunnel carving
var tunnel_a := FastNoiseLite.new()
tunnel_a.seed = noise_seed + 10
tunnel_a.noise_type = FastNoiseLite.TYPE_SIMPLEX_SMOOTH
tunnel_a.frequency = tunnel_frequency
tunnel_a.fractal_octaves = 2
# Tunnel noise B: perpendicular axis — tubes form where both cross zero
var tunnel_b := FastNoiseLite.new()
tunnel_b.seed = noise_seed + 20
tunnel_b.noise_type = FastNoiseLite.TYPE_SIMPLEX_SMOOTH
tunnel_b.frequency = tunnel_frequency
tunnel_b.fractal_octaves = 2
# Ridge noise: creates sharp pillars, arches, bridge formations
var ridge_noise := FastNoiseLite.new()
ridge_noise.seed = noise_seed + 30
ridge_noise.noise_type = FastNoiseLite.TYPE_SIMPLEX_SMOOTH
ridge_noise.frequency = ridge_frequency
ridge_noise.fractal_octaves = 2
# Domain warp noise: warps coordinates for organic shapes
var warp_noise := FastNoiseLite.new()
warp_noise.seed = noise_seed + 40
warp_noise.noise_type = FastNoiseLite.TYPE_SIMPLEX_SMOOTH
warp_noise.frequency = warp_frequency
warp_noise.fractal_octaves = 2
# Detail noise: small-scale surface roughness
var detail_noise := FastNoiseLite.new()
detail_noise.seed = noise_seed + 50
detail_noise.noise_type = FastNoiseLite.TYPE_SIMPLEX_SMOOTH
detail_noise.frequency = detail_frequency
detail_noise.fractal_octaves = 2
var half: float = terrain_size / 2.0
var step: float = terrain_size / float(voxel_resolution)
var res: int = voxel_resolution + 1
# Generate Voronoi cell centers with random floor heights
var cell_rng := RandomNumberGenerator.new()
cell_rng.seed = noise_seed + 100
var voronoi_centers: Array[Vector2] = []
var voronoi_floor_heights: Array[float] = []
var cell_spacing: float = terrain_size / float(voronoi_cell_count)
for cy in range(voronoi_cell_count):
for cx in range(voronoi_cell_count):
# Jittered grid for Voronoi
var center_x: float = -half + (cx + cell_rng.randf_range(0.2, 0.8)) * cell_spacing
var center_z: float = -half + (cy + cell_rng.randf_range(0.2, 0.8)) * cell_spacing
voronoi_centers.append(Vector2(center_x, center_z))
voronoi_floor_heights.append(cell_rng.randf_range(floor_height_min, floor_height_max))
# Sample 3D density field
var density: PackedFloat32Array = PackedFloat32Array()
density.resize(res * res * res)
for z_i in range(res):
for y_i in range(res):
for x_i in range(res):
var x: float = -half + x_i * step
var y: float = -half + y_i * step
var z: float = -half + z_i * step
var idx: int = z_i * res * res + y_i * res + x_i
# === Domain warping: offset sample coords for organic shapes ===
var wx: float = x + warp_noise.get_noise_3d(x, y, z) * warp_strength
var wy: float = y + warp_noise.get_noise_3d(x + 31.7, y + 47.3, z + 89.1) * warp_strength
var wz: float = z + warp_noise.get_noise_3d(x + 73.1, y + 11.9, z + 59.7) * warp_strength
# === 1. Weak ground plane bias ===
# Just enough to ensure SOME ground exists — noise dominates shape
var d: float = -y * ground_bias
# === 2. Primary 3D noise — the DOMINANT shape term ===
# This is NOT a heightmap. Full 3D creates caves, overhangs, masses.
d += primary_noise.get_noise_3d(wx, wy, wz) * primary_strength
# === 3. Worm tunnels — carved where two perpendicular noises both cross zero ===
# The squared sum of two noise values is small only along a tube-like path.
# This creates genuine walkable tunnels, not just surface dents.
var ta: float = tunnel_a.get_noise_3d(wx, wy * 0.7, wz)
var tb: float = tunnel_b.get_noise_3d(wx + 200.0, wy * 0.7, wz + 200.0)
var tube_dist_sq: float = ta * ta + tb * tb
# Carve where tube_dist_sq < tunnel_radius^2 (inside the tube)
var tube_carve: float = maxf(1.0 - tube_dist_sq / (tunnel_radius * tunnel_radius), 0.0)
d -= tube_carve * tunnel_strength
# === 4. Ridged noise for pillars, arches, bridges ===
# 1.0 - abs(noise) peaks sharply at zero crossings, creating thin ridges
# that read as pillars (vertical) and arches (horizontal)
var ridge_raw: float = ridge_noise.get_noise_3d(wx, wy, wz)
var ridged: float = 1.0 - absf(ridge_raw)
# Square it to sharpen the ridges further
ridged = ridged * ridged
d += ridged * ridge_strength
# === 5. Surface detail ===
d += detail_noise.get_noise_3d(wx, wy, wz) * detail_strength
# === 5.5. Voronoi floor/ceiling flattening ===
# Find nearest Voronoi cell
var xz := Vector2(x, z)
var nearest_dist_sq: float = INF
var nearest_floor_h: float = 0.0
var second_dist_sq: float = INF
for vi in range(voronoi_centers.size()):
var vd: float = xz.distance_squared_to(voronoi_centers[vi])
if vd < nearest_dist_sq:
second_dist_sq = nearest_dist_sq
nearest_dist_sq = vd
nearest_floor_h = voronoi_floor_heights[vi]
elif vd < second_dist_sq:
second_dist_sq = vd
# Edge blend: smooth transition between cells (0 at edge, 1 at center)
var edge_ratio: float = 1.0 - nearest_dist_sq / (second_dist_sq + 0.001)
var cell_blend: float = clampf(edge_ratio * 2.0, 0.0, 1.0)
cell_blend = cell_blend * cell_blend * (3.0 - 2.0 * cell_blend) # smoothstep
# Floor: strong downward push below floor height, creates flat surface
var floor_dist: float = nearest_floor_h - y
var floor_effect: float = 0.0
if floor_dist > 0.0:
# Below floor: make solid
floor_effect = clampf(floor_dist * 0.5, 0.0, 2.0)
elif floor_dist > -1.5:
# Just above floor: sharp transition to air
floor_effect = floor_dist * 1.5
# Ceiling: prevent terrain above room_height from floor
var ceiling_h: float = nearest_floor_h + room_height
var ceil_dist: float = y - ceiling_h
var ceil_effect: float = 0.0
if ceil_dist > 0.0 and ceil_dist < 3.0:
ceil_effect = -clampf(ceil_dist * 0.5, 0.0, 2.0)
# Apply floor/ceiling effect, modulated by cell center proximity and strength
var voronoi_effect: float = (floor_effect + ceil_effect) * cell_blend * floor_strength
d += voronoi_effect
# === 6. Height clamping — solid floor and open sky ===
# Deep underground becomes unconditionally solid
var floor_blend: float = maxf((-y - solid_floor_depth) * 0.1, 0.0)
d += floor_blend
# High up becomes unconditionally air
var sky_blend: float = maxf((y - sky_height) * 0.1, 0.0)
d -= sky_blend
# === 7. Flat spawn area ===
var dist_xz: float = Vector2(x, z).length()
var safe_radius: float = flat_center_radius
var transition: float = safe_radius * 0.5
if dist_xz < safe_radius + transition:
# Smooth blend from wild terrain to flat ground
var blend: float = 1.0 - clampf((dist_xz - safe_radius * 0.3) / (safe_radius * 0.7 + transition), 0.0, 1.0)
blend = blend * blend * (3.0 - 2.0 * blend) # Smoothstep
# Flat ground: strong downward bias below y=0, strong upward above
var flat_d: float = -y * 0.8
d = lerpf(d, flat_d, blend)
density[idx] = d
# Marching cubes
var positions := PackedVector3Array()
var normals := PackedVector3Array()
var indices := PackedInt32Array()
_march(density, res, step, half, positions, normals, indices)
if positions.is_empty():
return
# Build mesh
var arrays := []
arrays.resize(Mesh.ARRAY_MAX)
arrays[Mesh.ARRAY_VERTEX] = positions
arrays[Mesh.ARRAY_NORMAL] = normals
arrays[Mesh.ARRAY_INDEX] = indices
var mesh := ArrayMesh.new()
mesh.add_surface_from_arrays(Mesh.PRIMITIVE_TRIANGLES, arrays)
var mat := StandardMaterial3D.new()
mat.albedo_color = terrain_color
mesh.surface_set_material(0, mat)
# Find or create child nodes
if _mesh_instance == null:
_mesh_instance = _find_or_create_child("VoxelMesh", "MeshInstance3D") as MeshInstance3D
_mesh_instance.mesh = mesh
if _collision == null:
_collision = _find_or_create_child("VoxelCollision", "CollisionShape3D") as CollisionShape3D
var shape := ConcavePolygonShape3D.new()
shape.set_faces(mesh.get_faces())
_collision.shape = shape
print("[VoxelTerrain] Generated: ", positions.size(), " verts, ", indices.size() / 3, " tris")
func _march(density: PackedFloat32Array, res: int, step: float, half: float,
positions: PackedVector3Array, normals: PackedVector3Array,
indices: PackedInt32Array) -> void:
var threshold: float = iso_threshold
var vert_map: Dictionary = {}
for z_i in range(res - 1):
for y_i in range(res - 1):
for x_i in range(res - 1):
var corners: PackedFloat32Array = PackedFloat32Array()
corners.resize(8)
corners[0] = density[_idx3(x_i, y_i, z_i, res)]
corners[1] = density[_idx3(x_i + 1, y_i, z_i, res)]
corners[2] = density[_idx3(x_i + 1, y_i, z_i + 1, res)]
corners[3] = density[_idx3(x_i, y_i, z_i + 1, res)]
corners[4] = density[_idx3(x_i, y_i + 1, z_i, res)]
corners[5] = density[_idx3(x_i + 1, y_i + 1, z_i, res)]
corners[6] = density[_idx3(x_i + 1, y_i + 1, z_i + 1, res)]
corners[7] = density[_idx3(x_i, y_i + 1, z_i + 1, res)]
var cube_index: int = 0
for ci in range(8):
if corners[ci] > threshold:
cube_index |= (1 << ci)
if cube_index == 0 or cube_index == 255:
continue
var edge_flags: int = EDGE_TABLE[cube_index]
if edge_flags == 0:
continue
# Corner world positions
var bx: float = -half + x_i * step
var by: float = -half + y_i * step
var bz: float = -half + z_i * step
var p: Array[Vector3] = []
p.resize(8)
p[0] = Vector3(bx, by, bz)
p[1] = Vector3(bx + step, by, bz)
p[2] = Vector3(bx + step, by, bz + step)
p[3] = Vector3(bx, by, bz + step)
p[4] = Vector3(bx, by + step, bz)
p[5] = Vector3(bx + step, by + step, bz)
p[6] = Vector3(bx + step, by + step, bz + step)
p[7] = Vector3(bx, by + step, bz + step)
# Interpolate edge vertices
var edge_verts: Array[Vector3] = []
edge_verts.resize(12)
for ei in range(12):
if edge_flags & (1 << ei):
var e0: int = EDGE_PAIRS[ei][0]
var e1: int = EDGE_PAIRS[ei][1]
var t: float = (threshold - corners[e0]) / (corners[e1] - corners[e0] + 0.0001)
t = clampf(t, 0.0, 1.0)
edge_verts[ei] = p[e0].lerp(p[e1], t)
else:
edge_verts[ei] = Vector3.ZERO
# Build triangles from table
var tris: Array = TRI_TABLE[cube_index]
var ti: int = 0
while ti < tris.size() and tris[ti] != -1:
var tri_indices: Array[int] = []
for tv in range(3):
var edge: int = tris[ti + tv]
var vert: Vector3 = edge_verts[edge]
# Deduplicate by edge key
var key: int = _edge_key(x_i, y_i, z_i, edge, res)
if key in vert_map:
tri_indices.append(vert_map[key])
else:
var vi: int = positions.size()
positions.append(vert)
normals.append(Vector3.UP)
vert_map[key] = vi
tri_indices.append(vi)
# Winding: swap 1↔2 so normals point outward (positive density = solid)
indices.append(tri_indices[0])
indices.append(tri_indices[2])
indices.append(tri_indices[1])
ti += 3
# Compute smooth normals from faces
var normal_accum: PackedVector3Array = PackedVector3Array()
normal_accum.resize(positions.size())
for ni in range(normal_accum.size()):
normal_accum[ni] = Vector3.ZERO
var tri_count: int = indices.size() / 3
for ti2 in range(tri_count):
var i0: int = indices[ti2 * 3]
var i1: int = indices[ti2 * 3 + 1]
var i2: int = indices[ti2 * 3 + 2]
var face_normal: Vector3 = (positions[i2] - positions[i0]).cross(positions[i1] - positions[i0])
normal_accum[i0] += face_normal
normal_accum[i1] += face_normal
normal_accum[i2] += face_normal
for ni2 in range(positions.size()):
var n: Vector3 = normal_accum[ni2]
normals[ni2] = n.normalized() if n.length_squared() > 0.0001 else Vector3.UP
func _idx3(x: int, y: int, z: int, res_val: int) -> int:
return z * res_val * res_val + y * res_val + x
func _edge_key(x: int, y: int, z: int, edge: int, res_val: int) -> int:
var e0: int = EDGE_PAIRS[edge][0]
var e1: int = EDGE_PAIRS[edge][1]
var ox0: int = x + CORNER_OFFSETS[e0][0]
var oy0: int = y + CORNER_OFFSETS[e0][1]
var oz0: int = z + CORNER_OFFSETS[e0][2]
var ox1: int = x + CORNER_OFFSETS[e1][0]
var oy1: int = y + CORNER_OFFSETS[e1][1]
var oz1: int = z + CORNER_OFFSETS[e1][2]
var k0: int = oz0 * res_val * res_val + oy0 * res_val + ox0
var k1: int = oz1 * res_val * res_val + oy1 * res_val + ox1
if k0 > k1:
var tmp: int = k0
k0 = k1
k1 = tmp
return k0 * res_val * res_val * res_val + k1
func _find_or_create_child(child_name: String, type_name: String) -> Node:
for child in get_children():
if child.name == child_name:
return child
var node: Node
match type_name:
"MeshInstance3D":
node = MeshInstance3D.new()
"CollisionShape3D":
node = CollisionShape3D.new()
_:
node = Node3D.new()
node.name = child_name
add_child(node)
if Engine.is_editor_hint():
node.owner = null # Don't serialize into .tscn
return node
# ---------------------------------------------------------------------------
# Marching Cubes Lookup Tables (Paul Bourke)
# ---------------------------------------------------------------------------
const CORNER_OFFSETS: Array = [
[0,0,0], [1,0,0], [1,0,1], [0,0,1],
[0,1,0], [1,1,0], [1,1,1], [0,1,1]
]
const EDGE_PAIRS: Array = [
[0,1], [1,2], [2,3], [3,0],
[4,5], [5,6], [6,7], [7,4],
[0,4], [1,5], [2,6], [3,7]
]
const EDGE_TABLE: Array = [
0x0, 0x109, 0x203, 0x30a, 0x406, 0x50f, 0x605, 0x70c,
0x80c, 0x905, 0xa0f, 0xb06, 0xc0a, 0xd03, 0xe09, 0xf00,
0x190, 0x99, 0x393, 0x29a, 0x596, 0x49f, 0x795, 0x69c,
0x99c, 0x895, 0xb9f, 0xa96, 0xd9a, 0xc93, 0xf99, 0xe90,
0x230, 0x339, 0x33, 0x13a, 0x636, 0x73f, 0x435, 0x53c,
0xa3c, 0xb35, 0x83f, 0x936, 0xe3a, 0xf33, 0xc39, 0xd30,
0x3a0, 0x2a9, 0x1a3, 0xaa, 0x7a6, 0x6af, 0x5a5, 0x4ac,
0xbac, 0xaa5, 0x9af, 0x8a6, 0xfaa, 0xea3, 0xda9, 0xca0,
0x460, 0x569, 0x663, 0x76a, 0x66, 0x16f, 0x265, 0x36c,
0xc6c, 0xd65, 0xe6f, 0xf66, 0x86a, 0x963, 0xa69, 0xb60,
0x5f0, 0x4f9, 0x7f3, 0x6fa, 0x1f6, 0xff, 0x3f5, 0x2fc,
0xdfc, 0xcf5, 0xfff, 0xef6, 0x9fa, 0x8f3, 0xbf9, 0xaf0,
0x650, 0x759, 0x453, 0x55a, 0x256, 0x35f, 0x55, 0x15c,
0xe5c, 0xf55, 0xc5f, 0xd56, 0xa5a, 0xb53, 0x859, 0x950,
0x7c0, 0x6c9, 0x5c3, 0x4ca, 0x3c6, 0x2cf, 0x1c5, 0xcc,
0xfcc, 0xec5, 0xdcf, 0xcc6, 0xbca, 0xac3, 0x9c9, 0x8c0,
0x8c0, 0x9c9, 0xac3, 0xbca, 0xcc6, 0xdcf, 0xec5, 0xfcc,
0xcc, 0x1c5, 0x2cf, 0x3c6, 0x4ca, 0x5c3, 0x6c9, 0x7c0,
0x950, 0x859, 0xb53, 0xa5a, 0xd56, 0xc5f, 0xf55, 0xe5c,
0x15c, 0x55, 0x35f, 0x256, 0x55a, 0x453, 0x759, 0x650,
0xaf0, 0xbf9, 0x8f3, 0x9fa, 0xef6, 0xfff, 0xcf5, 0xdfc,
0x2fc, 0x3f5, 0xff, 0x1f6, 0x6fa, 0x7f3, 0x4f9, 0x5f0,
0xb60, 0xa69, 0x963, 0x86a, 0xf66, 0xe6f, 0xd65, 0xc6c,
0x36c, 0x265, 0x16f, 0x66, 0x76a, 0x663, 0x569, 0x460,
0xca0, 0xda9, 0xea3, 0xfaa, 0x8a6, 0x9af, 0xaa5, 0xbac,
0x4ac, 0x5a5, 0x6af, 0x7a6, 0xaa, 0x1a3, 0x2a9, 0x3a0,
0xd30, 0xc39, 0xf33, 0xe3a, 0x936, 0x83f, 0xb35, 0xa3c,
0x53c, 0x435, 0x73f, 0x636, 0x13a, 0x33, 0x339, 0x230,
0xe90, 0xf99, 0xc93, 0xd9a, 0xa96, 0xb9f, 0x895, 0x99c,
0x69c, 0x795, 0x49f, 0x596, 0x29a, 0x393, 0x99, 0x190,
0xf00, 0xe09, 0xd03, 0xc0a, 0xb06, 0xa0f, 0x905, 0x80c,
0x70c, 0x605, 0x50f, 0x406, 0x30a, 0x203, 0x109, 0x0
]
const TRI_TABLE: Array = [
[-1],
[0, 8, 3, -1],
[0, 1, 9, -1],
[1, 8, 3, 9, 8, 1, -1],
[1, 2, 10, -1],
[0, 8, 3, 1, 2, 10, -1],
[9, 2, 10, 0, 2, 9, -1],
[2, 8, 3, 2, 10, 8, 10, 9, 8, -1],
[3, 11, 2, -1],
[0, 11, 2, 8, 11, 0, -1],
[1, 9, 0, 2, 3, 11, -1],
[1, 11, 2, 1, 9, 11, 9, 8, 11, -1],
[3, 10, 1, 11, 10, 3, -1],
[0, 10, 1, 0, 8, 10, 8, 11, 10, -1],
[3, 9, 0, 3, 11, 9, 11, 10, 9, -1],
[9, 8, 10, 10, 8, 11, -1],
[4, 7, 8, -1],
[4, 3, 0, 7, 3, 4, -1],
[0, 1, 9, 8, 4, 7, -1],
[4, 1, 9, 4, 7, 1, 7, 3, 1, -1],
[1, 2, 10, 8, 4, 7, -1],
[3, 4, 7, 3, 0, 4, 1, 2, 10, -1],
[9, 2, 10, 9, 0, 2, 8, 4, 7, -1],
[2, 10, 9, 2, 9, 7, 2, 7, 3, 7, 9, 4, -1],
[8, 4, 7, 3, 11, 2, -1],
[11, 4, 7, 11, 2, 4, 2, 0, 4, -1],
[9, 0, 1, 8, 4, 7, 2, 3, 11, -1],
[4, 7, 11, 9, 4, 11, 9, 11, 2, 9, 2, 1, -1],
[3, 10, 1, 3, 11, 10, 7, 8, 4, -1],
[1, 11, 10, 1, 4, 11, 1, 0, 4, 7, 11, 4, -1],
[4, 7, 8, 9, 0, 11, 9, 11, 10, 11, 0, 3, -1],
[4, 7, 11, 4, 11, 9, 9, 11, 10, -1],
[9, 5, 4, -1],
[9, 5, 4, 0, 8, 3, -1],
[0, 5, 4, 1, 5, 0, -1],
[8, 5, 4, 8, 3, 5, 3, 1, 5, -1],
[1, 2, 10, 9, 5, 4, -1],
[3, 0, 8, 1, 2, 10, 4, 9, 5, -1],
[5, 2, 10, 5, 4, 2, 4, 0, 2, -1],
[2, 10, 5, 3, 2, 5, 3, 5, 4, 3, 4, 8, -1],
[9, 5, 4, 2, 3, 11, -1],
[0, 11, 2, 0, 8, 11, 4, 9, 5, -1],
[0, 5, 4, 0, 1, 5, 2, 3, 11, -1],
[2, 1, 5, 2, 5, 8, 2, 8, 11, 4, 8, 5, -1],
[10, 3, 11, 10, 1, 3, 9, 5, 4, -1],
[4, 9, 5, 0, 8, 1, 8, 10, 1, 8, 11, 10, -1],
[5, 4, 0, 5, 0, 11, 5, 11, 10, 11, 0, 3, -1],
[5, 4, 8, 5, 8, 10, 10, 8, 11, -1],
[9, 7, 8, 5, 7, 9, -1],
[9, 3, 0, 9, 5, 3, 5, 7, 3, -1],
[0, 7, 8, 0, 1, 7, 1, 5, 7, -1],
[1, 5, 3, 3, 5, 7, -1],
[9, 7, 8, 9, 5, 7, 10, 1, 2, -1],
[10, 1, 2, 9, 5, 0, 5, 3, 0, 5, 7, 3, -1],
[8, 0, 2, 8, 2, 5, 8, 5, 7, 10, 5, 2, -1],
[2, 10, 5, 2, 5, 3, 3, 5, 7, -1],
[7, 9, 5, 7, 8, 9, 3, 11, 2, -1],
[9, 5, 7, 9, 7, 2, 9, 2, 0, 2, 7, 11, -1],
[2, 3, 11, 0, 1, 8, 1, 7, 8, 1, 5, 7, -1],
[11, 2, 1, 11, 1, 7, 7, 1, 5, -1],
[9, 5, 8, 8, 5, 7, 10, 1, 3, 10, 3, 11, -1],
[5, 7, 0, 5, 0, 9, 7, 11, 0, 1, 0, 10, 11, 10, 0, -1],
[11, 10, 0, 11, 0, 3, 10, 5, 0, 8, 0, 7, 5, 7, 0, -1],
[11, 10, 5, 7, 11, 5, -1],
[10, 6, 5, -1],
[0, 8, 3, 5, 10, 6, -1],
[9, 0, 1, 5, 10, 6, -1],
[1, 8, 3, 1, 9, 8, 5, 10, 6, -1],
[1, 6, 5, 2, 6, 1, -1],
[1, 6, 5, 1, 2, 6, 3, 0, 8, -1],
[9, 6, 5, 9, 0, 6, 0, 2, 6, -1],
[5, 9, 8, 5, 8, 2, 5, 2, 6, 3, 2, 8, -1],
[2, 3, 11, 10, 6, 5, -1],
[11, 0, 8, 11, 2, 0, 10, 6, 5, -1],
[0, 1, 9, 2, 3, 11, 5, 10, 6, -1],
[5, 10, 6, 1, 9, 2, 9, 11, 2, 9, 8, 11, -1],
[6, 3, 11, 6, 5, 3, 5, 1, 3, -1],
[0, 8, 11, 0, 11, 5, 0, 5, 1, 5, 11, 6, -1],
[3, 11, 6, 0, 3, 6, 0, 6, 5, 0, 5, 9, -1],
[6, 5, 9, 6, 9, 11, 11, 9, 8, -1],
[5, 10, 6, 4, 7, 8, -1],
[4, 3, 0, 4, 7, 3, 6, 5, 10, -1],
[1, 9, 0, 5, 10, 6, 8, 4, 7, -1],
[10, 6, 5, 1, 9, 7, 1, 7, 3, 7, 9, 4, -1],
[6, 1, 2, 6, 5, 1, 4, 7, 8, -1],
[1, 2, 5, 5, 2, 6, 3, 0, 4, 3, 4, 7, -1],
[8, 4, 7, 9, 0, 5, 0, 6, 5, 0, 2, 6, -1],
[7, 3, 9, 7, 9, 4, 3, 2, 9, 5, 9, 6, 2, 6, 9, -1],
[3, 11, 2, 7, 8, 4, 10, 6, 5, -1],
[5, 10, 6, 4, 7, 2, 4, 2, 0, 2, 7, 11, -1],
[0, 1, 9, 4, 7, 8, 2, 3, 11, 5, 10, 6, -1],
[9, 2, 1, 9, 11, 2, 9, 4, 11, 7, 11, 4, 5, 10, 6, -1],
[8, 4, 7, 3, 11, 5, 3, 5, 1, 5, 11, 6, -1],
[5, 1, 11, 5, 11, 6, 1, 0, 11, 7, 11, 4, 0, 4, 11, -1],
[0, 5, 9, 0, 6, 5, 0, 3, 6, 11, 6, 3, 8, 4, 7, -1],
[6, 5, 9, 6, 9, 11, 4, 7, 9, 7, 11, 9, -1],
[10, 4, 9, 6, 4, 10, -1],
[4, 10, 6, 4, 9, 10, 0, 8, 3, -1],
[10, 0, 1, 10, 6, 0, 6, 4, 0, -1],
[8, 3, 1, 8, 1, 6, 8, 6, 4, 6, 1, 10, -1],
[1, 4, 9, 1, 2, 4, 2, 6, 4, -1],
[3, 0, 8, 1, 2, 9, 2, 4, 9, 2, 6, 4, -1],
[0, 2, 4, 4, 2, 6, -1],
[8, 3, 2, 8, 2, 4, 4, 2, 6, -1],
[10, 4, 9, 10, 6, 4, 11, 2, 3, -1],
[0, 8, 2, 2, 8, 11, 4, 9, 10, 4, 10, 6, -1],
[3, 11, 2, 0, 1, 6, 0, 6, 4, 6, 1, 10, -1],
[6, 4, 1, 6, 1, 10, 4, 8, 1, 2, 1, 11, 8, 11, 1, -1],
[9, 6, 4, 9, 3, 6, 9, 1, 3, 11, 6, 3, -1],
[8, 11, 1, 8, 1, 0, 11, 6, 1, 9, 1, 4, 6, 4, 1, -1],
[3, 11, 6, 3, 6, 0, 0, 6, 4, -1],
[6, 4, 8, 11, 6, 8, -1],
[7, 10, 6, 7, 8, 10, 8, 9, 10, -1],
[0, 7, 3, 0, 10, 7, 0, 9, 10, 6, 7, 10, -1],
[10, 6, 7, 1, 10, 7, 1, 7, 8, 1, 8, 0, -1],
[10, 6, 7, 10, 7, 1, 1, 7, 3, -1],
[1, 2, 6, 1, 6, 8, 1, 8, 9, 8, 6, 7, -1],
[2, 6, 9, 2, 9, 1, 6, 7, 9, 0, 9, 3, 7, 3, 9, -1],
[7, 8, 0, 7, 0, 6, 6, 0, 2, -1],
[7, 3, 2, 6, 7, 2, -1],
[2, 3, 11, 10, 6, 8, 10, 8, 9, 8, 6, 7, -1],
[2, 0, 7, 2, 7, 11, 0, 9, 7, 6, 7, 10, 9, 10, 7, -1],
[1, 8, 0, 1, 7, 8, 1, 10, 7, 6, 7, 10, 2, 3, 11, -1],
[11, 2, 1, 11, 1, 7, 10, 6, 1, 6, 7, 1, -1],
[8, 9, 6, 8, 6, 7, 9, 1, 6, 11, 6, 3, 1, 3, 6, -1],
[0, 9, 1, 11, 6, 7, -1],
[7, 8, 0, 7, 0, 6, 3, 11, 0, 11, 6, 0, -1],
[7, 11, 6, -1],
[7, 6, 11, -1],
[3, 0, 8, 11, 7, 6, -1],
[0, 1, 9, 11, 7, 6, -1],
[8, 1, 9, 8, 3, 1, 11, 7, 6, -1],
[10, 1, 2, 6, 11, 7, -1],
[1, 2, 10, 3, 0, 8, 6, 11, 7, -1],
[2, 9, 0, 2, 10, 9, 6, 11, 7, -1],
[6, 11, 7, 2, 10, 3, 10, 8, 3, 10, 9, 8, -1],
[7, 2, 3, 6, 2, 7, -1],
[7, 0, 8, 7, 6, 0, 6, 2, 0, -1],
[2, 7, 6, 2, 3, 7, 0, 1, 9, -1],
[1, 6, 2, 1, 8, 6, 1, 9, 8, 8, 7, 6, -1],
[10, 7, 6, 10, 1, 7, 1, 3, 7, -1],
[10, 7, 6, 1, 7, 10, 1, 8, 7, 1, 0, 8, -1],
[0, 3, 7, 0, 7, 10, 0, 10, 9, 6, 10, 7, -1],
[7, 6, 10, 7, 10, 8, 8, 10, 9, -1],
[6, 8, 4, 11, 8, 6, -1],
[3, 6, 11, 3, 0, 6, 0, 4, 6, -1],
[8, 6, 11, 8, 4, 6, 9, 0, 1, -1],
[9, 4, 6, 9, 6, 3, 9, 3, 1, 11, 3, 6, -1],
[6, 8, 4, 6, 11, 8, 2, 10, 1, -1],
[1, 2, 10, 3, 0, 11, 0, 6, 11, 0, 4, 6, -1],
[4, 11, 8, 4, 6, 11, 0, 2, 9, 2, 10, 9, -1],
[10, 9, 3, 10, 3, 2, 9, 4, 3, 11, 3, 6, 4, 6, 3, -1],
[8, 2, 3, 8, 4, 2, 4, 6, 2, -1],
[0, 4, 2, 4, 6, 2, -1],
[1, 9, 0, 2, 3, 4, 2, 4, 6, 4, 3, 8, -1],
[1, 9, 4, 1, 4, 2, 2, 4, 6, -1],
[8, 1, 3, 8, 6, 1, 8, 4, 6, 6, 10, 1, -1],
[10, 1, 0, 10, 0, 6, 6, 0, 4, -1],
[4, 6, 3, 4, 3, 8, 6, 10, 3, 0, 3, 9, 10, 9, 3, -1],
[10, 9, 4, 6, 10, 4, -1],
[4, 9, 5, 7, 6, 11, -1],
[0, 8, 3, 4, 9, 5, 11, 7, 6, -1],
[5, 0, 1, 5, 4, 0, 7, 6, 11, -1],
[11, 7, 6, 8, 3, 4, 3, 5, 4, 3, 1, 5, -1],
[9, 5, 4, 10, 1, 2, 7, 6, 11, -1],
[6, 11, 7, 1, 2, 10, 0, 8, 3, 4, 9, 5, -1],
[7, 6, 11, 5, 4, 10, 4, 2, 10, 4, 0, 2, -1],
[3, 4, 8, 3, 5, 4, 3, 2, 5, 10, 5, 2, 11, 7, 6, -1],
[7, 2, 3, 7, 6, 2, 5, 4, 9, -1],
[9, 5, 4, 0, 8, 6, 0, 6, 2, 6, 8, 7, -1],
[3, 6, 2, 3, 7, 6, 1, 5, 0, 5, 4, 0, -1],
[6, 2, 8, 6, 8, 7, 2, 1, 8, 4, 8, 5, 1, 5, 8, -1],
[9, 5, 4, 10, 1, 6, 1, 7, 6, 1, 3, 7, -1],
[1, 6, 10, 1, 7, 6, 1, 0, 7, 8, 7, 0, 9, 5, 4, -1],
[4, 0, 10, 4, 10, 5, 0, 3, 10, 6, 10, 7, 3, 7, 10, -1],
[7, 6, 10, 7, 10, 8, 5, 4, 10, 4, 8, 10, -1],
[6, 9, 5, 6, 11, 9, 11, 8, 9, -1],
[3, 6, 11, 0, 6, 3, 0, 5, 6, 0, 9, 5, -1],
[0, 11, 8, 0, 5, 11, 0, 1, 5, 5, 6, 11, -1],
[6, 11, 3, 6, 3, 5, 5, 3, 1, -1],
[1, 2, 10, 9, 5, 11, 9, 11, 8, 11, 5, 6, -1],
[0, 11, 3, 0, 6, 11, 0, 9, 6, 5, 6, 9, 1, 2, 10, -1],
[11, 8, 5, 11, 5, 6, 8, 0, 5, 10, 5, 2, 0, 2, 5, -1],
[6, 11, 3, 6, 3, 5, 2, 10, 3, 10, 5, 3, -1],
[5, 8, 9, 5, 2, 8, 5, 6, 2, 3, 8, 2, -1],
[9, 5, 6, 9, 6, 0, 0, 6, 2, -1],
[1, 5, 8, 1, 8, 0, 5, 6, 8, 3, 8, 2, 6, 2, 8, -1],
[1, 5, 6, 2, 1, 6, -1],
[1, 3, 6, 1, 6, 10, 3, 8, 6, 5, 6, 9, 8, 9, 6, -1],
[10, 1, 0, 10, 0, 6, 9, 5, 0, 5, 6, 0, -1],
[0, 3, 8, 5, 6, 10, -1],
[10, 5, 6, -1],
[11, 5, 10, 7, 5, 11, -1],
[11, 5, 10, 11, 7, 5, 8, 3, 0, -1],
[5, 11, 7, 5, 10, 11, 1, 9, 0, -1],
[10, 7, 5, 10, 11, 7, 9, 8, 1, 8, 3, 1, -1],
[11, 1, 2, 11, 7, 1, 7, 5, 1, -1],
[0, 8, 3, 1, 2, 7, 1, 7, 5, 7, 2, 11, -1],
[9, 7, 5, 9, 2, 7, 9, 0, 2, 2, 11, 7, -1],
[7, 5, 2, 7, 2, 11, 5, 9, 2, 3, 2, 8, 9, 8, 2, -1],
[2, 5, 10, 2, 3, 5, 3, 7, 5, -1],
[8, 2, 0, 8, 5, 2, 8, 7, 5, 10, 2, 5, -1],
[9, 0, 1, 5, 10, 3, 5, 3, 7, 3, 10, 2, -1],
[9, 8, 2, 9, 2, 1, 8, 7, 2, 10, 2, 5, 7, 5, 2, -1],
[1, 3, 5, 3, 7, 5, -1],
[0, 8, 7, 0, 7, 1, 1, 7, 5, -1],
[9, 0, 3, 9, 3, 5, 5, 3, 7, -1],
[9, 8, 7, 5, 9, 7, -1],
[5, 8, 4, 5, 10, 8, 10, 11, 8, -1],
[5, 0, 4, 5, 11, 0, 5, 10, 11, 11, 3, 0, -1],
[0, 1, 9, 8, 4, 10, 8, 10, 11, 10, 4, 5, -1],
[10, 11, 4, 10, 4, 5, 11, 3, 4, 9, 4, 1, 3, 1, 4, -1],
[2, 5, 1, 2, 8, 5, 2, 11, 8, 4, 5, 8, -1],
[0, 4, 11, 0, 11, 3, 4, 5, 11, 2, 11, 1, 5, 1, 11, -1],
[0, 2, 5, 0, 5, 9, 2, 11, 5, 4, 5, 8, 11, 8, 5, -1],
[9, 4, 5, 2, 11, 3, -1],
[2, 5, 10, 3, 5, 2, 3, 4, 5, 3, 8, 4, -1],
[5, 10, 2, 5, 2, 4, 4, 2, 0, -1],
[3, 10, 2, 3, 5, 10, 3, 8, 5, 4, 5, 8, 0, 1, 9, -1],
[5, 10, 2, 5, 2, 4, 1, 9, 2, 9, 4, 2, -1],
[8, 4, 5, 8, 5, 3, 3, 5, 1, -1],
[0, 4, 5, 1, 0, 5, -1],
[8, 4, 5, 8, 5, 3, 9, 0, 5, 0, 3, 5, -1],
[9, 4, 5, -1],
[4, 11, 7, 4, 9, 11, 9, 10, 11, -1],
[0, 8, 3, 4, 9, 7, 9, 11, 7, 9, 10, 11, -1],
[1, 10, 11, 1, 11, 4, 1, 4, 0, 7, 4, 11, -1],
[3, 1, 4, 3, 4, 8, 1, 10, 4, 7, 4, 11, 10, 11, 4, -1],
[4, 11, 7, 9, 11, 4, 9, 2, 11, 9, 1, 2, -1],
[9, 7, 4, 9, 11, 7, 9, 1, 11, 2, 11, 1, 0, 8, 3, -1],
[11, 7, 4, 11, 4, 2, 2, 4, 0, -1],
[11, 7, 4, 11, 4, 2, 8, 3, 4, 3, 2, 4, -1],
[2, 9, 10, 2, 7, 9, 2, 3, 7, 7, 4, 9, -1],
[9, 10, 7, 9, 7, 4, 10, 2, 7, 8, 7, 0, 2, 0, 7, -1],
[3, 7, 10, 3, 10, 2, 7, 4, 10, 1, 10, 0, 4, 0, 10, -1],
[1, 10, 2, 8, 7, 4, -1],
[4, 9, 1, 4, 1, 7, 7, 1, 3, -1],
[4, 9, 1, 4, 1, 7, 0, 8, 1, 8, 7, 1, -1],
[4, 0, 3, 7, 4, 3, -1],
[4, 8, 7, -1],
[9, 10, 8, 10, 11, 8, -1],
[3, 0, 9, 3, 9, 11, 11, 9, 10, -1],
[0, 1, 10, 0, 10, 8, 8, 10, 11, -1],
[3, 1, 10, 11, 3, 10, -1],
[1, 2, 11, 1, 11, 9, 9, 11, 8, -1],
[3, 0, 9, 3, 9, 11, 1, 2, 9, 2, 11, 9, -1],
[0, 2, 11, 8, 0, 11, -1],
[3, 2, 11, -1],
[2, 3, 8, 2, 8, 10, 10, 8, 9, -1],
[9, 10, 2, 0, 9, 2, -1],
[2, 3, 8, 2, 8, 10, 0, 1, 8, 1, 10, 8, -1],
[1, 10, 2, -1],
[1, 3, 8, 9, 1, 8, -1],
[0, 9, 1, -1],
[0, 3, 8, -1],
[-1]
]