Quadtree Demo

// Requires canvasGUI 0.9.1 or later and p5.js

const DOMAIN_SIZE = 512;

​

function preload() {

    imgCol = loadImage('view_collision.png');

    imgDom = loadImage('view_domain.png');

    imgOcc = loadImage('view_occupy.png');

    imgBox = loadImage('view_box.png');

    icons = loadImage('stop-start.png');

    avatar = loadImage('qavatar.png');

    qtinfo = loadStrings('info.txt');

}

​

function setup() {

    let p5canvas = createCanvas(640, 690);

    gui = GUI.get(p5canvas);

    makeGUI();

    makeGUIextra();

    // Create the root partition

    tree = makeTree();

    stats = QuadPartition.getStats(tree);

    lastTime = currTime = millis();

    textSize(13); textAlign(RIGHT);

    testGraph = createGraphics(40, 250).background(0);

​

    paused = false;

    frameRate(50);

}

​

function draw() {

    // Perform updates before drawing

    if (!paused) {

        currTime = millis();

        elapsedTime = currTime - lastTime;

        eTimeSeconds = elapsedTime / 1000.0;

        lastTime = currTime;

        tree.updateTree(eTimeSeconds);

        stats = QuadPartition.getStats(tree);

    }

    push();

    push();

    background(230);

    push();

    translate(2, 2);

    drawPartitions(tree, levelColor);

    drawBalls(tree, levelColor);

    pop();

    fill(240, 240, 255); noStroke();

    drawBox();

    drawDomainData(stats);

    drawCollisionData(stats);

    drawOccupancyData(stats, levelColor);

    pop();

    gui.draw();

    pop();

}

​

function drawBox() {

    push();

    translate(518, 516);

    image(imgBox, 0, 0);

    image(avatar, 32, 2);

    pop();

}

function drawDomainData(stats) {

    push();

    translate(518, 2);

    image(imgDom, 0, 0);

    text(nbr_objects, 110, 56);

    text(nfc(min_col_rad, 1), 110, 96);

    text(nfc(max_col_rad, 1), 110, 116);

    pop();

}

​

function drawCollisionData(stats) {

    push();

    translate(518, 134);

    image(imgCol, 0, 0);

    text(stats.nbr_tests, 110, 40)

    text(maxTests, 110, 58)

    let rate = 100 * stats.nbr_tests / maxTests;

    text(nfc(rate, 1), 60, 100);

    testGraph.fill(0, 7);

    testGraph.noStroke();

    testGraph.rect(0, 0, testGraph.width, testGraph.height);

    testGraph.fill(255, 175, 0);

    testGraph.rect(0, 2.5 * (100 - rate) - 2, testGraph.width, 4);

    image(testGraph, 24, 110);

    pop();

}

​

function drawOccupancyData(stats, colors) {

    push();

    translate(2, 518);

    image(imgOcc, 0, 0);

    text(depth, 80, 39)

    text(stats.nbr_parts, 134, 59)

    text(capacity[depth], 234, 59);

    text(psize[depth], 180, 79);

    text(stats.max_occ, 180, 99);

    text(split_at, 180, 119);

    push();

    translate(260, 24);

    fill(128); noStroke();

    rect(0, 0, 240, 7 * 16);

    for (let i = 0; i < 7; i++) {

        if (i < depth) {

            fill(220);

            rect(2, 2 + 16 * i, 236, 12);

            fill(colors[i]);

            rect(2, 2 + 16 * i, 236 * stats.occ_by_level[i] / nbr_objects, 12);

        }

        else {

            fill(100);

            rect(2, 2 + 16 * i, 236, 12);

        }

    }

    pop();

    pop();

}

​

function drawPartitions(part, colors) {

    fill(colors[part.level]);

    stroke(0, 60); strokeWeight(0.5);

    rect(part.lowX, part.lowY, part.size, part.size);

    part.children?.forEach(p => drawPartitions(p, colors));

}

​

function drawBalls(part, colors) {

    fill(colors[part.level]);

    stroke(0); strokeWeight(0.75);

    part._balls.forEach(b => {

        ellipse(b.pos.x, b.pos.y, 2 * b.colRad, 2 * b.colRad);

    });

    part.children?.forEach(p => drawBalls(p, colors));

}

​

function makeTree() {

    let t = QuadPartition.makeTree(DOMAIN_SIZE, depth, split_at);

    for (let i = 0; i < nbr_objects; i++) {

        let px = Math.random() * DOMAIN_SIZE;

        let py = Math.random() * DOMAIN_SIZE;

        colRad = Math.random() * (max_col_rad - min_col_rad) + min_col_rad;

        let ball = new Ball(px, py, colRad);

        ball.vel.random(lowVel, highVel);

        t.addBall(ball);

    }

    return t;

}

​

