refine to length

[pca006132]

It would be nice to be able to refine triangles to a certain maximum length, so warp can a large surface (with large triangles originally) into a curved surface smoothly.

[elalish]

Agreed! We could potentially use an OpenGL 4 style algorithm for tessellation, though I think we can do better (in terms of triangle quality).

[hrgdavor]

that would be awesome :)

[ramcdona]

As someone who has written an unstructured surface mesh generator (with curvature based criteria), I would encourage you to limit yourself to OpenGL 4 style tessellation or other highly simplified means.

Ruppert's algorithm type approaches are able to converge to an angle-based criteria. Importantly, they add points, but don't ever move or remove them. I have not seen them applied to a length criteria.

Edge length based criteria (curvature criteria get converted into length criteria) require a 'background mesh' to inform the local mesh criteria. This background mesh is a giant pain in the rear.

Imagine you have a bar of soap that you want to mesh. There are flat sides connected with relatively tight radius curvature at the corners. You need tiny triangles in the corners, but can use huge triangles for the flats. In order to generate a quality mesh, you must gradually grow from tiny tris to huge tris. This is usually implemented as a growth rate limit -- say each edge can only be 1.2 times the length of any edge it is attached to.

The background mesh becomes the place where you solve for this smoothed length criteria. It later is the interpolation map that you use to look up the local criteria that should be applied. It is also the grid you search to find the smallest criteria to provide a place to start meshing.

Smoothing the background mesh is equivalent to an elliptical differential equation. A monster of a hidden problem in the mesh generation process.

Without the background mesh, you could easily generate edges that skip over the local curvature region and span from one flat region to another.

TLDR; Curvature based quality unstructured meshing is an iceberg problem -- it isn't the challenges you see that get you.

[elalish]

Yeah, agreed this is a hard problem in general, especially when coming from NURBS. I was going to take a very basic approach, since all of our edges just become cubic Beziers - just break them into some number of equal parts in terms of the bezier parameter (which automatically spaces them reasonably well regarding curvature). Then all I want to do is calculate the number of pieces to split each edge into - easy for length, a bit trickier for curvature error.

Then the only problem left is to subdivide a triangle for a arbitrary number of segments on each edge - this is a 2D problem and doesn't need to know anything about curvature. OpenGL 4 would work, but it makes for some very poor quality triangles. Still, it's probably a good place to start.

[ramcdona]

Uniform spacing in Bezier parameter doesn't actually guarantee anything in terms of clustering for curvature. You can readily construct a Bezier straight line with highly non-uniform parameter spacing.

I would have to think a bit more about coming up with a counter example. You may be right that the variation diminishing property of Beziers prevents things from getting too bad the other way.

If you're just intending these meshes to be used for graphics, I wouldn't worry about quality -- just generate something correct and be satisfied with that.

If someone wants a quality mesh, they're probably going to have a bunch of other requirements that they want to impose on it. You'll never be able to anticipate all of those requirements.

[elalish]

Fixed by #741.