I remember seeing Euler's polyhedron formula in CS 170 with regards to planar graphs. It's interesting to see it appear here, and to learn that this formula extends beyond graphs and into 3 dimensional objects!
colinsteidtmann
Michael on the last slide asked if there are there any efficient algorithms for checking if a mesh is a manifold. Perhaps we can use Euler's polyhedron formula as a quick check, though I think it only goes one way (not iff) but correct me if I'm wrong!
colinsteidtmann
Update, Michael, the book gives a way to check:
Every edge is shared by exactly two triangles.
Every vertex has a single, complete loop of triangles around it
If a manifold has an edge then the relaxed conditions are:
Every edge is used by either one or two triangles.
Every vertex connects to a single edge-connected set of triangles.
weszhuang
I understand it probably wouldn't work as a strict check, but if we augment a manifold with an edge by adding a point for each connected set of edges to connect to it should satisfy Euler's polyhedron formula in the case of a valid manifold.
I remember seeing Euler's polyhedron formula in CS 170 with regards to planar graphs. It's interesting to see it appear here, and to learn that this formula extends beyond graphs and into 3 dimensional objects!
Michael on the last slide asked if there are there any efficient algorithms for checking if a mesh is a manifold. Perhaps we can use Euler's polyhedron formula as a quick check, though I think it only goes one way (not iff) but correct me if I'm wrong!
Update, Michael, the book gives a way to check:
If a manifold has an edge then the relaxed conditions are:
I understand it probably wouldn't work as a strict check, but if we augment a manifold with an edge by adding a point for each connected set of edges to connect to it should satisfy Euler's polyhedron formula in the case of a valid manifold.