It is known that we can always 3-triangulate (i.e. divide into tetrahedra with the original vertices) convex polyhedra but not always non-convex ones. Polyhedra topologically equivalent to ball with p handles, shortly p-toroids, cannot be convex. So, it is interesting to investigate possibilities and properties of their 3-triangulations. Here we study the minimal number of necessary tetrahedra for the triangulation of a 3-triangulable p-toroid. For that purpose, we developed the concept of piecewise convex polyhedron and that of its connection graph.