In this paper, a new optimization method combining coarse and fine optimization is proposed based on 3D point clouds, which provides a solution to the blank localization problem of complex surface parts. The coarse-fine optimization method proposed in this paper consists of two steps: coarse optimization and fine optimization. In coarse optimization stage, the large minimum allowance space is obtained by the unconstrained max-min criterion, so that the machinability of the blank can be judged. In fine optimization stage, the reasonable specific constraint value is determined according to the minimum margin distance, and the least square criterion with constraints is used to ensure the uniform distribution of margin. Finally, the effectiveness of the coarse-fine optimization method is verified by two examples. Results show that the proposed method can overcome the limitations of the existing methods, and obtain good optimization performance. Keywords-blank localization; coarse-fine optimization; 3D point clouds; complex surfaces