6 ms·

Discrete Differential Geometry: An Applied Introduction [pdf]

230 points by adamnemecek 7y ago

adamnemecek 7y ago
You should really check out the author's research https://www.cs.cmu.edu/~kmcrane/ https://www.cs.cmu.edu/~kmcrane/ There's also a repo for this https://github.com/dgpdec/course https://github.com/dgpdec/course
- amelius 7y ago
  And check out this short video he made to promote a talk: https://www.youtube.com/watch?v=SUfRmvICnPA https://www.youtube.com/watch?v=SUfRmvICnPA
- ThouYS 7y ago
  Keenan Crane is awesome! All the work he puts into his graphics. High Quality stuff!
mlevental 7y ago
this is a very good book. it covers an interesting topic in a readable way with a lot of attention to exposition and intuition (rather than theorem->lemme->proof style). there are tons of good (instructive) diagrams, which is important for developing geometrical intuition and the sections are in "bite-sized" chunks. recommend++
electricslpnsld 7y ago
How does this help AI and machine learning?
- jefft255 7y ago
  I think this is more useful for 3D graphics and 3D reconstruction.
- bigred100 7y ago
  If you care about going deep under the surface I would think that the underlying optimization problems have many ties to DG. Not sure about the OPs pdf specifically
- whoevercares 7y ago
  In some sense DG is the foundation of all modern AI/ML/DL approach. The bar is just too high for normal people
  - mlevental 7y ago
    >In some sense DG is the foundation of all modern AI/ML/DL approach. in what sense? i love when people say pretentious things like this to sound authoritative. just because you take derivatives doesn't mean it's calculus. DG is not calculus - DG is calculus in spaces aren't globally flat but are locally flat. very different. >The bar is just too high for normal people in most schools that have DG classes they're junior level. certainly this class is a junior level class http://brickisland.net/DDGSpring2019/grading-policy/ http://brickisland.net/DDGSpring2019/grading-policy/ (no i didn't attend CMU or any similar tier school so i'm not speaking from a place of dunning-Kruger)
    - fspeech 7y ago
      Per Nash embedding https://en.m.wikipedia.org/wiki/Nash_embedding_theorem https://en.m.wikipedia.org/wiki/Nash_embedding_theorem DG actually is multivariate calculus. However DG can provide an intrinsic point of view of curved spaces without explicit reference to such an embedding. It would indeed be interesting to see a coherent description of ML in a DG framework.
      - mlevental 7y ago
        lol so backwards. i can put a fish in a fish tank in my living room it doesn't make it a mammal. >It would indeed be interesting to see a coherent description of ML in a DG framework. there is no need for such a thing - you don't need the machinery of connections, bundles, christoffel symbols, whatever else in order to take derivatives. you use those tools to be able to take derivatives in places where you can't do freshman calculus, not the other way around (bring those tools to places where you do do freshman calculus). it makes no sense. it's like reasoning that because wiles used algebraic geometry to resolve fermat's last theorem that solving quadratic equations is really about algebraic geometry.
auggierose 7y ago
Very interesting. I've been doing a lot of programming work in 3D computational geometry lately, and spent a lot of time learning/relearning stuff about differential geometry, particularly when applied to discrete meshes. From its title this sounds like a great book to read for people doing computational geometry work.
- auggierose 7y ago
  This book is also full of good stuff for practical computational geometry: https://www.amazon.co.uk/Guide-Computational-Geometry-Processing-Foundations/dp/1447140745 https://www.amazon.co.uk/Guide-Computational-Geometry-Proces...
