How does a recursive quadtree subdivision with concentric circles work?

69 Views Asked by At

I have a quadtree and the subdivision currently works with the distance from the camera to the center of a child and the width of the child.

_LODCircles(pos){
        
    const height = pos.y;  //height of the camera above ocean
    const lodRadius = [];
    const minRadius = 40;  //radius of the smallest lod
    const radius0 = Math.abs(height) > minRadius ? Math.abs(height) : minRadius;
    const qtSize = 200000;  //the size of the quadtree
    const lodSize = Math.log(qtSize/radius0)/Math.LN2;  //calculate the lodsize

    for(let i = 0; i < lodSize; i++){
        lodRadius.push(radius0 * 2 ** i);
    }
                            
    return lodRadius;   
}


_GetChildCorners(child) {
    const corners = [];
    corners.push(new THREE.Vector3(child.bounds.min.x, 0, child.bounds.min.y));
    corners.push(new THREE.Vector3(child.bounds.min.x, 0, child.bounds.max.y));
    corners.push(new THREE.Vector3(child.bounds.max.x, 0, child.bounds.max.y));
    corners.push(new THREE.Vector3(child.bounds.max.x, 0, child.bounds.min.y));
    return corners;
}


//pos = cameraPosition
Insert(pos, scenePosition) {
    let lodCircles = this._LODCircles(pos);
    this._Insert(this.root_, pos, lodCircles);  
}


_Insert(child, pos, lodCircles) {       
/*
    //this works, but i want to make a subdivision with radial concentric lod circles
    const distToChild = this._DistanceToChild(child, pos, scenePosition);

    if ( distToChild < child.size.x && child.size.x > this._params.min_node_size ) {

        child.children = this._CreateChildren(child);
    
        for (let c of child.children) {
            this._Insert(c, pos, lodCircles);
        }
    }
*/

  ???   //  I still have no idea what the code for concentric circles for subdivision might look like   
    
}

But now I want to use concentric circles to get a subdivision like you can see here:

radial quadtree subdivision

I tried to do that with chat gpt but chat gpt keeps suggesting functional examples that don't work.

Update regarding the comments:

I have box3() in three.js. This is an AABB bounding box and I already use it in my quadtree. Every child in my quadtree has one.

I have now used the boundingBoxes for the subdivision.

_Insert(child, pos, lodCircles){
    

    const lod0radius = lodCircles[0];
    const lod0Center = pos; //camera position 
    const closestPoint = new THREE.Vector3();
    child.bounds.clampPoint(lod0Center, closestPoint); 
    const squaredDistance = lod0Center.distanceToSquared(closestPoint);     


    if (squaredDistance <= lod0radius * lod0radius && child.size.x > lodCircles[0] ) {

        child.children = this._CreateChildren(child);

        for (let c of child.children) {
            this._Insert(c, pos, lodCircles);
        }
    }
    
}

I really like your idea! And it's also going in the right direction.

Subdivision with boundingBoxes

But what doesn't fit yet is that there are LOD transitions in which there is a 4:1 subdivision instead of just 2:1. I'm thinking how to fix that. I will probably need all sphere radii after all to ensure that the transitions from Lod to Lod number are only 2:1. Your advices were very helpful. Maybe you also have a good idea for this that I can't see yet?

0

There are 0 best solutions below