Hi there!

In my octree-based voxel terrain engine, to prevent cracks, each octree node (chunk) must know the LoDs/sizes of its neighbors.

Currently, this info is stored as 18-bit adjacency masks (for 6 face- and 12 edge-adjacent nodes), with costly neighbor finding to update those masks, for each octree node (like four hundred nodes translating into two thousand checks!).

I'd like to avoid maintaining adjacency masks and instead use an algorithmic approach.

I need a fast function for checking if an octree node at the given position and with the given LoD/size exists in the octree, without walking the entire hierarchy.

The function should preferably be integer-based (i.e. not use floating-point) and cause a square, clipmap-style node arrangement.

Here's the function I use for updating the octree; it ensures 2:1 LOD transitions, but sometimes creates rectangular 'rings' instead of cubic:

/// returns true if the given node requires splitting
bool Node_Should_Be_Split( const OctreeNode& _node, const OctreeWorld::Observer& _eye )
{
	const UINT nodeLoD = _node.id.GetLOD();
	const UINT nodeSize = (1u << nodeLoD);
	const UINT nodeRadius = nodeSize / 2u;
	const UInt3 nodeCenterCoords = (_node.id.ToUInt3() * nodeSize) + UInt3(nodeRadius);
	const UINT distance = Chebyshev_Distance( Int3::FromXYZ(_eye.coordsInChunksGrid), Int3::FromXYZ(nodeCenterCoords) );
	// Chebyshev distance is the 'smallest' norm: max(|dx|, |dy|, |dz|) <= distance(dx,dy,dz) <= |dx| + |dy| + |dz|.
	return distance < nodeSize * LOD_RANGE + nodeRadius;	// this node is far away
}

/// Chebyshev distance (aka "[Tchebychev|Chessboard|Center] Distance" or "maximum [metric|norm]"):
/// the maximum of the absolute rank- and file-distance of both squares.
template< typename TYPE >
TYPE Chebyshev_Distance( const Tuple3< TYPE >& _a, const Tuple3< TYPE >& _b )
{
	return Max3( Abs(_a.x - _b.x), Abs(_a.y - _b.y), Abs(_a.z - _b.z) );
}

I need a fast function for checking if an octree node at the given position and with the given LoD/size exists in the octree, without walking the entire hierarchy.

haven't tested it, just my brain fart:

template< typename TYPE >
int GetLod( const Tuple3< TYPE >& _a, const Tuple3< TYPE >& _b )
{

	const Tuple3< TYPE > ddx = a-b;
	return LeadingBit(dot(ddx,ddx));
}

the idea is: usually, you would call length(ddx), and then increase the lod with every doubling of the distance. (assuming LOD0 is highest quality).
taking the leading bit of the squared distance combines both, but runs with integer only.

for "LeadingBit" you could exploit that intrinsic: https://msdn.microsoft.com/en-us/library/bb384809.aspx

int Calculate_Desired_LoD( const CellID& _nodeId, const V3f& _eyePosition )
{
const int iNodeLoD = _nodeId.GetLOD();
const int iNodeSize = (1 << iNodeLoD); // size of this node, in LoD0 chunks

// The bounding box of the node.
AABBi nodeAABBi;
nodeAABBi.mins = _nodeId.ToInt3() * iNodeSize;
nodeAABBi.maxs = nodeAABBi.mins + Int3(iNodeSize);

// The bounding box of the LoD0-chunk (smallest) containing the view point.
AABBi eyeAABBi;
// Min-corner coordinates of the chunk containing the view point, in LoD0 chunks.
eyeAABBi.mins = Int3(
Float_Floor( _eyePosition.x / CHUNK_SIZE ),
Float_Floor( _eyePosition.y / CHUNK_SIZE ),
Float_Floor( _eyePosition.z / CHUNK_SIZE )
);
eyeAABBi.maxs = eyeAABBi.mins + Int3(1);

const int distance = Calc_Chebyshev_Dist( nodeAABBi, eyeAABBi ); // in LoD0 chunks
const int distance1 = Max( distance, 1 ); // bsr intrinsic expects arguments > 0

// LoD ranges increase as powers of two
DWORD wantedLoD;
_BitScanReverse( &wantedLoD, distance1 ); // log2(distance)
return wantedLoD;
}

/// Computes Chebyshev distance between the two integer AABBs.
int Calc_Chebyshev_Dist( const AABBi& _a, const AABBi& _b )
{
Int3 dists( 0 ); // always non-negative
for( int axis = 0; axis < NUM_AXES; axis++ )
{
const int delta_min = Abs( _a.mins[ axis ] - _b.mins[ axis ] );
const int delta_max = Abs( _a.maxs[ axis ] - _b.maxs[ axis ] );
if( _a.mins[ axis ] >= _b.maxs[ axis ] ) {
dists[ axis ] = _a.mins[ axis ] - _b.maxs[ axis ];
} else if( _a.maxs[ axis ] <= _b.mins[ axis ] ) {
dists[ axis ] = _b.mins[ axis ] - _a.maxs[ axis ];
} else {
dists[ axis ] = 0;
}
}
return Max3( dists.x, dists.y, dists.z );
}