memyselfando 7y ago
If somebody wants to discuss something about it, I am happy to hear about it. (Not that I am involved in some way. But I read it once, understood most to a certain depth, and I am always interested in how people use it.)
epr 7y ago
I was looking for exactly this only hours ago, and did not know exactly how to phrase it in my google search. Such a bizarre coincidence. From page 8: "The manifold assumption is powerful because it lets us translate many of the things we know how to do in flat Euclidean spaces (e.g., work with vectors, differentiate, integrate, etc.) to more interesting curved spaces." To be clear, it's not that I have worked with this in the past and merely forgot or something like that. I was thinking about linear transformations and essentially had the idea of taking that power to curved spaces and had no clue what would get me there or if that was even possible. Thank you for posting this. You saved me a lot of trouble.
- Scene_Cast2 7y ago
  I keep finding that Google keeps getting worse at these types of queries. I wonder what kind of metrics would incentivize Google to be better at finding these. Here's another example - https://hackaday.com/2018/12/22/clever-wedges-that-will-increase-your-pcb-assembly-yield/ https://hackaday.com/2018/12/22/clever-wedges-that-will-incr... Try to find this article without filtering for hackaday domain and not using the exact title. tl;dr of article - these are triangle / wedge shaped stencil holes for SMD surface mount soldering on square / rectangular pads.
  - kazinator 7y ago
    > I wonder what kind of metrics would incentivize Google to be better at finding these. Collection of personal information that can be monetized, and ad clicking. Everything about the Google search is easily understandable in terms of these fundamentals.
raxxorrax 7y ago
Could this be used to make light rendering on n-gons to not look like crap?
raymondh 7y ago
Learning a new topic also entails learning its terminology. As a newbie to the subject, I'm amused by chapter headings like "Abstract Simplicial Complex" that seem like an oxymoron :-)
- earthicus 7y ago
  FYI the word 'complex' in mathematics is often used similar to it's usage as an English noun - "a whole made up of interrelated parts", e.g. a building complex, apartment complex, military-industrial complex. A 'simplicial complex' is then, informally, "a whole made up of interrelated simplexes".
- jacobolus 7y ago
  A simplex is a point, line segment, triangle, tetrahedron, or higher-dimensional analog. A simplicial complex is a bunch of simplices stuck together (adjacent simplices might share a lower-dimensional simplex as a common boundary). https://en.wikipedia.org/wiki/Simplicial_complex https://en.wikipedia.org/wiki/Simplicial_complex I’m not convinced “abstract” is a good word here, but what they mean is that it doesn’t have any metrical/geometric relationships beyond the graph structure.
enriquto 7y ago
Notice that this subject has an almost total overlap with what is called "graph signal processing", yet the terminology sounds completely different.
- mehrdadn 7y ago
  Wow. I just Googled and found a graph Fourier Transform (GFT). Amazing. https://arxiv.org/pdf/1712.00468.pdf https://arxiv.org/pdf/1712.00468.pdf
  - adamnemecek 7y ago
    Fourier is gonna be big for representation discovery in reinforcement learning.
- joe_the_user 7y ago
  Yes, This sort of thing intrigues me tremendously and I'm going over the text. At the same time, I always have a certain "what could you really get" feeling about systems that begin with machinery from objects with lots of structure (differentiable manifolds) and generalize and generalize until it is dealing a structure that seems utterly arbitrary. I mean, locally, "almost everywhere" (and similar caveats), the characteristics of a point of a differentiable manifold determine "nearly everything" about the points in its neighborhood. Oppositely, one node of graph no necessary relation to the next node. So what exactly do we get from our complex machinery? Are the theorem ultimately more about "summation processes on graphs" than graphs?
  - adamnemecek 7y ago
    I think it's about operators and adjoints. http://www.reproducibility.org/RSF/book/bei/conj/paper_html/index.html http://www.reproducibility.org/RSF/book/bei/conj/paper_html/...
raphaelrk 7y ago
Related course: 6.838 Shape Analysis at MIT http://groups.csail.mit.edu/gdpgroup/6838_spring_2019.html http://groups.csail.mit.edu/gdpgroup/6838_spring_2019.html Roughly about measuring properties like curvature and distance on shapes, and similarity between shapes. Very cool class.
jacobolus 7y ago
Crane’s recent work on the “Heat Method” is awesome, http://cs.cmu.edu/~kmcrane/Projects/VectorHeatMethod/ http://cs.cmu.edu/~kmcrane/Projects/VectorHeatMethod/ I highly recommend the hour-long lecture linked there.
deleted 7y ago
[deleted]
soVeryTired 7y ago
Can anyone give a quick summary of what you can do with this theory? I know a bit about geometry (up to the basics of the De Rahm cohomology and the Riemann curvature tensor, say). What does the discrete version get you? What are its applications to CS?
- amelius 7y ago
  One important application is solving differential equations on a grid. Not sure if it is covered here, though.
  - dtornabene 7y ago
    ...go on
  - shoo 7y ago
    in a past life i learned a little about PDE and the theory justifying why finite element methods work to approximate solutions. i never explicitly ran into anything about discrete differential geometry, but that doesn't mean it wasn't there all along, lurking beneath (or perhaps above?) my level of understanding. some reading: Evans -- Partial Differential Equations, Wendland -- Scattered Data Approximation, Wahba -- Spline models for observational data .
