Quantcast

[SciPy-User] Triangulate point cloud

classic Classic list List threaded Threaded
10 messages Options
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

[SciPy-User] Triangulate point cloud

Vasco Gervasi
Hi all,
I am looking for a way to traingulate a point cloud, in other words nodes to triangular.
I tried scipy.spatial.Delaunay and ConvexHull, but for some reason it tends to connect nodes that are very far away.
At this address you can find a good example of what I am looking for: https://paste.ee/p/RBank.
As you can see I gave some points around the lateral face of a cylinder, the problems are
- it connects nodes that are on the opposite side of the cylinder
- if alseo connect nodes that are on the two front face of the cylinder
This is just a simple example, I am trying to triangulate a more complex point cloud.
So in my opinion the perfect solution would be to define the max distance between nodes that can be connected. 

Best regards

_______________________________________________
SciPy-User mailing list
[hidden email]
https://mail.scipy.org/mailman/listinfo/scipy-user
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Triangulate point cloud

Gary Ruben
Hi Vasco,

Another possible option is vtk's Delaunay3D method. I used this a long time ago when it was one of the only options I could find that could reliably triangulate points on the surface of a sphere. It has a couple of parameters you can fiddle with to affect its behaviour:
http://docs.enthought.com/mayavi/mayavi/auto/example_delaunay_graph.html

Gary

On 12 February 2016 at 06:23, Vasco Gervasi <[hidden email]> wrote:
Hi all,
I am looking for a way to traingulate a point cloud, in other words nodes to triangular.
I tried scipy.spatial.Delaunay and ConvexHull, but for some reason it tends to connect nodes that are very far away.
At this address you can find a good example of what I am looking for: https://paste.ee/p/RBank.
As you can see I gave some points around the lateral face of a cylinder, the problems are
- it connects nodes that are on the opposite side of the cylinder
- if alseo connect nodes that are on the two front face of the cylinder
This is just a simple example, I am trying to triangulate a more complex point cloud.
So in my opinion the perfect solution would be to define the max distance between nodes that can be connected. 

Best regards

_______________________________________________
SciPy-User mailing list
[hidden email]
https://mail.scipy.org/mailman/listinfo/scipy-user



_______________________________________________
SciPy-User mailing list
[hidden email]
https://mail.scipy.org/mailman/listinfo/scipy-user
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Triangulate point cloud

Athanasios Anastasiou-4
Hello

In addition to the already suggested ways of doing this:

1) If you don't have a prohibitively large dataset (a few hundred thousand points), you can evaluate their inter-point distance and then use that one to establish a threshold. If you do a histogram on point distance you will see clearly the bunches of points that are closely to each other and the bunches, or clusters, of points that are further apart. You can then determine the distance threshold that will exclude surfaces across the cylinder.

2) Another way I have found to do this is to use this plugin: http://blenderartists.org/forum/showthread.php?241950-A-Script-to-Skin-a-Point-Cloud-(for-Blender-2-6x-or-Later) for blender. It is really doing a good job and once your point cloud in in Blender you can use other tools to improve your mesh. In my case, I wrote a very simple script in Python to package my point cloud into a VRML pointset (http://www.c3.hu/cryptogram/vrmltut/part5.html) which was the easiest way in to import it to Blender.

Hope this helps.

All the best
AA



On Thu, Feb 11, 2016 at 11:35 PM, gary ruben <[hidden email]> wrote:
Hi Vasco,

Another possible option is vtk's Delaunay3D method. I used this a long time ago when it was one of the only options I could find that could reliably triangulate points on the surface of a sphere. It has a couple of parameters you can fiddle with to affect its behaviour:
http://docs.enthought.com/mayavi/mayavi/auto/example_delaunay_graph.html

Gary

On 12 February 2016 at 06:23, Vasco Gervasi <[hidden email]> wrote:
Hi all,
I am looking for a way to traingulate a point cloud, in other words nodes to triangular.
I tried scipy.spatial.Delaunay and ConvexHull, but for some reason it tends to connect nodes that are very far away.
At this address you can find a good example of what I am looking for: https://paste.ee/p/RBank.
As you can see I gave some points around the lateral face of a cylinder, the problems are
- it connects nodes that are on the opposite side of the cylinder
- if alseo connect nodes that are on the two front face of the cylinder
This is just a simple example, I am trying to triangulate a more complex point cloud.
So in my opinion the perfect solution would be to define the max distance between nodes that can be connected. 

Best regards

_______________________________________________
SciPy-User mailing list
[hidden email]
https://mail.scipy.org/mailman/listinfo/scipy-user



_______________________________________________
SciPy-User mailing list
[hidden email]
https://mail.scipy.org/mailman/listinfo/scipy-user



_______________________________________________
SciPy-User mailing list
[hidden email]
https://mail.scipy.org/mailman/listinfo/scipy-user
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Triangulate point cloud

Vasco Gervasi

Thanks. I will try mayavi and blender.
Regarding the suggestione number 1 of AA do you have an example.


_______________________________________________
SciPy-User mailing list
[hidden email]
https://mail.scipy.org/mailman/listinfo/scipy-user
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Triangulate point cloud

