Populating STL surface mesh uniformly with points

Question

I would like to be able to take a STL file (triangulated surface mesh) and populate the mesh with points such that the density of points in constant. I am writing the program in Fortran.

So far I can read in binary STL files and store vertices and surface normals. Here is an example file which has been read in (2D view for simplicity).

Example STL file in 2 dimensions.

My current algorithm fills each triangle using the following formula:

x = v1 + a(v2 - v1) + b(v3 - v1) (from here)

Where v1, v2, v3 are the vertices of the triangle and x is a arbitrary position within the triangle (or on the edges) . "a" and "b" vary between 0 and 1 and their sum is less than 1. They represent the distance along two of the edges (which start from the same vertex). The gap between the particles should be the same for each edge. Below is an example of the results I get: Example STL file in 2 dimensions populated with points

The resulting particle density if nowhere near uniform. Do you have any idea how I can adapt my code such that the density will be constant from triangle to triangle? Relevant code below:

        ! Do for every triangle in the STL file
        DO i = 1, nt

           ! The distance vector from the second point to the first
           v12 = (/v(1,j+1)-v(1,j),v(2,j+1)-v(2,j),v(3,j+1)- v(3,j)/)
           ! The distance vector from the third point to the first
           v13 = (/v(1,j+2)-v(1,j),v(2,j+2)-v(2,j),v(3,j+2)- v(3,j)/)
           ! The scalar distance from the second point to the first
           dist_a = sqrt( v12(1)**2 + v12(2)**2 + v12(3)**2 )       
           ! The scalar distance from the third point to the first
           dist_b = sqrt( v13(1)**2 + v13(2)**2 + v13(3)**2 )
           ! The number of particles to be generated along the first edge vector
           no_a = INT(dist_a / spacing)             
           ! The number of particles to be generated along the second edge vector           
           no_b = INT(dist_b / spacing) 
           ! For all the particles to be generated along the first edge
           DO a = 1, no_a
               ! For all the particles to be generated along the second edge
               DO b = 1, no_b

                  IF ((REAL(a)/no_a)+(REAL(b)/no_b)>1) EXIT

                  temp(1) = v(1,j) + (REAL(a)/no_a)*v12(1) + (REAL(b)/no_b)*v13(1)
                  temp(2) = v(2,j) + (REAL(a)/no_a)*v12(2) + (REAL(b)/no_b)*v13(2)
                  temp(3) = v(3,j) + (REAL(a)/no_a)*v12(3) + (REAL(b)/no_b)*v13(3)

                  k = k + 1

                  s_points(k, 1:3) = (/temp(1), temp(2), temp(3)/) 

                END DO 

           END DO 

           j = j + 3

       END DO

People seem really too sensitive with the downvotes in last days, although some of them were in place. Can you try to change the spacing so that the area (volume) of a unit box is constant? The solution will not be isotropic, but the density should be constant. — Vladimir F Героям слава, Oct 28 '14 at 21:05
I was confused as to why I was downwvoted, a comment would have been useful so I could edit my question to make it more useful / clear. I think it would be tricky to achieve isotropy. Ill try as you suggest and work out the volume of each plane / triangle. From that Ill try and ensure that the number of particles per area is constant. — 1QuickQuestion, Oct 29 '14 at 10:17
Try to scale the spacing so that the quadrilateral made from the vectors v12/spacing and v13/spacing has a defined area. Btw. in Fortran 2008 there is a function `norm2` that can be used to easily compute the length of a vector. — Vladimir F Героям слава, Oct 29 '14 at 10:22

score 0 · Answer 1 · edited May 23 '17 at 11:46

The solution I went with was to split each triangle into two right angled triangles. This is done by projecting the vetex opposite the longest edge orthogonally onto the longest edge. This splits the trianlge into two smaller triangles each with a 90 degree angle. A detailed answer on how to do this can be found here. By generating points along both 90° bends, a uniform distribution of particles can be achieved.

This method needs to be adapted so that particles are not generated more than once along edges which are common to multiple triangles. I have not done this yet. See image below for results. This solution does not achieve an isotropic distribution but this is not a concern for my intended application.

(Thanks to Vladimir F for his comments and advice on norm2, I tried to implement his approach but was not competent enough to get it to work).

enter image description here

Populating STL surface mesh uniformly with points

1 Answers1