Before we can get started with the actual generation/simulation algorithms we first need to decide how to store our data, i.e. how the world is represented in the data-model. Given that it’s not clear what algorithms, we will use later and what their requirements will be, we’ll want to choose an extendable model, that won’t restrict our options later.

In the last post we’ve looked at how we can store our geometry, how we can traverse the resulting mesh and how we’ll later store our actual data. But one aspect we haven’t looked at yet is how such a mesh data structure can be constructed in the first place, i.e. how we get from a soup of triangle faces to a quad-edge mesh.

There are two basic operations defined in the original paper to construct and modify meshes:

• MakeEdge: Creates a new edge e and its corresponding quad-edge
• Splice: Takes two edges a and b and either connects them or splits them apart, if they are already connected.

While these two operations are powerful enough to construct any quad-edge mesh and apply any modification we might want, they are not ideal for our use-case. First they are rather more complex to use, than I would like for everyday use because they require quite a bit of knowledge about topology and use concepts that are not as easy to visualize as faces in a triangle mesh. And secondly, they allow for structures that we don’t actually want to support, like non-triangular faces.

So, what we will do instead is define our own operations, to make our use case as easy as possible. In this post, we will first look at just the construction of a new mesh, for which we’ll define two functions:

This will (hopefully) be the last post about geometry and the Mesh-API, before we can start with the actual generation algorithms.

We’ve already defined a basic data structure for our geometry, implemented algorithms to traverse it and, in the last post, constructed a spherical Delaunay triangulation of random points, distributed evenly on a sphere.

So, the only part of the API that is still missing are functions to modify existing meshes. The three fundamental operations we’ll define for this are:

class Mesh {
  public:
	// ...
	
	void   flip    (Edge e);
	Edge   split   (Edge e, float split_point);
	Vertex collapse(Edge e, float join_point);
};