5
\$\begingroup\$

I'm building a space game where it is allowed for the player to insert his own mesh to be his spaceship. The problem I'm facing is that a ship must be a Polygon Mesh. The player will then be able to place thing inside the ship to make it behave. My question is, given an arbitrary mesh (a set of vertices and triangles), how check if it is a polygon mesh (no holes, with a clear inner side)?

\$\endgroup\$
1

2 Answers 2

8
\$\begingroup\$

Alternatively - to provide an easier-to-implement and more efficient solution - one can check the mesh's Euler-Poincaré characteristic. Given the number of vertices V, number of faces F and number of edges E.

A triangle mesh is a closed 2-manifold, if and only if

V + F - E = 2.

If you store your mesh as a list of vertices and indices, V and F can simply be read out. To compute the number of edges E, one can iterate over all faces and insert the three triangle edges in a set, effectively counting unique vertex-vertex-pairs in your mesh.

Additionally, you might want to clean your mesh before-hand, removing duplicate vertices.

Note that above approach only works for fully connected meshes, as pointed out by Adrian Maire. Using sets of connected vertices, you can split the input and assess each part individually instead.

\$\endgroup\$
4
  • \$\begingroup\$ This is not true. For example consider a triangulation of a torus. This is a closed 2-manifold, yet has Euler characteristic 0. \$\endgroup\$
    – WMycroft
    Commented Feb 5, 2018 at 15:21
  • \$\begingroup\$ My solution is targeted to sanity check a Mesh to have a continuous 2-dimensional surface. That implies, that there is an inside, where @LBg for example can place his objects. At that point, you're not concerned about topological holes. The objects can very well be placed inside a torus, like the command bridge of the infamous Torus-X300-Delta spaceship! \$\endgroup\$ Commented Feb 7, 2018 at 1:03
  • \$\begingroup\$ Still not a sufficient check: a sphere aside of a torus have V+F-E=2, when in fact is not a closed solid polygon. \$\endgroup\$ Commented May 17, 2022 at 13:12
  • \$\begingroup\$ That is a good point! I somehow assumed a connected mesh. This needs to be checked explicitly though. Thanks, I'll edit the answer. \$\endgroup\$ Commented May 18, 2022 at 15:19
3
\$\begingroup\$

For triangle meshes, you should check:

(1) If it is manifold and;

(2) If all vertices are inside of a closed fan.

To check (1), just:

(1.a) iterate over edges and check if each one is incident to just 1 or 2 faces and;

(1.b) iterate over vertices and check if all incident faces form a closed or open fan.

To check (2), just:

(2.a) iterate vertices and check all incident edges to it. If all of them are incident to exact 2 faces, then this vertex pass the test. It fails otherwise.

Note that you can do (1.b) and (2.a) at the same time to optimize things.

http://www.cs.mtu.edu/~shene/COURSES/cs3621/SLIDES/Mesh.pdf

\$\endgroup\$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .