Implement operation to simplify negated join on CsgTree

[esseivaju]

Required to generate infix notation for #1286 as part of #1282. The goal is to eliminate negated Join operations as those cannot be represented with infix notation.

[esseivaju]

@sethrj @elliottbiondo I still need to add tests and finalize the implementation but I think the logic is good now.

[esseivaju]

I'll add more complex test cases but this is ready for an initial review

[esseivaju]

Great commenting of what's going on! I know it's something of a work in progress, but a little restructuring would make this easier to review 😅 I think making the big function into a detail class (even a single-header one) will make it easier to read and process; that'll also make it easier to design a "visitor". Also don't forget the Overload class in corecel/cont/VariantUtils.hh as an alternative to writing a whole standalone class.

I had to add comments or even I'd get lost during the implementation. This function is getting unwieldy and way too long as you mentioned, thanks largely to the rough variant interface... I wanted to get a few more complex test cases working first, now that it's done it might be worth double-checking that the simplification is the logic you'd expect and that I didn't make any mistakes in the test strings. I had to get the pen and paper out for this, I think they are correct. Next, I'll refactor the function to make it shorter and easier to parse.

[esseivaju]

It's in a better state now. It could still use better comments and variable names but at least it's easier to review. I think the most important thing to check is the correctness and exhaustiveness of test cases.

[esseivaju]

Is it possible to initialize the regions/volumes/etc after we simplify the tree so that they directly use the correct node_id? If an arbitrary node can be referenced by an external component, there's no guarantee it still is in the simplified tree. For example, if we have a Negated{Joined{}} and that joined node has no other parents, it will be converted to the opposite join. If someone was keeping a node_id pointing directly to that joined node, there is no equivalent of the original joined node in the simplified tree.

[sethrj]

@esseivaju I should've thought to mention this before, but unfortunately it's not going to be that easy: consider the following, a union of two spheres inside a volume enclosed by a larger sphere:

flowchart TB
  n00["t"]
  n01["~"]
  n01 --> n00
  n02["[EXTERIOR]\nbound@s"]
  n03["bound\n~"]
  n03 --> n02
  n04["bottomsph@s"]
  n05["bottomsph\n~"]
  n05 --> n04
  n06["topsph@s"]
  n07["topsph\n~"]
  n07 --> n06
  n08["union\n|"]
  n08 --> n05
  n08 --> n07
  n09["~"]
  n09 --> n08
  n10["fill\n&"]
  n10 --> n03
  n10 --> n09
subgraph Volumes
  v02(["[EXTERIOR]@global"])
  v08(["union_vol"])
  v10(["fill_vol"])
end
  v02 <--> n02
  v08 <--> n08
  v10 <--> n10

We need to keep a reference both to fill_vol and union_vol.

Is the easy solution just to replace ~join(op, ...) with join(other_op, ~...) on insertion to the CSG tree (which would allow us to skirt the "no backward substitution" requirement by injecting negated daughter nodes)? I was hoping we could do this with a "simplification" step but perhaps adding this to CsgTree::insert is the best way...

[esseivaju]

I don't think moving that to insert would solve the problem. In your example, it's impossible to keep the union node and have an equivalent tree after simplification even if you do it during insertion, you'd create a new root. The intersect_vol volume would have to point to the negated union. If the graph below is valid after simplification, then it's easy to provide a mapping of old volume to new (negated) volume.

flowchart TB
  n00["t"]
  n01["~"]
  n01 --> n00
  n02["[EXTERIOR]\nbound@s"]
  n03["bound\n~"]
  n03 --> n02
  n04["bottomsph@s"]
  n06["topsph@s"]
  n08["intersect\n&"]
  n08 --> n04
  n08 --> n06
  n10["fill\n&"]
  n10 --> n03
  n10 --> n08
subgraph Volumes
  v02(["[EXTERIOR]@global"])
  v08(["intersect_vol"])
  v10(["fill_vol"])
end
  v02 <--> n02
  v08 <--> n08
  v10 <--> n10

[esseivaju]

@sethrj where is the Volume<->NodeId mapping stored?

