Introduction to Shape Analysis and Applied Geometry in 6838 Course

hello everybody and welcome to the first lecture of 6838 my name is justin solomon and i'll be

your instructor for this semester in our course which is covering topics in shape analysis

to give a tiny amount of background again there's my email you can also take a look at some

of the research that my students are doing by taking a look at this website gdp.seasale.mit.edu

our ta this semester david palmer is also a student in my research group so he's a very experienced member of the

geometry processing research community uh in today's video i'm not going to cover

administrative details of for our course you know how grading is going to be done and so on but we'll do that separately

in a zoom call there's no reason to put that on youtube so for now what i'm going to tell you about

is essentially what we're going to be covering for this semester in 6838 my goal here is to get you excited about

our course and to give you some idea of the kind of material that we'll be covering by the

end of the semester so just for a little bit of background the prerequisites that we're going to

need for this course are pretty loose i'm not going to check everybody's transcripts and make sure that they fit

into 6838 uh the main two things that we need here are pretty strong coding skill

our assignments are probably going to be put out in julia python or matlab although your final project i don't

really care you can do whatever programming language you prefer but the main skill that you're going to

need in 6838 is math fluency in linear algebra and multi-variable calculus

now in this course we're going to use a lot of ideas from differential geometry but we're not going to require it as

background in fact i think one of the really fun ways to learn differential geometry is in these

kinds of applied problems that we're going to study there are many different other areas

that are not required but won't hurt as some background many of you are students that took my

computer graphics class last semester that will give you some idea of the basic types of mathematics that we do in

6838 as well as some of the applications that are really critical in this research

field many students in our class come from the math department if you take in

differential geometry or numerical analysis that's great but again it's not required

and then finally machine learning especially in the last part of our course is going to be relevant to

motivate some of the applications and also gives you a lot of opportunity to

practice matrix calculus computing lots of gradients of functions and so on the basic philosophy here you know the

graduate classes that we teach at mit are faculty that are really excited about their research field and we want

to introduce it to all of you so david and i want you to take this course

now what that means you know our assignments are designed to be interesting um we're putting out new

assignments this year especially in our new online environment and some of them

might be particularly challenging um and so my hope is that you won't get discouraged but rather we'll reach out

to your instructors for help right we're trying to make this an interactive

experience that covers lots of interesting material in the applied geometry regime

so without further ado let's get started and give you a bit of a summary of the high-level philosophies of the

course and and essentially some of the content that we're going to be covering so we can think of this course as one

that's covering topics in geometric data analysis now this is a purposefully vague phrase and

i think that you can read it in two different ways which is what i've drawn on the slide here on the one hand we can

think of geometric data analysis as algorithms for analyzing geometric data

right so oftentimes in computer science we encounter shapes in many of the applications that we care about

right for example in three-dimensional computer vision computer graphics autonomous driving

robotics all of these are different research fields where basically we're trying to navigate

understand and manipulate a three-dimensional world on the other hand we're also going to

study geometric approaches to data analysis that is data analysis using geometric

techniques so many techniques in high-dimensional machine learning can be understood

as sort of thinking of a data set or probability distribution as some geometric object that's embedded in a

high dimensional space and essentially what we're going to find is that items 1 and 2

on our list here have a lot of commonalities so one of the really fun things that we can do

in this course is derive a mathematical idea or geometric construction and then show you guys how it's relevant

both to geometric data like autonomous driving robotics applications

as well as more abstract applications in high dimensional geometry and we're gonna go back and forth between the two

throughout 6838 so i thought for the rest of today's lecture what i would do is give you all

a very very high level picture of what the advanced geometry world looks like from my perspective as well

as some of the computational toolbox that we're going to be using in this course

so that's our basic outline here is to give you a sweeping and extremely biased toward my perspective uh overview of

applied geometry we'll start with some of the theoretical toolbox that are available to us from our colleagues in

the math department we'll talk about some of the computational toolbox like the

algorithms that we tend to use in this research field and we'll conclude with some of

the application areas that are particularly exciting and useful in this domain

now today's lecture is mostly a picture book i'm just going to show you some really cool

ideas and pictures from geometry and then starting in our next lecture we're going to dive right into the

mathematical content so today's lecture will be pretty approachable the next one

may scare you away but i hope not i hope that everybody sticks with it so let's get started here and talk about

the theoretical toolbox in geometry now probably most people that take three 6838 already have taken a geometry

course in their life probably in high school maybe your first or second year

and usually a high school geometry course covers what we would call euclidean geometry right and in a

euclidean geometry course we're studying you know euclid's elements right euclid was a pretty famous uh geometry

researcher from uh you know a few millennia centuries something to go

