Is there a way to implement something like marching squares on a grid drawn with triangle strips?

I am currently drawing a grid using a series of triangle strips. I am using this to render a height field, and generating the vertex data completely in the vertex shader without any input buffers just using the vertex and instance indexes. This is all working fine and is very efficient.

However, I now find myself also needing to implement border lines on this grid. The obvious solution here would be something like marching squares. Basically, what I want to achieve is something like this:

The black dots represent the vertices in the grid that are part of some set, and I want to shade the area inside the red line differently than that outside it.

Naïvely, this seems like it would be easy: Add a value to the vertices that is 1 for vertices in the set and 0 for those outside it, and render differently depending on if the interpolated value is above or below 0.5, for instance.

However, because this is rendered as a triangle strip, this does not quite work. In pracitce, since this is rendered as a triangle strip, this ends up looking like this:

So, half the edges work and half end up with ugly square staircases.

I've now been trying to wrack my brain for days whether there is some trick that could be used to generate the vertex values differently or making a more complicated test than >0.5 to get closer to the intended shape without giving up on the nice and simple triangle strips and having to actually generate geometry ahead of time, but I can not think of one.

Has anyone ever dealt with a similar problem? Is there some clever solution I am missing?

I am doing this in Metal, but I don't expect this to depend much on the specific API used.

It sounds like you're trying to calculate the colors in the fragment shader independently of the mesh underneath. If so, you should decouple the color calculation from the mesh.

Assuming your occupancy is stored in a texture, use textureGather to get the four nearby occupancy values; determine the equation of the boundary; then use the fractional part of the texture coordinates to determine its position relative to the boundary. (The devil here is in the details -- in particularly the ambiguous checker-board pattern case.)

Once you implement the above approach, it's very likely you won't even need the triangle strip mesh anymore -- simply fill your entire drawing area with a single large quad and let the fragment shader to do the rest.