potree-sdk/src/modules/Images360/tile/TileTree.js

import * as THREE from "../../../../libs/three.js/build/three.module.js";


function Node(e, t) {
    this.tree = e,  //所属树（TileTree）
    this.parent = t,
    this.children = [],
    this.id = ++u;
}

function o(e, t, i, r, a, s, l, h) {
    if (e) {
        l = l || TileTree.TraversalType.PreOrder;
        var u = r * c + i;
        if (l === TileTree.TraversalType.PreOrder && (a && a(e, t, u, i, r),
                s && s.push(e)),
            e.children && 0 !== e.children.length) {
            for (var d = r * c, p = i * c, f = 0; f < c; f++)
                for (var g = 0; g < c; g++)
                    o(e.children[g * c + f], t + 1, p + f, d + g, a, s, l, h);
            l === TileTree.TraversalType.PostOrder && (a && a(e, t, u, i, r),
                s && s.push(e))
        }
    }
}

function Plant(seed) {
    seed.root = Branch(seed, null, 0)
}

function Branch(seed, parent, level) {
    if (level > seed.levels)
        return null;
    var node = new Node(seed, parent);
    seed.allNodes.push(node);
    for (var o = 0; o < h; o++)
        node.children[o] = Branch(seed, node, level + 1);
    return node
}

function l(parent, t, level, n, r) {
    if (!parent)
        return null;
    if (0 === level)
        return parent;
    if (!parent.children || 0 === parent.children.length)
        return null;
    var o = Math.pow(c, level),
        a = o / c,
        s = n % a,
        h = r % a,
        u = Math.floor(r / a),
        d = Math.floor(n / a),
        p = u * c + d,
        f = parent.children[p];
    return l(f, t + 1, level - 1, s, h)
}


/*  cube每个面都有一个分层树  用于代表瓦片图的细分？

    树4096的分为三层，每层有4个子节点。（最后一层的四个子节点都是null）

 */
 
 
var c = 2,
    h = c * c; //4个子节点
var u = 0;




export default class TileTree {
    constructor(e, t) {
        this.levels = t,
        this.tileSize = e,
        this.root = null,
        this.allNodes = [],
        Plant(this);
    }

    getSubNode(e, t, i) {
        (!t || e < this.tileSize) && (t = 0),
        (!i || e < this.tileSize) && (i = 0),
        e < this.tileSize && (e = this.tileSize);
        var level = TileTree.getLevelCountForSize(this.tileSize, e),
            o = l(this.root, 0, level, t, i);
        return o
    }

    breadthFirst(e) {//广度优先搜索
        e = e || {};
        var t = !!e.nullLevelEnd,
            i = e.maxLevel,
            n = e.minLevel,
            r = e.callback,
            o = e.saveVisited,
            a = [],
            s = {},
            l = 0,
            c = 0;
        for (a.push(this.root),
            a.push(s); a.length > 0 && !(i && l > i);) {
            var h = a.shift();
            if (h === s)
                (!n || l >= n) && (r && t && r(null),
                    o && t && o.push(null)),
                a.length > 0 && a.push(s),
                l++,
                c = 0;
            else {
                if (h.children)
                    for (var u = 0; u < h.children.length; u++) {
                        var d = h.children[u];
                        d && a.push(h.children[u])
                    }
                var p = this.getFaceIndexFromNode(h);
                (!n || l >= n) && (r && r(h, l, p),
                    o && o.push(h)),
                c++
            }
        }
    }

    getFaceIndexFromNode(e) {
        if (!e)
            return -1;
        for (var t = 1, i = e, n = 0, r = 0;;) {
            var o = i.parent;
            if (!o)
                break;
            for (var a = -1, s = 0; s < o.children.length; s++)
                o.children[s] === i && (a = s);
            var l = a % c,
                h = Math.floor(a / c);
            n = l * t + n,
                r = h * t + r,
                t *= c,
                i = o
        }
        return r * t + n
    }

    depthFirst(e, t, i) {
        o(this.root, 0, 0, 0, e, t, i, this.tileSize)
    }
}

TileTree.TraversalType = Object.freeze({
    PreOrder: 0,
    PostOrder: 1
});

TileTree.getLevelCountForSize = function(tileSize, size) {//512->0 2024->1
    var i = 0;
    for (size < tileSize && (size = tileSize);;) {
        if (size /= c,
            size < tileSize)
            break;
        i++
    }
    return i
};

TileTree.getSizeForLevel = function(e, t) {
    return Math.pow(c, t) * e
};