This paper presents a new method for convex decomposition of polyhedrons. In comparison with existing methods, the new method can improve the efficiency greatly with complexities reduced in many aspects of execution time, storage and added new vertices, and it is more advantageous in treating the polyhedrons with reflex edges in higher numbers. Its strategy is to gradually decompose a polyhedron in local operations by the occlusion relationships between facets and edges along certain orthogonal directions. In treating general polyhedrons in practice, the new method has its time and storage complexities both in O(n) approximately, and its produced new vertices are in a number not more than O(r+n), here n is the vertex number and r is the reflex edge number. By testing a large number of complex polyhedrons, it shows that, compared with the popularly used 'cutting and splitting' method, our new method can run 14-120 times faster, reduce the storage requirement to 1/2.3-1/7.4, and reduce the new points to at most 1/28, and even needs no new point in some cases. Because most convex polyhedrons decomposed by the method are tetrahedrons, the resulted convex polyhedrons by the new method are more than those by the 'cutting and splitting' method. However, if convex polyhedrons are required to be further decomposed to tetrahedrons, the new method can produce much fewer tetrahedrons, due to much fewer added vertices for decomposition by the new method. Besides, the new method can be conveniently used to treat the polyhedrons with holes, or even the non-manifold polyhedrons that contain isolated facets, edges or vertices.