hi,

from time to time i'm saying thanks to @zipit , but for sure he's contributing a lot to the community.
there's not too much to say more that what have been said.

Brut force is the only option without using external python librairies. You can always use an external library if you want to use a kd-tree structure to be faster.

Using cpp would be a better solution if you really want to do it fast. We have in our API a kd-tree as show in this kd-stree manual.

You can see on github a full example on how to use it

And here are some code of me playing with different way of sampling a kd-tree using parallel method and also using voxelization to get the closest polygon.

//---------------------------------------------------------------------------------------- //---------------------------------------------------------------------------------------- /// GetClosestPolygon using voxelization //---------------------------------------------------------------------------------------- static maxon::Result<void> GETCLOSEST_POLY(BaseDocument* doc) { iferr_scope; if (doc == nullptr) return maxon::IllegalArgumentError(MAXON_SOURCE_LOCATION); // ------- Create a mesh with one poly const maxon::Int32 polyCnt{ 500 }; PolygonObject *mesh = PolygonObject::Alloc(polyCnt * 4, polyCnt ); if (mesh == nullptr) return maxon::OutOfMemoryError(MAXON_SOURCE_LOCATION); maxon::LinearCongruentialRandom<maxon::Float32> random; CPolygon *polyAdrW = mesh->GetPolygonW(); Vector* padrW = mesh->GetPointW(); const Float polySize{ 10 }; for (maxon::Int i = 0; i < polyCnt; i++) { CPolygon poly; maxon::Vector pointA(i * polySize, 0, 0); maxon::Vector pointB(i * polySize, 0, polySize); maxon::Vector pointC(i * polySize + polySize, 0, polySize); maxon::Vector pointD(i * polySize + polySize, 0, 0); const maxon::Int pointIndice = i * 4; padrW[pointIndice] = pointA; padrW[pointIndice + 1] = pointB; padrW[pointIndice + 2] = pointC; padrW[pointIndice + 3] = pointD; poly.a = pointIndice; poly.b = pointIndice + 1; poly.c = pointIndice + 2; poly.d = pointIndice + 3; polyAdrW[i] = poly; } doc->InsertObject(mesh, nullptr, nullptr); maxon::DistanceQueryRef distanceQueryRef = maxon::DistanceCalculator().Create() iferr_return; distanceQueryRef.Init(mesh, true) iferr_return; maxon::PrimitiveInformation result; const maxon::Int samplePointCnt = polyCnt; //---------------------------------------------------------------------------------------- /// sample using standard loop maxon::TimeValue start = maxon::TimeValue(maxon::TimeValue::NOW); for (maxon::Int i = 0; i < samplePointCnt; ++i) { const maxon::Vector pos{ i * polySize + polySize * 0.5, 0, 0 }; distanceQueryRef.GetClosestMeshPrimitive(pos, result); if (result.type == maxon::PRIMITIVETYPE::POLYGON) ApplicationOutput("pos @, polyIndex @ ", pos, result.GetRealPolyIndex()); else ApplicationOutput("not a polygon"); } ApplicationOutput("time to sample the points @ with MP", start.Stop()); //---------------------------------------------------------------------------------------- /// sample using parallelFor start = maxon::TimeValue(maxon::TimeValue::NOW); maxon::BaseArray< maxon::PrimitiveInformation> resultArray; resultArray.Resize(samplePointCnt) iferr_return; maxon::ParallelFor::Dynamic(0, samplePointCnt, [&resultArray, &polySize, &distanceQueryRef](maxon::Int i) { maxon::PrimitiveInformation result; const maxon::Vector pos{ i * polySize + polySize * 0.5, 0, 0 }; distanceQueryRef.GetClosestMeshPrimitive(pos, result); if (result.type == maxon::PRIMITIVETYPE::POLYGON) ApplicationOutput("pos @, polyIndex @ ", pos, result.GetRealPolyIndex()); else ApplicationOutput("not a polygon"); resultArray[i] = result; } ); ApplicationOutput("time to sample the points @ with MP", start.Stop()); for (auto& value : resultArray) { if (value.type == maxon::PRIMITIVETYPE::POLYGON) ApplicationOutput("polyIndex @ ", value.GetRealPolyIndex()); else ApplicationOutput("not a polygon"); } return maxon::OK; } //---------------------------------------------------------------------------------------- //---------------------------------------------------------------------------------------- /// Sample a KD tree with multi thread //---------------------------------------------------------------------------------------- class SampleTreeJob : public maxon::JobInterfaceTemplate<SampleTreeJob, maxon::Int> { public: SampleTreeJob() { }; MAXON_IMPLICIT SampleTreeJob(maxon::KDTree* kdtree, const maxon::Vector& samplePoint) { _kdtree = kdtree; _samplePoint = samplePoint; } // function operator with the actual workload maxon::Result<void> operator ()() { maxon::Int nearestIndex = _kdtree->FindNearest(maxon::JobRef::GetCurrentWorkerThreadIndex(), _samplePoint, nullptr); // store result return SetResult(std::move(nearestIndex)); } private: maxon::KDTree* _kdtree; maxon::Vector _samplePoint; }; static maxon::Result <maxon::BaseArray<maxon::Vector>> CreateArrayOfPoints() { iferr_scope; const maxon::Int pointCnt = 1000000; maxon::BaseArray<maxon::Vector> points; points.EnsureCapacity(pointCnt) iferr_return; maxon::LinearCongruentialRandom<maxon::Float32> random; for (maxon::Int i = 0; i < pointCnt; ++i) { maxon::Vector pos(maxon::DONT_INITIALIZE); pos.x = random.Get01() * 100000.0; pos.y = random.Get01() * 100000.0; pos.z = random.Get01() * 100000.0; points.Append(pos) iferr_return; } return points; } static maxon::Result<maxon::BaseArray<maxon::Vector>> CreateSamplePoints() { iferr_scope; // sample points const maxon::Int samplePointCnt = 10000; maxon::BaseArray<maxon::Vector> samplePoints; samplePoints.EnsureCapacity(samplePointCnt) iferr_return; for (maxon::Int i = 0; i < samplePointCnt; ++i) { const maxon::Vector pos{ i* 10.0 }; samplePoints.Append(pos) iferr_return; } return samplePoints; } static maxon::Result<void> KDTREE_MP(BaseDocument* doc) { iferr_scope; maxon::BaseArray<maxon::Vector> points = CreateArrayOfPoints() iferr_return; maxon::BaseArray<maxon::Vector> samplePoints = CreateSamplePoints() iferr_return; const maxon::Int samplePointCnt = samplePoints.GetCount(); const maxon::Int pointCnt = points.GetCount(); maxon::KDTree tree; tree.Init(maxon::JobRef::GetCurrentThreadCount()) iferr_return; // insert points for (maxon::Int i = 0; i < pointCnt; ++i) { tree.Insert(points[i], i) iferr_return; } // balance tree tree.Balance(); //---------------------------------------------------------------------------------------- /// sample using classic loop maxon::TimeValue start{ maxon::TimeValue::NOW }; for (const maxon::Vector& samplePoint : samplePoints) { // find nearest point const maxon::Int nearestIndex = tree.FindNearest(0, samplePoint, nullptr); } ApplicationOutput("time to sample the points @ ", start.Stop()); //---------------------------------------------------------------------------------------- /// sample using parallelFor start = maxon::TimeValue(maxon::TimeValue::NOW); maxon::ParallelFor::Dynamic(0, samplePointCnt, [&samplePoints, &tree](maxon::Int i) { const maxon::Vector samplePoint = samplePoints[i]; const maxon::Int nearestIndex = tree.FindNearest(maxon::JobRef::GetCurrentWorkerThreadIndex(), samplePoint, nullptr); } ); ApplicationOutput("time to sample the points @ with MP", start.Stop()); //---------------------------------------------------------------------------------------- /// Sample using job // create group start = maxon::TimeValue(maxon::TimeValue::NOW); maxon::JobGroupRef group = maxon::JobGroupRef::Create() iferr_return; for (auto i = 0 ; i < samplePointCnt; i++) { // create and add job const maxon::Vector samplePoint = samplePoints[i]; auto job = SampleTreeJob::Create(&tree, samplePoint) iferr_return; group.Add(job) iferr_return; } // enqueue jobs and wait group.Enqueue(); group.Wait(); ApplicationOutput("time to sample the points @ with jobs", start.Stop()); //---------------------------------------------------------------------------------------- /// sample using classic loop again start = maxon::TimeValue(maxon::TimeValue::NOW); for (const maxon::Vector& samplePoint : samplePoints) { // find nearest point const maxon::Int nearestIndex = tree.FindNearest(0, samplePoint, nullptr); } ApplicationOutput("time to sample the points @ second time to see if caches are envolved", start.Stop()); return maxon::OK; }

Cheers,
Manuel

FileSelect for multiple files