Home       About Me       Contact       Downloads       Part 74    Part 76   

Part 75: Things Are Not As They Seem

December 19, 2012

Last part, I mentioned two problems with the summarized landscape code. First, it seemed to produce abrupt changes in resolution, and I couldn't figure out why.

Fig 1: Chunk contains eye
Fig 2: Chunk near eye
The problem here is that I didn't understand the effects of the rules I had used to subdivide terrain. The idea is to divide the size of a chunk (32 meters for the smallest chunks) by the distance from the eye to the chunk. I try to keep this ratio within a range, subdividing chunks when the ratio is too high (resolution too low for the distance) and combining them when the ratio is too low (resolution too high for the distance.) And of course, if the eye is actually within a chunk, it has to be subdivided (distance zero.)

These two rules interact in a way I did not appreciate. Start with the situation in Figure 1. The eye is inside a chunk, so it has to be subdivided into 2x2x2 children. This will happen recursively until the eye is within a minimum sized chunk. This produces the power-of-two landscape I had been seeing. I was assuming the size/distance rule was producing this, but it was entirely a side effect of subdividing the chunk containing the eye.

Consider Figure 2, where the eye is near a chunk, but not in it. The distance rule is in effect here, but trivially. Since the eye is so close, the rule wants a minimum-sized chunk. That causes the large chunk to be recursively subdivided until the nearest piece is minimum size. This again produces a power-of-two landscape.

In the Ring demo image from last time, the top-level blocks are 262 kilometers across. Since all the nearby blocks were divided the way I expected, out to this very large distance, it never occurred to me that the distance rule was never actually being used. It would only come into effect where the eye is distant from the chunk.

In the power-of-two areas, a block twice the size is at twice the distance, giving an effective ratio of 1. I had actually coded a ratio of 3 for splits and 2 for recombination. That meant the size/distance rule produced a very different pattern of chunks, but only out at a great distance where it had a chance to take effect. That was what caused the abrupt 4-1 change in resolution in the image from last week. You can see that in Figure 3 where the green chunk meets the smaller power-of-two chunks near the eye.

Fig 3: Distant chunks obey rule, giving 4-1 resolution change

This is all due to my poor 3d visualization skills. I'm not really sure this rule is what I want now that I see how it works, so I'm rethinking it.

A Stable Distance Measure

Fig 4: Distance to center
Another issue with this algorithm is that distance doesn't work the way I expected. I initially took the distance from the eye to the center of a chunk, since this was sort of an average distance to blocks in the chunk. That doesn't work, and Figure 4 shows why not.

The problem here is that the size/distance ratio of the large chunk causes a split, but the new size/distance ratio of the children is different. In fact, if the eye is in the wrong place, it can then decide the children have to be recombined (because they are all too small for their distance), causing the algorithm to thrash.

The way I fixed this was to measure distance from the eye to the nearest point in the chunk. After the split, there is always one child that is this same distance, preventing the children from being recombined. I got this by trial and error though, not realizing exactly what was happening.

This worked well enough in my flat Crafty-type landscape, but on the Ring, there is another complication. In Figure 5, you can see what curved landscape does to the distance calculation. Even the "eye to nearest point" distance is no longer stable, if I just map the corners of a chunk to the cylinder. The nearest child could be closer to the eye than the parent was.

Fig 5: Subdivision on a cylinder

I can change the Ring and Habitat code to calculate the distance to the curved walls (it's just a radius of the cylinder), and leave the others as planes. Then it should all work. Still, it's all an unexpected nuisance.

The other issue was performance, which was much slower than I expected. I've found the piece of code that's slow, but still haven't decided what to do about it. It's spending a huge amount of time accessing the brick patterns on each face of each cell in the chunk. Since chunks are 32 by 32 by 32 (32K cells) and are scanned in six directions to produce the summaries, any extra code in the inner loop is costly.

I'm still surprised the code is as slow as it appears to be, since it's just a few multiplies, but when I comment it out, the test case is several times faster. I still need to look it over, and try to find a quicker way to handle creation of the face patterns when creating the summary quads.

What To Do?

My bigger problem is that I'm sick of the whole thing! I'm not thrilled with the look, and I'm absolutely disgusted and frustrated with the amount of time I've sunk into this for the results I've gotten. Scott Richmond mentioned last time that "Iteration is key." I need to get something working and then improve it, not obsess over every little detail.

He also apparently thinks that cubes are "so 2010" that there's no point now. I'm not sure of that. I wanted cubes originally not because of the Minecraft look, but because they were easy to build with. I still think that's true. I would like a non-cube landscape, so perhaps now that I'm sleeping slightly better, I could take another whack at understanding dual-contouring.

For the moment, I'm so annoyed with this whole thing that I've been procrastinating for the last couple of weeks and have hardly worked on it. I could just take time off like I did last year -- play games, read books and watch movies until my need to write code reasserts itself. Or, I could work on an unrelated side project, just to accomplish something!

I'm toying with the idea of some kind of 3D printing project, probably a case for the computer I mentioned last time. To do that, I need some kind of Constructive Solid Geometry package, to produce the meshes I send off to one of the printing services.

I downloaded three packages to look at. OpenCascade is huge and does far more than I need. I didn't even know where to begin on it. CGal is not quite as bad, but still very large. There was Carve, a simple Google Code library, but there's not a lot of documentation, and the source didn't all compile.

Finally, there's a small Javascript CSG demo page that looks manageable. I could either do my printing specifications in Javascript, or convert this piece of code to C++. I haven't decided. I'll do a writeup if I go this route and actually get anything built.

In the meantime, Happy Winter Solstice! If we all dance naked in a circle, chanting and beating drums, I'm sure the Sun will return. And so will I -- next year.


Home       About Me       Contact       Downloads       Part 74    Part 76   

blog comments powered by Disqus