��������Voronoi�ṹ���������沼�����
��ռ��1,2, �� ��1,2, �θ���3, ������3
1.����ѧ ��ѧԺ,��� 300072
2.����ѧ ������ͼ����Ϣ�о���,��� 300072
3.����ѧ װ����������켼��������ص�ʵ����,��� 300072
ժҪ
�����������Voronoi�ṹ����滮�ļ���,������������������ʺ�����Ϊ��������Voronoi�ṹ�е��ܶȺ���,���Գɱ�������������Ϊ�㷨������׼��,�����һ���µĻ�������Voronoi�ṹ�IJ������������ñ��ķ���ʵ���˲����������Ӧ�ֲ�,��ͨ������ʵ���봫ͳ�������������˶Ա���֤,�������,���ķ��������һ�����������������ȶ��ġ���Ч�ġ�
�ؼ���: ��е���칤�����豸; ����Ӧ����; ����Voronoi�ṹ; ����������������
Sculptured surface point distribution strategy based on centroidal Voronoi tesssellation
SONG Zhan-jie1,2, ZHANG Mei1,2, HE Gai-yun3, LIU Pei-pei3
1.School of Science, Tianjin University, Tianjin 300072, China
2.Television and Image Information Institute, Tianjin University, Tianjin 300072, China
3.Tianjin Key Laboratory of Equipment Design and Manufacturing Technology, Tianjin University, Tianjin 300072, China
Abstract
Referring to the existed skill of centroidal Voronoi tessellation(CVT) generation, the curvature function of surface was studied and modified to satisfy the demand of the density function of CVT, and the convergence of cost function was regarded as the end criterion of algorithm, a new sampling method was proposed based on CVT. The adaptive distribution of the sampling points was realized by the proposed method. The method was comparatively validated with the traditional sampling methods by simulation tests. The results show that the method is better than the traditional ones, and it is stable and efficient for the common sculptured surface.
Keyword: manufacturing technology and equipment; adaptive point distribution; centroidal Voronoi tessellation; curvature of sculptured curve and surface

�����������澫��ʱ,�ܲ����ɱ���Ч�ʵ�Ӱ��,�����������������ܹ������ʹ���޵IJ����㾡����ȫ��̻������������������������еĹؼ����ܼӹ��������ܵ�Ӱ��,����������������,���ʴ�IJ�λ�������ڽϴ�ļӹ����,��͵����˲�����Ӧ���������������Ӧ�ֲ������õIJ��������о��Ȳ���������������������Ȳ���ֻ���ڲ�������Ŀ�㹻���ǰ���²��ܷ�ӳ���������ʵ����,���϶�IJ�����ή�Ͳ���Ч��;����������Žϴ������,��ĿǰΪֹû���γ�ͳһ�IJ�����׼[1];���е�Hammersley��Halton���в��������Ч�ؽ��Ͳ����ܶ�ȴ����ʵ�����������Ӧ����[2,3]�������һ����������������ڶ�ѧ�߶���������������Ӧ�ֲ�����˶��ַ����������д����Ե���Li[4]������������ʲ������Ӧ�滮����,�������[5]��������������һ��ȷ�����ʲ�ȵķ���,ʵ���˸������������µ�����Ӧ����;Zhang��[6]����������IJ�ͬ��������������ȡ,���ø�˹ӳ��õ��˿��з���,�Ӷ��滮������·��,�����˻��������ļ��ϵͳ;Elkott��[7,8]���������Ȳ������߲�������,���õõ��IJ������ع�����ļ�����״,�������ֻ������ߵ�������������������������������Ϣ�Ķ�ʧ;Hu��[9]�����һ�ֻ������ߵĵȻ�������,���ַ���Ҳ���������������Ϣ�Ķ�ʧ,���ҽ���������ijЩ�����¶ȵ�����,������һ����;Suleiman��[10]���������滮��Ϊ��������,�ڸ������ڷֱ��ҳ����������С��˹���ʺ�ƽ�����ʵĵ���ʵ�����������Ӧ����,��ȱ���Dz������ڴ�С���ʴ����ּ���,����ȫ��ؿ̻�������ṹ;����������Voronoi�ṹ���������񻮷֡�ͼ�������Ż���Դ���䡢��������ȷ����Ӧ��Խ��Խ��[11,12],��ȡ����һ���ijɹ�,��������[13]��������Voronoi�ṹ�����Ӧ��ֵ�����������ɢ,֤���˸÷��������򲼵㷽��Ŀɿ��ԡ�

