Զѧ
ACTA AUTOMATICA SINICA
1999 25 1 vol.25 No.1 1999



һµĻڶ㷨1)

ܡ־ʯӢ

ժҪڼͼѧУöģ.ڻʱʹ洢εȣӴģͨǲʵõ.ģͼڼʵͽʽӻȼͼӦŹӦǰ.ΪһµĻڶ㷨.㷨ð˲Ӧ֣һֻڵ㵽ƽЧƷûָΧͨʹԭʼеĶﵽ򻯵Ŀ.㷨ʵּ򵥣ٶȿܺܺõرֱ߽.һͼ˵˸㷨Ч.
ؼʡ򻯣࣬ϸڲ.
A NEW MESH SIMPLIFICATION ALGORITHM BASED
ON VERTEX CLUSTERING
ZHOU Kun,PAN Zhigeng,SHI Jiaoying
(State Key Lab.of CAD&CG,Zhejiang University,Hangzhou310027)
AbstractIn computer graphics,models are often discribed by polygonal meshes.Because the rendering and storage cost is proportional to the number of polygons,too large models are not practical.Model simplification techniques are widely used in computer graphics fields such as computer animation,virtual reality and interactive scientific visualization.In this paper a new algorithm of mesh simplification based on vertex clustering is presented.The algorithm adopts octree structure to subdivide the mesh model adaptively.A new error control method is also presented.The implementation of the algorithm is simple and it runs very fast.Examples illustrate the efficiency of the algorithm.
Key wordsPolygonal mesh,mesh simplification,vertex cluster,level of detail.

1
ڼͼѧӦ򣬾öģ.ʹüɨϵͳԻøָӵ⣬άģعõĶģͨʮƬ.ڻʱʹ洢εȣӴģͨǲʵõ.һ棬⻷УͨҪϸڿ̻úϸģͣǿΪÿ幹ɸͬϸڲεģͣҪѡĳģ.Ϊʾ洢Ҫ󣬱ิӵģͽм.ģͼڼʵͽʽӻȼͼӦŹӦǰ.
ģͼ򻯵оһϵгɹ.Schroeder1˻ڶɾɾTurk2ݸ˻»ֵĶģͼ򻯷Hoppe3ݲŻ򻯷Rossignac4һֻڶ򻯷Eck5ݽСģͼ򻯣Cohen6ͨ򻯵ȫGarland7ö.ⷽҲչһЩ׿гЧо8910.
ϷУRossignac4ķˣٶ.˼ǣһΧаԭģͰΧͨȷְΧеĸ߽ΧеȷֳɸСĳ壬ԭģ͵жͷֱЩڣɨЩ壬ĳж㣬Ѹóڵжɾһ¶㣬¶ǱɾԭļȨƽ.ַԣȣԭģϵĵڿռķֲδ֪ģַ԰Χнеȷ֣ܵµȷֺĳЩĳڰܶĶ㣬ĳЩĳûлֻкٵĶ㣬һɿռʱ˷ѣһģ͵ĳЩֹּ򻯣Σĳڵ¶ʱַֻȡ򵥵ļȨƽûиһֽϺõƷٴΣԭģͱȽʱĳЩڵĶԭģ͵ĲϴĲ֣Щһͻɺܴı.ͼ1һӣʵ߱ʾ߱ʾΧеĻ.ͼ1(a)ԭʼͼ1(b)Rossignac4ݷõļ򻯣ѿּ򻯵ı̫.


aԭʼ񡡡(b)ɵļ
ͼ 1Rossignac㷨ɵı

