LabVIEW

cancel
Showing results for 
Search instead for 
Did you mean: 

Delaunay triangulation and mesh generation in 3D

Dear all,

 

I am starting to work with "point clouds" like those obtained from LASER scanner for an academic student project and I have seen that in LabVIEW 8.6 there is a VIs set called Geometry where you can find some mesh generation and manipulation algorithms (like Delaunay triangulation). I am presently working with LabVIEW 7.1. I am wondering to upgrade to LV 8.6 but I am not sure about what I could really do with LV 8.6 (it seemed to me also that all those subVIs are for a 2D domain). Probably should I rather focus to Mathscript? In particular I would like to obtain from the "point clouds" the normal vectors to the triangles generated by the Delaunay triangulation (or similar algorithms).

Thank you a lot for your help.

 

Best regards,

 

Paolo

 

0 Kudos
Message 1 of 10
(7,693 Views)

Hi Paolo,

in LV 8.6 there is a method for class SceneMesh (you can set it through an invoke node) which generates a Delaunay triangulation: you can have a look at the help at this link.

You can also use Mathscript to perform this algorithm: a specific function exists (its help is here).

I hope this will help you!

Bye!

Licia

 

0 Kudos
Message 2 of 10
(7,665 Views)

HI Licia,

 

thank you a lot for your swift reply and information. Do you know please if the method you mention works also for 3D set of points or only on a 2D domain? I mean: can it also create a 3D mesh for a 3D object)? In case I will seriously consider to upgrade to LV 8.6.

Thank you a lot again.

 

Bye

 

Paolo

 

 

0 Kudos
Message 3 of 10
(7,659 Views)

Hi Paolo,

the method has as input an array of 3D points, each of them with x, y, z coordinates, so, yes, the method works for a 3D set of points.

Bye!

Licia

 

0 Kudos
Message 4 of 10
(7,641 Views)

Hi Licia,

 

sounds good! 

Thank you a lot again.

All the best,

 

Paolo

0 Kudos
Message 5 of 10
(7,632 Views)

Thanks to Licia and Paolo for unearthing this function. Now that mathscript isn't part of the standard LabView distribution, a built-in algorithm for computing the Delaunay triangulation it is especially welcome.

 

I found the documentation for the SceneMesh object pretty thin and it took a bit of experimentation to get this working. It turns out the DelaunayMesh method sorts the input array, rendering the output indices meaningless in terms of what the caller passed as input. I wrote a wrapper function around SceneMesh.DelaunayMesh that re-references everything to the input array and provides a more useful data structure as output.

 

The wrapper is released under the MIT license, so anyone may use it for any purpose. (The code is in LabView 2010; I can post a back-rev if there is interest.)

 

 

DelaunayTriangleDemo.png

Message 6 of 10
(7,041 Views)

Hi Rob,

 

Is that something a non-MIT grad (like me) could figure out?

 

I sounds like you have figured out how to generate all of that data I find in a wrl file when loading a 3D picture. I have not had to crack that nut yet but I may have to do so myself soon and my customers have lawyers that don't like extra licenses....

 

Curious,

 

Ben

Retired Senior Automation Systems Architect with Data Science Automation LabVIEW Champion Knight of NI and Prepper LinkedIn Profile YouTube Channel
0 Kudos
Message 7 of 10
(7,030 Views)

> sounds like you have figured out how to generate all of that data I find in a wrl file when loading a 3D picture...

 

 

I'm not doing anything with 3D pictures at all, actually. I just needed a Delaunay triangulation routine for some computational geometry I'm doing and good ones are nontrivial to write. (See the algorithms section of this Wikipedia entry). LabView's looks to be O(n log n) to my calibrated eye :-), which means it's pretty good.

 

DelaunayPerformance.png

 

Pretty good but not bug-free, unfortunately. While generating this plot I discovered that calling DelaunayMesh with a single vertex (but not zero, or two!) causes LabView to crash. (Silently, without failure logs, sigh...) So I put the input-checking code back in, and recommend the version in this post be used over the one above.

 

I filed a ticket on the crash.

Message 8 of 10
(7,015 Views)

hi! Rob, I am interested in the code. Can you please post it. I want to do delauney triangulation for 2D as well as 3D node-link graphs.

 

0 Kudos
Message 9 of 10
(5,855 Views)

This post is from a while ago. Recent versions of LabView have a computational geometry palette (Mathematics->Geometry->Computation Geometry) which includes Delaunay Triangulation, convex hull, polygon area etc.

 

The Computation Geometry version of the Delaunay Triangulation is much easier to use. Sadly it is also nearly 10 times slower than the 3DObj version :-(.

 

delaunay.png

Message 10 of 10
(5,182 Views)