An interface for meshes

[juliohm]

Hi @SimonDanisch , this is a follow up from yesterday's Discourse post where we shared that it would be nice to have an interface for general meshes, from simple Julia arrays (treated as regular meshes with zero storage for the coordinates) to general mixed-element meshes for various different purposes.

As an initial target, we could try to prove the concept that such interface would enable (1) geostatistical estimation/simulation of properties over meshes with GeoStats.jl, (2) physical simulation with available FEM solvers, and (3) plotting with Makie.jl

I understand that (3) is already done, and that perhaps (2) as well? Regarding (1), I would like to have your feedback on the interface copied/pasted below:

module Meshes

using StaticArrays: MVector

#--------------
# MESH TRAITS
#--------------
ndims(::Type{M}) where M = @error "not implemented"

ctype(::Type{M}) where M = @error "not implemented"

cbuff(m::Type{M}) where M = MVector{ndims(m),ctype(m)}(undef)

isstructured(::Type{M}) where M = Val{false}()

isregular(::Type{M}) where M = Val{false}()

COMPILE_TIME_TRAITS = [:ndims, :ctype, :cbuff, :isstructured, :isregular]

# default versions for mesh instances
for TRAIT in COMPILE_TIME_TRAITS
  @eval $TRAIT(::M) where M = $TRAIT(M)
end

elements(mesh::M) where M = @error "not implemented"

nelms(mesh::M) where M = length(elements(mesh))

#----------------------
# MESH ELEMENT TRAITS
#----------------------
coords!(x::AbstractVector, mesh::M, elm::E) where {M,E} =
  @error "not implemented"

function coords!(X::AbstractMatrix, mesh::M,
                 elms::AbstractVector) where M
  for j in 1:length(elms)
    coords!(view(X,:,j), mesh, elms[j])
  end
end

function coords(mesh::M, elm::E) where {M,E}
  x = cbuff(M)
  coords!(x, mesh, elm)
  x
end

function coords(mesh::M, elms::AbstractVector) where M
  X = Matrix{ctype(M)}(undef, ndims(M), length(elms))
  coords!(X, mesh, elms)
  X
end

coords(mesh::M) where M = coords(mesh, elements(mesh))

vertices(mesh::M, elm::E) where {M,E} = @error "not implemented"

nverts(mesh::M, elm::E) where {M,E} = length(vertices(mesh, elm))

#------------------------
# ELEMENT VERTEX TRAITS
#------------------------
coords!(x::AbstractVector, mesh::M, elm::E, vert::V) where {M,E,V} =
  @error "not implemented"

function coords!(X::AbstractMatrix, mesh::M, elm::E,
                 verts::AbstractVector) where {M,E}
  for j in 1:length(verts)
    coords!(view(X,:,j), mesh, elm, verts[j])
  end
end

function coords(mesh::M, elm::E, vert::V) where {M,E,V}
  x = cbuff(M)
  coords!(x, mesh, elm, vert)
  x
end

function coords(mesh::M, elm::E, verts::AbstractVector) where {M,E}
  X = Matrix{ctype(M)}(undef, ndims(M), nelms(mesh))
  coords!(X, mesh, elm, verts)
  X
end

end # module

It is a quite simple interface that covers all algorithms currently implemented in GeoStats.jl as far as I can tell. It consists of basic information about the dimension of the mesh and type of coordinates, an access function to an iterator of elements (e.g. elements could simply be the range 1:n), and functions to access the coordinates of the elements themselves (some pre-defined baricenter or centroid for different element types), and the coordinates of the vertices of the elements.

Does the current implementation in GeometryBasics.jl (and associated interface) cover this use case already? If not, can we work on it together to create a separate package (I suggest Meshes.jl) with a set of traits without implementation that covers the use case?

After that we could start extending this interface to include volume, surfacearea and other useful properties of elements that are constantly used in algorithms.

[visr]

Discourse thread for reference: https://discourse.julialang.org/t/finite-element-mesh-interface/33325

Just want to mention mesh types are becoming more frequent in geospatial context as well, so I'm quite interested in having an interface that could help there as well.

See for instance MDAL that @evetion make a start at wrapping in MDAL.jl.

Mesh data are (currently at least) not part of GeoInterfaceRFC.jl, but it is relevant since it is an interface that we hope GeometryBasics will subscribe to, to allow interoperability with other geospatial packages. Since GeometryBasics is close to many of the ideas in the interface, the implementation is very simple: https://github.com/JuliaGeometry/GeometryBasics.jl/compare/master...visr:rfc.

