Support circular sweeps

[hannobraun]

When defining models, Fornjot users can sweep a 2D sketch along a straight path to create a 3D solid. It would be desirable to support sweeping along other types of paths, for example circles.

This would be a larger project, but I think roughly speaking, it would consist of these steps:

1. Extend Surface, or more specifically SweptCurve, to support circular paths.
2. Make sure that all code that touches Surface/SweptCurve can deal with those circular paths, or at least dutifully panics using todo! and an explicit error message.
3. Make sure that the sweep algorithm can deal with circular paths.
4. Extend the fj crate to enable users to define circular paths.

We could later extend this to support helical sweeps, which is currently tracked on the feature wishlist.

[dwcarr]

I'm down for this. I would expect that a sweep that worked on a generalized curve would be only slightly more work than one for a circular curve, and would make helical curves a trivial extension. But I say this with some ignorance of the kinds of curves that are implemented thus far.

[dwcarr]

I see now. A line and a circle are the only kinds of curve. Cool. This should be straightforward.

[hannobraun]

Thank you for your interest, @dwcarr! I certainly appreciate the help.

Your comments triggered some thoughts. None of this is intended to tell you how to do the work (half of what I'm suggesting might not work for one reason or another), but I figured maybe it's helpful to you if I note my thoughts down:

• There's the question of how to represent the new SweptCurve. Right now, path is a vector, and that obviously needs to change. Not sure what is most appropriate, but maybe a CurveKind<3> plus a Vector<1> (to define the length of the sweep on the curve) would work well.
• Large parts of the sweep algorithm should actually be not too hard to adapt to circular sweeps. Just generalize it here and there; don't create line-based side edge, create ones based on the sweep curve; stuff like that. I don't expect that this would change the structure of the algorithm.
• However, there are new edge cases that would have to be considered. If the sweep path is a full circle, then the resulting side surface connects to itself. In surface coordinates, it would be bound by different HalfEdges on both sides, but those should refer to the same GlobalEdge, and not slightly different ones (as that would lead to follow-up bugs).
• But it's perfectly fine if the initial version doesn't consider all the new edge cases. Just ignoring them and opening an issue to track that would be fine. Recognizing the unhandled edge case and panicking with a nice message would be better.
• Even when the sweep algorithm is updated and generates the correct b-rep data structures, there are other parts of the system that might not be able to handle them. The approximation code comes to mind. So far, when approximating a face, it only considers the bounding edges of the face to create the approximation. Once you have something like a torus, you need points in the middle of the face itself to approximate it. But this is another thing that doesn't need to be (maybe shouldn't be) in the initial version.

I'd like to stress, new code doesn't need to be perfect to get merged. As long as it doesn't break existing functionality, it's perfectly fine for the new functionality to panic when it encounters edge cases. For now, Fornjot is super-experimental, so this kind of thing is acceptable. In the future, we'll have experimental features to steer users away from edge cases that aren't working yet.

I hope that helped. Please don't hesitate to ask questions, if you have them!

[hannobraun]

Hey @dwcarr, I have some follow-up thoughts and a heads-up.

---

