"""Genesis engine: lightweight geometry, graph and procedural generators.
This module provides a compact but useful set of utilities for 2D vector
math, simple graph and triangular-mesh representations, an L-system based
generator for procedural structures, and tiny IO/export helpers (OBJ/JSON).
The code is dependency-free (only Python stdlib) and intended to be safe to
add to the repository as a self-contained demonstration of geometry and
generation primitives.
Key pieces:
- Vector2D: small 2D vector helper
- Graph: node/edge graph with simple layout support
- Mesh: triangular mesh builder and simple Delaunay-like splitter (not
production-grade but useful for small demos)
- LSystem: compact L-system interpreter for procedural geometry
- exporters: write OBJ and JSON representations
The module includes a small CLI demo when executed directly.
"""
from __future__ import annotations
import json
import math
import random
from dataclasses import dataclass, field
from typing import Dict, Iterable, List, Optional, Sequence, Tuple
##########################
# Vector utilities
##########################
@dataclass(frozen=True)
class Vector2D:
x: float
y: float
def __add__(self, other: Vector2D) -> Vector2D:
return Vector2D(self.x + other.x, self.y + other.y)
def __sub__(self, other: Vector2D) -> Vector2D:
return Vector2D(self.x - other.x, self.y - other.y)
def __mul__(self, s: float) -> Vector2D:
return Vector2D(self.x * s, self.y * s)
def dot(self, other: Vector2D) -> float:
return self.x * other.x + self.y * other.y
def cross(self, other: Vector2D) -> float:
return self.x * other.y - self.y * other.x
def length(self) -> float:
return math.hypot(self.x, self.y)
def normalized(self) -> Vector2D:
l = self.length()
if l == 0:
return Vector2D(0.0, 0.0)
return Vector2D(self.x / l, self.y / l)
def rotate(self, ang_rad: float) -> Vector2D:
c = math.cos(ang_rad)
s = math.sin(ang_rad)
return Vector2D(self.x * c - self.y * s, self.x * s + self.y * c)
def tuple(self) -> Tuple[float, float]:
return (self.x, self.y)
def polygon_area(points: Sequence[Vector2D]) -> float:
if len(points) < 3:
return 0.0
a = 0.0
for i in range(len(points)):
x1, y1 = points[i].tuple()
x2, y2 = points[(i + 1) % len(points)].tuple()
a += x1 * y2 - y1 * x2
return 0.5 * abs(a)
def centroid(points: Sequence[Vector2D]) -> Vector2D:
if not points:
return Vector2D(0.0, 0.0)
sx = sum(p.x for p in points)
sy = sum(p.y for p in points)
n = len(points)
return Vector2D(sx / n, sy / n)
##########################
# Graph primitives
##########################
@dataclass
class Node:
id: int
pos: Vector2D
data: dict = field(default_factory=dict)
@dataclass
class Edge:
a: int
b: int
weight: float = 1.0
class Graph:
"""Simple undirected graph with node positions for layout and export."""
def __init__(self) -> None:
self._nodes: Dict[int, Node] = {}
self._edges: List[Edge] = []
self._next_id = 1
def add_node(self, pos: Vector2D, data: Optional[dict] = None) -> int:
nid = self._next_id
self._next_id += 1
self._nodes[nid] = Node(id=nid, pos=pos, data=data or {})
return nid
def add_edge(self, a: int, b: int, weight: float = 1.0) -> None:
if a not in self._nodes or b not in self._nodes:
raise KeyError("both nodes must exist to add an edge")
self._edges.append(Edge(a=a, b=b, weight=weight))
def nodes(self) -> Iterable[Node]:
return list(self._nodes.values())
def edges(self) -> Iterable[Edge]:
return list(self._edges)
def to_dict(self) -> dict:
return {
"nodes": [{"id": n.id, "pos": n.pos.tuple(), "data": n.data} for n in self.nodes()],
"edges": [{"a": e.a, "b": e.b, "weight": e.weight} for e in self.edges()],
}
def bounding_box(self) -> Tuple[Vector2D, Vector2D]:
pts = [n.pos for n in self.nodes()]
if not pts:
return Vector2D(0, 0), Vector2D(0, 0)
minx = min(p.x for p in pts)
miny = min(p.y for p in pts)
maxx = max(p.x for p in pts)
maxy = max(p.y for p in pts)
return Vector2D(minx, miny), Vector2D(maxx, maxy)
def random_layout(self, seed: Optional[int] = None, scale: float = 1.0) -> None:
if seed is not None:
random.seed(seed)
for n in self._nodes.values():
n.pos = Vector2D((random.random() - 0.5) * scale, (random.random() - 0.5) * scale)
def radial_layout(self, center: Optional[Vector2D] = None, radius: float = 1.0) -> None:
nodes = list(self._nodes.values())
if not nodes:
return
if center is None:
center = centroid([n.pos for n in nodes])
n = len(nodes)
for i, node in enumerate(nodes):
ang = 2 * math.pi * (i / max(1, n))
node.pos = Vector2D(center.x + math.cos(ang) * radius, center.y + math.sin(ang) * radius)
##########################
# Mesh primitives
##########################
@dataclass
class Triangle:
a: int
b: int
c: int
class Mesh:
"""A tiny triangular mesh container (indexed vertices + triangles).
This is intentionally minimal: utility methods to add points/triangles and
to export to OBJ. It also contains a simple ear-clipping polygon triangulator
for simple polygons.
"""
def __init__(self) -> None:
self.vertices: List[Vector2D] = []
self.triangles: List[Triangle] = []
def add_vertex(self, p: Vector2D) -> int:
self.vertices.append(p)
return len(self.vertices) - 1
def add_triangle(self, a: int, b: int, c: int) -> None:
self.triangles.append(Triangle(a, b, c))
def to_obj(self) -> str:
lines: List[str] = []
for v in self.vertices:
lines.append(f"v {v.x:.6f} {v.y:.6f} 0.0")
for t in self.triangles:
# OBJ indices are 1-based
lines.append(f"f {t.a + 1} {t.b + 1} {t.c + 1}")
return "\n".join(lines)
def from_polygon_earclip(self, poly: Sequence[Vector2D]) -> None:
"""Triangulate a simple polygon using ear clipping. Returns triangles in place.
Not suitable for complex, self-intersecting polygons. Intended for demos.
"""
pts = [Vector2D(p.x, p.y) for p in poly]
n = len(pts)
if n < 3:
return
# We'll append the polygon vertices to the mesh; remember base index
base_index = len(self.vertices)
for p in pts:
self.add_vertex(p)
idx = list(range(n))
# helper to check if vertex i is an ear (using polygon-local indices)
def is_convex(i0, i1, i2) -> bool:
a = pts[i0]
b = pts[i1]
c = pts[i2]
# positive cross indicates counter-clockwise (convex for CCW polygons)
return (b - a).cross(c - b) > 0
def point_in_triangle(pt: Vector2D, a: Vector2D, b: Vector2D, c: Vector2D) -> bool:
# barycentric technique
v0 = c - a
v1 = b - a
v2 = pt - a
dot00 = v0.dot(v0)
dot01 = v0.dot(v1)
dot02 = v0.dot(v2)
dot11 = v1.dot(v1)
dot12 = v1.dot(v2)
denom = dot00 * dot11 - dot01 * dot01
if denom == 0:
return False
u = (dot11 * dot02 - dot01 * dot12) / denom
v = (dot00 * dot12 - dot01 * dot02) / denom
return u >= 0 and v >= 0 and (u + v) <= 1
# Ear clipping main loop
while len(idx) > 3:
ear_found = False
for k in range(len(idx)):
i_prev = idx[(k - 1) % len(idx)]
i_curr = idx[k]
i_next = idx[(k + 1) % len(idx)]
if not is_convex(i_prev, i_curr, i_next):
continue
a = pts[i_prev]
b = pts[i_curr]
c = pts[i_next]
# ensure no other point is inside triangle
any_inside = False
for j in idx:
if j in (i_prev, i_curr, i_next):
continue
if point_in_triangle(pts[j], a, b, c):
any_inside = True
break
if any_inside:
continue
# record triangle (indices offset by base_index)
self.add_triangle(base_index + i_prev, base_index + i_curr, base_index + i_next)
# remove ear vertex from polygon index list
idx.pop(k)
ear_found = True
break
if not ear_found:
# fallback: stop to avoid infinite loop on degenerate polygons
break
# final triangle
if len(idx) == 3:
self.add_triangle(base_index + idx[0], base_index + idx[1], base_index + idx[2])
##########################
# L-system / procedural generator
##########################
class LSystem:
"""A very small L-system interpreter.
The LSystem applies one-step symbol rewriting using provided rules, then
optionally interprets the final string into 2D turtle geometry commands.
Supported turtle commands in the interpreter:
- F: move forward and draw
- f: move forward without drawing
- +: turn right by angle
- -: turn left by angle
- [: push state
- ]: pop state
The interpreter returns a list of line segments (pairs of Vector2D).
"""
def __init__(self, axiom: str, rules: Dict[str, str]):
self.axiom = axiom
self.rules = rules
def generate(self, iterations: int) -> str:
s = self.axiom
for _ in range(max(0, iterations)):
out = []
for ch in s:
out.append(self.rules.get(ch, ch))
s = "".join(out)
return s
def interpret_turtle(self, program: str, step: float = 1.0, angle_deg: float = 25.0) -> List[Tuple[Vector2D, Vector2D]]:
angle_rad = math.radians(angle_deg)
pos = Vector2D(0.0, 0.0)
dir_vec = Vector2D(0.0, 1.0)
stack: List[Tuple[Vector2D, Vector2D]] = []
segments: List[Tuple[Vector2D, Vector2D]] = []
for ch in program:
if ch == "F":
new_pos = pos + dir_vec * step
segments.append((pos, new_pos))
pos = new_pos
elif ch == "f":
pos = pos + dir_vec * step
elif ch == "+":
dir_vec = dir_vec.rotate(-angle_rad) # right turn
elif ch == "-":
dir_vec = dir_vec.rotate(angle_rad) # left turn
elif ch == "[":
stack.append((pos, dir_vec))
elif ch == "]":
if stack:
pos, dir_vec = stack.pop()
else:
# ignore unknown symbols
pass
return segments
##########################
# Small helpers / exporters
##########################
def export_graph_json(graph: Graph, path: str) -> None:
with open(path, "w", encoding="utf-8") as fh:
json.dump(graph.to_dict(), fh, indent=2)
def export_mesh_obj(mesh: Mesh, path: str) -> None:
with open(path, "w", encoding="utf-8") as fh:
fh.write(mesh.to_obj())
##########################
# Example high-level generators
##########################
def random_point_cloud(n: int, radius: float = 1.0, seed: Optional[int] = None) -> List[Vector2D]:
if seed is not None:
random.seed(seed)
pts = [Vector2D((random.random() - 0.5) * 2 * radius, (random.random() - 0.5) * 2 * radius) for _ in range(n)]
return pts
def make_grid_graph(rows: int, cols: int, spacing: float = 1.0) -> Graph:
g = Graph()
ids = []
for r in range(rows):
row_ids = []
for c in range(cols):
nid = g.add_node(Vector2D(c * spacing, r * spacing))
row_ids.append(nid)
ids.append(row_ids)
for r in range(rows):
for c in range(cols):
if c + 1 < cols:
g.add_edge(ids[r][c], ids[r][c + 1])
if r + 1 < rows:
g.add_edge(ids[r][c], ids[r + 1][c])
return g
def polygon_to_mesh(poly: Sequence[Vector2D]) -> Mesh:
m = Mesh()
m.from_polygon_earclip(poly)
return m
##########################
# CLI demo and small smoke test
##########################
def demo_lsystem_tree(iterations: int = 4, step: float = 1.0, angle: float = 25.0) -> Mesh:
# A simple plant-like L-system (Algae-like variant)
rules = {
"X": "F-[[X]+X]+F[+FX]-X",
"F": "FF",
}
ls = LSystem(axiom="X", rules=rules)
prog = ls.generate(iterations)
segs = ls.interpret_turtle(prog, step=step, angle_deg=angle)
# Build a mesh by creating thin rectangles for segments (crude)
mesh = Mesh()
# For each segment create two vertices offset perpendicular to the segment
for a, b in segs:
v = b - a
n = Vector2D(-v.y, v.x).normalized() * (step * 0.1)
ia = mesh.add_vertex(a + n)
ib = mesh.add_vertex(a - n)
ic = mesh.add_vertex(b + n)
id = mesh.add_vertex(b - n)
# two triangles
mesh.add_triangle(ia, ib, ic)
mesh.add_triangle(ib, id, ic)
return mesh
def demo_pipeline() -> None:
print("Genesis engine demo:\n")
print("- Generating grid graph 4x4")
g = make_grid_graph(4, 4, spacing=1.0)
print(f" nodes: {len(list(g.nodes()))}, edges: {len(list(g.edges()))}")
print("- Generating random polygon and triangulating via ear clipping")
poly = [Vector2D(math.cos(a) * (1 + 0.3 * math.sin(3 * a)), math.sin(a) * (1 + 0.3 * math.cos(5 * a))) for a in [i * 2 * math.pi / 12 for i in range(12)]]
m = polygon_to_mesh(poly)
print(f" mesh vertices: {len(m.vertices)}, triangles: {len(m.triangles)}")
print("- Generating L-system tree and exporting OBJ sample (in-memory)")
tree_mesh = demo_lsystem_tree(iterations=3, step=0.6, angle=22.5)
print(f" tree mesh vertices: {len(tree_mesh.vertices)}, triangles: {len(tree_mesh.triangles)}")
# show small metrics
area = polygon_area(poly)
print(f"- sample polygon area: {area:.4f}")
if __name__ == "__main__":
# Simple smoke-run to verify nothing crashes
demo_pipeline()
##########################
# Additional utilities
##########################
class GridIndex:
"""Simple spatial hash / grid index for 2D points.
Useful for small-to-medium point sets where we need fast nearest
or radius queries without external dependencies.
"""
def __init__(self, cell_size: float = 1.0):
self.cell_size = float(cell_size)
self._cells: Dict[Tuple[int, int], List[int]] = {}
self._points: List[Vector2D] = []
def _cell(self, p: Vector2D) -> Tuple[int, int]:
return (int(math.floor(p.x / self.cell_size)), int(math.floor(p.y / self.cell_size)))
def insert(self, p: Vector2D) -> int:
idx = len(self._points)
self._points.append(p)
key = self._cell(p)
self._cells.setdefault(key, []).append(idx)
return idx
def radius_query(self, p: Vector2D, r: float) -> List[Tuple[int, Vector2D]]:
r = float(r)
cx, cy = self._cell(p)
delta = int(math.ceil(r / self.cell_size))
out: List[Tuple[int, Vector2D]] = []
for dx in range(-delta, delta + 1):
for dy in range(-delta, delta + 1):
for idx in self._cells.get((cx + dx, cy + dy), []):
pt = self._points[idx]
if (pt - p).length() <= r:
out.append((idx, pt))
return out
def poisson_disc_samples(radius: float, domain: Tuple[float, float, float, float], k: int = 30, seed: Optional[int] = None) -> List[Vector2D]:
"""Bridson's Poisson-disc sampling in a rectangular domain.
domain: (xmin, ymin, xmax, ymax)
"""
if seed is not None:
random.seed(seed)
xmin, ymin, xmax, ymax = domain
width = xmax - xmin
height = ymax - ymin
cell_size = radius / math.sqrt(2)
grid_w = int(math.ceil(width / cell_size))
grid_h = int(math.ceil(height / cell_size))
grid: List[List[Optional[int]]] = [[None] * grid_h for _ in range(grid_w)]
def to_grid(p: Vector2D) -> Tuple[int, int]:
gx = int((p.x - xmin) / cell_size)
gy = int((p.y - ymin) / cell_size)
return gx, gy
samples: List[Vector2D] = []
active: List[int] = []
# first sample
first = Vector2D(xmin + random.random() * width, ymin + random.random() * height)
samples.append(first)
gx, gy = to_grid(first)
grid[gx][gy] = 0
active.append(0)
while active:
idx = active[int(random.random() * len(active))]
base = samples[idx]
found = False
for _ in range(k):
r = random.uniform(radius, 2 * radius)
theta = random.random() * 2 * math.pi
cand = Vector2D(base.x + r * math.cos(theta), base.y + r * math.sin(theta))
if not (xmin <= cand.x <= xmax and ymin <= cand.y <= ymax):
continue
cgx, cgy = to_grid(cand)
ok = True
for i in range(max(0, cgx - 2), min(grid_w, cgx + 3)):
for j in range(max(0, cgy - 2), min(grid_h, cgy + 3)):
sidx = grid[i][j]
if sidx is None:
continue
if (samples[sidx] - cand).length() < radius:
ok = False
break
if not ok:
break
if ok:
samples.append(cand)
grid[cgx][cgy] = len(samples) - 1
active.append(len(samples) - 1)
found = True
break
if not found:
active.remove(idx)
return samples
def refine_mesh(mesh: Mesh, max_edge_length: float) -> Mesh:
"""Refine mesh by subdividing triangles that contain edges longer than max_edge_length.
This performs a single-pass refinement (one subdivision iteration). It's
intentionally simple and deterministic for demo purposes.
"""
new = Mesh()
# copy existing vertices
for v in mesh.vertices:
new.add_vertex(Vector2D(v.x, v.y))
def mid(a: int, b: int) -> int:
va = new.vertices[a]
vb = new.vertices[b]
mpt = Vector2D((va.x + vb.x) * 0.5, (va.y + vb.y) * 0.5)
return new.add_vertex(mpt)
for tri in mesh.triangles:
a, b, c = tri.a, tri.b, tri.c
va = mesh.vertices[a]
vb = mesh.vertices[b]
vc = mesh.vertices[c]
dab = (va - vb).length()
dbc = (vb - vc).length()
dca = (vc - va).length()
if dab <= max_edge_length and dbc <= max_edge_length and dca <= max_edge_length:
new.add_triangle(a, b, c)
continue
# split edges where needed, create midpoints
mab = mid(a, b) if dab > max_edge_length else -1
mbc = mid(b, c) if dbc > max_edge_length else -1
mca = mid(c, a) if dca > max_edge_length else -1
# simple cases: if all three edges split -> 4 new triangles
if mab != -1 and mbc != -1 and mca != -1:
new.add_triangle(a, mab, mca)
new.add_triangle(mab, b, mbc)
new.add_triangle(mca, mbc, c)
new.add_triangle(mab, mbc, mca)
else:
# fallback: if only one edge split, replace by two triangles
if mab != -1 and mbc == -1 and mca == -1:
new.add_triangle(a, mab, c)
new.add_triangle(mab, b, c)
elif mbc != -1 and mab == -1 and mca == -1:
new.add_triangle(b, mbc, a)
new.add_triangle(mbc, c, a)
elif mca != -1 and mab == -1 and mbc == -1:
new.add_triangle(c, mca, b)
new.add_triangle(mca, a, b)
else:
# mixed or two splits: attempt a conservative split by adding original triangle
new.add_triangle(a, b, c)
return new
def laplacian_smooth(mesh: Mesh, iterations: int = 1, lam: float = 0.5) -> None:
"""In-place Laplacian smoothing of vertex positions.
lam in (0,1) controls the amount of smoothing per iteration.
"""
if not mesh.vertices:
return
# build adjacency
adj: List[set] = [set() for _ in mesh.vertices]
for t in mesh.triangles:
adj[t.a].update([t.b, t.c])
adj[t.b].update([t.a, t.c])
adj[t.c].update([t.a, t.b])
for _ in range(max(0, iterations)):
new_positions: List[Vector2D] = [v for v in mesh.vertices]
for i, v in enumerate(mesh.vertices):
neighbors = adj[i]
if not neighbors:
continue
sx = sum(mesh.vertices[j].x for j in neighbors) / len(neighbors)
sy = sum(mesh.vertices[j].y for j in neighbors) / len(neighbors)
new_positions[i] = Vector2D(v.x + lam * (sx - v.x), v.y + lam * (sy - v.y))
mesh.vertices = new_positions
def export_mesh_svg(mesh: Mesh, path: str, scale: float = 100.0, margin: float = 10.0) -> None:
"""Export mesh to a simple SVG file (triangles stroked).
This is a convenience for quick visual checks; it writes a minimal SVG.
"""
if not mesh.vertices:
with open(path, "w", encoding="utf-8") as fh:
fh.write("")
return
xs = [v.x for v in mesh.vertices]
ys = [v.y for v in mesh.vertices]
minx, miny, maxx, maxy = min(xs), min(ys), max(xs), max(ys)
w = (maxx - minx) * scale + 2 * margin
h = (maxy - miny) * scale + 2 * margin
def to_xy(v: Vector2D) -> Tuple[float, float]:
return ((v.x - minx) * scale + margin, (maxy - v.y) * scale + margin)
lines: List[str] = []
lines.append(f"")
with open(path, "w", encoding="utf-8") as fh:
fh.write("\n".join(lines))
## small additional smoke-run to exercise new utilities when run directly
if __name__ == "__main__":
# generate Poisson-disc samples inside unit square
pts = poisson_disc_samples(0.08, (0.0, 0.0, 1.0, 1.0), seed=42)
print(f"Poisson samples generated: {len(pts)}")
# build a mesh from a regular polygon and refine it
poly = [Vector2D(math.cos(a), math.sin(a)) for a in [i * 2 * math.pi / 8 for i in range(8)]]
m = polygon_to_mesh(poly)
print(f"Original mesh: v={len(m.vertices)}, t={len(m.triangles)}")
m2 = refine_mesh(m, max_edge_length=0.8)
print(f"Refined mesh: v={len(m2.vertices)}, t={len(m2.triangles)}")
laplacian_smooth(m2, iterations=2, lam=0.4)
# export SVG to temporary file for quick visual check (file path safe to overwrite)
try:
export_mesh_svg(m2, "genesis_sample.svg")
print("Exported genesis_sample.svg")
except Exception:
# ignore filesystem errors in restricted environments
pass