ѧ
JOURNAL OF SOFTWARE
1999 6 10 Vol.10 No.6 1999



ڳ㷨*
ܡ־
ժҪһֻڳ㷨.㷨˽ṹ,ܶƼ򻯵ȫ,ٶȿ졢Чõŵ.ڴ㷨Ļϣһϸڲģ͵ɷһʵ˵㷨Ч.⣬»㷨ȫƵļ㷨˱Ƚ.
ؼʡ,,,۽.
ͼšTP391

Triangle Mesh Simplification Algorithm Based on Super-envelopes
ZHANG Ming-min1 ZHOU Kun1 PAN Zhi-geng2
1(State Key Laboratory of CAD & CG Zhejiang University Hangzhou 310027)
2(Department of Computing Hongkong Polytechnic University Hongkong)
Abstract An algorithm for triangle mesh simplification based on super-envelopes is presented in this paper. This algorithm can not only deal with arbitrary meshes, but also control the global error bound of the simplification. It runs fast and the result is perfect. The authors also give a method for constructing continuous level of detail models. Examples illustrate efficiency of the algorithm. Finally, the authors compare the algorithm with those algorithms with global error control.
Key wordsTriangle mesh, envelope, mesh simplification, progressive meshes.
ģʱ,Ҫǧβ̻ܿϸ,Ӵģ͵ĳ.ڻʱʹ洢εĿ,ˣӴģͨǲʵõ.򻯷ڱ״ǰ´εĿ,Ӷõ򻯵ģ.
Schroeder1˻ڶɾģͼ򻯷;Turk2ݸ˻»ֵĶģͼ򻯷;Hoppe3һŻ㷨,㷨˱ȽϸӵȫŻ;Rossignac4һֻڶ㷨;Cohen5˰ĸ,ðԼڶɾ򻯹;Garland6ʹöƱļ,㷨ʹö۵һ򻯲,ɵõĽģ;Hoppe7ԭ㷨Ļ˻ڱ۵ġӵйص۽ɷ;Guziec8ʹûݲ壨tolerance volumeȫƵ򻯷;Bajaj9ҲһȫֽƷ;Cohen101998SIGGRAPHϣܱģԵļ㷨.ⷽо㷨ĸĽͰ㷨ڶϸڲģ͵Ĺȣ1112.
һ˵,㷨ԷΪ:һС㷨һСĿ㷨.С㷨ʵѴﵽСЧ,ΪӶĿ̶ĽǶȺҵԭʼϲСĶ׼,Ҫ˵ҵǸСļ.СĿ㷨һ,ȸһı׼,׼¾ɾ,õһ׼ΧڵľٶĿļ.,ƽԭʼĳ̶ȾͿͨ׼ж.ڰĶ㷨5ݾһ㷨нȻЧһ.㷨׼Ǽϵеԭʼľ.㷨Ļ˼ǣԭʼΧ,Ȼ֮.ûľ,һƫԭʼ/2һƫԭʼ-/2ڰ,Լ֮ԭʼм(ɾ)һȲཻҲԽļ.
Cohen5㷨ڱ֤ԭʼ֮һΧǰ,ɾԭʼϵĶ.,ԶӦ,Чر.Ȼ㷨ȱҲǺԵ:(1) 㷨ھԽ.㷨ڼ⵽ԭʼԽʱͲٴȥ,ʵӦУԽģձڵ;(2) 츴,.㷨ҪͨжϰǷԽÿƫ,㷨ļȽϴ.
,һֻڳ㷨.,ĸǰչ,Բ,һЩΧԭʼΧ(ⲿڲ)Ƭ.㷨Cohen㷨ŵ,ҿԴ˽ṹģ,еԽ.ĹҲǳ,С.,ǻһֻڶɾ۽Ĺ췽,Ӷֶ֧LOD(level of detail)ģ֮.ĵ1㷨.2ڽܻڶɾ۽Ĺ.3ȸ㷨ʵֺʵ,Ȼ㷨еľȫƵļ㷨бȽ..
1 㷨
1.1 ƹ㼰Ĺ
ͨϸ,ǲѷ,㷨Ҫð,˰Ŀռλʹԭʼ±ֵؼ.Զɾ㷨Ϊ:㷨ɾԭʼϵһ,ɾöγɵĶֲǻ;Ȼ󣬶ÿɾֲǻõΣжǷཻûཻ˵öԱɾ,ܱɾ.,Ƕ԰ĸƹ,˳ĸ.粻һ,ǽΧԭʼһЩμ.
,ǿַ쳬.һַ,طƫԭʼĶ.ǲҪƫƺõĳ,Խ.һַ,ԭʼÿ䷨ƫ,õĳʵǿռһЩɢεļ.
Ϊ˼򻯳Ĺ,ԭʼÿƫͬľ,ֻóƼ򻯵ȫ;ڶԭʼмʱ,ٿǾļԪ()ľֲ.Զɾ㷨Ϊ,ǿԼÿ,ɾСĶ,ԭʼľֲ.,㷨ȿԭʼȫ,ֿԭʼľֲ.,ǶԳ缸ûκ,㷨ڴԽģ.
ͼ1ƹ˰ĸ,ͷһʾ.ͼ1(a)(b)ֱǶӦڳⳬ.óͨԭʼϵ䷨ƫƾԾ10õ.ͼпԿ,ⳬɿռһ,δ.

