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



ɴģӦõķȼԶ񻯷
ơҹ
ժҪ񻯳ЧؽзȼҪǰ.еҪʷַϸַӰ߽㷨.ǰڱҪʱԴƬԶϸ,ȽӰ,ȻӰ߽л.ǰߴڵ޷ڴƬмϸڱ仯,Ƶò֤.һַ־ڻֻܴγ,Ҽʱ䳤,ʵָ,ڹϽӦ.һ񻯷,ģӦ,,ɽϸͼ.ַȽ滮ֳ㾫ҪϸСԪ,ȻݸԪԳиԴĿɼкϲ,ʹ仯ͬԲͬСĳߴʷ,,ڼƬ,ͼûԵĽ.ʵͳݱ,˷򵥡Ч,ʺϴģĹӦ.
ؼʷ,Ƭ,Ԫ,.
ͼšTP391
An Automatic Meshing Scheme for Radiosity Calculation of Large-scale Application
CHEN Yan-yun1WU En-hua1,2SUN Jia-guang3
1Laboratory of Computer ScienceInstitute of SoftwareThe Chinese Academy of SciencesBeijing100080
2Faculty of Science and TechnologyUniversity of MacaoMacao
3Department of Computer Science and TechnologyTsinghua UniversityBeijing100084
AbstractProperly meshing a scene model is an important precondition to efficient radiosity calculation. There are basically two existing meshing strategies, subdivision method and shadow boundary calculation method. By the former method, large patches are automatically subdivided while necessary, and in the latter method, meshing is performed along the shadow boundary of the regions and the shadows in the scene are analytically pre-calculated. The problem in the former strategy is the detail between vertices of a big patch could be missed, so the rendering quality is unable to be assured. On the other hand, the latter approach has a limitation of being primarily applied to polyhedral scenes, and its complexity of implementation and the requirement of heavy computation also prevent itself from being applied in engineering applications. In this paper, the authors present a meshing scheme, with a primary destination towards large-scale engineering applications with a property of easy implementation and high efficiency in producing high quality images. By the scheme, they first divide the energy-receiving surfaces into small elements with a desire precision and then recombine the elements according to their visibility feature to the light source within the environment. In this method, the regions in different energy distribution could be meshed by different scale. As a result, the number of patches to be calculated is greatly reduced without degrading the image quality. The implementation and the statistics from test examples show that the scheme is particularly suitable for large-scale engineering applications due to its ease of implementation and high efficiency.
Key wordsRadiosity, patch, element, meshing.
ʵͼεķȷǽи񻯳Ƭ(patch),ͨƬֱ֮ƽӽƽƳ.,㷨ĺûֱӰ쵽ȷЧ.
򵥵񻯷һĳߴԳеͳһĻ.ַȻʵּ,ڽлʱûпǸϵֲ,ҪﵽȽЧ,뻮ֵ÷ǳϸ,ڴҪ,ҼʱҲܳ.
ڳ,оֲͬ㷨.Cohen1986ӦŻ㷨1,㷨ƬԪ(element)ṹ.˼,Ƚи滮ֳƬ,г,ĳЩƬ仯ֵ,ͶԴƬһϸ,ϸõԪԭƬйռ.ַŵʵּ,Եض仯Եϸ.ȱֻǸ֮,޷ڶ֮ϸСӰ,ͼ1(a)A.