��������������Voronoi�ṹ���ŵ�,��������������������ʺ����������뼸������,�����һ���µ�������������Ӧ�����㷨��

1 ����Voronoi�ṹ

����һ�������򦸪�RN,������{Vi}ki=1����Vi��Vj=��(i��j),�����Ϊ����һ���ṹ,ȡ������2ΪRN�е�ŷʽ����,���е�һ���{zi}ki=1,����zi���Ӧ��Voronoi����Ϊ

Voronoi�ṹҲ������һ���������ڵ�ֱ�߶εĴ�ֱƽ������ɵ���������ι��ɡ���֪����Ԫ������Ϊzi(xi,yi)��zj(xj,yj),���ݽ������ε�֪ʶ����䴹ֱƽ���ߵķ���Ϊ

��������V��RN��һ��������V�ϵ��ܶȺ�����,��������V������z*Ϊ

��Voronoi�����ķ���Ԫ���������غ�,�������ĽṹΪ����Voronoi�ṹ�����򦸵ijɱ���������Ϊ

��������Ļ���Ϊ���ܶȺ������µ�����Voronoi�ṹʱ,������ijɱ������ڸ��ܶȺ����´ﵽ��Сֵ,��ͼ1��ʾ��


.

ͼ1 ����Voronoi�ṹFig.1 Centroidal Voronoi tessellation
2 ��������Voronoi�ṹ���������߲������
2.1 �������߲����㷨

��֪�����������俴��һ�����������������ֲ������ȵ�����,�������ʺ�����Ϊ�����ߵ��ܶȺ���,ʽ(6)Ϊ���ʺ�������ʽ��

����ʽ(6)��֪,���ʺ�������,���䲢���⻬�������ʽ(6)���ʵ�����,ʹ����Ҫ��Χ�ڳ�Ϊ�⻬����ֵ����,��Ϊ��ʽ

�Ϳ���������������Voronoi�ṹ�����ж��ܶȺ�����Ҫ��,����[14]��֤��,��һά�����,����ijɱ�������ȫ��������,���Կ���������Ϊ�㷨���������ݡ�ʵ����������Ӧ������㷨��������:.

Step1 ������������ֲ���������Ϊ��ʼ��,������С�ڲ�����Ŀ,�Գ�ʼ��Ϊ��������ʽ(2)�����߻���Ϊ��Ӧ��Voronoi����.

Step2 ����ʽ(3)���������������ġ�

Step3 �ڸ�������������ʽ(5)�����������ߵijɱ�����,�������Ƿ�����,��������ֹͣ,������������ļ���Ϊ���������,����������Ϊ�µij�ʼ��ת��Step2��

Step4 �ڵ�����������,�ھ���������������֮��(��Ϊƽ̹������)���Ӳ�����,ֱ������ʵ��Ͳ�������������Ҫ��,��������㡣

2.2 ����ʵ��

������Ϸ���,��������˷���ʵ���Լ��������㷨�Ƿ���Ч��ȡ��������r(u)=sin(u)-u2/16,ͼ2Ϊ��5�ε���������IJ���Ч��,��ͬһ���������þ��Ȳ������㡢�Ȼ��������������ֳ��õķ����ɼ���ͬ��Ŀ�IJ��,����ͬһ�ַ������в�ֵ,ͼ3Ϊ���ַ�����ϳɵ�������ԭ���ߵĶԱȡ����Կ����������㷨�õ��IJ������ڿ̻�������״����ȳ��õķ���ȡ���˸��õ�Ч��,�ܹ���ʵ��Ӧ�������״,�ر��������ʽϴ�ĵط���ͼ4����1��ʾ�˲�ֵ������ԭ���ߵķ���ƫ�

.

ͼ2 ���ֲ�ʾ��ͼFig.2 Sampling points distribution
ͼ3 ������϶Ա�ʾ��ͼFig.3 Comparison of three interpolated curves
ͼ4 ����ƫ��Ա�ͼFig.4 Comparison of normal deviation
��1 ��ͬ������������Ա�Table 1 Comparison of fitting error by different methods
3 ��������Voronoi�ṹ��������������Ӧ�������
3.1 �������沼���㷨

