kdtree (2D) for collider #1160

pca006132 · 2025-02-21T16:58:12Z

Simple kdtree for collider. This reduces memory consumption (for performance) as well as speed up triangulation a bit. The implementation is very simple for now. Naming is subject to changes, I don't know what is a good name for this.

On my computer, the 104 polygon tests took 1355ms instead of 1554ms previously.

This is doing a lot of sorting, but from my testing building the index takes a negligible amount of time in our triangulator, so it should be fine. I thought about using quadtree, but it feels like kdtree can be more balanced. I also tried making a separate vector for the split coordinates for less cache access. Not helpful either, probably because our polygons are usually quite small.

Multiway kdtree can improve performance slightly but not by much, and the code is considerably more complex, so I don't think it is a good idea to use that. In case you are interested:

template <typename P, bool sortX = true>
void BuildTwoDTreeImpl(VecView<P> points) {
  if (points.size() <= 8) return;
  std::sort(points.begin(), points.end(), [](const P& a, const P& b) {
    return sortX ? a.pt.x < b.pt.x : a.pt.y < b.pt.y;
  });
  size_t mid = points.size() / 2;
  size_t low = mid / 2;
  size_t high = (points.size() - mid) / 2 + mid;
  const P a = points[low];
  const P b = points[mid];
  const P c = points[high];

  std::move_backward(points.begin() + mid + 1, points.begin() + high,
                     points.begin() + high + 1);
  std::move_backward(points.begin() + low + 1, points.begin() + mid,
                     points.begin() + mid + 2);
  std::move_backward(points.begin(), points.begin() + low,
                     points.begin() + low + 3);
  points[0] = a;
  points[1] = b;
  points[2] = c;

  BuildTwoDTreeImpl<P, !sortX>(points.view(high + 1));
  BuildTwoDTreeImpl<P, !sortX>(points.view(mid + 2, high - mid - 1));
  BuildTwoDTreeImpl<P, !sortX>(points.view(low + 3, mid - low - 1));
  BuildTwoDTreeImpl<P, !sortX>(points.view(3, low));
}

template <typename P>
void BuildTwoDTree(VecView<P> points) {
  ZoneScoped;
  BuildTwoDTreeImpl<P, true>(points);
}

template <typename P, typename F>
void QueryDTreeImpl(VecView<P> points, Rect r, Rect parent, F f, bool sortX) {
  if (points.size() <= 8) {
    for (const auto& p : points)
      if (r.Contains(p.pt)) f(p);
    return;
  }
  // first three points are the split points
  for (const auto& p : points.view(0, 3))
    if (r.Contains(p.pt)) f(p);

  auto coord = [sortX](vec2& v) -> double* { return sortX ? &v.x : &v.y; };
  size_t mid = points.size() / 2;
  size_t low = mid / 2;
  size_t high = (points.size() - mid) / 2 + mid;

  Rect current = parent;
  *coord(current.max) = *coord(points[0].pt);
  if (r.DoesOverlap(current)) {
    QueryDTreeImpl(points.view(3, low), r, current, f, !sortX);
  }
  *coord(current.min) = *coord(points[0].pt);
  *coord(current.max) = *coord(points[1].pt);
  if (r.DoesOverlap(current)) {
    QueryDTreeImpl(points.view(low + 3, mid - low - 1), r, current, f,
                     !sortX);
  }
  *coord(current.min) = *coord(points[1].pt);
  *coord(current.max) = *coord(points[2].pt);
  if (r.DoesOverlap(current)) {
    QueryDTreeImpl(points.view(mid + 2, high - mid - 1), r, current, f,
                     !sortX);
  }
  *coord(current.min) = *coord(points[2].pt);
  *coord(current.max) = *coord(parent.max);
  if (r.DoesOverlap(current)) {
    QueryDTreeImpl(points.view(high + 1), r, current, f, !sortX);
  }
}

