Last active
October 31, 2024 06:19
-
-
Save paniq/8bdec20d00d08810f081 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| 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 |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
You might also want to check the CGAL library and documentation: http://doc.cgal.org/latest/Manual/packages.html