Geometric layer management

[Jeremy-Gaillard]

There are currently two PRs (#214 and #195) that are adding 3D geometric data to the scene through various protocols.

I am pretty concern by the approach that is being used in both these cases. The favoured solution seems to be shoving every new geometric feature as an attribute in the TileMesh class.

I have several issues with this method:

• It requires editing TileMesh (and nodePorcess) for each new data type, leading to huge, confusing classes, and hardships for third-party developers
• It forces the data to be fitted inside the globe quadtree
• There is no independence between the layers, which can lead to difficulties when managing a specific layers (e.g. if you want to hide a layer, you have to go through the whole TileMesh hierarchy instead of just hiding the topmost one)

On my side, I've been adding layers that are totally independent from the globe class (you can see some of my work in the 3DBuildings and 3d-tiles branches). My last PR #213 also aims at enabling this method more easily. Basically, each new layer has its own quadtree (or grid, or BVH, or any other data structure) and nodeProcess, and works on its own.

I realise there are drawbacks to this method:

• It requires more computing since there are several quadtrees to go through
• It is harder to clamp data to the ground

I think we should discuss here of a unique, "good practice" way of doing these things.

[nosy-b]

Yes that's a feature difficult to design to optimize all aspects.

About clamp to ground 2D Features:

• Web Feature Service part 2 #214 handle clamp to ground for polygons and lines using resterization. (Other 3D objects were done fastly with three geometry for the usual kml type.)
• The feature layer handling is not finished but the idea is that all clamp to ground 2D features (from all feature layers) should be drawn in the same texture to keep light GPU memory and frag processing.
• That doesn't block independency of the layers has on every new settings (alpha, z-order...) the feature texture will be re-written.

But it also has its drawbacks such as

• slow if animation on rendering (of clamp to ground 2D features)
• resolution is limited by elevation texture max res (max tileLevel)

[nosy-b]

Concerning global 3D layer, yes I agree that it should be possible to have a different Quadtree than globe elevation one for example. Like 3D Tiles it should be able to incorporate its own pyramidal hierarchy.
@qdnguyen @mlamure is it possible to specify new quadtrees for example to access wfs building or Lyon data?

[peppsac]

So with this one, we have 5 issues discussing Layer(s):

• Api high level : Layer for Object3D #120
• Layer recasting #121
• Layer #91
• Choose new name for Class Layer #124
  Plus 2 issues directly linked to Layers:
• [PointCloud] Visualizing PointClouds / potree integration #77 pointclouds
• [OrientedImage] Visualize oriented images #23 oriented images
• 3D Tiles support #185 3D tiles

Clearly a core issue :)

[peppsac]

