13
\$\begingroup\$

As a personal project, I'm trying to make a terrain generator that will create terrain looking something like the Castle Story smooth terrain.

If you haven't seen it before, here: enter image description here

So as you can see, it's combination of blocks and "smooth" blocks.

What I've tried to do to emulate this look is to give each surface block a mini heightmap. This generally works, but there are some issues, yielding a terrain like this:

enter image description here

The problem is is that each block is 1x1x1, but sometimes the height at a particular location is negative or > 1. In that case, I clip it and set the height to 0 or 1.

To better illustrate what I mean, here's a diagram: enter image description here

To generate the height, I basically do:

genColumn(int x, int z)
{
    int highestBlockY = (int)noise2d(x, z);

    bool is_surface = true;

    for(int y = max_height - 1; y >= 0; y--)
    {
        Block b;

        if(is_surface)
        {
            b = Block.Grass;
            b.HasHeightMap = true;

            // generate heightmap
            for(int ix = 0; ix < 5; ix++)
            {
                for(int iz = 0; iz < 5; iz++)
                {
                    float heightHere = noise2d(x + ix / 4, z + iz / 4) - y;

                    // clip heights
                    if(heightHere > 1)
                        heightHere = 1;

                    if(heightHere < 0)
                        heightHere = 0;

                    b.HeightMap[ix][iz] = heightHere;
                }
            }

            is_surface = false;
        }
        else
        {
            b = Block.Dirt;
        }

        setBlock(x, y, z, b);
    }
}

Perhaps I'm approaching this incorrectly by using the "true" perlin noise value?

Any help would be greatly appreciated!

\$\endgroup\$

1 Answer 1

11
\$\begingroup\$

Castle Story looks like this due to technical constraints: Were there to be a heightmap per each voxel in the entire volume, rather than only a heightmap per each surface voxel, storage cost would be vastly greater, on the order of O(n^3) which can be prohibitive, as opposed to a more favourable O(n^2), where n is the side length of a cubic voxel space representing your world. Bear in mind that heightmap information for subterranean voxels is implicit in the grid structure, so heightmap info need only be explicitly stored for those voxels which lie on the surface. So the Castle Story guys have snapped vertices to grid interstices to save on storage cost and mesh-construction complexity... read on.

First off, let's look at your options:

enter image description here

(1) is going to make things difficult for you, since in a single voxel column you only want mini-heightmap information for the topmost voxel -- refer back to the first paragraph for the reasons why. Looking at (1), the column on the right has heightmap information for both the topmost and the second-from-top (and this could apply to the third-from-top and so on, if the slope were extreme enough.). This is no good.

(2) Is probably a better option then; that is, ensuring that corner vertices snap to voxel grid interstices. But how then do we address the extreme slope issue? Well, we need to pick some gradient where we simply snap to a vertical column and thus ensure we have no gradients than can crosscut through n topmost voxels. A 45 degree gradient is the natural cutoff for reasons I explain below. So instead of (3), we'd have (4):

enter image description here

(4) Snapping the voxel's corner vertex to the nearest grid interstice is the solution. The visual effect -- diagonal aliasing -- can be seen in your screenshot of Castle Story. The cutoff slope for the voxels is a 1:1 gradient, or 45 degrees (as viewed orthogonally). Working backward from the solution, let's look at the reasons:

  • The only way we could have an unbroken, extreme slope, is if a voxel were vertically elongated...
  • .... But no voxel's mesh can exceed it's bounding area, irrespective of it's actual smoothed shape; a voxel needs to sit in a defined space in a 3D grid which accounts, if not for it's exact form, then at least for it's axis-aligned bounding box.

Another reason to approach it this way is that, as you've already discovered, not using snapping (discretization) leads to a range of geometrically complex surface smoothing scenarios, which are best avoided altogether... games of this sort generally do not require the degree of accuracy that a proper CSG algorithm would provide, which is the whole reason we are using voxels in the first place: Voxels make it far easier to work incrementally with volumes, than floating-point (continuous) polygon intersection / CSG algorithms do.

\$\endgroup\$
7
  • \$\begingroup\$ I just tried implementing this, and I ran into some confusion - what do you mean by "interstices?" Do you mean the integral grid coordinates? \$\endgroup\$
    – untitled
    Dec 28, 2012 at 5:49
  • \$\begingroup\$ @ThomasBradworth. "A space that intervenes between things." For 2D, if you have a n x n grid of cells, you will have (n+1)x(n+1) interstices. This extends directly to 3D. They are the "vertices" which bound each cell, which are mostly shared between multiple cells / voxels. If you boil it down to 1D (a line) then if both the cells and the interstices are represented as array, then cell 0 is bounded by interstice 0 and interstice 1, while cell 1 is bounded by interstice 1 and interstice 2... etc. \$\endgroup\$
    – Engineer
    Dec 28, 2012 at 10:39
  • \$\begingroup\$ Thanks for the reply! I tried doing exactly that, but I got some unfavorable results. At first, I tried simply rounding the height values at the edges (when x is 0 or 4, or z is 0 or 4), but that got me: i.imgur.com/eQW7Y.png (pastebin.com/Lr8vyyHB) Next, I tried smoothing out the points in the middle, so I added a "fix heights function": pastebin.com/AazQ07Xm That, however, also gave me a more angular, but also bad result: i.imgur.com/q1JVP.png Perhaps something is wrong with my noise function? \$\endgroup\$
    – untitled
    Dec 28, 2012 at 22:10
  • \$\begingroup\$ @ThomasBradsworth Sadly, I sense you've only half-read/understood the answer I took over an hour to write and edit. Forget noise; moreover, if you don't understand the noise function, remove it from the equation for now. Your problem lies in how individual voxel mesh data are constructed, and noise has nothing to do with that, because you can create a heightmap in the absence of noise. Work with the simplest test case, i.e. hardcode the height array. Then view your results, and tweak your mesh generation algorithm. Repeat until it does what's expected. Then put the noise back in, and review. \$\endgroup\$
    – Engineer
    Dec 28, 2012 at 22:57
  • \$\begingroup\$ Are you saying that I should just store the height values for the corners and not store height values of the "intermediate" points? \$\endgroup\$
    – untitled
    Dec 29, 2012 at 2:21

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .