Skip to content

Instantly share code, notes, and snippets.

@paniq
Last active February 14, 2024 20:17
  • Star 99 You must be signed in to star a gist
  • Fork 9 You must be signed in to fork a gist
Star You must be signed in to star a gist
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:
http://en.wikipedia.org/wiki/Types_of_mesh
http://en.wikipedia.org/wiki/Tetrahedron
http://en.wikipedia.org/wiki/Simplicial_complex
A C++ library that deals with tetrahedral and other volumetric meshes
http://www.openvolumemesh.org/
The data structure from "Half-edges redux" could be expanded similarly
to OVM for one more indirection.
https://fgiesen.wordpress.com/2012/04/03/half-edges-redux/
Mesh Generation (slides)
Gives Euler-Poincaré metrics for tet meshes, typical valences, a whole range of
methods for tetrahedralization and refinement.
http://perso.uclouvain.be/vincent.legat/teaching/documents/meca2170-jfr-cours3.pdf
The Linear Tetrahedron
Course paper about tetrahedra, discussing properties, use cases and associated
formulas for metrics, transformations, etc.
http://www.colorado.edu/engineering/CAS/courses.d/AFEM.d/AFEM.Ch09.d/AFEM.Ch09.pdf
------------------------------
(Vaguely) related research links:
* An Unified Approach for 2D and 3D Rasterization
voxelization of tetrahedra as analog to rasterization of triangles.
http://virtual.inesc.pt/siacg02/papers/10.pdf
* 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.
http://openvm.org/data/OVM.pdf
* TransCut: Interactive Rendering of Translucent Cutouts
Renders tetrahedral meshes with subsurface scattering in real time,
provides non-destructive cutting to look inside the mesh
http://research.microsoft.com/en-us/um/people/stevelin/papers/tvcg13.pdf
* 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.
ftp://ftp.disi.unige.it/person/DanovaroE/pdf/3dpvt.pdf
A newer summary is here
* The Half-Edge Tree: A Compact Data Structure for
Level-of-Detail Tetrahedral Meshes
ftp://ftp.disi.unige.it/person/MagilloP/PDF/het-short.pdf
* Progressive Simplicial Complexes
Describes a format to store simplices at varying levels of detail
http://groups.csail.mit.edu/graphics/pubs/sigg97-psc.pdf
* Multiphase Flow of Immiscible Fluids on Unstructured Moving Meshes
Uses deformable simplical complexes to animate fluids
https://www.cs.ubc.ca/~rbridson/docs/misztal-sca2012-multiphaseDSC.pdf
[LD08] Accelerating Ray Tracing using Constrained Tetrahedralizations
Tetrahedralizes space around an object to skip space while raytracing
http://graphics.cs.kuleuven.be/publications/LD08ARTCTc/LD08ARTCTc_supplementary.pdf
* Fast, Exact, Linear Booleans
Describes how to elegantly perform CSG operations on BSP trees
http://www.gilbertbernstein.com/resources/booleans2009.pdf
In this context probably relevant:
* Automatic Convexification of Space using BSP-trees
http://vgc.poly.edu/~csilva/papers/bsp-fill.pdf
* BSP-ASSISTED CONSTRAINED TETRAHEDRALIZATION
http://cow.mooh.org/research/joshi_imr2003.pdf
* Exact and Robust (Self-)Intersections for Polygonal Meshes
Follow-up paper to the one above, expanding on the technique
https://www.graphics.rwth-aachen.de/publication/35/campen_2010_eg_021.pdf
* Automatic merging of tetrahedral meshes (S.H.Lo)
To my knowledge the only paper on doing boolean operations / CSG
on tetmeshes.
http://onlinelibrary.wiley.com/doi/10.1002/nme.4425/abstract [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.
http://luebke.us/publications/eg09.pdf
* Real-Time Deformation and Fracture in a Game Environment
The research that went into the Euphoria engine
http://graphics.berkeley.edu/papers/Parker-RTD-2009-08/Parker-RTD-2009-08.pdf
* Invertible Finite Elements For Robust Simulation of Large Deformation
demonstrates how preserving inverted tets can be used to reconstruct objects
after severe deformation.
https://www.math.ucla.edu/~jteran/papers/ITF04.pdf
* Delaunay Triangulation in R3 on the GPU
gDel3D thesis: http://daariga.github.io/papers/gdel3d-thesis.pdf
software: https://github.com/ashwin/gstar4d
Follow-up paper from 2014:
http://www.comp.nus.edu.sg/~tants/gdel3d_files/gDel3D.pdf
* Dihedral Angle-based Maps of Tetrahedral Meshes
introduces an alternate parametrization in which meshes are completely
defined by their dihedral angles
http://www-etud.iro.umontreal.ca/~paillegp/volumeabf.html
* Optimized Spatial Hashing for Collision Detection of Deformable Objects
does exactly what it says on the tin, the example operates on tetmeshes
http://matthias-mueller-fischer.ch/publications/tetraederCollision.pdf
* Air Meshes for Robust Collision Handling
deals with tesselating air around moving objects
http://matthias-mueller-fischer.ch/publications/airMeshesPreprint.pdf
* Position-Based Simulation Methods in Computer Graphics
long tutorial text on how to implement a position based dynamics physics system
http://www.researchgate.net/profile/Jan_Bender/publication/274940214_Position-Based_Simulation_Methods_in_Computer_Graphics/links/552cc4a40cf29b22c9c466df.pdf
* Projective Dynamics: Fusing Constraint Projections for Fast Simulation
an improvement on position-based dynamics supporting meshing independence
http://www.seas.upenn.edu/~ladislav/bouaziz14projective/bouaziz14projective.html
* Stable Constrained Dynamics
a physics system presented at SIGGRAPH 2015, claiming an improvement over projective
dynamics and a high level of stability
https://hal.inria.fr/hal-01157835/document
* Simulating Liquids and Solid-Liquid Interactions with Lagrangian Meshes
contains a method to create unions of overlapping tets
http://graphics.berkeley.edu/papers/Clausen-SLS-2013-04/Clausen-SLS-2013-04.pdf
* A Realtime GPU Subdivision Kernel
a strategy to subdivide meshes on the GPU; they use catmull-clark,
but claim other methods are possible.
http://www.cs.kent.edu/~zwang/schedule/dc6.pdf
and a later one from 2012
* Feature Adaptive GPU Rendering of Catmull-Clark Subdivision Surfaces
http://graphics.pixar.com/library/GPUSubdivRenderingA/paper.pdf
* Nick's Voxel Blog: Implementing Dual Contouring
a new implementation of dual contouring including source code; that's always nice.
http://ngildea.blogspot.de/2014/11/implementing-dual-contouring.html
* Fast Ray–Tetrahedron Intersection using Plücker Coordinates
http://pelopas.uop.gr/~nplatis%20/files/PlatisTheoharisRayTetra.pdf
* 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.
http://www.cs.utah.edu/~aek/research/triangle.pdf
* Fast tetrahedron-tetrahedron overlap algorithm
http://vcg.isti.cnr.it/Publications/2003/GPR03/fast_tetrahedron_tetrahedron_overlap_algorithm.pdf
clojure implementation is here
https://gist.github.com/postspectacular/9021724
* Smooth Subdivision of Tetrahedral Meshes
a variation of Loop subdivision for volumes
http://www.cs.rice.edu/~jwarren/papers/tetrahedral.pdf
and a catmull-clark like scheme for hexahedral volumes
http://www.cs.rice.edu/~jwarren/papers/hexahedral.pdf
* Arbitrary Cutting of Deformable Tetrahedralized Objects
what it says on the tin
http://pages.cs.wisc.edu/~sifakis/papers/cutting.pdf
* 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.
http://www.ann.jussieu.fr/frey/papers/meshing/Bridson%20R.,%20Adaptive%20physics%20based%20tetrahedral%20mesh%20generation%20using%20level%20sets.pdf
* A CRYSTALLINE, RED GREEN STRATEGY FOR MESHING HIGHLY DEFORMABLE OBJECTS WITH TETRAHEDRA
More on the subject from the paper above (same authors, same pictures)
https://www.math.ucla.edu/~jteran/papers/MBTF03.pdf
* Adaptive and Quality Tetrahedral Mesh Generation
explains the basics of octree-based BCC volume meshing
http://www.imr.sandia.gov/papers/imr19/RNwang.pdf
* 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"
http://on-demand.gputechconf.com/gtc/2010/presentations/S12020-GPU-Accelerated-Data-Expansion-Marching-Cubes-Algorithm.pdf
* RealTime QuadTree Analysis using HistoPyramids
describes how to use histopyramids to extract a quadtree / octree analog is similar
http://citeseerx.ist.psu.edu/viewdoc/download;jsessionid=BA2CD67F3A384DDDBFC63862DB248AC0?doi=10.1.1.90.7288&rep=rep1&type=pdf
* GPU Data Structures for Graphics and Vision
a short summary of how histopyramids can help creating quadtrees / octrees
http://www.cg.tuwien.ac.at/~vogi/_misc/thesis%20defense%20-%20presentation.pdf
* Cascaded Light Propagation Volumes for Real-Time Indirect Illumination
could be adapted for a tetrahedral BCC grid
http://www.vis.uni-stuttgart.de/~dachsbcn/download/lpv.pdf
solid angle calculations for how much flux each face receives
have been done in detail here:
Light Propagation Volumes - Annotations (Andreas Kirsch)
http://blog.blackhc.net/wp-content/uploads/2010/07/lpv-annotations.pdf
and an extensive thesis is here, with a shorter solid angle calculation scheme in the appendix
Higher Order Light Propagation Volumes
https://escholarship.org/uc/item/3d36v53h
Multiple papers on Sparse Voxel Octree Cone Tracing & related stuff:
* Interactive Indirect Illumination Using Voxel Cone Tracing
https://research.nvidia.com/publication/interactive-indirect-illumination-using-voxel-cone-tracing
* High Resolution Sparse Voxel DAGs
http://www.cse.chalmers.se/~uffe/HighResolutionSparseVoxelDAGs.pdf
* CASCADED VOXEL CONE TRACING
http://fumufumu.q-games.com/archives/000934.php
* Lattice-Based Volumetric Global Illumination
light propagation on a FCC (face-centered cubic) lattice
http://www3.cs.stonybrook.edu/~mueller/papers/latticeVis07_final.pdf
* VolQD: Direct Volume Rendering of Multi-million Atom Quantum Dot Simulations
contains implementation details for FCC lattices
https://engineering.purdue.edu/purpl/level2/papers/VolQD.pdf
* Isosurface Stuffing: Fast Tetrahedral Meshes with Good Dihedral Angles
describes how to perform marching tetrahedra on BCC lattice
http://www.cs.berkeley.edu/~jrs/papers/stuffing.pdf
* 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.
http://www.cs.utah.edu/~bronson/papers/Cleaver_IMR_2012.pdf
* Isosurfaces on Optimal Regular Samples
does marching octahedra on BCC lattice
http://ivg.ucd.ie/files/shared/CTM03_BCCIsosurfaces.pdf
* Fast Deformation of Volume Data Using Tetrahedral Mesh Rasterization
a tetrahedral grid is used to deform a voxel cube
http://www.gmrv.es/Publications/2013/GEPTO13/paper.pdf
* Light probe interpolation using tetrahedral tessellations
subdivides open spaces in map into tetrahedra, stores light probes at vertices
http://twvideo01.ubm-us.net/o1/vault/gdc2012/slides/Programming%20Track/Cupisz_Robert_Light_Probe_Interpolation.pdf
* Highly Adaptive Liquid Simulations on Tetrahedral Meshes
what it says on the can; the subdivision scheme is BCC
http://pub.ist.ac.at/group_wojtan/projects/2013_Ando_HALSoTM/download/tetflip_fixed.pdf
* Particle-based Sampling and Meshing of Surfaces in Multimaterial Volumes
high quality results but expensive computations
http://www.cs.utah.edu/~kirby/Publications/Kirby-36.pdf
* Per-face parametrization for Texture Mapping of Geometry in Real-Time
how the frostbite engine maps textures per face
http://www.frostbite.com/wp-content/uploads/2014/11/meshcolors_report.pdf
* Fast Grid-Free Surface Tracking
a fast way to track and fix evolving 2-manifold meshes
http://matthias-mueller-fischer.ch/publications/explicitSurfaceTrackingPreprint.pdf
* Generalized Distance Functions
SDF functions for polyhedra
http://www.viz.tamu.edu/faculty/ergun/research/implicitmodeling/papers/sm99.pdf
* 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)."
http://www.cs.columbia.edu/~keenan/Projects/DGPDEC/
* Theory, Analysis and Applications of 2D Global Illumination
discussing global illumination in 2D
http://www.cs.dartmouth.edu/~wjarosz/publications/jarosz12theory.pdf
* Instant Level-of-Detail
An algorithm for decimating meshes on the GPU; contains an approach to sorting
edges and finding duplicates
http://www.mathematik.uni-marburg.de/~derzapf/public/2011/Simplifizierer.pdf
* Improved GPU Sorting
An algorithm for sorting 1D values on the GPU in O(n log2(n) + log(n)) time
http://http.developer.nvidia.com/GPUGems2/gpugems2_chapter46.html
* A parallel GPU-based algorithm for Delaunay edge-flips
Refining a mesh after transformation so it remains Delaunay, on the GPU.
http://swp.dcc.uchile.cl/TR/2011/TR_DCC-20110315-003.pdf
* 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
http://www.ci.i.u-tokyo.ac.jp/~hachisuka/tdf2015.pdf
* PositionBasedDynamics
An MIT licensed library that simulates physics using position based dynamics
https://github.com/janbender/PositionBasedDynamics
* Real-time Image Quilting: Arbitrary Material Blends, Invisible Seams, and No Repeats
A texturing technique based on vertex splats that requires no UV maps
http://advances.realtimerendering.com/s2011/Malan%20-%20Real-time%20Texture%20Quilting%20(Siggraph%202011%20Advances%20in%20Real-Time%20Rendering%20Course).pptx
http://hl.udogs.net/files/Uploads/%20User%20Uploads/PunkUser'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
http://alice.loria.fr/publications/papers/2011/HASH/CoherentParallelHashing.pdf
Books
=====
* 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.
http://www.amazon.com/Finite-Element-Mesh-Generation-Daniel/dp/041569048X
@thierry-sousbie
Copy link

You might also want to check the CGAL library and documentation: http://doc.cgal.org/latest/Manual/packages.html

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