Quoting myself (from issue #124):

A Layer is used to display data sources.
Currently we only support Layers that are geometries + textures|colors, e.g:

• globe (tilemesh + layerematerial)
• point cloud
• mobilemapping or 360 panorama
• buildings

Geometries, textures and colors can be data layers (wmts, geojson, etc) or computed by itowns (tilemesh)

Some Layers depends on other Layers (e.g: buildings may depend on globe to get accurate vertical positionning).

A Scene is composed of N (>=1) of Layers.

[peppsac]

IMHO a valid solution should cover at least our current and planned use cases:

• globe: raster and vector data
• planar mode
• oriented images
• panoramas
• 3d geometries: e.g building
• point cloud

Am I forgetting something?

[gchoqueux]

I'll look at this

[gchoqueux]

Am I forgetting something?

• helpers and tools (axis, rules...)

[Jeremy-Gaillard]

@peppsac Seems complete to me. I would like to put an emphasis on the fact that we want to be able to handle all these cases without having to modify core files (e.g. Scene.js, TileMesh.js).

@gchoqueux Please share your conclusions with us when you're done!

[gchoqueux]

if you want to hide a layer, you have to go through the whole TileMesh hierarchy instead of just hiding the topmost one

• Imagery layer
  It's true only for imagery layers that are displayed simultaneously inside one shader program (GlobeFS.glsl). We have to change uniform bool visibility[8] for all node's material. To my knowledge, there's not global uniform to hierarchize visibility. A solution, it's deferred rendering, with one pass by imagery layer, and not render layer's pass if it's invisible.

• Feature layer
  On the other hand, actually to hide a feature layer, it's possible to simply hide the highest node.

[Jeremy-Gaillard]

Feature layer
On the other hand, actually to hide a feature layer, it's possible to simply hide the highest node.

Well, it depends on how it is implemented: if you look at the WFS PR, the features are added inside the TileMesh objects ("content" attribute). They are not in a separated data structure.

[gchoqueux]

There's a problem in this PR #195, I have added a new comment, to hide feature layer without traverse all nodes. It's possible to have a separated data structure and switch visibility with the highest node.

[gchoqueux]

Some suggestions for reflection

Design architecture

• Node : a 3D object, 2D object, a data
• Layer : it contains data structure of nodes and layers
• 3DLayer (Inherited Layer) : displayable data structure of 3d objects in scene 3d
  Examples : mesh, cloud, environment cube (panoramic)
• 2DLayer (Inherited Layer) : displayable data structure of 2d objects in screen space
  Examples : background image, tools, effects
• DataLayer (Inherited Layer) : image, elevation or vector data structure in imagery

itowns's instancing

• Map | Layer
  • terrain | 3DLayer : Quadtree plan or quadtree ellipsoid.wgs84
    • imagery | DataLayer : Quadtree wmts, wms, image, kml
    • elevation | DataLayer : Quadtree wmts, wms, image
  • Building | 3DLayer : 3d tile, kml, octree (object 3d, cloud)
  • PanoramicView | 3DLayer : Oriented images, panorama
• Helper | 3DLayer : Tools, Location pin

multi-data structure example

With 2 independent quadtrees : terrain and building.
It's necessary to traverse two trees to update scene.

One solution to optimize is to use a single traverse. We can use the spatial structure of first quadtree to group the nodes of the second. The node.content could be used to group these nodes.

[Jeremy-Gaillard]

How much do we gain by using the merged quadtree structure? We still have to compute SSE and process all the nodes regardless of the solution we use.

I fear that we are adding an extra layer of complexity for very little gain. How do I subdivide quadtree N if quadtree M is lagging behind (because of long request response for instance)? Do I add the new nodes to the content attribute while waiting for M to catch up? Do I need to move these nodes once it has caught up? How do I manage the fact that a single tile from N overlaps multiple tiles from M? Must I process tile A while visiting tile 0 or 2?

I agree that this solution is well suited for terrain data since everything is so intertwined. But aside from this specific case, I am not convinced the added complexity is worth the performance gain.

[gchoqueux]

How much do we gain by using the merged quadtree structure?

there 's only one traverse of one quadtree.

We still have to compute SSE and process all the nodes regardless of the solution we use.

We still have to compute SSE and process all the nodes visible (all nodes and theirs contents )

How do I subdivide quadtree N if quadtree M is lagging behind

Nothing prevents a content from being refined, if this content is visible

Do I add the new nodes to the content attribute while waiting for M to catch up?

You add new nodes to the children

Do I need to move these nodes once it has caught up?

these nodes B are added to other new nodes A's content

How do I manage the fact that a single tile from N overlaps multiple tiles from M?

A content may have several nodes

Must I process tile A while visiting tile 0 or 2?

yes

[autra]

I'm not that into itowns yet and might make some incorrect assumptions, so bear with my noobiness. So take the following more as questions than complete dismissal.

One potential problem I see with your merged quadtree is that... it's not a tree any more. It's becoming a more general graph (among others, it has simple cycles). While it's possible to deal with it, it makes traversal less trivial and more expensive cpu and memory-wise (we need to remember visited nodes, for a start). Whether it will perform better than several quadtrees is possible, but not guaranteed, from my intuition.

Also the child-parent relationship was one-to-many (typically 1-to-4 or 1-to-8). It's now many-to-many if I'm not mistaken. This will have consequences memory-wise, although I'm not sure whether or not it will be more than n quadtrees

The trees can also be vastly different. There is no guarantee the levels would coincide right? Meaning a level2 tile of tree2 can overlaps dozens of level2 tiles of tree1 or actually none. How do we deal with that? How do you actually calculate that? (I mean, simply and cheaply)

But most importantly, we would loose the cool fact that children have one and only one parent. Again, I'm just raising the question: what are the consequences? As far as I can tell, it would break Node.getNodeAtLevel at least, right? (and so maybe NodeProcess.findAncestorWithValidTextureForLayer and NodeProcess.updateNodeImagery - basically everywhere we need a unique ancestor). Not sure we want this. We might end up storing "real" parents of each node for this purpose, effectively recreating separate trees (even if not bi-directional) for each layers. I fear that it will only clutter the code and prevent us to move forward.

So tl;dr, in my humble opinion, it brings a lot of complexity and we're not sure the perf gain would be there. Also it might be a premature optimization as we are not feature-complete yet. But considering my experience with itowns, please take that with a grain of salt.

About @Jeremy-Gaillard proposal : I would do something similar, but instead of having one data structure (tree, grid, whatever) and so one geometry (if I understand correctly) per layer, I would allow a data structure + geometry to have several layers that shares the same geometry. This would limit the numbers of trees to spawn.

To summarize, one geometry could have:

• its own coordinate systems (if I'm right thinking the system is tied to the geometry)
• its own data structure and node refinement policy
• a set of compatible layers (imagery, elevation etc...) that can be applied to it.

That way, when starting itowns, consumers would

• define one or more geometry (each would have its own data structure, octree, quadtree)
• add layers to them
• place each geometry relative to each others.

These consumers app could define only a plane (for displaying a city for instance), or only a globe, or both (a plane of the size of a city can be placed on our globe without too much errors, right)? Also users can then add octrees for point cloud data too. We could then provide helpers for creating commonly used geometry (eg a Earth geometry, a generic configurable globe that can represents other planets or panoramic pictures if you're inside, a plane, a cube, etc), but users would also be able to define their own.

Does that make sense to you? Is this even a viable solution? Please let me know if I missed something and I hope that what I wrote is at least slightly logical ;-)

[gchoqueux]

I do not explain well one thing: the nodes keep their children, we add a notion of content to avoid to traverse all the trees.
There are content links in addition to kinship links.

Next drawing : dashed line : content link | continue line : parent-child link

It's now many-to-many and it's not a tree any more.

No, because, we keep all tree structures.

we would loose the cool fact that children have one and only one parent

We loose nothing for the same reason

Actually, for one tree, there is already 2 traverses, one with Scene.update and scene.rendererScene3D. If you add a tree, you have 4 traverses.... We must also optimize this part:

Next Drawing : Timeline 2 traverses (scene.step 9 ms) = (scene.update 5ms) + (scene.rendererScene3D 4ms)

It is necessary to reduce the number of traverses

[Jeremy-Gaillard]

Thank you @autra for explaining my concerns better than I could.

Concerning the second part of your message, there seems to be a little confusion on what's in a layer. You seem to think that there is one mesh per layer that is refined following a quadtree pattern (similar to Hoppe's progressive mesh). In reality, there's one geometry per node of the quadtree and the combination of these meshes form the terrain.

Our layer concept is a bit vague, as you can see in the first posts of this issue. Some layers are directly renderable (e.g. a point cloud layer), while others need to be combined with another layer (e.g. the imagery layers that need a terrain geometry).

@gchoqueux I think I understand better what you are trying to do. I think your reasoning is wrong on one point: the performance is not bound to the number of tree traversals but to the number of nodes that are visited. Whether we use my solution or yours, we visit the same number of nodes. Your solution is better only in cases where the refinement/visibility testing are the same for both layers and we need only one visit for several layers (like what is done for the terrain), in other cases there should not be significant difference between the two solutions, apart from the coding complexity.

This is what I suggest:

• Keep one traversal when the layers share a tree structure and have similar subdivision rules since we have improved performance and little added complexity
• Have separate traversals when data structures are different

Additionally, we could separate more clearly this notion of shared data structures in the architecture by introducing a container concept:

[gchoqueux]

the performance is not bound to the number of tree traversals but to the number of nodes that are visited.

The more you traverses the trees the more nodes you visit, isn't?

For example (see previous drawing)

• if you traverse only the tree M, if only node[0] is visible then node[A] and are node[B] are potentially visible
• in this case, you visit 7 nodes
• if you traverse the 2 trees N and M then you visit 10 nodes

Your solution is better only in cases where the refinement/visibility testing are the same for both layers and we need only one visit for several layers

In which case it is different?

Additionally, we could separate more clearly this notion of shared data structures in the architecture by introducing a container concept

This concept already exists, Layer or Node are already containers

[Jeremy-Gaillard]

Your example is incorrect: if node 0 is visible, you can't be sure node A or B are visible (camera 1 in the following illustration). Likewise, if node 0 is not visible, you can't be sure node A or B aren't visible (camera 2). You still have to test them.

In which case it is different?

Point clouds and 3d-tiles for example. Or any time the bounding box to test is different than the one of the terrain tile.

This concept already exists, Layer or Node are already containers

The point of this proposition is to be able to clearly state that a list of layers use the same refinement scheme so that the visibility and SSE test can be shared. While it may be possible to do it with some existing classes, I think having a specific class for this purpose simplifies the understanding of the code.

[gchoqueux]

I rectify, they are potentially visible, in any case there are always fewer visited nodes.

Point clouds and 3d-tiles for example. Or any time the bounding box to test is different than the one of the terrain tile.

The terrain's nodes have a BBox with contents (building, cloud...)

The point of this proposition is to be able to clearly state that a list of layers use the same refinement scheme so that the visibility and SSE test can be shared. While it may be possible to do it with some existing classes, I think having a specific class for this purpose simplifies the understanding of the code.

What are the differences between Container and Layer?
Otherwise just rename the instances correctly

[autra]

Specifically answering to #217 (comment)

It is necessary to reduce the number of traverses

Beware, your flame chart precisely shows that what is costly in a traversal are not the number of node or the number of levels of your tree, but the function that are called at the bottow of the stack (you see no horizontal shift on the applyFunctionToChildren and on browseDisplayableNode). We can't see everything in your graph, so let me attach another one:

The time is entirely taken by:

• Matrix4.prototype.makeRotationFromQuaternion
• Vector4.prototype.applyMatrix4
• Some JIT compilation we don't care about
• TileMesh.prototype.setDisplayed
• NodeProcess.prototype.isCulled

And they are all called once or twice for setDisplayed per traversal (apparently on the bottom node?). If my analysis is correct, the tree could have many more levels before it makes any difference. Any optimization that don't aim at removing these calls won't have any effects. More precisely, merging your 2 trees traversal won't remove these calls right? But instead you will probably add expensive computation to just build your merged tree. While I'm at it, how do you plan on building it? It's still very abstract to me 😄

Anyway, is it really the time to discuss optimization ? We don't have a perf problem at the moment. Hell, your tree traversal takes 9ms, which is way less than 60Hz. When I look at the timeline, itowns spends a helluvah time waiting for network answers and user actions, not working on something. Let's remember the 3 rules of optimization and find the right architecture first. We don't even have one that fits our feature needs! We must first design our architecture around these needs, THEN we'll think about optimization, if we need it. And if we did a good job in the first step, chances are we won't even need the second. Any optimization must first come for a clear a good design. If we do so, features would be natural to add and the code will remain efficient.

That being said, now that I've made my rants, I don't have more to propose that I have already said. Thank you @Jeremy-Gaillard for clarifying things. Actually I didn't think there was a mesh per layer, I just said that imho we don't need a tree per layer as you suggested in your first comment, but a tree per geometry. Which brings me to

Additionally, we could separate more clearly this notion of shared data structures in the architecture by introducing a container concept:

I'm with @gchoqueux on this one: any architectural concept that needs to be called container is bound to be useless 😀 So if we can't find a better name to it, it might be a good hint not to use it at all. Very honestly, I'm still a beginner on itowns, but I have the strong feeling we don't need yet another container 😀

In this particular case, I have the strong feeling that your container is what I call a geometry. What I call a geometry is a globe, which is composed of tiles, subdivided or not). It's actually the geometry that contains its layers. it it is so, I guess we more or less agree.

