3

I have a bunch of 3D coordinates (I believe this is called a Point cloud, but I'm no expert in the field, so I could be wrong) that all together define a roughly spherical shape. On top of that, I have a bunch of coordinates that may, or may not be within this point cloud. I need a way to determine if these coordinates are or are not within the point cloud.

What I've tried to do so far is use the point cloud to define a polygon mesh, and from there, determine if my other points are bounded within the mesh. Unfortunately, when I create the mesh (I was testing it out with the gui for meshlab, with plans to switch over to command line) it created a mesh that had holes in it, probably because some areas of my point cloud were more sparse that others.

Does anyone have any thoughts about how to do this? Perhaps an easier way than what I'm trying, or perhaps some programs and modules to try out?

Thanks

Nate
  • 31
  • 2

1 Answers1

2

I need a way to determine if these coordinates are or are not within the point cloud.

IMHO this depends on what you mean by within.
That is to say, you need a (formal) definition of this relationship: a point is within a point cloud.

For example, you might define within using convex combination:

Given 3D point q and point cloud Q = {q1, q2, ..., qn}, q is within Q, if and only if q is a convex combination of {q1, q2, ..., qn}.

If this is the case, given point q and point cloud Q, you can first find the convex hull of the points in Q, then decide if q is inside the convex hull or not. As for this task, you can refer to this SO question.

Or you can define within with respect to the mesh formed by the point clouds, like the way you did. Then the definition might be like:

Given 3D point q and point cloud Q = {q1, q2, ..., qn}, a watertight mesh S can be generated from Q. We say q is within Q, if and only if q is inside S.

This definition is rather sloppy. There can be all kinds of watertight meshes generated from the point cloud. For example, the surface reconstructed using Poisson surface reconstruction, or using some methods that use Delaunay triangulation.
However, for your application, any one of the watertight meshes from Q might just be OK.

And if this is the case, your problem would be to extract a watertight surface mesh from the given point cloud. There are many methods that can extract a triangle mesh from point cloud. In your case, you need those that can generate a watertight one.

MeshLab provide many ways to reconstruct surface from point cloud, the one you used seems do not guarantee watertight-ness. You might want to switch to Poisson surface reconstruction, which is also contained in MeshLab, and it guarantees watertight-ness.

FYI, Poisson surface reconstruction is open sourced and can be used in CLI.

abenci
  • 8,422
  • 19
  • 69
  • 134
Jing Zhao
  • 2,420
  • 18
  • 21