���������㷨�����߲���������ֳ�������Ч��,���ǴӶ�ά������ֲ����ά���ڽ������ɵ�����⡣�ɵ�2�ڵ�����֪,�ﵽ��ֲĿ�ص�ǰ������Ҫ�ҵ����ܷ�Ӧ�������ʱ仯�ֿ�����Ϊ�ܶȺ������º���,��֮��������Voronoi�ṹ,����ɱ���������΢�ּ��ε�֪ʶ֪,����ĸ�˹���ʵľ���ֵ��ʾ���Ǹõ㼰���ڽ���ĸ�˹ӳ����ɵ�����Ƭ����*�������ԭ����Ƭ���ҵ����֮�ȡ������ҡ�0,�������ɸõ�ļ���ʱ,�����ֵ���Ǹõ�ĸ�˹���ʡ���Ӧ�������ڸõ㴦�������̶ȡ�������IJ�������ʽΪS=S(u,v),���˹���ʵı���ʽΪ

ʽ��:�Ǵ�������ĵ�λ��������

�����������������涼�м�������ѧ����ʽ,������ɢ��ʽ������-ϸ�����桢�������桢��������,������һ����STL��ʽ�������洢����,��΢�ּ����е�Gauss-Bonnet����,���Զ���ɢ����и�˹���ʵĹ���,����pi�������ΪAM��������Gauss���ʵĻ��ֱ���ʽΪ

�Ի��ֽ�����ɢ,�õ���˹���ʵ���ɢ��ʽΪ

ʽ��:KG(pi)Ϊpi�����ĸ�˹����;��j��ʾ������Ƭ�б�pipj���pipj-1�ļн�;AMΪ����pi���������,�˴�����Voronoi��������㡣

ͨ������������Voronoi�ṹ�Ĺ��̽��з���,����������IJ����������Ҫ�õ��������,����Voronoi���򲢲�����,����ػ��ֵļ�������ܴ������,ͬʱ�����ܱ�֤��˹���ʺ����Ĺ�˳�ԡ�Ϊ�����һ����,���Ľ�����ͶӰ������ɢ,ѡ��һ�����ε�ƽ��,���Ը������ű�������,��������任ʹ������ƽ����ͬһ����ռ���,������ÿһ���㶼ͶӰ������������,����������ÿһ��Ҳ������,���������ϵ�ͶӰ��,���ʵ���ԭ�����϶�Ӧ��ĸ�˹���ʾ���ֵ,����ȡΪ����,�������бߴ�������,����ʵ�����������ڵIJ���,����������ֵļ�������,�������¶�������������Voronoi�ṹ�������õ���������ĵĹ�ʽ�ͼ�������ɱ������Ĺ�ʽ:

ʽ��:��Voronoi����;��������ꡣ

ʽ(12)Ϊ�������ڵijɱ�����,������[12]��֪,�ڶ�ά�����,�ɱ������Ǿֲ�������,�����Խ�����Ϊ�ж��㷨������׼��������ı߽��������������߲�����㷨,���������������IJ���,�㷨����ͼ��ͼ5��ʾ��

ͼ5 �����㷨����ͼFig.5 Flow chart of proposed algorithm
3.2 ����ʵ��

������Ϸ���,��������˷���ʵ���Լ����㷨����Ч��,ȡ��������,s=sin(u)+sin(v),u,v��[0,1],�ٶ�������Ϊ80��,ͼ6Ϊ����CVT��������������������������Ӧ�ֲ���ʾ��ͼ,����������ɱ�������432.5������123.2,�ɱ�����������71.5%����ͼ6���Կ�������IJ�����������������Ӧ�ֲ�,��Matlab2011�е�������Ϲ�����,��������������Ȳ���������CVT���������õ��IJ����ͬһ�ַ��������������,�������2��ʾ,����2��SSE��ʾ���������ԭʼ���ݶ�Ӧ������ƽ����,��Խ�ӽ���0˵���������Ч��Խ�á�RMES��ʾSSE��ֵ��ƽ������R-square��ʾȷ��ϵ��,��Խ�ӽ���1˵�����Ч��Խ���롣���Դ���2�ɿ����ñ��ķ����õ��IJ�������ϳ���������ԭ������ӽ�,�õ��IJ��������׼ȷ��ӳ�����������״��Ϣ��

ͼ6 ����ʾ��ͼFig.6 Schematic diagram of sampling
��2 ���ַ����������Ч���Ա�Table 2 Effect comparison of fitting surface
by three methods
4 �� ��

(1)���ķ������Խ������ط�Ӧ�������������������Ϣ,�������������û����߲�������ʱ������Ϣ�Ķ�ʧ��

(2)���ķ�������������,������ѧ����ʽ����������Ҳ���á�

(3)�õ��IJ������ܸ���ȷ�ؿ̻�������״,Ϊ������������������ṩ��������֧�֡�

(4)Ϊ�����㷨��д����Ӧ�ij���,����˷���ʵ��,���뼸�ֳ��õIJ�����Խ����˱Ƚ�,ʵ��������ķ�����ʮ����Ч�ġ�

�����
[1] �����, ������, ������, ��. ����ƽ��Halton��������Լ������ܷ���[J]. ��������������ͼ��ѧѧ��, 2007, 19��8��: 1063-1068.
Dong Yu-de, Wang Yu-xi, Liu Da-xin, et al. Halton points sampling strategy and performance analysis for triangle plane[J]. Journal of Computer-Aided Design & Computer Graphics, 2007, 19��8��: 1063-1068.
[��������:1] [CJCR: 0.87]
[2] Lee G, Mou J, Shen Y. Sampling strategy design for dimensional measurement of geometric features using coordinate measuring machine[J]. International Journal of Machine Tools & Manufacture, 1997, 37��7��: 917-934. [��������:1]
[3] Kim W S, Raman S. On the selection of flatness measurement points in coordinate measuring machine inspection[J]. International Journal of Machine Tools and Manufacture, 2000, 40��3��: 427-443. [��������:1]
[4] Li S Z. Adaptive sampling and mesh generation[J]. Computer-Aided Design, 1995, 27��3��: 235-240. [��������:1]
[5] ������, ����, ������, ��. ��ѧģ����֪�������������ֻ�����Ӧ����[J]. ��������������ͼ��ѧѧ��, 1999, 11��4��: 359-362.
Lai Xin-min, Huang Tian, Lin Zhong-qin, et al. Adaptive sampling of digitizing for the known free-form surface[J]. Journal of Computer-Aided Design & Computer Graphics, 1999, 11��4��: 359-362. [��������:1]
[6] Zhang S G, Ajmal A, Woottton J, et al. A feature-based inspection process planning system for coordinate measuring machine��CMM��[J]. Journal of Materials Processing Technology, 2000, 107��1-3��: 111-118. [��������:1]
[7] Elkott D, ElMaraghy H, ElMaraghy W. Automatic sampling for CMM inspection planning of free-form surface[J]. International Journal of Production Research, 2002, 40��11��: 2653-2676. [��������:1]
[8] Hu Jun, Li Ye, Wang Yu-han, et al. Adaptive sampling method for laser measuring free-form surface[J]. The International Journal of Advanced Manufacturing Technology, 2004, 24��11, 12��: 886-890. [��������:1] [JCR: 1.103]
[9] Obeidat Suleiman M, Raman Shivakumar. An intelligent sampling method for inspecting free- form surfaces[J]. The International Journal of Ad-vanced Manufacturing Technology, 2009, 40��11, 12��: 1125-1136. [��������:1] [JCR: 1.103]
[10] Du Qiang, Faber Vance, Gunzburger Max. Centroidal Voronoi tessellations: application and algorithms[J]. Society for Industrial and Applied Mathematics, 1999, 41��4��: 637-676. [��������:1]
[11] ������, ������, ����, ��. ��������Voronoi�ṹ�IJ����㷨��Ӧ��[J]. ��е����ѧ��, 2008, 44��1��: 168-172.
Ji Cui-lian, Zhou Shen-jie, Tian Yun, et al. Node placement algorithm and application based on the centroidal Voronoi tessellation[J]. Chinese Journal of Mechanical Engineering, 2008, 44��1��: 168-172.
[��������:1] [CJCR: 1.067]
[12] Du Qiang, Emelianenko Maria, Ju Li-li. Convergence of the lloyd algorithn for computing centroidal Voronoi tessellation[J]. Society for Industrial and Applied Mathematics, 2006, 44��1��: 102-119. [��������:1]