(a) ڳ磨ƫ-10(b) ⳬ磨ƫ+10
ͼ1 ƫƵõĳʾ
Ȼ,ڰĸƹɳ,ɳ㷨ͿԲüⳬǷԽ,ֱԭʼÿƫûָƫ.ǵ㷨ʵ԰˼ⳬǷԽһ,ԭûָƫкܴäĿ,ⳬǷԽṩһЩмֵϢû.㷨ûҪǷԭʼģͽм.
1.2 
Ϊ˱֤õļԭʼľûָĴС,ͱʹڡⳬ֮.ǰ¿ѡּ㷨,ɾ1ݡɾλǱ۵6.ɾ㷨Ϊȿʹþֲֿʹȫ.һʵľֲɾ㷨.
㷨. ʵľֲɾ㷨.
1 ԭʼеÿһ.
2 û̽жѡһСĶ,ɾö.
3 һɾγɵĶ㻷ɵĿռνǻ.
4 һǻõÿ,жǷ볬ཻ.ཻ,ö㲻ܱɾ,ָö;,ö㱻ɾ.
5 ж㶼̽,ת6;,ת2.
6 .
1ʵļԲοף12ݵķ.ͼ2ʾ,򵥶Q,ΪQƽƽķ,P1,P2,...,PkΪQΧĶ㻷еж,ΪQ㵽Pi(i=1,2,...,k),iΪļн,Qʿ¼.
(1)

,Ǿ͵õָΧھԽٶĿļ.Ȼ,ҲԽһЩŻ(,ⳤεĳ),ǰڳ֮.

ͼ2򵥶ʵļ
1.3 LODģ͵
Ȼ㷨ɢLODģ͵.Ϊ֧LODģͼƽɣбҪLODģ.۽һֹLODģ͵Ч.ַܴʡ洢,㷨ԭʼģһδͿ.,ķٷչ,۽ΪάͼݵһЧͷҲйӦǰ.
۽һֹ췽ǻڱ۵7.һԭʼģ,ÿִһα۵͵õһģ,۵¼.㷨õԭʼģ͵ʾʱ,Ҳõһ۵,еģִб۵(),ͿԵõԭʼģͺģ֮εģ.
ķԶɾΪ.ͼ3ʾ,V0ҪɾĶ,V1V2V3V4V5V0ΧĶ㻷.ɾV0,γɵĶǻ͵õͼ3(b)ʾ3.ǰV0ڶеԼΧĶ㻷(뻷)¼,ͲѴͼ3(b)õͼ3(a).һnĳʼģMn,ÿɾһ,ǾͰöصϢdi¼,õmļģMmʱ,Ҳ͵õһϢ{dn,dn-1,...,dm+1},ɸϢ{dn,dn-1,...,dm+1}ǾͲѴMmõģ{Mn,Mn-1,...,Mm+1}.