First, the head-up: My current work (#695) is indirectly touching the sweep code. I'm not really making changes to the sweep code itself (except for a tiny clean-up commit), but I'm working on some of the code that the sweep code is build on, which messes with the sweep test suite. That test suite already has some broken and disabled tests, which were impractical to fix at the time I broke/disabled them.

Once my local branch that addresses #695 is merged, fixing those tests becomes practical again. However, the way things are going, that branch itself is breaking some more tests. I will probably merge that branch with more tests disabled, then refactor and fix the test suite in a separate pull request. Since that work will be mostly (or completely?) limited to the test suite, I don't expect much interference in the form of merge conflicts. And I don't want to hold off on that either, as your work is most likely going to benefit from a (once more) complete test suite.

So yeah, sorry if that interferes with what you do, but I hope it'll be for the best.

---

Let's get to the follow-up thoughts. I wrote this:

There's the question of how to represent the new SweptCurve. Right now, path is a vector, and that obviously needs to change. Not sure what is most appropriate, but maybe a CurveKind<3> plus a Vector<1> (to define the length of the sweep on the curve) would work well.

I think this will work for circular sweeps (so you could definitely do it like this to address this issue), but it won't generalize to helical sweeps. I don't think a helix can be a CurveKind<3> under the current structure, because then we would also need to define a CurveKind<2>::Helix variant, and I don't see how that would work.

The following thoughts are not relevant for this issue. They will probably become relevant, once we want to extend to helical sweeps. I'm adding them here, because I need to get them out of my brain, and until we have an issue for helical sweeps, I don't know of a better place to put them.

I think that maybe CurveKind<3> shouldn't exist at all. That would imply that GlobalCurve wouldn't exist either. Instead, we'd have only Curve, and CurveKind would be 2D-only. Curve already references a Surface, and it can generate 3D points through that. So GlobalCurve/CurveKind<3> are not strictly required.

That has repercussions on the approximation code. Right now, a Curve could be a straight line (CurveKind<2>::Line) on its surface, but if that surface is curved (like the side wall of a cylinder), then it would be a circle in 3D space. It would know that through its GlobalCurve/CurveKind<3>. For that reason, GlobalCurve is also what determines how to approximate a curve.

If GlobalCurve/CurveKind<3> no longer existed, then Curve would need the help of Surface for approximation. There would need to be some mechanism to ask the surface, "if I move from this point along this path, where would I need to place the next approximated point to stay within a given tolerance". This isn't really a drawback, because we're going to need something like this anyway, to approximate surfaces that are curved along both of their axes (like a sphere; compared to the side wall of a cylinder , which is only curved along one axis).

In conclusion, I think the following might be a good idea mid- to long-term, as well as a prerequisite to implementing helical sweeps:

1. Implement the aforementioned code that can approximate a surface.
2. Use that code to approximate Curves, bypassing GlobalCurve/CurveKind<3>.
3. Remove GlobalCurve.
4. Simplify CurveKind to be non-generic and 2D-only.

I'll think some more about this. If I decide that this plan has merit, I'll open a dedicated issue to track it.

[hannobraun]

The sweep test suite is fixed: #1068

[dwcarr]

One thing that you see in most cad packages is the notion of a 3d curve. That can be a complex object, but the "code first" strategy of Fornjot could make it easy to parametrize. I would like to understand the constraint system a little more, or your vision thereof, as it would help to conceptualize things.

I bring it up, because a 3d curve parameterized by a surface is the same as having a 2d curve on that surface. And since some 3d curves cannot be parametrized by a single surface, I wonder if it might be worth the time explore that avenue.

I am still learning my way around all the code, and will begin implementing the plan that you outlined above today.

[hannobraun]

I would like to understand the constraint system a little more, or your vision thereof, as it would help to conceptualize things.

Right now, there is no constraint system, and I have no vision for one, beyond "I want it". My main exposure to such systems have been SolveSpace and FreeCAD. Right now, I don't have any ideas that go beyond that. It's not a topic I have looked into or thought about much.

I bring it up, because a 3d curve parameterized by a surface is the same as having a 2d curve on that surface. And since some 3d curves cannot be parametrized by a single surface, I wonder if it might be worth the time explore that avenue.

Can you point me to somewhere I can read up on that?

As things are implemented now, every curve in Fornjot exists on a surface. So far, I hadn't considered that this could turn into a problem. I still don't understand how it could, but that doesn't say a lot. I'm far from an expert in geometry, or CAD kernels, or anything really, hence my desire to learn more.

This is a hard balance to strike sometimes: On one hand, I need to implement solutions that work right now, and that will enable us to take the next steps. Trying to plan out everything in advance is just paralyzing and doomed to fail anyway. On the other hand, I don't want to maneuver Fornjot into some dead-end that will take a lot of work to get out of again.

I am still learning my way around all the code, and will begin implementing the plan that you outlined above today.

Sounds great! Let me know, if there's anything I can do to help.

[dwcarr]

Thanks for the clarifications.

The areas where a 3d curve come in handy is in things like pipes or wires, where you want to sweep a section through an arbitrary path. But for now, we can certainly stick with the idea that all curves are on a surface.

This is a hard balance to strike sometimes: On one hand, I need to implement solutions that work right now, and that will enable us to take the next steps. Trying to plan out everything in advance is just paralyzing and doomed to fail anyway. On the other hand, I don't want to maneuver Fornjot into some dead-end that will take a lot of work to get out of again.

You said it all, and I am definitely in agreement on the need to get things built, and not get bogged down in the planning of complex systems. From my view, Fornjot is in danger of the dead end if the constraint system is not thought out. The application of constraints is what allows the system to understand design intent. This translates to the system knowing how to make changes to the overall design if a single parameter changes. Even for simple, single part designs, this can be very important. And in the world of generative design, constraints are almost the whole story. I can take a look at what it might look like to implement constraints (and the much more difficult constraint solver!) on 2d sketches only, initially.

I'm pretty solid on the differential geometry side of things (undergrad math, phd physics), and I definitely don't mind sharing that knowledge. I am an experienced user/designer in Solidworks, Solid Edge, ProE/Creo, and Autodesk Fusion. I wish that they had a "code first" strategy. I also see the "code first" approach being extremely useful for implementing AI generative design, but I know that all that is down the road a ways.

[hannobraun]

The areas where a 3d curve come in handy is in things like pipes or wires, where you want to sweep a section through an arbitrary path. But for now, we can certainly stick with the idea that all curves are on a surface.

I think we might be talking about different things, so let me clarify:

• When I say curve, I mean an infinite, one-dimensional object that is defined on a surface. The purpose of a curve is to have an edge defined on it, and the purpose of an edge is to bound a face (together with other edges, in most cases). Since a face is defined on a surface too, a curve that is not defined on a surface would be of no use, because an edge defined on it would have no face to bound.
• Distinct from that is the concept of a path of a sweep, which serves a different purpose. The implementation of path and curve could be the same (as I suggested above, for the implementation of circular sweeps), or it could be completely different (as it is right now, and as it could be again, once we implement helical sweeps).

I'm not saying this is the right way to use those terms, I'm just saying this is how the terms are currently used in the Fornjot code, and how I've been using them here.

I didn't spell this out in my notes above, but if my idea of removing GlobalCurve and CurveKind<3> were to be implemented, then the definitions of "curve" and "path" would need to become distinct again. I imagine that there would be an enum for sweep paths, something like this:

pub enum SweepPath {
    Line { ... },
    Helix { ... },
    ...
}

That would basically fill the roll of a 3D curve, if I understand you correctly. But in the data structures generated by the sweep operation (or any other), all curves would be defined on a surface.

Does that sound right to you, or am I missing something?

From my view, Fornjot is in danger of the dead end if the constraint system is not thought out. The application of constraints is what allows the system to understand design intent. This translates to the system knowing how to make changes to the overall design if a single parameter changes. Even for simple, single part designs, this can be very important.

Thanks for the explanation and that link.

I'd like to note, that Fornjot doesn't need constraints to let the user express design intent, thanks to its code-based nature. Fornjot could provide a completely constraint-less direct modeling API, but the code that uses said API could have the built-in intelligence to always place this hole in the center of that plate, no matter how big the plate is. That's actually one of the big advantages of code-first CAD.

That's not to say constraints aren't important. They might still be the best way to express a given relationship, resulting in more compact and readable code. But in a code-first world, they are more of a convenience/efficiency feature, not something you critically need.

I share your worry that not thinking about constraints early-on will lead into a dead-end. Right now, I want to focus on boolean operations though, as I believe those are critically important. The combination of code-first CAD and boolean operations basically lets you do anything you could ever want from a CAD program. And to be clear, I'm not saying "do anything efficiently", I just mean that once we have boolean operations, users can express basically anything. (Even a NURBS surface can be approximated with many flat ones, if you write the code to do that. And users can do that in their model.)

We'd still want to offer more advanced modeling features though, so not every second model needs to have its own ad-hoc constraint system built into it. I'm just explaining why I want to focus on boolean operations right now, leaving constraints for later.

And in the world of generative design, constraints are almost the whole story.

Generative design is another thing I'm interested in but have no experience with. Would love to add it one day!

I can take a look at what it might look like to implement constraints (and the much more difficult constraint solver!) on 2d sketches only, initially.

That would definitely be welcome!

Constraint-based sketches are currently on the feature wishlist. If you're interested in tackling that, we can move it off there an open an issue.

I'm pretty solid on the differential geometry side of things (undergrad math, phd physics), and I definitely don't mind sharing that knowledge. I am an experienced user/designer in Solidworks, Solid Edge, ProE/Creo, and Autodesk Fusion. I wish that they had a "code first" strategy. I also see the "code first" approach being extremely useful for implementing AI generative design, but I know that all that is down the road a ways.

Those are some very useful skills! I hope you stay interested in Fornjot, so the project can benefit from your expertise 😄

I bring a few decades of software development experience to the table, but other than that, I'm just an enthusiastic amateur with no particular math or engineering experience. I'm basically just a programmer who wanted to use OpenSCAD and said "this is annoying, I can do better" (which I've yet to prove 😄).

[dwcarr]

Thanks for the clarifications, I really appreciate you taking the time to explain things. I see what you mean with constraints and code-first, and starting with constraints just on sketches would be good enough for many situations (until you start doing assemblies, but we are a long way from that).

I should also point out that I am dealing with long-covid, which can slow me down a lot on many days. If I am ever slow to respond, that's why. But it is also why I have time to work on things, as it is forcing me to switch careers to something I can do from bed, lol.

Here are a couple things that really make me want to do CAD in rust.

1. All CAD should be re-written in rust, for all the same reasons that many codebases are being re-written in rust. However, the CAD industry is uniformly hamstrung by using ancient kernels that they refuse/are unable to update. Solidworks just releases new UI updates every year, for the last 20 years, but without any actual change. Open source software that is done right could upend the industry.
2. We are rapidly moving towards a place where AI is going to be doing a big part of the design in the world going forward. AI would love to have a code-first approach that could enable designs to be rapidly iterated upon. This is where constraints come in. If AI is able to change a single variable in a design, then it can effectively do partial differential equations on the designs. But the existing systems are not code-first. They are code-last, with interfaces that are slow and not very well though-out thanks to the ancient codebases. So even though they can be used to do AI generative design, it is far from optimal. If someone produced a CAD program that AI could use for this purpose more efficiently than any other cad program, it would take over the world.

You've done great work so far on this codebase. I hope I can contribute. I am interested in tackling the constraint-based sketches. Related to that, I would also like to work on defining the data store. I will leave a comment on that issue pursuant to that.

[hannobraun]

Thanks for the clarifications, I really appreciate you taking the time to explain things.

No problem! Writing these explanations helps me clarify my own thinking, which in turn helps in recognizing areas for improvement. So I'm always happy to jump at the opportunity 😄

I see what you mean with constraints and code-first, and starting with constraints just on sketches would be good enough for many situations (until you start doing assemblies, but we are a long way from that).

👍

I should also point out that I am dealing with long-covid, which can slow me down a lot on many days. If I am ever slow to respond, that's why. But it is also why I have time to work on things, as it is forcing me to switch careers to something I can do from bed, lol.

No problem, take your time! I wish you all the best in getting better, and with your career change!

Here are a couple things that really make me want to do CAD in rust.

1. All CAD should be re-written in rust, for all the same reasons that many codebases are being re-written in rust. However, the CAD industry is uniformly hamstrung by using ancient kernels that they refuse/are unable to update. Solidworks just releases new UI updates every year, for the last 20 years, but without any actual change. Open source software that is done right could upend the industry.

2. We are rapidly moving towards a place where AI is going to be doing a big part of the design in the world going forward. AI would love to have a code-first approach that could enable designs to be rapidly iterated upon. This is where constraints come in. If AI is able to change a single variable in a design, then it can effectively do partial differential equations on the designs. But the existing systems are not code-first. They are code-last, with interfaces that are slow and not very well though-out thanks to the ancient codebases. So even though they can be used to do AI generative design, it is far from optimal. If someone produced a CAD program that AI could use for this purpose more efficiently than any other cad program, it would take over the world.

I'm more of a hobbyist/maker when it comes to my CAD use, so I appreciate these insights from a professional CAD user's perspective. Very interesting!

You've done great work so far on this codebase.

Thank you!

I hope I can contribute. I am interested in tackling the constraint-based sketches. Related to that, I would also like to work on defining the data store. I will leave a comment on that issue pursuant to that.

Again, thank you! As I said somewhere above, I appreciate the help. Fornjot certainly isn't something I can do on my own.

[hannobraun]

I've been musing about potential changes earlier, and in combination with some new problems, this has resulted in #1079.

Still not directly relevant to this issue, but given that we discussed helical sweeps here before (and this will become relevant when implementing those), I thought I'd mention it.

[dwcarr]

Regrettably, my body is not recovering very well. Sorry for inserting myself into this just as I fell ill. I am still very interested and will try to stay engaged, but I may not be able to contribute code any time soon.

[hannobraun]

No problem, @dwcarr! This issue is far outside of my own work's critical path, so feel free to pick this up (or not) if and when you feel like it. In addition, the discussions we had here have stimulated some thoughts and helped me figure out stuff that was very useful in my own work, namely #1079.

I wish you all the best for your recovery!

[hannobraun]

This remains a desired feature, but I've decided to close this issue as not actionable for now. I've added circular sweeps to the feature wishlist instead, alongside other extensions to sweeping.

There are significant changes to the geometry representation incoming, which should address many of the shortcomings we talked about here. And while it should be possible to implement circular sweeps before that (the path I laid out in the original issue description is partially outdated, but should still work in principle), I don't think it makes sense. With the new geometry representation, this would be much easier to achieve, and any circular sweeping code written before that, would essentially have to be rewritten anyway.

For these reasons, I consider this issue not actionable right now, and believe it would be better to address it once a new geometry representation has been implemented.