Node hierarchy - DAG or tree?

[pjcozzi]

Currently, the glTF node hierarchy is a DAG (as generated by COLLADA2GLTF and implemented in @fabrobinet's loader, and a bug in Cesium, CesiumGS/cesium#1754 (comment)); however, there is interest from @tparisi and @RemiArnaud to "flatten" at conversion time, which seems better inline with the spirit of glTF.

In #37, @RemiArnaud said:

Although available in COLLADA - an intermediate representation format - and rarely correctly implemented, I would not recommend generic external references in glTF - a presentation format.

The reason is that it becomes very hard to reference unique instances.
main.gltf could instance 2 forests from the same forest.gltf. forest.gltf instance the same tree several times.
you may end up with 4 trees for example, with 4 different paths to it:

forest1->tree1->tree
forest1->tree2->tree
forest2->tree1->tree
forest2->tree2->tree

the only way to differentiate between those 4 trees is to provide their full path.
If the user click on a tree, you have to return the full path to that tree to the application to know which tree it is.

What happen if you want to move the last of those trees, and only that tree?

you can't.
moving the tree node will move all the trees.
moving the tree1 node, will move two trees
moving the forest2 node, will move two different trees

In a run-time / presentation format, I'd recommend using a 'flat' scene, where instances get a new node.
There are several ways to do this, for example limiting external references to leaves objects (not container objects). So you could not instance a forest, you'd have to instance trees.

the collada2gltf tool could create such 'flat scenes' from COLLADA documents using external references.
PS : the openCOLLADA Maya exporter has been fixed to correctly export external references.

[RemiArnaud]

thus post has been moved from another thread and is now out of context.
The context of this post is about external references or generally instancing. I have no grief about current design that enable users to create scenes with the hiearchy depth they decide uppon.
This post says that external refernces should not be allowed as a generic mechanism in glTF. Instead, tools (or web servers) can br used to flatten the scene and avoid external reference namespace issues.

[tparisi]

yeah two different issues I think

but the issue Patrick raises is a big one. If a DAG in glTF is a valid
pattern, then it means an implementation needs to support multiple
instancing. That's fine for geometry, attributes etc. where you're trying
to share large hunks of data without duplication; not so fine for objects
at the mesh/group level where it's gnarly to de-DAG into a flatter
structure, say like the Three.js runtime, which is a tree. It requires a
potential deep copy.

On Wed, Aug 26, 2015 at 11:16 AM, Rémi Arnaud [email protected]
wrote:

thus post has been moved from another thread and is now out of context.
The context of this post is about external references or generally
instancing. I have no grief about current design that enable users to
create scenes with the hiearchy depth they decide uppon.
This post says that external refernces should not be allowed as a generic
mechanism in glTF. Instead, tools (or web servers) can br used to flatten
the scene and avoid external reference namespace issues.

—
Reply to this email directly or view it on GitHub
#401 (comment).

Tony Parisi [email protected]
Founder, Third Eye http://www.thirdeye.gl/
Follow me on Twitter! http://twitter.com/auradeluxe
Read my blog at http://www.tonyparisi.com/
Learn WebGL http://learningwebgl.com/
Mobile 415.902.8002
Skype auradeluxe

Read my books!
Learning Virtual Reality
http://www.amazon.com/Learning-Virtual-Reality-Experiences-Applications/dp/1491922834

Programming 3D Applications in HTML5 and
WebGLhttp://www.amazon.com/Programming-Applications-HTML5-WebGL-Visualization/dp/1449362966
http://www.amazon.com/Programming-Applications-HTML5-WebGL-Visualization/dp/1449362966WebGL,
Up and Running
http://www.amazon.com/dp/144932357X

[fabrobinet]

The current structure allows to share the exact same geometry and to implement instancing. it should be a converter option to force the flattening (or the client can do it as a pre-process...). Keeping things as currently define allows both scenarios (instancing or one big batch) and I would recommend to let things this way...

[fabrobinet]

note in my viewer, I ended in a hybrid solution, where I duplicate the node so it's not a DAG but I kept the same shared geometry in favor of instancing. (which is another benefit of having geometry an attribute of the nodes, and not inherit from it for those wondering).

[tparisi]

@fabrobinet right... what I am saying is that it's a hassle to de-instance nodes in the runtime and might be better done in a tool. the only reason to not do that is if we want to support runtime use of multiple node instances. that seems like an extreme and extravagant use case and puts more burden on people trying to write a simple but compliant viewer

[RemiArnaud]

Here's an idea (1)

• add flag to converted to create 'flat scenes', and have a way to mark the gltf (header) to say so. An application can check if the gltf is flat, and otherwise pun
• servers can provide an unprocessed or flat or optimized in many other ways gltf, based on what the client is asking for. this is very common practice in the web.

(2) Another idea would be to restrict valid gltf content to this 'flat' scene graph, still looking in the details where things can/should be shared.

(3) Another idea is to provide a de-instancing javascript (run-time) library, so that its easy to write a viewer? We could write several helper libraries.

adding a flag would improve current situation, but not make it so all viewers can visualize all gltf files without implementing full instancing anyways.

Which one of (1) or (2) or (3) [other ideas?] is closer to gltf design goals?

[tparisi]

I was implicitly lobbying for (2). it's the simplest and makes for easier implementation and conformance. But this does restrict potential use cases. What I don't have a feel for is if that restriction is a big deal or not.

(1) has the problem you mentioned

(3) is work, and would have to be justified. Again I wonder if the use cases for DAG in a runtime delivery standard are compelling enough.

[pjcozzi]

Does anyone know of any runtime formats for specific engines de-instance at runtime? I kinda doubt it.

In the spirit of glTF (simple and fast to load), it really feels like the converter should de-instance. De-instancing on the client seems like the exact thing glTF tries to avoid unless:

• It is useful to preserve the structure from the original model (like the relationship glTF has now where one mesh can have several primitives).
• It provides a significant size gain, which I don't think it does since it just saves the number of nodes.

If we can justify de-instancing client-side, @RemiArnaud's idea for (3) is good, and the Cesium team may be able to contribute since our users are interested in this (CesiumGS/cesium#1754 (comment)).

@tfili how hard is this to implement in COLLADA2GLTF?

[pjcozzi]

We can also make it a tree in glTF 1.0, and then make it a DAG in glTF 1.0.1 (or whatever) if needed. It will be easier to go that direction, then to restrict it later.

[tparisi]

That's a great idea... going once, twice... ?

[fabrobinet]

hope to state the obvious here: as long as the geometry will be still shared even though the node is a copy to make the tree, then we're good. It means deep copy for node part but references for its attributes.

[tparisi]

Yes by all means we should be able to share geometry or any other objects with large data inside them (animations etc.)

I think we can make this very explicit by forbidding a node to have more than one ancestor (as defined by the "children" property)

[pjcozzi]

All sounds good. We'll make this explicit in the spec and I will discuss with @tfili about adding the flatten feature to the converter.

[pjcozzi]

Talked with @tfili and he thinks this can be done as an asset modifier in COLLADA2GLTF.

[pjcozzi]

Also, for reference, OpenGEX has a tree not a DAG:

The nodes form tree structures in which each node can have at most one parent node.

[pjcozzi]

This is part of gltf-pipeline, CesiumGS/gltf-pipeline#42.

[pjcozzi]

If a glTF model does not follow the spec here and has a DAG, gltf-pipeline will convert it to a tree.

This is also integrated into the online COLLADA to glTF converter.