Options for constructing a 3D surface from a point cloud

[Chris]

If I have a set of 3D points, randomly sampled from some arbitrary surface, what are my options (in terms of Julia packages) for reconstructing the surface for plotting? I've done a little research and found the Meshes.jl package, but I can't find any good examples or documentation for it. In case it's not already obvious, I'm completely new to this topic, so any direction would be appreciated.

Thanks,

Chris

[J Luis]

It is not yet registered but you can use GMT, namely its module 'surface' to do a minimum curvature interpolation (but other algorithms are available as well).

[Tamas Papp]

This is not a Julia-specific problem: you need to decide what algorithm
to use, which depends on what you know about your surface.

Eg if it is a function f(x,y), and reasonably smooth and differentiable
over some domain, you can use a family of basis functions to interpolate
-- see ApproxFun.jl. If it is some more general surface, you would need
other algorithms or transformations; there are no general ones (this is
the nature of the problem) and you will need to make some assumptions.

Best,

Tamas

[Chris]

You're right, of course -- I'm sort of learning about the published methods while at the same time searching for implementations. For instance, the reason I mentioned Meshes is that I saw it had an implementation of the marching cubes algorithm, and I was hoping it might be easy enough to quickly try a test case.

[Igor]

Chris , I'm interested in this area too. Please post here if you come up with some solution you would like.

Best regards, Igor

[Steve Kelly]

Do you have a sample dataset? The algorithms for triangulating a signed distance field can be found in Meshing.jl. I implemented Marching Cubes recently and started Marching Squares today, but have yet to tag a release because I need to settle on an API.

I currently am working on solid modeling via implicit functions. More generally I work in digital fabrication (Fab Lab) and would love to have 3D scanning in the Julia workflow. If you can share more about the dataset you have, I'll see if we can make it work with the tools we have available now.

[Tomas Lycken]

There is a marching squares algorithm implemented in [Contour.jl](https://github.com/tlycken/Contour.jl) too; I have put some thoughts on API design in writing in [this issue](https://github.com/tlycken/Contour.jl/issues/29).

Meshing.jl might be a better place for these algorithm anyway (and the name "Contour.jl" is poorly chosen anyway - a plural form would have been better) so the question of moving the existing code into a different repo has already been raised independently). Maybe it's time to combine efforts? :)

I also saw discussions somewhere recently about a "marching triangles" algorithm for calculating contour curves on non-gridded data, which should probably live comfortably in the same space too.

// T

[Chris]

I will work on creating a small sample dataset, but the shape is essentially a "kidney bean" in 3D space. In fact, the actual "point cloud" is (right now) actually samples from a 3D probability density function, i.e. it's a "blob", and I want the 3D bounding surface of that blob. I imagine this makes things more difficult (at least computationally), and so I'm thinking of ways to go from "blob" to the "convex hull" of this point cloud -- even though convex hull isn't exactly what I want, since there is some concavity.

[Chris]

I've attached a sample dataset. It's a set of 500 x,y,z points. I still haven't been able to make much headway on this, so if someone could take the time to show me what's possible, I'd be very appreciative.

[Kristoffer Carlsson]

You could use WriteVTK.jl and render the point cloud in Paraview.

[Chris]

I am hoping for a solution I can use from Julia itself, but this is a good idea, thanks.

[Simon Danisch]

Well just for visualization you should checkout glvisualize... 

[J Luis]

Is something like this that you want?
Maybe Simon can make us a generic example on how to plot the point clouds like this.

[Florian Rhiem]

I rendered your data points as spheres using GR and GR3, to get an idea of what you are dealing with. They seem to show a curve, rather than a surface, though. Is the 'kidney bean' meant to be this elongated or am I interpreting your data in a wrong way?

In general, you might try using a Ball Pivoting algorithm for surface reconstruction. The ball radius parameter allows you to pick how much concavity you allow, with an infinite radius yielding the convex hull.

Here's the script for rendering the spheres and I'll attach a screenshot from it.

using JLD
using GR
using GR.GR3

points = load("testpts.jld")["pts"]
center = mean(points, 1)
scaling_factor = 1 / maximum([maximum(points[:, i])-minimum(points[:, i]) for i in 1:3])

for i in 1:3
 points[:, i] = (points[:, i]-center[i]) * scaling_factor
end

positions = vec(points')
colors = ones(positions)
radii = 0.01*ones(size(points, 1))

GR3.drawspheremesh(size(points, 1), positions, colors, radii)
GR.setviewport(0, 1, 0, 1)
for i in 1:400
 GR.clearws()
 GR3.cameralookat(2*sin(2π*i/200), 0, 2*cos(2π*i/200), 0, 0, 0, 0, 1, 0)
 GR3.drawimage(0, 1, 0, 1, 500, 500, GR3.DRAWABLE_GKS)
 GR.updatews()
end

[Chris]

Thanks. Yes, this is interpreted correctly - the scale will change quite a bit, but this is a typical data set. While one dimension is much more pronounced than the others, the 3D structure is important.

I'll look into the Ball Pivoting algorithm for sure.

[Tom Breloff]

I loaded this in yesterday but assumed the data must have been wrong because it wasn't kidney-shaped.  Anyways this was what I did if you're curious:

using JLD, Plots
data = load("/home/tom/windowsshared/testpts.jld")
x, y, z = map(i->vec(data["pts"][:,i]), (1,2,3))
scatter3d(x,y,z,m=(3,0.05,stroke(0.1)))