һµĻڶ㷨㷨ð˲ΧеӦ֣ͬʱ˿ƶЧRossignac4㷨ȣٶ൱Ч÷Χŵ㣬иһͼ˵˸㷨Ч.ڶκζ񶼿תΪָ.
2㷨
Ϊ(οף8)һЩ.
2.1
1.ռһΣع߼ڶ㴦ڽӣһζΪTMTMɶ㼯V=(v1,v2,vn)μT=(t1,t2,,tm)ɵĶԪ(VT)ʾ.
2.TMһߣñֻΪһУƸñΪ߽ߣñߵ㱻Ϊ߽綥㣬ñڵαΪ߽.
3.TMһvi,viΪһTikɵļϣΪ붥viصμPi.
4.TMһ㼯Vs={v0,v1,,vk}VsеÿصμϵĲΪ붥㼯VsصμTs(Vs)
(1)
2.2¶ɺĶ
ȿǣһЩһʱɾЩһ¶Լø¶汻ɾĶǶ.һѡ׼⣬㷨Ե㵽ƽľ7Ϊ׼.
ÿڶͱɵͼͨģ2.3ǽ㷨α֤һ.ǰᣬһ㼯Vs={v0,v1,,vk}һʱ¶ͼ.ǿȵõ붥㼯VsصμTs(Vs)ǰļ費ѷ֣μϹԭģϵһ.ͼ2һ򵥵ӣ㼯Ϊv1,v2,v3,v4Ϊv0.㼯VsΪvi0=xi0yi0zi01T(Vs)Ϊvi0μTs(Vs)ÿƽľƽ֮ͦi,1VsеĶ㵽ÿvi0صƽľƽ֮ͦi,2,
(Vs)=i,1+i,2.(2)
Ϊʹ(Vs)СԶʽ(1)еxi0,yi0zi0ƫΪ㣬
(3)
p=abcdTΪÿ붥㼯VsصμTs(Vs)еڵƽƽ淽ax+by+cz+d=0,a2+b2+c2=1,i,1ɱʾΪ

Mp44ĶԳƾTs(Vs)
(5)
vi0λúvi0صƽķδ֪Ԧi,2ļȽϸ.ͼ2ʾȼvi1Σvi0,vi5,vi6ƽľƽd.vi1=xi1yi1zi11T,vi5=xi5yi5zi51T,vi6=xi6yi6zi61T.Σvi0,vi5,vi6ƽķΪ
(6)


ͼ 2ʾͼ




(7)
vi1,vi5vi6֪p=abcdTʾΣvi1,vi5,vi6ƽ淽ax+by+cz+d=0,a2+b2+c2=1.Mp=ppTͬʱ

Ͳѵõvi0Σvi1,vi5,vi6ƽľƽΪ
(8)
ʽ(7)ʽ(8)Ƶ
(9)
vi1,vi5vi6֪M*pֻvi0λй.ٿvi1vi0صƽľƽԼVsеඥ㵽vi0صƽľƽЩƽ;ͿԵõ
(10)
Qi,2ֻvi0λйأvi0δ֪Qi,2Ҳδ֪vi0ĹʵҲQi,2Ĺ.Դǲõ⣺ȸQi,2Եֵ()õQiĳֵQi,1ʽ(3)vi0Ľֵv*i0;vi0Ľֵv*i0Qi,2ĽֵQ*i,2Ȼvi0һֵv*i0.һֱvi0ǰֵ֮ĲСĳƾ.ֵԣڳֵѡýϺã൱죬ʵ֤ʱѾܺ.ǾͿÿα۵ɵĵλú͸ò.
㼯Vsкб߽綥㣬Ϊ˱ԭģ͵ı߽μTs(Vs)ÿ߽һͨñ߽߲ñ߽ڵı߽δֱƽ.ڼʱЩƽҲ.ʵַ֤Աԭʼı߽ǷǳЧ.
2.3ģ͵ӦԻ
ζԭģ͵İΧнл.ǵĻǰ˲.ԭģ͵İΧΪ˲ĸڵ㣬Ȼ˳ԭж˲.㷨ͨư˲ÿҶӽڵʵģ͵ӦԻ.
һ˲ĳһҶӽڵʱҶӽڵڻ㣬Ѹöֱӷýڵ㣬ҶӽڵѾж㣬ǾҪжϸҶӽڵʾĳĳߴǷûָÿߴԼýڵĶĿǷûָÿܰĶĿǣҪѸýڵ㲢ѸýڵĶ䵽ӽڵȥΪ˱֤2.2ᵽÿڵĶͱɵͼͨͱͼ1ʾıιľ࣬㷨ҪжڰѸöó󣬻᲻ᵼ¶㼯صμĳЩεĳ()෴ᣬýڵҲҪ.
ͨ湹˲Ḷ́㷨ʵģ͵ӦԻ֣Ҳʹ2.2ƷΪЧ .ͼ3ǵӦֶͼ1ʾ񻮷־Чʵ߱ʾ߱ʾ.ע⵽ͼ3(b)ʾļ򻯻ͼ3(a)ʾԭ״.


ͼ 3㷨ļ

