Point clouds data, obtained from RGB-D cameras and laser scanners, or constructed through structural from motion (SfM), are becoming increasingly popular in the field of robotics perception. To allow efficient robot interaction, we require not only the local appearance and geometry, but also a higher level understanding of the scene. Such semantic representation is also necessary for as-built Building Information Model (BIM) creation and infrastructure inspection. In this work, we present our discrete energy minimization based approach for 3D scene parsing. First, we contribute to the understanding of theoretical hardness of discrete energy minimization problems, which are also known as the MAP inference for MRF/CRFs. This theory explains why a previous scene parsing approach cannot have guaranteed optimality. Second, we propose a max-margin structural learning algorithm with performance guarantee. Finally, we demonstrate the performance and efficiency of our algorithm in the application of semantic labeling.