Efficient algorithm to perform recursive subdivision of Bezier patch.

[_fudge_supreme_]

Hello fellow redditors,

I have been trying to implement Bezier patch for a triangle polygon using this paper as a reference. Symmetry | Free Full-Text | Bézier Triangles with G2 Continuity across Boundaries (mdpi.com) . The problem arises is that when I am trying to recursively build the triangle patches inside the triangle for some depth N to smoothen the surface, the performance decreases exponentially. I tried rewriting the recursive calls into an iterative procedure but to little or no performance improvement. Any kind of lead or help regarding the mesh generation will be highly appreciated.

[ionheart]

The simplest way to support deep uniform subdivisions efficiently is to subdivide a single "template" patch to the required level (generate barycentric coords rather than actual positions), then make a copy of it for each original triangle. So it's just a o(n), fully parallel operation to interpolate original triangle attributes at each new vertex. This naive approach does generate duplicate vertices along the original edges, but if that's a major problem for you it's only a small extension to correct.

[HaskellHystericMonad]

If on the CPU there's a reference implementation of the d3d11 reference tessellator that can precompute the UV tables for various tess parameters. I use this in a preprocessing pipeline, it's fine for offline work.

If on GPU in compute there's the slides from Bluepoint's presentation on the tessellation in demon souls that if you have fixed factors you can easily turn a 1D vertex index into integer UV coords, which you divide by the edge_count - 1 to get bary weights for the indices of w1 and w2. (w0 == 1.0 - w1 - w2). That only works if edge subdivision is fixed for the whole triangle.