<p>Virtual machining plays an important role in the production of complex components in various industries, in which determination of key geometric information such as cutter-workpiece engagement (CWE) and instantaneous undeformed chip thickness (IUCT) is the prerequisite for physical modeling and is profoundly affected by the geometric modeling technique. In this paper, a tri-dexel model based on array data structure is designed, where the modeling algorithm using STL models is constructed, and the analysis of the complex models is implemented via the processing of all alternative endpoints on a dexel, so as to complete the realistic modeling of fluted ball end mill with complex geometries. The cutter model and the modeling algorithm are then adapted to the GPU in order to achieve a high modeling efficiency. By using the tri-dexel models of the cutter and workpiece and the synchronous computation between CPU and GPU, the simulation of five-axis milling process is realized. By means of the Boolean subtraction operation between tri-dexel models of the cutter and workpiece, the CWE region extraction algorithm is designed, further fast calculation of IUCT is realized via cutter slicing, chip region simplification and partitioning. Finally, simulation examples of five-axis milling process with a two-flute ball end mill are given to demonstrate the effectiveness of the proposed algorithms.</p>