ѧ
JOURNAL OF SOFTWARE
1999 2 No.2 1999



һַȫֹģ͵ļ򻯷*
ѧ1 1,2
ժҪȫֹģͼͨеıֽ㹻ϸ,Ծȷز׽໥ڵӰЧһЩЧ.,һӳȫֹռ,ģ͸ӶԶԶ˵ͼιվʵʱ.һַȫֹģ͵ļ򻯷.㷨ȸݷȼصԼ۵Ӿص,ԷԱ仯ֵΪ׼,Ƭϲʵȫֹģ͵ĵ1,ԭȫֹģͼΪԱ仯ûΧڵһЩ.Ȼöɾʵֳ߽ļ,һӴԭģ͵ļ򻯳̶.,㷨Чؼ򻯷ȫֹģ,ܽϺõرԭģ͵.
ؼʡȫֹģ,ȫֹģ,,ϸڲģ,ʵ.
ͼšTP391
A Simplification Method for Radiosity Global-illumination Meshes 
LIU Xue-hui1 WU En-hua1,2 
Abstract The solution to the global illumination problem using radiosity method is usually represented by an illumination meshes, which are frequently very finely tessellated in order to capture shadow boundaries and other significant illumination features. So the geometry complexity of a complex scene with global illumination effect is beyond the capability of the current computer graphics workstation. In this paper, an automatic method is presented for simplifying the meshes produced as the solution to global illumination problem using radiosity method. Based on the character of the illumination meshes produced by radiosity and the characteristic of human eyes, it simplifies first by merging faces with maximum relative radiosity difference below the threshold that users define. And then the vertices on the perimeters of the merged face are deleted to further simplify the original meshes model. The model simplification samples based on these methods are given and the results show that the algorithm only significantly reduced the complexity of original meshes model, but also performed well to capture the coherent shadow discontinuity feature of illumination meshes.
Key wordsGlobal illumination models, radiosity mesh, simplification of meshes, level of detail, virtual reality.
ʵ⻷,߶ʵͼӾЧǲʵоıҪ.VR(virtual reality)ڴĿȻǸʵеıͼ,ʹȫֹģʾиӳʵͼαȻVR׷Ŀ.
ȫֹģ˵,߸㷨ӵ,൱һʱڲΪVRõĹģ.ȼھռֲܷ,ӵ޹,ΪԤ,пܳΪʵʵͼɵĹ.һЩϵͳɹʹ÷ȼΪVRĹģͣ1.
ڷȼ,Ϊȷ׽໥ڵӰһЩЧ,еıֽ÷ǳϸ,ȼģ͸Ӷԭгļʮϰٱ.ȻӦ֣2ԼӰɷ3,4ѽЧؼĸӶ,һзȫֹЧĸӳģ͸ӶԶԶ˵ͼιվĻ.ھȫֹЧģʵʱ,żͼѧӦ÷ΧĲ,.
ǵ۵Ӿص,˶ϸڲģLoD(level-of-detail) .üڲӰͼǰԲͬϸڱͬһάģ,Ҫ̶Ⱦģϸڵѡ,Դ˼СͼδĸӶ,ʵָģ͵ʵʱ.
ĸһַȫֹģ͵Ķϸڲģ͵Զ㷨.㷨÷ȵļص,ԷԱ仯Ϊ׼Ƭϲ㷨ʵֶԷȫֹģ͵ĵ1,õһԱ仯û巶ΧڵĴ.Ȼ㷨ԭģиRGBֵö߽綥ɾ,ʵָöı߽,һӴģ͵ļ򻯳̶.,㷨Чؼ򻯷ȫֹģ,ľзȫֹЧĶϸڲģ,ܽϺõرԭģ͵.
1 ع
ģ͵ԶĶϸڲģͷ,ǽ˶෽̽,˻ڶɾĶ57ݡڱɻĶ8ݡƬϲĶ9ݡ»ֵģͼ򻯷10ݡȥģͼ򻯷11ԼСĶֱʷ12ݵȵ.,ƬϲĶԽƽжʵֽλͬһƽϵεĺϲ,ﵽģͼ򻯵Ŀ.÷ģ͵ļ򻯳̶Ƚϴ,ʺαʾģ.
ܵģ͵ļ㷨ԼԼı仯ָģ͵ļ,Ȼģ͵Լ,ɫ,Ӧ뼸ԼͬҪĵλ.رǹɫ,Ϊṩʵⲿ,Ϊṩ˷ḻٽڵӾϢ.㷨,ھȫֹЧģ͵ԶҲһЩ,ȡһЩɹ.
Huges13ݷ˾йЧģһģģ͡رģ͵ص,ָ˶ߵ֮,ģͽԿɿάƽһĳԼĵģ.ף13ԽRGBԼֵرģеһά߶ԼֵӦ,ԻڼԼһģ͵ļ򻯷ɾʵֹģ͵ļ.,Hoppe
ף14нף6еļξ뺯ƹģ͵Լ,Աɻģʽʵȫֹģ͵ļ.еļξ뺯,HoppeƵľ뺯.ΪģиԼʵĲ,㷨ݶĸԼʵľ,RGBֵ,ж,ԾñǷɻΪ.㷨ԾзȫֹЧģͽм,ȡ˽ΪЧ.
2 㷨ԭ
ȼ軷еΪ.νBָ浥λ.غ,һxΪԴ,淴Χ.
(1) 
B(x)Ϊһxķ;(x)Ǹõϵ;xΪxΧһ;dAΪõ΢Ԫ;G(x,x)=;V(x,x)Ϊxxڵ;SΪбļ.
ΪĹֲܷ,ȷֻɸƬPi(i=0,...,n),ÿһƬPiгֵķBi,.xƬֲ޵ĺͽƷʽ(1),õһ鷽
Bi*Ai=Ei*Ai+i*Aj*Bj*Fij,i=0,...,n; 
AkƬk;FijƬPiƬPj״,
 
