Page MenuHome

Depsgraph: support safe physics collision cycle removal.
Needs RevisionPublic

Authored by Alexander Gavrilov (angavrilov) on Sun, Dec 29, 6:20 PM.

Details

Summary

Currently depsgraph code assumes that any dependency cycle is an
error, and it is reasonable to provide no behavior guarantees.

However, in the case of physics collision, cycles are actually
supported in a limited way by the underlying system via using
the saved collision data from the previous frame. It is also
reasonable for the user to want multiple cloth objects to collide
with one another, and it worked that way safely in 2.79.

In order to allow using this behavior, dependency graph should
know which relations are collisions, and prefer deleting them if
possible when a cycle is detected; it should also avoid excessive
message spam.

This adds a new relation flag that marks collision relations.
When resolving a cycle, collision relations going backward in
the alphabetic order of object names are chosen as primary
candidates for removal; this predictably resolves all cycles
between multiple objects all colliding with each other.

The depth first search cycle detection algorithm had to be
enchanced to unwind the stack to the relation being removed;
otherwise it cannot correctly detect all cycles. This would
already been a problem with the godmode flag, but it's not
that obvious there, as that flag is rare.

Diff Detail

Repository
rB Blender
Branch
temp-angavrilov-cloth-collision-cycles (branched from master)
Build Status
Buildable 6124
Build 6124: arc lint + arc unit

Event Timeline

However, in the case of physics collision, cycles are actually supported in a limited way by the underlying system via using the saved collision data from the previous frame.

This is VERY fragile assumption, which nowadays never work when you render animation (because there is simply no previous state in this case). It also known to cause issues when you open file which is somewhere in the middle of timeline.

In order to allow using this behavior, dependency graph should know which relations are collisions, and prefer deleting them if possible when a cycle is detected.

Not sure what exactly you mean by "should" here.

In a more ideal world the physics solver should have a dedicated depsgraph node which will receive all colliding objects, run solver, calculate momentums and what not, apply them, continue with modifier stacks of every colliding object. Just similar to IK solver and rigid body simulation (to certain extent).

This is a bigger project than this patch though. Not sure what are the plans about physics solvers and if there is nothing planned in the observable future then depsgraph "could" allow the behavior you've described. With proper indication that this is not amortized way of designing features and that it's caused by design limitation in physics area.

This adds a new relation flag that marks collision relations.

What are the rules of using this flag? I see similar cases when same components passed to DEG_add_object_pointcache_relation will be marked as PHYSICS_BREAK_CYCLES and sometimes they will not.
That's confusing and will likely be fragile (tweaking those flags to solve specific report without being able to easily validate all previously fixed cases).

When resolving a cycle, collision relations going backward in the alphabetic order of object names are chosen as primary candidates for removal; this predictably resolves all cycles between multiple objects all colliding with each other.

That's interesting. Is it possible to extend this predictable cycles solver to other cases as well (not just to physics relations) ?

The depth first search cycle detection algorithm had to be enchaced to unwind the stack to the relation being removed; otherwise it cannot correctly detect all cycles.

Can this be applied as a separate patch?

This would already been a problem with the godmode flag, but it's not that obvious there, as that flag is rare.

The godmode flag was introduced to avoid possible relation removal from INIT to CLEANUP, which was causing weird and wonderful threading issues. Think we should be able to remove this flag and adjust cycles solver in a way that it prefers to kill relation between two different ID, or between different components of the same object, and as last resort kill relation inside same component.
Just saying, this is a separate story.

source/blender/depsgraph/intern/builder/deg_builder_cycle.cc
52

It's relation, not edge. We should keep terminology consistent.

What is a node have multiple input relations? Is it get stashed when ANY or ALL input relations are removed?

184

Use clear naming which will indicate what exactly you are selecting the relation.

Are you selecting it to be the one which will be used to break cycle? select_relation_to_break_cycle.

186

check is too generic. Are you checking for the relation being valid? Relation being suitable for breaking a cycle?

206–221

Such refactor can (and likely should) happen separately.

source/blender/depsgraph/intern/depsgraph_physics.cc
143

Why in the case above DEG_OB_COMP_GEOMETRY relation allows to break cycle but not here? What are the rules?

Sergey Sharybin (sergey) requested changes to this revision.Thu, Jan 2, 11:28 AM
This revision now requires changes to proceed.Thu, Jan 2, 11:28 AM