(a) Cohen㷨ϸֽ(b) 㷨ĺϲ
ͼ1Cohen㷨뱾㷨ıȽ
˺,Campbell2,Lischinski3,Drettakis4ݺStewart5ݵýӰı߽,ɴԲͬƽ񻯷.ΪϵӰ߽׼ȷλ,һǵӰıӰ߽ͰӰ߽紦ɵĸֲ(discontinuity),Щõ˺׼ȷļ.Ϊ˸ӰıӰͰӰ߽,Щ㷨˱Ƚϸӵݽṹ.,BSPԿռ˹ϵ,ð㡢ߡ໥ϵϢ߽ṹ(winged-edge)¼񻯵м״̬ͽ(߽ṹ,Ϊ˼ӿӲ,ݴ洢6),,̸,Ƭʱ䳤,ĿǰӲ,ڹϵõʵӦ.,֪,ڹеӦ÷ǳ㷺,ЩDrettakisᵽĿԴ,ǿֻɴιɵĳ,͸ʵӦõҪ.
Դ,һִԪƬ񻯷.ɢķ,ȱ˸ӵĽȡӰ߽,ʡ˼ʱ,ܴĳü򵥶Чĺϲ㷨,ʹӰ߽õϸµķӳ,ʹǱ߽粿ֵ԰ϴߴ绮,ԱԽٵʱɸͼ.ʵ֤,һʺϴģӦõ񻯷.
1㷨Ļ˼
ڹԴԳķֲҪ,,㷨15һ,ֻǹԴӰ.˼ȽԴֳƬ,Ȼ󽫸滮ֳԪ,ȷԪԸԴƬĿɼ.ԴΪݽԪϲƬ,ͬʱںϲĴСƬ֮νй,ԱTζ(T-vertex,ף7,8).ΪõǴСкϲķ,ͼ1(a)ʾ(ͼ1(b)ʾ).ϸ㷨ĸ.
1.1Դ
ΪԴֲһǾȵ,ֻм򵥵ͳһߴĻ,ʹ䲻Χ.취ȼԴ֮̾,Ȼ屶ԭ(the Five-times Rule)л֣8.
1.2hs-buffer
Ϊ˼ȷԪԸԴƬɼԵļ,ǽhs-buffer¼ԴƬԳиĿɼϢ.£Դ񻯺,ÿԴƬϽһhemi-cube,Ȼ󽫳еЩhemi-cube͸ͶӰ,z-buffer,ͬòͬıż(ǳ֮ΪSurfaceID).ͶӰһŶά,Ŷάhs-buffer.жٹԴƬ,жٸӦhs-buffer.hs-buffer,ȷԪĳԴƬĿɼʱ,ֻҪһͶӰһζάҾͿ,Ҫӵļ.
1.3ȷԪйԴƬĿɼ
ÿҪ񻯵,Ƚ仮ֳСĵԪԪ.ԪĴСûԾȵҪȷ.ߴ̫,޷׼ȷϸ,ͼεҪ.Ԫߴ̫С,Ӵ洢,ٶ,óõhemi-cube״(Form-Factor),hemi-cubeֱصļ9.,ԪĻֳߴҪ֤ںϲƬ,СƬ(ͨԪ)ڼ״ʱ,hemi-cubeֱʲƬļͷֲ(屶ԭ)ķΧ֮.
滮ֳԪ֮,Ϊ˼,ǼٶԪ㹻С,ĳԴƬĿɼֻȫɼȫɼֲͬ.,ɼԿ·ȷȻԪеԴƬhemi-cubeͶӰ,ͶӰõĶάҶӦhs-buffer,õSurfaceIDΪԪƽSurfaceID,ԪԸùԴƬǿɼ,Ϊɼ.ȷĳԪйԴƬĿɼԺ,¼һؼVKey,ΪԪϲƬĸ.Ϊɼֻȫɼȫɼ,,ÿԴƬĿɼVKeyֻռһbit.ؼֵĳɹԴƬĿ.
1.4Ƭϲ
Ϊ˼ٴ洢,ӿֲ,ǽԪϲƬ.ݵǸԪɼԹؼVKey.ǲĲԪƬĲνṹ,һΪPchTypeĹؼʶͬһڵ4ӽڵϲķʽ.ȷPchTypeֵ,ȻPchTypeֵ,ͬһڵ4Ԫ(Ƭ)кϲ..
1.4.1ݽṹ
Ϊ˼򻯺ϲ,ԪΪҶӽĲṹ.ȿԸƬߴԪߴȷ,ǵľ,һΪ34.ͬһڵ4ӽڵֱΪTL,TR,BL,BR,ͼ2ʾ.

ͼ2 Ĳṹ
ؼPchTypeʶϲķʽ.ΪĲṹ,ͬһڵֻ4ӽڵ,ֻҪ1ֽڵĵλԱʶ,,PchTypeֽbit4bit7Ϊ,bit0bit3ֱͼ2еp0p34.1ʾ.
1ؼPchType

bit7bit6bit5bit4bit3bit2bit1bit0
p3p2p1p0