template <typename P, typename F>
void QueryDTree(VecView<P> points, Rect r, F f) {
  ZoneScoped;
  QueryDTreeImpl(points, r,
                   Rect(vec2(-std::numeric_limits<double>::infinity()),
                        vec2(std::numeric_limits<double>::infinity())),
                   f, true);
}

pca006132 · 2025-02-21T17:34:22Z

we should probably mark nodes as removed while ear clipping.

src/polygon.cpp

src/twodtree.h

elalish · 2025-02-22T01:44:54Z

src/twodtree.h

+
+namespace manifold {
+
+template <typename P, bool sortX = true>


I'll take a wild guess that the next version of this will be 3D, splitting X, Y, Z, X, Y, Z. Maybe bool sortX should be int sortAxis?

elalish · 2025-02-22T01:47:43Z

src/twodtree.h

+}
+
+template <typename P, typename F>
+void QueryTwoDTree(VecView<P> points, Rect r, F f) {


So, if this is faster than the collider for 2D, do you think a version of it will also be faster for 3D? It would be nice to have something universal. Or failing that, to at least have them use the same kind of API so it's easier to compare them? Is that reasonable?

I need to think a bit about this.

pca006132 · 2025-02-22T15:23:19Z

For some reason, I can't reproduce the CI failure locally. The exact polygon did not produce invalid triangulation here. Not sure if this is something caused by the unstable sort, so I am switching over to the stable sort we have and that should make it deterministic.

pca006132 · 2025-02-22T15:40:39Z

OK, it seems that we do need to expand the bounding box by epsilon.

codecov · 2025-02-22T15:50:19Z

Codecov Report

Attention: Patch coverage is 96.29630% with 2 lines in your changes missing coverage. Please review.

Project coverage is 91.70%. Comparing base (f178cd1) to head (fc20d1f).
Report is 1 commits behind head on master.

Files with missing lines	Patch %	Lines
src/tree2d.cpp	83.33%	2 Missing ⚠️

Additional details and impacted files

@@            Coverage Diff             @@
##           master    #1160      +/-   ##
==========================================
+ Coverage   91.69%   91.70%   +0.01%     
==========================================
  Files          30       32       +2     
  Lines        5959     5980      +21     
==========================================
+ Hits         5464     5484      +20     
- Misses        495      496       +1

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

elalish · 2025-02-22T20:37:48Z

src/polygon.cpp

+                         vec2(center.x + radius, center.y + radius));
+      earBox.Union(pos);
+      earBox.min -= epsilon;
+      earBox.max += epsilon;


Good call - surprised this wasn't a problem before.

We do need it previously, just that I forgot to add it back. Previously, we enlarge the bbox of each vertex, but now we enlarge the bbox of the query.

elalish · 2025-02-22T20:41:23Z

src/polygon.cpp

-              }
-              return cost;
-            }
-            return std::numeric_limits<double>::lowest();


Is this case handled inside the query function now?

I think for lowest, it just means it will not change the cost (because we take the max).

pca006132 added 2 commits February 21, 2025 17:16

kdtree

6db130e

remove verify code

8d046ba

elalish reviewed Feb 22, 2025

View reviewed changes

pca006132 added 2 commits February 22, 2025 23:19

address comments

1b511bd

try to add the CI failing case

b66e1d6

pca006132 added 4 commits February 22, 2025 23:29

fix build

9cd9933

set precision

61523f1

format

d621cb5

fix

fc20d1f

elalish approved these changes Feb 22, 2025

View reviewed changes

pca006132 merged commit 06b10e7 into master Feb 23, 2025
27 checks passed

pca006132 deleted the kdtree branch February 23, 2025 06:59

elalish mentioned this pull request May 14, 2025

v3.1 #1259

Merged

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Uh oh!

kdtree (2D) for collider #1160

kdtree (2D) for collider #1160

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!


		namespace manifold {

		template <typename P, bool sortX = true>

kdtree (2D) for collider #1160

kdtree (2D) for collider #1160

Uh oh!

Conversation

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!

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Codecov Report

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!