Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

So I'm trying to implement "smooth" terrain in my block engine by giving each surface block a heightmap.

Basically, what I do to generate these "heightmaps" for each block is I generate the heights at intervals of 0.25 along the edge of the block. Then, to build the block's vertices, I loop through the heights and create triangles from height to height and put rectangles under the triangles to create something like this: enter image description here

For example, to build the X positive side of a block, I do:

                    Vector2[] uv = BlockUtil.UVMappings[(byte)side]; // uv[0] = top left

                    float height;
                    float nextHeight;
                    float min;

                    float tex_len = 1f / EngineGlobals.TEXTURE_ATLAS_SIDE;

                    for (int i = 0; i < 4; i++)
                    {
                        height = (float)b.Heights[4, i] / 255f;

                        nextHeight = (float)b.Heights[4, i + 1] / 255f;

                        min = Math.Min(height, nextHeight);

                        //create the triangles at the top
                        if (nextHeight > height)
                        {
                            int offset = ch.vertexMap.Count;

                            AddVertex(ch, 0, 0, uv[0] + new Vector2(tex_len * (i / 4f), (1-height)*tex_len), blockPos, new Vector3(1f, height, i / 4f), tr, isliquid);
                            AddVertex(ch, 0, 0, uv[0] + new Vector2(tex_len * ((i + 1) / 4f), 0), blockPos, new Vector3(1f, height, (i + 1) / 4f), tr, isliquid);
                            AddVertex(ch, 0, 0, uv[0] + new Vector2(tex_len * ((i + 1) / 4f), 0), blockPos, new Vector3(1f, nextHeight, (i + 1) / 4f), tr, isliquid);

                            AddTriIndices(offset, 0, 1, 2);
                        }
                        else if (nextHeight < height)
                        {
                            int offset = ch.vertexMap.Count;

                            AddVertex(ch, 0, 0, uv[0] + new Vector2(tex_len * (i / 4f), (1-height)*tex_len), blockPos, new Vector3(1f, height, i / 4f), tr, isliquid);
                            AddVertex(ch, 0, 0, uv[0] + new Vector2(tex_len * (i / 4f), (1-nextHeight)*tex_len), blockPos, new Vector3(1f, nextHeight, i / 4f), tr, isliquid);
                            AddVertex(ch, 0, 0, uv[0] + new Vector2(tex_len * ((i + 1) / 4f), (1 - nextHeight) * tex_len), blockPos, new Vector3(1f, nextHeight, (i + 1) / 4f), tr, isliquid);

                            AddTriIndices(offset, 0, 1, 2);
                        }
                        // else: heights are equal; ignore

                        // create the base rectangle
                        AddVertex(ch, 0, 0, uv[0] + new Vector2(tex_len * (float)i / 4f + tex_len / 4f, (1 - min) * tex_len), blockPos, new Vector3(1, min, (float)(i + 1) / 4f), tr, isliquid);
                        AddVertex(ch, 0, 1, uv[0] + new Vector2(tex_len * (float)i/4f, (1 - min) * tex_len), blockPos, new Vector3(1, min, (float)i / 4f), tr, isliquid);
                        AddVertex(ch, 0, 2, uv[0] + new Vector2(tex_len * (float)i / 4f + tex_len / 4f, tex_len), blockPos, new Vector3(1, 0, (float)(i + 1) / 4f), tr, isliquid);
                        AddVertex(ch, 0, 3, uv[0] + new Vector2(tex_len * (float)i / 4f, tex_len), blockPos, new Vector3(1, 0, (float)i / 4f), tr, isliquid);

                        AddIndices(ch, 0, 1, 2, 2, 1, 3, isliquid);
                    }

I'm not sure if this is a floating point precision error, but when I render it, I get these curious holes on the borders of the base rectangles (I know they're holes because their colors match the color behind them)

What really throws me off is that rather than a whole line, it's just seemingly random dots.

enter image description here

A wireframe view of the world did not reveal any discrepancies. (all it did was make the game lag) enter image description here

A quick little hack that I did was to extend the (i+1)/4 in the code to (i+1.01f)/4, but I'd rather get a concrete solution than something like that.

Perhaps it's something in my shader? My texture sampler is:

Texture TextureAtlas;
sampler TextureSampler = sampler_state
{
        texture = <TextureAtlas>;
    magfilter = POINT;
    minfilter = POINT;
    mipfilter = POINT;
    AddressU = WRAP;
    AddressV = WRAP;
};

Thanks in advance!

share|improve this question
add comment

1 Answer

up vote 15 down vote accepted

From your diagram, it looks like the geometry you're constructing contains T-junctions - places where a vertex of one triangle is supposed to lie exactly on another triangle's edge (resulting in one edge meeting another in a "T" shape). Due to the limitations of finite-precision arithmetic, the vertex usually cannot be guaranteed to meet the edge perfectly and you will find microscopic cracks between them, which often show up as single-pixel glitches because an individual pixel may happen to land in the crack while its neighbors don't.

To fix it, you have to build your geometry in such a way that there are no T-junctions, by splitting each edge where a vertex is supposed to meet it. This diagram shows an example:

enter image description here

EDIT: The above applies to T-junctions in general. For your specific case, as Ilmari Karonen pointed out in the comments, you can build the geometry even better like this:

enter image description here

which also avoids T-junctions and has fewer triangles overall.

share|improve this answer
    
Thanks! I'll try this tomorrow. –  untitled Jan 14 '13 at 7:33
6  
A better way to avoid T-junctions would be to do the triangulation like this. That way, you only need two triangles per segment and no new interior vertices. (You could do it with even fewer triangles, if you wanted; the minimum is one plus the number of segments.) –  Ilmari Karonen Jan 14 '13 at 13:23
    
@IlmariKaronen Thanks, I took the liberty of adding your diagram to the answer. :) –  Nathan Reed Jan 14 '13 at 17:21
    
Worked like a charm! Thanks, guys. –  untitled Jan 15 '13 at 5:38
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.