[juliohm]

That is a quite important use case as well @visr , thanks for sharing. We can start by creating a minimum interface for discretising geometrical objects into mesh elements as above, and then start adding more traits for projections, geometry, etc to include the use case with geo maps. Hopefully we can find a nice set of traits that gives us the power to express both 3D models of the subsurface as well as 2D projections of geographical objects in spheroids. That would be amazing.

What I will try to do next is take the mesh type defined here in GeometryBasics.jl and make it adhere to the interface. This will consist of simply making sure that access functions for the elements and coordinates of elements are defined for each type of element.

Will keep you guys posted of any updates.

[SimonDanisch]

Some of these are already implemented with a different name... Btw, I'd much prefer writing out the names, e.g. a novice user likely (or actually me, I can only guess) won't know what ctype or cbuff does ;)

[juliohm]

Thank you @SimonDanisch perhaps a doc string solves the issue? Please let me know if it is not clear and we can rename to something more explicit.

I've put a draft here organized by different types of traits, inspired by the existing efforts: https://github.com/juliohm/Meshes.jl

I will try to make the types in GeometryTypes.jl and CompScienceMeshes.jl adhere to the interface as a proof of concept. Please let me know if the repo should be migrated to JuliaGeometry, it will certainly be a better home than my personal account.

I've separated the traits into "mesh traits" containing general information about the mesh object/type, "element traits" containing information about mesh elements, and "vertex traits" containing a simple access function for the coordinates. The source is organized as follows:

src/
--core.jl ---> core API that all mesh types can and should implement
--basic.jl ---> basic API derived from core API (i.e. fallback implementations)
--geotraits.jl ---> geometric properties of the mesh and its elements (e.g. centroid ,volume)

We can continue extending the interface in separate files to fit all use cases that were raised. @visr @evetion do you have suggestions about projections and geographical coordinates? How do you see them interacting with the current verbs defined in the draft?

[SimonDanisch]

Thank you @SimonDanisch perhaps a doc string solves the issue? Please let me know if it is not clear and we can rename to something more explicit.

I'm roughly sticking to the YASGuide, and I also find it super useful for reading code by someone else to have more explicit names without starting to look up docstrings (e.g. when reading code on github, you can't even look them up... And even if you have a running julia session, it's not always clear where the function comes from and therefore unclear how to look up the doc string ;) )

[visr]

@visr @evetion do you have suggestions about projections and geographical coordinates? How do you see them interacting with the current verbs defined in the draft?

Not at this point, and I'm not sure these should be part of the mesh interface. As long as there is a solid, well though out mesh interface that supports a wide variety of mesh types, I'm sure it will be useful.

[PetrKryslUCSD]

For the mesh interface design, wouldn't it be helpful to start with a verbal description of what is to be expected of such an interface. What types of operations should be supported, roughly at what level, and so on. I think writing code at this point is a bit premature.

[juliohm]

@PetrKryslUCSD I have some ideas of what is expected from the interface coming from a statistical perspective, but certainly will miss other views from FEM solver writers and visualisation package writers. I want to get this draft going so that we at least have a proof of concept that this interface includes two existing implementations designed with these other goals in mind.

[PetrKryslUCSD]

Perhaps this may help? https://petrkryslucsd.github.io/FinEtools.jl/latest/guide/guide.html#Finite-element-1

[juliohm]

Awesome :) one more reference to dive in.

On Wed, Jan 15, 2020, 22:08 Petr Krysl notifications@github.com wrote:

Perhaps this may help? https://petrkryslucsd.github.io/FinEtools.jl/latest/guide/guide.html#Finite-element-1

— You are receiving this because you authored the thread. Reply to this email directly, view it on GitHub https://github.com/JuliaGeometry/GeometryBasics.jl/issues/15?email_source=notifications&email_token=AAZQW3PXWSCHYEDXEOSJCOLQ56XP3A5CNFSM4KG4PJS2YY3PNVWWK3TUL52HS4DFVREXG43VMVBW63LNMVXHJKTDN5WW2ZLOORPWSZGOEJCMMAY#issuecomment-574932483, or unsubscribe https://github.com/notifications/unsubscribe-auth/AAZQW3JNLCW4Q6MVCZXOGSDQ56XP3ANCNFSM4KG4PJSQ .

[PetrKryslUCSD]

