利用者:Nazg-gul/GSoC-2013/LocalGraphs

Threaded Dependency Graph: Local graphs

The idea of local graphs is to separate objects state for viewport and renderer in order to solve threading conflicts between them. The same local graphs approach might be used to support local time offset for dupli-group.

There're multiple ways to do it, but the most suitable way to go seems to be a copy-on-write, which is described below.

Copy-on-Write

This is a way of solving data/state conflicts (which might occur between render and viewport threads) by copying data when it's necessary.

Outline of this approach:

• Transparent for object-update routines.
• Minimal memory usage.
• Effectively solves render/viewport threads conflict.
• Doesn't increase render stability if doing destructive changes during rendering.
• Allows to have famous dupli-group local time offset.
• Also allows such additional features:
  • Per-window scene/time.
  • Animation pre-fetching and cacheing.
• Apply-able for any kind of ID datablock.

Design

General Idea

Copy-on-Write is obviously only do a copy when write to a datablock happens. Reading a datablock doesn't require copying, only shall happen from a copied version of the datablock (if it exists).

There's no magic happening about how to detect whether datablock is gonna to be modified. It is done manually, by calling get_datablock_for_write function.

This function get's an original datablock and returns it's copied version. For sure it makes sure datablock is getting copied only once, by storing a pointer to the copy in a hash and uses this has to detect whether datablock has been already copied.

Example. Lets look into BKE_object_handle_update_ex function, which calculates object's matrix in case recalc flag has any of OB_RECALC_ALL bits. Currently it simply does:

BKE_object_where_is_ex(scene, rbw, object, NULL);

It is obviously a case when object datablock is modifying and it need to be copied here. After Copy-on-Write integration the code above becomes:

object = get_datablock_for_write(object);
BKE_object_where_is_ex(scene, rbw, object, NULL);

This will ensure renderer and viewport are not trying to write different matrices to the same object and they'll be using own copy of the object.

For sure we might try being smarter here and do copy only if object's matrix is different, but this only adds an extra code complexity.

The object itself is nicely copied for the current context (viewport or render), but other objects might reference it via parenting or modifier settings and they need to know copied version of the object somehow. This actually applies to any datablock which gets copied - everyone who uses it need to use it's copied version.

Instead of doing cascade copying, modifying pointer to a datablock which has been just copied, here's a function called get_datablock_for_read. This function gets an original datablock and either returns it's copied version from the hash (if it exists) or just returns the same exact datablock which was passed to it.

Example. Lets look into MOD_boolean.c:applyModifier. Currently it does

dm = bmd->object->derivedMesh;

Wouldn't run into details of creating derivedMesh if it doesn't exist yet issue. The idea here is that modifier requires operand object's derivedMesh and transformation matrix. With Copy-on-Write approach modifier shall do this:

Object *operand_object = get_datablock_for_read(bmd->object);
dm = operand_object->derivedMesh;
/* use operand_object->obmat instead of bmd->object->obmat */

Pretty much straightforward change.

Render/Dupli-group

For the render and dupli-group contexts Copy-on-Write happens as a part of scene graph update as was shown above.

Once all related dependency graph and scene update functions are using Copy-on-Write approach, conflict between viewport and render will disappear.

As an additional note here, with Copy-on-Write we don't need to have derivedRender (which was introduced in the branch a while ago). Both render engine and viewport will use object's derivedFinal. This is possible because modifier stack might copy the object, so render engine and viewport does actually have different object copies. This isn't likely to introduce noticeable memory overhead: sizeof(Object) is couple of magnitudes down comparing with derivedMesh anyway.

Viewport

Copy-on-Write for render or dupli-group purposes will work just fine, but viewport requires a bit special approach. This is because viewport tools are actually allowed to write data to original DNA structures which can not happen if a copy of datablock being created on write.

So when viewport tool modifies the object, it shall not create a copy but shall update original DNA instead. This might be solved by not calling get_datablock_for_write from the tools, but in lots of cases it's not obvious whether some generic function is used by a viewport tool or by render engine.

Easy and elegant solution would be to use EvaluationContext for Copy-on-Write routines. This EvaluationContext already contains flags whether update happens for the render of viewport purposes. Using this context get_datablock_for_write could decide to always return the original datablock if context is configured for the viewport.

