Support arbitrary transformation matrices

[hannobraun]

As of this writing, transformations are just isometries, so a combination of translation and rotation. I think we should support arbitrary transformation matrices, ideally coupled with a nice API on fj::Transform, to build those matrices.

This would require an update of fj::Transform, as well as any CAD kernel code that supports it. The former should be pretty straight-forward, but I'm not sure how many changes the latter would require.

[Siithy]

I'm going to try taking a stab at this. Since I am neither familiar with this crate or nalgebra, i don't have an estimated timeline, but obviously don't wait for me if this becomes a bottleneck.

[hannobraun]

Sounds great, @Siithy! I don't expect to be working on this any time soon. Unless something comes up or another contributor becomes interested, you should have a lot of time.

If there's anything I can help with, let me know. Happy to answer questions, explain the architecture, or offer my thoughts on a possible API. Whatever you need.

[Siithy]

So it looks like you are getting the current transform functionality based on parry2d/3d. Unless I am missing something, Isometric transformations is the most general type they have implemented. They are then using nalgebra::geometry::Transform and its implementing types( Rotation/Translation are subsets of Isometric, which is a subset of Affine, which is a subset of Projective, which is a subset of TGeneral which is the most general version)

How far up that chain do you mean by "arbitrary transformation matrices"? I suspect we want something invertible so it would be either Projective or Affine, but I have not gone deep enough to know if we need the general case of the last row or only the [0, 0, 0, 1] case.

Let me know if I am misinterpreting any of the implementation as is or the goals for this issue.

[hannobraun]

So it looks like you are getting the current transform functionality based on parry2d/3d. Unless I am missing something, Isometric transformations is the most general type they have implemented. They are then using nalgebra::geometry::Transform and its implementing types( Rotation/Translation are subsets of Isometric, which is a subset of Affine, which is a subset of Projective, which is a subset of TGeneral which is the most general version)

This is correct, as a description of the current state of the code. But it shouldn't be taken as gospel.

That we're using Isometry from Parry is mostly a historical artifact (unless I'm forgetting about something, which I might). The CAD kernel used to use triangle meshes as basically an intermediate representation, which meant transforming triangles was a routine thing. Hence Isometry, because that's what Parry's triangles can be transformed with.