This is VERY fragile assumption, which nowadays never work when you render animation (because there is simply no previous state in this case). It also known to cause issues when you open file which is somewhere in the middle of timeline.

Physics is inherently stateful, so not having any previous state means by the time render is performed all physics must be cached (baked). If you want to somehow compute physics "without state", you basically require a way to backtrack in time until you find a cached previous state or reach the start of timeline. You simply can't simulate physics just from nothing.

Btw, the collision modifier is already stateful: it stores not only current position, but also calculates velocity by comparing with the previous position, and that is used later for subframes and collision math.

Also, unrelated to this patch, I'm actually thinking about adding even more state: I want to know the velocity of the object for applying some forces - basically I want an option for the Drag force that would drag things together with the movement of the effector, so you can e.g. pull on cloth. Any suggestions re how to fit this in?

In order to allow using this behavior, dependency graph should know which relations are collisions, and prefer deleting them if possible when a cycle is detected.

Not sure what exactly you mean by "should" here.

Well, the cycle solver must know which relations should have special behavior.

In a more ideal world the physics solver should have a dedicated depsgraph node which will receive all colliding objects, run solver, calculate momentums and what not, apply them, continue with modifier stacks of every colliding object. Just similar to IK solver and rigid body simulation (to certain extent).
This is a bigger project than this patch though. Not sure what are the plans about physics solvers and if there is nothing planned in the observable future then depsgraph "could" allow the behavior you've described. With proper indication that this is not amortized way of designing features and that it's caused by design limitation in physics area.

Thing is, since collision is a modifier in the stack, you can do weird stuff with it, like adding more modifiers between cloth and collision. This would require redesigning the collision feature.

This adds a new relation flag that marks collision relations.

What are the rules of using this flag? I see similar cases when same components passed to DEG_add_object_pointcache_relation will be marked as PHYSICS_BREAK_CYCLES and sometimes they will not.
That's confusing and will likely be fragile (tweaking those flags to solve specific report without being able to easily validate all previously fixed cases).

Well, currently I only use it for relations related to collision and depending on geometry, but not forces, or collision dependencies on object transform etc. I.e. those relations that actually cause the cycles when you have multiple cloth objects.

Btw, what is that point cache relation thing all about?

When resolving a cycle, collision relations going backward in the alphabetic order of object names are chosen as primary candidates for removal; this predictably resolves all cycles between multiple objects all colliding with each other.

That's interesting. Is it possible to extend this predictable cycles solver to other cases as well (not just to physics relations) ?

Maybe, but this is mainly targeting dense cyclic sub-graphs, like when you have a set of objects which each depend on all of the others. Sorting the objects in some stable way and killing 'wrong direction' links is a simple and reliable way to solve it. This heuristic is also only guaranteed to work if you can kill any relation in the cycle, so in a hybrid physics/non-physics cycle involving multiple objects it can fail to solve the cycle, depending on object naming.

The depth first search cycle detection algorithm had to be enchaced to unwind the stack to the relation being removed; otherwise it cannot correctly detect all cycles.

Can this be applied as a separate patch?

I guess so.

This would already been a problem with the godmode flag, but it's not that obvious there, as that flag is rare.

The godmode flag was introduced to avoid possible relation removal from INIT to CLEANUP, which was causing weird and wonderful threading issues. Think we should be able to remove this flag and adjust cycles solver in a way that it prefers to kill relation between two different ID, or between different components of the same object, and as last resort kill relation inside same component.
Just saying, this is a separate story.

It's mainly the case that if you kill a relation up the stack, you have no right to be in that sub-tree anymore, and have to backtrack and unwind the stack. Otherwise, for example, you may encounter a case where you find another cycle, but you have seemingly 'already resolved it' via that killed relation, and that completely breaks the logic of the algorithm. Without backtracking the cycle resolver totally fails on 3 inter-colliding objects.

source/blender/depsgraph/intern/builder/deg_builder_cycle.cc
52

It is stashed if during DFS we kill a relation that is already in the stack (rather than the 'leaf' currently being checked), and thus must abandon the subtree. Potentially it could even go to NOT_VISITED, but although I didn't try to prove it, I have a hunch that it's safe to retain the num_visited_children counter values, so the state of such nodes is in fact distinct, and thus I added a new enum value.

184