This is interesting: https://codedocs.xyz/CEED/FMS/. I found it especially so since it uses several concepts included in my FinEtools. :)

[PetrKryslUCSD]

I wonder if this conversation could be revived? Again, I am asking: what is the purpose of the interface?

To answer my own question I will try to describe a scenario.

Let us say there are application libraries A, B, C (as you say, perhaps statistical modeling, finite element modeling, visualization). Then there is a package the user writes to define the mesh, D. The package D defines the structure for the mesh, functions to access this data, and the data for some particular meshes. The mesh data then should be available for processing in the libraries A, B, C. This can be done provided these libraries (A, B, C) are all aware of the interface: in other words, the interface must be defined in its own package, I, and the libraries A, B, C be using I.

So in this way the packages A, B, C are insulated from the actual implementation and storage of the mesh data in package D. However, they all need to be aware of I. And so do all the packages of the type of D.

Is that in any way consistent with what this conversation is about in the minds of those who already participated?

[juliohm]

That is pretty much it @PetrKryslUCSD. The ultimate goal is to be able to seamlessly transfer mesh types across different frameworks and have them work out of the box, no matter the internal storage layout, the different complexities involved, etc.

Sorry I didn't get back yet regarding this interface initiative. I've migrated the repository to the organization already, but got busy with a submission deadline for unrelated research. The issue is on my radar, and it will certainly be addressed to some extent before my next paper submission, which depends on it.

It would be really nice if we could prove the concept with the GeoStats.jl + FEM solver + Makie.jl combo. Will keep you posted of any progress or if I have questions regarding the design of the traits. My plan, as I shared above, is to first refine the interface to accommodate the existing mesh types in the ecosystem, starting with the mesh types defined in GeometryBasics.jl and CompScienceMeshes.jl.

[PetrKryslUCSD]

OK. So I take it your plan is to work on I? It seems to me that in order for this to make sense, package I should not reflect the realities of current mesh implementations (GeometryBasics.jl and CompScienceMeshes.jl). To begin with, they are fairly limited in what they can support (mostly only simplexes?).

I believe that a good place to start would be to list the functionality that this interface should support. Evaluation of interior and boundary integrals, location of points, evaluation of various fields (and differential operators on fields), topological operations (merging, splitting, boundary taking), and so on.

[PetrKryslUCSD]

I guess the alternative to an interface package with some functionality (which should work without any need for access to implementations other than through the interface) would be a bare-bones access to plane-vanilla mesh data (coordinates, connectivity), leaving everything up to the packages using the interface.

[juliohm]

Yes, the plan is to work on the set of traits in "I". You can find a very rough initial draft from that discussion in the beginning of the month here: https://github.com/JuliaGeometry/Meshes.jl

I certainly don't have the expertise to cover the FEM requirements well, and your help is much appreciated. To give you some context, my experience with FEM is limited to writing a simple 3D heat transfer solver with standard Galerkin methods for a specific PDE in C++.

What I would like to do before we move on with more advanced use cases for this interface, is to get the core API right (the coordinates and connectivity that you mentioned). My understanding is that the GMSH and VTK specifications, cover most mesh types of interest. After we have this core API set, we can add iterator traits for faces, edges, etc, and possibly default implementations based on the core traits.

[PetrKryslUCSD]

I think traits is the right tool. In addition to the mesh itself, I think also the "element" types should be equipped with trait dispatch. It other words, imagine you have an FE with four nodes. Obviously it must be handled differently when it is a quad as opposed to a tet.

[PetrKryslUCSD]

By the way, I don't think it is enough to consider homogeneous meshes. Mixing triangles with quadrilaterals, or wedges with hexahedra is quite common.

Also, there are meshes for the interior and meshes for the boundary. Obviously they are related by compatibility requirements. Should these meshes be stored separately or together?

Quite often multi-material domains require some treatment to distinguish between the materials. Separate meshes, or perhaps labels.

One other point: Incompatible meshes with tie constraints are also a possibility. Again, this may require storing meshes composed of different element types. So either separate meshes, or meshes that are heterogeneous.

[juliohm]

Fully agree. We have to provide a set of traits for elements of the mesh, and that is in the plans. The traits should be such that the different branches of code are determined at compile time without runtime penalties.

What taxonomy of elements you currently have in mind? The draft could start by listing the different element trait types like:

abstract type Element end
struct Simplicial <: Element end
struct Quadlateral <: Element end
...

This taxonomy will interplay with the connectivity traits and vertex ordering assumptions.

