A complex curved surface was divided into several patches and trajectory planning for each patch was performed. The trajectory integration problem can be modeled as the tool trajectory optimal integration problem (TTOI), and an ant colony algorithm was advanced to solve the TTOI. Simulations were carried out on the automotive body parts and the results validated the proposed algorithm. And a workpiece with a complex curved surface was used to test the scheme. The results of the experiments showed that the trajectory optimization algorithm achieved satisfactory performance, and the time of robotic spray painting saved 20%.