avoid sparse indices #1186

pca006132 · 2025-03-09T18:18:06Z

Start removing sparse indices usage in Boolean3.cpp. This is mainly for discussion about invariants that I am not sure about. Closes #972.

The code is really ugly now, but it seems to be working. I will clean it up later. The refactor here is surprisingly simple: just change the binary search to a function call. There is more to be done to make it faster, though.

Performance:

Previously:

Now:

For some numbers:

Previously:
---------------------------------------------------
Threads= 1
Total time
  avg : 179.569
  min : 2.692
  max : 10754.046
Converting MeshGL to Manifold
  avg : 11.869
  min : 1.015
  max : 76.816
Manifold boolean
  avg : 167.559
  min : 1.089
  max : 10702.296
Converting Manifold to MeshGL
  avg : 0.141
  min : 0.003
  max : 1.686

Threads= 16
Total time
  avg : 34.759
  min : 2.903
  max : 1688.115
Converting MeshGL to Manifold
  avg : 6.419
  min : 1.078
  max : 24.742
Manifold boolean
  avg : 28.170
  min : 1.021
  max : 1670.252
Converting Manifold to MeshGL
  avg : 0.170
  min : 0.003
  max : 1.480

---------------------------------------------------
Now:
---------------------------------------------------
Threads= 1
Total time
  avg : 84.570
  min : 2.537
  max : 2886.896
Converting MeshGL to Manifold
  avg : 12.471
  min : 1.016
  max : 77.300
Manifold boolean
  avg : 71.948
  min : 0.943
  max : 2831.661
Converting Manifold to MeshGL
  avg : 0.151
  min : 0.003
  max : 1.758

Threads= 16
Total time
  avg : 17.625
  min : 2.154
  max : 270.270
Converting MeshGL to Manifold
  avg : 6.517
  min : 1.059
  max : 25.309
Manifold boolean
  avg : 10.920
  min : 0.737
  max : 250.945
Converting Manifold to MeshGL
  avg : 0.189
  min : 0.003
  max : 1.606

Not all models are equal in this case, when the sparse indices are relatively small, e.g. for our perfTest where we use high resolution spheres, the speedup is minimal (nTri = 8388608, time = 1.80269 sec).

pca006132 · 2025-03-09T18:24:02Z

src/boolean3.cpp

  // Sum up the winding numbers of all vertices.
-  w03_ = Winding03(inP, p0, s02, false);
+  w03_ = Winding03(inP, inQ, p0q2, expandP_, true);


@elalish I'm thinking if it is possible to somehow integrate this winding number computation into Intersect12, but not sure if that is sound. Will it ever miss anything?

Not sure if you already answered this for yourself, but w03 is calculated for every vertex. It doesn't need to be - I used to only calculate it for the verts of intersected edges and faces - you can flood fill the values to the rest because they're always consistent. I removed that because my flood-filling algorithm was slower than just calculating them all, but I may have just been doing it poorly.

I think calculating them all is probably good for now, it is pretty fast.

pca006132 · 2025-03-09T18:25:22Z

src/boolean3.cpp

+          expandP,
+          forward ? inP.vertNormal_ : inQ.vertNormal_,
+          forward};
+  F11 f11{forward ? inP.vertPos_ : inQ.vertPos_,


I will definitely fix these later, it is just interesting that it works within 30 minutes of trying :)

codecov · 2025-03-09T18:32:00Z

Codecov Report

Attention: Patch coverage is 86.71875% with 17 lines in your changes missing coverage. Please review.

Project coverage is 92.25%. Comparing base (d4439bc) to head (176399c).
Report is 1 commits behind head on master.

Files with missing lines	Patch %	Lines
src/properties.cpp	52.00%	12 Missing ⚠️
src/collider.h	76.92%	3 Missing ⚠️
src/boolean3.cpp	97.05%	2 Missing ⚠️

Additional details and impacted files

@@            Coverage Diff             @@
##           master    #1186      +/-   ##
==========================================
+ Coverage   91.62%   92.25%   +0.63%     
==========================================
  Files          32       31       -1     
  Lines        6067     5902     -165     
==========================================
- Hits         5559     5445     -114     
+ Misses        508      457      -51

☔ View full report in Codecov by Sentry.
📢 Have feedback on the report? Share it here.

🚀 New features to boost your workflow:

❄ Test Analytics: Detect flaky tests, report on failures, and find test suite problems.
📦 JS Bundle Analysis: Save yourself from yourself by tracking and limiting bundle sizes in JS merges.

to run with different benchmark.csv files

src/boolean3.cpp

pca006132 · 2025-03-10T08:54:20Z

I'm thinking about several things now

Should we just remove SparseIndices and use something like a Vec<std::pair<int, int>>? We no longer need the optimizations associated with SparseIndices for now.
Should we still sort the final results? The results are now smaller but non-deterministic. Sorting them may not introduce too much overhead but can potentially improve stability (e.g., avoid the random error I mentioned above, probably).
For changing the other Collider usages, should we do it in this PR or another one?

