[Bug] Cant close last edge of a plain surface

[kroozo]

Hi,

Sorry, testing around :)

So, when I try to assemble a plain surface, I can't close the last edge.

A minimal example:

It's a simple cube, I've subdivided on side, the small rectangle is the last piece.

If I close the edge, the last one remains:

And even if I click on it, nothing happens.

On the exported svg, both a fold line and a flap is added:

(The cut line includes the edge as well as cut line, it just overlaps).

This sounds like wanted behavior unless all the pieces form a flat surface (obviously, if there was an angle, the there would be a small opening with a flap), I guess this is just an edge case.

I have checked if maybe the hidden fold angle has an effect on this, but it hasn't.

[rodrigorc]

Sorry, testing around :)

Don't worry, I really appreciate you take the time to test and write things.

This sounds like wanted behavior unless all the pieces form a flat surface

This is by design. You are right that if all the triangles in this piece form a flat surface, it could be done in principle, and the uses might find it useful. In fact I tried to implement it once, by rebuilding the whole model, but I failed.

The issue is not whether the face is flat or not, but that my geometry computations rely on the piece being a tree of faces. With tree I mean a "direct acyclic graph", that is that you cannot travel from face to face, following folds, and do a loop without walking back.

My n-gon tessellation algorithm is carefully built so that it always produces trees; joining two trees always result in a tree; splitting a tree always gives two trees... but if I let the user join two edges of the same piece together... no more a tree and the program will crash!

In fact, I'm not checking that the pieces are trees anywhere (probably should, at least when loading a .craft file). I'm just assuming that is always the case.

Naturally, for your particular model, you can just go back to Blender and dissolve all 4 edges. Note that you can still have this face with 8 sides, that is totally ok.

As a footnote, to handle these issues I find particularly useful in Blender the options "Limited Dissolve", "Make Planar Faces" and "Split Non-Planar Faces".

[kroozo]

If this is hard, then this is certainly something you can live with, and fix it in the model or post processing, I thought this was a byproduct, not a feature of the model. (But now that you say that I think I can remember some odd case when joining two sides gave some odd overlapping render :) )

And yes, strictly acyclic is in most of the cases makes thing easier :) Having said that, there are pretty robust ways of dealing with "real" graphs. I am assuming from what you say that your model basically starts at a face, its children of all (uncut) edges, those having a child to the other connected face, and so on. And when you cut or join, you basically remove or restore a possible child connection.

I'm guessing that since you look at this as a tree, you're probably doing a depth first walk (because that's the pretty straightforward recursive implementation: you just call yourself on all children). You can adjust that to graphs by keeping track of visited nodes, and simply not processing anything twice. Through DFS does have some issues: it can loop in certain conditions (that I can't remember :) ), the order it gives you is somewhat arbitrary, and I'm guessing not really optimal, for what you're doing, so I'd consider some breadth first approach, that is going to get you a more even walk ordered by distance from the root. It's main disadvantage is it is O(jesuschrist) on memory, but given the practical limit of this software is somewhere in the thousands node range anyway that should not be a huge issue.

[rodrigorc]

Even Blender has some limitation with face geometry. For example it will not let you build an n-gon with a hole. I'm not sure why, maybe it has to do with the tessellation not creating a DAG, or with having two contours, or something different.

I am assuming from what you say that your model basically starts at a face...

That's exactly it, in fact, when you import a model, all faces are split, so they are trivially DAGs. Then I just have to prevent loops and they will always be DAGs.

I'm guessing that since you look at this as a tree, you're probably doing a depth first walk...

That would be my guess, too... but I'm actually doing "breadth first walk" :nerd_face: . Take a look at the core of the "island walking" algorithm traverse_faces_ex, it is a bit heavy on generics because it is used for a lot of different things, but you can see the classic two sets of open and visited nodes. The actual memory usage will depend on the generics used to call it.

I discarded the easier recursive algorithm because of the possibility of a model with a very long strip of faces: that could easily overflow the stack. In papercraft it's easy in principle, to do a strip with thousands of faces, but not so easy to do a face with thousands of neighbors.

--

I've been thinking on why this can't be done, and tried a few experiments... I think that the main reason is not the tree thing, that could be fixed, but that co-planar faces are never actually 100% exactly co-planar. That happens for an N-gon, too, but for that I assume that the model is sensible: I tessellate it, compute the plane of a random triangle and project all the other triangles to that plane. Good enough. But when drawing an island with a loop I cannot do that, each face has its own plane, and the the final edge will almost never match exactly.

I mean, with a DAG the position of a face is decided only by the position of its single parent and the angle between those two faces. Easy and deterministic. But with a "real" graph, the position of a face will have to match that of any of its neighbors... I don't think that will work.