I'm trying to generate an arbitrary quad mesh with each side having a different, arbitrary number of vertices, ideally with a fairly evenly-size distribution of triangles making up the final mesh, similar to a normal quad subdivision. I haven't been able to find any algorithms for generating such a shape, but Delauney triangulation looks like it might be helpful if I could figure out how to evenly distribute the interior vertices. Is there an algorithm for such triangulation?
I'm not already aware of an algorithm that solves this problem, but if I had to write one, here is what I would try.
n_u = (top vertex count + bottom vertex count) / 2 - 2.n_v = (left vertex count + right vertex count) / 2 - 2.n_u × n_v rectangular grid.By taking the mean of the edge counts, the difference between the interior triangle size and the edge triangle size is minimized, which should avoid overly skinny triangles. Of course, it could be tweaked downward to trade off density match for lower total triangle count.
It might be more efficient in triangle count to smoothly interpolate from one edge's vertex count to the other, but that reopens the question of how to place the points. Perhaps it could be treated as a dithering (of point presence or absence) on a grid as fine as the finest edge subdivision?
