Note: This is an archived version of the Blender Developer Wiki (archived 2024). The current developer documentation is available on developer.blender.org/docs.

User:Howardt/Reports

2021 June 7 - July 25

In the past six weeks I fixed some Boolean bugs and a Bevel bug, and, with erik85's help, added functionality and improved the performance of Constrained Delaunay Triangulation.

For Boolean, I had made a triangulization optimisation for quads that didn't work for concave quads. After an intial fix, which worked but was slower than before, several other commits eventually clawed back the performance loss. Then Erik provided a patch with a number of parallelizations and other optimizations that made nice speed improvements on very dense meshes.

Erik is using my CDT routine to fill curves for his geometry node work, and needed an output mode that detected and filled in holes, so we added that. After that, he found that the performance was quite poor in when there were a lot of holes. This turned out to be due to how faces were being tracked from input to output. A different data structure, some parallelization, and just all-out optionalizing the tracking of faces combined to vastly improve performance in cases like that.

Commits:

  • Delaunay add support for detecting and removing holes from output. Commit rB5f71b1ed.
  • Fix T89330 Exact Boolean fails on a simple model.. Commit rB7223a034.
  • Fix performance regression in Exact boolean due to exact triangulation. Commit rBb8115f0c.
  • Various Exact Boolean parallelizations and optimizations. From patch D11780 by Erik. Commit rBceff86aa.
  • Fix a compiler warning on Windows for Exact Boolean. Commit rB4c716ced.
  • Greatly improve speed of Delaunay when have a lot of holes. Commit rB3c8d2615.
  • Speed up Delaunay raycast. From a patch by Erik. Commit rB24801e0a.
  • Make it optional to track input->output mapping in delaunay_2d_calc. Commit rB72d1ddfc.
  • Update documentation string for mathutils.geometry.delaunay_2d_cdt. Commit rB76f0ef29.
  • Fix crash in delaunay C interface test. Commit rB94717157.
  • Fix bug in assert in delaunay test. Commit rB3cfd6439.
  • Another slight increase in speed for Delaunay CDT. Commit rBde2c4ee5.
  • Fix T89391, etc. Boolean bugs when objects have negative scale. rB0aad8100.
  • Fix T86768, bevel doesn't loop slide sometimes. rB4886ed28.

2021 April 27 - June 6

The past five weeks were pretty quiet for me, but towards the end my activity picked up.

For Exact Boolean, I worked on performance problems, incorporating and inspired by some patches from erik85. Mostly these affect cases where there are a lot of disconnected pieces, each of which have a lot of faces.

For Faster OBJ I/O, I worked more on a test file, and using it, discovered and fixed some bugs in the exporter.

Commits:

  • Exact Boolean performance bug. Commit rB28bf1d40.
  • Boolean: applying patch D11431 to speed up hole-tolerant raycast. Patch from erik85. Commit rBa1556fa0
  • Boolean exact: speedup by parallelizing a plane calculation. Patch from erik85. Commit rB81366b7d.
  • Exact Boolean: speed up when there are many separate components. Commit rB8e43ef5f.
  • Exact Boolean: fix last commit: pass an arg by reference instead of value. Commit rBdbfde0fe.
  • Obj I/O: Fix crash when UVs are not asked to be exported. Commit rB984ab471.
  • Obj I/O: Export transform was wrongly calculated. Commit rB22686b4c.

2021 March 29 - April 26

I have been mostly bug fixing for the last month, though I did take some time out to learn about Geometry Nodes by making a patch for a Smooth node, D10951 (still in review). I also prepared a patch for the Fast I/O 2020 GSoC project's OBJ exporter, D11019, still in review. And I reviewed a patch for a BMesh core test, D10973.

On Exact Boolean, there was a bug related to triangulation, which took several tries to fix. Since switching to the code to bypass BMesh, I needed to do my own triangulation. I had originally used the fast, floating point, polyfill routine that is in Blenlib. But that can produce zero-area triangles in some circumstances. While such triangles are removed by my code before doing the Boolean, removing them can leave holes in the mesh, meaning that the non-manifold-mesh fallback code is used to do the Booleans, which sometimes makes mistakes. So I switched to using the slower but more accurate multiprecision arithmetic Constrained Delaunay Triangulator that I had written for other purposes already. That triangulator doesn't produce zero-area triangles, but it has another problem: if the original face has self intersections when projected on the plane perpendicular to the face normal, then the triangulator adds extra "Steiner" points, which my code was not expecting to see. So I fixed that by falling back to the polyfill triangulator in that (rare) case.

