Vertex List Descriptor

1.0.0-beta

Summary

A cross-platform way to describe vertex memory layouts so that APIs can interoperate without requiring knowledge of the underlying data structures.

Terms

  1. Descriptor: A set of values that describe an associated dataset.
  2. Coordinate: A numeric value member of a set of values that define a specific location.
  3. Vertex: A structure that holds a contiguous block of Coordinate values defining a point. It may contain other fields.
  4. Dimensionality: Number of Coordinates required to define the location of a Vertex.
  5. Pointer: A platform native integer value representing a memory address
  6. Offset: A numeric value added or subtracted from a Pointer to retrieve data at a relative memory location.
  7. Array: A contiguous block of memory with elements directly after each other
  8. Linked List: A chain of Nodes
  9. Node: A structure with a Pointer to another Node
  10. Stride: The distance in bytes from element to element in an Array, in case of a Linked List the distance from a Node start to the Pointer it holds for the next Node
  11. Axis: The set of Coordinate values at one ordinal position across every Vertex in a list. A 2-dimensional list has two Axes, all X values and all Y values.
  12. Axis Array: An Array holding the Coordinates of a single Axis.
  13. Structure of Arrays: A layout holding one Axis Array per Axis rather than one Array of Vertices.
  14. Axis Stride: The distance in bytes from one Axis Array to the next, or where the Axis Arrays are located by Pointers, from one such Pointer to the next.

The Vertex List Descriptor

Memory Layout

0   uint8   version
1   uint8   data_type
2   uint8   list_type
3   uint8   indirection
4   uint8   dimensionality
5   uint8   coordinate_system
6   uint16  stride
8   uint64  count
16  void*   data
20  uint32  _padding_    (32-bit only)
24  uint16  structure_offset
26  uint16  pointer_offset
28  uint16  axis_stride
30  uint16  _reserved_

Consider that the size of void* at offset 16 may be 32-bit on some platforms, but we need to ensure that structure_offset is at byte offset 24. One way to ensure this is to add padding for 32-bit (see _padding_ below).

Fields are ordered by descending alignment requirement, so each one falls on its natural boundary and the descriptor is exactly 32 bytes on every platform with no implicit padding. This ordering is not optional. A uint64 may not begin at an address that is not a multiple of 8, so a count declared directly after four 8-bit fields is placed by the compiler at offset 8 and not offset 4, silently moving every field that follows it.

For brevity we will call a structure that holds coordinates a Vertex, but it may be more complex than just the simple definition of a spatial point position.

The following values are provided by the descriptor. The byte offsets are in brackets []:

Sample C++ implementation

VertexArrayDescriptor.h cpp 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

#include <cstdint>
#include <cstddef>

struct VertexArrayDescriptor {
    std::uint8_t  version = 1;
    std::uint8_t  data_type = 0;
    std::uint8_t  list_type = 0;
    std::uint8_t  indirection = 0;
    std::uint8_t  dimensionality = 0;
    std::uint8_t  coordinate_system = 0;
    std::uint16_t stride = 0;
    std::uint64_t count = 0;
    void*         data = nullptr;
#if UINTPTR_MAX == 0xFFFFFFFFULL
    std::uint32_t _padding_ = 0;
#endif
    std::uint16_t structure_offset = 0;
    std::uint16_t pointer_offset = 0;
    std::uint16_t axis_stride = 0;
    std::uint16_t _reserved_ = 0;
};

static_assert(offsetof(VertexArrayDescriptor, version)           ==  0);
static_assert(offsetof(VertexArrayDescriptor, data_type)         ==  1);
static_assert(offsetof(VertexArrayDescriptor, list_type)         ==  2);
static_assert(offsetof(VertexArrayDescriptor, indirection)       ==  3);
static_assert(offsetof(VertexArrayDescriptor, dimensionality)    ==  4);
static_assert(offsetof(VertexArrayDescriptor, coordinate_system) ==  5);
static_assert(offsetof(VertexArrayDescriptor, stride)            ==  6);
static_assert(offsetof(VertexArrayDescriptor, count)             ==  8);
static_assert(offsetof(VertexArrayDescriptor, data)              == 16);
static_assert(offsetof(VertexArrayDescriptor, structure_offset)  == 24);
static_assert(offsetof(VertexArrayDescriptor, pointer_offset)    == 26);
static_assert(offsetof(VertexArrayDescriptor, axis_stride)       == 28);
static_assert(offsetof(VertexArrayDescriptor, _reserved_)        == 30);
static_assert(sizeof(VertexArrayDescriptor)                      == 32);

Implementations should add static asserts to ensure alignment and may add strong types via getters and setters. The asserts above are the whole set rather than a representative sample, since it is the field order that produces the layout and a reordering will otherwise pass unnoticed.

Constraints

Common Vertex List types

A non-exhaustive list of common representations of coordinate data.

In illustrations below:

Note that 1-based subscript is used in illustrations (simplifies the syntax for the last element in the series).

In all cases below, will the vertex array descriptor have:

Structure holding Coordinates (Vertex)

Even though the structures that hold coordinates can be more complex than simple vertices we will still call them Vertices for simplicity. A Vertex is a structure of the form {pre, (x, y), post} where pre and post are optional data before and after the coordinates (X and Y).

Arrays of Vertices

Contiguous memory of Vertices of the form [v1, v2, ... vn]. If we expand with our definition of Vertex the memory can be seen like this: [{pre_1, (x1, y1), post_1}, {pre_2, (x2, y2), post_2}, ... {pre_n, (xn, yn), post_n}]

