Jump to content
  • Advertisement
Sign in to follow this  
Anfaenger

Checking if an octree node should be split (refined) or merged (collapsed)

This topic is 552 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

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

Share this post


Link to post
Share on other sites
Advertisement

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.


You could use one uniform grid for each LOD where the grid cell stores only one bit to indicate there exists geometry at given LOD.
To reduce memory you further could use a sparse grid on top where each cell points to a block of n^3 bits.

Share this post


Link to post
Share on other sites
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

Share this post


Link to post
Share on other sites

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

 

 
I've implemented your idea, it does work!
Here is my code in case anybody would find it useful:
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 );
}

I use it so: if( _node.id.GetLoD() > Octree::Calculate_Desired_LoD( _node.id, eyePos ) ) then Split( _node );

It causes square, clipmap-style LoD regions (the third picture; the first uses 1-norm and the 2nd - Euclidean distance):

gvueeW6.jpg

But this function cannot still be used for neighbor LoD calculations. And it uses branches.

I also use closest distance between eye position and the node's bounding box (or between bounding boxes).

Otherwise, LoD regions may become rectangular.

 

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!