1
\$\begingroup\$

So I have recently been researching how to implement DC for procedural terrain. I originally planned to use a 3D grid that just stated if the point is solid or not. I have noticed that most other implementations use a more granular system where a function defines the density of a point rather than if it's solid or not. I have also noticed that instead of using a grid, octrees are used when generating the mesh. So my question is how can I save player modifications to the terrain into the density octree?

A few things I though I'd mention just in case it's relevant:

  • I'm using Unity and working in 3d.
  • By modifications I mean mining, digging, building, etc.
  • I would also like to save this octree so that the data can be re-loaded at a later point.

P.S. I'm not quite sure if this belongs here or in a more math focused section so please inform me if I should move it..

Edit: Here is the code I was using to generate my octree. I'll be honest I don't fully understand how it works as I found it in a c++ implementation of Dual Contouring and just ported it over to c# for testing purposes. I plan on rewriting it so that it is more understandable and documented.

using System.Collections;
using System.Collections.Generic;
using UnityEngine;

public class Octree
{
    public World world;

    const int MATERIAL_AIR = 0;
    const int MATERIAL_SOLID = 1;

    /// <summary>
    /// Offset values when created children.
    /// </summary>
    private Vector3Int[] CHILD_MIN_OFFSETS =
    {
         // needs to match the vertMap from Dual Contouring impl
         new Vector3Int( 0, 0, 0 ),
         new Vector3Int( 0, 0, 1 ),
         new Vector3Int( 0, 1, 0 ),
         new Vector3Int( 0, 1, 1 ),
         new Vector3Int( 1, 0, 0 ),
         new Vector3Int( 1, 0, 1 ),
         new Vector3Int( 1, 1, 0 ),
         new Vector3Int( 1, 1, 1 )
    };

    /// <summary>
    /// Indice values for the end points of edges.
    /// </summary>
    int[,] edgevmap =
    {
        {0,4},{1,5},{2,6},{3,7},    // x-axis 
        {0,2},{1,3},{4,6},{5,7},    // y-axis
        {0,1},{2,3},{4,5},{6,7}     // z-axis
    };

    public Octree(World w)
    {
        world = w;
    }

    /// <summary>
    /// Recursively constructs octreenodes depth first.
    /// </summary>
    /// <param name="node"></param>
    /// <returns></returns>
    public OctreeNode ConstructOctreeNodes(OctreeNode node)
    {
        if (node == null)
        {
            return null;
        }

        if (node.size == 1)
        {
            return ConstructLeaf(node);
        }

        int childSize = node.size / 2;
        bool hasChildren = false;

        for (int i = 0; i < 8; i++)
        {
            OctreeNode child = new OctreeNode();
            child.size = childSize;
            child.min = node.min + (CHILD_MIN_OFFSETS[i] * childSize);
            child.type = OctreeNodeType.Node_Internal;

            node.children[i] = ConstructOctreeNodes(child);
            hasChildren |= (node.children[i] != null);
        }

        if (!hasChildren)
        {
            node = null;
            return null;
        }

        return node;
    }


    private OctreeNode ConstructLeaf(OctreeNode leaf)
    {
        int corners = 0;
        for (int i = 0; i < 8; i++)
        {
            Vector3 cornerPos = leaf.min + CHILD_MIN_OFFSETS[i];
            float density = world.generator.Density(cornerPos);
            int solid = density > 0f ? MATERIAL_SOLID : MATERIAL_AIR;
            corners |= (solid << i);
        }

        if (corners == 0 || corners == 255)
        {
            // voxel is full inside or outside the volume
            leaf = null;
            return null;
        }

        int MAX_CROSSINGS = 6;
        int edgeCount = 0;
        Vector3 averageNormal = Vector3.zero;
        QEFSolver3D qef = new QEFSolver3D();

        for (int i = 0; i < 12 && edgeCount < MAX_CROSSINGS; i++)
        {
            int c1 = edgevmap[i, 0];
            int c2 = edgevmap[i, 1];

            int m1 = (corners >> c1) & 1;
            int m2 = (corners >> c2) & 1;

            if ((m1 == MATERIAL_AIR && m2 == MATERIAL_AIR) ||
             (m1 == MATERIAL_SOLID && m2 == MATERIAL_SOLID))
            {
                // no zero crossing on this edge
                continue;
            }

            Vector3 p1 = leaf.min + CHILD_MIN_OFFSETS[c1];
            Vector3 p2 = leaf.min + CHILD_MIN_OFFSETS[c2];
            Vector3 p = ApproximateZeroCrossingPosition(p1, p2);
            Vector3 n = world.generator.Gradient(p);

            qef.Add(p.x, p.y, p.z, n.x, n.y, n.z);
            averageNormal += n;

            edgeCount++;

            OctreeDrawInfo drawInfo = new OctreeDrawInfo();

            Vector3 min = leaf.min;
            Vector3 max = leaf.min + (Vector3.one * leaf.size);
            if (drawInfo.position.x < min.x || drawInfo.position.x > max.x ||
             drawInfo.position.y < min.y || drawInfo.position.y > max.y ||
             drawInfo.position.z < min.z || drawInfo.position.z > max.z)
            {
                //drawInfo.position = drawInfo.qef.masspoint;
            }
        }

        return null;
    }

