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.