and euclidean geometry is mostly an excuse to teach high school math students how to write proofs

and so the actual shapes that we see in euclidean geometry are pretty darn straightforward right if

you remember you spent a lot of time worrying about drawing circles and straight lines line segments and

triangles and that's basically it right and this sort of beautiful and mildly terrifying

thing about euclid's elements is that just with these basic

shapes you know like right triangles and circles we already can really struggle and prove

really difficult non-trivial things about geometry um using a nice formal system of calculus

or not even calculus really just just you know compass straight edge and simple geometric constructions

uh and so on but here's the thing in computer science we're not worried about a compensated

straight edge we're worried about data that looks like this right so this is a point cloud that was

collected i believe using a lidar scanner of a three-dimensional scene you can see

that there's complicated structure there's noise it's incomplete and most importantly from euclid's

perspective the uh the shapes here are not triangles right there's all kinds of crazy things going on

in this scene and in fact all of the pictures that we're drawing so far are two and three dimensional but the

reality is that oftentimes our geometry is totally abstract

like here's the famous mnist digit uh data set right these are a bunch of handwritten digits on

people's computer um and these are some low dimensional subset of a very high dimensional space

of possible images that you could draw on the computer and so the questions that we're going to

be answering are how do these basic ideas of euclidean geometry apply to these much more high

dimensional noisy incomplete challenging problems now if we

trace forward a little bit in the history of mathematics whereas we started with euclidean geometry and

these sort of basic elements um pretty soon mathematicians realized that that wasn't

sufficient and so we started developing more and more complicated theories of geometry

that could handle more and more complicated shapes so one of the big major developments in

geometry moving forward from euclidean geometry jumping forward many centuries i believe

is the development of an area called differential geometry now differential geometry is all about

how to apply tools from calculus to geometry problems and i believe historically it actually

appeared pretty shortly after the development of calculus is one of the the major applications in the

mathematical domain incidentally here on the slide i'm showing you pictures from a really

famous series of uh i guess five textbooks in differential geometry by spivak this is a

comprehensive introduction to differential geometry i certainly have never read all five of these books but

i encourage all of you guys to they're really beautiful textbooks um both mathematically and actually the covers

are really funny they're like from the 60s or 70s and they have this whole series of

cartoons of the plot ending with a marriage i believe of gauss and binet anyway it's a fun read and in fact when

you read the introduction to these textbooks spivak talks about how he set out to

write the great american differential geometry text and i think he succeeded here

in any event differential geometry is all about the study of a particular object called a smooth

manifold and basically a manifold is differential geometry's term for shape

right so a manifold is an object like what i s i'm showing you on this slide here and

it satisfies a few properties um essentially a manifold you can think of as some space

where if i take a magnifying glass to that space i get really really close up to it

it looks like euclidean space rn right so for example if you look at this double taurus on the slide here

the double taurus is not euclidean it's not flat it's some weird curved object but if i get really really close to that

double taurus i can't see that right if i'm just an ant crawling along the surface to me it just

looks like this infinite uh space of just vast flatness and that's what a manifold is locally

but then globally these little local flat areas can be curved

ever so slightly to form an interesting object like a surface like what we see on the slide here

so in this course we're going to define what a smooth manifold is we're mostly going to be worried

about manifolds that are embedded in euclidean space so here the manifold that you see

is sitting in three-dimensional space it's a two-dimensional slice of 3d so here n uh rather k would equal

two and n would equal three there are more abstract notions of manifold where we

get rid of the requirement that it's sitting inside of some higher dimensional space

and we'll talk about that a little bit later on in this course when we talk about romanian geometry and some of the

applications in machine learning and manifold optimization but essentially this idea of a manifold was

extremely powerful and it enabled differential geometers to develop a huge toolbox of different

computations measurements about surfaces and so on whose job was to capture both locally

and globally what a geometry of a surface should be so here are some of the things that we

were able to derive in the theory of differential geometry

first of all we can compute notions of curvature now most of the shapes in euclidean

geometry are basically flat right they're like either embedded in the plane they're

straight lines and so on in differential geometry we're now worried about curved objects and we want to come up with

different measurements of bendiness for that curved object here i'm showing you two which are

specifically for two-dimensional surfaces embedded in 3d although i guess you can

get rid of the embedded part and these are called gaussian and mean curvature and we're going to go into

extreme detail in this course on how to derive gauss and mean curvature

how to manipulate them and how to approximate them computationally because they're extremely useful

for understanding how people are modeling 3d surfaces on their computers so for example people that are making 3d

models of cars in the automobile industry often use

gaussian meat curvature as ways to understand the night you know how smooth or nice the shape of a car is before you

manufacture it right so these kinds of computations happen a lot in computer-aided design

the differential geometry toolbox also gives us some way to talk about distances other than just simple

euclidean distance so uh in this course we're going to talk a lot about an idea called geodesic

distances so let's say that i'm an ant crawling along the surface of the bunny that we

see here in 3d then essentially there's two notions of distance right one of them

allows you to cut through three-dimensional space so for example uh if i were to go from the ear of the

bunny down to his back i could just do that by cutting through the white space

on my slide and drawing a straight line but if i'm an ant crawling along the surface

of the bunny i don't have that option right i have to crawl along the surface so now the ant has to start on the ear

crawl down to his head and then onto his back so that notion of distance this distance

along a curved space is called geodesic distance and it's a really critical construction

both for 3d surfaces as well as higher dimensional spaces anytime your data essentially isn't

embedded in some flat domain so we're going to talk about forward and inverse distance problems in this class

so a forward distance would be like given the 3d model of the bunny that you see on the slide here and two points

compute the distance from point a to point b constrained to move along the surface on

the other hand sometimes we have inverse problems where we're given a bunch of points and the

distances between them and our task is to reconstruct the piece of geometry

this happens a lot in data visualization where maybe i have a bunch of data points where

people tell me which ones are similar to one another and now my task is to reconstruct an

embedding of my data that represents those relationships that i put on my computer

but differential geometry actually still tells us even more than just distances in curvature

for example one of the really powerful ideas in differential geometry involves flows and vector fields so

on surfaces we can put little hairs on a surface that are tangent to the surface at every point

um so for example if i'm describing the flow of a fluid along a surface then maybe the velocity

would be a vector field then part of the theory of differential geometry

actually tells us how to understand these vector fields in their dynamics in fact there are all kinds of intricate

links between the structure of vector fields for example singular points that they

circulate around and the geometry of the underlying domain so for example

the vector fields that are possible to draw on 3d space like what you might see with

fluids sloshing around in a big bucket of water are quite different from the vector fields that you might be

able to observe on different two-dimensional surfaces for example

tracking wine as it drips down the side of a wine glass so we're going to talk about some of the

big construction in vector field on surfaces both in the smooth case as well as how to discretize it on triangle

mesh domains which is a really popular idea especially in the computer graphics

world in fact what we're going to see is that we can even come up with structure

preserving methods that can handle the theory of vector fields on a discrete domain which

is pretty exciting another big idea from the differential geometry toolbox

is the construction of partial differential equations and differential operators

so there's this really cool idea uh in an area of mathematics in differential geometry this came even

later than some of the ideas that i'm already showing you where essentially you can learn a lot

about a shape by hitting it with a hammer so if i take that bunny or this bust

that you see on the slide here and i give it a delicate tap not enough to break it but just to kind of hear the

sound that it makes when i tap essentially what i observe is a bunch of different vibration frequencies

right we all know this intuitively you know if i knock on the table that's right in front of me

um even if i'm looking away i can probably tell that it's a piece of wood maybe i know something about how thin or

thick it is and so on this basic intuition led people in differential geometry to ask

the question how much can i learn about geometry by doing physical calculation and the

really critical one here was an idea called spectral geometry which is essentially saying

what can i learn about a shape by observing its vibration patterns and vibration frequencies

in fact there was an open mathematical problem for a surprisingly long time given the solution

of the problem which is a kind of simple uh thing which was can i come up with two iso

spectral shapes meaning can i make two drum heads where if i hit those two drum heads and

i don't get to look at the drum i just get to hear the sound that it makes can i make two drums that always sound

the same but have two different shapes for a long time we didn't know the answer which is really surprising right

i mean if you think about it vibration frequencies are somehow a one-dimensional signal right it's just

like a list of of hertz um but a shape is maybe a two three-dimensional object

now the answer is unfortunately no there is or yes no no whatever um the answer is that

there do exist eyes iso spectral shapes but they're extremely rare they're hard to construct and

the idea of using differential operators essentially like the derivatives that show up and the

equations that govern the motion of vibration heat diffusion and so on can tell you a

ton about a piece of geometry so these are just a few of the really cool tools in the differential geometry

toolbox notice i haven't told you how to use them computationally but these are all of the

really big ideas that have existed in mathematics for centuries in some cases now the one that

we're looking at here turns out to be a lot more recent but particularly important in the

applied domain so if we zoom forward another 100 years or so then we

start reaching some of the even more modern theories of geometry and we're going to touch on these in this course

so for example one of the big ideas in advanced geometry is something called riemannian geometry

now here's a bit of a philosophical question take a look at the map that i'm showing you on this slide here

in some sounds this map has two different geometries associated to it right now

