It is known that we can always 3-triangulate (i.e. divide into tetrahedra) convex polyhedra but not always non-convex polyhedra. Here we discuss possibilities and properties of 3-triangulation of 2-toroids, i.e. polyhedra topologically equivalent to sphere with 2 handles, and develop the concepts of piecewise convex polyhedra and graph of connection.