Consider uniform intermediate representation for geometry

[hannobraun]

Where we are right now

The current system of defining geometry is just a placeholder. The only geometric primitives that are supported are the two types of curve: lines and circles. Those can be swept along a straight path to create surfaces. Since this is the only method of creating surfaces, only planes and cylinders (which in this context means just the side walls) are supported.

As far as placeholders go, this one has been fine. It has allowed me to come to grips with the object graph and how to update it. So far, this has not really been limiting.

However, as the operation API expands, I can start to see the limits of this placeholder representation coming. We're not there yet, but pretty soon, we will need something better.

Why not just expand the current system?

Most operations that are implemented right now, are pretty dumb. Take face splitting as an example: Yes, it will split a face for you, but you have to tell it exactly which half-edges have the endpoints of the new half-edge (that will be between the new faces).

It would be much more convenient, if you could just give it a curve, and say "split the face along that". Or a whole sketch, for that matter, to split the face into an arbitrary number of smaller faces.

Doing any of that would require it to be smarter, and figure out which half-edges to split and where, by itself. Which means querying the existing geometry and making decisions based on what it finds.

If we just expanded the current system with more primitives, and more ways to combine those primitives, then such queries would be more complicated. Finding the intersection between two lines requires different math than finding the intersections between two circles. How about finding the intersections between a line and a circle, or the intersection between a circle and a curve that is defined as the intersection of two surfaces (which themselves could be defined in any number of ways).

What I see coming, is a combinatorial explosion of stuff that needs implementing. Going down that route will be a lot of work, and will create a million little edge cases, all with their own little bugs.

The solution: a uniform intermediate representation

If we had some kind of uniform intermediate representation that all primitives can translate to, then implement our geometric queries and operations based on that intermediate representation only, the combinatorial explosion would be thwarted.

An there is a rather obvious intermediate representation we could use:

• All curves can be represented as polylines.
• All surface can be represented as triangle meshes.

Such a representation would, of course, be an approximation. I don't think that can be fully avoided, if we one day want to support arbitrary geometry. Or even if we stick to a powerful representation like NURBS, as I don't think there is a closed-form solution for intersections between NURBS surfaces.

And I don't think it matters, actually! This is just an intermediate representation. The primitives that generated it are still there, and can provide a higher-resolution approximation whenever necessary.

What about SVG/STEP/...?

So what if we want to export our geometry to a file format that can represent the original primitives? Like SVG or STEP. Won't we lose information by first operating on a lossy intermediate representation?

Well yes, but I'm reasonably sure this can be addressed. We can tag the intermediate representation with the primitive it came from, and the exporter can then be aware of those tags. For example:

1. We might generate a curve from the circle primitive;
2. later shorten that to an arc through some operation that uses the intermediate representation to figure out what the end points of the arc should be;
3. then, when exporting to SVG, read the tag, realize the curve comes from a circle, and use the appropriate primitive when generating the SVG.

While this is a bit hand-wavy, it's enough for me personally, at least unless more specific information comes to light. Many times, people have told me I need to consider this or that aspect from the beginning, but the simple fact is that creating a CAD kernel is a colossal project, and I can't consider everything from the beginning. I could have never started in the first place. I believe this is one of those cases. I've been thinking about this for months, and at some point I need to take concrete steps.

If that means that we'll end up in a situation where we have a geometry representation that can't export STEP files, for example, that's fine too. This isn't meant to be the last word on geometry representations! Nothing I can say will be the last word on any topic. If this concept can serve us for the next steps of Fornjot's development and then make way for whatever comes next, I call that progress.

Next steps

I've been thinking about this for a while, but this is the first time I've gone beyond brief notes in writing it out. If anybody has thoughts, please speak up!

I don't intend to work on this right away, but I think I will want to do this, or something like it, in the not-too-far future. Not only will the current system not hold up much longer, building more on top of it means work that has to be redone anyway, once we move to a better system.

However, before starting work here, we should definitely address #2116.

[TheEppicJR]

