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?

enter image description here


1 Answer 1


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.

  1. Let n_u = (top vertex count + bottom vertex count) / 2 - 2.
  2. Let n_v = (left vertex count + right vertex count) / 2 - 2.
  3. Generate interior points in a 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?


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .