Mark Sachs (ksleet) wrote,
Mark Sachs

  • Mood:
  • Music:

He gazed upon Burnout Revenge and wept, for there were no more worlds to conquer.

So basically what I've been trying to do with the raytracer this weekend is to fix some problems with the fractal terrain. I'll walk you through it with some pictures.

For starters, here's a very simple planet. It's colored pure white and it just has a fractal terrain on it. (What you're really seeing here is the surface normals from the fractal terrain painted onto the sphere, so it looks as if it has a rough, textured surface.) It's not hard to notice that the surface is very heavily creased in a triangular pattern; if you look closely you can pick out the outlines of many of the larger triangles making up the landscape.

This "creasing problem" is actually very common to fractal landscapes which are simplistically generated by taking each edge of each triangle (or square), subdividing it into two new edges, and generating the new point based solely on its two parents. It's a little hard to explain why it happens, but consider that the ideal fractal landscape has every point very similar to all its adjacent points. For example, in a network of triangles, each point has six adjacent points it should be similar to, surrounding it on all sides. However, we only ever generate it based on two points in a straight line. Effectively, information about the landscape can't cross that line, and so you get a crease. There's a much better explanation here on a web page about xmountains, a fractal landscape generator for XWindows; that's where I found useful information on the problem and how to address it.

I followed the xmountains lead to address the problem with two steps. First, when generating the new points, I also take into account the third point on the triangle that's being subdivided, allowing it some influence on the new point's altitude.

This is definitely an improvement, but the seams are still visible. So the second step is, after we've fully generated each level of new points in the triangulation, to then go back and recreate the previous level's points. This time, we know all six adjacent points since we just generated them, and so we can rebuild the points based on all six neighbors. The result is a virtually creaseless planet. I've put all three in order so the change is visible:

Success! A nice side benefit is that in order to keep track of the adjacent points, I had to rewrite how I was generating and storing them while creating the fractal. I can now have, if I wish, a proper list of all the points that make up the fractal planet and can potentially do a lot of interesting things with it. That's a post for another time, though.

You've probably noticed, however, that this planet is still not perfect. It appears to have a "navel" of some sort. This imperfection is also reproduced at the top of the planet; in fact, there's a glitch like this at every corner of the original octahedron the fractal is based on. Looking closely, the triangles making up the planet are smaller near a corner, and larger in the center of the original octahedron's sides. This problem is caused by the way I'm projecting the points onto the surface of the sphere. Here's an illustration:

To explain what you're looking at, the black sphere is the planet. We're looking down on it from above the north pole. The white box inside the planet is the octahedron the fractal is actually generated on. (Keeping all the fractal information on the surface of the octahedron allows me to work with it more efficiently, since all the triangles are in the same plane.) On the top side of the octahedron, I've subdivided some of the triangles; as you can see, all the smallest triangles are equal in size. But the red lines represent projecting the triangles' corners out onto the surface of the sphere for rendering, and as you can see, once projected like this the smallest triangles now have different sizes. They're about half as big at the corners as they are at the edges. This, along with some artifacts caused by how I'm calculating the surface normals, is largely the cause of the glitches at the triangle corners and along the edges that connect them.

At press time I'm still trying to figure out what to do about this short of abandoning the octahedron entirely. Really, I'm encountering a classic map projection problem. Converting between a flat map and a round sphere is the original problem in cartography and there are no good answers, only varying amounts of error.
Tags: raytracer
  • Post a new comment


    default userpic

    Your reply will be screened

    Your IP address will be recorded 

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.