Actually, I completely disagree. With the addition of a function argument, this is a generic 'select first relation that matches predicate' function. The name exactly reflects what it does.

186

predicate would be more appropriate I guess.

source/blender/depsgraph/intern/depsgraph_physics.cc
143

Mainly, because the collision modifier has cached state, so it's safe to kill dependencies on it, provided there is a reverse dependency to prevent simultaneously reading and updating it. I didn't check how forces work, so it might not be safe.

Btw, the collision modifier is already stateful: it stores not only current position, but also calculates velocity by comparing with the previous position, and that is used later for subframes and collision math.

This is fine if you are baking or doing playback in viewport starting from frame 1.
It wouldn't work if you start animation render without baking or caching first.

Also, unrelated to this patch, I'm actually thinking about adding even more state: I want to know the velocity of the object for applying some forces - basically I want an option for the Drag force that would drag things together with the movement of the effector, so you can e.g. pull on cloth. Any suggestions re how to fit this in?

That very quickly escalates to a desire of pulling cloth based on a rigged character. Object velocity will be 0 in this case, but vertex velocity will not.

Not really sure what is the best approach here. Here are the following cases which doesn't fit the idea of using previously known object state:

  • Animation render (no previous state, current state is evaluated from scratch for every frame), or rendering of single frame from command line
  • Motion blur render (order in which scene will be updated for subframes is not strictly defined)
  • Fast-forward in the timeline (jump from frame 50 to 100)
  • Framedropping/AV sync
  • Transform (what is the desired speed when you move object)
  • Probably something else.

Anyway, there should be a solution, but lets move discussion somewhere else.

Well, the cycle solver must know which relations should have special behavior.

I disagree with such wording. Area must be designed in a way that doesn't require other areas to work around its weirdeness.

Btw, what is that point cache relation thing all about?

Physics gets cached to a pointcache. This cache is to be invalidated when you modify scene (i.e. when you move object around, change physics settings and so on).

source/blender/depsgraph/intern/builder/deg_builder_cycle.cc
52

Such description should be easier to discover than looking into code review page. IO.e. by being written in the comment in the code itself.

184

The name exactly reflects what it does.

No, it doesn't.
Even as you've mentioned in this comment, there is a difference between select relation and select first relation that matches predicate.

Trying to be too abstract and generic for no reason does not help understanding what's going on.

Btw, the collision modifier is already stateful: it stores not only current position, but also calculates velocity by comparing with the previous position, and that is used later for subframes and collision math.

This is fine if you are baking or doing playback in viewport starting from frame 1.
It wouldn't work if you start animation render without baking or caching first.

From frame 1 is the ONLY way physics can be evaluated. You can't jump in time, unless you have it cached.

In other words. if you have it cached, you can jump in time, and you don't care about state because nothing is being evaluated anymore. If you don't have it cached, then you care about state, and you inherently can't jump in time.

Also, unrelated to this patch, I'm actually thinking about adding even more state: I want to know the velocity of the object for applying some forces - basically I want an option for the Drag force that would drag things together with the movement of the effector, so you can e.g. pull on cloth. Any suggestions re how to fit this in?

That very quickly escalates to a desire of pulling cloth based on a rigged character. Object velocity will be 0 in this case, but vertex velocity will not.

When you speak about vertex velocity you get into the area of collision - it has friction, although I'm not sure how well it works.

Here I'm mainly thinking it would be good to have a fully custom user controlled 'pull' effector, so instead of trying to simulate the real physics by sandwiching cloth between colliders or whatnot, you could just directly apply a force where you want the cloth to be pulled, and be done with it. Then you can just animate whatever is actually 'causing' the pull on top without it being an actual part of the simulation. I.e. it would be a targeted tool for more directly making the cloth do what the animator wants, instead of a more hands off 'realistic' simulation.

Not really sure what is the best approach here. Here are the following cases which doesn't fit the idea of using previously known object state:

  • Animation render (no previous state, current state is evaluated from scratch for every frame), or rendering of single frame from command line
  • Motion blur render (order in which scene will be updated for subframes is not strictly defined)
  • Fast-forward in the timeline (jump from frame 50 to 100)
  • Framedropping/AV sync
  • Transform (what is the desired speed when you move object)
  • Probably something else.

None of those things can or should be simulating physics. Physics is inherently stateful, and has to be evaluated in order.