Athanasios Anastasiou-4
Off the top of my head:

from scipy.spatial import distance
from scipy.stats import histogram
from scipy import nan
#p is your data structures that holds all of your data points, it can be n-dimensional of course.
#Here, it is a list of tuples, suggesting a simple 2D problem.
p=[(2,2),(5,5),(1,7),(2,3)]
#Get the unique distances
#If you have a huge amount of points, this is the point where the program might take a little bit of time until it comes back with the results.
d = distance.pdist(p)
#Get the distance matrix, this is always a square kxk matrix, where k is the index of a point in p
#If you have a huge amount of points, this is the bit where the program a) takes a long time to finish, b) crashes because of memory issues. For very large problems, you can upload your points to a database server and run a query for it to calculate your distance matrix. So, you can hire a powerful EC2 (for example) instance and run your query there or run the query over a distributed configuration. Both options aiming to improve speed and capacity.
Q = distance.squareform(d)
#The d matrix are the unique values of the upper (or lower) diagonal part of Q. Q is much easier to work with (in terms of referencing), if you want the distance between any two point m,n you just Q[m,n].
#Here is the Euclidean Q for the above p.
#array([[ 0.        ,  4.24264069,  5.09901951,  1.        ],
#       [ 4.24264069,  0.        ,  4.47213595,  3.60555128],
#       [ 5.09901951,  4.47213595,  0.        ,  4.12310563],
#       [ 1.        ,  3.60555128,  4.12310563,  0.        ]])

#Get the histogram of that
H = histogram(d); #This could also be done on Q, by reshaping it to a 1 x (M*N) vector but if you have a huge number of points it is not advisable. You can see how quickly this eats up memory.
#This can also be done with matplotlib.pyplot.hist(d) which will also draw the histogram for you besides returning it.
If you want to free up some memory to fit even more data to your problem, you can round everything to a few decimal places and use integers. So, for example, int(round(5.678928527817364 * 10000))==56789, which is a nice little unsigned integer of 2 bytes instead of a double of 8 bytes. Of course this assumes that 4 decimals is accurate enough. To get back to your data range, just divide by 10000 and assign to (float or double).

Hope this helps.

All the best
AA




On Fri, Feb 12, 2016 at 1:24 PM, Vasco Gervasi <[hidden email]> wrote:

Thanks. I will try mayavi and blender.
Regarding the suggestione number 1 of AA do you have an example.


_______________________________________________
SciPy-User mailing list
[hidden email]
https://mail.scipy.org/mailman/listinfo/scipy-user



_______________________________________________
SciPy-User mailing list
[hidden email]
https://mail.scipy.org/mailman/listinfo/scipy-user
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Triangulate point cloud

Vasco Gervasi

Sorry but i didn't understand how to use the histogram [H] to find the connectivity.

Thank you very much.


_______________________________________________
SciPy-User mailing list
[hidden email]
https://mail.scipy.org/mailman/listinfo/scipy-user
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Triangulate point cloud

Athanasios Anastasiou-4
Ah, the above code will not help you connect the right points, this is still a triangulation problem. The above code will help you determine the distance threshold you need to use (in other tools or algorithms, including the surface plugin of blender) to avoid artifacts such as those that you are describing in your original question (i.e. surfaces across a cylinder). Otherwise, you would have to estimate this with trial and error.

All the best
AA


On Fri, Feb 12, 2016 at 3:00 PM, Vasco Gervasi <[hidden email]> wrote:

Sorry but i didn't understand how to use the histogram [H] to find the connectivity.

Thank you very much.


_______________________________________________
SciPy-User mailing list
[hidden email]
https://mail.scipy.org/mailman/listinfo/scipy-user



_______________________________________________
SciPy-User mailing list
[hidden email]
https://mail.scipy.org/mailman/listinfo/scipy-user
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Triangulate point cloud

François Boulogne-3
You also have this code : https://github.com/pearu/pyvtk
The doc has weaknesses, but I could make it work for my problem.

Best,

--
François Boulogne.
http://www.sciunto.org
GPG: 32D5F22F

_______________________________________________
SciPy-User mailing list
[hidden email]
https://mail.scipy.org/mailman/listinfo/scipy-user
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Triangulate point cloud

Vasco Gervasi
François could you share an example for pyvtk, because examples in https://github.com/pearu/pyvtk/tree/master/examples do not work.

Thanks

_______________________________________________
SciPy-User mailing list
[hidden email]
https://mail.scipy.org/mailman/listinfo/scipy-user
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Triangulate point cloud

Vasco Gervasi
Seems that I found a good solution [I will try later with real data].
Using pyevtk I am able to create a .vtu file:
import numpy
from pyevtk.hl import pointsToVTK
n = 10**5
x = numpy.random.randn(n)
y = numpy.random.randn(n)
z = numpy.random.randn(n)
d = numpy.random.randn(n)
pointsToVTK("./points", x, y, z, data = {"C" : d})
Then open the points.vtu file in paraview and run Filters -> Alphabetical -> Delauny3D.

Thanks

_______________________________________________
SciPy-User mailing list
[hidden email]
https://mail.scipy.org/mailman/listinfo/scipy-user
Loading...