2
\$\begingroup\$

I am converting two 2D images (A Voronoi graph and a Diamond Square noise map) into a 3D object.

However when finding the corner points of the Voronoi I am left with gaps, so I thought to drop these by calculating adjacency to existing nodes before creating the vertex. However no matter which algorithm for the weld I use, or the tolerance level of the distance I can't seem to get it to work.

This has led me to believe I am doing something wrong.

Image of the issue:

Gaps in generated 3D terrain

These gaps do not appear if I run without the weld, they are created by the weld jumping to spots, but then later welds not finding that spot.

I have even tried to increment the weld distance to a maximum of 10, if a suitable node wasn't found. But this is far to aggressive and has the effect of simplifying the mesh instead and creating more gaps.

My Repo for the full code is here: https://github.com/HughAJWood/TerrainGenerator

private void CalculatePolys()
{
    var nodesForEdges = new List<VNode>();
    foreach (var region in _regions)
    {
        foreach (var point in region)
        {
            if (point == null)
            {
                continue;
            }
            // We calculate where the voronoi node corners are, and pass them into the region
            var diff = ColoursDifferent(point);
            if (diff > 1)
            {
                RenderNodePointsOnImage(point);

                // Points are 2D, so to translate to 3D they are set to the Z property of the 3D node
                var node = new VNode
                {
                    X = point.X,
                    Z = point.Y
                };
                // Weld points within 1 unit from each other by determining if we already have one that exists
                // then using the existing node instead
                // A weld is calculated by determining the X,Z distance to see if we have a node stored already
                // that is within 2 units of the node we are creating
                VNode existingNode = Nodes.FirstOrDefault(n => n.Adjacent(node));
                if (existingNode == null)
                {
                    // Optimise node creation by skipping perlin lookup and ID iteration for only when needed
                    node.ID = VNodeId;
                    node.Y = _perlin.GetPixel(point.X, point.Y).R;
                    Nodes.Add(node);
                    Mesh.ControlPoints.Add(new Vector4(node.X, node.Y, node.Z, 1));
                }
                else
                {
                    node = existingNode;
                }
                nodesForEdges.Add(node);
            }
        }
        //if (i++ > 20) return;
        AddNodesToMeshAsPolys(nodesForEdges);
        nodesForEdges.Clear();
    }
}

The adjacency method is currently simplified to the fact I want to ignore the height of the node.

internal static bool Adjacent(this VNode a, VNode b, int tolerance = 3)
{
    var distance = Math.Abs(a.X - b.X) + Math.Abs(a.Z - b.Z);
    return distance < tolerance;
}

[UPDATE]

I have tried sorting the points by distance and fuzzy distance, both sort in the correct order. Then I tried taking the first point and using that as the welding point. Same effect.

I tried to average the points at the intersections at the image level and pass that back as the point every time, then weld. Same effect.

Clearly there are many approaches I can take for this, the problem arises when there are 2 points close to each other on the edge of a voronoi region. Sometimes they weld and create a gap. Sometimes however in some variances of the algorithm that the points don't weld even though their X,Z coordinates are very close to each. I'm still stumped as how to approach this.

\$\endgroup\$
2
\$\begingroup\$

Shouldn't your adjacent function be like this:

internal static bool Adjacent(this VNode a, VNode b, int tolerance = 3)
{
   var distance = Math.Sqrt(Math.Pow(a.X - b.X, 2) + Math.Pow(a.Z - b.Z, 2));
   return distance < tolerance;
}

EDIT:

After reviewing your project a little, I would suggest some changes to make it more easy to spot any bugs.

  • Leave performance issues for later. It has a tendancy to make the code more difficult to follow.
  • Add unit-testing. I think it works greate with this kind of project, when you want to be sure every math and algorithm does what it should. (I like to use it when trying to boost performance too.)
  • Don't generate your maps when you are trying to find what's wrong, reload previously saved ones. It's much more easy to pinpoint the problem when your input is the same.
  • Output your own file of the polygons for debugging, it can be just a textfile with one polygon for each row. Just to be sure their is no problem with the usage of the third party library (Aspose3D).
\$\endgroup\$
  • \$\begingroup\$ This is a true distance algorithm, I have tried this too. The one I was using was a lazy version using the 2d coordinate system working out the total x+z distance as a positive number. Both yield the same results with the method you show being more accurate as a double. If you take a look at line 110 on github.com/HughAJWood/TerrainGenerator/blob/master/… you can see I have moved to using this but without the sqr root as this isn't required for ordering by distance. \$\endgroup\$ – Hugh Wood Jun 2 '16 at 11:54
  • \$\begingroup\$ Yes the sqr root can be omitted when the ordering is the task. However the lazy version would not work for ordering as distance as vector (0,5) would be considered nearer than (3,3) \$\endgroup\$ – Fredrik Lundvall Jun 3 '16 at 21:39
  • \$\begingroup\$ The max distance should never be more than 1,1 away because it comes from a border of a 2d coordinate. So all I do is presume that 1,0 and 0,1 are closer than 1,1 for this to work. \$\endgroup\$ – Hugh Wood Jun 4 '16 at 22:41
  • \$\begingroup\$ I suspected that was the case, the tolerance is sort of stuck to 3. \$\endgroup\$ – Fredrik Lundvall Jun 5 '16 at 6:59
  • \$\begingroup\$ 1) Performance isn't a concern, and I don't care about it. There are some basic performance optimisations however when I simplify something it is to get it working by the basic parameters of the issue. \$\endgroup\$ – Hugh Wood Jun 9 '16 at 7:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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