Get all neighboring points (including not connected by edge). Fast.

intenditore

Hi. My goal is simple - I need to gather info from all the points which are near a given one. I can use

c4d.utils.Neighbor.GetPointOneRingPoints()

But it's downside (for me) is it only considers the points connected to specified point by edge. I need all of which belong to the polygons this point belongs to.

So that could be done by Utils.Neighbour, but... First you have to get neighbour polys. Than their points. Than exclude the first given point from the list and toss them all so the list doesn't contain duplicates. And only than you get the list of the points.

On dense geometry this would increase the cyclecount and memory consumption much! I don't really like that.

Are there any handier way to achieve the same?

ferdinand

Hi,

first of all, GetPointOneRingPoints is currently bugged, see here for details and to my knowledge this has not been fixed yet. Aside from that, no, you will have to get the polys and then the points, but I do not really get your speed concerns. Edge index / neighbour data structures in itself are quite efficient, because they are basically just a glorified hash map (at least that how it is usually done, I don't know what Maxon is doing). The point access from CPolygon is also efficient, because they are storing just indices. So far everything should be of constant complexity. The only part that would be of non-ideal complexity would be creating a set from these points you want to retrieve (i.e. remove duplicates and also remove your seed point), because Cinema's vectors are not hashable, so you cannot use Python's set type for example.

To circumvent this, you could cast these vectors to tuples, which would allow you to build sets from them. But I do not really see the point in doing that. Removing all unwanted points form your vector list at the end could be done in in linear time if you hash these vectors, so that should not be that much of a problem either. If you don't, it will be exponential, but honestly, unless you are dealing with some crazy ZBrush or scan geometry, this should not be a problem either.

Cheers,
zipit

nophoto

Hi,

I would use a BaseSelect to 'collect' all points of the neighboring polys. Deselect the first point and get all points without duplicates using BaseSelect.GetAll().

By
Peter

intenditore

@zipit I don't get why you're still not working in Maxon. That seems illogical!
Many thanks for a such detailed answer once again!
The problem is the solution is intended to chew a lot of polys and there may be some "Zbrush"-like model. So as I already understand, I will have to port it to CPP anyway.

@nophoto said in Get all neighboring points (including not connected by edge). Fast.:

I would use a BaseSelect to 'collect' all points

Quite a point! Great suggestion I think, I will try that out

Manuel

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