2025-04-06

Last modified: 2025-04-06 21:59:12

• Targeted blends
• Uncommittable strings
• Clock stopped
• Constraint solving

Targeted blends

• fix whatever is the issue where the Sphere doesn't intersect with the Gyroid (add a test; it could be as simple as it messes up if you ask for a blend where one of the arguments doesn't exist)
• make it work with this.uniform() instead of P.const(), also maybe instead of using this.blendRadius or whatever, the uniform should refer to the parameter of the blend
• recompiling the shader every time
• more complex unit tests
• particularly make sure we combine multiple things into one even if there is more than one id, as long as all combinations of id take the same blend parameters
• UI for applying blends

Well I added a unit test for the thing where you request a blend where one argument doesn't exist, and it goes into infinite recursion.

OK, the infinite recursion was because distributing over the right child was creating circular references to t.left because of assigning it in the new right child after already re-assigning the new left child.

And, yeah, making it not try to apply blends where one of the arguments doesn't exist solves the problem with the sphere not being intersected with the gyroid. Great success.

I'm going to add some more complex tests before fixing the shader issues.

OK, a test with 4 objects and blends between all 6 pairs is only finding 3 successful pairs instead of 6.

My thinking is we may need to check if the tree satisfies its blends after one pass of _rewriteTree and run another pass if not. Probably there is a better algorithm though.

Applying a second pass of _rewriteTree causes infinite recursion.

How should we rewrite it?

Union(Intersection(a,b), Intersection(c,d))

becomes

Intersection(Union(a, Intersection(c,d)), Union(b, Intersection(c,d)))

becomes

Intersection(Intersection(Union(a,c), Union(a,d)), Intersection(Union(b,c), Union(b,d)))

Then what?

Well for a start, we're not even managing this much, because that is 4 pairs instead of just 3.

OK, we get infinite recursion because we can put 2 copies of a subtree into the tree. If they then get rewritten so that one is a parent of the other, then infinite recursion. So the fix is to make one of the copies a clone instead of a reference.

Still seeing infinite recursion though, hmm.

I added a check for cycles and it is not getting triggered, which maybe means we're not creating cycles, but are somehow just endlessly expanding a finite tree?

I made it print out the size of the tree, and it is never bigger than 19 nodes. Are we somehow recursing into a copy of ourself?

I don't see how.

I made it throw if it visits the same node twice, and now that is throwing, so that's a good sanity check.

But now I made it return early instead of throwing, which should cut out infinite recursion, and it doesn't! It still infinitely recurses somehow. Obviously into cloned copies instead of duplicates.

But if I remove the cloning then it still recurses infinitely! So somewhere it is constructing new nodes and recursing into them.

Since this tree has no modifiers we can ignore the code that handles modifier chains.

I made it break the recursion if it has visited more than 30 nodes, and this time it actually has interactions between 5 of the 6 pairs of nodes! Increasing that to 100 or 200 makes the tree larger but does not get to all 6 interactions.

If it possible that you actually can't do all 6? Unsure.

In fact we get to 5 pairs of primitives if we break the recursion as soon as we have seen more than 5 nodes.

I think what might be happening is it keeps noticing that it can't satisfy all 6 blends, and naively applying the distributivity rule just in case it helps. Which makes the tree bigger but doesn't satisfy all 6 blends.

Looking at it mathematically, if intersection is multiplication and union is addition, we kind of have

a*b + c*d

So how can we rewrite that to give the same answer, but have every pair of variables as immediate children of some operator?

Actually that is not equivalent, because addition doesn't distribute over multiplication? Or the other way around.

But thankfully min() and max() do distribute over each other.

So if + is min and * is max, our leaf nodes would be:

• ab = a*b
• cd = c*d
• ac = a+c
• ad = a+d
• bc = b+c
• bd = b+d

And then how do we combine them?

• abcd = ab+cd
• abc = ab+c
• abd = ab+d
• acd = a+cd
• bcd = b+cd
• abcd = abc + abd + acd + bcd?

OK, update: I made it only apply each rewrite with 50% probability, and I made it run _rewriteTree() 6 times, and kept refreshing the page, and one time it actually did get to a tree that satisfies all 6 blends!

Obviously randomly disabling some of the rewrites is not what we want, not least because it makes it non-deterministic. But it does prove that it is possible to get to a good tree using the application of these rules, just need to work out when not to apply the rule.

