Skip to content

Instantly share code, notes, and snippets.

Last active February 14, 2024 20:17
Show Gist options
  • Save paniq/8bdec20d00d08810f081 to your computer and use it in GitHub Desktop.
Save paniq/8bdec20d00d08810f081 to your computer and use it in GitHub Desktop.
Below I collected relevant links and papers more or less pertaining to the subject of tetrahedral meshes.
It's an ever-growing list.
Relevant links:
A C++ library that deals with tetrahedral and other volumetric meshes
The data structure from "Half-edges redux" could be expanded similarly
to OVM for one more indirection.
Mesh Generation (slides)
Gives Euler-Poincaré metrics for tet meshes, typical valences, a whole range of
methods for tetrahedralization and refinement.
The Linear Tetrahedron
Course paper about tetrahedra, discussing properties, use cases and associated
formulas for metrics, transformations, etc.
(Vaguely) related research links:
* An Unified Approach for 2D and 3D Rasterization
voxelization of tetrahedra as analog to rasterization of triangles.
* OpenVolumetricMesh-An Efficient Data Structure for Tetrahedral
and Hexahedral Meshes
Data structure for both cubic and tetrahedral volumes. Elevates
the face structure to a half-face structure analog to half-edges.
Volume mesh operations are then well-defined.
* TransCut: Interactive Rendering of Translucent Cutouts
Renders tetrahedral meshes with subsurface scattering in real time,
provides non-destructive cutting to look inside the mesh
* Half-Edge Multi-Tessellation: A Compact Representation for
Multi-Resolution Tetrahedral Meshes
Discusses techniques to store different LOD levels of a volume
in a single structure for adaptive mesh extraction.
A newer summary is here
* The Half-Edge Tree: A Compact Data Structure for
Level-of-Detail Tetrahedral Meshes
* Progressive Simplicial Complexes
Describes a format to store simplices at varying levels of detail
* Multiphase Flow of Immiscible Fluids on Unstructured Moving Meshes
Uses deformable simplical complexes to animate fluids
[LD08] Accelerating Ray Tracing using Constrained Tetrahedralizations
Tetrahedralizes space around an object to skip space while raytracing
* Fast, Exact, Linear Booleans
Describes how to elegantly perform CSG operations on BSP trees
In this context probably relevant:
* Automatic Convexification of Space using BSP-trees
* Exact and Robust (Self-)Intersections for Polygonal Meshes
Follow-up paper to the one above, expanding on the technique
* Automatic merging of tetrahedral meshes (S.H.Lo)
To my knowledge the only paper on doing boolean operations / CSG
on tetmeshes. [paywall]
* Fast BVH Construction on GPUs
Introduces the LBVH as an efficient method to quickly build a
bounding volume hierarchy. Useful for doing spatial queries on tetmeshes.
* Real-Time Deformation and Fracture in a Game Environment
The research that went into the Euphoria engine
* Invertible Finite Elements For Robust Simulation of Large Deformation
demonstrates how preserving inverted tets can be used to reconstruct objects
after severe deformation.
* Delaunay Triangulation in R3 on the GPU
gDel3D thesis:
Follow-up paper from 2014:
* Dihedral Angle-based Maps of Tetrahedral Meshes
introduces an alternate parametrization in which meshes are completely
defined by their dihedral angles
* Optimized Spatial Hashing for Collision Detection of Deformable Objects
does exactly what it says on the tin, the example operates on tetmeshes
* Air Meshes for Robust Collision Handling
deals with tesselating air around moving objects
* Position-Based Simulation Methods in Computer Graphics
long tutorial text on how to implement a position based dynamics physics system
* Projective Dynamics: Fusing Constraint Projections for Fast Simulation
an improvement on position-based dynamics supporting meshing independence
* Stable Constrained Dynamics
a physics system presented at SIGGRAPH 2015, claiming an improvement over projective
dynamics and a high level of stability
* Simulating Liquids and Solid-Liquid Interactions with Lagrangian Meshes
contains a method to create unions of overlapping tets
* A Realtime GPU Subdivision Kernel
a strategy to subdivide meshes on the GPU; they use catmull-clark,
but claim other methods are possible.
and a later one from 2012
* Feature Adaptive GPU Rendering of Catmull-Clark Subdivision Surfaces
* Nick's Voxel Blog: Implementing Dual Contouring
a new implementation of dual contouring including source code; that's always nice.
* Fast Ray–Tetrahedron Intersection using Plücker Coordinates
* Optimizing Ray-Triangle Intersection via Automated Search
an analog but superior alternative to the method above, computing ray distance
and barycentric coordinates of hit from the triple product of 4 tetrahedra.
* Fast tetrahedron-tetrahedron overlap algorithm
clojure implementation is here
* Smooth Subdivision of Tetrahedral Meshes
a variation of Loop subdivision for volumes
and a catmull-clark like scheme for hexahedral volumes
* Arbitrary Cutting of Deformable Tetrahedralized Objects
what it says on the tin
* Adaptive Physics Based Tetrahedral Mesh Generation Using Level Sets
volumetric meshing using a body-centered cubic (BCC) lattice, incluing
an explanation why BCC lattices are awesome (top reason: Octree compatible)
Also describes a spring model to keep tetrahedra convex.,%20Adaptive%20physics%20based%20tetrahedral%20mesh%20generation%20using%20level%20sets.pdf
More on the subject from the paper above (same authors, same pictures)
* Adaptive and Quality Tetrahedral Mesh Generation
explains the basics of octree-based BCC volume meshing
* GPU-accelerated data expansion for the Marching Cubes algorithm
these slides explain histopyramids, an approach to do O(log n) filter/reduce on the GPU, there
called "stream compaction / expansion"
* RealTime QuadTree Analysis using HistoPyramids
describes how to use histopyramids to extract a quadtree / octree analog is similar;jsessionid=BA2CD67F3A384DDDBFC63862DB248AC0?doi=
* GPU Data Structures for Graphics and Vision
a short summary of how histopyramids can help creating quadtrees / octrees
* Cascaded Light Propagation Volumes for Real-Time Indirect Illumination
could be adapted for a tetrahedral BCC grid
solid angle calculations for how much flux each face receives
have been done in detail here:
Light Propagation Volumes - Annotations (Andreas Kirsch)
and an extensive thesis is here, with a shorter solid angle calculation scheme in the appendix
Higher Order Light Propagation Volumes
Multiple papers on Sparse Voxel Octree Cone Tracing & related stuff:
* Interactive Indirect Illumination Using Voxel Cone Tracing
* High Resolution Sparse Voxel DAGs
* Lattice-Based Volumetric Global Illumination
light propagation on a FCC (face-centered cubic) lattice
* VolQD: Direct Volume Rendering of Multi-million Atom Quantum Dot Simulations
contains implementation details for FCC lattices
* Isosurface Stuffing: Fast Tetrahedral Meshes with Good Dihedral Angles
describes how to perform marching tetrahedra on BCC lattice
* Lattice Cleaving: Conforming Tetrahedral Meshes of Multimaterial Domains with Bounded Quality
Constructs a subdivided tetrahedral mesh from a multi-material isosurface
using a 6-cut stencil.
* Isosurfaces on Optimal Regular Samples
does marching octahedra on BCC lattice
* Fast Deformation of Volume Data Using Tetrahedral Mesh Rasterization
a tetrahedral grid is used to deform a voxel cube
* Light probe interpolation using tetrahedral tessellations
subdivides open spaces in map into tetrahedra, stores light probes at vertices
* Highly Adaptive Liquid Simulations on Tetrahedral Meshes
what it says on the can; the subdivision scheme is BCC
* Particle-based Sampling and Meshing of Surfaces in Multimaterial Volumes
high quality results but expensive computations
* Per-face parametrization for Texture Mapping of Geometry in Real-Time
how the frostbite engine maps textures per face
* Fast Grid-Free Surface Tracking
a fast way to track and fix evolving 2-manifold meshes
* Generalized Distance Functions
SDF functions for polyhedra
* Digital Geometry Processing with Discrete Exterior Calculus
A suggestion from a comment at hacker news; "It's an introductory course
in discrete differential geometry and it emphasizes the use of simplicial
complexes (like tetrahedral meshes)."
* Theory, Analysis and Applications of 2D Global Illumination
discussing global illumination in 2D
* Instant Level-of-Detail
An algorithm for decimating meshes on the GPU; contains an approach to sorting
edges and finding duplicates
* Improved GPU Sorting
An algorithm for sorting 1D values on the GPU in O(n log2(n) + log(n)) time
* A parallel GPU-based algorithm for Delaunay edge-flips
Refining a mesh after transformation so it remains Delaunay, on the GPU.
* Implementing a practical rendering system using GLSL
Includes a clever strategy for BVH traversion in the fragment shader,
a better pseudo random number generator for GLSL shaders,
and an approach for generating stochastic hash tables in shaders
* PositionBasedDynamics
An MIT licensed library that simulates physics using position based dynamics
* Real-time Image Quilting: Arbitrary Material Blends, Invisible Seams, and No Repeats
A texturing technique based on vertex splats that requires no UV maps's%20Uploads/Malan%20-%20Real-time%20Texture%20Quilting%20(Siggraph%202011%20Advances%20in%20Real-Time%20Rendering%20Course).pdf
* Coherent Parallel Hashing, Garcia, Lefebvre et al
* Finite Element Mesh Generation (Daniel S.H.Lo)
contains a method on how to merge meshes, but exorbitantly expensive,
so I can't afford it.
Copy link

You might also want to check the CGAL library and documentation:

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment