n-wach
commented
3 years ago Yes, this was made as a school project--class was basically "make something cool in 10 weeks". The original idea was to bring precise, constraint-driven design (like you'd find in Solidworks) to digital art. But I ran out of time for the "art" part...
Unfortunately, I don't have any documentation on how the constraint solving works (just the code docs which I assume you found). I wanted to try to figure out the constraint solving on my own, so I didn't do too much research into specific techniques, and am unfamiliar with "Overveld relaxation".
Here's the basic idea:
- Each relation in the sketch acts on a number of figures, that each contain a number of variables
- Each relation calculates how close it is to being solved with a
getErrorfunction. The total error in the sketch is the sum of the error of the relations. The goal of the solver is to minimize this total error. - Solving is done with a pseudo-gradient descent (basically, I hard-coded the gradients for each variable in each relation):
- Each relation calculate a list of
VariableDelta. In theory, each delta represents the change in a single variable to reduce the relation's error the most. For instance, the midpoint constraint would try to change the midpoint to the average of the line endpoints, and would try to change the line endpoints to make the current "midpoint" correct. These calculations are coded manually, and can get pretty complex (for instance, collinear points are projected onto least-square regressions, and points tangent to a circle requires some fancy derivative approximations). - For each variable, the delta's across all relations are added together (sometimes they'll cancel out).
- Then, we change each variable based some heuristics that usually work
(total delta / (2 + number of relations that involve the variable)). - We hope this iteratively approaches total error zero
- Each relation calculate a list of
That's the basic idea. But there's an important optimization done for equality relations--where two variables should be equal. For instance, two equality relations are created when two points should be coincident (x1 = x2, y1 = y2). It didn't make sense to treat these equality relations like other ones (with deltas), because it would lead to super slow convergence.
Basically, my optimization works by merging "equal" variables. I lied earlier when I said the solver works on a per-variable basis. It actually works on a per-value basis (merged variables have a single shared Value instance). Changing the value of one variable directly changes the value of the other. In this way, no work on part of the solver is needed for equality relations--they're just always true by way of design.
There's also a concept of "constant" variables, to be able to fix/lock points to the cursor when dragging. Most relations will take into account constant variables to simplify delta calculation.
There are still a lot of shortcomings in this design though. Relations need to be carefully designed to converge, and there's no randomness in the "gradient descent", plus the overall relation "error" is pretty subjective, and causes things to break down at smaller scales.
I've written geometric constraint solvers in the past and this looks like a great start. I was curious how exactly the constraint solver works. I looked through the codebase and it sort of reminds me of the Overveld relaxation method. Looks like maybe you did this as a student project. Did you happen to do a write up by any chance?