[sethrj]

@esseivaju These aren't internally saved anywhere in the CSG tree, but there's a vector of volumes in CsgUnit at orange/orangeinp/detail/CsgUnit.hh:

    std::vector<NodeId> volumes;  //!< CSG node of each volume

These will all be final at the time when we simplify the tree.

[esseivaju]

And is this not going to pose an issue to have that extra disjoint tree when the tree is converted to a logical expression? Maybe we'll need to select which roots we want to convert.

[sethrj]

@esseivaju Yeah. We're creating the logical trees from each of the volumes as a root. Lots of the time, a given volume doesn't touch every node in the tree.

[esseivaju]

Okay, I've moved the volumes to the CsgTree and updated the simplification example. I'll need to add more complex test cases. This now simplifies to the following tree:

flowchart TB
  n00["t"]
  n01["~"]
  n01 --> n00
  n02["topsph@s"]
  n03["bottomsph@s"]
  n04["topsph\n~"]
  n04 --> n02
  n05["bottomsph\n~"]
  n05 --> n03
  n06["intersect\n&"]
  n06 --> n02
  n06 --> n03
  n07["union\n|"]
  n07 --> n04
  n07 --> n05
  n08["[EXTERIOR]\nbound@s"]
  n09["bound\n~"]
  n09 --> n08
  n10["fill\n&"]
  n10 --> n06
  n10 --> n09
subgraph Volumes
  v02(["[EXTERIOR]@global"])
  v08(["union_vol"])
  v10(["fill_vol"])
end
  v02 <--> n08
  v08 <--> n07
  v10 <--> n10

[esseivaju]

@sethrj I think this is ready for another look. The only thing I'm not convinced of yet is that MatchingNodes::modified is a bit overloaded and factorizing it into 3 variables would make the algorithm easier to follow.

[esseivaju]

This is the most complicated test problem, the ATLAS tilecal cylinder segment. Roots 16 and 27 are preserved so we have to duplicate many nodes.

Before simplification (mermaidchart):

flowchart TB
  n00["00:t"]
  n01["01:~"]
  n01 --> n00
  n02["02:S0"]
  n03["03:S1"]
  n04["04:~"]
  n04 --> n03
  n05["05:S2"]
  n06["06:~"]
  n06 --> n05
  n07["07:&"]
  n07 --> n02
  n07 --> n04
  n07 --> n06
  n08["08:S3"]
  n09["09:~"]
  n09 --> n08
  n10["10:&"]
  n10 --> n02
  n10 --> n04
  n10 --> n09
  n11["11:~"]
  n11 --> n10
  n12["12:S4"]
  n13["13:S5"]
  n14["14:&"]
  n14 --> n12
  n14 --> n13
  n15["15:&"]
  n15 --> n07
  n15 --> n11
  n15 --> n14
  n16["16:~"]
  n16 --> n15
  n17["17:S6"]
  n18["18:S7"]
  n19["19:~"]
  n19 --> n18
  n20["20:&"]
  n20 --> n06
  n20 --> n17
  n20 --> n19
  n21["21:&"]
  n21 --> n09
  n21 --> n17
  n21 --> n19
  n22["22:~"]
  n22 --> n21
  n23["23:S8"]
  n24["24:S9"]
  n25["25:&"]
  n25 --> n23
  n25 --> n24
  n26["26:&"]
  n26 --> n20
  n26 --> n22
  n26 --> n25
  n27["27:~"]
  n27 --> n26
  n28["28:&"]
  n28 --> n15
  n28 --> n27

after simplification (mermaidchart):