2.4㷨ܽ
Ļڶ㷨㷨
㷨1.ڶ㷨
1.ԭʼ2.2ķʼ˲.
2.һİ˲ÿǿҶӽڵ㣬ýڵʾĳаĶ㼯ϵ;ɵµԼ.ûָķΧڣоࣻ򣬶ԸýڵٽзѣֱҪִо.
3..
3ݽṹʵ
3.1ݽṹ
㷨ҪдΣҪƺݽṹʹ㷨ܴģͣҪнϿٶ.㷨õݽṹУ(a)(b)α(c)ģ͵İ˲.ÿξõµֱӷԭԭıʡռ.
3.2ʵ
㷨IBM Power PCʵ֣ͼ456һʵ.ʵ㷨ԽϹ⻬Ͳ⻬ģݶǱȽЧ.ͼ4Уӵģڼ84.7%֮ԭģͻܽӽΪ98.8%ʱõļģͻǿɽܵ.ͼ5еͷģֻͣ76.6%ԭʼԵ.⣬㷨Ҳرǻĵģͣͼ6.ͼ6(a)һεԭģͣͼ6(b)(c)(d)ֱ49.5%74.8%93.9%ļģͣע⵽εıֵ߽úܺ.
ͼ7Rossignac4㷨ģļ򻯣ע⵽ͼ7(b)ļģкܴı.⣬㷨еƷGarland7.Garland7㷨м򻯵ĻǶ۵ԭйһߵĶԻ߾ϽĶԺϲһ.ʵϣǱ㷨һֻҪģ͵İ˲ϸƣͬʱڵİ˲ڵҲоͿʵGarland7㷨.㷨ȣ㷨ٶҪö࣬Ч൱.ͼ8Garland7㷨Եļ.1㷨ٶȶԱ.еݶIBM Power PCϲõ.


ͼ 4㷨ģ͵ļ


ͼ 5㷨ͷģ͵ļ


ͼ 6㷨Եģ͵ļ(Gouraud)


ͼ7Rossignac㷨ģ͵ļ򻯡ͼ 8Garland㷨Եģ͵ļ򻯲Gourand
1㷨ʱԱ

ԭģ
()ģ
()Rossignac㷨
ʱ(s)Garland㷨
ʱ(s)㷨
ʱ(s)
ͷ(1355)5970.311.480.52
(8192)20572.3331.024.56
(69473)277220.601738.8744.02


4
µĻڶ㷨ˡٶȿЧ.ģΪģʱ㷨Ӱ.㷨ʵͽʽӻеĶϸڲγԶ.
㷨ף4е㷨һƷӶЧĿƼԭʼ֮ͬʱܶģͽЧӦԻ֣мʸߣЧٶ൱ŵ.
оҪ棺1)оЧƷ2)о()Թݽ.⣬ǻѸ㷨ӵͻ㷨γӵصʵʱ㷨.Ϊ㷨ģͽ˰˲֣ǿԸӵλãģ͵ĲֲͬòͬļõĴٶ.
1)õȻѧصĿʵͼʵʱɺʾ͹ȻѧĿʵж̬ϸڲμоͬ.
ߵλ:(㽭ѧCAD & CGصʵҡݡ310027)
ܡУ1977Ϊ㽭ѧCAD & CGصʵ˶ʿо.оΪʵѧӻ.
־У1965ʿΪ㽭ѧCAD & CGصʵоԱ.оΪֲʽ㡢ʵý弼.
ο
1Schroeder W J,Zarge J A et al.Decimation of triangle meshes.Computer Graphics,1992,26(2):6570
2Turk G.Re-tiling polygonal surface.Computer Graphics,1992,26(2):5564
3Hoppe H,DeRose T et al.Mesh optimization.Computer Graphics(SIGGRAPH'93),1993,27:1926
4Rossignac J,Borrel P.Multi-resolution 3D approximation for rendering complex scenes.In:Falcidieno B,Kunii T.editors,Geometric Modeling in Computer Graphics.New York:Springer Verlag,1993:455465
5Eck M,DeRose T et al.Multi-resolution analysis of arbirtary meshes.Computer Graphics(SIGGRAPH'96),1996,30:173182
6Cohen J,Varshney A,Manocha D et al.Simplification envelopes.Computer Graphics(SIGGRAPH'96),1996,30:119128
7Garland M,Heckbert P S.Surface simplification using quadric error metrics.Computer Graphics(SIGGRAPH'97),1997,31209216
8־СʯӢ.⻷жϸڲģԶ㷨.ѧ19967(9)526531
9ƣȨ.׼Ķģͼ򻯷.ѧ()199619(9)217223
10־־ʯӢ.Ż㷨Ӧ.ѧ19978(12)881888


ոڡ1997-08-01յ޸ĸڡ1998-03-10
