honeycomb_kernels

Module grisubal

Source
Expand description

GRISUBAL algorithm description & implementation

This module contain all code used to implement our grid submersion algorithm, or GRISUBAL for short.

This algorithm builds the mesh of a geometry by overlapping a grid over it and intersecting the grid with the geometry. It is inspired by the approach described in this research note.

§Assumptions / Hypotheses

Boundaries are consistently oriented, i.e.:

  • normals of segments making up a boundary all point outward / inward, no mix
  • boundaries are closed
  • if there are nested boundaries, their orientation are consistent one with the other; this is an extension of the first condition

§Algorithm

The steps followed by the algorithm are detailed in the user guide. The following is a summary.

§Pre-processing

  1. Compute characteristics of a grid covering the entire geometry, avoiding exact intersection between the grid’s segments and the geometry’s vertices.
  2. Remove “redundant” Points of Interest to avoid duplicated vertices.
  3. Check for obvious orientation issues (open geometry & orientation per boundary).

§Main kernel

  1. Compute intersection vertices between the geometry’s segments and the grid.
  2. Insert given intersections into the grid.
  3. Build new edge data by searching through the original segments.
  4. Insert the new edges into the map. Mark darts on each side of the edge with the Boundary attribute.

§Post-processing clip

Depending on the specified argument, one side (or the other) of the boundary can be clipped. This is specified using the Clip enum; The following steps describe the operation for Clip::Left.

  1. Fetch all darts marked as Boundary::Left during the last step of the main kernel.
  2. Use these darts’ faces as starting point for a coloring algorithm. The search is done using a BFS and only consider adjacent faces if the adjacent dart isn’t marked as a boundary. This step is also used to check for orientation inconsistencies, most importantly orientation across distinct boundaries.
  3. Delete all darts making up the marked faces.

The Boundary attribute is then removed from the map before return.

Enums§

  • Clip
    Post-processing clip operation.
  • GrisubalError
    Enum used to model potential errors of the grisubal kernel.

Functions§