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\$
7
\$\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.

\$\endgroup\$
  • \$\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 Feb 5 '18 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\$ – Tobias Gurdan Feb 7 '18 at 1:03
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\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.