Pipeline Hints

From K-3D

Overview

Whenever the value of a node property changes, a "change" signal is emitted. This signal is used for two main purposes:

Notify the user interface that the property value has changed, so the UI can be updated - see http://en.wikipedia.org/wiki/Model_view_controller.

Notify downstream nodes that one of their inputs has changed. The downstream node will reset its internal state so that it gets re-calculated the next time it is accessed, and emits its own change signal(s). This process cascades down the pipeline until every node affected (directly or indirectly) by the original change has been notified.

Originally, change signals in K-3D were empty notifications that a change occurred without providing any additional data:

sigc::signal0<void> foo_changed_signal;

These notifications had correspondingly-simple signal handlers:

void on_foo_changed()
{
  // Deal with the change here ...
}

Although trivial to understand and implement, this approach missed-out on a key optimization - for certain complex data types, downstream nodes may be able to significantly reduce their computational costs if they have additional information about what exactly changed.

As an example, a mesh modifier cannot alter its input mesh - it must make a copy of its input, then change the copy. If the input mesh changes, a naive modifier starts over from scratch, deleting the old copy, creating a new copy, then reapplying its changes. Depending on what changed in the input mesh, this can lead to a large number of time-wasting heap allocations. If the topology of the input mesh changes, then the reallocation is usually the most practical response, but if the topology of the input mesh didn't change (e.g. only point positions changed), then many modifiers don't need to reallocate anything - they could just reapply their changes, if only they knew for certain that the topology didn't change.

In a nutshell, whenever a property changes, we want upstream nodes to be able to pass "hints" to downstream nodes to provide more information about what changed.

Requirements

Because the visualization pipeline carries many different types of data, and because the set of potential changes that could apply to a given type is large, a flexible hinting mechanism is necessary:

A hint can be a simple identifier that classifies the nature of a change, e.g: "topology changed", "geometry changed", "selection changed", etc.
A hint can include arbitrary amounts of metadata describing the change to varying levels of detail, e.g: a hint can provide bounding-box data, ranges of indices that changed, etc.
The hint system allows for any combination of "smart" nodes (nodes that alter their behavior based on hints), and "dumb" nodes (nodes that ignore hints).
Nodes can implement sensible "fallback" behavior if they receive a hint that they don't recognize.
Nodes need to "translate" hints as they travel down the pipeline, e.g. a node that receives a "selection changed" hint as an input may need to produce a "topology changed" hint for an output, depending on how the node works.

Design

Overview

To support the above, change signals are actually implemented as follows:

sigc::signal1<void, k3d::iunknown*> foo_changed_signal;

With corresponding signal handlers:

void on_foo_changed(k3d::iunknown* Hint)
{
  if(dynamic_cast<k3d::hint::mesh_geometry_changed*>(Hint))
  {
    // Efficient computation here
  }
  else
  {
    // Fallback computation here
  }
}

Now, whenever emitting a change signal, the emitter can provide a hint object:

m_output_property.changed_signal().emit(&k3d::hint::mesh_geometry_changed::instance());

or not:

m_output_property.changed_signal().emit(0);

Hint Lifetimes

An important subtlety about the lifetime of hints: hints are created by the emitter of a signal, but the emitter has no way of knowing (nor should it care) how many observers will "see" the hint, nor what they will do with the information it contains. For this reason, observers of a hint cannot store any pointers or references to it - they must assume that the hint object will go out-of-scope as soon as the signal emission returns. If a hint observer needs to retain any of the data associated with a hint, it must make a copy of that data before returning.

Implementation

Several hint classes are defined in k3dsdk/hints.h, and there are a few node implementation classes that are beginning to make use of them.

Hints and cached data

This section goes into more detail on some extra aspects that were introduced to the hint system for use in the mesh painters using shared data caches, i.e. the VBO (Vertex Buffer Object) painters and SDS (SubDivision Surfaces) painters.

Hint processing

In order to simplify the processing of hints, an abstract class hints_processor has been declared in k3dsdk/hints.h. This class handles all the typecasting required to determine the type of change, so a node that needs to process hints can simply derive from this class and implement the different on_..._changed methods. Ideally, when a new hint is introduced it should also get a method in this class.

Cached data

Every mesh shown in the viewport is drawn using a painter. For certain types of painters, it can be useful to keep a data-cache associated with each mesh it has to draw. The VBO painters, for example, keep a vertex buffer cached, and the subdivision surface painters keep a cache containing the subdivided mesh. This cached data should have the following properties:

One cache for each mesh, so if multiple painters paint the same mesh, the same cached data is used
Every change transmitted by the pipeline must be applied to the cache
When the pipeline transmits a change, the cache should only be updated once, not once for every painter using it
When a mesh is removed from the scene, the cached data should also be removed
When all painters using a cache are removed, the cached data should also be removed

In order to facilitate this, a class painter_cache has been defined in k3dsdk/painter_cache.h. This class uses two template arguments: the first is the key used for the cache. Usually, this will be the boost::shared_ptr<...> used to store mesh components in k3dsdk/mesh.h, since these uniquely define the mesh. I.e. using boost::shared_ptr<const k3d::mesh::points_t> as key allows caching of data associated with a mesh's point array. The second template argument determines the type of data that is stored in the cache. Using the instance method, any painter can gain access to cached data that is active in the document. This is great for sharing data, but it raises the problem of who will update the cache when the need arises. To make this simpler, painter_cache.h also defines the abstract class scheduler. This class has two public methods: schedule() and execute(), which in turn call two methods that can be overrided by the client: on_schedule and on_execute. The idea is that on_schedule contains some very light-weight preliminary setup, and on_execute does the real work, with on_execute being called only once after a schedule(). If the scheduler class is implemented by data types stored in a cache, every painter can safely call the schedule() method when a change is detected, and execute() whenever the mesh is drawn. Upon the first call to execute(), the update will be performed, and for all subsequent painters that call execute() it will be ignored.

Dependency changes

The previous use cases work fine when the adresses of the arrays that are used in the cache don't change. When inserting or removing nodes from the pipeline, however, the mesh pointers get reset and their address may change. When no hint is set, this results in a complete recalculation of all downstream nodes, and ultimately a painter will create a new data cache keyed by the new address, leaving the old data in place. To solve this, two new hints were introduced: mesh_address_changed_t and mesh_deleted_t. In order to allow transmission of a hint upon node insertion, the idag::set_dependencies() method now accepts a hint, and the imesh_source class now has a hint() method that returns the hint to be used when this source is inserted into the pipeline. Whenever a new node is inserted, the hint (0 unless imesh_source::hint() is overridden) is passed along through the pipeline. One important application of this mechanism is the insertion of the TweakPoints modifier. This modifier is inserted the first time an interactive transform tool is used, and it basically just causes mesh addresses to change, but until the user has dragged the mouse, no geometry changes. In order to prevent a time-consuming pipeline recalculation just when the user expects interactivity, a mesh_address_changed_t hint is emitted, causing the painters to simply switch the keys on their cahced data and reuse the data itself. This is perfectly safe, since cached data only refers to mesh indices and not to the addresses of mesh data. Similarly, when a mesh is deleted because of an explicit delete or an undo operation, a hint mesh_deleted_t hint is passed to the painter before the mesh address changed, so the painters can use the addresses (which are the key) to delete data that is about to become invalid.

Retrieved from "http://www.k-3d.org/wiki/Pipeline_Hints"

Category: Developer