casperlamboo
commented
6 months ago The remaining issue that wall ordering was a bit odd when wall-ordering was set to "inner to outer" wasn't caused by the parent-child nesting logic, but was instead caused in the part where we use this nesting logic to create the resulting wall ordering. Below is an example of tool paths where the wall ordering went "wrong".
Since wall ordering is set to "inner to outer" the resulting nesting logic was (correctly) determined to be
graph TD;
g --> f
f --> e
e --> d
d --> b
c --> b
b --> aPreviously the logic was such that a dfs was performed on this nesting graph for every root node (blue nodes figure above). In this example the root nodes are $c$ and $g$ are root nodes. The initial root is chosen to be the tool path with the closest point to the current nozzle position. When this node would be $c$ the printing sequence would be $\langle c, b, a, g, f, e, d \rangle$. Which didn't feel ordered from inner to outer. Main issue is that wall tool path $b$ is printed before $f, g, e, d$ while $b$ is a parent of all these tool paths.
This lead me to add the following constraint: A path $u$ can only be printed if all paths $v$ for which there is an order dependency $(u, v)$ in the order requirement is done printing. This is done by keeping track of of the number of incoming edges to each path. Each time a path $p$ is handled (done processing and added to the final ordering list) the number of incoming edges of all $p$'s neighbors is decreased by $1$. When finding the next wall tool path to print the candidate wall tool paths are limited to those with an incoming edges count of 0.
Side node: this was only an issue in the situation where wall ordering is set to "inner to outer". When wall ordering is set to "outer to inner" the order requirements analog to a tree-graph. One property in a tree-graph is that all nodes have exactly one incoming edge (except for the root nodes, which have $0$ incoming edges). When such a tree is traversed handling a node makes all neighbors valid candidates as all their incoming edges are decreased from $1$ to $0$. When this setting is set to "inner to outer" instead all edges are revered. When edges are reversed in a tree-graph the graph is no longer a tree and we loose this property.
As we were only taking the very inner contour of the true extrusion polygon. There was code that would increase this area a bit, but it wasn't properly implemented, so for certain cases we would miss parent child relationships.
CURA-11388