{ "cells": [ { "cell_type": "raw", "metadata": { "raw_mimetype": "text/restructuredtext" }, "source": [ "*******************************************\n", "Topological Invariants of Discrete Surfaces\n", "*******************************************" ] }, { "cell_type": "raw", "metadata": { "raw_mimetype": "text/restructuredtext" }, "source": [ ":cite:`botsch2010polygon` is a whirlwind tour of the applications that makes use\n", "of differential geometry. The lack of exercises makes this is a quick read.\n", "Its focus is to provide a mental model of the digital geometry processing\n", "pipeline.\n", "\n", ":cite:`zhang2016gcs` is a nice introductory overview to peruse before starting\n", "differential geometry. There are a few concepts to be aware of:\n", "\n", "- An analytic function is a function that is locally given by a convergent\n", " power series.\n", "- `Not all smooth functions are analytic`_.\n", "- `Isomorphic vector spaces have equal dimension`_.\n", "- :cite:`zweckiftrm` gives a more intuitive explanation that supplements the\n", " proof for Theorem 1.1.4 in :cite:`zhang2016gcs`.\n", "\n", ".. _Not all smooth functions are analytic: https://en.wikipedia.org/wiki/Non-analytic_smooth_function#The_function_is_not_analytic\n", ".. _Isomorphic vector spaces have equal dimension: http://linear.ups.edu/html/section-IVLT.html\n", "\n", "At the core of discrete differential geometry lies a hierarchy of structures in\n", "geometry: `topological structure`_ :math:`\\supset`\n", "`differentiable structure`_ :math:`\\supset` `geometric structure`_. The\n", "intuition behind these conceptual primitives are essential to understanding more\n", "complex subjects.\n", "\n", ".. _topological structure: http://brickisland.net/DDGSpring2016/wp-content/uploads/2016/02/DDG_CMUSpring2016_TopologicalStructure-1.pdf\n", ".. _differentiable structure: http://brickisland.net/DDGSpring2016/wp-content/uploads/2016/02/DDG_CMUSpring2016_DifferentiableStructure.pdf\n", ".. _geometric structure: http://brickisland.net/DDGSpring2016/wp-content/uploads/2016/02/DDG_CMUSpring2016_GeometricStructure-2.pdf\n", "\n", "After reading the aforementioned materials, complete Chapter 4 in\n", ":cite:`crane2015discrete`." ] }, { "cell_type": "raw", "metadata": { "raw_mimetype": "text/restructuredtext" }, "source": [ "Polyhedral Formula\n", "==================\n", "\n", "Recall that a `simple polygon`_ encloses a region with no holes where exactly\n", "two edges meet at each vertex, and the number of edges :math:`E` is equal to the\n", "number of vertices :math:`V`.\n", "\n", ".. _simple polygon: https://en.wikipedia.org/wiki/Simple_polygon\n", "\n", "Polygonal Disk\n", "--------------\n", "\n", "A polygonal disk is any topological disk constructed out of simple polygons.\n", "The simplest polygonal disk is a simple polygon that has :math:`F = 1`. By\n", "inspection, the base case is satisfied. For the inductive step, suppose\n", ":math:`V - E + F = 1` holds for a polygonal disk with :math:`F` faces,\n", ":math:`V` vertices, and :math:`E` edges.\n", "\n", "There are only two valid operations on a polygonal disk. When placing a new\n", "vertex on an existing edge, that edge is split into two edges without affecting\n", ":math:`F`. The polyhedral formula still holds because\n", ":math:`(V + e) - (E + e) + F = 1` where :math:`e = 1`.\n", "\n", "When a new face is delimited within the polygonal disk, the resulting simple\n", "polygon must introduce :math:`e + v` new vertices and :math:`e + v + 1` new\n", "edges where :math:`v \\in \\mathbb{W}` is the number of new vertices placed on\n", "non-edges and :math:`e \\in \\mathbb{W}` is the number of new vertices placed on\n", "edges. The simple polygon cannot be formed using an entirely new set of\n", "vertices and edges because that decomposition would violate the definition of a\n", "polygonal disk. The polyhedral formula still holds because\n", ":math:`(V + e + v) - (E + e + v + 1) + (F + 1) = 1`.\n", "\n", "Polyhedron\n", "----------\n", "\n", "A polyhedron is a sphere made of polygons. The simplest polyhedron is a\n", "tetrahedron with :math:`V = 4` vertices, :math:`E = 6` edges, and\n", ":math:`F = 4` faces. By inspection, the base case :math:`V - E + F = 2` is\n", "satisfied. For the inductive step, suppose that relationship holds for a\n", "polyhedron with :math:`F` faces, :math:`V` vertices, and :math:`E` edges.\n", "Imagine inflating that polyhedron until it is a sphere. Any decomposition of\n", "the polyhedron can then be interpreted as operations on the surface of the\n", "sphere. These operations are equivalent to the ones for a polygonal disk\n", "assuming the polyhedron is simply connected. Thus :math:`V - E + F = 2` holds\n", "for any simply connected polyhedron." ] }, { "cell_type": "raw", "metadata": { "raw_mimetype": "text/restructuredtext" }, "source": [ ".. _nlph2017dgp-ex-1-platonic-solids:\n", "\n", "Platonic Solids\n", "===============\n", "\n", "The vertices of a Platonic solid have equal valence :math:`q`. Let :math:`p` be\n", "the number of edges (or equivalently vertices) of each face, and let :math:`q`\n", "be the number of faces (or equivalently edges) that meet at each vertex.\n", "\n", "Since any edge joins two vertices and has two adjacent faces,\n", "\n", ".. math::\n", "\n", " pF = 2E = qV\n", "\n", "because the edges are double counted. Since the simplest Platonic solid has\n", ":math:`p, q \\geq 3`, there are only five Platonic solids that satisfy\n", "\n", ".. math::\n", "\n", " V - E + F &= 2 & \\quad & \\text{Euler's polyhedral formula}\\\\\n", " \\frac{2E}{q} - E + \\frac{2E}{p} &= 2\\\\\n", " \\frac{1}{q} + \\frac{1}{p} &= \\frac{1}{E} + \\frac{1}{2}\\\\\n", " \\frac{1}{q} + \\frac{1}{p} &> \\frac{1}{2}." ] }, { "cell_type": "raw", "metadata": { "raw_mimetype": "text/restructuredtext" }, "source": [ ".. _nlph2017dgp-ex-1-regular-valence:\n", "\n", "Regular Valence\n", "===============\n", "\n", "The valence of a vertex in a piecewise linear surface is the number of faces\n", "that contain that vertex. A vertex of a simplicial surface is said to be\n", "regular when its valence equals :math:`q = 6`. A simplicial surface is defined\n", "to have :math:`p = 3` edges per face. Since any edge joins two vertices and has\n", "two adjacent faces, the\n", ":ref:`previously derived relationship `\n", "\n", ".. math::\n", "\n", " \\newcommand{\\Euler}{\\textrm{Euler}}\n", " \\newcommand{\\Poincare}{\\textrm{Poincaré}}\n", " qV = 2E = pF\n", "\n", "still holds. Applying the :math:`\\Euler-\\Poincare` formula reveals\n", "\n", ".. math::\n", "\n", " 2 - 2g &= V - E + F\\\\\n", " &= \\frac{2E}{6} - E + \\frac{2E}{3}\\\\\n", " &= 0\\\\\n", " g &= 1.\n", "\n", "Therefore, the only simplicial surface for which every vertex has a regular\n", "valence is a torus that has a genus of one." ] }, { "cell_type": "raw", "metadata": { "raw_mimetype": "text/restructuredtext" }, "source": [ ".. _nlph2017dgp-ex-1-minimally-irregular-valence:\n", "\n", "Minimally Irregular Valence\n", "===========================\n", "\n", "Suppose a simplicial surface :math:`K` has a genus :math:`g` where each vertex\n", ":math:`i` has valence :math:`q_i \\geq 3`, :math:`p = 3`, and there are finitely\n", "many faces.\n", "\n", "The :ref:`relationship ` between edges,\n", "faces, and vertices is now\n", "\n", ".. math::\n", "\n", " pF = 2E = 6 (V - n) + \\sum_{j = 1}^n q_j\n", "\n", "where :math:`n` is the number of vertices with irregular valence. Applying the\n", ":math:`\\Euler-\\Poincare` formula gives\n", "\n", ".. math::\n", "\n", " 2 - 2g &= V - E + F\\\\\n", " &= V - \\frac{1}{2} pF + F\\\\\n", " &= V +\n", " \\frac{2 - p}{2} \\left( \\frac{6 (V - n) + \\sum_{j = 1}^n q_j}{p} \\right)\\\\\n", " &= V - (V - n) - \\frac{1}{6} \\sum_j q_j\n", " & \\quad & p = 3\\\\\n", " n &= 2 - 2g + \\frac{1}{6} \\sum_j q_j\\\\\n", " n &= 2 - 2g + \\frac{1}{6} \\sum_j 3 + q'_j\n", " & \\quad & q'_j = q_j - 3 \\geq 0\\\\\n", " n &= 4 - 4g + \\frac{1}{3} \\sum_j q'_j\\\\\n", " &\\geq 4 - 4g.\n", "\n", "By inspection, :math:`m(K)` is satisfied for :math:`g = 0` and :math:`g = 1`.\n", "When :math:`g \\geq 2`, :math:`n \\geq 1` because\n", "\n", ".. math::\n", "\n", " n &= 4 - 4g + \\frac{1}{3} \\sum_j q'_j\\\\\n", " 0 &= 4 - 4g\n", "\n", "contradicts while\n", "\n", ".. math::\n", "\n", " n &= 4 - 4g + \\frac{1}{3} \\sum_j q'_j\\\\\n", " 1 &= 4 - 4g + \\frac{1}{3} q'_j\\\\\n", " q'_j &= 12g - 9\n", "\n", "is feasible for a connected, orientable simplicial surface." ] }, { "cell_type": "raw", "metadata": { "raw_mimetype": "text/restructuredtext" }, "source": [ "Mean Valence\n", "============\n", "\n", "The :ref:`relationship ` between\n", "edges, faces, and vertices in a connected, orientable simplicial surface is now\n", "\n", ".. math::\n", "\n", " pF = 2E = \\sum_{i = 1}^V q_i.\n", "\n", "Applying the :math:`\\Euler-\\Poincare` formula gives\n", "\n", ".. math::\n", "\n", " 2 - 2g &= V - E + F\\\\\n", " &= V - \\frac{1}{2} \\sum_i q_i + \\frac{1}{p} \\sum_i q_i\\\\\n", " \\frac{1}{6} \\sum_i q_i &= V - 2 + 2g\n", " & \\quad & p = 3\\\\\n", " \\frac{1}{V} \\sum_i q_i\n", " &= 6 - \\frac{12 + 12g}{V},\n", "\n", "which shows that the mean valence :math:`q_\\infty = V^{-1} \\sum_i q_i \\to 6` as\n", ":math:`V \\to \\infty` and\n", "\n", ".. math::\n", "\n", " q_\\infty = V^{-1} 2E = V^{-1} pF\n", " \\implies\n", " \\begin{cases}\n", " F = \\frac{1}{p} V q_\\infty = 2V\\\\\n", " E = \\frac{1}{2} V q_\\infty = 3V\n", " \\end{cases}" ] }, { "cell_type": "raw", "metadata": { "raw_mimetype": "text/restructuredtext" }, "source": [ ".. _nlph2017dgp-ex-1-area-of-a-spherical-triangle:\n", "\n", "Area of a Spherical Triangle\n", "============================\n", "\n", "Recall that any two distinct great circles intersect in two points which are\n", "negatives of each other :cite:`champanerkarstgt`. The angle between two great\n", "circles at an intersection point is the angle between their respective planes.\n", "A region bounded by two great circles is called a diangle. The angle at both\n", "the vertices are equal. Both diangles bounded by two great circles are\n", "congruent to each other.\n", "\n", "Let :math:`\\theta` be the angle of a diangle. Suppose the area of the diangle\n", "is not :math:`2 \\theta`. When the diangles are parallel (:math:`\\theta = \\pi`),\n", "each diangle represents a hemisphere whose area is :math:`2 \\pi` because the\n", "surface area of a sphere is :math:`4 \\pi`. However, this implies each diangle\n", "has an area of :math:`2 \\theta`, which is a contradiction. Therefore, the area\n", "of a diangle is :math:`2 \\theta`.\n", "\n", "Given a spherical triangle with interior angles\n", ":math:`\\left\\{ \\alpha_i \\right\\}_{i = 1}^3`, let :math:`A` denote the area of\n", "the spherical triangle and :math:`a_i = 2 \\alpha_i` represent the area of each\n", "diangle. Observe that the union of all diangle pairs covers more than the\n", "surface area of a sphere because :math:`A` gets counted four times over. Thus\n", "\n", ".. math::\n", "\n", " 4 \\pi &= \\sum_i 2 a_i - 4A\\\\\n", " A &= \\sum_i \\alpha_i - \\pi\n", " & \\quad & \\text{Girard’s Theorem}." ] }, { "cell_type": "raw", "metadata": { "raw_mimetype": "text/restructuredtext" }, "source": [ ".. _nlph2017dgp-ex-1-area-of-a-spherical-polygon:\n", "\n", "Area of a Spherical Polygon\n", "===========================\n", "\n", "Recall that a polygon with :math:`n > 3` vertices can be decomposed into\n", ":math:`n - 2` triangles. \n", "\n", "A spherical polygon is a polygon whose sides are parts of great circles.\n", "\n", "Computing the area of each resulting\n", ":ref:`spherical triangle ` gives\n", "\n", ".. math::\n", "\n", " A =\n", " \\sum_i \\alpha_i - (n - 2) \\pi =\n", " (2 - n) \\pi + \\sum_i \\alpha_i." ] }, { "cell_type": "raw", "metadata": { "raw_mimetype": "text/restructuredtext" }, "source": [ "Angle Defect\n", "============\n", "\n", "For a discrete surface, the area on the unit sphere bounded by a spherical\n", "polygon whose vertices are the unit normals of the faces around :math:`v`\n", "is equal to the angle defect\n", "\n", ".. math::\n", "\n", " d(v) = 2 \\pi - \\sum_{f \\in F_v} \\angle_f(v)\n", "\n", "where :math:`F_v` is the set of faces containing :math:`v` and\n", ":math:`\\angle_f(v)` is the interior angle of face :math:`f` at vertex :math:`v`.\n", "\n", "By the :ref:`area of a spherical polygon `,\n", "the following condition must hold:\n", "\n", ".. math::\n", "\n", " A &= d(v)\\\\\n", " 2 \\pi - n\\pi + \\sum_{i = 1}^n \\beta_i\n", " &= 2 \\pi - \\sum_{f \\in F_v} \\angle_f(v)\\\\\n", " \\sum_{i = 1}^n \\beta_i\n", " &= \\sum_{f \\in F_v} \\pi - \\angle_f(v)\n", "\n", "where :math:`\\left\\{ \\beta_i \\right\\}_{i = 1}^n` are the consecutive interior\n", "angles of the spherical polygon.\n", "\n", "Suppose :math:`a, b, c` are consecutive faces of the discrete surface sharing\n", "the vertex :math:`v`. Let :math:`N_a, N_b, N_c` denote the corresponding unit\n", "normals of the faces. The direction of the intersection line (or edge) between\n", "each face is defined as :math:`E_{ba} = N_b \\times N_a` and\n", ":math:`E_{bc} = N_b \\times N_c`.\n", "\n", "The dihedral angle between two planes, which have normal vectors\n", ":math:`N_a` and :math:`N_b`, is given by\n", ":math:`\\cos \\theta_{ab} = N_a \\cdot N_b`.\n", "\n", "The great-circle distance is the shortest distance between two points on the\n", "surface of a sphere measured along the surface of the sphere. A great circle of\n", "a sphere is the intersection of the sphere and a plane that passes through the\n", "center of the sphere. The angle between two great circles at an intersection\n", "point is the angle between their respective planes.\n", "\n", "In order to show :math:`\\beta_i = \\pi - \\angle_f(v)` where :math:`i = f` (i.e.\n", "they share a unit normal), an appropriate origin :math:`O` for the sphere is\n", "needed. Define :math:`O + N_b` as the intersection between the geodesic arc\n", "connecting :math:`N_a` to :math:`N_b` and the geodesic arc connecting\n", ":math:`N_c` to :math:`N_b`.\n", "\n", "The projection of that intersection onto the plane :math:`(v, N_b)` is\n", "\n", ".. math::\n", "\n", " P_b &= (O + N_b) - \\left( N_b \\cdot (O + N_b - v) \\right) N_b\\\\\n", " &= (O + N_b) - (N_b \\cdot O) N_b - N_b + (N_b \\cdot v) N_b\\\\\n", " &= O - (N_b \\cdot O) N_b + (N_b \\cdot v) N_b\\\\\n", " &= O + \\left( N_b \\cdot (v - O) \\right) N_b.\n", "\n", "By the `spherical law of cosines`_, the angle :math:`\\beta_b` is given by\n", "\n", ".. _spherical law of cosines: https://en.wikipedia.org/wiki/Spherical_law_of_cosines\n", "\n", ".. math::\n", "\n", " \\cos \\beta_b = t_{ba} t_{bc}\n", "\n", "where the tangent vectors are defined as\n", "\n", ".. math::\n", "\n", " t_{b\\cdot} =\n", " \\frac{\n", " N_\\cdot - N_b (N_b \\cdot N_\\cdot)\n", " }{\n", " \\left\\Vert N_\\cdot - N_b (N_b \\cdot N_\\cdot) \\right\\Vert\n", " } =\n", " \\frac{\n", " N_\\cdot - N_b \\cos \\theta_{b\\cdot}\n", " }{\n", " \\sin \\theta_{b\\cdot}\n", " }\n", "\n", "and :math:`\\theta_{b\\cdot}` denotes the geodesic arc length on the unit sphere.\n", "\n", "The tangent vectors at :math:`P_b` are orthogonal to both edges because\n", "\n", ".. math::\n", "\n", " t_{b\\cdot} \\cdot E_{b\\cdot}\n", " &= \\frac{\n", " N_\\cdot - N_b \\cos \\theta_{b\\cdot}\n", " }{\n", " \\sin \\theta_{b\\cdot}\n", " }\n", " \\cdot\n", " (N_b \\times N_\\cdot)\\\\\n", " &= \\frac{1}{\\sin \\theta_{b\\cdot}} \\left(\n", " N_\\cdot \\cdot (N_b \\times N_\\cdot) -\n", " N_b \\cos \\theta_{b\\cdot} \\cdot (N_b \\times N_\\cdot)\n", " \\right)\n", " &= 0.\n", "\n", "By inspection of :math:`v`, :math:`P_b`, and the projection of :math:`P_b` onto\n", "both edges, the resulting polygon is regular and has an internal angle sum of\n", ":math:`2 \\pi = \\angle_b + \\beta_b + \\pi`. Therefore,\n", ":math:`\\beta_b = \\pi - \\angle_b`. :cite:`gluck2012gnt` has an insightful\n", "illustration of this proof." ] }, { "cell_type": "raw", "metadata": { "raw_mimetype": "text/restructuredtext" }, "source": [ "Discrete Gauss-Bonnet Theorem\n", "=============================\n", "\n", "The (connected, orientable) simplicial surface :math:`K` has no boundary.\n", "\n", "The following makes use of the fact that a triangle has an internal angle sum\n", "equal to :math:`\\pi`.\n", "\n", ".. math::\n", "\n", " \\sum_{v \\in V} d(v)\n", " &= \\sum_{v \\in V} 2 \\pi - \\sum_{f \\in F_v} \\angle_f(v)\\\\\n", " &= 2 \\pi V - \\sum_{v \\in V} \\sum_{f \\in F_v} \\angle_f(v)\\\\\n", " &= 2 \\pi V - \\pi F\n", " & \\quad & p = 3\\\\\n", " &= 2 \\pi V - \\pi F + 0\\\\\n", " &= 2 \\pi V - \\pi F + \\pi (3F - 2E)\n", " & \\quad & pF = 2E\\\\\n", " &= 2 \\pi \\chi." ] }, { "cell_type": "raw", "metadata": { "raw_mimetype": "text/restructuredtext" }, "source": [ "Total Curvature\n", "===============\n", "\n", "Recall that the median of a triangle is a line segment joining a vertex to the\n", "midpoint of the opposing side. The intersection of all medians is at the\n", "triangle's barycenter. The resulting six smaller triangles have equal area.\n", "The medians are not necessarily orthogonal to the edge they bisect. The\n", "intersection of a triangle's perpendicular bisectors is called the circumcenter.\n", "\n", ":cite:`crane2015discrete` approximates the discrete Gaussian curvature with\n", "barycentric cells because of its simplicity.\n", "\n", ":cite:`meyer2003discrete` proposes a unified and consistent set of flexible\n", "tools to approximate important geometric attributes such as normal vectors and\n", "curvatures on arbitrary triangle meshes, specifically 2-manifolds and\n", "3-manifolds in :math:`nD`. The approximation, based on Voronoi cells, has\n", "tight error bounds. The curvature operators (e.g. mean, Gaussian, principal)\n", "are motivated through the Laplace-Beltrami operator, a generalization of the\n", "Laplacian from flat spaces to manifolds." ] }, { "cell_type": "raw", "metadata": { "raw_mimetype": "text/restructuredtext" }, "source": [ "Pointwise Curvature Estimates\n", "=============================\n", "\n", ":cite:`meek2000surface` shows that the angle deficit method approximates the\n", "curvature to accuracy :math:`\\mathcal{O}(1)`. The method does converge to the\n", "correct solution as the mesh becomes more refined :cite:`magid2007comparison`." ] }, { "cell_type": "raw", "metadata": { "raw_mimetype": "text/restructuredtext" }, "source": [ ".. rubric:: References\n", "\n", ".. bibliography:: chapter-01.bib" ] } ], "metadata": { "anaconda-cloud": {}, "celltoolbar": "Raw Cell Format", "kernelspec": { "display_name": "Python [default]", "language": "python", "name": "python3" }, "language_info": { "codemirror_mode": { "name": "ipython", "version": 3 }, "file_extension": ".py", "mimetype": "text/x-python", "name": "python", "nbconvert_exporter": "python", "pygments_lexer": "ipython3", "version": "3.5.2" } }, "nbformat": 4, "nbformat_minor": 0 }