(a)ɾǰ(b)ɾ
ͼ3ɾʾͼ
2 㷨ʵ֡ʵ㷨Ƚ
2.1 㷨ʵ
㷨SUN SPARCվCʵ.㷨ʵҪݽṹǰ˲.ڼ㷨ÿɾһҪжɵλ᲻ͳཻ,ԶԳ罨˲ݽṹͲɨ,Ӷӿ㷨ٶ.㷨õݽṹУ(a) (b) α(c) ÿصɵı(d) İ˲.
2.2 ʵ
ʵ,㷨ԽϹ⻬Ͳ⻬ģݶǱȽЧ.ͼ4ʾ,ӵģڼ95%֮ԭģͻܽӽ,Ϊ99%ʱ,õļģͻǿԽܵ.ͼ5мɽģͶ,㷨ʹ󲿷ɽɽȵõ,ϱԭ.,㷨ҲرǻĻеģ,ͼ6ʾ.ͼ6(a)һǻԭʼģ,ͼ6(b)(c)(d)ֱ39%72%81%Ժļģ.Կֱõ˺ܺõı.

(a) ԭʼģ
(60 473)(b) ģ1
(16 633)(c) ģ2
(3 287)(d) ģ3
(633)
ͼ4 㷨ģ͵ļ


(a) ԭʼģ
(6 035)(b) ģ1
(3 505)(c) ģ2
(1 706)(d) ģ3
(934)
ͼ5 㷨Լɽģ͵ļ


(a) ԭʼģ
(11 328)(b) ģ1
(6 906)(c) ģ2
(3 126)(d) ģ3
(2 204)
ͼ6 㷨Իеģ͵ļ

3  
Ļڳ㷨ٶȿЧ.һҪǿӵ,Ӧάʽͼϵͳ.ǿԶģ͵Ĳֲͬȡͬƫ.磬ӵϽĲҪ̻ϸһЩ,ӵԶĲԿ̻ôֲһЩ;ھʵУɿǶӵϽĲֲȡСƫ,ӵԶĲֲȡϴƫ.ȡСƫĲ־ͼ򻯵һЩ,ȡϴƫĲ־ͼ򻯵öһЩ.һоǣѸ㷨ӵͻ㷨,㷨Ӧõάʽͼϵͳ(罻ʽӻʵ)ȥ.
*оõȻѧ㽭ѧܹ߿Ƽ.
߼顡,Ů,1968,ʦ,ҪоΪý㣬ʵ.
,1975,˶ʿ,ҪоΪͼ.
־,1965,ʿоԱʿʦ,ҪоΪʵý㼼.
ͨѶϵ:־310027,㽭ѧCAD&CGصʵ
ߵλܡ(㽭ѧCAD&CGصʵҡݡ310027)
־(ѧӼѧϵ)
ο
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, 1993,27(SIGGRAPH'93):1926
4Rossignac J, Borrel P. Multi-resolution 3D approximation for rendering complex scenes. In: Falcidieno B, Kunii T eds. Geometric Modeling in Computer Graphics. Springer Verlag, 1993. 455465
5Cohen J, Varshney A, Manocha D et al. Simplification envelopes. Computer Graphics, 1996,30(SIGGRAPH'96):119128
6Garland M, Heckbert P S. Surface simplification using quadric error metrics. Computer Graphics, 1997,31(SIGGRAPH '97):209216
7Hoppe H. View-dependent progressive meshes. Computer Graphics, 1997,31(SIGGRAPH'97):189198
8Technical Report, RC20440. IBM Research Division, T.J Watson Research Center, 1995
9Bajaj C L, Schikore D R. Error-bounded resolution of triangle mesh with multivariate data. In: Insethuraman P ed. Proceedings of SPIE on Electronic Imaging, SPIE, 1996,2656:3445
10Cohen J, Olano M, Manocha D et al. Appearance-preserving simplification. Computer Graphics, 1998,32(SIGGRAPH '98):115122
11־,־,ʯӢ.㷨Ӧ.ѧ,1997,8(12):881888
(Tao Zhi-liang, Pan Zhi-geng, Shi Jiao-ying. Mesh simplification algorithm based on energy evaluation and its application. Journal of Software, 1997,8(12):881888)
12־,С,ʯӢ.⻷жϸڲģԶ㷨.ѧ,1996,7(9):526531
(Pan Zhi-geng, Ma Xiao-hu, Shi Jiao-ying. The generation generation algorithm for multiple levels of detail in virtual environment. Journal of Software, 1996,7(9):526531)
1998-01-08յԭ,1998-07-14յ޸ĸ
