Mesh support for n-gons with holes #68888

This is useful in CAD pipelines.

There may be enough reasons to not support ngons with holes (it adds complexity to addons and tools).

If this is the case we can close this task as long as this is properly documented in the development wiki.

Added subscriber: @dfelinto

Added subscriber: @ideasman42

This seems more like a design task, were we have to weight up the pros and cons.

There are significant advantages in having to relatively simple mesh structure.

I think there might be some conflicting goals with support for holes and high poly mesh modeling as well.
Where supporting holes will slow down mesh evaluation in other areas.

This also complicates the mental model for users (with holes we need ways to group/ungroup faces, users will manage to end up with degenerate cases - holes that don't overlap, accidentally merging faces that aren't co-planar etc).

I'm curious if modeling applications which support high-poly sculpting also support meshes with holes,
and if they do this using the same data-structures internally.

It may be that we need different data structures for this - or, that only a sub-set of the modifier stack supports holes, when a mesh has holes we use a different tessellation method and don't attempt to use the same feature-set.

We should also consider this is a fairly complex project, as well as increasing the complexity of code developed in the future.

Added subscriber: @PabloDobarro

I'm curious if modeling applications which support high-poly sculpting also support meshes with holes,
and if they do this using the same data-structures internally.

@ideasman42 Other sculpting applications don't support ngons at all, they triangulate all ngons when importing a mesh

@PabloDobarro, interesting.

From the looks of it Maya supports holes in faces and has a sculpt tool,
although I didn't use either - just noting that it seems at least one other application does this.

My concern is having n-gons w/ holes will impact our ability to deal with high poly meshes as efficiently.

@ideasman42 We are about to remove the multires memory optimization, entering sculpt mode with a high poly sculpt is going to be slower and it is going to take more memory. Supporting a more complex mesh structure may make the problem worse.
For me, the ideal solution would be having two different mesh structures, one specifically designed for high poly meshes (it could even not support ngons or lose geometry if we can make it faster by doing that), and another full featured one, supporting ngons with holes if necessary. The high-performance mesh structure could be limited to sculpt mode/object mode, without support for modifiers or shape keys. We can do the conversion only if one of those features is used and give the user an option to disable all unsupported features and convert the mesh back to high performance if needed.

@PabloDobarro, this is probably the way to go irrespective of hole support.

Even if sculpt is made into a special case, we will want to be able have reasonably high poly meshes go though the modifier stack (animating detailed characters for example).

Added subscriber: @mont29

Honestly, I’m not sure that adding holes-in-faces support is a critical feature we really need in Blender currently. As already said, this will make things much slower and/or much more complicated, and our mesh codebase is not exactly a simple area already, we already have two different data models (at least, not counting specialized stuff for sculpting, some modifiers like subsurf, etc.).

