In the last week I was working on a DirectX 11 graphics tutorial called PLYViewer.

This tutorial illustrates how to read in a 3D mesh in PLY format and render it in DirectX 11 API. It also shows how to use DirectX Math library to do view navigation.

The interesting part of this tutorial is that a static dependency graph is used to resolve data dependencies among entities.

The dependency graph can be output in Graphviz format and we can visualize it using dot. In the PLYViewer project, the dependency graph is shown below.

PLYViewer dependency graph

Design and implementation

A dependency graph is a directed acyclic graph(DAG) which models the relations among entities. There exists a topology order in the DAG. We can update entities in this topology order without violating the dependencies among entities.

For an example in PLYViewer, a PLY model should be read in memory first, then should the vertex buffer be filled after that. We cannot update them in a reverse order. Otherwise the vertex buffer would be filled with uninitialized data.

For another example, we setup the initial view configuration(view and projection matrices) depending on the scale of imported PLY model. Concretely, we calculate the bounding sphere of imported model and place the camera at the distance of bounding sphere’s radius. We can see that we should compute the model’s bounding sphere first or radius would be incorrect.

By using dependency graph the data dependencies can be resolved in a cleaner way. It requires no manual intervention or ad-hoc code to manipulate the order of entities updating. Besides, having a global knowledge of all dependencies we can safely dispatch updates in parallel.

I start with static dependency graph in PLYViewer project. By “static” it means the topology of dependency graph will not change during the runtime. That is, the nodes will not be created or destroyed; and the edges will not be altered.

Several entities are implemented to model the concrete objects, e.g. the PLY model, the input states, or the camera setup.

Then dependency graph nodes are created to reflect the state of entities, that is, whether an entity is clean, updated, or dirty. These nodes are used to build the topology structure of the dependency graph. We construct a directed edge \( (u \rightarrow v) \) if \(v\) should be updated after \(u\).

Note that the dependency graph nodes are not necessarily mapped to the entities in an injective manner. That is, we can create several nodes for a single entity. In this case a node reflects the state of a portion of entity. We implement the class PLYViewer in this way.

In the update phase, some independent entities are updated first and their corresponding nodes are marked updated. After that the dependency graph propagates these updates to descendant nodes by marking a node dirty.

Whenever we see a node marked as dirty while traversing the nodes in topology order, we perform a dependency resolution. Since we do this in topology order the dependency resolution is always safe.

Ideas and future work

I learned the idea of dependency graph from Blender. In Blender a dynamic dependency graph is implemented. The source code worth reading carefully.

I think there also is some similar code in LLVM’s pass management for dependencies resolution. The passes are registered to the LLVM system and scheduled based on the dependencies. The source code is also worth reading.

I notice that there will be many small objects(graph nodes) allocated in a dependency graph based implementation. The impact to the performance has to be measured.