So I have some thoughts here. Ill start off by saying my perspective here is a reasonable amount of experience/frustration with the API in Fusion 360 and a somewhat naive understanding of Rust.

The approach that Fusion uses for its API is a 3 way split approach that is partly abstracted/obfuscated to the user (of the api), with a geometry layer (imperative), BRep layer (this is effectively solved/declared form of the geometry), and mesh layer/polylineish stuff. A typical way I would use the API is to take a user selection which is a BRep object and I perhaps use the provided function to switch to the geometry representation and traverse the geometry through references. Most of the pain points in fusion exist in constantly having to switch between representations to get the information you need. Want know the radius of a cylindrical BRep surface? Well you have to cast it into a geometry object and the type system gives you no guarantee that your going to get a cylinder.

What I have a inkling should be possible here is a much cleaner version of that Fusion is trying to accomplish. Having only, what i will call, a imperative and declared layers. The cad-as-code is only ever generating the imperative layer but can reference geometry that will (the object exists now, and the solver will store the solution there) exist in the declared layer. So lets say I want a plane that is defined by 3 points that are the ends of lines in a sketch that have constraints that need to be solved, when generating the imperative version (ie like let _ = Plane::from_three_points(l1.end, l1.start, p3);) of the plane I would pass reference to each of the 3 points, and there will now be a declared version of the plane in existence. Then fornjot generates a solution for the position of all the lines based on constraints, which gives the points real positions, and then the declared plane has a real solution.
Now with the example of a extruded sketch, for each edge of the sketch there will be a declared vertical face, and a then a top and bottom declared face, -- now here is the place where it gets ugly in fusion -- lets say I have a hole that is tangent to the edge of this body that was created, it can both entirely remove a vertical declared face or split one in half and maybe delete one half. Fusion just deletes the object completely in when none of it when none of the face continues to exist, What I think the solution is, is to make the declared object 'phantom' whenever a later operation would change that object, that has a reference to any geometry derived from this object that remains after the next operation that edits the object and the geometry (if any) that remains once all operations have been completed. (both of those should be options, so you can have like ::Deleted, ::Final, or ::Phantom(Faces) or whatever)
Now lets say I'm making a STEP exporter, to set the stage we have: Coordinate Systems, points/vertex, axis/infinite line, planes, edges/lines, surfaces, shells, and bodys as our base geometry traits, all of which have a imperative and declared form, and for any combination of the two (eg a declared surface) there is a requirement that implement a certain set of fn. In fusion a BRepFace would equivalent to a declared surface, and it is required to implement a surface evaluator that has functions getCurvature, getNormalAtParameter, getPointAtParameter, getSecondDerivitive(at parameter), getThirdDerivitive(at parameter), and ect; everything that you would need to implement a function generate a new set of declared surfaces that represent a imperative feature (I think features should only be imperative but not totally sold) that is a fillet between two surfaces along the edge between them. Back to the STEP exporting, you would have a trait that represents the export needs of that kind of geometry, so a edge would be required to implement a function that will return a representation of the edge with a guarantee that it is either a straight line, arc/circle, polyline, or other simple geometry, but the exporter is free to see that it has been given an edge geometry it is familiar with in a switch statement and use a less lossy option.
So then you can introduce fancy geometry, like polynomial surfaces for lenses/mirrors, easily with a lossy representation and then have the option to optimize it later on.

I hope that all made sense and is useful to some extent

[hannobraun]

Thank you for that post, @TheEppicJR. I can't say I understand all of it (I have no experience with Fusion), but it was interesting to read.

My approach is always to start simple, and add more concepts as required. So I think a lot of what you describe will only become relevant as Fornjot grows more to cover more use cases. I hope I'll keep what you say in mind, as that happens.

[jdegenstein]

I thought I should add a resource to this issue that might have some value. In 2014 a comparison was made between the ACIS kernel (closed source) and the OCCT kernel. A whitepaper documenting this comparison between the two kernels was finally published late last year. The PDF is available here:

https://quaoar.su/files/papers/cascade/ACIS_OCCT_comparison_v2.0.pdf

