Winged-Edge Mesh

Math essence

For each triangle (v0, v1, v2), three directed edges e0=(v0,v1), e1=(v1,v2), e2=(v2,v0). For each edge, find the opposite edge in the adjacent triangle (if any) and link them. Vertex normals: average the cross products of the two outgoing edges of every face incident to the vertex. Subdivide: each triangle becomes 4 by inserting midpoint vertices on each edge (new vertex position = (v_a + v_b) / 2 for non-shared edges, or Loop-weighted blend for shared ones). The data structure supports O(1) vertex-to-face and face-to-edge traversal.

Parameters

Reference

First 60 lines of reference.py. Full source: library_external/toxi_toxiclibs/WingedEdgeMesh/reference.py

"""WingedEdgeMesh — half-edge / winged-edge data structure for triangle meshes.

A pure-numpy port of Karsten Schmidt's toxiclibs.geom.WingedEdge (2010)
https://web.archive.org/web/2011/http://toxiclibs.org/2010/08/wingededge-mesh/

Each directed edge stores:
  * `v_from`, `v_to`           — its two endpoint vertices
  * `opp_a`, `opp_b`            — the 'wings' (the two opposite edges,
                                  one in each of the two incident faces)
  * `f_left`, `f_right`         — the two incident triangle faces

This lets you traverse from edge to edge in O(1) and compute vertex
normals by averaging the cross products of outgoing edges.

The original 2010 Karsten demo included a Catmull-Clark style
subdivision pass; this port uses Loop subdivision (the variant
for triangle meshes) and a 3D Perlin-style displacement field.
"""
from __future__ import annotations

from dataclasses import dataclass

import numpy as np


@dataclass
class _Edge:
    v_from: int
    v_to: int
    f_left: int
    opp_a: int = -1
    f_right: int = -1
    opp_b: int = -1
    # The reverse-direction edge (used internally during build)
    twin_idx: int = -1


def _build_platonic(name: str):
    """Return (V, F) for a base platonic solid."""
    if name == 'tetrahedron':
        V = np.array([
            [1, 1, 1], [-1, -1, 1], [-1, 1, -1], [1, -1, -1],
        ], dtype=np.float32) * 0.8
        F = np.array([[0, 1, 2], [0, 3, 1], [0, 2, 3], [1, 3, 2]], dtype=np.int32)
    elif name == 'cube':
        V = np.array([
            [-1, -1, -1], [1, -1, -1], [1, 1, -1], [-1, 1, -1],
            [-1, -1, 1], [1, -1, 1], [1, 1, 1], [-1, 1, 1],
        ], dtype=np.float32)
        F = np.array([
            [0, 1, 2], [0, 2, 3], [4, 6, 5], [4, 7, 6],
            [0, 4, 5], [0, 5, 1], [2, 6, 7], [2, 7, 3],
            [1, 5, 6], [1, 6, 2], [0, 3, 7], [0, 7, 4],
        ], dtype=np.int32)
    elif name == 'octahedron':
        V = np.array([
            [1, 0, 0], [-1, 0, 0], [0, 1, 0], [0, -1, 0], [0, 0, 1], [0, 0, -1],
        ], dtype=np.float32)
        F = np.array([
            [0, 2, 4], [2, 1, 4], [1, 3, 4], [3, 0, 4],