- delhanty 7y ago
  Applications of discrete curvature have been around a while, for example this PDF [0] from 2003, so maybe this paper provides theoretical context for existing work. [0] "Anisotropic Polygonal Remeshing" Pierre Alliez, David Cohen-Steiner, Olivier Devillers, Bruno Lévy, Mathieu Desbrun https://hal.inria.fr/inria-00071778/document https://hal.inria.fr/inria-00071778/document
- mistrial9 7y ago
  it seems useful to distinguish between applying transforms to meshes, or not. There seems to be a lot of interest in using math to improve meshes for surface analysis, but there are also many problems that are not like that, hence identify up-front...
cevi 7y ago
I took the class these notes were based on at Caltech with Peter Schröder - it was one of the most interesting courses I ever took. Glad to see these notes show up on HN.
DreamScatter 7y ago
Please check out my differential geometry package package> https://github.com/chakravala/Grassmann.jl https://github.com/chakravala/Grassmann.jl YouTube> https://www.youtube.com/watch?v=eQjDN0JQ6-s https://www.youtube.com/watch?v=eQjDN0JQ6-s PDF doc> https://www.dropbox.com/sh/tphh6anw0qwija4/AAACiaXig5djrLVAKLPFmGV-a/Geometric-Algebra?preview=grassmann-juliacon-2019.pdf https://www.dropbox.com/sh/tphh6anw0qwija4/AAACiaXig5djrLVAK...

230 points by adamnemecek 7y ago

You should really check out the author's research https://www.cs.cmu.edu/~kmcrane/ https://www.cs.cmu.edu/~kmcrane/ There's also a repo for this https://github.com/dgpdec/course https://github.com/dgpdec/course

amelius 7y ago
And check out this short video he made to promote a talk: https://www.youtube.com/watch?v=SUfRmvICnPA https://www.youtube.com/watch?v=SUfRmvICnPA
ThouYS 7y ago
Keenan Crane is awesome! All the work he puts into his graphics. High Quality stuff!

mlevental 7y ago

this is a very good book. it covers an interesting topic in a readable way with a lot of attention to exposition and intuition (rather than theorem->lemme->proof style). there are tons of good (instructive) diagrams, which is important for developing geometrical intuition and the sections are in "bite-sized" chunks. recommend++

electricslpnsld 7y ago

How does this help AI and machine learning?

jefft255 7y ago
I think this is more useful for 3D graphics and 3D reconstruction.
bigred100 7y ago
If you care about going deep under the surface I would think that the underlying optimization problems have many ties to DG. Not sure about the OPs pdf specifically
whoevercares 7y ago
In some sense DG is the foundation of all modern AI/ML/DL approach. The bar is just too high for normal people
- mlevental 7y ago
  >In some sense DG is the foundation of all modern AI/ML/DL approach. in what sense? i love when people say pretentious things like this to sound authoritative. just because you take derivatives doesn't mean it's calculus. DG is not calculus - DG is calculus in spaces aren't globally flat but are locally flat. very different. >The bar is just too high for normal people in most schools that have DG classes they're junior level. certainly this class is a junior level class http://brickisland.net/DDGSpring2019/grading-policy/ http://brickisland.net/DDGSpring2019/grading-policy/ (no i didn't attend CMU or any similar tier school so i'm not speaking from a place of dunning-Kruger)
  - fspeech 7y ago
    Per Nash embedding https://en.m.wikipedia.org/wiki/Nash_embedding_theorem https://en.m.wikipedia.org/wiki/Nash_embedding_theorem DG actually is multivariate calculus. However DG can provide an intrinsic point of view of curved spaces without explicit reference to such an embedding. It would indeed be interesting to see a coherent description of ML in a DG framework.
    - mlevental 7y ago
      lol so backwards. i can put a fish in a fish tank in my living room it doesn't make it a mammal. >It would indeed be interesting to see a coherent description of ML in a DG framework. there is no need for such a thing - you don't need the machinery of connections, bundles, christoffel symbols, whatever else in order to take derivatives. you use those tools to be able to take derivatives in places where you can't do freshman calculus, not the other way around (bring those tools to places where you do do freshman calculus). it makes no sense. it's like reasoning that because wiles used algebraic geometry to resolve fermat's last theorem that solving quadratic equations is really about algebraic geometry.

