Draft : Per-loop update traversal

[Desplandis]

This issue is a feature proposal. Feel free to upvote (with 👍 ), comment and provide your use-cases if you're interested by this feature.

Context

This proposal aims to remove the hard-coded depth-first traversal of the quadtree/octree when updating a geometry layer and replace it with per-layer customizable traversal strategies. The depth-first strategy is not always optimal and leads to performance issues in some identified use-cases (see below).

Description of the proposal

This proposal will describe different possible architectures (from non-breaking to hard breaking changes) to allow different geometry layers to use different traversal strategies.

Identified use-cases

A non-exhaustive (feel free to complete) list :

• PointCloudLayer due to the current traversal strategy do not prioritize the expected nodes when querying plus queries too much nodes. The postUpdate step limits a posteriori the rendering to the greatest priority loaded nodes (within the point budget). Since the priority changes with respect to the loaded nodes, this causes pop-in/pop-out effects (especially for huge datasets). We could use a priority queue to limit a priori during the update step(s) the queried nodes (with respect to the point budget).

Implementation

In the following, let:

• G denote the current geometry layer updated (this does not include FeatureGeometryLayer BTW)
• l an attached layer to $G$ (usually a RasterLayer/FeatureGeometryLayer)
• S the set of changes (i.e. nodes of L, L itself, the camera and/or the view) triggering the update
• C the current context

Current implementation

A GeometryLayer interface could be defined as:

interface GeometryLayer<Node, O extends Object3D>  {
     attached: AttachedLayer[]
     preUpdate(ctx: Context, changes: S) -> Node[]
     update(ctx: Context, n: Node) -> Node[]
     postUpdate(ctx: Context, changes: S)
     getObjectToUpdateForAttached(n: Node) -> O[]
}

Note that:

• The preUpdate procedure usually returns a common ancestor node from S used to start the update traversal (it can also be used to pre-compute node-independant results: e.g. pre-SSE).
• The update procedure returns the children of a node (wrt. culling and other heuristics)
• getObjectToUpdateForAttached is kinda peculiar since it returns the set of Object3D currently loaded by the current node (and optionally the parent Object3D). For each object o and each attached layer l, o and its parent are passed to update procedure of l. Since the function is usually of the form (n: Node) => [n.obj] (for TiledGeometryLayer this is equivalent to an identity function), I suppose this is some kind of leftover of passing 3D objects for texturing by attached layers (should I open an issue?).

An AttachedLayer interface could be defined as:

interface AttachedLayer<O extends Object3D> {
    preUpdate(ctx: Context, changes: S)
    update(ctx: Context, o: O, parent: O | undefined)
}

Note that preUpdate and update do not have the same semantics as geometry layers.

A pseudo-code of the current implementation:

def updateElements(nodes: Node[]):
  for n in nodes:
     children: Node[] = G.update(C, n)
     # Update the attached layers for this node
     objs : Object3D[] = G.getObjectToUpdateForAttached(n)
     for o in objs:
        for l in L.attached:
          l.update(C, o, o.parent)
     updateElements(children)

for l in L.attached:
    l.preUpdate(ctx, changes)
roots: Node[] = G.preUpdate(C, changes)
updateElements(roots)  # depth-first update
G.postUpdate(C, changes)

And the sequence diagram:

sequenceDiagram
    participant M as Main Loop
    participant l as Attached Layer (l)
    participant L as Geometry Layer (G)

    loop For each l in G.attached
        M->>l: l.preUpdate(C, changes)
        l->>M: undefined
    end
    M->>L: G.preUpdate(C, changes)
    L->>M: nodes : Node[]

    loop for each n in nodes (updateElements)
        M->>L: G.update(C, n)
        L->>M: children: Node[]
        M->>L: G.getObjectToUpdateForAttachedLayers(n)
        L->>M: objs: Object3D[]
        loop for each o in objs
            loop for each l in G.attached
                M->>l: l.update(C, o, o.parent)
                l->>M: undefined
            end
        end
        M->>M: updateElements(children)
    end

    M->>L: G.postUpdate(C, changes)
    L->>M: undefined

Loading

Proposed Implementation A : "Layer takes all"

The main loop only call the update (or an updateAll if we do wish to introduce breaking changes) method once. Implementation details are not exposed to MainLoop (this is kinda similar to 3d-tiles-renderer). The update(All) default implementation (depth-first) would be more or less the same that updateElements. However, we'll have to ensure that each layer implementation expects the same sets of property for attached layers...

for l in L.attached:
    l.preUpdate(ctx, changes)
roots: Node[] = G.preUpdate(C, changes)
G.updateAll(C, roots)
G.postUpdate(C, changes)

We could go further and even make preUpdate and postUpdate private:

G.update(C, changes)

Proposed Implementation B : "The iterator"

The main loop calls iterator (or whatever we wish to name it) which returns an iterator over nodes (default depth-first iterator). We could propose the following non-breaking implementation :

// traversal.ts
function* depthFirstTraversal(this: GeometryLayer<Node>, nodes: Node[]): Iterator<Node> {
    for (const node of nodes) {
        children = this.update(node);
        yield node;
        yield* depthFirstTraversal(children);
    }
}

class PriorityQueueIterator<Node> {
    constructor(layer: GeometryLayer<Node>, roots: Node[]) {
        this.layer= layer;
        this.priorityQueue = new PriorityQueue<Node>();

        roots.forEach(node => this.priorityQueue.enqueue(node, node.priority));
    }

    *[Symbol.iterator](): Iterator<Node> {
        while (!this.priorityQueue.isEmpty()) { // could add point budgets here
            const node = this.priorityQueue.dequeue()!;
            const children = this.layer.update(node);  // Update node and get children
            yield node;

            children.forEach(child => {
                this.priorityQueue.enqueue(child, child.priority);
            });
        }
    }
}

// GeometryLayer.ts
class GeometryLayer<Node> {
    iterator(roots: Node[]): Iterator<Node> {
        return depthFirstTraversal(this, roots); // default iterator
    }
}

// PointCloudLayer.ts
class PointCloudLayer extends GeometryLayer<PointCloudNode> {
     iterator(roots: Node[]): Iterator<Node> {
        return new DepthFirstIterator(this, roots)
    }
}

And the updated pseudo-code of MainLoop:

for l in L.attached:
    l.preUpdate(ctx, changes)
roots: Node[] = G.preUpdate(C, changes)
# custom update traversal
for n in G.iterator(roots):
    objs: Object3D[] = G.getObjectToUpdateForAttached(n)
    for o in objs:
        for l in L.attached:
            l.update(C, o, o.parent)
G.postUpdate(C, changes)

Potential Problems

Breaking changes in the low-level Layer API:

• GeometryLayer#preUpdate
• GeometryLayer#update
  Honestly, I don't think many users customize this..

Potential Solutions

Depends on the chosen architecture

Documentation