Commits:

  • Fix Boolean exact crash with dependency loop. Commit rB94079ffc.
  • Fix Inconsistent results for exact boolean. Commit rB2d5a715f.
  • Fix Boolean Exact crash. Commit rBf7afd78b.

2021 March 15 - March 28

I made some progress on getting the Fast I/O 2020 GSoC project, on branch soc-2020-io-performance, ready for merge to master. Most of Sybren's comments on the exporter patch have been addressed now.

I also interacted with several prospective 2021 GSoC students, attended several Modeling Module meetings with Campbell / Hans, and reviewed a patch by Hans (D10599).

Commits:

  • Progress towards making material output the same as the python exporter. Commit rBfec16d4a.
  • Fixed problem of repeated same materials output in MTL file. Commit rBccc97b66.
  • Fix a bad default assignment and an unused parameter. Commit rBbfea06a6.
  • Put the blender file basename in comment in the header of the .mtl file. Commit rB85ab8eaa.
  • Bevel code: add a null pointer check. Commit rB057292e7.
  • Fixed up the TODOs re materials left when making it compile again. Commit rB8268e687.


2021 March 8 - March 14

I fixed two bugs and made a tiny bit of progress on the OBJ I/O code.

Commits:

  • Fix T86390 Exact Boolean crash. Commit rBe8e4a795.
  • Fixed T86427 Boolean Modifier "Exact" solver does not apply target object material to created faces. Commit rBa01fb22f.
  • Fixed up the TODOs re materials left when making it compile again (soc-2020-io-performance branch). Commit rB8268e687.

2021 March 1 - March 7

I had some bug fixes to do and a speed regression to fix this week, so nothing new otherwise.

It turns out that the change I reported here for the week of Jan 30, the one that made exact Boolean work on meshes with holes (like Suzanne), caused a dramatic slowdown on large non-manifold meshes. While I don't really guarantee support for non-manifold meshes, I want it to work as well as possible in those cases. The fix I made then was to do inside-outside testing per triangle rather than per patch (a patch is a large set of manifoldly-connected faces). I needed to be able to use the old per-patch way in the usual case, and only use the per-triangle way when needed. Since I couldn't figure out a way to decide automatically, I made a new parameter, Hole Tolerant, which when true, will use the slower method. It is false by default. I had to change the modifier UI to expose this parameter, and since the UI was getting kind of messy with exact-mode specific parameters, I decided to make a separate "Solver options" subpanel to hold them. Commit rB1ba15f1f.

Other fixes this week:

2021 February 22 - February 28

While I started to look at the Fast Obj I/O code, and merged in current master, got no more work done on it this week.

I fixed some bugs:

2021 February 8 - February 21

In that past two weeks I finished an improvement to the Exact Boolean modifier that I've been working on for a while: skipping the round trip through BMesh. This was submitted as rBa3f091d7

When I originally coded Exact Boolean, I didn't need BMesh so I used my own Mesh representation called IMesh. In Blender, modifiers work on Mesh inputs and produce a Mesh output (Meshes are what are persisted in .blend files; they are like BMesh but BMesh includes topology structures that Mesh doesn't have). So it is wasteful to convert all of the operands to BMesh, then to IMesh, then back to Bmesh, and then back to Mesh.

