I need to implement subj. Not realtime. Just to get one mesh from another and displacement map. I.e. I have a mesh and black and white texture covering it. We interpret the texture as a height map, roughly speaking.

Are there some C++ libraries implementing it or some articles with description of algorithms? If possible, I'd prefer not to reinvent the wheel. But if it's inevitable, I'd like to discuss some thoughts.

If there is no need in adding new triangles to the mesh, we just shift all points along their normals depending on the colour of the point of the corresponding pixel on the texture (or on that pixel and adjacent pixels). Of course it's a degenerate case. Usually we should add triangles to the original mesh. Let us think of the problem of adding that triangles.

Let ABC be the triangle in the mesh. It corresponds to the triangle A'B'C' in the texture. Then I go through all pixels in the texture that lie inside the triangle (at least partly) to calculate some "deviation value of this triangle". This deviation value could be calculated, for example, like this. Imagine the displacement texture as a plot of function of two variables, so the plot is a subspace of R^3. Points A', B' and C' define the plane. And the deviation value could be the maximum distance from pointson the plot whose projections to the horizontal plane correspond to the centers of pixels inside the triangle A'B'C'. If that deviation value is less than a given tolerance value we are done with that triangle of the mesh. Otherwise we split the triangle ABC into smaller triangles and recursively repeat for them. And here we have two options depending on how we do the split.

1. There are no new vertices on the edge on the triangle (for example, on a three small triangles). This is good for simplicity, 'cause splitting of one polygon is completely independent from anothers. But this is bad 'cause despite areas of small triangles goes to zero there would be triangles with big perimeter. So we would not approximate all peaks on the displacement map correctly. See the figure. There the red point corresponds to a peak on the displacement map.

2. There are new vertices on the edge, like on the figure. So we're splitting a triangle on a four small ones. This splitting is good, but creation of vertices on edges makes us care about that adjacent polygons should have the same splitting on adjacent edges or there would some artifacts when the mesh would rendered. It is unpleasant that if we do this way we should keep some additional information like (initial) triangles adjacency and information about splitting of their edges. But the real issue is that splitting of one triangle could cause additional splitting of the triangle already splitt (and this could cause another and so on). See the figure with red and green small triangles. If we split left triangle when we're splitting right we should split left one again. Maybe it's possible to somehow avoid it?

I appreciate any advices.

Recently on gamdev.net I participated in a discussion where I stated that a vertex has no normal. But we agree that we could assign the average of the touching faces normals [to the vertex]. And then you interpolate back these normals across the faces. I would use a proven height map renderer and stich together vertices at the original edges. The models I have on my mind then do not need any LOD at the mesh level. Only height-map LOD.

And then, why do we not just use Catmull-Clark. For each subdivision we store some delta. Thus we need a mipMap. Again the mesh would originally very low poly and each face would typically be split into 10 or more facelets in a regular grid. Think of NURBS surfaces (besides the R).

Recently on gamdev.net I participated in a discussion where I stated that a vertex has no normal. But we agree that we could assign the average of the touching faces normals [to the vertex]. And then you interpolate back these normals across the faces.

Yes, it's obvious. Or normals could be assigned by an artist.

I would use a proven height map renderer and stich together vertices at the original edges.

How to stitch polygons at the original edges is the only nontrivial question.

And then, why do we not just use Catmull-Clark.

I don't see how Catmull-Clark could be useful here. It's the algorithm for a subdivision of the original mesh that cares only about that original mesh, not a displacement map. What I need is, yeah, kind of height map, with additional polygons in the vicinity of peaks on that height map. And with no additional polygons at the original polygons which corresponds to flat areas at the height map.

Think of NURBS surfaces (besides the R).

I don't see how they can be of much use here too. Yeah, splines provide a smooth surface through a given set of points. But it seems that there's no much problem with smoothing a displacement map, because it usually comes from some high-poly version of a model -- so it's already smooth enough. Plus splines doesn't provide the solution to the real problem: how to subdivide the mesh so that there would be many additional polygons where there's abrupt "height" change and to not any of them where the "height map" is flat.

Please tell more about your idea (and your use case, it it the same?). It may be interesting. Of course, we have to split faces anyway -- what if there's a peak in the middle of the face? -- but maybe a preliminary division of edges is useful. It mostly solves the problem of stitching the adjacent polygons at the expense of complication of division of faces. Do I understand correctly?

It would be nice to see some code if it would explain the idea.

The displacement is planned to be used for relief on a human model and maybe for modification of model mesh when a human wears boots, braces and lightweight clothing.

I came up with some solution. I hope I'll find time this week to implement it. Then I'll write on the results. Actually, I'm quite surprised that nobody wrote something: "dude, don't reinvent the wheel, here's a library doing that" or "here's the description of standard algorithm". Because humanity solved that standard task -- in implementations of OpenGL, for example; it's rather close to sculpting in Maya/ZBrush/whatever.