[PetrKryslUCSD]

FinEtools separates FEs by manifold dimension. Then by individual characteristics (how to compute basis functions, how to determine boundary, how to determine point inside/outside, etc.).

[SimonDanisch]

Btw, the mesh type in here already supports arbitrary connections & vertex types, and it also supports arbitrary edge/face/vertex metadata!

[PetrKryslUCSD]

Here is a sample implementation of the mesh interface and a package that wraps FinEtools meshes. Only a little bit of the functionality is actually implemented. https://github.com/PetrKryslUCSD/TestMeshInterface.jl.git https://github.com/PetrKryslUCSD/MeshInterface.jl.git

[juliohm]

Thank you @PetrKryslUCSD , I am collecting all the resources shared so far to tackle this interface seriously in the near future. When time allows, I will try to list the major use cases behind the interface.

[Paulms]

Hi, I have been learning recently the virtual element method VEM (works in polytopal heterogeneous meshes) and replicated some of my class examples by modifying the JuaFEM.jl code. The base mesh type that I found useful for VEM is the following: https://github.com/Paulms/jFEMTools.jl/blob/master/src/mesh.jl I hope you find it useful as an additional perspective for the interface.

[evetion]

@visr @evetion do you have suggestions about projections and geographical coordinates? How do you see them interacting with the current verbs defined in the draft?

For me, adding a CRS attribute would be enough to have this working, you could refer to the CoordinateReferenceSystemFormat type here: https://github.com/JuliaGeo/GeoFormatTypes.jl/blob/master/src/GeoFormatTypes.jl

Mesh data are (currently at least) not part of GeoInterfaceRFC.jl, but it is relevant since it is an interface that we hope GeometryBasics will subscribe to, to allow interoperability with other geospatial packages.

To be fair, Simple Features does specify some mesh support (PolyhedralSurface, such as TINs), see my issue here: https://github.com/yeesian/GeoInterfaceRFC.jl/issues/3. I would like to support the Meshes implemented here.

Lastly, there are proposals (disclosure, partly made by my organization @Deltares), to support meshes (output from our unstructured numerical models) in structured formats such as NetCDFs, called UGRID. The API is actually quite relevant and written out completely: https://ugrid-conventions.github.io/ugrid-conventions/.

[PetrKryslUCSD]

I have designed a lightweight mesh library. I believe it could accommodate the desirable features listed above. Even though it currently implements only linear shapes (simplex and cuboid types), adding quadratic and higher-order shapes is trivial. It may even be possible to accommodate shapes with implicit geometry (such as for topologically regular grids). https://github.com/PetrKryslUCSD/MeshCore.jl

[juliohm]

Thank you @PetrKryslUCSD , it seems like you have an implementation of meshes for FEM, correct? I see some structs defined there, and some actual implementations of how things behave.

I am almost done with that journal paper, and will start reviewing the prior art soon. Thank you for sharing yet another resource. 💯

[SimonDanisch]

Cool! There is lots of overlap with GeometryBasics, how do we want to handle that?

[juliohm]

I maintain that viewpoint that we can work together on a lightweight Meshes.jl interface (without implementations), and let people implement the interface for their own mesh types.

P.S.: I bought this book on Voronoi tessellation that arrived yesterday, and I hope that I will find the time to start working on the interface by the end of the month. Do you have suggestions of books on meshes and meshing algorithms in general?

[PetrKryslUCSD]

There are good papers I'd recommend. I will make up a list and post it here.

There are also poor mesh topology designs: The one underlying FENICS (as implemented in Dolfin) is for instance wrong.

[PetrKryslUCSD]

I need to go to work, but later today I will address the questions above.

[PetrKryslUCSD]

I maintain that viewpoint that we can work together on a lightweight Meshes.jl interface (without implementations), and let people implement the interface for their own mesh types.

The mesh library can not a simple container of stuff. It needs to be able to generate new information: incidence relations, often based on new, derived, meshes. That means that either the library must have an implementation built-in for these purposes, or the user must provide hooks for the mesh information to be generated on the fly and stored in the user's data structures.

At this point I decided to endow the library with an implementation, leaving open the question whether or not I want to provide dispatch based on traits leaving the implementation open. Or, perhaps providing a default implementation that the user can override.

[PetrKryslUCSD]

This one is rather good: This paper has a lot of good stuff on high-order methods and the requirements they impose on meshes:

[PetrKryslUCSD]

Cool! There is lots of overlap with GeometryBasics, how do we want to handle that?

