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