bit0Ϊ0,p0Ϊ0,ʾöȡ,ӽڵTLTRԺϲ,ʾTLTRܺϲ.ͬ,p1,p2,p3ȡֵҲӳӦӽڵܷϲϢ.
ͬʱ,ǵԪҪ洢ɼԹؼVKey,Ƭ(Ԫ)ĲݽṹɶΪ
struct pTree{
charPchType;
VKey typeVKey;
struct pTree*TL,*TR,*BL,*BR;
} 
1.4.2PchTypeؼֵȷ
PchTypeȷҶӽڵĸڵ㿪ʼ,ͬһڵ4ҶӽڵVKeyڵҶӽڵVKey.ȿͬһڵ4Ҷӽڵ,PchTypep0ӦλֵȷΪ(ͼ2ʾ),TLTRVKeyͬ,Ҳ˵,TLTRӽڵԸԴƬĿɼԲһ,˵TLTR֮бȽԵ仯,ӽڵ㲻ܺϲ,p0ӦĶ㲻ȡ,,PchTypep0ӦλӦΪ1.֮,TLTRVKeyͬ,˵ǶйԴƬĿɼԶһ,֮䲻Ե仯,ҶƬӽڵԺϲ,p0ӦĶȡ,Ӧ,PchTypep0ӦλӦȡ0.p1,p2,p3ֵȷp0.ɴ,ǵõ4ж䣺
(TL->VKey!=TR->VKey)?p0=1:p0=0;
(TR->VKey!=BR->VKey)?p1=1:p1=0;
(BR->VKey!=BL->VKey)?p2=1:p2=0;
(BL->VKey!=TL->VKey)?p3=1:p3=0.
ٿǷͬһڵҶӽڵ֮໥Ӱ,ڵķͬһڵҶӽڵ໥ӰΪ(ͼ3ʾ).ҶӽڵTRLVKeyұҶӽڵTLRVKeyͬ,˵֮бȽԵ仯,,p0Lp0RӦĶ㶼ȡ,ȷ㾫Ⱥͼ.ͬ,BRLBLRӦp2Lp2RҲƵ.ڵķͬһڵҶӽڵVKeyҶӽڵĸڵPchTypeӰжɣ
if (TRL->VKey!=TLR->VKey)p0L=p0R=1;(1)
if (BRL->VKey!=BLR->VKey)p2L=p2R=1.(2)
ͬ,ڵķͬһڵҶӽڵVKeyҶӽڵĸڵPchTypeӰҲƵж.

ͼ3 ڵķͬһڵҶӽڵ
Ҫڽڵ໥Ӱ.ڵPchTypeؼp1LΪ1,ҽڵPchTypeؼp3RҲӦΪ1,Tζ.֮,p3RΪ1,p1LҲӦΪ1.ڵĽڵҲҪӦ޸.
ӽڵҶӵĽڵ,ȷPchTypeؼֵֵĲӽڵVKeyؼ,ӽڵPchTypeؼǷΪ0ȷ,£ȽPchTypeؼ0,Ȼ4ӽڵһж,ĳӽڵPchTypeؼΪ0,ʾӽڵ4ӽڵѺϲһƬ,ɽһϲɸƬ,PchTypeؼûκӰ죻֮,ĳӽڵPchTypeؼֲΪ0,˵ӽڵ4ӽڵ㲻ȫϲ,ɸƬ,Ҳڵһĺϲ,ԽڵPchTypeؼصλ1,Աʶص㲻ȡ.,ǵõ4ж䣺
if (TL->PchType!=0)p0=p3=1;
if (TR->PchType!=0)p0=p1=1;
if (BR->PchType!=0)p1=p2=1;
if (BL->PchType!=0)p2=p3=1.
ͬ,Ҫڽڵ໥Ӱ,Tζ,Ҷӽڵ㸸ڵ.
1.4.3 
ȷĲڵPchTypeؼԺ,ͿԽкϲ,ϲҶӿʼ,ݵľPchTypeؼ.ǰ,PchTypeؼֻõλ,,һ16͵ĺϲ,еλΪ0ʱ,Ĳڵ,ͽ4ӽڵϲһƬ.ǷǸڵ,4ӽڵϲ,ǷƬ丸ڵPchTypeؼֶ.ף10,15ֺϲͼ4ʾ(ͼбPchTypeؼֵλĶ,ʵ߱ʾϲĽ).

ͼ4 ƬԪĺϲ
2ʵ
ͼ5ñĽܵ㷨ֱԪΪƬзõĽıȽ.ͼǿԿ,ñĽܵ㷨ʹƬĿΪ,ͼûн.


ͼ5Ľܵ㷨ֱԪΪƬıȽ
ͼ6ñĽܵ㷨ȽϸӵĴγͰBzierתĳ񻯵߿ͼ.Ӱ߽紦ƽ滮ֵñȽϸ,طȽϡ.