flowchart TB
  n00["00:t"]
  n01["01:~"]
  n01 --> n00
  n02["02:S0"]
  n03["03:~"]
  n03 --> n02
  n04["04:S1"]
  n05["05:~"]
  n05 --> n04
  n06["06:S2"]
  n07["07:~"]
  n07 --> n06
  n08["08:|"]
  n08 --> n03
  n08 --> n04
  n08 --> n06
  n09["09:&"]
  n09 --> n02
  n09 --> n05
  n09 --> n07
  n10["10:S3"]
  n11["11:~"]
  n11 --> n10
  n12["12:|"]
  n12 --> n03
  n12 --> n04
  n12 --> n10
  n13["13:&"]
  n13 --> n02
  n13 --> n05
  n13 --> n11
  n14["14:S4"]
  n15["15:~"]
  n15 --> n14
  n16["16:S5"]
  n17["17:~"]
  n17 --> n16
  n18["18:|"]
  n18 --> n15
  n18 --> n17
  n19["19:&"]
  n19 --> n14
  n19 --> n16
  n20["20:|"]
  n20 --> n08
  n20 --> n13
  n20 --> n18
  n21["21:&"]
  n21 --> n09
  n21 --> n12
  n21 --> n19
  n22["22:S6"]
  n23["23:~"]
  n23 --> n22
  n24["24:S7"]
  n25["25:~"]
  n25 --> n24
  n26["26:|"]
  n26 --> n06
  n26 --> n23
  n26 --> n24
  n27["27:|"]
  n27 --> n10
  n27 --> n23
  n27 --> n24
  n28["28:&"]
  n28 --> n11
  n28 --> n22
  n28 --> n25
  n29["29:S8"]
  n30["30:~"]
  n30 --> n29
  n31["31:S9"]
  n32["32:~"]
  n32 --> n31
  n33["33:|"]
  n33 --> n30
  n33 --> n32
  n34["34:|"]
  n34 --> n26
  n34 --> n28
  n34 --> n33
  n35["35:&"]
  n35 --> n21
  n35 --> n34

[esseivaju]

And a smaller test case with volumes:

Before:

flowchart TB
  n00["00:t"]
  n01["01:~"]
  n01 --> n00
  n02["02:S0"]
  n03["03:S1"]
  n04["04:~"]
  n04 --> n02
  n05["05:~"]
  n05 --> n03
  n06["06:|"]
  n06 --> n04
  n06 --> n05
  n07["07:~"]
  n07 --> n06
  n08["08:S2"]
  n09["09:~"]
  n09 --> n08
  n10["10:&"]
  n10 --> n07
  n10 --> n09
  subgraph Volumes
    v0["vol0"]
    v1["vol1"]
    v2["vol2"]
  end
  v0 --> n06
  v1 --> n10
  v2 --> n07

After simplification:

flowchart TB
  n00["00:t"]
  n01["01:~"]
  n01 --> n00
  n02["02:S0"]
  n03["03:S1"]
  n04["04:~"]
  n04 --> n02
  n05["05:~"]
  n05 --> n03
  n06["06:&"]
  n06 --> n02
  n06 --> n03
  n07["07:|"]
  n07 --> n04
  n07 --> n05
  n08["08:S2"]
  n09["09:~"]
  n09 --> n08
  n10["10:&"]
  n10 --> n06
  n10 --> n09
  subgraph Volumes
    v0["vol0"]
    v1["vol1"]
    v2["vol2"]
  end
  v0 --> n07
  v1 --> n10
  v2 --> n06

Without volumes, this tree simplifies to:

flowchart TB
  n00["00:t"]
  n01["01:~"]
  n01 --> n00
  n02["02:S0"]
  n03["03:S1"]
  n04["04:&"]
  n04 --> n02
  n04 --> n03
  n05["05:S2"]
  n06["06:~"]
  n06 --> n05
  n07["07:&"]
  n07 --> n04
  n07 --> n06

[sethrj]

One thing I notice (not to do with your work or in scope for this PR) is that we have join(and, [join(and, [..]), ...]) which should probably be "canonicalized" into a single join. I wonder if that can easily be implemented by NodeSimplifier...

[esseivaju]

I wonder if that can easily be implemented by NodeSimplifier...

If you know that there are no other parents (volume) for that nested join, then I suppose that the NodeSimplifier should be able to do that.

[esseivaju]

@sethrj I reworked the code to remove MatchingNodes::modified and use multiple variables instead, being more explicit about which value is needed in a given situation. I think this makes the algorithm clearer.

[esseivaju]

@sethrj I'm finally happy with the implementation so it should be good for review.