The new Weekly Dev Log is Out: Fornjot - Weekly Dev Log - 2022-W25
This week I was working on simplifications.
The new Weekly Dev Log is Out: Fornjot - Weekly Dev Log - 2022-W25
This week I was working on simplifications.
The Weekly Dev Log is out: Fornjot - Weekly Dev Log - 2022-W26
Lot of progress this week! All ongoing cleanups have been wrapped up, and the road is clear for resuming some actual non-cleanup work!
The Weekly Dev Lot is out: Fornjot - Weekly Dev Log - 2022-W27
This week, I mostly spent on getting the new release out, and making plans for how to make that way less painless in the future.
This time, I've decided I've had enough. Starting next week, there will be weekly releases, and the changelog format will be updated to closely match this Weekly Dev Log, which will become the release announcement. This will hopefully make releases both regular and manageable.
At a previous job, I got into the routine of cutting a new release every Friday afternoon and found it worked really well both in terms of user engagement, leaving a paper trail, and keeping me accountable.
Having a smooth release process also means you'll want to cut releases more frequently because it's not a 2-3 hour menial task that you'll want to put off.
My process was:
# Unreleased
section in my changelog to a versioned releaseThanks for sharing your experience, @Michael-F-Bryan! I hope to arrive at a similarly smooth process. I got the process of writing the weekly dev log down pretty well, and we already have some release automation (which I hope will become more solid through frequent use), so I'm optimistic that the weekly schedule will work out well.
Hey folks! Fornjot is switching to a weekly release schedule. Weekly release announcements are going to replace the Weekly Dev Logs which I've previously posted here. I've updated the thread title to reflect that.
Here's the first weekly release announcement: Fornjot - Weekly Release - 2022-W29
This week, I made progress on implementing the union operation and encountered what could become the next detour.
This week's release is out: Fornjot - Weekly Release - 2022-W30
Highlights include improvements to the modeling API, more smarts when dealing with a model's Cargo package, and improvements to kernel APIs.
This weeks' release it out: Fornjot - Weekly Release - 2022-W31
Highlights include me being focused on the union algorithm and @Michael-F-Bryan implementing the --version
argument.
This week's release is out: Fornjot - Weekly Release - 2022-W32
Highlights include progress on the union algorithm, no more potential crashes because of missing graphics backend features, and a UI element to display the current status of the model.
In my very very limited understanding of CAD:
the 'hard part' of a CAD program is the geometric kernel -- the data structures for storing and operations on the b-rep
these operations / algorithms would be straight forward if we could do arithmetic on arbitrary precision numbers in O(1)
due to floating point rounding errors, these ops become really complicated, because the errors introduced to rounding may cause self intersection / other weird cases that make models 'invalid'
Can you comment a bit on how you designed the fornjot geometric kernel / what algorithms you used / suggested reading ?
Thanks!
Hey @zeroexcuses, thanks for the question!
Definitely correct!
This is only true for a small subset of algorithms, I'd say. There's plenty of difficult code to implement, even ignoring precision.
Fornjot is still a work in progress, so anything I'm about to say is only preliminary and might change.
On the architectural level, I've approached this by avoiding problematic floating point operations. For example, for various reasons, objects in Fornjot ("object" in this sense means a geometric or topological object, i.e. the stuff that 2D/3D shapes are made out of) are defined in a local coordinate system. Vertices are defined as 1D coordinates on curves. Curves are defined as 2D objects on surfaces.
To avoid any problems with floating point accuracy, those local objects always reference the corresponding global object, which is only created once. So, the 1D Vertex
struct references the 3D GlobalVertex
struct, and there's never a reason to compute 3D vertices from 1D vertices, which would unquestionably lead to a 3D mesh that isn't properly connected.
On an algorithmic level, there is complicated stuff you can do to make your floating point operations more robust. Fortunately, smarter people have taken care of this, so I haven't had to deal with that myself so far (see robust
, robust-predicates
).
Then there's the odd piece of code, where you just have to be careful. For example, if you have a sorted list of vertices that you want to deduplicate, you can't just call Vec::dedup
. Instead, call Vec::dedup_by
, and use the global form of the vertex as the criterion for deduplication.
As far as Fornjot is concerned, this is all a developing situation. I'm sure there will be new challenges that will require new solutions. I have some ideas.
I did not mean to trivialize these algorithms. What I meant to say is that if we had O(1) arbitrary precision, we could probably reason about these mesh algorithms as one would in CLRS / Introduction-to-Algorithms -- but the issues caused by floating point error raises throws a wrench into this.
On the architectural level, I've approached this by avoiding problematic floating point operations. For example, for various reasons, objects in Fornjot ("object" in this sense means a geometric or topological object, i.e. the stuff that 2D/3D shapes are made out of) are defined in a local coordinate system. Vertices are defined as 1D coordinates on curves. Curves are defined as 2D objects on surfaces.
Could we work through one concrete example. Suppose we have curves c0(t), c1(t) defined for 0 <= t <= 1.
Furthermore, suppose these two curves intersect at some point (x, y, z), i.e. c0(t0) = (x, y, z) = c1(t1).
Since we are storing local coordinates and not global coordinates (x, y, z), what are we storing? Are we storing (c0, t0), or (c1, t1), or something else ?
In either case, there seems something non-symmetric in an otherwise-should-be-symmetric setup.
Throwing in rounding errors, if we store the rounded (x, y, z) we likely incur similar errors to both c0(t0) and c1(t1), but if we store a local/relative rep, it seems like we minimize error in one curve and get more error in other curve.
Now, maybe none of this matters, but I'm somewhat curious as meshes + floating points + rounding errors completely break many of my intuitions.
I did not mean to trivialize these algorithms. What I meant to say is that if we had O(1) arbitrary precision, we could probably reason about these mesh algorithms as one would in CLRS / Introduction-to-Algorithms -- but the issues caused by floating point error raises throws a wrench into this.
Yeah, that's true.
Could we work through one concrete example. Suppose we have curves c0(t), c1(t) defined for 0 <= t <= 1.
Furthermore, suppose these two curves intersect at some point (x, y, z), i.e. c0(t0) = (x, y, z) = c1(t1).
Since we are storing local coordinates and not global coordinates (x, y, z), what are we storing? Are we storing (c0, t0), or (c1, t1), or something else ?
It would return both!
As I said earlier, local forms reference the corresponding global form, and that global form is only computed once. The result of intersect(c0, c1)
would be the local points (t0, t1)
, each of which would reference the same global point (x, y, z)
.
Depending on how the algorithm works out (I haven't implemented this specific one so far), the algorithm might compute (x, y, z)
first, then compute t0
and t1
by projecting (x, y, z)
onto the respective curves. Or if the first results of the algorithm are t0
and t1
, then it would create (x, y, z)
once through whatever means I deem most appropriate (convert one and use that for both? convert both and use the average?).
Whatever the specific technique, if the algorithm is implemented correctly, the result will be the tuple (t0, t1)
, each of those referencing the same (x, y, z)
.
I'm mis understanding something very basic. Let me introduce a bit of notation here. Let x_t
be the true, arbitrary precision value of x
. Let x_f32
be the f32 approximation of x_t
.
So now, we start with c0, c1. They intersect at (x_t, y_t, z_t).
We compute and store a (x_f32, y_f32, z_f32).[1]
Then, we compute t0_t, t1_t such that:
c0(t0_t) is very close to (x_f32, y_f32, z_f32)
c1(t1_t) is very close to (x_f32, y_f32, z_f32)
and we store t0_f32, t1_f32.
Above, I say "very close to" because although (x, y, z) is on c_i, (x_f32, y_f32, z_f32) is not guaranteed to be on c_i.
So now we have
c0(t0_f32), c1(t0_f32), (x_f32, y_f32, z_f32)
all of which are very close to each other, but not identical
Under this notation, (1) what are we storing, and (2) when faced with c0(t0_f32), how does the system know to (3) not evaluate it, and (4) just return the 'memorized (x_f32, y_f32, z_f32) instead ?
[1] Technically not, since we get rounding errors at every step of the calculation, and thus what we get is not necessairly the f32 rounding of (x_t, y_t, z_t), but let us ignore this for now.
Under this notation, (1) what are we storing
We store two tuples:
(t0_f32, (x_f32, y_f32, z_f32))
(t1_f32, (x_f32, y_f32, z_f32))
This is actually pretty close to what Fornjot does right now, but the details are not important for this discussion, I think. The second item in these tuples could also be a reference to a single deduplicated instance of (x_f32, y_f32, z_f32)
.
(2) when faced with c0(t0_f32), how does the system know to (3) not evaluate it, and (4) just return the 'memorized (x_f32, y_f32, z_f32) instead ?
I think this is where the misunderstanding lies. The system is never faced with c0(t0_f32)
or any equivalent of that. It is faced with the tuple (t0_f32, (x_f32, y_f32, z_f32))
. It takes from that tuple whatever it needs for that task at hand.
Yes, you could go out of your way to get c0
, plug t0_f32
in there, and get an incorrect value. That would be a bug, and it's also way harder than to just call vertex.global().position()
. I think this kind of thing would stand out in a code review.
Thanks for your patience in explaining all this. This clarifies up quite a bit. Thanks!
You're welcome! Always happy to answer questions about Fornjot.
Hey folks! I've taken a week off, but now I'm back! The new release is out: Fornjot - Weekly Release - 2022-W34
Highlights include lots of work on intersection testing code, improvements to the host/model API, and some UI work.
The weekly release is out: Fornjot - Weekly Release - 2022-W35
Highlights include me falling into a rabbit hole of cleanups, after making modest progress on what I was actually attempting to do.
The weekly release is out: Fornjot - Weekly Release - 2022-W36
I'm still deep down the rabbit hole of cleanups that I feel into last week!