probably most people in 6838 would agree with me that the earth is a sphere i'm not going to hold that debate in

this course but is the figure that i'm showing you on this slide here

is that a sphere no it's a rectangle right and so there's actually two pieces of geometry that are somehow interacting

right there's the map that i'm drawing on the screen and then there's the object that the map represents that we

all understand which is the 3d sphere-like object which is the earth

so here's the question that riemann asked now here i've shown you two different

line segments uh on this map of the world and the way that i did this

is i was in powerpoint i made one of the red line segments i copy pasted it and i just dropped it somewhere else right so

one of them is in what like russia europe the other one is you know connecting south of central

america and and africa here and the question is are these two line segments identical

now one answer is yes i mean on the powerpoint slide that i'm showing you

these are identical i copy paste it to get from one to the other but if we understand this picture as a

representation of some other piece of geometry right the 3d earth

then the answer is no so essentially what riemann did his one of his one of his many big

contributions to the mathematical world is to divorce these two ideas this map is giving us some notion of connectivity

topology and so on but we can attach a different notion of distance to every point in the domain

what do i mean by that well if you look at antarctica on this map it's stretched out quite a

bit horizontally whereas maybe central america is actually

stretched out a lot less and so essentially the notions of computing angles and computing

distances depends on what point you're at in this map here and that was the big

idea of reminding geometry in fact what riemann's viewpoint here was that

just by having some local notion of being able to compute angles and distances

you can do most of the differential geometry calculations that i already gave you

so for example let's say that i wanted to sense curvature i wanted to know how bendy the earth is but i

am some tiny ant that's walking along the surface of the earth now from my perspective it's really hard

to know whether or not the world is curved in fact you know we know that for hundreds

of years people weren't so sure and why is that well as we walk around in boston we don't really sense the

curvature of the earth right we need some clever experiments in order to do that

but what riemann observed is that by doing certain differential measurements we can begin to sense things like

curvature and they only depend on local notions of computing angles distances and so on

so for example let's take a look at the three images that we see on the slide here

these are sort of prototypical examples of a domain with zero uh gauss curvature or

you know curvature tensor if you want higher dimensional stuff so that would be like a flat domain

positive curvature like a sphere and negative curvature like a saddle and let's say that i know i have a

friend who's another aunt and now i'm going to take these two ants and they're going to hold hands with one

another normally you know if i'm teaching this in classroom maybe i would make a

student uncomfortable and ask them to come join me here but if uh two ants held hands and they

start walking forward they can actually sense the curvature of the earth that's underneath them now

they'd have to probably walk a long distance because ants are pretty small but what's going to happen as

illustrated on this slide is that they'll actually get even if the two ants are moving along geodesics

they're moving in straight lines just you know following their toes they'll actually get closer to

together horizontally to one another if the earth is positively curved we'll get farther apart

if it's negatively curved so what's riemann's point here riemann's point is that

even if the only thing i know how to do is to sense the earth as a two-dimensional object that i can walk

along i can still sense things like curvature i don't actually need 3d space at all to

measure these sorts of things this is a really big idea because it actually allows us to generate

all kinds of interesting abstract geometric spaces and in fact this shows up in a lot of applications

as well so uh for example if you want a totally mind-blowing really difficult to think about uh area of

research um some people study how to put a geometric structure

on the space of geometries now this sounds like a really abstract problem but it's not so

for instance if we take a look on the right hand side here we have some animated character that's moving his

arms up and down we can think of each pose of this character

at some point in a very high dimensional space of all the possible poses for this character

and then the question is which poses are nearby and how can i get from one to the other

well that sounds an awful lot like computing geodesic distances but in order to do that we need to put a

geometry on that space now this is a successful idea in a lot of different areas

both in computer animation like what i'm showing you on the right hand side and actually one of the most popular

applications of this idea is in medical image analysis so for example let's say that i have a large

population of people that i've put into an mri or some other scanner that senses the shape

of their brain i'm not an anatomy expert so when i give these kinds of examples i'm probably

going to get it wrong and now what i want to do is understand over a large population

what are the interesting variations that i see in a particular organ you know so for

example maybe people's livers tend to get taller and smaller fatter maybe there's some bump that

tends to go in and out one thing i can do is try to put a geometry on the space of medical images

and that allows me to apply techniques like principal component analysis to do statistics on that collection of

shapes that i just uh accumulated so this really abstract idea that dates all the way back to riemann

if not earlier actually has really important practical perspective that we can apply

in different domains like medical imaging computer animation now to continue in our grab bag of

interesting modern ideas from geometry that we're going to try and explore in this class

another big one that's important in the physical simulation uh and computational engineering world

is the idea of geometric mechanics now geometric mechanics is closely linked in with lee groups