So I think this means some of the rewrites are undoing the good work of previous rewrites?

So maybe instead of rewriting a node just because it has unsatisfied blends, I need to rewrite a node only if doing so would get it closer to satisfying its blends.

OK, weirdly it passes if I make it rewrite left, then recurse left, then recurse right, then rewrite right. Why shouldn't it be symmetrical?

And it only needs 2 passes of _rewriteTree.

But if I run a third pass of _rewriteTree then it makes more changes to the tree! Which implies satisfiesBlends() is giving false for some subtree even when the tree as whole actually does satisfy its blends.

Probably the issue is that when we have 2 copies of some node, it's OK if not every one satisfies every blend. In fact it is impossible to do that, that's why we're making copies.

We only need a subtree to satisfy the blends of the nodes that are contained in that subtree. So this is like the problem with trying to apply blends where one argument doesn't exist, except in a subtree.

And yeah, even in the case where it passes the unit test, satisfiesBlends() is returning false for some nodes.

Because they are satisfied in a different subtree.

So how can a subtree know if there are blends that it doesn't need to handle?

Each subtree needs to pass up information saying which blends it is satisfying, and then if one subtree is satisfying a blend we don't need the other subtree to also satisfy the same blend.

Wow! That has worked! Passing now, the result looks small, the result doesn't grow if I add extra passes, and when I iterate over the tree and check that every blend is satisfied, I find that they are. And it only takes 2 iterations of _rewriteTree() - do I maybe need to keep calling _rewriteTree() until it is done? Will it always be done in 2?

The good result is:

Intersection(Intersection(Union(Union(Intersection(Sphere2,Gyroid3),Intersection(Sphere2,Box1)),Intersection(Box1,Union(Gyroid3,Box1))),Union(Intersection(Sphere2,Union(Gyroid3,Box1)),Union(Intersection(Negate(Cylinder4),Gyroid3),Intersection(Negate(Cylinder4),Box1)))),Intersection(Intersection(Union(Sphere2,Box1),Union(Sphere2,Negate(Cylinder4))),Union(Gyroid3,Negate(Cylinder4))))

And this is getting pretty gnarly. I think instead of passing around the full list of blends, plus a Set of blends you can skip, I should instead just pass around the Set of blends you need to care about.

OK, done that, not much simpler though.

The next test to add is that in:

Union(Intersection(a,b), c)

If (a,c) and (b,c) have the same blend radius then we can simply apply it at Union without having to rewrite the tree.

This is all getting really hairy and out of hand. A few obvious things:

• instead of using cloneWithSameIds() everywhere, which clones an entire tree, I should have something like "clone only this particular node without children but keep the same id"
• modifier chains should maybe be a property instead of a node type
• is there a different representation that is going to make the rewriting easier?
• can I write down the actual algorithm in pseudocode?

Something like:

rewriteTree(t, blends) :=
  rewriteTree(t.left, blendsNotHandledBy(t.right, blends))
  rewriteTree(t.right, blendsNotHandledBy(t.left, blends))
  blends = blendsNotHandledBy(t.left, blends)
  blends = blendsNotHandledBy(t.right, blends)
  if t satisfies all the blends not handled by its children:
    return
  otherwise:
    do the distributivity thing

Where blendsNotHandledBy(t, b) gives the subset of b that is not handled within t. But this pseudocode is not the same as what I've implemented, and I don't think it will work because I think we need to do the distributivity thing before recursing?

I need to get a solid idea of what the rules are for when a particular node has to handle a particular blend, when a subtree can successfully handle it, and when we need to redistribute and try again.

Uncommittable strings

There should be some strings you can write into comments that won't let you commit them, so that you can ensure temporary code doesn't get committed.

I don't know if you could already manage this by writing merge conflict markers? Or need a custom pre-commit hook.

Clock stopped

The clock stopped today after having been running for several days.

The thing that stopped it is the adjacent-arm shaft slides back and forth in its bearings, and the collar binds up in the gear. Just needs collars at each bearing to keep it located axially.

Constraint solving

https://github.com/xibyte/jsketcher

Could I nick the sketcher and constraint solver from this?

No. It says if you modify it you have to assign copyright to them, not worth it.

There is https://github.com/Salusoft89/planegcs which is a WASM port of FreeCAD's solver.