I would rather add a proper IO support for such features ( #46761 (Add support to tessellate 'ngons with holes' in mesh's validate() func? Much useful for importers (FBX, OBJ...)) already exists since years for the import side, think we could also have something that generates faces with holes from co-planar polygons for exporters, maybe?). That would keep that aspect in a well-defined and confined area, and prevent it from spreading all over our codebase.

We could have basic support for holes, eg: keep the mesh structure virtually the same as it is now, only adding flags to denote holes (add a flag for a complex polygon, and a flag for polygons after it to be used as holes).

Initially the complexity would be limited to tessellation (which could be kept as it is now unless holes are used), however tools and some modifiers would still need to be updated to handle this properly.

Noting it as an alternative since it would allow more gradual support for holes compared to a larger overhaul of the mesh format, although it risks remaining half-implemented since properly supporting holes for all tools would still be a lot of work.

Added subscriber: @Ivo

I’m sorry for disturbing your discussion here (please keep it going), Taking my first steps in mesh modeling, I already find it difficult to get my head around triangles, normals, n-gons, degenerate stuff-stuff, co-planarity. If suddenly a hole appears in my mesh faces because some tool or modifier decided that it should an can do that, I would be hopelessly lost on a mental picture of what a non-coplanar (?) hole in my n-gon even means and what effect it will behave under further operations; let alone if it is somehow degenerate (?). Could I still enjoy playing with geometry which such beasts around?

@Ivo it's a valid point, the counter to this would be that well designed tools would minimize confusion for the user.

Sketchup has meshes with holes and seems quite usable. Even so, this would need to be integrated with Blender's existing mesh editing feature-set, unless we have a new object-type + edit-mode.

Added subscriber: @Josephbburg

Someone mentioned Maya's support for holes in faces and sculpt tools: it's worth mentioning that Maya's sculpt tools don't support non-manifold geometry at all (nor deformers or skinning, and it has major limitations for display).

Are any developers familier with Blender's mesh code interested to support this?

I'm not convinced this is worth the significant additional effort & complexity for tools, modifiers and drawing.

If maintainers of mesh-system, modifiers and drawing code are not pushing to support this, I think this task could be archived.

Added subscriber: @testure

In #68888#759424, @ideasman42 wrote:
We could have basic support for holes, eg: keep the mesh structure virtually the same as it is now, only adding flags to denote holes (add a flag for a complex polygon, and a flag for polygons after it to be used as holes).

This is something I've suggested in the past and agree that it's a good compromise solution. I have some mockups I would need to dig up but the idea was that if you flag ngon support edges and simply hide them, tool/addon authors can account for them and make their own decisions on what happens. For example, loop selection on the hole becomes trivial, where it takes two attempts currently due to the support edge breaking the loop (and no discernable difference between the user-made edge and the one added internally to support the ngons).

Alternatively you could flag them and not hide them, the benefit would be the same. As long as tool authors have a way of knowing that an edge is not user-constructed geometry we can work around a lot of the limitations with the current bmesh ngons.

Added subscriber: @howardt

I was about to suggest the same thing eldee said: flagging "support edges" as such, so that the only thing affected is display and selection of edges and perhaps export to file formats that support holes. I too think this is a decent compromise. But it is likely to uncover a number of cases where current code has to be modified to take account of these as hidden, else users will be surprised. E.g., bevel and inset and boolean may all give strange and buggy-looking results if not updated; similarly some select types (e.g., selecting ngons of a given # of sides) will appear buggy unless fixed.

I'll append here what I wrote on a devtalk thread, though it echoes many things that have already been said above:

As a mesh tools developer, I am of two minds about supporting holes.

On the pro side:

Clearly users want this.
It makes some algorithms easier to implement: it is a pain to deal with booleans or knife cuts that make a hole right now, because you have to arrange for 2 support edges to be added to connect the hole to the surrounding face. (However, this by itself doesn’t solve all the problems: Blender also doesn’t want vertices repeated in a face, so there are other funny cases that knife and boolean have to fix up with extra support edges anyway.)

On the con side:

A large amount of code, both inside Blender and in addons, has been written assuming that faces do not have holes. All of that code would not work (in the best case) or maybe crash (in the worst case) until updated to deal with holes. This is a pretty massive undertaking. The fact that you can do this with 2D curves is a proof that it can be done but doesn’t negate the fact that there is a massive amount of work to do to get this to work. And it is not easy to figure out everything that has to change: sometimes when one is developing an algorithm, one assumes certain “invariants” are true and writes code that is correct assuming those invariants hold. Developers are not great at documenting all such hidden invariant assumptions, so it may be a long difficult task to uncover all of the bugs that would be introduced by introducing holes.
Maybe there’s a performance or memory concern. At the very least, faces are likely to take at least 8 more bytes each in BMesh face (the way the ifdef’d-out code works). Maybe with careful attention the performance and memory effects could be very minimal, however.
Maybe this makes it harder to export to other 3d formats that don’t allow holes. Though one could always add the needed support edges on export, so this isn’t too big a deal.
I would estimate that it might be a 3 month full-time job to put holes properly into Blender’s BMesh and Mesh representations. Doable, but needs to be prioritized and balanced against other things that the developers could be doing.

Personally, I am somewhat interesting in tackling a project like this but it seems lower priority than the things I am working on now. And maybe higher priority in general is the project mentioned above about having a higher-performance-less-featureful mesh structure for high-poly work.

I was about to suggest the same thing eldee said: flagging "support edges" as such, so that the only thing affected is display and selection of edges and perhaps export to file formats that support holes. I too think this is a decent compromise. But it is likely to uncover a number of cases where current code has to be modified to take account of these as hidden, else users will be surprised. E.g., bevel and inset and boolean may all give strange and buggy-looking results if not updated; similarly some select types (e.g., selecting ngons of a given # of sides) will appear buggy unless fixed. I'll append here what I wrote on a devtalk thread, though it echoes many things that have already been said above: As a mesh tools developer, I am of two minds about supporting holes. On the pro side: * Clearly users want this. * It makes some algorithms easier to implement: it is a pain to deal with booleans or knife cuts that make a hole right now, because you have to arrange for 2 support edges to be added to connect the hole to the surrounding face. (However, this by itself doesn’t solve all the problems: Blender also doesn’t want vertices repeated in a face, so there are other funny cases that knife and boolean have to fix up with extra support edges anyway.) On the con side: * A large amount of code, both inside Blender and in addons, has been written assuming that faces do not have holes. All of that code would not work (in the best case) or maybe crash (in the worst case) until updated to deal with holes. This is a pretty massive undertaking. The fact that you can do this with 2D curves is a proof that it can be done but doesn’t negate the fact that there is a massive amount of work to do to get this to work. And it is not easy to figure out everything that has to change: sometimes when one is developing an algorithm, one assumes certain “invariants” are true and writes code that is correct assuming those invariants hold. Developers are not great at documenting all such hidden invariant assumptions, so it may be a long difficult task to uncover all of the bugs that would be introduced by introducing holes. * Maybe there’s a performance or memory concern. At the very least, faces are likely to take at least 8 more bytes each in BMesh face (the way the ifdef’d-out code works). Maybe with careful attention the performance and memory effects could be very minimal, however. * Maybe this makes it harder to export to other 3d formats that don’t allow holes. Though one could always add the needed support edges on export, so this isn’t too big a deal. I would estimate that it might be a 3 month full-time job to put holes properly into Blender’s BMesh and Mesh representations. Doable, but needs to be prioritized and balanced against other things that the developers could be doing. Personally, I am somewhat interesting in tackling a project like this but it seems lower priority than the things I am working on now. And maybe higher priority in general is the project mentioned above about having a higher-performance-less-featureful mesh structure for high-poly work.

Howard, just for clarification, are the pros and cons you listed in relation to actual holes in faces (ie, multiple loops per face) or does that also apply to the tagging solution?

Obviously I don't speak for all addon developers, but faces with holes seems like it could be an easy can to keep kicking down the road (for the reasons already mentioned). If the realistic options were 'feasible stopgap solution' or 'nothing' I'd vote for the stopgap solution, personally.

Eldee, they were pros and cons about the actual-holes-in-faces BMesh solution.

For the tagging solution, I would say some amount of "discover the bug due to there being hidden edges and fix it" con would still be there, but it would be less severe. I am also not familiar enough with the display and rendering code in Blender to know how much pain this would cause.

Thinking about it a bit more, I think we could solve some of issues you mentioned with a tagging solution if we left the support edges visible but displayed them in a slightly different way to indicate their nature. (See the mockup I've attached). In this example, you can see that the 'support edges' are tagged and displayed differently than normal edges. This would allow them to remain selectable like normal edges, and would inform the user about the underlying geometry that could have an impact on tools like bevel and inset. I imagine users could even select and manipulate them (re-connect them to different verts if the automatically generated solution is not optimal or interferes with a tool). I think this could also help new users understand the difference between an edge they can dissolve and an edge they cannot. It would be intuitive visual feedback to say "dotted edges are different than normal edges for these reasons, and cannot be dissolved". Currently there's a UX issue where a user could create an ngon like the one in my example and attempt to dissolve one of the supporting edges and have it fail without understanding why.

And of course, with the support edges tagged- now you could have tools like loop selection that correctly account for these types of edges and handle the direction change while walking the loops. You could have tools like Bevel detect adjacent support edges and automatically un-check the Loop Slide option. Such a tag would enable a lot of interesting workarounds to holes in faces. And obviously it doesn't solve all of the situations CAD users would want out of a system like this, but I think it checks enough boxes that people would be happy until that point in the future where such an undertaking is feasible.

Added subscriber: @jeacom

From this thread on Blenderartists, my impression is that performance is a bigger concern, people are not happy about how slow edit mode is. If adding more checks for edges or a more complex mesh datastructure could be done without slowing even more the viewport it would be fine.

https://blenderartists.org/t/retopology-design-task/1172311/105

In #68888#764808, @jeacom wrote:
From this thread on Blenderartists, my impression is that performance is a bigger concern, people are not happy about how slow edit mode is. If adding more checks for edges or a more complex mesh datastructure could be done without slowing even more the viewport it would be fine.

https://blenderartists.org/t/retopology-design-task/1172311/105

I'm just guessing here, but I can't imagine it would be any more overhead than the other tags we already use- for example, boundary edges and UV Seams are already tagged and updated each time geometry changes, and the average mesh is going to have far fewer ngons with holes than UV seams. Additionally, this 'support edge' check already exists (in one form or another)- the logic to know whether or not an edge supports an ngon is already needed to prevent the user from being able to dissolve it. That's not to diminish the importance of viewport performance, which of course is paramount- but the optimizations mentioned by Pablo and Howard will have far more impact than something like this.

Added subscriber: @AlbertoVelazquez

I think that it's not really necessary. The few users that ask for this is only because they don't have any way to work with nurbs surfaces and they are searching a way to avoid this limitation. From my perspective, although somewhat useful this, its real usefulness would be minimal compared to everything that would imply in the modeling. But taking into account that you can easily avoid the problem today.

If possible it would be more useful to improve the support of Nurbs surfaces, in addition to opening a completely new user sector to blender from the field of architecture and engineering.

Added subscriber: @1D_Inc

In #68888#757780, @ideasman42 wrote:

There are significant advantages in having to relatively simple mesh structure.

Definitely.

The problem is that thing like the level of abstraction is the thing around which software is being built.
Every lower level provides better flexibility, every higher level provides better parameterization ability, but also more restrictions and rules of more complex engine.

Here is system's abstraction level scale:

Blender was built around the concept of a highly flexible mesh system, so it have a lot of advantages in this area, like dyntopo sculpting and organic modeling. Also, due to this, Blender is awesome in fixing meshes obtained from other apps.
3ds Max doesn't have such Ngon system yet, but it have higher level of abstraction (like editable poly), that gives better native possibilities for parametrization, but also inherits problems, like setting sharp edges or multimaterials ID assigning.
Don't know about Maya, all videos with booleans in meshes gives same result as in 3dsmax.
Sketchup was built around semi-solid mesh representation, so it have such Ngons (and also auto-cutting holes feature ), but inherits limits of that level of abstraction, so sometimes such Ngons are interpreted pretty much poorly even by Sketchup itself. That's why models obtained from Sketchup are that legendary messy (abstraction level interpretation problems), and it don't have flexible mesh editing by default.

There is the only way to get higher level of abstraction for such systems in software development - provide a layer of a higher level of abstraction.
So, in case if Blender will get such Ngons, it will no longer be lowest abstraction level mesh anymore. That will be another abstraction level, with ability of converting mesh to it, like editable poly or editable patch in 3dsmax.
Such moves are usually requires better reasons, than cutting multiple holes, because this is how serious industry solutions are usually created.

> In #68888#757780, @ideasman42 wrote: > There are significant advantages in having to relatively simple mesh structure. Definitely. The problem is that thing like the level of abstraction is the thing around which software is being built. Every lower level provides better flexibility, every higher level provides better parameterization ability, but also more restrictions and rules of more complex engine. Here is system's abstraction level scale: ![MESH.png](https://archive.blender.org/developer/F7819119/MESH.png) - Blender was built around the concept of a highly flexible mesh system, so it have a lot of advantages in this area, like dyntopo sculpting and organic modeling. Also, due to this, Blender is awesome in fixing meshes obtained from other apps. - 3ds Max doesn't have such Ngon system yet, but it have higher level of abstraction (like editable poly), that gives better native possibilities for parametrization, but also inherits problems, like setting sharp edges or multimaterials ID assigning. - Don't know about Maya, all videos with booleans in meshes gives [same result ](https://youtu.be/4P80nl-KLtw) as in 3dsmax. - Sketchup was built around semi-solid mesh representation, so it have such Ngons (and also [auto-cutting holes feature ](https://youtu.be/AQXdDmaJ9cg)), but inherits limits of that level of abstraction, so sometimes such Ngons are interpreted pretty much poorly even by Sketchup itself. That's why models obtained from Sketchup are that legendary messy (abstraction level interpretation problems), and it don't have flexible mesh editing by default. There is the only way to get higher level of abstraction for such systems in software development - provide a layer of a higher level of abstraction. So, in case if Blender will get such Ngons, it will no longer be lowest abstraction level mesh anymore. That will be another abstraction level, with ability of converting mesh to it, like editable poly or [editable patch ](https://youtu.be/HIlgYQWJ2vE) in 3dsmax. Such moves are usually requires better reasons, than cutting multiple holes, because this is how serious industry solutions are usually created.

@1D_Inc: Blender features some abstractions still: after creating a new UV-Sphere, parameters like location and rotation are presented that can be tweaked before committing the shape to a real mesh. I can imagine that the commit could be postponed to allow the user to change some parameters at a later stage (I've seen proposals for this support before). But that should also postpone any mesh-based editing. Those shapes would 'live' as ghosts between the real meshes. A disadvantage is that the algorithm that generated the shape in the first place needs to be linked to the shape and remain available for later adjustments. Not so difficult for the UV-sphere but it may be a tough complication for shapes that are provided by add-ons. Can a user understand the distinction between the two if Blender would not allow 'ghosting' of add-on based shapes?

BUT it would allow application of selected object constraints and object-modifiers such as 'Track To' and 'Boolean' and might circumvent that entire n-gon-with-holes issue.

In #68888#795875, @Ivo wrote:
parameters like location and rotation are presented that can be tweaked before committing the shape to a real mesh.

Problem, that it is not "core mesh abstraction level", like editable patch, for example, but simple decoration)
There were addons that fixes that issue, core features cannot be fixed with simple addons, because reqiures separate math engine.
3Dsmax also have same type of abstrction - you are able to edit new sphere's size only before converting it to regular mesh, that kills that feature, so it is also kind a decorator.

Asked Maya python developer about Ngons. He said

"Previous (old) boolean were creating such Ngons,

new boolean creates support edges:

However, Maya still support multihole Ngons, so edges can be deleted in order to get such Ngons.
But it is a bit not obvious structure type. For example - obj export result:

So it mostly causes more problems than solves.
Multihole Ngons are supported, but you can use them only at your own risk because of compatibility problems."

So abscense of such Ngons basically makes Blender models natively compatible with any other 3d software or format.

Added subscriber: @mavek

Is it possible to identify, via python/bmesh, an ngon with holes versus an ngon without?

I think a good, temporary, fix might be the ability to triangulate just ngons with holes.

The current triangulate options is for everything, including quads. Obviously quads are blenders bread and butter, but ngons without holes seem to work fine now too.

Added subscriber: @Zeirus

Added subscriber: @JosephEagar

Woo! I always regretted my decision not to add holes in faces to the bmesh project; if 3d printers had taken off just a bit sooner I would have. At one point I actually started coding support within the core bmesh data structures but removed it later. It seemed like too big of a change for too niche of a use case.

Nowadays I meet people who use Blender for CAD all the time. I think this is a great idea. I implemented holes in faces in a modeler I wrote years ago (see https://www.youtube.com/watch?v=8Vt0Eu-wygA ), and IIRC the core modelling tools weren't as difficult as I'd feared.

Hey @JosephEagar it is never too late to send a patch for that ;) I do remember the #IFDEFs, but ultimately they were getting on the way since they were never fully implemented.

I wonder if adding holes will make implementing the modelling tools more complicated.

Hi @dfelinto, they do complicate things like dissolve and face splitting. From what I remember from the work I did in AllShape five years ago the hardest part was implementing a decent CDT tessellator, which Blender already has. I remember for subdivision surfaces I literally would triangulate the faces and then run a triangle to quad algorithm; it was "good enough" for a use case that should never happen anyway (why would you use holes in faces with subsurf?).

That said, Campbell might be right to ask if there is a tradeoff between being a high-poly modeler and one suited for CAD. There is a performance cost for complicated, object-oriented BReps. It's not like we were unaware of this; Geoffry Bantle tried to design the core BMesh data structures to be as efficient as possible. If you've heard the game industry's phrase "data-oriented programming" then you know what I mean. Data structures based around lots of small individual objects that are referenced by pointer tend to mess up CPU caches.

@JosephEagar
Well, we are architects, and we have many faces to perforate)
But Blender have pretty much wide range of use. How about the behavior of such ngons with modifiers, UVs unwrap, visualization engines, normals baking, rigging/vertext paint, simulations, import/export formats?
They will influence almost everything.

In #68888#888884, @1D_Inc wrote:
@JosephEagar
Well, we are architects, and we have many faces to perforate)
But Blender have pretty much wide range of use. How about the behavior of such ngons with modifiers, UVs unwrap, visualization engines, normals baking, rigging/vertext paint, simulations, import/export formats?
They will influence almost everything.

Paul, that is the question. It'd be nice if we could keep this within the core modelling toolset. In general I'd like to see some way of allowing a more complicated brep in Blender without having to change every last thing. One of these days I or someone else will try and implement a curve network brep in Blender; imagine a world where edges have curves, faces have trim curves, edges store fillets, etc, etc. The only reason I've not done it already (it's one of my research areas) is I'm not sure how to keep the added BRep complexity from metastasizing to all of Blender.

In principle you could represent face holes by connecting with edges to the outer loop and then mark those edges to be dissolved later. I know that smacks of the hated FGon hack, but it might be worth it. I dunno.

In #68888#888901, @JosephEagar wrote:
Imagine a world where edges have curves, faces have trim curves, edges store fillets, etc, etc.

Yeah, I am familiar a bit with ACIS SAT solid body and IFC file structures.

The only reason I've not done it already (it's one of my research areas) is I'm not sure how to keep the added BRep complexity from metastasizing to all of Blender.
In principle you could represent face holes by connecting with edges to the outer loop and then mark those edges to be dissolved later. I know that smacks of the hated FGon hack, but it might be worth it. I dunno.

I am not sure that it is possible to get stable solid body features in mesh engine without decorative hacks representation. That's the math question)
Sketchup outperformed it, but it was built around such paradigm from the very begining, and it have some limits in order to support such a system.

Changed status from 'Confirmed' to: 'Archived'

There is no developer with time in the foreseeable future to look at that.

In #68888#954873, @dfelinto wrote:
There is no developer with time in the foreseeable future to look at that.

There is no developer team in the foreseeable future to form and design a separate semi-solid mesh paradigm, compatible with
list of possible features that can be reached with separate semi-solid mesh paradigm, like n-gons with holes, curvy ACIS edges, adaptive topology, parametric non-destuctive edit poly modeling that will be asked by 3dsmax users, and so one and so one...

This task is staggering and overwhelming in itself, the chanses of success was very low from the very begining.
I'm not sure how it was created with such a non-revealing reason as "This is useful in CAD pipelines".
Nice that it is closed.

Added subscriber: @MarioCarvao

Download

What's New

Blender Studio

Manual

Developers Blog

Documentation

Benchmark

Blender Conference

Development Fund

One-time Donations

Mesh support for n-gons with holes #68888