Heightmap triangulation (jaggy valleys)

This topic is 3856 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

Recommended Posts

Howdy, Here's a picture of my terrain: What happens is any terrain shape like a valley between two hills that isn't parallel to the central edges of the triangle pairs that make up the terrain will look jaggy. If I don't apply any smoothing and try to make a pyramid, two out of the four edges leading up to the summit will look like stairs, while the others will look fine and perfectly straight. I was wondering if there was a specific name for this graphical artifact that would allow me to search for solutions... What I think I need to do is "turn" the central edges in the places where the problem occurs... But I'm not sure if that can be done automatically and reliably... (EDIT: image to better illustrate:) Ideas welcome!

Share on other sites
The real problem to solve is which line to use to divide each quad into two triangles, at the smallest level, and it only occurs if the four points are not coplanar. Of course, artifacting occurs more as the four corners of the quad become less coplanar, but if the corners have very different altitudes, this implies more detail in the terrain at those points.

The best solution to the problem would be to know which line causes the smallest amount of artifacting - which requires that you know the intended altitude at the center point of the quad. But that would require more vertices.

If you're like me (and many other developers here) and you're using a heightmap to create the terrain - I would suggest using a very highly detailed heightmap (very high resolution). This will minimize artifacting, but require you to perform LOD optimizations, such as ROAM or Geomipmapping.

Share on other sites
A pretty successful way to solve this I've found involves looking at each quad individually to determine which way it should be triangulated. Basically, it goes something like this...

For each quad, determine the midpoint based on the two triangulations (in 2D, the two midpoints will appear identical, but in 3D they will be at varying heights, depending on the four corner points of the quad). Additionally, compute a nice weighted average of the surrounding vertices (you could just use the four quad points plus the next row/column out, or more for smoother; you can also do nice bi-cubic spline based averaging). Now, compute the error between this "ideal" point and the two points you computed from the two potential triangulations; use the triangulation that minimizes this error.

Rinse and repeat for each quad.

Hope that helps!

Share on other sites
This is not a "problem". This is due to the graphic card linearly interpolating between vertices' colors.
You really shouldn't bother with that : when you will apply texturing, shadowing, and many other effect on your terrain, you won't notice that anymore.
I add the same problem. I just had a terrain with diffuse lighting per-vertex. Then I tried to create a normal map the exact same resolution as my terrain, and did the shading using this normal map. I didn't have any artefact. Although I used exactly the same number of normals ... It's because the textures are not interpolated the same way as vertices are.

Well, and trying to modify the triangle / quad order is simply a bad idea since the principle of terrains is to have a regular grid which can be sent to the GPU as a trianglestrip, or in a GPU-friendly way. Must be fast. And must be optimized for fast rendering. Doing per-triangle tests and breaking the regularity of your grid is not a good idea.

Share on other sites
Thanks for the input guys.

eyemex, that was good advice, thanks, but it turns out it won't be necessary after all (paic is right, turning polygons in irregular patterns will make it a headache to turn my mesh into triangle strips or triangle fans), I'm just going to add more resolution and details, as klaymore and paic suggested.

The problem only happens in between hills that are close together or on very thin hilltops, so increasing the LOD makes the problem much less visible -- it becomes "locally flatter" so quads aren't as convex as before. With texturing and lightmaps, it completely ceases to be an issue.

I was mostly worried that my character would bob up and down when he walked on there, but with the increased level of detail, those triangles are not only smoother overall, they're smaller than his foot, so I can smooth the very minor bobbing out without affecting the gameplay at all.

Thanks again!

Share on other sites
Quote:
 Well, and trying to modify the triangle / quad order is simply a bad idea since the principle of terrains is to have a regular grid which can be sent to the GPU as a trianglestrip, or in a GPU-friendly way. Must be fast. And must be optimized for fast rendering. Doing per-triangle tests and breaking the regularity of your grid is not a good idea.
Flipping triangles in a quad has nothing to do with this; you can do this offline and still use highly optimized strips or index lists. Admittedly, it's more complicated, but it's not a "bad idea" as you claim from the perspective of performance. Indeed, after texturing and all, those artifacts aren't noticeable, however there are other issues that are affected by the way you triangulate your quads, particularly in ridges/valleys; it can affect the success of geomorphing algorithms, and just the overall topology of your mesh. It largely depends on how tesselated your mesh is (doing this "flipping" can allow you to get away with fewer triangles in ridges/valleys in particular). This may be moot if you're not worried about your tri counts.

Share on other sites
I agree with emeyex - flipping triangles does not necessarily break triangle strips, it just makes them more difficult to build.

Check out my terrain page at http://www.klaymore.net/klaymore/terrain.php

1. 1
Rutin
46
2. 2
3. 3
4. 4
5. 5

• 13
• 10
• 12
• 10
• 13
• Forum Statistics

• Total Topics
632995
• Total Posts
3009774
• Who's Online (See full list)

There are no registered users currently online

×