In this paper, based on the octree partition, bounding boxes and triangulated surface model, we developed a new virtual material removal method for machining of 3D complex surfaces. In this method a new tri-prism space partition algorithm based on octree and triangulated surface model is applied to partition the 3D complex surfaces. Traditional triangular-faced algorithm is used in 3-axis machining simulation, which is computationally expensive and memory demanding. In contrast, this paper presents a virtual material removal model using the dynamic tri-prism space decomposition algorithm (i) to represent 3D complex objects, (ii) to reduce the computation complexity, and (iii) to accelerate the model updating procedures in a graphic simulation process. Based on mathematical model of virtual material removal, the 3D model of virtual CNC machining process was developed.