̼ɵõռĹֲܷ,ɫ仯ӦڸƬķȴС仯.
,ȼĽԭ,еƬгֵ.۶ԹԾֱ,ʵʻһøֲֵ,½Ĺֲܷ,Եõܾȹɵⳡͼλ.Ϊͼμͼ,ͨC0ֵ.ԶΧƬķֵƽȡƬĹǿ,ȻͼռԸƬĹǿԲֵͼλ.
ӷ(1)֪,ڻ໥ڵ,ȵķֲŸϵ.Щϵ,رǵ12ϵΪӾṩ˷ḻ塢ٽڵӾϢ.ڹģ͵ļвӦ޶ȵؼģ,ڼ򻯹Ӧʶԭģ͵.
Ϸȫֹģͼص,ԷԱ仯ֵΪϲ׼Ƭϲ򻯲ʵַȫֹģ͵ĵ1.õһԭģͶ㡢ԭģͱɵġû巶ΧԱ仯Ķ.ΪһӴģ͵ļ򻯳̶,㷨ԭģͶRGBֵı仯߽ɾ,ʵԭģ͵Ľһ.Ϊ,».
1. ռһع߼㴦ڽ,һζΪģTM.
2. ģTMһڽӵĶιɵļMΪģTMһ.
3. ģTMһб߽綥㹹ɵĿռΪӦڴ˰ĳSuperSM.ɴ˶εı߳Ϊ˳ı߽.˳ڽӵԭģTMеĶν˳ı߽Ƭ.
ȹģ͵ļ򻯹̼ƬԶϲϺϲĹ,ҲӦ治ϺϲΧƬĹ,㷨Ҫ¼:(1) Ƭ򻯻,ȫֹģͻΪһϲİ,Ӧĳ,ʵģ͵ĵ1.(2) ԭģͶRGBֵ,ͨݹָʵֳı߽,ģ͵ĵ2.(3) Ȼƽ̬ȼȨľֲǻʵֳʷ,ɷȹģ͵ļ.
3 Ҫ㷨
3.1 
ɹ̼߽粻ŵĹ,Ҳ߽ƬϱϲĹ.㷨ѡԭģеƬΪʼֵ.߽Ƭϱϲ,߽粻ֱб߽Ƭϲ.,ǳƳʼֵƬΪӡƬ.
3.1.1 ϲ׼
ϽڷȼĽ֪,ȼĽԭ,ڻĻвC0ֵɽϹ⻬ͼλ.ڲԲֵ,ԼϵԵýܵ,ɵĻԵġ©⡱.,㷨Ա仯ֵĺϲ׼,ϲƬķԱ仯ֵƽΪӦķԱ仯ֵ.֤,Ա仯ֵ׼򲻽ܽϺõʶλڼϵԵƬ,ܽ׼ȷطӳܵı仯.
ƬPiзֵBi,ΪAi.nƬPijڽ.ƬPijֱΪAij,ֵΪBij(j=1,...,n).ǶƬPiķԱ仯ֵCiΪ
Ci=max(abs(Bi-Bij)/((Ai+Aij)*Bi),abs(Bi-Bij)/((Ai+Aij)*Bij)),j=1,...,n 
SuperSMĳ߽ƬPj
Cj && (Cj*Aj+CSuperSM*ASuperSM)/(Aj+ASuperSM), 
߽ƬPjϲ,ΪSuperSMϲ;,Ϊ˳ϲ.,ΪûΧֵ.ASuperSMΪSuperSM,ϲƬ.
Ϻϲ׼ܴλڷԱ仯ֵûΧڵƬ,ȴܼλڼϵԵķԱ仯ֵûΧȴͬı仯ԵƬ.Ϊ,ڳSuperSM¶ΧƬPķԱ仯ֵCj.
Cj=max(abs(Bi-BSuperSM)/((AiASuperSM)*Bi),abs(BiBSuperSM)/((Ai+ASuperSM)*
BSuperSM), 
,BSuperSMΪSuperSMķֵ,ǳϲĸƬķֵƽ.ֵСûΧ,ƬɱSuperSMϲ;,Ƭܱϲ.
, ƬϲĲԿܽΪα:
int Merged(SuperS S, Patch P, threshold)
{
float CP;
if(Pmerged) return(0);
if (CPthreshold){
if ((CP*AP+CS*AS)/(AP+AS)threshold)
return(1);
else
return(0);
}
else{
CP=max(abs(BP-BS)/((APAS)*BP),abs(BPBS)/((AP+AS)*BS))
if (CPthreshold)
return(1);
else
return(0);
}
}
3.1.2 ӡƬѡ
ף6ָ,ģ͵ļһȫNP.㷨ģ͵ļ򻯺ϲ,Ծֲָ,ӡƬѡ˳ģ͵ļ򻯽һЩӰ.㷨ģ͵ļ򻯹С˳ģƬķԱ仯ֵ,ԴָӡƬѡ.㷨ÿԶͷӦƬΪӡƬ,ϺϲΧƬ,ֱΧƬϲ.Ƭѱϲٲ롰ӡƬѡ,ɾڷֵеӦ.㷨ظϲֱΪ.
Ȼ,㷨ԵһƵʹֲģͽм.ʵӦ,ȵļһΪRGBֵɫֲ.Դ,ַͨ.1ַף13һ,RGBɫԼֵرģ͵һά߶ԼֵӦ.2ַRGBֵͬȶԴ,ף14.Ĳõ2ַ.ƬϲͬʱRGBɫܵԱ仯,ֻɫܵԱ仯ûΧʱ,Ƭϲʵʩ;߽Ƭܱϲ.Ա仯ֵRGBɫԱ仯ֵΪλֵС.
3.2 ߽ļ
ͨϽڵĳ㷨,ǽԭģͼΪһЩûΧԱ仯,õӦԭģͶ㡢ԭģͱɵƽΡ.湲һ.ЩеĲλͬһֱ,ûӾΧɫֵԻԱ仯.бҪõĳ߽.
賬SuperSMб߽綥㼯V={1,2,3,...},ǰʱ˳ɳSuperSMı߽.SuperSMΪڽӶеһ,㼯V={j,j+1,j+2,...,j+r}еı߽綥,j0j0+1ǵĹ߽(j0=j,..,j+r-1).ǲõݹָʵֳ߽ļ.㷨߶Φjj+rƱʾSuperSMSuperSMı߽.м䶥j+1,j+2,...,j+r-1RGBֵ뾭˵RGBֵԲֵõӦRGBֵ֮Сû巶Χd,Ҹм䶥㵽߶Φjj+rľСûd;,Щм䶥˵RGBֵֵĶ߶Φjj+rĵj1ָߦjj+r,õߦjj1ͦj1j+r.Ƕظϲ,ֱڸߵм䶥߶˵RGBֵֵĲûΧ,Ϊһֱ߻߲ٴм䶥.
ڱ,ڲõģͶǾģ,㷨нǸɫ,ԸɫֵΪ߽򻯵,Ǽξ.
3.3 ǻ
ƬϲĹ֪,ɵĳԭģûΧԱ仯Ƭ,пΪͨ.ɵĳпǴڻĶ.ΪʵִڻĶεʷ,ͨڻ⻷߽֮ͨͨתΪİ,Ȼƽ̬ȼȨľֲŻǻʵֳʷ,Խٵƽԭģ.
3.3.1 ͨתΪͨ
ͨڲп׶.ͨ⻷ı߽ڻı߽ͨ,ǽͨ򻮷Ϊİ(ͼ1ʾ).ͨǶһڻɵ.Ϊ뻷ཻͨ,ȶԻ.,ǽڻPΪInnP,⻷PΪOutP.賬λXYƽ.
 
ͼ1 
Ƕƽϵĵ㶨һ˳:y,y=xu,(x,y)(u,).˳,ǼǻP󶥵ΪTOP(P).
Ϊ֤ɵİξõ״,ͬʱ֤ɵͨ߳˵ⲻཻ,庯D(l,),lΪһ߶,һ.ӦԵlĴߵĴ߶,D(l,)ΪԵlľ;,D(l,v)Ϊvl˵ľĽСֵ.
㷨ȽڻyֵĵӴС,ȻȡеڻInnP.Ϊ⻷OutPڻInnPͨ,㷨⻷Ѱһѱl,ȻӱlѰѶ˵TOP(InnP)һͨ,ڻ⻷.ڻ,󽫶ͨתΪͨ.
Ѱѱlʱ,OutPб߶Ϊѡ,ֻЩһ˵yֵTOP(InnP)yֵı߲ſΪѡ.Щѡѡһl,ʹD(l,TOP(InnP))ֵС.Ȼڴ˱ߵĶ˵ѰһѶ˵,ʹ˵㵽TOP(InnP)ľС.Ӵ˶˵TOP(InnP)Ϊ⻷OutPڻInnPͨ.
3.3.2 ȨľֲŻǻ
ƽεʷֿɲþֲ̰ʷ֡Kong㷨㷨.ĲԼƵƽ̬ȾֲŻǻ.
νƽ̬,εԲ뾶Բ뾶֮.ƽ̬׼Ԫ񻮷񻮷Ҫб׼.15Circle׼ԼС׼ȼ,Delaunayǻ.,ǽô˸ζȨֵ,ƶʷõ̬.
㷨ʹû֯ζ,εаļ.Ϊƶʷõ̬,㷨ӴС˳Ȩֵ.Ȩֵ:j0Ϊ,j0ȨֵΪ0;,ѭ˳ȡj0ڶj0-1,j0+1,Φj0-1j0j0+1ƽ̬Ratio(j0-1j0j0+1)ΪõȨֵ.Ratio(j0-1j0j0+1)ļ.
Ratio(j0-1j0j0+1)=cos(Ϧj0-1j0j0+1)+cos(Ϧj0j0+1j0-1)+cos(Ϧj0+1j0-1j0)-1. 
ڶεʷֹ,ÿȡеͷӦjʷֲ.ö㼰ڶj-1,j+1ɵΦj-1jj+1е,ʷֳɹ.ͶɾjӦ,¼ڶj-1j+1͹ԼȨֵ,¼ĸȨֵȨֵ,ظϲֱȨֵΪ.,ȨֵеһӦʷֲ.
4 ʵ
ͨ㷨,ǵõûڵԭģͶӼɵԭȫֹģ͵ļģ.roomģͺofficeģ֤㷨(ͼ27ʾ),ӦģͻƵЧͼ.

ͼ2ԭģroomͼ3=0.1,=2

ͼ4=0.8,=50ͼ5ԭģoffice

ͼ6=0.06,=1ͼ7=0.8,=4
ͼ34ֱǦ=0.1,=2=0.8,=50ʱ,㷨roomģͼ򻯵ĴͲЧͼ.пԿ,ûƵķſ,ȹģ͵ļ򻯳̶֮,Ĺֲܷڵһ,λԱ仯ûΧڵӰƬ಻ΪΧƬϲ.Ƕofficeģͽͬʵ.=0.06,=1=0.8,=4Чͼͼ67ʾ.
ģ͵,ǻ㷨ڦȡֵ2ʱ,㷨ļ򻯳̶ű仯̬ͼԼ㷨ڦȡֵ0.8ʱ,㷨ļ򻯳̶ı仯̬ͼ(ͼ811ʾ).

ͼ8ģroomļ򻯳̶
ű仯̬ͼ(ģ2)ͼ9ģofficeļ򻯳̶
ű仯̬ͼ(=2)


ͼ10ģroomļ򻯳̶
ı仯̬ͼ(=0.8)ͼ11ģofficeļ򻯳̶
ı仯̬ͼ(=0.8)

5  
ĸ۵Ӿصͷȼص,Ա仯ֵΪ׼,Ƭϲ򻯲Ա仯û巶ΧڵƬϲ,ʵַȫֹģ͵ĵ1,ԭģͶRGBֵı仯һӴģ͵ļ,зȫֹЧĶϸڲģ.㷨Чؼ˷ȫֹģ,ܽϺõرԭģ͵.㷨ûƵķſ,ģ͵ļ򻯳̶֮.㷨.
оõȻѧ.
߽ܣѧ,Ů,1968,ʿ,ҪоΪͼѧ,ʵ.
,1947,оԱ,ʿʦ,ҪоΪͼѧ,д,ʵ.
ͨѶϵ:ѧ, 100080,йѧԺоѧʵ

ߵλѧۡйѧԺоѧʵҡ100080
йѧԺоѧʵҡ100080Ŵѧѧϵ
ο
1Peter Astheimer. Virtual design: a generic V.R. system for industrial application. Computer & Graphics, 1993,17(6):671678
2Cohen M F, Greenberg D P, Immel D S et al. An efficient adiosity approach for realistic image synthesis. IEEE Computer Graphics and Application, 1986,6(3):2635
3Campbell A I, Fussell D S. Adaptive mesh generation for global diffuse illumination. Computer Graphics(Proceedings of SIGGRAPHICS'90), 1990,24(4):155164
4Schroeder W J, Zarge J A, Lorensen W E. Decimation of triangle mesh. Computer Graphics(Proceedings of SIGGRAPHICS '92), 1992,26(2):6570
5Heckbert P. Discontinuity meshing for radiosity. In: Chakmers A, Paddon D eds. Proceedings of the 3rd Eurographics Workshop on Rendering. Bristol, UK: Consolidation Express, May 1992. 203226
6,Ȩ.׼Ķģͼ򻯷.ѧ,1996,19():
212223(Zhou Xiao-yun, Liu Shen-quan. Polygonal model simplification method based on feature angle criterion. Chinese Journal of Computers, 1996,19(supplement):212223)
7־,С,ʯӢ.⻷жϸڲģԶ㷨.ѧ,1996,7(9):532536(Pan Zhi-geng, Ma Xiao-hu, Shi Jiao-ying. The automatic generation algorithm for models at multiple levels of detail in virtual reality. Journal of Software, 1996,7(9):532536)
8Hoppe H, DeRose T, Duchampn T et al. Mesh optimization. In: Proceedings of SIGGRAPHICS'93. Anaheim, California: ACM SIGGRAPH, 1993. 1926
9Kalvin A D, Taylor R H. Superfaces: polygonal mesh simplification with bounded error. IEEE Computer Graphics and Application, May 1996,16(3):6477
10Turk G. Re-tiling polygonal surfaces. Computer Graphics(Proceedings of SIGGRAPHICS'92), 1992,26(2):5564
11Hamann B. A data reduction scheme for triangulated surfaces. Computer-Aided Geometry Design, 1994,11(2):197214
12Eck M, DeRose T, Duchamp T et al. Multiresolution analysis of arbitrary meshes. In: Proceedings of SIGGRAPH'95. Los Angeles, CA: ACM SIGGRAPH, 1995. 173182
13Hoppe H. Progressive mesh. In: Proceedings of SIGGRAPHICS'96. New Orleans, LA: ACM SIGGRAPH, 1996. 97108
14Merlin H, Anselmo A L, Edward S. Simplification of global-illumination Mesh. Computer Graphics Forum(Proceedings of Eurographics '96), 1996,15(3):339344
15 ,ʥ.άDelaunayǻ̬.ѧ,1994,17():2025(Min Wei-dong, Tang Ze-sheng. Maximum average aspect ratio property of the 2D delaunay triangulation. Chinese Journal of Computers, 1994,17(supplement):2025)
1997-11-04յԭ,1998-02-18յ޸ĸ 
