how to tesselate bezier triangles?

Question

My concern are quadratic bezier triangles which I'm trying to tesselate for rendering them.

I've managed to implement this by subdividing the triangle recursively like described in a wikipedia page. Though I'd like to get more precision to subdivision. The problem is that I'll either get too few subdivisions or too many because the amount of surfaces doubles on every iteration of that algorithm.

In particular I would need an adaptive tesselation algorithm that allows me to define the amount of segments at the edges. I'm not sure whether I can get that though so I'd also like to hear about uniform tesselation techniques.

Hardest trouble I have trouble with calculating normals for a point in bezier surface, which I'm not sure whether I need, but been trying to solve out.

Answer 1

Adaptive tesselation. There are many algorithms to this. But here's one:

def line_angle((x0,y0),(x1,y1)):
    return atan2(y1-y0,x1-x0)

def adaptive_bezier(p0,p1,p2,lev=32):
    p01 = midpoint(p0,p1)
    p12 = midpoint(p1,p2)
    m = midpoint(p01, p12)
    da = abs(line_angle(p0,p1) - line_angle(p1,p2))
    if da <= max_tolerance or lev <= 0:
        yield m
    else:
        for p in adaptive_bezier(p0,p01,m,lev-1): yield p
        for p in adaptive_bezier(m,p12,p2,lev-1): yield p

For tesselating triangles this way there are complications to the matter. You need to drive the adaptive tesselator algorithm according to the angles of the edge beziers. There's three unique ways how your triangle can split when tesselating.

 2 edges      one edge     3 edges    
--------     ---------    --------
\  ...//     \   |   /    \ /  \ /
 \/___/       \  |  /      \____/
  \  /         \ | /        \  /
   \/           \|/          \/

Define tesselation results for these patterns and you're well off. Only the tesselation with one edge is described in wikipedia article.

Two other tesselation results can be obtained by studying the case of one edge split.

"2 edges" can be obtained straight out by splitting first one edge and then another.

"3 edges" is a bit more work to find out. But you can see the "2 edges" -case brings you a mid-edge. In the case of quadratic bezier triangle it is an averaged sum of diamond appearing there:

--------      /\
\      /     /  \
 \____/     -____-
  \  /       \  /
   \/         \/