And probably need some comments about the code organization. I think for simplicity, we should probably just get rid of those forward parameters in high level functions, as I need to do many conditional to deal with that.

src/vec.h

src/boolean3.cpp

elalish · 2025-03-11T05:52:00Z

src/boolean3.cpp

  // Sum up the winding numbers of all vertices.
-  w03_ = Winding03(inP, p0, s02, false);
+  w03_ = Winding03(inP, inQ, p0q2, expandP_, true);


Not sure if you already answered this for yourself, but w03 is calculated for every vertex. It doesn't need to be - I used to only calculate it for the verts of intersected edges and faces - you can flood fill the values to the rest because they're always consistent. I removed that because my flood-filling algorithm was slower than just calculating them all, but I may have just been doing it poorly.

src/sparse.h

src/collider.h

pca006132 · 2025-03-11T11:20:09Z

src/boolean3.cpp

 inline bool Shadows(double p, double q, double dir) {
  return p == q ? dir < 0 : p < q;
 }

 inline std::pair<int, vec2> Shadow01(
    const int p0, const int q1, VecView<const vec3> vertPosP,
    VecView<const vec3> vertPosQ, VecView<const Halfedge> halfedgeQ,
-    const double expandP, VecView<const vec3> normalP, const bool reverse) {
+    const double expandP, VecView<const vec3> normal, const bool reverse) {


changed the naming because it is not really for P, but depends on reverse. When reverse is false, it is for P, but otherwise it is for Q.

Okay, so this one is weird - I managed to confuse myself a bunch of times, which means my naming is terrible, and part of the problem is I added on this expandP thing late. At a global level, only P is expanded (or contracted if false), according to its own normals. The normals of Q are never used for anything. This is weird because this function reverses P and Q sometimes, but the normals are always the same. I think I've used them right, but a double-check would be great. As for naming... I don't know.

pca006132 · 2025-03-11T11:20:26Z

src/boolean3.cpp

  VecView<const vec3> vertPosP;
  VecView<const vec3> vertPosQ;
  VecView<const Halfedge> halfedgeP;
  VecView<const Halfedge> halfedgeQ;
  const double expandP;
-  VecView<const vec3> normalP;
-  const SparseIndices &p1q1;
+  VecView<const vec3> normal;


Similarly here.

pca006132 · 2025-03-11T11:21:51Z

src/boolean3.cpp

-  Vec<int> x12(p1q2.size());
-  Vec<vec3> v12(p1q2.size());
+  // a: 1 (edge), b: 2 (face)
+  const Manifold::Impl &a = forward ? inP : inQ;


Now, instead of swapping inP and inQ parameters, I just define new temporaries a and b, depending on forward. This should hopefully be cleaner now.

pca006132 · 2025-03-11T11:22:46Z

src/manifold.cpp

- *
- * @param other A Manifold to overlap with.
- */
-size_t Manifold::NumOverlaps(const Manifold& other) const {


I just removed this function because it is not used, and to be honest, I don't think the number of overlaps from the collider result is meaningful.

pca006132 · 2025-03-11T11:23:25Z

test/polygons/polygon_corpus.txt

@@ -1694,3 +1694,272 @@ CondensedMatter64 19 2.30642e-11 1
 -0.06842195833766776 9.6799396338048
 -0.06842195833766818 9.679939633804798
 -0.06842195833766825 9.679939633804798
+DISABLED_Sponge4b 291 5.000000000000000909e-13 27


The weird triangulation failure. It seems that it requires really high precision to reproduce the error.

pca006132 · 2025-03-11T12:54:42Z

Sorting the result in boolean3 only adds minor runtime, so we can have determinism there without hurting performance.

@elalish I think this is ready for full review, e.g., naming, organization, etc.

pca006132 · 2025-03-11T12:57:40Z

This change removed 413 LoC (excluding the triangulator test case), completely removed some of the logic related to sparse indices. The logic in boolean3 is also a lot more straightforward now.

pca006132 · 2025-03-11T13:45:42Z

src/boolean3.cpp

 };

 struct Kernel02 {
-  VecView<int> s;
-  VecView<double> z;
  VecView<const vec3> vertPosP;


Maybe we should change the name of these P and Q, because we will swap them. Not sure what is the best name here.

I like your renaming of them to e.g. vertPosA and halfedgeB to handle the swapping.

elalish

Looking awesome, thanks!

elalish · 2025-03-12T08:29:05Z

src/collider.h

@@ -269,6 +241,16 @@ constexpr inline uint32_t SpreadBits3(uint32_t v) {
 /** @ingroup Private */
 class Collider {
 public:
+  template <typename F>
+  struct SimpleRecorder {
+    using LocalT = F;


Why rename something short to something longer? Also, what does LocalT mean?

Oh, it is just some local storage type, I can just rename it to Local.

Why not just leave it as F or T? What is special about the type that makes it local?

It has to be a bit more specific because each thread has its own instance of this value, and the implementation has to deal with this thread local thing. Maybe I should just write a comment about this.

Or put it more simply, this is part of the API interface of recorder for collider, but due to c++ having no interfaces, this is defined implicitly in the collider code...

src/face_op.cpp

elalish · 2025-03-12T08:34:10Z

src/parallel.h

-                        for (Iter i = range.begin(); i != range.end(); i++)
-                          f(*i);
-                      });
+    tbb::this_task_arena::isolate([&]() {


What does this do?

This prevents the current thread from executing work that is outside this scope. Otherwise, thread local variables can be modified by another thread... See https://uxlfoundation.github.io/oneTBB/main/tbb_userguide/work_isolation.html

elalish · 2025-03-12T08:35:32Z

src/polygon.cpp

@@ -125,7 +125,7 @@ void CheckGeometry(const std::vector<ivec3> &triangles,
 }

 void Dump(const PolygonsIdx &polys, double epsilon) {
-  std::cout << std::setprecision(16);
+  std::cout << std::setprecision(19);


I just found a bug at work that was sensitive to the least significant bit of a float getting flipped. Argh!

src/properties.cpp

src/boolean3.cpp

elalish · 2025-03-12T09:01:37Z

src/boolean3.cpp

 };

 struct Kernel02 {
-  VecView<int> s;
-  VecView<double> z;
  VecView<const vec3> vertPosP;


I like your renaming of them to e.g. vertPosA and halfedgeB to handle the swapping.

elalish · 2025-03-12T09:11:40Z

src/boolean3.cpp

 inline bool Shadows(double p, double q, double dir) {
  return p == q ? dir < 0 : p < q;
 }

 inline std::pair<int, vec2> Shadow01(
    const int p0, const int q1, VecView<const vec3> vertPosP,
    VecView<const vec3> vertPosQ, VecView<const Halfedge> halfedgeQ,
-    const double expandP, VecView<const vec3> normalP, const bool reverse) {
+    const double expandP, VecView<const vec3> normal, const bool reverse) {


Okay, so this one is weird - I managed to confuse myself a bunch of times, which means my naming is terrible, and part of the problem is I added on this expandP thing late. At a global level, only P is expanded (or contracted if false), according to its own normals. The normals of Q are never used for anything. This is weird because this function reverses P and Q sometimes, but the normals are always the same. I think I've used them right, but a double-check would be great. As for naming... I don't know.

pca006132 · 2025-03-12T11:16:05Z

@elalish I changed the naming a bit, but for Interpolate and Intersect I will leave the naming to you. Not sure if I should change them to aL, aR, bL, bR or just simply l1, r1, l2, r2.

pca006132 · 2025-03-12T11:21:07Z

and I will leave it for you to merge it, if you think the naming is fine now

elalish · 2025-03-13T06:26:51Z

Hmm, I think I wasn't clear about the naming. Would you mind just reverting the fix naming commit and then we can merge this? Let's talk through the naming separately, because I'm not sure this clarifies it for me.

This reverts commit 79a2526.

pca006132 · 2025-03-13T06:37:21Z

Sure

pca006132 added 3 commits March 10, 2025 02:13

ugly removal

ec22e35

remove more

de34dd9

avoid sort

7c354a2

pca006132 commented Mar 9, 2025

View reviewed changes

pca006132 added 4 commits March 10, 2025 14:49

avoid intermediate sparse indices

4cf4d7e

make analyze_ember_tests accept optional parameter

1dcd9da

to run with different benchmark.csv files

remove p0q2 computation

e4ffad4

fix race?

725daf3

pca006132 commented Mar 10, 2025

View reviewed changes

src/boolean3.cpp Show resolved Hide resolved

properly isolate stuff

1f77a0b

pca006132 mentioned this pull request Mar 11, 2025 10000

Ember tests #1184

Merged

elalish reviewed Mar 11, 2025

View reviewed changes

pca006132 added 4 commits March 11, 2025 15:04

added failing triangulator case

db7d12f

cleanup dead code

7fa4a0f

slight cleanup

436eac0

add comment

f2578d3

pca006132 commented Mar 11, 2025

View reviewed changes

pca006132 added 5 commits March 11, 2025 20:22

avoid writing to SparseIndices

5e914b7

fix

66bff8a

remove sparse indices

7c8c2ec

fix compilation error

607a795

sort results

cf3258c

pca006132 commented Mar 11, 2025

View reviewed changes

elalish approved these changes Mar 12, 2025

View reviewed changes

simplify collider recorder code

afa9631

pca006132 added 2 commits March 12, 2025 19:11

fix naming

79a2526

fix normalP

4790023

pca006132 mentioned this pull request Mar 12, 2025

make boolean deterministic #1187

Merged

add documentation

da28c0c

Revert "fix naming"

176399c

This reverts commit 79a2526.

pca006132 merged commit bc70f58 into master Mar 13, 2025
27 checks passed

pca006132 deleted the avoid-sparseindices branch March 13, 2025 06:59

elalish mentioned this pull request May 14, 2025

v3.1 #1259

Merged

avoid sparse indices #1186

avoid sparse indices #1186

Uh oh!

Conversation

Uh oh!

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Codecov Report

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!