uh and other uh sort of constructions by the way i'm gonna tell you something right now

and um i need you to remember this for the rest of this course or else uh you know there's like the one

way that i'm gonna guarantee you lose points in 6838 which is that if you see this word l-i-e

this is somebody's name this is a capital l and it is pronounced l-e-e

this is a lee group if i hear any of you guys in my office hours calling it a lie group

it's going to be a problem that's a classic mathematical mistake all right but in any event the basic

idea of geometric mechanics and related uh disciplines is as follows so essentially take a look at the double

pendulum that i'm showing you on the slide here so remember that a double pendulum is

like two sticks that are hanging off of the ceiling like what you see on the slide and essentially

one is allowed to pivot along the top and the second one is allowed to pivot along the hinge that's attached to the

first now in the finger on the left hand side it looks like this is essentially

you know some configuration in two-dimensional space but the reality of the matter is that

the sticks that are tied together cannot change length and so in geometric mechanics the

question that we ask is should we really understand this as like the two-dimensional plane with some

pendulum swinging back and forth when i've added constraints to my system and in fact there are other perspectives

that are equally valuable so for example on the right hand side i show you the configuration space

of this two-dimensional system which is essentially the product of two circles right the the top piece of the pendulum

can pivot about the point um where it's attached to the ceiling

and the second one theta two here can pivot about the first right so there's basically two different

angles between 0 and 360 degrees that govern the dynamics of this physical system

so in geometric mechanics rather than understanding the pendulum as swinging around

in 2d space like what i'm showing you on this slide maybe instead i view it as a path on a

torus like what i'm showing you on the right which is basically the product of the

angles theta 1 and theta 2 measured around so you can take the

equations of motion right like f equals m a and we can try to understand what those

look like as dynamical systems on this tourist object and these trace out all kinds of really

cool interesting geometric figures and they have the added benefit that when i simulate this physical system

i'm sort of operating the natural space of parameters i don't have to worry about

the length of the pendulum accidentally getting too long or something which can happen if i don't discretize

it this way now lead groups are essentially groups in the algebraic sense

with a geometric structure attached so for example here essentially there's two groups both of

which are circles right the circle being theta one and another circle being theta two

so this is simultaneously a manifold like a circle but it's also a group like an angle with

a plus sign operator and so the three of lead groups essentially says that you can combine

algebra and geometry and come with all kinds of interesting ideas many of which interact with these

geometric mechanics setups which tend to be discretized in terms of like angles and

rotations translations things with group structure now zooming back even further in

the theory of geometry maybe we no longer assume that we have calculus at our disposal

there are a lot of spaces that have distances attached to them but they're too noisy or singular

to allow us to compute derivatives or maybe they're composed of a bunch of discrete objects

in that case we have to make do with a much weaker theory called metric geometry

which is essentially all the geometry that we can do when the only objects we have

access to are some space like a set of points and the distances between them now

metric geometry is really critical for problems like embedding where maybe

i can sense these kinds of distance relationships but i want to put them into a space to visualize

there are also some algorithms out there that only operate on distances and it's actually enough to just have a

metric structure so for example in a lot of retrieval problems like i have a big collection of

weird objects and all i can do is measure which ones are similar and which ones are not

then i can still try to solve problems like retrieval which says given a query give me other objects that

are nearby so for example if i think of the set of web pages on the internet

as some geometric space or maybe it's actually not unreasonable to measure some notion of distance or

similarity between two web pages then i can just use that distance metric structure even if it's not euclidean or

even riemannian to solve problems like find me the closest 10 web pages to the one that i

just read so these kinds of ideas appear not only in applied geometry but also in areas

like natural language processing where the kind of geometric structures we have are extremely weak

and only approximate in this class basically because it's close to my heart we'll touch upon a theory called optimal

transport this is relevant especially to machine learning domain and some in computer

graphics the theory of optimal transport which happens to be central to my own research

personally is all about how you take geometry on a space and lift it

to a geometry on the space of probability measures so what we're going to see in optimal

transport is that essentially it allows us to do some of the geometric computations that

we're going to derive in the first half of the class even when our data is noisy or uncertain

right so in the noisy and uncertain case maybe now we think of our shapes as probability

distributions we can't sense them exactly but we're going to see that we can still

compute things like distances and even curvature just given that fuzzy notion this is an

emerging area of research in geometry and one that changes every single year and then finally if we want to put the

weakest possible structure on a geometric domain maybe the only thing that we know is what is connected

to what so that is something called topology right so in general mathematics there's

geometry topology right geometry means i can you know measure distances bending stretching and

so on whereas in topology all i know is connectivity

now there's an entire research domain called computational topology which essentially takes different

topological constructions and applies them to data that we see in the real

world right so this is sometimes called tda or topological data analysis now we may only touch upon

topological constructions in this course but we're going to see that they appear especially when we talk about vector

fields essentially as some global way to understand some space whether it's a

shape a particular vector field and so on and unlike our geometric constructions

topological measurements are going to be ones that are very very stable right if i take my

geometry and i just bend it and stretch it and don't do anything totally drastic like cutting it the

topology of the domain remains the same there are all kinds of beautiful open challenges in this domain

as well for example if i'm given a bunch of samples from some topological domain but

i forgot the topology can i come up with an algorithm that with high probability or

reliably or whatever can actually try to reconstruct or sense the topological structure underneath

uh this gives rise to a lot of the ideas in tda persistent homology and so on which we

may touch upon toward the end of this course kind of depending on timing and where

the student interest is so essentially in it looks like about 33 minutes here we have some very high

level summary of the theory of geometry and hopefully i've managed to convince you

guys that this isn't just like a mathematical exercise that's intended to

you know torture students in the math department it's actually really important for the

applied domain and essentially our job in this course is first to introduce these ideas we're

only going to do that intuitively i'm not going to do a ton of theorems and proofs

but then also to show how they can be translated into discretizations and algorithms

so that's the next step of our discussion for today is what computational toolbox that we have at

our disposal to take these high-level ideas from theoretical geometry

and make them work in the applied domain now in the applied world there's so many different

notions of what it means to be a shape in computer graphics we care about triangle meshes triangle soups

subdivision surfaces cad surfaces splines and so on in other areas of computer science maybe

we have graphs or networks um in autonomous driving robotics oftentimes you have point clouds like

just big piles of points sampled from some piece of geometry so in this course we're going to talk about

many different applications that have many different notions of what it means to be a shape

so this term shape here is going to be extremely vague it's essentially almost any object with some notion

of proximity or distance or curvature bendiness holonomia and so on uh and and we're

gonna see that in many different domains so to give you some sense of why this is so challenging

and why this is interesting from an applied perspective instead of just like a footnote let's take a look at this

very simple surface on the slide here now essentially what i'm trying to introduce to you all today

is why is it so hard to even interpret a piece of geometric data so here we have an extremely simple

example of a shape that i might store on a computer here we took a dolphin and we're

representing it with a bunch of triangles those of you who took my intro graphics

class know that this is called a triangle mesh and it's going to be one of the basic objects

that we'll study a lot in 6838 and here's the basic issue that we have to contend with

all the time in this course when i look at this dolphin i can interpret it two different ways

now if i'm being a nitpicky mathematician when i look at this dolphin

what is this thing well it's just a big pile of triangles but that actually already implies a

bunch of information in particular well triangles are flat right so what is this object in the most

basic sense from a geometric perspective well it's just a bunch of little flat domains

that are glued together along these hinge edges and meet also at vertices

on the other hand if i step back 10 feet and i look at the same surface what do i see

well probably i'm thinking of this triangle mesh not as just a bunch of flat stuff glued

together but actually some approximation of a smooth surface with curvature and this plays out in a lot of different

ways right is this an approximation of a smooth object or is it a discrete object with lots of flat

facets and what does that imply about the way that we do geometry

so for example one question that i might ask is can a triangle mesh like this dolphin that i showed you on the

previous slide have curvature now initially this seems like a goofy question i mean of course

it can like we look at the dolphin it looks it looks bent you know what

what are you asking here but if we think about the dolphin as a triangle mesh just a bunch of triangles linked

together the triangles are all flat they don't have curvature so from that perspective

maybe we actually have a singular domain we have a domain that is piecewise flat where the pieces meet together and

suddenly this infinite amount of curvature as the surface bends from one triangle

to the next on the other hand maybe i'm just thinking about curvature the wrong way i

should think of that dolphin surface as an approximation of this smooth object and

maybe it does have curvature at least approximately and in a finite way these are two different questions and

depending on who you ask in our domain they might answer this question yes or no i think we'd all say yes but then

what we have in our head of what the word curvature means might be a little bit different

so doing research or in this domain or participating in our course essentially requires you to be a jack of

all trades so when we look at a surface we simultaneously

have to split our brain into two different ways of thinking on the one hand we're going to be

thinking about smooth differential geometry and what that implies about the way that we analyze

this surface right when we step back 10 feet from this wiggly bar object that i'm showing you

on this slide it looks like a smooth object on the other hand you know putting our

foot back into the euclidean universe this is also discrete objects

composed of a bunch of different triangles that are all linked together and when we actually sit down and start

writing algorithms that process these shapes we're going to need to keep that

