User:Phonybone/PhysicsRoadmap

From BlenderWiki

Simulation Framework

[Scene level instead object/modifiers, simulaneous stepping, depsgraph integration, object interaction, constraints?] One pervading problem with Blender's physics simulations is the attachment of simulations to objects. All the current simulation systems are implemented as modifiers on objects. The reason for this is that modifiers provide a convenient way of reacting to changes in the scene using the dependency graph and to advance a simulation on frame steps.

However, there are fundamental differences between the concepts of modifiers and iterative simulations:

• Modifiers can be calculated at any point in time based on other data in the scene (e.g. object locations and meshes)
• Simulations must be calculated step-by-step based on data from the previous (sub)frame

It helps to think of these differences in terms of State: The state of an object is the combination of all its data at a given point in time. The state of the scene is simply the combination of all object states and additional scene/world settings.

A state can be valid or not: The state is valid if it represents the correct result for the settings of an object at that point in time. When the user changes relevant settings or moves to a different frame the state of an object is usually outdated and becomes invalid, necessitating a recalculation.

The predominant paradigm in Blender is that there is 1 single state for the current frame. Every time the user changes a setting or the current frame, the depgraph reevaluates each object, which drops the current state and replaces it with a new one.

The scene state that a modifier or constraint has access to during this evaluation process is a mixture of old and new object states. The job of the depgraph is to sort the objects such that each object only accesses new states of the objects it depends on. This works fine in cases where a clear hierarchy can be established, e.g. for parent/child relationships, but fails in cases where there are cyclic dependencies between objects. Luckily in most cases encountered with modifier or constraint relationships such cyclic dependencies can be avoided.

Now let's look at some real dependency cycle cases:

• IK Chains: Each bone's position depends on both the previous and next bone in the chain to reach a sort of minimal energy state for the whole chain.
• Mesh cage binding ("MeshDeform" modifier): Harmonic coordinates for each vertex are calculated, which also defines a kind of minimal energy state of the mesh as a whole.
• Rigid Body Collisions: 2 (or more) dynamic rigid bodies collide with each other, the resulting forces for each body depend on the others.
• Interaction of different physics systems: E.g. fluids reacting to rigid bodies falling into them, at the same time excerting forces through buoyancy and inertia.

What these systems have in common is that they must satisfy a "global" condition involving all the participants. This means that the system can not be calculated one-by-one, the objects/bones/bodies/etc. can not be sorted in a definite order to produce the correct result. Instead the equations governing those systems must be solved in an iterative way, meaning a specific state is chosen as a starting point and the result is approximated by repeatedly calculating small improvements.

There are 2 different classes of iterative solvers used here, depending on the type of initial state they use:

1. Instantaneous Solvers (modifiers, constraints): The initial state is a rest state, i.e. the bone rest position or the initial mesh geometry.
2. Time-based Solvers (physical simulations): The initial state is the state of the system in the previous frame.

Due to the fact that all instantaneous solvers used in Blender are sub-systems contained within mesh or armature objects, it is relatively easy to implement solvers for them that fit into the current object-based depgraph system. When evaluating these systems the solver has full control over the state of all the data. There may be exceptions to this rule, but for the purpose of this document let's consider these solvers unproblematic.

Time-based solvers on the other hand exhibit a flaw in the object-based structure: Since the solver needs to take into account all the components participating in the simulation they can not work inside a single-object update function as soon as multiple objects are involved. Individual systems such as a fluid domain or a hair system can be evaluated on their own, but once they need to interact with other objects the initial state for the solver is not consistent any more!

Furthermore time-based solvers must get their initial state from the previous frame. The solvers can not produce the correct result if the initial state is changed by modifiers or constraints. This means that time-based solvers must be evaluated before any modifiers or constraints are applied to the state of the scene.

Conclusion

What is needed for the evaluation of time-based iterative solvers is a scene-based framework. Data for each simulation will still be stored as part of objects (though separate from modifiers), but this data is passive, meaning it will not be directly updated as part of the depgraph object updating.

