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:
- Fix T85948 Exact boolean crash with some nonplanar ngons. rBf3d60c68
- Fix T86082 Bevel messed up UVs on some multisegment bevels. rBfbba239e
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.
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.
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.
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.