discrete perspective in mind and so we're going to go back and forth between discrete and smooth a lot in this course

and in fact oftentimes they get blurred together so one of my favorite research fields in geometry

is an area called discrete differential geometry now mathematicians that i talk to always

think of this name of a research discipline as somehow a contradiction in terms you know differential

sort of implies that we're working with smooth objects but then discrete seems to imply that we're working with

things like triangle meshes discrete differential geometry the basic idea here is that we should be able to

have our cake and eat it too that when we look at triangle meshes like what i show you on the slide here

we're going to come up with a theory of differential geometry for example how to define things like

geodesic distance and curvature that work on a triangle mesh domain and have many

similar theorems to what we might encounter in the smooth domain but the theorems actually hold with an

equal sign it's not an approximation that only holds as our triangles get really really

small so in order to do that we have to really really carefully define different notions that are

compatible with both discrete and smooth domains so this modern approach essentially

needs us to use two different terms and be very careful with what we mean

there's discrete geometry this would be like understanding a triangle mesh as a big

collection of triangles and doing a computation directly on the domain and there's discretized

geometry which would say our triangle mesh is not a geometric object in itself it's just some approximation of a smooth

domain that we don't have access to and both of these perspectives are really useful but they're separated in

the theory of discrete differential geometry in particular ddg is a discrete theory

paralleling the theory of differential geometry so we'll talk about that a lot in the

first sort of third of six eight three eight the basic idea here is to study an idea called structure

preservation so this is a really interesting sort of idea that arose and i would say

the last 20 years or so which is the idea that maybe rather than just approximating notions like

curvature on a triangulated domain i'm going to define a new notion of curvature on a triangulated domain

that preserves properties from the continuous one so let's see what we mean so in our next

couple lectures after we do some math preliminaries we're going to talk about curves

just you know curves in the plane and one of the basic things that we might want to measure about a curve is its

curvature now roughly if i think of a curve as some function gamma of t

then the curvature of my curve is gamma double prime of t now i have to be a little bit careful

when i define curvature because if i hit on the gas when i drive along that curve then the geometry doesn't

really change just the way that i trace it out so i have to make an additional assumption

which is that i'm traveling along my curve with constant speed if you're not familiar with these terms

that's okay we're going to cover them in about two lectures but curvature satisfies a really interesting property

which is the turning number theorem what i'm showing you on the slide here now at a high level what the turning

number theorem says is if i take the curvature of a curve and i integrate it along the entire

curve what i get is actually a topological invariant called the turning number or

the winding number that's what i'm showing you on the top of the slide here essentially the

turning number of the curve is the number of times that it loops over itself

before it meets up again so here's the theorem on the top and essentially curvature is some second

derivative quantity we're going to go through this in a lot more detail in a few lectures

but there's some interesting property of curvature namely that when i integrate this local quantity along the whole

curve i get some topological invariant like the number of times the curve twists over itself

and maybe that's the structure that we want to preserve when we discretize curvature

now here's one way to discretize curvature which is sort of intuitive and that's illustrated on the bottom

part of our slide here where essentially what we do is we say that a curvature of a curve when it's just a bunch of line

segments like what i'm showing you on the bottom it's concentrated at the vertices and

it's the turning angle of the vertex right so this is sort of

the idea that you know well if two vertices meet and they form one long line segment the curvature is zero

and as those vertices hinge the curvature increases like what i'm showing you on this slide

now you might remember a theorem from your high school geometry class if you haven't that's okay again we're

going to review this later uh which was the exterior angle theorem she essentially says if i draw a polygon in

the plane and i sum up all these exterior angles what i get is 2 pi

and in fact i can generalize it ever so slightly and get 2 pi times the number of times that a polygon

winds over itself if it's allowed to intersect well if i took a look at these two

formulas they look awfully similar right the two blue boxes here are essentially very similar properties

so one thing i might do is to find the curvature of a curve on the discrete domain

here just a bunch of line segments as some quantity that is sitting on the vertices

and is the turning angle like the angle between uh the these two uh line segments i

guess uh subtracted from 180 degrees and then there's actually a nice notion

of structure preservation namely i chose a notion of curvature of my discrete curve

that satisfies the same property that the turning angle theorem satisfies in the smooth case now what

have i not done i have not shown you that this alpha measure of curvature on the bottom of the slide here has

anything to do with that smooth measurement namely if i take my curve and i start refining it

and refining it refining it until it's a bunch of itty-bitty line segments that this

measurement i'm showing you has anything to do with kappa on the top of the slide and

that second notion is something called convergence which is essentially am i approximating some smooth quantity

as i refine my discretization so again we have these two sort of interplaying ideas there's convergence