    private Vector3 ApproximateZeroCrossingPosition(Vector3 vec0, Vector3 vec1)
    {

        // approximate the zero crossing by finding the min value along the edge
        float minValue = 100000f;
        float t = 0f;
        float currentT = 0f;
        const int steps = 8;
        const float increment = 1f / (float)steps;
        while (currentT <= 1f)
        {
            Vector3 vec = vec0 + ((vec1 - vec0) * currentT);
            float density = Mathf.Abs(world.generator.Density(vec));
            if (density < minValue)
            {
                minValue = density;
                t = currentT;
            }

            currentT += increment;
        }

        return vec0 + ((vec1 - vec0) * t);
    }
}

public class OctreeNode
{
    /// <summary>
    /// The type of this node.
    /// </summary>
    public OctreeNodeType type;
    /// <summary>
    /// Used to determine the bounding box of this node.
    /// </summary>
    public Vector3Int min;
    /// <summary>
    /// Used to determine the bounding box of this node.
    /// </summary>
    public int size;
    /// <summary>
    /// An array of this node's children.
    /// </summary>
    public OctreeNode[] children;
    /// <summary>
    /// The information needed to render this node as part of a mesh.
    /// </summary>
    public OctreeDrawInfo? drawInfo;

    /// <summary>
    /// Offset values when created children.
    /// </summary>
    private Vector3Int[] CHILD_MIN_OFFSETS =
    {
         // needs to match the vertMap from Dual Contouring impl
         new Vector3Int( 0, 0, 0 ),
         new Vector3Int( 0, 0, 1 ),
         new Vector3Int( 0, 1, 0 ),
         new Vector3Int( 0, 1, 1 ),
         new Vector3Int( 1, 0, 0 ),
         new Vector3Int( 1, 0, 1 ),
         new Vector3Int( 1, 1, 0 ),
         new Vector3Int( 1, 1, 1 )
    };

    public OctreeNode()
    {
        type = OctreeNodeType.Node_None;
        min = new Vector3Int(0, 0, 0);
        size = 0;
        drawInfo = null;

        for (int i = 0; i < 8; i++)
        {
            children[i] = null;
        }
    }

    public OctreeNode(OctreeNodeType nodeType) : this()
    {
        type = nodeType;

    }


}

public enum OctreeNodeType
{
    Node_None,
    Node_Internal,
    Node_Psuedo,
    Node_Leaf
}

public struct OctreeDrawInfo
{
    /// <summary>
    /// The index of this node's vertex.
    /// </summary>
    public int index;
    /// <summary>
    /// Information about which edges contain the surface.
    /// </summary>
    public int corners;
    /// <summary>
    /// The position of the vertex.
    /// </summary>
    public Vector3 position;
    /// <summary>
    /// The normal of the vertex.
    /// </summary>
    public Vector3 averageNormal;
    /// <summary>
    /// The state of this node's QEF.
    /// </summary>
    public QEFData3D qef;

};

I understand that a node splits into 8 children when it contains a boundary between positive and negative values. This children are stored in an array within the parent node. A node is marked as a leaf when it contains a boundary and has a size of 1 unit. The boundary appears to be estimated by looping through the points on each edge and finding the closest point to zero. As I said previously this is not my code but just a port from a c++ implementation of DC. It is not fully functional at this time but should show the general idea of how my octree would be working.

Edit 2: I still can't find any info on how to accomplish this. Is there a better way of doing it instead of octrees? The modifying of the terrain would be much easier if it was stored in a grid that just stated if that point was solid or not but then I can't get as smooth of a mesh from DC.

\$\endgroup\$

Your Answer

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

Browse other questions tagged or ask your own question.