Selecting random points of a PolyData (Stratified sampling)

Hi. I would like to know how to get a sample of points of my polydata that are evenly distributed on the mesh surface. My input is a longBonePolyData.

Here is my code till now:

desiredNumberOfPoints = 1000
ratio = int(longBonePolyData.GetNumberOfPoints()/desiredNumberOfPoints)

sampleSource = vtk.vtkSphereSource()
sampleSource.SetRadius(1)

maskPointsFilter = vtk.vtkMaskPoints()
maskPointsFilter.SetInputData(longBonePolyData)

#This works but the sampling could be biased spatially I think
maskPointsFilter.SetOnRatio(ratio)
maskPointsFilter.RandomModeOn()

#This doesn't work the output is clustered spatially not evenly distributed.
#maskPointsFilter.SetRandomModeType(2)#SPATIALLY_STRATIFIED
#maskPointsFilter.SetMaximumNumberOfPoints(desiredNumberOfPoints)

maskPointsFilter.Update()


sampleGlyph3D = vtk.vtkGlyph3D()
sampleGlyph3D.SetInputConnection(maskPointsFilter.GetOutputPort())
sampleGlyph3D.SetSourceConnection(sampleSource.GetOutputPort())
sampleGlyph3D.ScalingOff()
sampleGlyph3D.Update()

#Visualize the glyph

You might also try vtkPolyDataPointSampler with random point generation

You might also try vtkPolyDataPointSampler with random point generation

I tried but I coudn’t get it to give me less samplePoints than the original number of points of the inputPolyData. Am I using it wrong?

Here is another approach I tried that the output fails (is not a random distribution of points, thresholding is not working as expected):

polydata0 = vtk.vtkPolyData()
polydata0.ShallowCopy(boneModel0.GetPolyData())
sampleRatio0 = 0.1
randomSampleArray = np.random.default_rng().uniform(0,1,polydata0.GetNumberOfPoints())

selectionArray = vtk.vtkIntArray()
selectionArray.SetName("Selection")
selectionArray.SetNumberOfValues(polydata0.GetNumberOfPoints())
selectionArray.Fill(0)

for i in range(polydata0.GetNumberOfPoints()):
    if randomSampleArray[i] < sampleRatio0:
        selectionArray.SetTuple1(i,1)

pointScalars = polydata0.GetPointData()
pointScalars.AddArray(selectionArray)

thresholdFilter = vtk.vtkThreshold()
thresholdFilter.SetInputData(polydata0)
thresholdFilter.ThresholdBetween(0.9, 1.1)
thresholdFilter.SetInputArrayToProcess(0, 0, 0,
    vtk.vtkDataObject.FIELD_ASSOCIATION_POINTS,
    "Selection")
thresholdFilter.Update()
geometryFilter = vtk.vtkGeometryFilter()
geometryFilter.SetInputData(thresholdFilter.GetOutput())
geometryFilter.Update()

polydata0.ShallowCopy(geometryFilter.GetOutput())

But for this way the only improvement to the script I posted firstly is that the ratio can be any real number between 1 and 0.

I might have to stay with the first script because is the only one that works till now but my algorithm that uses those points as input would benefit if the points where evenly distributed over the mesh

I tried but I coudn’t get it to give me less samplePoints than the original number of points of the inputPolyData. Am I using it wrong?

I assume that you are experimenting with the Distance parameter

I assume that you are experimenting with the Distance parameter

yes. Is it possible to get less points that inputPolyData number of points?

I have no idea, that’s what source code is for :wink: It could be the filter needs a refresh, a MR/patch would be welcome.

For that I often use the vtkCleanPolyData filter with SetTolerance(value) of the order of 0.1. The subsampled points will be evenly spaced.

Thanks but it takes a too long on 200 thousand points polydata.

The reason I opened this thread was because I was developing an algorithm to register two similar bones without user inputs. Here it is if you want to check out: SVD ModelToModel Registration Idea - #4 - Development - 3D Slicer Community

It works, although the algorithm would make a little bit better registrations if the points of the meshes were evenly sampled from the meshes surface instead of randomly sampled like right now

on my mac it takes 1.45sec to go from 200k to 200 and 0.3sec to go from 200k to 1k:

from vedo import *
import numpy as np
import time

pts = Points(np.random.rand(200000, 3), r=8)
t0 = time.time()
pts.clean(0.05)
t1 = time.time()
print(pts.NPoints(), t1-t0)
show(pts, axes=1)

maybe you can random-select a subset and then “clean” that one, not sure if that helps…

I’ll try that

If you keep using the vtkMaskPoint, I think you may be interested in the UNIFORM_SPATIAL_SURFACE that you can enable with a SetRandomModeType(4). It should do what you want.

Here is the corresponding doc extracted from ParaView for all random modes for this filter:

Randomized Id Strides picks points with random id increments starting at
Offset (the output probably isn't a statistically random sample). Random
Sampling generates a statistically random sample of the input, ignoring Offset
(fast - O(sample size)). Spatially Stratified Random Sampling is a variant of
random sampling that splits the points into equal sized spatial strata before
randomly sampling (slow - O(N log N)). The Uniform Spatial Distribution (Bound
based) samples points using random poisitions inside the bounds of the data
set and a point locator. The Uniform Spatial Distribution (Surface Sampling)
samples points randomly via an inverse transform on surface area of each cell
(3D cells are ignored). The Uniform Spatial Distribution (Volume Sampling)
samples points randomly sampled via an inverse transform on volume area of
each cell (2D cells are ignored). 

Hi Charles. Thank for the answer but it doesn’t work. The points are clustered over the metaphysis and sparse around the diaphysis of the bone using the script I posted firstly with this options:

maskPointsFilter.SetRandomModeType(4)#UNIFORM_SPATIAL_SURFACE 
maskPointsFilter.SetMaximumNumberOfPoints(desiredNumberOfPoints)

Is your mesh a clean surface with only convex polygons ?

I think so, yes. Only triangles I think.

So indeed, this is not the expected output. Which version of VTK are you using ?

Can you share the dataset ? (or any dataset on which you observe the problem)

Here is the bone:

I think Slicer uses VTK 8 version, but I’m not sure

This version of VTK does not contains the UNIFORM_* mode yet unfortunately :confused:

Here is a result with ParaView using this mode:

Maybe you can use ParaView 5.9.1 or 5.10.0-RC1 or VTK 9 to extract these points ?

That result looks good. Although I think I’ll have to wait to Slicer to update its VTK version and try it. The idea is to launch the registration script inside Slicer or in the Slicer’s python interactor.

As the image above) shows (and I experienced this outside of VTK, too), surface-weighted random sampling produces highly non-uniform point distribution on surface meshes: points are often clumped together in small groups and there are huge empty areas between these clumps.

Can someone explain this? Is it just because the number of samples is relatively small (and the distribution would eventually become uniform when you reach hundreds of thousands of samples)?

Is there a solution in VTK that would provide more uniform distribution for few hundred or few thousand points? Is there a point sampler or a post-processing filter that would try to maximize distance between sample points on the surface?

Current Slicer version uses VTK9. The last stable release was still created with VTK8.

You can use vtkPoissonDiskSampler if you want evenly spaced points in your output. This filter guarantees that the output cannot have 2 points closer than Radius.

BTW. I just discovered a bug that can make the filter crash… I’ll push a fix.

1 Like