Now with the above commit, the Exact mode Boolean modifier skips the BMesh intermediate forms (and thus, doesn't have to calculate as much topology). On a sample Boolean between two spheres, with a total of 262K quads, the Exact Boolean now goes 33% faster.

I also added some modeling ideas to the GSoC 2021 ideas page.

Next

While I have many more ideas for speeding up Exact Boolean, I think I will take a detour and spend some time on helping get last summer's Fast OBJ I/O into Master. I was a co-mentor for that, and it would be a pity not to have it land.

2021 January 30 - February 7

I'm a volunteer Blender Developer, making contributions in my spare time. My reports may not be every-weekly, and they may be more verbose than some, as I want to explain the reasoning behind what I'm working on.

This week I finished work on and committed rB6f63417b a fix for T84493 and others like it. A nice video of the effect of the fix was posted by a user here.

Exact Boolean with cut through open eye sockets of Suzanne

More Details

The general issue was that Exact Boolean (and Fast Boolean, for that matter) were intended to be volume operations, where all of the operands need to represent enclosed volumes. In particular, the algorithm I implemented for Exact Boolean requires the operands to be PWN (Piecewise constant winding number), which approximately means that the edges are all manifold. The code has an algorithm that determines "insideness" and "outsideness" by partitioning the intersected meshes into cells -- enclosed volumes of space -- delimited by patches -- maximal sets of contiguous faces ending at non-manifold edges. This algorithm doesn't work if the inputs are not PWN.

In cases where the operands are not PWN, Exact Boolean needed a fallback option, because users continue to try to use Boolean in such cases and have expectations about what will happen. Sometimes those expectations are just to take almost-closed operands and behave as if they were closed (as an example, Blender's monkey -- Suzanne -- has open eye sockets, and separate eyes inside them; users would like this to behave as if the sockets were closed). In other cases, users want to use the Difference mode as a way to trim off pieces of a mesh (for example, using a plane to bisect and throw away part of a model).

In the initial release of Exact Boolean, I implemented a "Generalized Winding Number" (GWN) method for determining insideness. It did this for each patch: find a test point on a test triangle, and then project all the triangles onto a unit sphere around that point. The percent of the sphere covered by those projections (paying attention to sign) will be large if the patch is inside, and small if it is outside. That method works OK to determine insideness for nearly closed meshes, but needed some hacky thresholding to handle the trim-by-plane-etc. cases. It was also quite computationally expensive. I used exact arithmetic - almost certainly overkill.

But the GWN method still didn't work for a box cutting Suzanne, even though it seemed to be the perfect almost-closed case. And other bug reports were piling up where non-PWN inputs were causing not-the-expected output - T64554, T84493, T83403, T82642. The problem was that the idea of testing just one sample triangle per patch is a flawed idea. When the top of a box goes through the open eye sockets of Suzanne, it causes a single patch that is both inside the head and outside it. So, depending on where the test triangle is, you might either keep or remove the whole patch, which is not what is expected.

What does Fast Boolean do? It uses raycasting to determine insideness: it shoots a ray along the positive x-axis from a point on a test triangle from its equivalent of a patch. It counts the number of intersections with the other mesh operand, and uses the evenness or oddness of that count to determine outsideness / insideness. Raycasting is not too expensive if one has a BVH tree of all the triangles, which Fast Boolean conveniently already had for another reason. You can see that this method has its own problems: it has the same testing-only-a-patch problem mentioned above, and it also is only testing one ray direction, which may or may not work on a partially enclosed volume, basically depending on luck.

I decided to use raycasting too, but modified from the Fast Boolean method in two ways. First, I test every triangle in one operand to see if it is inside the other, rather than one triangle per patch. This will, unfortunately, make for a big slowdown, but is necessary to get the expected results for things such as Suzanne. Second, I shoot in 6 directions, almost but not quite axis aligned, and use a threshold for how many of those directions indicate inside versus outside to make the final determination. The Fast Boolean raycasting does more work per cast: it uses water-tight raycasting and also sorts the hits to catch cases where a ray might go through an edge and therefore get counted twice at a particular intersection. I decided to slightly skew the ray directions and by using a voting system for six directions, hopefully be less likely to hit edges and more tolerant if I do so. We'll see if bug reports come in that make me live to regret and revise that decision.

Note that this still doesn't guarantee that Boolean will do what users expect in 100% of the cases, but it will handle more now, I hope.

One thing to think about for the future: the trim use case doesn't really want to do Booleans: it wants to discard everything outside of a given volume or implied volume (e.g., whole side of 3space on one side of a surface). I think there should be more modes -- besides Intersect, Union, Difference -- for using the basic Boolean code to get the trim effects that users sometimes want.

Next

What I intend to do next is return to a patch D9957 that I made a while ago to speed up Exact Boolean when used as a modifier. The idea is to avoid the round trip in and out of BMesh. Campbell mostly approved the patch, but I have to do a better job of dealing with Custom Data when there are multiple layers of the same type.

Retrieved from "https://wiki.blender.org/w/index.php?title=User:Howardt/Reports&oldid=25755"