Synchronization

There're couple of cases when synchronization between edited state of scene and copied objects storage is needed. This is needed because of two main reasons:

• Copied objects shall not hang around in the memory to prevent any sort of memory overhead.
• Copies could not be dropped from the storage if they're actually used by other objects (which means it's not possible to be lazy and just wipe all copies on scene graph update).

Object Update

Editing scene from the viewport should lead to copy of the object to be update as well. In this particular context it's an edits which doesn't change scene graph topology (like moving the object, but not deleting the object).

Proposed assumption here is to that only copies associated with viewport context gets updated on scene edit, and that there's no need to propagate update to copies associated with render context.

It's not a big deal if editing the scene during the rendering sometimes giving update lags.

Another assumption here is that database might only could be copied by it's own update function, and no datablock is allowed to call get_datablock_for_write for another datablock. This is actually totally sane assumptions, otherwise there'll be all sorts of threading conflicts.

Taking all this assumptions into account allows to make the following statement valid: copied datablocks are to be deleted when their original datablock is tagged for the update.

This way when updates are being flushes to the dependencies, dependency graph itself takes care of getting rid of copies for datablocks which are to be updated.

This would require having update flag a generic ID property, so dependency graph fully knows how to handle things like materials and textures (which currently doesn't have and update flags).

Scene Graph Editing

When doing edits to a scene which changes it's graph topology it is very much likely changing one datablock would make other datablocks' copies no longer needed (for example when removing Empty with dupli-group or changing dupli-group settings).

Undo Stack

Currently undo/redo totally equals to reading file from scratch, which implies full scene graph rebuild and update of all visible objects.

This is not so much optimal solution, but being smarter here is really a separate rather huge project.

But for now we could safely wipe all evaluation contexts after undo/redo, this is not gonna to lead to any artifacts or performance impact.

Fit into current design, ownership

Copy-on-write extends an idea of EvaluationContext which was introduced during this GSoC.

So now EvaluationContext will become an owner of copied datablocks (the hash map mentioned above). And EvaluaitonContext should be passed to get_datablock_for_write and get_datablock_for_read functions, so they know how to handle viewport and where to get hash from.

This seems the least changes required to the code, since EvaluationContext is need to be known in all object-update routines anyway. From the code side point of view, adding copy-on-write support would just replacing direct datablock access (object, mesh, materials and so) with a get_datablock funtions.

Pretty much straightforward changes and the only major question at this point is who owns EvaluationContext.

In case of EvaluationContext configured for render cotext it's easy: render engine is an owner of evaluation context. It creates the context before updating scene for render and frees it after the render.

For the viewport there're multiple ways, but for now Global could be an owner of EvaluationContext. In the furure when per-window scene/time is allowed viewport's EvaluationContext would be moved to the window.

Short Story

So to make long story short and to summarize design overview:

• Two API calls:
  • get_datablock_for_read if user only reads from the datablock

This function returns the same datablock which was passed to it if it was never copied-on-write before.

• • get_datablock_for_write if user modifies the datablock

This function returns a copy of given datablock, ensuring copy only happens once using hash of original->copied datablock.

• Extends EvaluationContext idea:
  • EvaluationContext is an owner of copied datablocks.
  • Global is an owner of EvaluationContext used for viewport.
  • Render engine does have it's own EvaluationContext.

Having explicit data/state separation is rather confusing and requires lots of changes all over the shop to port all tools and objects usage to the new system. And in fair huge amount of cases such a separation is not needed because render/viewport (or dupligroups) conflicts are not so commonly happens.

The idea of copy-on-write (COW) is to allow to have Object structure which is getting copied when update routines writes state (foe example, Object->obmat) to the object.

This approach seems to require the least amount of changes which are needed to make to existing code to solve object state conflicts.

Open Question

For now only one major question: who will own EvaluationContext used for dupli-group with local time offset evaluation? There're number of options here:

• Local dependency graph owns EvaluationContext.
• Someone would need to own local depdendency graph anyway (?), so he might also own EvaluationContext.
• Object might have EvaluationContext for it's dupli-group.

Think actual decision is to be made here after we know exactly how local time offset is gonna to be implemented.