Generating meshes from point clouds

[ElOceanografo]

Apologies if this is already possible and I just couldn't find it. It would be excellent to have methods for generating meshes from randomly ordered point clouds. Likewise, methods for refining them so they are "nice" (angles not too acute, etc.).

[juliohm]

You are not missing anything, we still need to implement such methods. I am trying to finish something first before jumping into the tesselation problem from point clouds. It would be nice to understand how you are using the package? Also, more than welcome to contribute with code too 👍

[ElOceanografo]

Good to hear! I'm interested in generating meshes for Markov random spatial fields, to use in spatio-temporal statistical models. My use case is to take a set of geographical boundaries (e.g. coastlines) and a set of irregularly-spaced observations and generate a triangulated mesh that follows the boundaries and is higher-resolution in areas with more observations. A simple example is on the Readme for this WIP package; see also this issue.

[juliohm]

It would be nice to interface with GeoStats.jl at some point, that is create a solver that is compatible with the project so that it can be easily plugged with other types and features there.

Meshes.jl is being developed with spatial modeling in mind, it is nice to see projects like yours in this context. :)

[ucalyptus2]

@juliohm would delaunay triangulation be a good candidate to answer this issue?

[juliohm]

@forkbabu yes, Delaunay is a valid approach. I've finished the FIST algorithm for triangulation of polygonal areas, and the next step is to add some Delaunay/Voronoi functionality. If you have experience in the subject, please feel free to contribute. There is also other open issues that could be addressed more quickly like test coverage.

[ElOceanografo]

I was recently looking at the method in this paper, which is what VoronoiDelaunay.jl uses and seems like a fast and robust approach. I don't think it would be that hard to implement using the interface in this package. While I'm tempted, I unfortunately don't think I have the time to do it myself right now.

Whatever approach is used, having some way to refine the triangulation is important. That might be a separate issue, though, since it'll be applicable to all triangulations (polygons, point clouds, combinations, whatever).

[evetion]

FWIW, there's a first work-in-progress attempt at wrapping startin over at StarTIN.jl, so you would have at least the Delaunay Triangulation part covered.

[juliohm]

Thanks @evetion there is also VoronoiDelaunay.jl in pure Julia right? We would like to have an implementation inside Meshes.jl to avoid the fragmentation we currently have in JuliaGeometry. Also we would like to use a consistent set of geometry and point types that has been extensively tested as we are doing here. VoronoiDelaunay.jl uses raw Julia vectors for points and from what I quickly scanned StarTIN.jl uses matrices. Ideally we will create an implementation that uses Point for the vertices and Triangle for the triangles and Mesh for the result.

[evetion]

VoronoiDelaunay.jl only accepts coordinates between 1.0 and 2.0 I believe. StarTIN.jl should use a trait based interface to accept points and return meshes, while the underlying C interface just are vectors.

Btw, do you have a star struct already in Meshes? See Blandford et al. (2003). https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.9.6823

[juliohm]

Em seg., 8 de mar. de 2021 às 17:49, Maarten Pronk <notifications@github.com> escreveu:

VoronoiDelaunay.jl only accepts coordinates between 1.0 and 2.0 I believe. StarTIN.jl should use a trait based interface to accept points and return meshes, while the underlying C interface just are vectors.

It would be nice to try to reuse some of the work in VoronoiDelaunay.jl and provide a scaling of the result (pre and post) processing the results.

Btw, do you have a star struct already in Meshes? ☺️

As in the star generator right? The region of a polygon from which all other points are seen... I have to remember the exact definition, but we don't have a type for it yet nor an algorithm if there exists one. :)

…

— You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub <#18 (comment)>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/AAZQW3PQBEAUCFRE673PDX3TCUZ4DANCNFSM4TXRF5EA> .

[juliohm]

Unfortunately, VoronoiDelaunay.jl is very buggy and is not user-friendly. I checked StarTIN.jl but couldn't find an easy method to get the connectivity list. Is there a method already exposed?

Fortunately, I could use MiniQHull.jl in some of my current research assignments. It is simple and to the point.

[evetion]

I checked StarTIN.jl but couldn't find an easy method to get the connectivity list. Is there a method already exposed?

Not yet. Is there a preferred way of getting such a list? The structure in StarTIN is a star, so from a vertex to all other vertices. Or do you want the actual triangles like [a, b, c]?

[juliohm]

The connectivities of the triangle would be ideal. It will be nice to compare all these different well-established implementations as we evolve our own pure Julia implementations in Meshes.jl.

[juliohm]

Update. We can now sample points homogeneously on an initial mesh with blue noise. That means that we can enforce a minimum distance between points and consequently produce good triangles during tesselation.

Next step consists of introducing a tesselate(pointset, method) function and adding methods. We can introduce a separate package to integrate existing tesselation libraries written in other languages while we gradually implement some methods in pure Julia.