Due to the complex geometry of free-form surfaces, generating paint gun optimization trajectories for free-form surfaces to satisfy paint thickness requirement is still a challenge. A quadratic function of the paint deposition rate on a plane was proposed according to the experimental data, and then a mathematical model of film thickness on a free-form surface was established. Instead of widely used parametric representation of surfaces, a planar facet scheme was used to obtain the painting surfaces approximately. A multi-objective constraint optimization problem was formulated for the trajectories optimization. An optimal tool trajectory with an optimal time and film quantity deviation was generated by the weighed ideal point approach. The generated trajectory was verified by the simulation results. The results show that the developed optimal tool planning algorithm can be applied to generate optimal tool trajectories.