Lift limitation, that coincident `HalfEdge`s must be congruent
hannobraun opened this issue · 9 comments
The approximation code makes the assumption, that coincident HalfEdges are always congruent. This requirement is documented, as is the reason for it.
I'd like to implement an operation that can split the faces of a shell, which will be useful for further manipulation of the shell. In the presence of such an operation, maintaining this limitation becomes wholly impractical. Hence, I think it's time to remove it. This will require changes to the object graph.
I'm sure an appropriate design will reveal itself as I'm working on it, but for now I'm thinking we need a new object to represent a curve in global space. That would then be referenced by HalfEdge, and GlobalEdge would become redundant and could be removed. But we'll see how it shakes out. (Idea on nomenclature: Maybe the current Curve can become Path or SurfacePath, then the new object can be called Curve.)
Hi, I'm still new to this repo, but I think I understand the problem.
Approximating / Meshing a Solid requries knowledge of which edges are coincident, such that no gaps between connected faces appear due to approximation errors.
I wonder if Faces in a FaceSet (named FaceGroup in Ian Strouds book) should have to be continuous. This means that neigbouring faces in a FaceSet always have a joined HalfEdge. Then, a FaceSet could store the information for the Global Edge / Curve object.
I think the idea of renaming Curve to SurfacePath and calling the new object Curve makes sense. I think it helps to try to stick to the naming conventions from Ian Stroud - Boundary Representation Modelling Techniques.
Thank you for the feedback, @TobiasJacob!
Approximating / Meshing a
Solidrequries knowledge of which edges are coincident, such that no gaps between connected faces appear due to approximation errors.
Yes, and we have that knowledge because coincident edges must reference the same Curve (previously the same GlobalEdge; right now both the new Curve and the old GlobalEdge exist in parallel).
I wonder if
Facesin aFaceSet(named FaceGroup in Ian Strouds book) should have to be continuous. This means that neigbouring faces in aFaceSetalways have a joinedHalfEdge. Then, aFaceSetcould store the information for the Global Edge / Curve object.
Please note that FaceSet has no inherent meaning in Fornjot. It's just a utility wrapper around a BTreeSet<Face> (or something along those lines). There is Shell though, which fills the role that you suggest here, I think. We have validation code (a bit of a mess right now, due to the transition from GlobalEdge to Curve) that checks that each Shell is watertight (you used the word continuous, but I believe we mean the same thing).
I think the idea of renaming Curve to SurfacePath and calling the new object Curve makes sense. I think it helps to try to stick to the naming conventions from Ian Stroud - Boundary Representation Modelling Techniques.
Yeah, that's what I ended up going with. I haven't updated this issue as I've been working on it, but if you check the list of merged pull requests above your comment, you can see that I've been making progress.
I was actually heavily inspired by the Stroud book originally, but I've deviated from it where I thought it made sense. I do like Shell better than FaceGroup, as the former seems more descriptive to me. But I agree that it makes sense to stick to established terminology, unless there's a good reason to deviate. Feel free to make suggestions, if you see anything that can be improved!
Thanks for your clarifications!
I spent some more time thinking about the problem.
Not sure if I understood this correctly, but faces are defined on a surface which is bounded by surface paths, with the surface paths being in 2d surface coordinates.
This information is needed, for example, for converting the surface into a triangle mesh, to figure out the boundaries of the surface.
However, two connected faces share two surface paths, which is redundant information, because they have to refer to the same 3d curve. If one surface path approximation is already cached, the other surface path needs to use that cache. So the whole operation also depends on the order of which surface path is being cached first.
Maybe it makes more sense to store the 3d information in the curve. This curve object is unique for all faces connected to it. It can be cached to get the 3d positions of all points. This could then be projected back onto the surface with the
pub fn project_global_point(&self, point: impl Into<Point<3>>) -> Point<2> {
function to figure out the 2d surface path.
Always projecting the 3d curve back onto the 2d surface might be a little bit slower than storing the boundary information directly, but it would remove the complexity of having redundant information and obey to the "single source of truth" principle.
Thank you for thinking about this, @TobiasJacob! Not a lot of people are digging into the core of Fornjot, so I appreciate any feedback I get.
Not sure if I understood this correctly, but faces are defined on a surface which is bounded by surface paths, with the surface paths being in 2d surface coordinates.
This information is needed, for example, for converting the surface into a triangle mesh, to figure out the boundaries of the surface.
However, two connected faces share two surface paths, which is redundant information, because they have to refer to the same 3d curve. If one surface path approximation is already cached, the other surface path needs to use that cache. So the whole operation also depends on the order of which surface path is being cached first.
Yes, that sounds about right.
One note though, about the result depending on order of evaluation: Maybe you already understand this, but in general there are validation checks to make sure that stuff looks as it should (although those are not complete; there are a few open issues). So the differences we might get due to evaluation order are quite tiny, and shouldn't ever make a difference in practice.
This might still cause problems, if the user is relying on determinism (e.g. comparing an already created mesh with a new one, for some reason), but that sounds like a surmountable problem. We could just make sure that the order of evaluation is always well-defined.
Maybe it makes more sense to store the 3d information in the curve. This curve object is unique for all faces connected to it. It can be cached to get the 3d positions of all points. This could then be projected back onto the surface with the
pub fn project_global_point(&self, point: impl Into<Point<3>>) -> Point<2> {function to figure out the 2d surface path.
Always projecting the 3d curve back onto the 2d surface might be a little bit slower than storing the boundary information directly, but it would remove the complexity of having redundant information and obey to the "single source of truth" principle.
Maybe it does, but I'm not sure.
First off, these surface coordinates are only associated with 3D data in the context of a Solid. In the context of a Sketch, you only have 2D data. Solid and Sketch share the same objects from Region downwards, so we can't introduce 3D coordinates there without upsetting this whole structure.
Second, and I might be missing something here, I can't think of a way to do this that would actually remove the redundancy. I think rather, we'd just shift it around. For example, you have a surface and a curve. The curve must always be on the surface, because otherwise a face would be invalid. With the current approach, it is guaranteed that the curve is in the surface, as there's simply no way to express the curve otherwise. With your proposal, it would be possible to define a curve that is not part of the surface.
The reason for that is, that the definition of the surface and the curve is partially redundant, if both are defined in 3D. That redundancy is not as apparent as it is with the current approach (you don't have two structures that literally are the same thing in 3D), but it is still there. You simply have more degrees of freedom than you need.
Plus, projecting global points into a surface is not enough. We'd need code to project whole curves. Check out the intersection code, for examples. I think there are a lot of intersection checks here that couldn't be written without local (non-3D) data.
So yes, we could do what you propose. But I'm not convinced it would actually end up being better. (And actually, the object graph used to work more like you propose, storing 3D coordinates. That didn't work out too well back then, but I don't think that alone is a reason to reject your proposal. Many other things have changed, and the object graph has become much simpler, so it could be worth another try.)
All that said, what we currently have is certainly not the final word. We are way too limited in the kind of geometry we can even express (without resorting to an approximation with many flat faces). And when we think long-term, about topics like NURBS, I don't think it would even be possible to define the 2D curves analytically then. I think SolveSpace defines curves as intersections of NURBS surfaces, which sounds like a good approach.
I've been thinking about that stuff for a while, but I haven't come up with a firm solution. But I think we don't want to lose the ability to define 2D only stuff. (You might want to reuse a sketch to extrude some shape on multiple faces, for example. And some use cases don't require 3D at all, and you end up exporting to DXF or SVG in the end.) I also don't think it's desirable to have redundant object graphs for 2D and 3D.
Not sure what the solution will end up being.
Thanks for this long response! I'm definetly interested in a new, open-source and easy-to-use CAD Software because I'm not satisfied with current software. Also, it would be nice to have python bindings like SolidPython.
I'm not sure yet how we could integrate this best, but it might be a major restructuring.
Second, and I might be missing something here, I can't think of a way to do this that would actually remove the redundancy. I think rather, we'd just shift it around. ... With your proposal, it would be possible to define a curve that is not part of the surface.
You're right, it's shifting the redundancy to another place and there is a new constraint for the curves to be a part of the surface.
And when we think long-term, about topics like NURBS, I don't think it would even be possible to define the 2D curves analytically then.
I wonder if the intersection of two NURB Surfaces is a NURB Curve in 3D.
I started thinking about if it is possible to define all edges as intersections of two faces + a start face + an end face. But I think this could become difficult for cases like below, if there are multiple intersections between two sufaces. With an intersection based approach it would be difficult to differenciate between the curve from B to C and the one from A to D.
So I think if we accept the redundancy as a necessary evil, the question becomes where to store it so it's the least pain to carry it around.
I have the feeling that storing it in 3d is easier. Lets say for example we want to join 2 Spheres together. We could represent the intersection as a 3d circle, but I'm not sure about a solution in surface coordinates.
For rendering it we could rasterize the circle and project it into surface coordinates of the spheres. All other operations (Extrusions, Revolutions, Sweeps, Union/Intersect/Difference) would have to be defined in 3d.
Thanks for this long response! I'm definetly interested in a new, open-source and easy-to-use CAD Software because I'm not satisfied with current software. Also, it would be nice to have python bindings like SolidPython.
I'm not sure yet how we could integrate this best, but it might be a major restructuring.
I don't think I want to maintain any language bindings as part of this repository though, at least not any time soon. But I'd love to see this, and I'd be happy to make merge changes here to remove any hurdles.
I wonder if the intersection of two NURB Surfaces is a NURB Curve in 3D.
My understanding is no, but I'll now stop speculating about stuff that I know nothing about 😄
I started thinking about if it is possible to define all edges as intersections of two faces + a start face + an end face. But I think this could become difficult for cases like below, if there are multiple intersections between two sufaces. With an intersection based approach it would be difficult to differenciate between the curve from B to C and the one from A to D.
Yeah, there are definitely problems. I don't know. It's just something I've been thinking about in the back of my head.
So I think if we accept the redundancy as a necessary evil, the question becomes where to store it so it's the least pain to carry it around.
I have the feeling that storing it in 3d is easier. Lets say for example we want to join 2 Spheres together. We could represent the intersection as a 3d circle, but I'm not sure about a solution in surface coordinates.
Don't forget my arguments about 2D-only environments (i.e. sketches) though. I'm pretty sure we'll end up with some kind of hybrid solution.
The changes to the object graph that I talked about in the issue description are done now. What remains to address this issue, is to update the approximation code. I've been making progress on that, but it has turned out rather tricky.
I'll be on vacation for the next 1-2 weeks, so don't expect any more progress until September!
I'd like to post a quick update, to put the recent (and upcoming) pull requests into context.
As I've said before, what remains to be done is to update the approximation code. The core piece here is the caching of approximated curves. Right now, it's super-simple, assuming that approximations for different curve segments never overlap. To lift the HalfEdge congruency limitation, it needs to be more flexible: Handling overlaps, handling partially available approximations, etc.
I've been working on a local branch for a while, where I was implementing a new curve approximation cache that fulfills these requirements. However, this got a bit more complex than I thought. Switching over to that new cache once it's done would have in itself been a big change. And finishing the cache before that switchover became quite hard. Without integration into the existing code, I struggled to make design decisions, as I had to basically foretell how that integration would look like before it was done (or even started).
Things got a bit out of hand, so I decided to change course. Using the insights won from working on the local branch, I started implementing the new curve cache incrementally, submitting pull requests as I went. This in turn led to new insights, which I've been merging into my local branch. This is an iterative process, and with each iteration, main and my local branch become a bit more similar. I expect this to continue, until my local branch is fully merged into main.
As of #2020, my local branch is fully merged. And as best as I can tell, that means the curve approximation cache is finished. Next, I need to update the code that uses the curve approximation cache, as that doesn't make use of the new capabilities yet.