Trajectory optimization of spray painting robot for surfaces is studied. Because the current paint deposition rate function is too complicated, the paint deposition rate function on a plane according to the experiment data is provided. The paint thickness function for free-form surfaces is also given. A multi-objective constraint optimization problem is formulated. An optimal tool trajectory with an optimal time and film quantity deviation is generated.Experiments are performed to verify the generated trajectory. The results show that the developed optimal tool planning algorithm could be applied to generate optimal tool trajectories.