This is a work-in-progress collector for facts and references about computational geometry and topological mesh modeling that I think might be useful when thinking about 3D design.
STL files
Standard Tessellation Language files are not much more than lists of triples of triples of numbers, or in other words, ordered lists of three points in three-dimensional space. Or, in other other words, descriptions of oriented triangles, like this:
facet normal ni nj nk outer loop vertex v1x v1y v1z vertex v2x v2y v2z vertex v3x v3y v3z endloop endfacet
Triangulations
A triangulation of a polygon is a maximal set of non-crossing interior diagonals, as shown here: Fun facts:
- Every polygon has at least one triangulation.
This can be proved by strong induction on the number of vertices, where the inductive step involves cutting the polygon into smaller polygons along a diagonal, and using the Jordan Curve Theorem to ensure that the triangles in the two smaller polygons do not overlap. Some polygons have only one possible triangulation, while others have many. - Not every polyhedron is tetrahedralizable.
The simplest example is the Schönhardt polyhedron, which is a twisted triangular prism constructed in such a way that all tetrahedra that share vertices with the polyhedron fall into the exterior.
In OpenSCAD, the Schönhardt polyhedron can be constructed with just two* lines of code, using linear_extrude and the $fn option:linear_extrude(height=10,twist=30,slices=1) circle(5,$fn=3);
- For every triangulation of an n-vertex polyhedron, we have:
Number of triangles
If there are h holes added, then number of triangles
Number of diagonals
Sum of interior angles
Total turn angle around the boundary
See the free Chapter 1 of Devadoss/O’Rourke for proofs of these facts, each of which rely either on strong induction or simple combinatorics. - The area of a polygon with vertices is:
Here the sum over is “wrap around”, so that is one of the terms. This crazy fact is a special case of Green’s Theorem known as the surveyor’s formula, or the shoelace algorithm.
- The number of triangulations of a convex polygon with vertices is:
Here is the th Catalan number. The number of triangulations of a non-convex polyhedron is always less than or equal to this number. For more on the enumeration of convex polygon triangulations, see Greg Aloupis’ project page.
- more fun facts will be inserted here…
Reference Books
- Discrete and Computational Geometry, Devadoss/O’Rourke
This textbook is a nice bridge between the algorithmic and theoretical. You can see the Table of Contents and all of Chapter 1 free online. - Computational Geometry, de Berg/Cheong/van Kreveld/Overmar
A more advanced textbook, and the one used in Suri’s and Ungor’s Computational Geometry courses in the list below. The Table of Contents and all of Chapter 15 are free online.
Course Pages
- Computational Geometry class from Subash Suri
Very nice course notes from Suri’s Computational Geometry course at the University of California, Santa Barbara, including pages about triangulations, convex hulls, and Voronoi diagrams. - Computational Geometry class from Alper Ungor
Links and outline from Ungor’s Computational Geometry course at the University of Florida, including these non-lecture notes about Polygon Triangulation. - Computational Geometry class from Stefan Langerman
Lecture-links and projects from Langerman’s course at the Computational Geometry Lab at McGill University.
Links
- Modelling Three-Dimensional Objects Using Java 2D and 3D, at what-when-how
This four-part tutorial overview starts with Part 1, which discusses triangulations, topology, voxels, and tessellations. Part 2 continues with surface modelling, Java 3D scenes, and two-variable functions. Part 3 covers geometric transformations, and Part 4 deals with affine transforms and animations. - Pepakura software for making papercraft
Pepakura is a Windows-based program that can turn 3d meshes into tabbed paper models. The Designer software costs $38, but the Viewer is free. There is even a dedicated Sihouette Cameo Viewer, for using with that particular papercutter.
Publications
- Topological Mesh Modeling Papers List
Ergun Akleman, Professor in the Visualization Department at Texas A&M University, has an amazing list of publications about topology, remeshing, texturization, and more. The math in those publications is made real in the mesh modeling system TopMod. - Creating Optimized Cut-Out Sheets for Paper Models from Meshes
This paper, by Raphael Straub and Hartmut Prautzch of the Karlsruher Institut fur Technologie, discusses an optimized algorithm for converting a textured polygon mesh represented by an indexed face set in a VRML97 file into cut-out sheets for paper models. - An End-to-End Approaceh to Making Self-Folded 3D Surface Shapes by Uniform Heating
Eric Demaine at MIT and many coauthors have this paper that is related to what some people now call “4d printing,” that is, converting a 3D mesh into a self-folding sheet that creases when heat is applied.
* I think actually that might only be one line of code that I happened to press “Return” in the middle of. Although I suppose any bunch of code could technically be written on one loooong line…
1 Response