Fornjot (b-rep CAD kernel in Rust) - Release Announcements

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!

3 Likes

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.

2 Likes

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:

  • Any PR that affects a user-facing feature includes a relevant entry in the changelog (I really like the Keep A Changelog format and philosophy)
  • Run the release script at the end of the week. This would...
    • Promoted the # Unreleased section in my changelog to a versioned release
    • Tag the commit
    • Compile the project and generate an installer
    • Upload the installer to our servers
  • Because I'd been writing up the changelog as I went, it was also trivial to copy it into an email (with some tweaks and general project updates) so I could notify interested parties while the release script was doing its thing
2 Likes

Thanks 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.

1 Like

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.

1 Like

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.

1 Like

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.

1 Like

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.

1 Like

In my very very limited understanding of CAD:

  1. the 'hard part' of a CAD program is the geometric kernel -- the data structures for storing and operations on the b-rep

  2. these operations / algorithms would be straight forward if we could do arithmetic on arbitrary precision numbers in O(1)

  3. 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.

6 Likes

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.

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.

Yeah, that's true.

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.

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).

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.

1 Like

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.

1 Like

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.

1 Like

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!

1 Like