How do I enforce a constant 2:1 subdivision from LOD to LOD in a quadtree?

Question

First of all thanks to TARN4T1ON. His recommendation to use boundingBoxes for distance detection helped me to solve my problem.

Now I have a new obstacle.

I want a radially symmetrical gradation of detail from my camera. I achieve radial symmetry with concentric spherical shells around my camera and boundingBoxes for the quadtree childs (AABB collision detection). These spherical shells intersect the quadtree and provide the subdivision. Which of the spherical shells interacts with the quadtree depends on the camera distance. The reason why I need several spheres and not just one is because I want to have defined lod levels. I want a 2:1 gradation from lod to lod. That's why my spherical shells get bigger with 2^i. Nevertheless, it sometimes happens that I get lod transitions of 4:1 instead of 2:1. This is certainly due to my subdivision condition, because this is not a clean solution.

If I transfer the exact child size that results from the intersection of the outermost spherical shell with the quadtree to the underlying spherical shell and and so on, would that be a clean solution?

I always need a 2:1 detail gradation and no larger

_LODRadii(minRadius, numLayers){
        
    const lodRadii = [];
    for(let i = 0; i < numLayers; i++){
        lodRadii.push(minRadius * 2 ** i);
    }           
    return lodRadii;    
}

//I don't use this function for anything right now
_Lod0(child, pos, numLayers, lodRadii){
        
    const lodCenter = pos;
    const closestPoint = new THREE.Vector3();
    child.newBounds.clampPoint(lodCenter, closestPoint); 
    const squaredDistance = lodCenter.distanceToSquared(closestPoint);              

    let lod0 = -1; 
            
    for (let i = 0; i < numLayers; i++) { 
        const lodRadius = lodRadii[i]; 
        if (squaredDistance <= lodRadius ** 2) { 
            lod0 = i; 
            break; 
        } 
    }   
    return lod0;            
}


//pos = cameraPosition
Insert(pos) {
    const minRadius = this._params.min_lod_radius;  //is 24
    const numLayers =   this._params.lod_layers;    //is 15
    const lodRadii = this._LODRadii(minRadius, numLayers);
    const lod0 = this._Lod0(this.root_, pos, numLayers, lodRadii);      
    this._Insert(this.root_, pos, lodRadii, numLayers, lod0);   
}


_Insert(child, pos, lodRadii, numLayers, lod0) {    
    
    //lod0  is the smallest spherical radius that intersects the quadtree. But I don't use that
                
    const lodCenter = pos;
    const closestPoint = new THREE.Vector3();
    child.newBounds.clampPoint(lodCenter, closestPoint); 
    const squaredDistance = lodCenter.distanceToSquared(closestPoint); //squared distance from the camera to bounding box
            

    for(let i = numLayers; i >= 0; i--) {
            
        const lodRadius = lodRadii[i];
    
        if(squaredDistance <= lodRadius ** 2 && child.size.x >= lodRadius ) {
            child.children = this._CreateChildren(child);
            for (let c of child.children) {
                this._Insert(c, pos, lodRadii, i, lod0);
            }
            break;
        }           
    }   
}

The core is my _Insert function. It determines the subdivision of my quadtree. Since everything else about quadtrees is more or less the same and doesn't matter for the subdivision, I left it out. Hundreds of lines of non-contributory code don't help. The core is the _Insert function. What happens in it determines the subdivision.

The reason why I made a function _Lod0 was because I had the idea of ​​using the smallest area directly around the camera as a reference and then going outside with 2:1 smaller subdivisions, but I have no idea how I could implement that and if that would make sense.

Update regarding to Iman Hedeshy's recommendation

Hello Iman, I implemented and tested your detailed recommendations right away. That looks very good, thank you very much. Here is a screenshot:

Once the smallest lod sphere intersects the quadtree, the entire subdivision disappears, but I'll find the cause and fix it. Your recommendation is definitely the solution and it is elegant.

P.S. fixed:

_LODBuckets(minRadius, numLayers){
        
    const lodBuckets = [];
    lodBuckets.push({min: 0, max: minRadius}); //first entry: for lod between 0 and minRadius
    for(let i = 0; i < numLayers; i++){
        lodBuckets.push({min: minRadius * 2 ** i, max: minRadius * 2 ** (i + 1)});
    }
    return lodBuckets;
}

Answer 1

Your current method is determining the appropriate LOD by the distance between the camera and the quadtree bounding boxes. This will give a radial gradation of LODs. However, the problem you're encountering is the non-constant subdivision of 2:1 between LODs, and sometimes you're getting a 4:1 difference.

I'll provide a solution to ensure a 2:1 subdivision:

1- Distance Bucketing:

Before the subdivision process, compute the distance buckets for each LOD level:

let lodBuckets = [];
for(let i = 0; i < numLayers; i++){
    lodBuckets.push({min: lodRadii[i], max: lodRadii[i+1]});
}

2- Determine LOD:

The function to determine the LOD will be:

function determineLOD(distance, lodBuckets){
   for(let i = 0; i < lodBuckets.length; i++) {
       if(distance >= lodBuckets[i].min && distance < lodBuckets[i].max) {
           return i;
       }
   }
   return -1; // or whatever you want for out-of-range distances
}

3- Recursive Insertion:

Modify your _Insert function to use the determine LOD method:

_Insert(child, pos, lodRadii, numLayers, lodBuckets) {    
 
    const lodCenter = pos;
    const closestPoint = new THREE.Vector3();
    child.newBounds.clampPoint(lodCenter, closestPoint); 
    const squaredDistance = lodCenter.distanceToSquared(closestPoint); //squared distance from the camera to bounding box
    const distance = Math.sqrt(squaredDistance);
    const currentLOD = determineLOD(distance, lodBuckets);

    if(currentLOD != -1 && child.size.x >= lodRadii[currentLOD]) {
        child.children = this._CreateChildren(child);
        for (let c of child.children) {
            this._Insert(c, pos, lodRadii, numLayers, lodBuckets);
        }
    }           
}

By bucketing your distances, you ensure that the space between two concentric spheres is always mapped to one LOD. This should provide a consistent 2:1 detail gradation between LODs, and the transition should always be 2:1.

Also, keep in mind that you need to make sure that the sizes of your bounding boxes and initial distances are appropriate to ensure this gradation. If they're not properly set, you might still experience unexpected jumps in LOD.

Lastly, always visualize your structures and LODs as you develop. It'll help you quickly spot inconsistencies and areas of potential improvement.