Please correct me if I'm wrong but there don't seem to be any topological operations implemented yet in GeometryBasics. On the other hand it does have the "shapes" covered pretty well.

[SimonDanisch]

be any topological operations implemented yet

What kind of operations are you thinking of?

[PetrKryslUCSD]

So in my little library I have implemented so far the indicated operations: But, eventually one should provide all those incidence relations. For instance, continuous mixed methods may require adjacency information for which faces separate individual finite elements, which edges are shared by finite elements, and so on.

There also needs to be access to the boundary as one of the basic operations. That can be satisfied by one of the incidence relations above, equipped with an appropriate predicate.

[SimonDanisch]

You need to consider, that I have no formal education in geometries whatsoever, so it's pretty hard for me to follow ;) Are you talking about connections between vertices? Because I think I've all combinations of flat + volume simplices with arbitrary edge metadata covered... But I already figured out with @mohamed82008 in https://github.com/JuliaGeometry/GeometryBasics.jl/issues/2, that we'll need to write out some documentation & wrappers around it, so that they're easy to use...

[PetrKryslUCSD]

The table above is straightforward: d -> 0 means list the vertices connected by the entity, 0 -> d means list entities connected to a vertex. The other incidence relations indicated by an "X" may be, for instance, for a given face list all edges in the mesh that are connected to it (2 -> 1), or list all faces in the mesh that bound a given solid (3 -> 2), or list the solid elements that share face (2 -> 3). I hope this helps?

[PetrKryslUCSD]

I should add that the entities involved in these relations are global, not local, entities. For instance, all faces of a 3D mesh constitute a related mesh, consisting of unique faces.

[sjkelly]

@PetrKryslUCSD can you drop a link to your library?

If I am understanding correctly and can put the table into (other) words... We would want to be able to pick an edge and get all tetrahedra with that edge?

[PetrKryslUCSD]

https://github.com/PetrKryslUCSD/MeshCore.jl

If I am understanding correctly and can put the table into (other) words... We would want to be able to pick an edge and get all tetrahedra with that edge?

Yes, that type of relation.

[PetrKryslUCSD]

Two more topology operations implemented. There are easy two more, by transposition. That will give me a pretty good idea what sort of interface we should implement by traits if the user's code was to store the data instead of the library.

[mohamed82008]

I think realistically we also need to think about the tradeoffs here. For example, the time and memory complexity of various topology operations for different mesh representations. Optimizing the memory access patterns for different topology operations and different mesh representations is another practical concern. I don't know if people here have given these much thought yet but I imagine it's not going to be straightforward. What I would like to see though is being able to store multiple representations of the same mesh in a Mesh struct to make more topology operations more time efficient if needed at the expense of additional memory.

[PetrKryslUCSD]

Would you elaborate a bit? Sounds relevant, but I am not sure what is being suggested.

[PetrKryslUCSD]

Found an interesting series of papers on the Sieve. It is implemented in DMPlex. Looks really cool, despite its fierce insistence on using words not normally used in this subject area.

[mohamed82008]

@PetrKryslUCSD what I mean is that the 0 -> 3 operation may have a time complexity of O(N) where N is the number of points/elements if we only store the points in each element but not the inverse mapping. If we store the inverse mapping, 0 -> 3 can be made O(1) in time but O(N) additional memory is needed. The same applies to other mappings.

[PetrKryslUCSD]

@mohamed82008 Very true. These costs are often hidden with the use of fancy stuff (iterators). It is probably better to make these costs explicit.

[mohamed82008]

Yes so one can have arguments specifying which mappings get pre-computed and stored at mesh construction time. Dispatch should then be able to do the 0 -> 3 query for example in O(1) time if possible. Otherwise, an O(N) fallback can be used. If the query is done once or a few times, the user may not need the additional caching. But if an algorithm will call 0 -> 3 many (~N) times, then the user can opt in to the additional caching to avoid a quadratic complexity.

[mohamed82008]

I think this automatic caching and iterator interface plus visualization are enough reasons for me to switch to the new mesh interface in TopOpt.jl. It will simplify a fair bit of code that I have over there.

[PetrKryslUCSD]

Yes, I see the value. At this point I am redesigning the lib using incidence relations consistently. It should be checked in later today. That will fill in all those incidence relations in the "guide" table that make sense (not the d -> d, d > 0; those need definitions through a third entity. That is another place where the Logg mesh interface of FENICS does not make sense.)