Skip to content

Mesh elements storage

Mesh domains are defined as a collection of Mesh elements.

We are using R-Tree spatial index in Sort Tile Recursive implementation from NetTopologySuite.

The created index consists of:

  • non-leaf nodes : stores a collection of child nodes, and the bounding box (rectangle)
  • leaf node - contains mesh elements, so-called 'level 0'

image.png

Each node is setup to have at most 16 child nodes.

Building the index is a non-trivial spatial operation. For reuse we store the created R-tree index in 2 files. These files are reused for quick reconstruction of the index during queries.

  • spatial.lfs file - contains leave nodes (mesh elements).
  • spatial.idx file - constains non leaf nodes hierarchy.

Mesh node

Defined by X, Y position and optional Z (for static vertical domains)

Mesh element

In a typical mesh, nodes are shared among many elements

image.png

Storing each individual element with its full node definition would lead to excessive information storage. For better performance we reuse the node definition among elements:

  • store nodes as an array
  • element nodes are defined as indexes to node array.

Mesh Page

To be able to retrieve only a small number of elements required by the query and fully reconstruct their nodes, we store spatially adjacent set of at most 256 elements as a mesh page.

The 'level 1' of R-tree index ( contains 256 = 16*16 elements) is mapped to a mesh page. Each 'level 1' page contains 'Page start' and 'Page size' values, describing the position and allocation of the page inside spatial.lfs file.

image.png

Mesh page binary serialization

  • Element node indexes are stored as bytes not integers
  • (save 3 bytes * number of nodes per element (3,4)), saves 30% of space.
  • Nodes on a mesh page are adjacent, 1 node is stored with double precision, but other are stored as deltas with single precision, for (x,y only) - 8 bytes is saved per node.
  • Each page fits to 3kB which can be retrieved very quickly from the storage.