Last modified: 2025-04-08 22:10:14
< 2025-04-07 2025-04-09 >I wrote https://incoherency.co.uk/blog/stories/frep-cad-building-blocks.html over the last couple of days and came up with a few things that I hadn't seriously looked at before:
While travelling yesterday I did some thinking about targeted blends and wrote down this algorithm:
while true:
for each blend:
if !Satisfy(tree, blend):
Rewrite(tree, blend)
if all were satisfied:
break
Rewrite(t, blend):
If both args in left child and Rewrite(t.left, blend):
return true
If both args in right child and Rewrite(t.right, blend):
return true
If t.left is combinator:
distribute left
If Satisfy(t, blend):
return true
If right is combinator:
distribute right
return Satisfy(t, blend)
Satisfy(t, blend):
If args are not both under t:
return false
If Satisfy(t.left, blend) or Satisfy(t.right, blend):
return true
If all possible surface pairs need the same blend params in the full set of blends:
t.blendParams = whatever
return true
return false
I still don't like that it is maybe recursing the tree exponentially, but let's just program it and see if it works.
Other prerequisites are:
I am making some progress, but having trouble working out how to attach modifiers when doing the distributivity rewrite. I have:
M(C(a,b)) => C(M(a), M(b))
and
C1(C2(a,b), c) => C2(C1(a,c), C1(a,b))
So then
C1(M(C2(a,b)), c) => C1(C2(M(a), M(b)), c) => C2(C1(M(a),c), C1(M(b),c))
OK great, that bit is sorted.
In the "AllPairsBlends" test is it doing too much rewriting, making a tree much bigger than necessary.
I think we should always make it pick the rewrite that gets it closest to having them as siblings. Where distance is defined as the number of combinator nodes between the blend arguments.
So in Rewrite:
Rewrite that childRewrite that childI am getting disillusioned with this idea of tree rewriting. I think it doesn't work. I think the "AllPairsBlends" thing would prove it didn't work if I actually tried to look at it. I don't think it is possible to build a shape that has different radii between all pairs of surfaces.
So the easy solution is we just forget about it and say the user is responsible for organising the tree. That does lose some power though, because the "union of sphere and box, intersected with gyroid, with blend between sphere and gyroid" is not possible without duplicating the gyroid in the tree. So rewriting the tree gets you something.
But we need to make sure not just that there is an interaction between the blend argument surfaces that has the right radius, but that all interactions between those surfaces have the right radius.
But:
Intersection(Union(a,b), c) => Union(Intersection(a,c), Intersection(b,c))
This is ok even though the Union can yield (a,c), because the (a,c) interaction is handled deeper on the left hand side. So it's a
problem if there is any node in the tree where one surface can come out of one side and the other surface can come out of the other side
and we don't have the correct blend params. If both surfaces can come out of either side then we don't care about the other side.
So then if we do think it is actually impossible to apply all-pairs blends, how can we detect that case and not just keep rewriting the tree larger and larger and never making it work? Under what circumstances is it possible to satisfy all of the requested blends?
Maybe instead of starting from the existing tree and trying to rewrite to a tree that satisfies its blends, we could start from a bunch of disconnected surface pairs and build up a tree that satisfies the blends by construction.
So take each pair of surfaces, labelled with their blend params and the type of node that is their least common ancestor. Give each one the modifier chain that includes all modifiers between that node and the root.
So in the example above we'd have:
(a,b):r0,union (b,c):r0,intersection (a,c):r1,intersection
And now we want to build up a tree using a subset of these interactions that covers every surface id.
Is this something we can do with something like a minimum spanning tree?
Make a graph where each surface is a node, and each pair of surfaces is connected through another node labelled with the blend radius and operation type. And then how do you connect them together?
Do you just union them all? No, because then you'd have Union(a,b) in your resulting shape, and that is wrong because it needs
intersecting with c.
I think take the document tree as our starting point, and then add in extra routes that "bypass" combinators, so for each subset of combinators, we imagine replacing the subtree rooted at that combinator with first its left subtree and then its right subtree, and we add the resulting trees to the graph. And then we find a spanning tree that satisfies all the blends. Where "satisfies all the blends" is defined" as... what?
Having built the graph, go through every combinator node and label it with a blend radius if all of its possible surface pairs have the same radius. Delete all combinator nodes that don't have a blend radius.
Then find the kind of minimum spanning tree of what remains? And if the graph becomes disconnected then there's no solution?
We're kind of building the graph of all possible distributivity rewrites, and then pruning off nodes that don't have a consistent blend radius, and then taking a minimum spanning tree of what remains.
This not quite a minimum spanning tree. It's a weird kind of graph where there are 2 types of nodes: combinators and primitives. We only need to span the primitives.
https://en.wikipedia.org/wiki/Steiner_tree_problem
The Steiner tree problem in graphs can be seen as a generalization of two other famous combinatorial optimization problems: the (non-negative) shortest path problem and the minimum spanning tree problem. If a Steiner tree problem in graphs contains exactly two terminals, it reduces to finding the shortest path. If, on the other hand, all vertices are terminals, the Steiner tree problem in graphs is equivalent to the minimum spanning tree.
I think this is exactly what I want.
The Steiner tree problem in graphs can be seen as a generalization of two other famous combinatorial optimization problems: the (non-negative) shortest path problem and the minimum spanning tree problem. If a Steiner tree problem in graphs contains exactly two terminals, it reduces to finding the shortest path. If, on the other hand, all vertices are terminals, the Steiner tree problem in graphs is equivalent to the minimum spanning tree.
Rats.
The Steiner tree problem in graphs can be seen as a generalization of two other famous combinatorial optimization problems: the (non-negative) shortest path problem and the minimum spanning tree problem. If a Steiner tree problem in graphs contains exactly two terminals, it reduces to finding the shortest path. If, on the other hand, all vertices are terminals, the Steiner tree problem in graphs is equivalent to the minimum spanning tree.
OK, good.
Actually I don't want exactly the Steiner tree problem, because I don't care about minimising edge weights very much, I just want a "good" solution.
How large would the graph containing all possible distributivity rewrites get? I think for each combinator in our expression tree, we'd add 2 new nodes to our graph, and that's it? So would it literally just be twice as big? Or 2^n?
Duh, the graph is infinite, because you can always apply the rule again.
And then there's the question of whether this will even work.
I've added an "Add blend" option to the context menu, which lets you click another surface and add a blend with that surface. But it actually doesn't work most of the time. I guess it rewrites the tree into a form where every blend argument technically is an immediate sibling of its blend partner, but then further up the tree it is recombined with its blend partner in a way that doesn't apply the blend. So that is pretty stupid.
I think persist on this for this evening, and if I don't make any real progress, then stash it on a branch, and reset everything back to the point before I started working on this nonsense, say that it's the user's responsibility to structure the tree to suit their blends, and work on something else
Oh, the real reason my "Add blend" doesn't work is because it doesn't markDirty()...
So actually maybe it is working?? I must try to come up with some test case that it doesn't work on.
Damn, maybe I had a "good enough" version days ago and I only had to add a UI for it to find out that it is working.
One issue is there seems to be some discontinuity at the boundary of the blend:
And actually the field looks fine, so it must be the derivative that is discontinuous.
So yeah, now the problem is:
One issue is even if I apply blends between all pairs of surfaces, I still get a sharp edge where the blended subtrees are unioned together:
So in that respect the workflow where you structure the tree properly and apply blends manually is actually better. And it's more "true" to the SDF way.
Err, actually, I'm wrong. That sharp edge is there simply because the box itself doesn't have a radius on it. Adding a radius to the box solves it, good.
The version on incoherency.co.uk doesn't have the discontinuous normals problem. That is on 6421019d030ed1536c171da7ae59f66399692393
55ea57e42459c65c516df07bf53d5587a5acf20a also good, that's when the "fillet/chamfer continuum" was introduced.
Tree rewriting is new since then. I wonder if it is drawing a union of 2 copies of the scene on top of each other or something? No, the output of tree rewriting is perfectly reasonable.
This is a blended union of a Box and a translated Box, and the output of tree rewriting is just
Union(Box, Transform(Box)), same as the input.
Ah, one change I made since then is making smoothabs use 1e-5 instead of 1e-10. And yeah, putting that back
fixes the normals. Why did I do that? To fix a similar glitch in the thing where I was fading out blend radii
near other surfaces.
I'll leave it back at 1e-10 for now but if I have to change it again then I'll have to think harder.
So now I want a panel for editing blends. I guess just put them at the bottom of the property editor when you click on Document?
Adequate:
I'd probably also want to see the blends that affect any surface in the document when you are editing it. Cool, easy, done. Cursor is phenomenal.
As for selecting blends by clicking...
I can do it by making the blend return its own id as the surface id for points within the blend region, but because of the tree normalisation thing, the id of the blend doesn't actually appear in the document tree, so you can't select it.
So maybe blends need to get ids as well? And we can propagate a "blend id" value? And then in the mouse cursor ray marching, if the blend id is nonzero we say you're hovering over the blend, otherwise we say you're hovering over the surface.
Seems good enough, let's go for that.
If we draw blend ids and surface ids from the same pool then there won't be any collisions and we can just use one field to say the "surface id or blend id" of the thing under the cursor.
This is working but having to track blends as a "different type of object" is maybe not the way. What if a blend is actually a type of modifier?
So they'd be attached to the first surface you clicked on, and contain a reference to the second surface?
Then we can edit blend properties using the normal property editor, delete them using the normal context menu, refer to them by their tree id,
etc.? And TreeRewriter collects them up to make the list of blends?
Nice, this is working:
Actually the Blend should show up as a child of the node it is blending. And maybe a reference to it as a child of the other one as well? So for primitives we need to allow child nodes, but only blends, and blends can only be added as children of primitives. How will this work when a primitive can have multiple surfaces? Maybe still the same.
OK so issues to address with targeted blends are:
For now I want to make the GrabHandles for "translate" work a bit better. Instead of starting at the origin and showing the translation vector, it should centre itself at the point it is translating to, and have arms proportional to zoom level or something.
Great success, working now. And the handles scale inversely with zoom level, so they are always the same size on the screen.