which is how well am i capturing the smooth theory and there's structure preservation which

is saying i want my smooth theory to hold exactly in the discrete domain and there's a

push pull between these two considerations in fact one question that you might ask

is can you have it all can you come up with a convergent theory of discrete differential geometry

that preserves a bunch of structures from the smooth case but operates on objects like triangle

meshes or sequences of line segments or what have you

unfortunately or excitingly depending on your perspective the answer is actually no and this is

super interesting and not obvious at all um so here is a well-known paper in the

geometry processing domain it's called discrete laplace operators no free lunch and essentially what they do is they go

down a long list of all of the properties of the laplace operator one object that we're going to study in this

course later on the plus operator has a lot of different properties you might know from math

class you might not i mean they include something called the maximum principle

that it's elliptic or positive definite and so on you can make a long list of all the

things that the laplace operator holds in the theory of smooth differential geometry then you can ask

can i make some construction in this case operating on a triangle mesh that satisfies analogs of all the same

properties and the answer is actually no so here in this paper it says you know

building on the smooth setting we present a set of natural properties for discrete

laplace operators for triangle of service meshes we prove an important theoretical

limitation discrete laplacians cannot satisfy all natural properties

retroactively this explains the diversity of existing discrete laplace operators now that last

little tag i think is what's so cool about this domain that if you're in engineering if you're

an engineer working with discrete geometry even if you care about some smooth

uh a bunch of smooth properties of your domain that you only have approximate access to

you have to pick and choose which properties you need to measure well

and you can't necessarily measure them all well and what that means for example for curvature is that for

every one measurement we do in the smooth theory there's a whole zoo of potential analogs

in the discrete theory and it's not clear which one is the correct analog it

depends on your application which is super interesting it essentially gives us a lot of freedom

to pick and choose the properties we need for our discrete calculation because we can't have them

on luckily when we're doing this kind of modeling there's a huge toolbox of

different algorithms numerical measurements approximations that we can draw from

and so in this course essentially by exploring these ideas how we can do geometric measurements

on discrete or discretized domains we're going to make use of all kinds of different sledgehammers

from numerical analysis computational geometry and other disciplines

one of the big ones that's going to come into play a lot in this course is numerical partial differential

equations pde partial differential equations is not a background prerequisite for this class

so we're going to introduce all of the notions that you need as they come up during our discussion

and we're also going to talk about how we can make partial differential equations work

on a discrete domain so we'll introduce the finite element theory as well as some other theories that are

relevant specifically uh in in the geometric case algorithms that are relevant to geometry are not just

numerical pde another important one is large scale optimization

large scale optimization is a super popular problem to study in regime of machine learning but it

also shows up all over the place in computer graphics and other domains that are operating mostly on geometric

domains now one of the really interesting things and one of the reasons that i hope some

of our friends in optimization come join us for this course is that the kinds of optimization problems that we

tend to encounter in geometry are structured very differently from the kinds of ones that you

encounter in like deep learning or some other discipline algorithms like stochastic gradient

descent are no longer what's relevant to us because we really care about smooth uh

structures and those last couple bits of precision in our optimization problems and moreover oftentimes we have really

complicated constraints so on the slide here i'm showing you one prototypical example of a really yucky

optimization problem that we encounter in geometry domain this is something called surface

parametrization so here we have a 3d cow and our job is to make that cow into a carpet you know

we're going to take that cow and smash it onto the plane those of you who are familiar with

computer graphics know that the reason we might do this is to have a texture map so maybe i store

an image with the texture on the cow and then i can wrap it around the surface using this parametrized object

now if you think from an optimization perspective the problem becomes super interesting

and challenging now why is that well what are our variables here our variables are the

positions of every single vertex on this triangulated surface now even a simple triangulated

surface has thousands or millions of vertices that i have to contend with moreover i have really challenging

constraints because if any two triangles overlapping the plane the entire parametrization is

useless right because then those two triangles have to be textured the same way in my texture map

so i have like a quadratic number of constraints and a huge number of variables

so these are very different problems than like training a deep network doing stochastic gradient descent and so on

in fact some of our optimization problems are actually discrete so if you're uh interested in

computational fluid dynamics or some of the engineering applications of our domain then discrete optimization

problems become really critical so this would include things like tiling a surface with

elements that are squares or triangles this is sometimes called quadrangulation and this is a problem where the

variables are not just very large scale but some of them are integer you know like the

grid that i'm going to use to cover this particular 3d model incidentally fun fact this shape is

called a fan disc i think it's a part of a car and i have no idea what it does but all

of us in geometry use it all the time for testing our algorithms other tools that we're going to use a

lot include linear algebra in fact our next lecture in this course is going to be basically a refresher on