How to generate tiled delaunay triangulation mesh (delaunay triangulation within a rectangle with triangles connecting opposing edges)?

Question

I have a nice triangulation of a square mesh. The way I do this currently is

1. generate square mesh (two triangles), from (0.,0.) to (1.,1.) (axis-aligned and normalized for simplicity)
2. add point somewhere within square (poisson disk sampling)
3. detect which triangle point falls within
4. subdivide into 3 triangles
5. iterate over all tris, perform "delaunay flips" where necessary
6. GOTO 2

This works great (a bit simplified, as there's also edge-case detection code to account for colinear points, fp precision errors, etc...).

Anyways, what I want to do now is have the edges of this square "wrap".

EDIT: Upon request, here are some illustrations to help convey my problem:

So, we have an initial set of pts:

A normal delaunay triangulation would generate something like this:

What I want is a tessalated delaunay triangulation. That is, what edges would have to exist to allow this to be infinitely tile-able:

An example set of edges might be like this:

Now, imagine if you left those connections, but didn't tile them. I've drawn just the "wrapping" connections for the red dot and the purple dot in green, assuming there is only one instance of each dot in view (centered around the initially displayed set of dots):

Already, it's a topological mess. But in theory, I'd expect it would work, assuming I stick to some implementation constraints.

So, the plan would be to create a mesh containing all these pts and their respective connections. I would have some offset, and move the points in the vertex shader as a modulus of that offset. That way, every point will exist as "the closest instance of that point in the infinitely tiling plane" to the offset (for example, the camera). Since all the connections are in place, I wouldn't have to mess with them, and would get infinitely-scrolling (repeating) "terrain". All the topologically-messy-wrapping connections would be "backfacing" triangles, and would be culled... right?

Edit: Ok no they would not necessarily be backfacing... shoot. (if the wrap of the triangle was both vertically and horizontally wrapped, it would be back to frontfacing. My best guess at a solution is to, in the vert shader, artificially lower all the pts "close" to being wrapped, so any wonky giant tri's show up way below any legitimate tris. #hack.

Ok. off to try this. Will report back with any updates...

Answer 1

Ok. I did it. I'll give a brief description- if someone in the future needs more details feel free to request source.

Because it's tiled, my "non-tiled" solution for generating a delaunay mesh doesn't work. It starts by creating a 4 bounding corner points, dividing them into 2 triangles, and then adding one point at a time (each added point subdividing the triangle it is within). When tiling, you can't do this, because those 4 bounding points are all the same point.

So, to alleviate that, I instead create 9 internal points (at intersection of x = 0.15, 0.5, and 0.85, and y = the same). I connect them as triangles as though they were in a standard grid. But I also create backfacing triangles connecting the left side to the right, and the top side to the bottom. Then I create front facing triangles connecting the four corners in a square (I'll leave it as an exercise to the reader to see why this makes sense).

Once you have this basic, wrapping triangulation, you can (similar to the old method) add one point at a time, subdividing its internal triangles. The trick is that you need to do some modulus arithmetic, centered around the point you are adding, to ensure the "triangle" you're considering is in the orientation as it would be displayed (for example, if you have a triangle with two points near the top left, and one point near the bottom right, the intended orientation of that triangle is one that wraps both the vertical and horizontal axis- NOT a triangle spanning the entire mesh).

Because we started with a triangulation with each triangle's bounding area of less than (0.5,0.5), we know that no larger triangles will be created. So a quick test of its area is helpful in determining whether you are considering the triangle correctly.

Once you are able to do that, just add points to your own satisfaction!