The general procedure will look somewhat like this:

1) Frame change / depgraph tagging 2) simulation steps (only for frame changes) 3) animation/driver/parenting/modifier/constraint updates

Point Cache

[Alembic, Disk vs. Internal caching, automatic vs. baking]

Caching is a crucial part of any sufficiently complex workflow. Without caching, the effect of animations and simulations on mesh and other object data has to be recalculated whenever a frame change occurs. This may be feasible for relatively cheap calculations such as subsurf modifiers, but for more complex setups it quickly becomes impossible to achieve acceptable frame rates. Caching solves this problem by storing the resulting states so they can just be loaded from memory or disk, which is fast enough for smooth playback.

Currently we have essentially 2 methods for caching data, both of which have a number of drawbacks:

1. The Point Cache is used for physics simulations
2. Mesh objects can have a Mesh Cache modifier

Both of these methods have a number of drawbacks, in particular the size of the stored data. This is because the file formats used here (mdd for mesh cache, a custom binary format for point cache) are designed for storing data of a single frame. Such simple storage ignores a great deal of potential optimizations in the time domain and leads to a lot of redundant data.

Another problem in case of the point cache is that it is very inflexible. The file format supports only a fixed number of data points (vertices, particles, etc.) and the types of data that can be stored are hardcoded. These limitations prevent the use of more dynamic data in particles, like variable emission rates and user-defined attributes.

The point cache has to be refactored as a prerequisite for more advanced physics systems. Alembic would be used as a backend for a new implementation. This is a widely used open-source library which is designed for efficiently storing time-based sequences of (point-)data. The main use case of Alembic is export of whole scenes for lighting or rendering, but it can be and is used also as a point cache implementation.

Alembic has a wide range of supported data types and these can be combined freely for any kind of data structure, which allows much more flexible attribute layers in mesh and particle data. Variably sized data set, which is important for particles, can also be implemented, by extending existing standard schemas.

Mesh caching could also be unified with other point cached data using Alembic (after all, this is what Alembic is specifically designed for). A thin API layer will be added to integrate the point cache into Blender. All caching can then use consistent preferences like storage folders, packing in .blend files (aka memory cache), compression setting and so on.

A very desirable side effect of using Alembic as a cache backend is that we get a regular exporter/importer almost for free. Collecting the whole scene in a single exported file is straightforward once the individual geometry schemas (meshes, particles) have been defined. This would be a valuable tool for integrating Blender into larger pipelines.

Particles

With the help of the new point cache it becomes a lot easier to implement a powerful particle system. The two most important limitations of the existing system can be resolved quite easily then:

• Fixed buffer size (this prevents things like animated emission rates and flexible reactions)
• Hardcoded attributes

The particle system essentially becomes a description of data attributes (comparable to custom data layers in meshes). These attributes can be either

• mandatory (e.g. unique ID/index layer, positions)
• standardized but not required (velocity, mass, size, ...)
• users-defined for customization

An API layer will allow basic manipulations of the particle data, i.e. adding/removing particles and reading/writing attributes.

The API can get python bindings via RNA, although it should be expected that this is not a particularly fast way of accessing massive data sets. Further down the line the API can be integrated into a dedicated scripting language using stronger optimizations (see XXX). This will also be the basis for a node system.

Dupli API

Duplis are an efficient way of adding detail to a scene without a large memory footprint. They work reasonably well for rendering, but the methods of actually generating such instances are fairly limited. Also dupli instances are not generally available for physics simulations yet.

To make dupli instances a viable tool in particle and rigid body simulations they should get some improvements to their API. The system is largely hardcoded at this point and doesn't allow a lot of customization. The API should be formalized more to make it possible to extend the dupli generators without creating spaghetti code issues (which is starting to become a problem there due to recent modifications for cycles particle rendering features).