ͼ6ñ㷨ӵĴγBzierת
ͼ7ǽĽܵ㷨ڸӳ,SGIͼιվIndigo2ϽõĽ,ͳ2ʾ.



(a) ֱԪΪƬõĽ(b) Ľܵ㷨õĽ
ͼ7Ľܵ㷨ڸӳ
2ͼ7ͳ


θԴ
Դ
ƬƬ
Ŀ
ʱ(s)ռ
ʱ(s)
ʱ(s)
ԪΪƬ(ͼ7(a))114451474481037393739
ñĽܵ㷨(ͼ7(b))11445142020217790807

ϱͳݼ(ͼ7ʾ),ñĽܵķֱӲԪΪƬķȻƬĿͼʱкܴ,ͼȴδԲͬ.ɴ˿ɼ,Ľܵ㷨ǼЧ. 
3 
ڳ񻯵,רҺѧڹȥ10ʱֲͬĽ.Щ¿ԹΪϸַӰ߽㷨.Campbell,LischinskiGeorgeõӰ㷨24,Cohenõϸַ1,µķϲ.
Ӱ㷨ŵ,Ӱı߽绮׼ȷ,ֲļҲȽϾȷ,ͼ.ȱ,,ٶ,ǶڹԴȽ϶ĳ.ӸиͳݿԵؿCampbellף2иͳݱ,ף2ݽܵ㷨ƽ񻯷ʱǹռʱ10ϣLischinskiף3нܵ㷨ƽ񻯷Ҫף2㷨ö,Ҳӽڹռʱ.ϸַȻͼԶԲӰ㷨,ȴмٶȿ,̼,ʵֵŵ.ĺϲϸַ洦,ͬϸַĸŵ,ұϸַ׼ȷ.ʵ,Ľܵ㷨Ч,ʺڴģӦ.
ƪϵ,ֻıε㷨,һ㳡Σεı֮,ֻҪ㷨޸ļ.ƬĲʷͼ8ʾ.

оõȻѧ͹ҡ塱صƼĿ.
߳,1971,ʿ,ҪоΪͼѧ,ʵͼ.
,1947,ʿ,оԱ,ʿʦ,ҪоΪͼѧ,ʵ,ѧӻ.
ҹ,1946,,ʿʦ,ҪоΪCAD/CAM,ݿ,ͼѧ.
ͨѶϵˣ, 100080,йѧԺоѧоʵ
ߵλơйѧԺоѧоʵҡ100080
ŴѧƼѧԺţ
ҹ㡡廪ѧѧ뼼ϵ100084
ο
[1]Cohen M, Greenberg D P, Immel D S et al. An efficient radiosity approach for realisity image synthesis. IEEE Computer Graphics and Application, 1986,6(3):2635
[2]Campbell III T, Fussell D S. Adaptive mesh generation for global diffuse illumination. Computer Graphics (Proceedings of the SIGGRAPH'90), 1990,24(4):155164
[3]Dani Lischinski, Filippo Tampieri, Greenberg D P. Discontinuity meshing for accurate radiosity. IEEE Computer Graphics and Application, Nov. 1992,12(6):2539
[4]Drettakis G. Eugene Fiume A fast shadow algorithm for area light sources using backprojection. Computer Graphics(Proceedings of the SIGGRAPH'94), 1994,28:223230
[5]Stewart J A, Ghail S. Fast computation of shadow boundaries using spatial coherence and backprojections. Computer Graphics (Proceedings of the SIGGRAPH'94), 1994,28:231238
[6]Glassner, Andrew S. Maintaining Winged-Edge models. In: Arvo J ed. Graphics Gems 񪢢. San Diego: Academic Press, 1991
[7]Cohen M F, Wallace J R. Radiosity and Realistic Image Synthesis. Boston: Academic Press, Inc., 1993
[8]Ian Ashdown. Radiosity: A Programmer's Perspective. New York: John Wiley & Sons, Inc., 1994
[9]Wallace J R, Elmquist K A, Haines E A. A ray traciing algorithm for progressive radiosity. Computer Graphics (Proceedings of the SIGGRAPH'89), 1989,23(3):315324
[10]Baum D R, Mann S, Smith K P et al. Making radiosity usable: automatic preprocessing and Meshing techniques for the generation of accurate radiosity solutions. Computer Graphics (Proceedings of the SIGGRAPH'91), 1991,25(4):5160
1997-10-20յԭ,1998-05-28յ޸ĸ
