Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Stage to convert DAG node hierarchy to a tree #40

Closed
pjcozzi opened this issue Apr 1, 2016 · 1 comment
Closed

Stage to convert DAG node hierarchy to a tree #40

pjcozzi opened this issue Apr 1, 2016 · 1 comment

Comments

@pjcozzi
Copy link
Contributor

pjcozzi commented Apr 1, 2016

For a test model and discussion, see CesiumGS/cesium#1754

For the unit tests, please make a few test models to cover all the cases instead of reusing that model. Note that we originally supported DAGs in glTF, but the final spec does not, so we need to convert it to a tree as part of the pipeline.

I did not implement this, but here are my notes, which I'm pretty confident will work:

Given a Directed Acyclic Graph (in this case, a glTF node hierarchy), how do we convert it into a tree such that nodes with multiple incident edges are duplicated to only have one incident edge? This is used for converting a 3D model data structure to a data structure used for rendering, e.g., to compute transforms based on each node's ancestors.

Assuming each node has a visited property, initialize this to false for all nodes. Traverse the graph breadth-first. If a node's visited property is true, duplicate it and the subgraph it is the root of (all nodes in this subgraph should have visited === false), and update its parent's pointer. Otherwise, set visited to true.

For example, D is visited twice below.

 A   // Pretend these have downward facing arrows
/ \
B C
\ /
 D

And the converted tree is:

  A
 / \
B   C
|   |
D   D1   // D1 is the only copy made

In the next graph, G is visited four times.

 A
/ \
B C
\ /
 D
/ \
E F
\ /
 G

The converted tree is:

   A
  /  \
 B     C
 |     |
 D     D1
/ \   /  \
E F   E1 F1
| |   |  |
G G1  G2 G3
@pjcozzi
Copy link
Contributor Author

pjcozzi commented Apr 12, 2016

Added in #42.

@pjcozzi pjcozzi closed this as completed Apr 14, 2016
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

1 participant