In particular it would be very useful if custom data could be associated with dupli instances, which can then be accessed in shaders. A typical example would be using the particle age to fade between two color variations or textures. This could be achieved by allowing arbitrary data layers in dupli objects, mirroring the attribute layers in particles.

In terms of implementation the way duplis are generated can be improved a lot. Currently they are generated as a linked list, which is far from efficient for larger datasets. A more optimized approach could be to generate duplis on-the-fly, using fixed-size pre-allocated blocks. That way the memory requirements are constant and predetermined while the overhead of frequent function calls is still largely avoided.

On Scripting and Node Systems

The improvements described so far are all fairly conservative in that they can be implemented with a fixed set of features that work together in predefined ways (Particles as mentioned are also only a basic data description system with an API, more about particle nodes below).

The next couple of sections will describe features which really benefit from, or even necessitate, the use of more complex programmable systems. The term programmable is used in a broad sense here, meaning the combination of pre-defined operations in a sequence with shared data storage. This can be a classic text-based compiler as well as a graphical node-based "language".

In fact using both of these interpretations together has a number of advantages over pure text or node systems. What this means is that a programming language with a parser/compiler forms the backbone of a scriptable feature. On top of this a node system provides a more accessible and intuitive UI layer.

The parser/compiler can be executed at runtime, which means that new scripts can be created dynamically in addons. Python fills the same role for general purpose scripting in Blender already. But preferably a domain-specific language (DSL) should be developed, since Python's syntax has no static types, which limits its usefulness for nodes without further metadata and also prevents a number of optimizations. High-performance code is a key goal of using a runtime compiler, since modifiers, simulations and textures all deal with large amounts of data that need to be processed frequently.

Node systems are the UI representation of certain functions in the underlying language. Each socket of a node is a symbolic representation of a function parameter or return value. Connecting two nodes is equivalent to storing the output of one node in a variable and then passing that variable to the second node's function. Unconnected inputs and other properties associated with a node can be simple constant values. A key advantage of using a runtime compiler is that it allows generating a combined piece of code for a node tree as a whole. That way a lot of optimizations such as constant folding are possible which simply can not be performed when each node's function is a precompiled blackbox.

The syntax of a domain-specific language can be tailored to the needs of node systems. A good example is the Open Shading Language (OSL), which is a language definition as well as an implementation library. It uses C-like syntax in general, but has special keywords to make it more easily usable in shader networks, i.e. node graphs. In many cases the node doesn't even have to be defined explicitly but can be generated automatically from a piece of code and some sparse metadata.

Improved Effectors

Effectors are force fields and colliders in Blender code terminology. They are a shared feature in most physics systems, but contrary to their importance their implementation is rather crude and inefficient.

Despite the fact that both colliders and force fields are shoehorned in the same API they are actually quite different in their application to physical simulations, so they should be vested with seperate APIs.

Colliders

Colliders are any kind of surface objects (usually meshes) with which simulated elements can collide (whatever that means in detail).

The ways in which "collision" is defined and calculated varies greatly among different types of simulations (e.g. particles vs. rigid bodies vs. fluids). In fact the standard handling method defined for colliders is basically only used for particles, while other simulations use their own interpretation of the collider settings. So for the sake of consistency it would be best to deliberately avoid any concrete calculation of collision reactions in the basic collider API and simply let each simulation decide how to interpret a collision event.

Most settings for colliders can be standardized and shared between different types of simulation, for example "bounciness" (energy absorption) or friction. However, it may be desirable to have different settings for each simulation interacting with a collider. So as a first generalization a collider may have a list of collision settings, each of which can be enabled selectively for some simulation types.

But stopping there would only go half the way. Collision can be useful for a lot of non-standard effect combinations, e.g. rigid body collisions that spawn new particles, shader changes, etc. The required flexibility can not be achieved with a hard-coded system in a sensible way. Instead the collider reaction needs to be scriptable.

Texture Nodes

Scripting Language