function makeGUI() {

    gui.textSize(14);

    let pane = gui.pane('pane', 'south', 300).text('Configure Quadtree');

    pane.setAction((info) => {

        if (info.state === 'open') {

            paused = true;

            gui.$('animate').icon(resumeIcon);

            gui.$('animate').disable();

        }

        else {

            paused = false;

            gui.$('animate').icon(pauseIcon);

            gui.$('animate').enable();

            lastTime = millis();

        }

    })

    // Number of balls

    nbr_objects = 80; maxTests = nbr_objects * (nbr_objects - 1) / 2;

    sdr = gui.slider('nbr_balls', 210, 20, 410, 30).limits(20, 1000).value(nbr_objects)

        .ticks(98, 0, true).parent(pane).opaque().setAction((info) => {

            gui.$('nb1').text(info.value);

        });

    gui.label('nb0', -190, 0, 130, 30).text('Number of balls').parent(gui.$('nbr_balls'));

    gui.label('nb1', -60, 0, 60, 30).scheme('red').text(nbr_objects).parent(gui.$('nbr_balls'));

    // Collision radius

    min_col_rad = 2.6; max_col_rad = 4.4;

    gui.ranger('col_radius', 210, 60, 350, 30).limits(1, 6).ticks(5, 10, true).parent(pane)

        .opaque().range(min_col_rad, max_col_rad).setAction((info) => {

            gui.$('cr_low').text(nfc(info.low, 1));

            gui.$('cr_high').text(nfc(info.high, 1));

        });

    gui.label('cr0', -190, 0, 130, 30).text('Collision radius').parent(gui.$('col_radius'));

    gui.label('cr_low', -60, 0, 60, 30).scheme('red').text(min_col_rad).parent(gui.$('col_radius'));

    gui.label('cr_high', 350, 0, 60, 30).scheme('red').text(max_col_rad).parent(gui.$('col_radius'));

    // Depth

    depth = 3;

    sdr = gui.slider('depth', 210, 100, 410, 30).limits(1, 7).value(depth)

        .ticks(6, 0, true).parent(pane).opaque().setAction((info) => {

            gui.$('dp1').text(info.value);

        });

    gui.label('dp0', -190, 0, 130, 30).text('Depth').parent(gui.$('depth'));

    gui.label('dp1', -60, 0, 60, 30).scheme('red').text(depth).parent(gui.$('depth'));

    // Split at

    split_at = 3;

    sdr = gui.slider('split_at', 210, 140, 410, 30).limits(2, 10).value(split_at)

        .ticks(8, 0, true).parent(pane).opaque().setAction((info) => {

            gui.$('sa1').text(info.value);

        });

    gui.label('sa0', -190, 0, 130, 30).text('Split if >=').parent(gui.$('split_at'));

    gui.label('sa1', -60, 0, 60, 30).scheme('red').text(split_at).parent(gui.$('split_at'));

​

    // Initial velocity range 

    lowVel = 50; highVel = 80;

    gui.ranger('vellocities', 210, 180, 350, 30).limits(40, 140).parent(pane)

        .opaque().range(lowVel, highVel).setAction((info) => {

            gui.$('vel_low').text(nfc(info.low, 1));

            gui.$('vel_high').text(nfc(info.high, 1));

        });

    gui.label('vel0', -190, 0, 130, 30).text('Initial velocity').parent(gui.$('vellocities'));

    gui.label('vel_low', -60, 0, 60, 30).scheme('red').text(lowVel).parent(gui.$('vellocities'));

    gui.label('vel_high', 350, 0, 60, 30).scheme('red').text(highVel).parent(gui.$('vellocities'));

    // Restore controls button

    gui.button('sync', 20, 240, 160, 50).text('Restore controls to\ncurrent configuration')

        .parent(pane).setAction((info) => {

            gui.$('nbr_balls').value(nbr_objects);

            gui.$('nb1').text(nbr_objects);

            gui.$('col_radius').range(min_col_rad, max_col_rad);

            gui.$('cr_low').text(min_col_rad, 1);

            gui.$('cr_high').text(max_col_rad);

            gui.$('depth').value(depth);

            gui.$('dp1').text(depth);

​

            gui.$('split_at').value(split_at);

            gui.$('sa1').text(split_at);

​

            gui.$('vellocities').range(lowVel, highVel);

            gui.$('vel_low').text(lowVel);

            gui.$('vel_high').text(highVel);

        });

    // Use this config button

    gui.button('use', 460, 240, 160, 50).text('Animate using\nthis configuration')

        .parent(pane).setAction((info) => {

            nbr_objects = gui.$('nbr_balls').value();

            maxTests = nbr_objects * (nbr_objects - 1) / 2;

            min_col_rad = gui.$('col_radius').low();

            max_col_rad = gui.$('col_radius').high();

            depth = gui.$('depth').value();

            split_at = gui.$('split_at').value();

​

            gui.$('pane').close();

            lowVel = gui.$('vellocities').low();

            highVel = gui.$('vellocities').high();

            tree = makeTree();

        });

​

    gui.button('cancel', 280, 240, 80, 50).text('CANCEL')

        .parent(pane).setAction((info) => {

            gui.$('pane').close();

        });

    // Animate button

    pauseIcon = icons.get(20, 0, 20, 20);

    resumeIcon = icons.get(0, 0, 20, 20);

    gui.button('animate', 525, 616, 104, 36).text('Toggle\nanimation').icon(pauseIcon)

        .setAction((info) => {

            paused = !paused;

            info.source.icon(paused ? resumeIcon : pauseIcon);

        });

}

​

function makeGUIextra() {

    let pane = gui.pane('paneextra', 'south', 600).text('About');

    pane.setAction((info) => {

        if (info.state === 'open') {

            paused = true;

            gui.$('animate').icon(resumeIcon);

            gui.$('animate').disable();

        }

        else {

            paused = false;

            gui.$('animate').icon(pauseIcon);

            gui.$('animate').enable();

            lastTime = millis();

        }

    });

    gui.label('qtinfo', 40, 20, 560, 500).text(qtinfo, LEFT).opaque().parent(pane).textSize(14).scheme('green');

}

levelColor = ['#FF6565', '#FFE148', '#AAFF4D', '#32AF5D', '#14FFFF', '#5274FF', '#CF6EFF'];

capacity = [0, 1, 5, 21, 85, 341, 1365, 5461];

psize = [0, 512, 256, 128, 64, 32, 16, 8];

​

​

​