auggierose 7y ago

Very interesting. I've been doing a lot of programming work in 3D computational geometry lately, and spent a lot of time learning/relearning stuff about differential geometry, particularly when applied to discrete meshes. From its title this sounds like a great book to read for people doing computational geometry work.

auggierose 7y ago
This book is also full of good stuff for practical computational geometry: https://www.amazon.co.uk/Guide-Computational-Geometry-Processing-Foundations/dp/1447140745 https://www.amazon.co.uk/Guide-Computational-Geometry-Proces...

memyselfando 7y ago

If somebody wants to discuss something about it, I am happy to hear about it. (Not that I am involved in some way. But I read it once, understood most to a certain depth, and I am always interested in how people use it.)

epr 7y ago

I was looking for exactly this only hours ago, and did not know exactly how to phrase it in my google search. Such a bizarre coincidence. From page 8: "The manifold assumption is powerful because it lets us translate many of the things we know how to do in flat Euclidean spaces (e.g., work with vectors, differentiate, integrate, etc.) to more interesting curved spaces." To be clear, it's not that I have worked with this in the past and merely forgot or something like that. I was thinking about linear transformations and essentially had the idea of taking that power to curved spaces and had no clue what would get me there or if that was even possible. Thank you for posting this. You saved me a lot of trouble.

Scene_Cast2 7y ago
I keep finding that Google keeps getting worse at these types of queries. I wonder what kind of metrics would incentivize Google to be better at finding these. Here's another example - https://hackaday.com/2018/12/22/clever-wedges-that-will-increase-your-pcb-assembly-yield/ https://hackaday.com/2018/12/22/clever-wedges-that-will-incr... Try to find this article without filtering for hackaday domain and not using the exact title. tl;dr of article - these are triangle / wedge shaped stencil holes for SMD surface mount soldering on square / rectangular pads.
- kazinator 7y ago
  > I wonder what kind of metrics would incentivize Google to be better at finding these. Collection of personal information that can be monetized, and ad clicking. Everything about the Google search is easily understandable in terms of these fundamentals.

raxxorrax 7y ago

Could this be used to make light rendering on n-gons to not look like crap?

raymondh 7y ago

Learning a new topic also entails learning its terminology. As a newbie to the subject, I'm amused by chapter headings like "Abstract Simplicial Complex" that seem like an oxymoron :-)

earthicus 7y ago
FYI the word 'complex' in mathematics is often used similar to it's usage as an English noun - "a whole made up of interrelated parts", e.g. a building complex, apartment complex, military-industrial complex. A 'simplicial complex' is then, informally, "a whole made up of interrelated simplexes".
jacobolus 7y ago
A simplex is a point, line segment, triangle, tetrahedron, or higher-dimensional analog. A simplicial complex is a bunch of simplices stuck together (adjacent simplices might share a lower-dimensional simplex as a common boundary). https://en.wikipedia.org/wiki/Simplicial_complex https://en.wikipedia.org/wiki/Simplicial_complex I’m not convinced “abstract” is a good word here, but what they mean is that it doesn’t have any metrical/geometric relationships beyond the graph structure.

enriquto 7y ago

