The new generation of 3D video is an international frontier research hotspot. However, the large amount of data and high complexity are core problems to be solved urgently in 3D video coding. The latest generation of video coding standard versatile video coding (VVC) adopts the quad-tree with nested multi-type tree (QTMT) partition structure, and the coding efficiency is much higher than other coding standards. However, the current research work undertaken for VVC is less for 3D video. In light of this context, we propose a fast coding unit (CU) decision algorithm based on the gray level co-occurrence matrix (GLCM) and Extra trees for the characteristics of the depth map in 3D video. In the first stage, we introduce an edge detection algorithm using GLCM to classify the CU in the depth map into smooth and complex edge blocks based on the extracted features. Subsequently, the extracted features from the CUs, classified as complex edge blocks in the first stage, are fed into the constructed Extra trees model to make a fast decision on the partition type of that CU and avoid calculating unnecessary rate-distortion cost. Experimental results show that the overall algorithm can effectively reduce the coding time by 36.27–51.98%, while the Bjøntegaard delta bit rate (BDBR) is only increased by 0.24% on average which is negligible, all reflecting the superior performance of our method. Moreover, our algorithm can effectively ensure video quality while saving much encoding time compared with other algorithms.