# How can I save a local player modification into a procedurally generated terrain density octree?

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);

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.