163 Implementing a Triangulated Mesh

Predica schemas describe types, attributes, cardinalities, keys, and constraints. They do not say that every entity must become a separately allocated object or that every relationship must become a memory pointer. A triangulated mesh illustrates why that distinction matters.

Mesh algorithms commonly process millions of vertices and triangles. A representation made from one heap allocation per vertex, triangle, and edge would have substantial allocation overhead and poor cache locality. A Predica compiler is free to use dense arrays and compact integer indices instead.

Logical schema

value Point3
{
    Float32 x;
    Float32 y;
    Float32 z;
}

entity Vertex
{
    Integer id;
    Point3 position;
    key {id};
}

entity Triangle
{
    Integer id;
    List<Vertex> vertex;
    key {id};

    constraints
    {
        vertex.length = 3;
    }
}

entity Mesh
{
    Vertex vertex*;
    Triangle triangle*;
}

The schema says that every triangle has an ordered list of exactly three vertices and that vertices and triangles have logical keys. The list order defines the triangle orientation needed by normal and half-edge algorithms. The schema does not prescribe OIDs, pointers, heap allocation, a half-edge structure, or a particular order of triangles in memory.

Dense indexed representation

For a mesh stored and processed as one unit, the compiler can assign each vertex a dense slot number. A triangle then stores three 32-bit slot numbers:

using VertexIndex = uint32_t;

struct Point3f
{
    float x;
    float y;
    float z;
};

struct MeshData
{
    vector<Point3f> position;
    vector<array<VertexIndex, 3>> triangleVertex;
};

position
    0 ── (x₀, y₀, z₀)
    1 ── (x₁, y₁, z₁)
    2 ── (x₂, y₂, z₂)
    3 ── (x₃, y₃, z₃)

triangleVertex
    0 ── [0, 1, 2]
    1 ── [2, 1, 3]

The VertexIndex values are not persistent pointers. They are compact local indices interpreted relative to the containing mesh representation. If Vertex.id values are already dense they can equal the slot numbers. Otherwise, loading or constructing the mesh creates a map from logical vertex keys to dense slots. Serialisation can record the logical keys alongside the positions when they must remain externally visible.

A mesh of up to roughly four billion vertices can use 32-bit indices even when the surrounding persistent object store uses 64-bit OIDs. One OID can name the coarser serialised mesh object; its internal strings, vectors, vertices, and triangles are encoded inside that object's byte sequence.

Structure of arrays

Some algorithms use only one coordinate or stream coordinates into vector or GPU operations. The same logical Point3 values can be lowered into a structure-of-arrays representation:

struct MeshData
{
    vector<float> positionX;
    vector<float> positionY;
    vector<float> positionZ;

    vector<VertexIndex> triangleVertex0;
    vector<VertexIndex> triangleVertex1;
    vector<VertexIndex> triangleVertex2;
};

Array-of-structures and structure-of-arrays layouts implement the same Predica schema. The choice depends on vectorisation, GPU transfer, compression, and which fields an algorithm reads together.

Sequential triangle algorithms

Computing a normal for every triangle is a sequential pass over the triangle arrays. For each triangle the implementation performs three indexed loads from the position arrays:

for (auto v : mesh.triangleVertex)
{
    Point3f a = mesh.position[v[0]];
    Point3f b = mesh.position[v[1]];
    Point3f c = mesh.position[v[2]];
    normal.push_back(cross(b - a, c - a));
}

There are no heap objects to traverse and no edge labels to interpret. Triangles are read sequentially, vertex records are compact, and adjacent triangles often reuse positions already present in a processor cache. The logical path mesh.triangle.vertex.position has been compiled into array and index operations.

Derived adjacency indexes

The triangle representation directly supports triangle-to-vertex navigation. Algorithms that repeatedly navigate from a vertex to its incident triangles benefit from an additional physical index. A compressed sparse row representation stores all incident triangle indices in one array:

struct VertexTriangleAdjacency
{
    // Incident triangles for vertex v occupy
    // triangle[first[v] ... first[v + 1]).
    vector<uint32_t> first;
    vector<uint32_t> triangle;
};

first:     [0, 1, 3, 5, 6]
triangle:  [0, 0, 1, 0, 1, 1]

vertex 2 incident triangles = triangle[3 ... 5) = [0, 1]

This index is analogous to materialising an inverse relationship. It consumes storage and must be rebuilt or maintained when topology changes, but it permits compact sequential access without allocating a vector object for every vertex. It is derived physical state rather than another source of logical facts.

Half-edge navigation without pointers

Algorithms that walk around faces or across neighbouring faces often use a half-edge representation. That representation also need not contain pointers. With three half-edges per triangle, a half-edge can be identified by 3 * triangleIndex + corner:

using HalfEdgeIndex = uint32_t;
const HalfEdgeIndex noHalfEdge = UINT32_MAX;

struct HalfEdgeData
{
    vector<VertexIndex> origin;
    vector<HalfEdgeIndex> opposite;
};

The next half-edge around a triangle is calculated arithmetically. The opposite array gives the half-edge across the same undirected edge, or noHalfEdge at a boundary. Face, corner, origin, next, and opposite navigation therefore use integer arithmetic and indexed array loads.

This demonstrates an important physical-independence property. The logical schema contains vertices and triangles, while a particular algorithm may use a generated half-edge working representation. The compiler or library can build it transiently, cache it as derived state, or serialise it when the workload justifies the update cost.

Persistence granularity

A moderate mesh can be one persistent object containing its vectors. Reading its OID returns one byte sequence from which the dense arrays are deserialised. This is much coarser than assigning an OID to every vertex and triangle.

A mesh too large to read or rewrite as one object can be divided into spatial tiles or fixed-size blocks. The top-level mesh record then contains OIDs for those blocks, while vertices and triangles inside each block still use compact local indices. Boundary tables translate the comparatively small number of cross-block references.

Mesh OID
├── block OID 1 → dense local arrays
├── block OID 2 → dense local arrays
└── block OID 3 → dense local arrays

The persistent boundary is chosen from I/O size, update locality, and the algorithms applied to the mesh. It is not determined by the number of entity values in the logical schema.

Contrast with pointer chasing and relational joins

A generic object-graph implementation might allocate every vertex and triangle separately and store three pointers in each triangle. A direct mapping into an unnested relational schema might use Vertex, Triangle, and TriangleVertex relations and reconstruct triangle vertices with joins. Both are possible implementations of the logical information, but neither is the natural high-performance representation for typical mesh algorithms.

Dense arrays avoid allocation headers, improve cache density, support vectorisation, and make topology suitable for GPU transfer. They also show why Predica navigation should not be equated with pointer chasing: a typed path can compile into field access, integer-indexed arrays, a B-tree lookup, an OID resolution, a set-oriented operation, or another representation appropriate to the type and workload.