This is mostly irrelevant now and will be completely irrelevant soon (see #97). For now, the last vestiges of that approach are something we might need to work around, but it shouldn't inform our decisions here too much.

I'll reply to the rest of your comment first, but I have an idea for a workaround that I've written up below.

How far up that chain do you mean by "arbitrary transformation matrices"? I suspect we want something invertible so it would be either Projective or Affine, but I have not gone deep enough to know if we need the general case of the last row or only the [0, 0, 0, 1] case.

Well, in my rather naive view, can't we just store a generic 4x4 matrix in fj::Transform, build a Transform out of that in the kernel, and then use that to transform whatever we need to? I can't see a reason why we couldn't.

If you follow the chain of transform methods to the bottom, you'll find methods like Circle::transform and others like it. Those methods are just using transform_point and transform_vector, which a Transform can provide just as well as an Isometry.

I can imagine some cases where the type of transformation might become relevant, and I'm sure there are many other reasons to introduce limitations that I'm not seeing yet, but let's not get ahead of ourselves. If we can support general transformation with relative ease right now, then we totally should.

I think at this point, it would be a mistake to be too conservative. I'd prefer to support potentially dangerous stuff, learn from that, then scale back to a stable subset as needed. That is, unless you can make an argument why general transforms are a bad idea. I'm happy to learn!

Let me know if I am misinterpreting any of the implementation as is or the goals for this issue.

No, I think you're on the right track. If I can give you one piece of advice, then not to take my earlier decisions to seriously.

We're using Isometry because that was the convenient and obvious thing a while back. That doesn't mean it's a good idea now, or even was back then. I'm trying to eat an elephant one bite at a time here. Any decision I make just represents a snapshot of the requirements and available knowledge at a given point in time, nothing more.

---

Okay, here's my idea for working around the last vestiges of the triangle mesh representation, until #97 is done.

Here's the code that deals with transforming triangle meshes:
https://github.com/hannobraun/Fornjot/blob/e2bc072a40ab1e4e97aaa55f1fcac1ded258343b/src/kernel/topology/faces.rs#L94-L100

It calls Triangle::transformed, which takes an Isometry. I don't know why. I'm sure there's a good reason in the context of Parry. But, for our purposes, can't we just transform the triangle manually, i.e. each point one by one, using Transform::transform_point?

I can't think of a reason why that wouldn't work.

[Siithy]

Well, in my rather naive view, can't we just store a generic 4x4 matrix in fj::Transform, build a Transform out of that in the kernel, and then use that to transform whatever we need to? I can't see a reason why we couldn't.

I believe you are right. I was just trying to get a better sense of the constraints of the system. My guess is that we can use either the general Transform struct or the Projective variant and cover the use-cases we need.

That is, unless you can make an argument why general transforms are a bad idea.

I believe the associative property is lost when the matrix isn't invertible. Since we are essentially talking about doing chains of transformations to points, then not having association feels a bit odd to me. My guess is that it really doesn't matter much for anything we'd run into soon and swapping out the two types is trivial either direction. I'll stick to the general form for now. Probably less work anyway.

can't we just transform the triangle manually, i.e. each point one by one, using Transform::transform_point? I can't think of a reason why that wouldn't work.

That was my expectation as well unless there is some handy convenience function that nalgebra gives us.

[hannobraun]

I believe the associative property is lost when the matrix isn't invertible. Since we are essentially talking about doing chains of transformations to points, then not having association feels a bit odd to me. My guess is that it really doesn't matter much for anything we'd run into soon and swapping out the two types is trivial either direction.

Ah, interesting. That is odd, but I agree that it probably doesn't matter. I assume that most users would create pretty tame matrices using whatever methods we provide on fj::Transform. Those that go beyond that might or might not know what they're doing 😁

I'll stick to the general form for now. Probably less work anyway.

Sounds good 👍

can't we just transform the triangle manually, i.e. each point one by one, using Transform::transform_point? I can't think of a reason why that wouldn't work.

That was my expectation as well unless there is some handy convenience function that nalgebra gives us.

Triangle comes from Parry, so there can't be such a function in nalgebra. And the one in Parry takes Isometry. Doesn't matter. There are worse thing than calling transform_point three times.

[Siithy]

I assume that most users would create pretty tame matrices using whatever methods we provide on fj::Transform

Slightly off topic but this reminds me of a question. What is the plan for how to handle things like bevels and rounded corners? Obviously they can't be a transform because it isn't one-to-one in terms of mapping points to each other. I have no idea what standard practice is for how the arcs of rounded edges gets generated for a straight line.

[hannobraun]

What is the plan for how to handle things like bevels and rounded corners? Obviously they can't be a transform because it isn't one-to-one in terms of mapping points to each other. I have no idea what standard practice is for how the arcs of rounded edges gets generated for a straight line.

There's no real plan yet, but I do have thought about the topic.

First, we need some way for users to select edges. I'm currently assuming that this will involve a central change to the way geometry is generated: Instead of composing structs, there would need to be an API that you can use to create geometry via method calls. So instead of this (pseudo code, not the real API we have right now):

let cube = fj::Cube { side_length: length };

We'd have something like this:

let cube = fj.cube(length);

cube would be some kind of handle that can be used with the API for various purposes. This handle could then be used with other operations:

let transform = fj.transform(cube, matrix);

So far, I've shown nothing that isn't already possible. The new capability here would be that you could use this API to query aspects of the geometry, maybe like this:

let all_edges = fj.select_all_edges(cube);
let top_edges = fj.select_edges_around_top(cube);

There are some open questions here, like how are edges identified, exactly? Obviously something like select_edges_around_top could be well-defined for a cube, but not any arbitrary shape.

My current idea is to have a hierarchical id system. Let's move away from the cube example here, as that's not a real primitive we have. The way to make a cube would be to create a rectangular sketch, then sweep that. When you create a sketch, you could already assign specific ID numbers to edges that you know are important (other edges could have a numerical id as a fallback).

Let's say you create a square-shaped sketch, and specify that the right edge is called "right". You can then select that edge like this:

let right_edge = fj.select_edge(square, ["right"]);

After you sweep the square into a cube, the sweep operation would add its own layer to the id. A sweep operation has well-defined bottom, top, and side faces. So now you can select the successors to your right edge like this:

let bottom_right_edge = fj.select_edge(cube, ["bottom", "right"]);
let top_right_edge = fj.select_edge(cube, ["top", "right"]);

This is all a bit hand-wavy and not fully thought through. But I assume we'd need something like this to be able to select edges (and other geometry).

Once we have some means to select edges, we can specify a bevels/chamfers:

let chamfered_cube = fj.chamfer(cube, edge_ids);

As for the actual implementation of the chamfer, I think it makes most sense to re-use the (not yet implemented) difference operation. You select edges, and for each edge, the kernel computes the shape that would need to be taken away (a triangle that is swept along the selected edge) and uses the difference operation to subtract it.

[Siithy]

That all makes a lot of sense to me. Only missing a way to classify edges/corners/sides on shapes that weren't extruded.

From a conceptual standpoint, difference doesn't sound particularly hard to implement to me. Is there anything that makes it tricky or is it just a matter of just having a lot of stuff to implement?

[hannobraun]

That all makes a lot of sense to me. Only missing a way to classify edges/corners/sides on shapes that weren't extruded.

Yeah, as I said, this isn't fully thought out. But I'm hopeful that solutions can be found for all operations. We'll see.

From a conceptual standpoint, difference doesn't sound particularly hard to implement to me. Is there anything that makes it tricky or is it just a matter of just having a lot of stuff to implement?

I'm actually working my way towards that right now. The main obstacle is the aforementioned transition from triangles-as-intermediate-representation to boundary representation (#97). I don't think it's practical to implement any CSG operations until this is finished.

This is mostly done. The last holdout are the side faces created by the sweep operation. To finish that last part, we need new capabilities in the kernel, namely sweeping vertices into edges, and edges into faces. And on the geometry side, sweeping points into lines, lines into planes. This also has some follow-on effects, like once we have support for sweeping lines into planes, we don't need a "native" plane representation and can consolidate that code.

All of this should be relatively straight-forward, but I decided to tackle #78 first. This is not strictly necessary, but I figured, maybe it's better to look into that before writing too much more CAD kernel code that would then need to be adapted for this.

Not sure how long this work on #78 will take. I'm still in the exploratory phase and have the feeling that the problem and potential solution don't fully fit in my head yet. I'm hoping I can wrap this up within the next few weeks, then address #97 relatively quickly, then tackle CSG (which is tracked in #42, #43, #44).

[Siithy]

I've made a chunk of the changes locally, and planned out the changes I haven't yet.

One thing I want some clarification on though. In fj/syntax, I'm needing to use nalgebra functions for things like Rotate as the fields are no longer explicitly stored. As it is, fj does not seem to have any external dependencies. Is this a priority to maintain? Is there some mechanism for forwarding dependencies through crate definitions that you want to use?

[hannobraun]

Great to hear you're making progress, @Siithy!

A general note: If you want to get part of your work merged early (for example, replacing Isometry with Transform in the kernel without changing fj), I'm totally open to that. The more ongoing work you have in your fork, the higher the chance there will be merge conflicts with other work at some point.

I don't think this is strictly necessary in this case. Just saying, it is an option, if you want to take it.

One thing I want some clarification on though. In fj/syntax, I'm needing to use nalgebra functions for things like Rotate as the fields are no longer explicitly stored. As it is, fj does not seem to have any external dependencies. Is this a priority to maintain?

It's a priority that incremental changes to models compile fast. For that reason, I've avoided adding dependencies to fj, as I'm not sure how dependencies there would affect model compile times, and so far I didn't want to allocate time to investigate.

I can totally see why you need a math library though. I'd say, just use nalgebra in fj to do the job. If you're up for it, you can make some comparisons to see if/how compile times are affected (i.e. cargo run, make a change to models/cuboid/src/lib.rs, check the output that was passed through from Cargo to see how long it takes to compile with/without nalgebra)

If you don't want to get distracted with this, that's fine though. Let's just solve the current problem (by depending on nalgebra). We can always investigate and optimize later (#14 is relevant).

There's one open question though: While we can certainly use nalgebra to do the math, I'm not sure we can store an nalgebra::Transform in fj::Transform, as fj types need to be #[repr(C)] (see #122). Worth investigating, but don't feel the need to get side-tracked, unless you're interested.

Is there some mechanism for forwarding dependencies through crate definitions that you want to use?

I think if we're using nalgebra anyway, it makes sense to expose it to models through a pub use nalgebra as na; in fj's root module,or something like that.

[hannobraun]

Heads up: I've made some minor changes to the transformation code in the kernel, as part of my ongoing work on #97. This might interfere with the work already done to address this issue.

I think #163 and #168 are all the relevant pull requests, and specifically 622d58e, 0b4ea9a, and d300dd8 made changes to transform functions.

[Siithy]

Noted. Had some life stuff come up so I haven't done much more yet. Hopefully get some time in next weekend.

[hannobraun]

Thanks for the update!

I've made some more changes that indirectly affect transform methods in the meantime. #183 comes to mind.

[hannobraun]

I've made more changes, this time directly to the transform code. See #196.

Sorry for stepping all over your work, @Siithy. The good new is, that changing the transform type used in the kernel should be much easier now, and should mostly require changes in the math module.

[Siithy]

That's fine. A lot of the effort was learning the basics of your code and the math for the transformations.

[hannobraun]

I've made another change that is relevant to the work in this issue: #275

Again, sorry for getting in the way. On the plus side, this has made future change easier yet again, as the transform code is no longer split across many small methods.

[Siithy]

That's fine. I'm just about done with one of my busiest work cycles of the year. Probably will be a zombie this weekend, but i hope to get back on task with this sometime in the following week.

[hannobraun]

Sounds great, thank you @Siithy!

Warning: I expect more changes to the kernel::algorithms::transform module soon, as part of my work on #280. I don't think this will conflict much with this issue though, as the math::Transform type should encapsulate all the changes that are required. Maybe, I think. We'll see.

[hannobraun]

I've made some progress on this issue in #501, hoping I could quickly close a few issues, but (of course 😁) I ran into complications. The problem is the rotate syntax extension method in the fj crate:
https://github.com/hannobraun/Fornjot/blob/a8e933350334e8f64ad22bb1d187dad8f71c2208/crates/fj/src/syntax.rs#L114-L122

If fj::Transform where changed to contain a transformation matrix (i.e. [[f64; 4]; 4]), that method would need to compute that transformation matrix, which is not trivial. Basically, we'd need Rodrigues' rotation formula. Specifically the matrix notation further down on the linked page:

Implementing that without the use of a vector library is going to be a hard-to-debug/understand/maintain pain. Since the fj crate does currently not have access to a vector library, I consider this issue blocked on #122, which in turn is blocked on #14. Adding https://github.com/hannobraun/Fornjot/labels/status%3A%20blocked.

[hannobraun]

My step towards addressing this, making fj_math::Transform more flexible (#501), has been partially rolled back in #523 (for good reason). In addition, there are the problems I mentioned in my previous comment.

I think supporting arbitrary transforms would have been a good idea, if it was easier. Then it would have been a nice experiment. But given the difficulties, and since there aren't any specific benefits beyond "would be cool, let's see how this goes", I've decided to close this issue.

[Siithy]

If fj::Transform where changed to contain a transformation matrix (i.e. [[f64; 4]; 4]), that method would need to compute that transformation matrix, which is not trivial. Basically, we'd need Rodrigues' rotation formula. Specifically the matrix notation further down on the linked page:
rodrigues-rotation-formula
Implementing that without the use of a vector library is going to be a hard-

Are you sure that this is the case? When I was looking at this, I believe I only used nalgebra functions for the functionality.

[hannobraun]

Are you sure that this is the case? When I was looking at this, I believe I only used nalgebra functions for the functionality.

I'm talking about fj::Transform. The fj crate has no dependencies (so nalgebra is not available), and when I tried to add a dependency on fj-math, it had severe effects on compile times (see #122).

[Siithy]

Are you sure that this is the case? When I was looking at this, I believe I only used nalgebra functions for the functionality.

I'm talking about fj::Transform. The fj crate has no dependencies (so nalgebra is not available), and when I tried to add a dependency on fj-math, it had severe effects on compile times (see #122).

Ah, yes. Now I see what you're talking about.