Dynamically create complementary triangles of a regular grid in OpenGL

Question

I have created a regular grid which originates from a 2D image, i.e. each pixels has a vertex. There are two triangles per four pixels so that I have a triangle in the top right and in the bottom left. I use vertex and index buffers for that.

Now I dynamically remove triangles / faces at the border of two different kinds of vertices (according to my application) because else there would be distortions. I wrote a geometry shader which takes a triangle and outputs the triangle or nothing (see first picture). The shader recognizes if a triangle is "faulty" (has orange edges) and omits it.

Now this works fine, but I may lose some details because of my vertex geometry. I can add complementary triangles to the mesh (see second picture, new triangles with dashed orange line).

How do I accomplish this in OpenGL?

My first idea is to create one quad instead of two triangles, check for the four possible triangles cases and create those triangles dynamically in the geometry shader. But this might be slow; GL_QUADs are deprecated and alternatives might be slow too. What do you have in mind?

Answer 1

Here's my idea:

Put the whole grid in a buffer/texture.
Build four triangles for each four pixels. They cross each other, yes.
In the geometry shader you can tell if a triangle is "faulty" because it connects two wrong regions. Or, sampling form the texture, because the crossing triangle is valid, so this new one can be discarded.

EDIT: Another approach

Use the texture. Draw instanced with GL_POINTS. With some order and the help of the instanceID the shader knows where the point is.
For this point test the four possible triangles. If you instance top to down and left to right, only a point to the right and the two below are used for the four triangles. And you avoid repeating tests.
Emit only those you choose.