'Curve Closest Point' Bottleneck

Hi there,

I’m running a mesh deformation script that deconstruct a mesh into its verticies, and checks the distance to the closest curve. For a high resolution mesh I’m getting using about 300K vertices and about 120 lines. This takes about 10 minutes to compute:

I was wondering whether anyone had any ideas on a way I could speed this up? I’m thinking there surely is a smarter method than me finding the closest point to each curve then sorting through to find the closest curve.

Thanks for any help,

Chris

A thread safe // approach could speed things a bit. Post some indicative test stuff (in R5 format).

1 Like

Well … the R File is not in R5 format (for the type of R/GH usage [very few real-life things I confess] in the practice the R5 is all what is needed).

So post something in R5 format.

Other than that there’s some other “unusual” ways to skin the cut on that matter.

My apologies, I forget to export back to Rhino 5 file format when I saved it. Here it is in Rhino 5, assuming that’s what ‘R5’ format is.

210904_test script-RH5.3dm (4.1 MB)

OK, I’ll test some things but this w/e is a critical F1 w/e (forza Lewis) and Mercedes has issues with the W12 oil pump (if this is really the problem).

Update:

Well … FP3 is over and the news are BAD (but for the pole later on hope dies last):

On less serious matters: prior // things one should conclude to some Method that is faster than a Harley Davidson. A variation of the [pre-existed] attached maybe(?) has some(?) potential (most notably when the result is related with some sort of artistic thingy).

Mesh_ClosestVertexToCrv_Test_V1.3dm (813.4 KB)

Update:

Disaster: Lewis lost pole for a r#&*&#% 37 milliseconds. That’s very bad since Zandvoort is a soap opera cirquit (kinda Monaco and Hungary): you can’t overtake. Anyway … hope dies last.

With a quite low moral I’ve added some stuff more:

Mesh_ClosestVertexToCrv_Test_V1A.gh (409.5 KB)

2 Likes

Hi Peter,

Sorry about your race. Thanks for taking a look at this. I’m not sure if I’m missing something but on my computer your C# script isn’t yet faster than the CurveClosestPoint node?

Hey @christopher6
Off the top of my head a few things that would make this slow:

  1. The component executes the same number of times that there are mesh vertices
  2. The component needs to output the number of curves * the number of vertices points
  3. Even though each check is exclusive, they are run in parallel

Other improvements could be using a spatial data structure (4) (KD-Tree or OcTree) to remove the need for each point to check each curve, but let’s try without first.

To reduce (1), using a C# component with list/list access (rather than the default component which has item/list access) should be much faster.

To reduce (2), we can only output the data needed by performing some sorting in the component. In addition to this, we can cast directly to the type we need as the GH cast mechanisms are a little slow.

And for (3) we can perform it in parallel.

Implementing (1) and (2)

As a C# component

private void RunScript(List<Point3d> points, List<Curve> curves, ref object distance)
  {
    List<GH_Number> results = new List<GH_Number>();

    foreach (Point3d p in points)
    {
      double closestDistance = double.MaxValue;
      foreach (Curve c in curves) {
        double param;
        if (c.ClosestPoint(p, out param)) {
          double dist = c.PointAt(param).DistanceTo(p);
          if (dist < closestDistance) {
            closestDistance = dist;
          }
        }
      }
      results.Add(new GH_Number(closestDistance));
    }

    distance = results;
  }

2 Curves about 10-15% faster

5 Curves about 25-30% faster,

Implementing (3): running in parallel

A slight refactoring to use arrays and indexing the points lets us run in parallel

  private void RunScript(List<Point3d> points, List<Curve> curves, ref object distance)
  {
    GH_Number[] results = new GH_Number[points.Count];

    System.Threading.Tasks.Parallel.For(0, points.Count, (index) => {
      Point3d p = points[index];
      double closestDistance = double.MaxValue;
      foreach (Curve c in curves) {
        double param;
        if (c.ClosestPoint(p, out param)) {
          double dist = c.PointAt(param).DistanceTo(p);
          if (dist < closestDistance) {
            closestDistance = dist;
          }
        }
      }
      results[index] = new GH_Number(closestDistance);
      });

    distance = results;
  }

2 Curves about 2x faster
5 Curves about 5x faster,
120 curves about 40x faster!

Discussion