To Define the Vertex Array Descriptor we provide

Arrays of Pointers to Vertices

Pointers adjacent in memory with a stride from element to element as size of pointer: [p1, p2 ..., pn] where p1, p2, etc. are pointers to Vertices e.g. p1 -> v1, p2 -> v2, etc.

To Define the Vertex Array Descriptor we provide

Arrays of structures with pointers to Vertices

Arrays hold structures that in turn hold pointers to Vertices. These structures can hold other data as well. For instance we could have {pre1, p1, post1}, {pre2, p2, post2},....

Assume the elements are of type Elem with pointer p to Vertices, e.g. Elem1.p -> v1, Elem2.p -> v2, etc.

To Define the Vertex Array Descriptor we provide

Linked list of structures

Linked lists are chains of pointers to Nodes. Nodes can be located anywhere in memory, each node has a pointer to the next Node in the list and also holds the coordinate values of a specific vertex. Coordinates are held directly by the Node or in a nested Vertex structure.

For example: n1 -> {pre_1, (x1, y1), inter_1, n2, post_1}, n2 -> {pre_2, (x2, y2), inter_2, n3, post_2}, the location of the pointer to the next node is specified by a pointer offset, and the structure offset, as before, is the distance from the start of the structure to the first coordinate.

Please note that the pointer to next Node could also appear before the vertex, for instance: n1 -> [pre_1, n2, inter_1, (x1, y1), post_1].

To Define the Vertex Array Descriptor we provide

Linked list of pointers to structures

We can have a linked list where each node does not directly hold our vertex, but rather points to it. n1 -> {pre1, p1, inter_1, n2, post_1}, where p1 -> v1.

To Define the Vertex Array Descriptor we provide

Structure of Arrays

Rather than one array of Vertices, coordinates are held in one Axis Array per axis, and the coordinates of a single vertex are no longer adjacent. Vertex i is assembled from element i of each Axis Array.

For two Cartesian dimensions the coordinate data is X = [x1, x2, ... xn] and Y = [y1, y2, ... yn]. What differs between the forms below is only how those two arrays are located, which is what axis stride describes.

Resolving a coordinate

For axis a in [0, dimensionality) and vertex i in [0, count), where base is the address held in data and T is the type given by data_type.

Where indirection is 1 and data locates one pointer per Axis Array:

axis_a = *(void**)(base + pointer_offset + a * axis_stride)
coord  = *(T*)((byte*)axis_a + i * stride + structure_offset)

Where indirection is 0 and the Axis Arrays are held in the block at data:

spacing = (axis_stride != 0) ? axis_stride : count * stride
coord   = *(T*)(base + pointer_offset + a * spacing + i * stride + structure_offset)

Arrays of Pointers to Axis Arrays

Pointers adjacent in memory, one per axis, with a stride from element to element as size of pointer: [pX, pY] where pX -> [x1, x2, ... xn] and pY -> [y1, y2, ... yn]. This is the form of a double*[2].

To Define the Vertex Array Descriptor we provide

Structures with pointers to Axis Arrays

A structure holds the pointers to the Axis Arrays and may hold other data before, between or after them: {pre, pX, pY, post}. Assume the structure is of type Soa with pointers x and y, e.g. Soa.x -> [x1, x2, ... xn].

To Define the Vertex Array Descriptor we provide

Adjacent Axis Arrays in a single block

All axes are held in one block of memory, one Axis Array after the other, and no pointers are involved: [(x1, x2, ... xn)(y1, y2, ... yn)]. The block may hold a header before the first coordinate.

To Define the Vertex Array Descriptor we provide

Spaced Axis Arrays in a single block

As above, but the Axis Arrays are deliberately spaced further apart than their contents require, for instance so that each begins on a cache line: [(x1, ... xn) inter_1 (y1, ... yn) inter_2].

To Define the Vertex Array Descriptor we provide

Axis Arrays of structures

An Axis Array may hold structures rather than coordinates directly, in which case structure_offset locates the coordinate within an element exactly as it does for an array of Vertices: pX -> [{pre_1, x1, post_1}, {pre_2, x2, post_2}, ...]. Assume the elements are of type AxElem with coordinate v.

To Define the Vertex Array Descriptor we provide

Axis Arrays over an array of Vertices

An Axis Array need not be a dedicated allocation. Given an existing array of Vertices [{pre_1, (x1, y1), post_1}, {pre_2, (x2, y2), post_2}, ...], pointing each axis pointer at the corresponding coordinate of the first element describes the same data as a Structure of Arrays, with a stride that steps over the rest of each Vertex. This lets a producer present an array of Vertices to a reader of a Structure of Arrays without copying it.

To Define the Vertex Array Descriptor we provide

Future versions

Version field needs to remain fixed as the first value and incremented when the memory layout or structure changes. The Version value should be incremented by 1 when the structure is changed.

Older readers may not assume the structure of a descriptor with a newer unknown version, but a best effort should be made to avoid breaking changes:

If a breaking change is made it should be clearly noted in an updated specification. Doing this will allow API developers to check what versions their API can support. Once a breaking change is approved, the entire structure with exception of the Version field may be restructured and the size of fields modified. While this is not foreseen, it cannot be precluded.

Note: Version numbers refer to the descriptor format, not the specification version

_reserved_ at offset 30 is the only space remaining in the descriptor. A field that does not fit there requires the descriptor to grow to 40 bytes, that being the next size its alignment allows.

Known limitations that a future version may address:

Copyright 2025 Jasper Schellingerhout. All rights reserved.