This is not intended to greatly influence the direction of Fornjot, however I feel that studying these existing tools a bit might be very valuable to this project.

[hannobraun]

Thank you, @jdegenstein, that was an interesting read!

[hannobraun]

I've started working on this issue. A while ago, actually, as you can see from the list of pull requests above this comment. Sorry for only updating this issue just now. I haven't been very good about communication lately 😅

The work so far was mostly experimentation and design. I'm starting to figure out how the geometry system needs to look like in practice. I don't have a lot more to say about it right now. There weren't any big issues or open questions so far. Just lots of minor details, as is so often the case.

As per the new development process, I won't submit any pull requests from now on, which will make following my work a bit more difficult. I'll try to make up for it by being a bit better about posting progress reports here, but we'll have to see how that goes 😄

[hannobraun]

I've been making some progress on this issue, and some things have been falling into place. There are traits for generating uniform representation for curves and surfaces now, respectively, and they are already being used in quite a few places. There's more work to do, to migrate more of the code, and I'm sure more surprise problems waiting.

Subjectively I'd say that performance has taken a hit. Which is not surprising, as I'm generating (and re-generating) geometry wherever it's needed, without much thought. I'm currently operating on the assumption that I'm going to solve this at an architectural level later on. Once it's a bit more clear how these changes turn out, and what needs to happen where, I'll restructure things to generate geometry once, then pass that where it's needed.

(For example, right now geometry is being generated piecemeal to do various tasks while CAD operations are performed; then again for everything to create a mesh for rendering; and then again for everything, to create a bounding box for the geometry, to help actually draw that mesh.)

[hannobraun]

The rate of progress on this issue has been a bit unsteady so far. First it was slow, with many small problems and design issues dominating my work. Then quite a few things fell into place in a short time (which I wrote about in my previous update here). Now I'm back to small problems and design issues 😁

I already mentioned that geometry is currently being re-generated multiple times. I assumed this was primarily a performance problem, and that I could address it later. But as I've found out, it is an architectural problem, and I probably need to address it right now.

For example, most recently I was working on some pure geometry code. Projecting a curve onto a surface, that kind of thing. All this code needs to operate, is a polyline and a triangle mesh, but what it has instead, are traits that can generate those. But then it needs to know in which range (of the curve) or section (of the surface) to generate them, because both curves and surface are infinite, so it's not as easy as just generating the curve/surface and going from there.

And to do that, it basically needs to know much more about that curve and surface and the context they exist in, than it otherwise would.

And yeah, I obviously can just solve the problem for this specific piece of code. But it's just one instance of a more general problem. It will pop up again and again, and I don't think I'll win anything by deferring it for later, instead of just solving it right now.

Here's my current idea for doing that (details might change as I make progress):

• Curves and surfaces have two geometrical things associated with them:
  • A generator (the trait) that can generate geometry for that curve/surface on demand.
  • The generated geometry (the polyline or triangle mesh, respectively).
• When the curve/surface is created, its generator is stored, and the empty generated geometry is initialized.
• When an object that constrains the curve or surface is generated (an edge or a face, respectively) is created, the generated geometry is amended with new geometry within the constrained area.
• Pure geometry code doesn't need to bother with the generator and can just operate based on the generated geometry.

I think this would be more manageable than what I've been building so far. As a side effect, it might have a positive effect on performance, as generated geometry would already be available when needed, and wouldn't have to be re-generated again.

That's the plan I'm going with for now. I'll keep you up to date on how that develops.

[hannobraun]

I forgot to update this issue yet again. I'm sorry.

I have not been working on this issue (at least not directly) since late October. I talked about some of the problems I was working on in my previous post here. I don't think there was a specific one that tripped me up, but rather the whole situation of everything going so slowly, with new problems at every turn, was what finally made me reconsider my approach.

I've since started working on a more experimental approach. Check out the README of the first experiment I worked on, which explains a lot of my thinking there.

Those new experiments have the idea of uniform geometry built into them at the lowest level. If this new approach goes somewhere, it will therefore address this issue too.