So computing multiple curves takes a similar amount of time to computing a singular one as we distribute the load across multiple threads. This ends up diminishing slightly when we are computing for more curves than we have processor threads, which is why we see a 1:1 improvement with 5 curves, but a 1:3 improvement with 120 curves.

On my Ryzen 9 3900X (12 core/24 thread) these are results for comparison with the base Curve CP component:

Plus we can then remove the expensive sorting that comes after (another 20s).
About 40x faster (due to (1) (2) and (3) not just the multithreading!

Attached:
210904_test script_cn.gh (11.4 KB)

1 Like

You can knock about 2s off by reducing the time it takes to cast the 82,000 points. Instead, pass them in as System.Object and cast them yourself.

Before:

private void RunScript(List<Point3d> points, List<Curve> curves, ref object distance)

...

Point3d p = points[index];

After:

private void RunScript(List<System.Object> points, List<Curve> curves, ref object distance)

...

Point3d p = (Point3d) points[index];
1 Like

Implementing (4): Spatial data structures

Using the kdtree.dll distributed with chromodoris or tarsier we can improve performance significantly more, as long as a tiny bit of error is acceptable.

In this case, we can perform the same functions that we do in chromodoris to isosurface - divide the geometry into points, build a spatial data structure from those points, then parallel sample that structure.

Combining that with the techniques discussed earlier (1,2,3 and the minor extension above) this sample now runs in 1.6s, or ~400x faster than the original (10x faster than the simple parallel method).

The parameter here, max_error is just controlling the division length of the lines. Even if you set max_error very small (so the results are quite accurate) you’ll still see major performance improvements.

To run this def you’ll need the kdtree.dll dependency from either of the aforementioned plugins, and to reference it with right click > manage assemblies.

You could also build an equivalent without C# just using the tarsier KD-Tree components but it won’t be quite as efficient passing the data back and forth to the Grasshopper document (conversions take a long time when dealing with 10,000+ objects.

Generally speaking, if you prefer speed the dependency C# option is best - but if you’d rather no dependencies (easier to distribute the GH definition, no linking) then the 10s compute time is the sacrifice for the previous parallel method.

210904_test script_kd_cn.gh (13.9 KB)

7 Likes

Wow, Cam. I’m amazed. I just ran it on 1.3 million vertices with 2000 curves and it computed in 5 seconds! This is going to help my students so much. Lower resolution computing will become real-time and higher resolutions that weren’t possible at all are now!

I will link this thread to my students presently. Thanks so much!

C

Lewis did the best possible (compare his times VS Valteri)

Other than that PRIOR any parallel implementation ALWAYS try different ways to skin the cat. See modes 2,3,4.

Mesh_ClosestVertexToCrv_Test_V1B.gh (409.4 KB)

Here is solution based on implementing RTree (spatial search structure, part of RhinoCommon).
First we divide curves into equal segments (by setting segLength) and from dividing-points we construct RTree.
Then for every vertice we search Rtree for candidate curves => we find point within dividing-points that is closest to the vertice and then we find all curves that are within segment-distance from this closest point. By doing so we get only few curves that we have to check against vertice to find closest curve.
This approach (by using RTree) will generally be efficient if we have large number of geometry object in space that we have to search thru. In this case if we have 10 times more curves ( 1200 instead 120) time of execution will not be 10x longer but only aprox 6 times.


Mesh_ClosestVertexToCurves_RG-1.gh (16.9 KB)

3 Likes

That’s a good solution, and removes the dependency.

Extending @RadovanG’s solution very slightly with multithreading and outputting a GH_ object and it is very fast!

Mesh_ClosestVertexToCurves_RG-1_CN.gh (27.3 KB)

4 Likes

Thanks @RadovanG and @camnewnham. It’s very handy not to have to get the students to install dependencies!

How would you extract the closest point in addition to the distance within the same script?

Sub Optimal Solution for the Non-Optimized Answer to also extract points attached.

Also, not sure if it is actually faster than CCP…

But hey, it’s
my first ever C# Script so it would be great to hear how this could be optimized further to extract the Points and parameters.

-H
03152022_crvcp_solution_hf.gh (20.8 KB)

1 Like

Nice work! For me I didn’t need the actually closest points just the distance, I wonder if there are faster ways to find the actual closest point though.

C

Actually, is there anyway to output the curve parameter at the closest point too?