[autra]

To clarify my last comment: I might very well be completely wrong about my perf analysis (I've analysed only a small portion of the execution and perf analysis are hard). My point is: we shouldn't care yet.

[gchoqueux]

The time is entirely taken by:

More you traverse trees, more you visit nodes, more you use functions (like makeRotationFromQuaternion) so we need to reduce the traverses.

We don't have a perf problem at the moment

there are perfomance problems :

• on firefox is slower that on chrome
• on all browser, iTowns's navigation is less fluid than Cesium or Google map 3d

find the right architecture first

• architecture comment
• The idea is to have a generic updater to which have added some static functions nodeProcess, but not having several updater. The 'nodeProcess' are applied to each node and the traverse stops when a process returns false or undefined. There is also a notion of 'nodeProcess' order.
  example

const processList = [
  nodeProcess.occlusion,
  nodeProcess.occlusionHorizon,
  nodeProcess.SSE,
  nodeProcess.refineNode,
];
var updaterQuadtree = new updater(processList);
var quadTree = new QuadTree();

// link updater to quadtree for update 
scene.apply(quadTree,updaterQuadtree);

We can even imagine a process tree to be applied to each node. The children process will be performed according to the parent process. You can instance a new Updater with different process list for each data structure. The difference is the processList, it must be adapt to the structure.

The format of a process is static function foo(node, camera, params) to be able to be added generically in a updater. The idea is to have a generic updater to which have added some nodeProcess, but not having several updater.

[autra]

on firefox is slower that on chrome

we don't know why yet. It could be because of webgl performances, not because of the code or tree traversal, or because of something else entirely.

on all browser, iTowns's navigation is less fluid than Cesium or Google map 3d

Then maybe we can start by caring about all the perf warnings we have in the console 😺 :

I'm talking about

Error: WebGL: texImage2D: Incurred CPU-side conversion, which is very slow.  itowns2.js:33082:6
Error: WebGL: texImage2D: Incurred CPU pixel conversion, which is very slow.  itowns2.js:33082:6
Error: WebGL: texImage2D: Chosen format/type incurred an expensive reformat: 0x1908/0x1401
[....]
Error: WebGL: No further warnings will be reported for this WebGL context. (already reported 32 warnings)

It's so serious it's reported as errors (mind the last line too, I don't even want to know how many we really have)

And then - for instance - we could get rid of things like:

function applyFunctionToChildren(func, node) {
    for (let i = 0; i < node.children.length; i++) {
        func(node.children[i]);
    }
}

which forces us to create an anonymous function instance for each node we traverse and would certainly prevent any possible JIT loop optimization (seriously, we should never create functions in loops).

So of course, we could do better performance-wise, but I still think we should not try to be driven by performance issues in our architecture. There's so many things we have to do for this before trying complicated things. I'm saying that because I had the feeling that performance was the goal of your merged tree idea. Please correct me if I misunderstood.

The 3 rules of optimization:

• Don't
• Don't ... yet
• Profile before optimizing

And imho, the 3rd item should be the very last step, a last resort in fact.

My opinion is still that we should go for the most natural way of organizing the code and that we would then have naturally good performances. I think a merged tree is not a natural way of expressing our data (but maybe I misunderstood your solution of course) because they are too heterogeneous for one data structure.

Anyway, maybe it will be easier to discuss it IRL on January! 😃

[peppsac]

Regarding the whole quadtree / 2 quadtrees / ... discussions : imho we should focus on not depending on a particular tree structure. The opportunity to merge 2 quadtrees could be nice to have but later.

Here is my wish list for iTowns as a framework:

• as we depend on three.js and its scene structure it makes sense to have geometric datas organized as a tree and stored in the Scene's tree (btw: we could also have multiple Scene, one per Layer?). Similarly we should not mimic three.js behavior but with minor difference because this is really misleading (we got bitten by this exact issue last week)
• iTowns' update method would simply be a straightforward tree traversal - very similar to what BrowseTree currently does but simpler (no visibility / cleanup management)
• for each Node, a process or update method would be called. Of course different process methods would be needed (one for globe, one for planar, one for pointcloud, etc)
• these process methods would use Commands and Providers
• if several process ends up implementing the same behavior (tile refinement for instance), we could easily split off the behavior as a helper method class (that's similar to @gchoqueux processor list idea)

So it's quite close to the current architecture, but with a more strict split between what is the framework and what is Globe-specific.

Last but not least: we need to be able to change controls more easily (camera control should not be created in c3dEngine)

Last but not least: I don't see the need for Layer, Layer3D classes. What purpose would they serve exactly?

[gchoqueux]

we should focus on not depending on a particular tree structure

Yes, quatrees are examples, and can be replaced by any structure

Similarly we should not mimic three.js behavior but with minor difference because this is really misleading

Can you specify?

iTowns' update method would simply be a simple tree traversal - very similar to what BrowseTree currently does but simpler (no visibility / cleanup management)

Yes

We could easily split off the behavior as a helper method class

yes, something like that.

tile refinement for instance

It needs some factorization too, make generic imagery and elevation

So it's quite close to the current architecture, but with a more strict split between what is the framework and what is Globe-specific.

I agree

Last but not least: we need to be able to change controls more easily (camera control should not be created in c3dEngine)

Yes this must change

Last but not least: Je ne vois pas la nécessité de Layer, Layer3D classes. À quoi serviraient exactement?

Effectively 3D Layer is not really necessary, however more the process to manage layer with Object3D

[peppsac]

Similarly we should not mimic three.js behavior but with minor difference because this is really misleading

Can you specify?

Add a child to a Layer, then add the Layer to the Scene -> child is displayed
Add the Layer to the Scene, then add child to the Layer -> child is not displayed

[gchoqueux]

I close #121 and move content here

• rename class Layer to avoid confusion
• recast architecture Layer/Provider

Layer and Object3D

• Create new class LayerObject3D or edit the class Layer
  • function addTransform(transform)
• Parameters : id, visibility, opacity, scheduling
• This Layer is mapped with Object3DProvider
• Automatic mechanism to clean and dispose Object3Ds

[gchoqueux]

I close #120 and move content here

new functions in Api high level to manage Layer Object3D

• Api.addLayer(idLayer,browseLayer, nodeProcess)
• Api.removeLayer(idLayer)
• Api.setVisibilityLayer(idLayer,visible)
• Api.setOpacityLayer(idLayer,opacity)
• Api.selecteObjectsInLayer(idLayer,pickingMouse)
• Api.getSelecteObjectsInLayer(idLayer)

Add and remove object in LayerObject3D

• Api.addObjetInLayer(url,idLayer)
• Api.loadObject(url) return object3D/Node
• Api.loadTreeObject(url) return object3D/Node
• Api.removeObjetInLayer(url,idLayer)

[gchoqueux]

The current architecture has responded to requests.