Notice that this subject has an almost total overlap with what is called "graph signal processing", yet the terminology sounds completely different.

mehrdadn 7y ago
Wow. I just Googled and found a graph Fourier Transform (GFT). Amazing. https://arxiv.org/pdf/1712.00468.pdf https://arxiv.org/pdf/1712.00468.pdf
- adamnemecek 7y ago
  Fourier is gonna be big for representation discovery in reinforcement learning.
joe_the_user 7y ago
Yes, This sort of thing intrigues me tremendously and I'm going over the text. At the same time, I always have a certain "what could you really get" feeling about systems that begin with machinery from objects with lots of structure (differentiable manifolds) and generalize and generalize until it is dealing a structure that seems utterly arbitrary. I mean, locally, "almost everywhere" (and similar caveats), the characteristics of a point of a differentiable manifold determine "nearly everything" about the points in its neighborhood. Oppositely, one node of graph no necessary relation to the next node. So what exactly do we get from our complex machinery? Are the theorem ultimately more about "summation processes on graphs" than graphs?
- adamnemecek 7y ago
  I think it's about operators and adjoints. http://www.reproducibility.org/RSF/book/bei/conj/paper_html/index.html http://www.reproducibility.org/RSF/book/bei/conj/paper_html/...

raphaelrk 7y ago

Related course: 6.838 Shape Analysis at MIT http://groups.csail.mit.edu/gdpgroup/6838_spring_2019.html http://groups.csail.mit.edu/gdpgroup/6838_spring_2019.html Roughly about measuring properties like curvature and distance on shapes, and similarity between shapes. Very cool class.

jacobolus 7y ago

Crane’s recent work on the “Heat Method” is awesome, http://cs.cmu.edu/~kmcrane/Projects/VectorHeatMethod/ http://cs.cmu.edu/~kmcrane/Projects/VectorHeatMethod/ I highly recommend the hour-long lecture linked there.

deleted 7y ago

[deleted]

soVeryTired 7y ago

Can anyone give a quick summary of what you can do with this theory? I know a bit about geometry (up to the basics of the De Rahm cohomology and the Riemann curvature tensor, say). What does the discrete version get you? What are its applications to CS?

amelius 7y ago
One important application is solving differential equations on a grid. Not sure if it is covered here, though.
- dtornabene 7y ago
  ...go on
- shoo 7y ago
  in a past life i learned a little about PDE and the theory justifying why finite element methods work to approximate solutions. i never explicitly ran into anything about discrete differential geometry, but that doesn't mean it wasn't there all along, lurking beneath (or perhaps above?) my level of understanding. some reading: Evans -- Partial Differential Equations, Wendland -- Scattered Data Approximation, Wahba -- Spline models for observational data .
delhanty 7y ago
Applications of discrete curvature have been around a while, for example this PDF [0] from 2003, so maybe this paper provides theoretical context for existing work. [0] "Anisotropic Polygonal Remeshing" Pierre Alliez, David Cohen-Steiner, Olivier Devillers, Bruno Lévy, Mathieu Desbrun https://hal.inria.fr/inria-00071778/document https://hal.inria.fr/inria-00071778/document
mistrial9 7y ago
it seems useful to distinguish between applying transforms to meshes, or not. There seems to be a lot of interest in using math to improve meshes for surface analysis, but there are also many problems that are not like that, hence identify up-front...

cevi 7y ago

I took the class these notes were based on at Caltech with Peter Schröder - it was one of the most interesting courses I ever took. Glad to see these notes show up on HN.

DreamScatter 7y ago

Please check out my differential geometry package package> https://github.com/chakravala/Grassmann.jl https://github.com/chakravala/Grassmann.jl YouTube> https://www.youtube.com/watch?v=eQjDN0JQ6-s https://www.youtube.com/watch?v=eQjDN0JQ6-s PDF doc> https://www.dropbox.com/sh/tphh6anw0qwija4/AAACiaXig5djrLVAKLPFmGV-a/Geometric-Algebra?preview=grassmann-juliacon-2019.pdf https://www.dropbox.com/sh/tphh6anw0qwija4/AAACiaXig5djrLVAK...