о뷢չ
JOURNAL OF COMPUTER RESEARCH AND DEVELOPMENT
1999 36 8 Vol.36 No.8 1999



άѹоչ
ϼ־ʯӢ
ժҪάѹָάģݽѹԱģݵĴ洢紫䣬ڷֲʽʵЭͬӦáûƵϷģڼڲĴ洢ʹŷǳҪ.нάѹ򵥷ֱģ͵ѹֱģ͵ѹв˵ǰµоչĿǰдڵоǰ.
ؼʡѹͨ۽۽ɭʷ 
ͼšTP301.6
STATE OF THE ART OF 3D GEOMETRY COMPRESSION
YAN Li-Xia, PAN Zhi-Geng, and SHI Jiao-Ying
(State Key Laboratory of CAD & CG, Zhejiang University, Hangzhou 310027)
Abstract3D geometry compression is the technique which aims at the compression of model data in 3D scenery. It is important for distributed virtual realityco-operation, and multi-player video games, as well as for storing and transfering data in computer. A 3D geometry compression method is introduced in this paper. Existing methods are classified into two kinds according to their usage for single-resolution model and multi-resolution model. The recent achievements of 3D compression are discussed and the existing problems are analysed.
Key wordsgeometry compression, generalized triangle mesh, progressive mesh, progressive forest split
1
ſѧķٷչ缰Ӧüо룬ýͨżȡ˾޴Ľչ.ýͨǶý弼ͨżлϣǶöýʾļɴϢбʾ洢ʹ.ýͨżĳִ˼֮ͨľ룬ڼĽԡͨŵķֲԺ͵ӵʵΪһ.ڶýͨУͼƵԼƵѹѹ˹㷺оһЩʵʿеķάͼݵѹоȽ.
άѹָάģݽѹԱģݵĴ洢紫䣬ڷֲʽʵЭͬӦáûƵϷģڼڲĴ洢ʹŷǳҪ.ʵάͼεϢʱҲǳ󣬸洢ʹصϰѹӦе紫似һЩʵʱӦóϸҪѹ֧.
ڼͼѧУάʱͨöʾģ.һʾģͨ3ɣ ݣλꣻ ϵÿĶ㼰֮ϵ ԣɫ淨ȵ. ѹԵҲ⼸ֵ.ڵǰодʹõɵģͣεͨʽṹԼӲ֧.ͼݵӴ洢ʹ䶼˺ܴѣӰһЩӦãֲʽʵЭͬӦãʵ.
1995Sun MicrosystemsMichael Deering1SIGGRAPHϷһƪΪGeometry CompressionѹĺάѹʼܵѧעȡһЩ½չ.Ľǵоֱ򵥷ֱģ͵ѹֱģ͵ѹ.
2ֱģ͵ļѹ
ֱģ͵ļѹָһֲϸڵĶʾʽļݽѹ.еоУMichael Deering1ݵĻͨļѹStefan Gumhold2ݵӹϵʵʱѹ㷨Gabriel Taubin3ݵĻļѹ㷨д.ļݱʽ3㷨Է.
ռõĴ洢ռ.򵥵ķÿζ39øҪ36ֽһΣҲɫݣֱʹÿԼ豻6Σ˷˴Ĵ洢ռ.һָĽķǶηֿʾ.ÿ3ʾλȷÿΣʾÿε3.ʹô洢ռõ̶ܴȵĽʡ.һ˲ҪĶ㴫䣺ڵιһߣôӵڶοʼһ¶ļǰһεһ߼ɹһΣʹÿ봫.
2.1ͨļѹ
Сÿ豻õĴ6ν2ңһεĴԸģ˵Ƿǳ.Michael Deering1ݶıʽ˽һŻͨ񣬲ڸñѹ㷨ҪΪ4
(1) תͨʽ
ͨһŻݱʽһֽյļαʾͬʱݵԽṹҲ˵ԿͨһζԶݽṹɨȡ.Ϊ˱ԾɶظȡDeering˶㻺壬ɶʽһУٴõʱʽ.16ɶĻ弴ɱ94%ľɶظȡ.


ͼ1ͨ
(2) ÿλԼɫ
ڶλУDeeringԷĴ˼֮˼ηֲĶԳ.ȵλɷΪ81/8򣨿ñ־λÿ1/8壩Ȼֱͨ۵ƽX=YX=ZY=Zɽÿ1/8ٷΪ6.Ĵֻ֮1/48Ҫһ䷨򣬼ʹ÷ұԭ100000Ϊ2000.


ͼ2ļ򻮷
(3) ڽ꼰Ĳֵ
ڼʵľֲԣ16λģͿռУһڽֵԶԶ16λӦԣʹҪռõĴ洢ռõһ.ͬɫȻɺͷƽӣRGBNҲʹڽֵ֮б.
(4) Ե3õݽHuffman
λĲֵûڱǩĿɱ䳤Huffman,Ӷõѹļ.
Deering ѹ㷨Ҫصͨö㻺ʹö꼸ظ.ʵʲУͨǱȽѵ.Deeringļѹѹȿɴ6/110/1ʧȽСѹ.
2.2ӹϵʵʱѹ
ӹϵʵʱѹһ򵥷ֱģ͵ѹɵ¹TbingenѧGumhold2ݵ.ַУͬʹ˶㻺壬ѹбDeering. DeeringͨıܿӹϵGumholdӹϵһϵеĴö㻺ʹÿֻ贫һ.
ӹϵʵʱѹ㷨·Ϊ¼裺
(1) ȷ˳
ͨ˳򣬿ȷȣdepth-first strategyǹȣbreadth-first strategy.
(2) ӹϵ
һϵеĴ硰ʼӣǰӣ*¶㣻.߽磻iи߽磻Uipи߽ϣպи߽磬ʹεӹϵɱȷ벢λ.
(3) ݴ
ݣλáɫȣӦλγϢɱЧ.
Gumhold㷨̶ͨı˳ʹöԻС.ЩHuffman 룬ôÿεӹϵֻλ.Gumhold㷨ṩ˿ٵѹʹö㻺壬ӶڻСΪ12.72ʱ֤ÿֻһ.ѹͽѹʱȽΪ2/1Ҫδѹȡʾʽ.ң÷ѹҪڻͨѹ1ֱַ5ֲͬѹ˱Ƚ.
1ӹϵʵʱѹͻͨѹѹȱȽ

ģԭʼС(bits)ѹ
ͨѹӹϵѹ
triceratops179,7045.8/17.4/1
galleon155,0648.2/111.2/1
viper1,698,1168.6/111.6/1
cherry958,1609.2/112.0/1
insect8,383,7887.2/111.4/1

2.3ļѹ
Gabriel TaubinJarek Rossignac3ݵĻļѹ㷨ҲһԵֱģ͵ѹ㷨.㷨˶ĸ.ӹ춥ضиõı뼴õӹϵ.㷨ԶѹDeeringڽֵѹһ.ѹ㷨.
(1) 춥
ѡеһΪĸڵ㣬ýڵĵͨΪһ߽.ƣNξǲСNκβ㣬ҰһN߽綥μ.ڣN+1߽ǵNЩڵN߽бɵ.Щ߽ߵϲһÿ߽綼ɻɣÿβҲΧһܵɵ.ĹͨЩת״ʵ.ʹķ֧ٵǰ£ѡN߽еһN+1߽еһӳΪԽߣɽб߽绷ͨɶ.ͼ3ʾ.


ͼ3춥
(2) 
붥ʱѡĸڵ㣬Ԥĸ֧.ÿһ֧3־λ룺run length,branching bit,leaf bit.
(3) ѹ
ѹӦ˶ڽֵԣÿԤֵͽֵ֮Ĳֵ.ԤֵǴ˶Ӧرǰֵ.
(4) 
ıΪrun length, leaf bitrun length÷֧бߵĿĿ1leaf bit־÷֧յǷΪһҶΣз֧.
(5) ѹнģʽ
ʱı˳ѾȷнģʽɱʾΪһϵұı־λر. 
㷨ӹϵѹģԶѹѹ.ѹȸǰѹ㷨ͨɴ50/1.
ڱн3򵥷ֱʵļѹ㷨ϸ֮ѹĸָȽ2ʾ.
23ּѹܱȽ

ѹ㷨ѹѹѹ/ѹʱ
ӹϵ
ͨļѹ6/110/13/1
ӹϵļʵʱѹ8/112/12/1
ļѹ50/135/1


3ֱģ͵ļѹ 
ֱģ͵ѹֱģ͵ѹ.ֱģͿɷΪɢֱģͺֱģ.ɢֱģǶԸӵͨ㷨𲽵õͬϸڲεĶģֱͣģͨһֽյģͱʾֱͬʵģ.ֲͬģֱͣģ͵ѹֿɷΪɢֱģ͵ѹֱģ͵ѹ.ľߴԵStefan Gumhold4ݵȵɢֱģ͵ѹGabriel Taubin5ݵȵ۽ɭʷ㷨.
3.1ɢֱģ͵ѹ
ɢֱģǶԸӵ񾭹һϵм򻯲õ˶ֱͬʵĶģ.ּ㷨ͨʩԾֲı仯𲽵õͬϸڲ(LOD)Ϊ˱֤ԭʼ㹻ƣÿ򻯲趼õ.GumholdȵɢֱģѹУʹõƼHausdorff룺
dH(X,Y)=max(d(X,Y),d(Y,X))
XYֱΪ㼯ϣHausdorff һ޹صĲ.򻯹УҪ3ּ㷨 ۵(edge collapse)  ۵(triangle collapse)  ȥ(vertex decimation).


ͼ4Ƭκ͹
PuppoȵMTmulti-triangulationGumholdڽһʡ洢ռֲԶֱͨϵͲιϵѹ·õѹĶֱģpbMRM (pattern based multiresolution model.ݽṹҪ3бƬΣfragmentбб͹б.ÿһƬаһӹϵĶϵԼϺµ.ڹбÿŶģʽ(ceiling pattern)͵ģʽ(floor pattern).ڶɢĶֱģѹУԼݡݵѹDeeringѹ㷨ӹϵͲιϵѹ̽.ѹ㷨ҪΪ
(1) еӹϵѹ
Ӧöȥļ㷨һȥӹϵμʾһȥʷֵμףһȥǰμ.еӹϵɹʾÿһģʽһģʽ.
(2) ιϵѹ
pbMRMرڹУιϵƬ֮.ÿһƬһѭָÿƬ˵иƬɵѭбÿĲιϵԼҪ3.47룬MT˵ÿĲιϵԼҪ24.pbMRMĽڲιϵĴϽԼ5.5Ĵ洢ռ.
(3) ƬκͶ
Ƭбб
Ƭ˳ɼ㷨Ƭμ˳෴Ҳ㷨Ƭ˳򣺣Ƭε˳ӦΪ.ȷǰеƬαҪܻƬεӦ㣬ʶ㼯ӦƬμͬ.
ɢֱģѹ㷨Ҫֱͨc.ʹöȥ㷨Уÿ㷨ȥһ㣬ɵĿնʷ֣ԭʼʷֵ֮HausdorffΧ.pbMRMУƬf趨һȫֽΪ䶥Hausdorff..ԭʼ񣬿ڷֱɵöȥķϴֻӶõѹʷ.
pbMRMԴ洢ռMTС6ϸ̺ʹֻÿԲȥ18,000㣬ÿ30֡Ĵٶ˵ÿ֡ɲȥ600㣬ٶȶʵʱ˵ǿԽܵ.
3.2۽ɭʷѹ
Taubin5ݵ1998۽ɭʷѹprogressive forest split compression㷨.㷨˱Hoppe6ݵȵ۽progressive meshΪӵϸܸЧؽѹ.÷صڴ洢ʹ۽ġѹʽŵʱһӦԵľַġͬϸڲεľģ֮Ĺ⻬.
3.2.1ɭʷֲ
ɭʷֿԿǽһϵı߷ѲγΪһϣΪһϵжĲ.ʵʩɭʷֲ١ɭֵıи񣻢ڡ߽·ʷ֣ۡ¶λ.
3.2.2ɭʷѹ
PFSʽеĶֱһʼĵͷֱʵLODһϵеɭʷֲɵ.PFSTStopological surgeryչ죬PFSгʼͷֱģ͵ıõTS.ѹ㷨ʾ.
1 ͷֱģ͵ѹͱ
һֱʵģУλɶر˳ĸöǰͨõ.ݵѹͨ洢ʵֵԤֵ֮Huffmanõ.ʾ

Ц(Vn)ǸöλPnǶλõԤֵVn-1, ..., Vn-kǸöų򶥵·ǰK.
2 ɭʷֲ˳ݽѹͱ
һַΪ3֣
 ɭֵı.ɭֵıÿҪһλ.磺1ñڴɭ֣Ϊ0.Щ־λԱΪѹУ
 Լ򵥶εı.ʷɭֲļ򵥶αۺϲ˱䳤루һmarching bitsͶ루2λһΣѡһ϶̵ıѹУһλ˵õı뷽ʽ
 ԶƫƵѹͱ.λϢԶıΪ˳ѹ.ԺɭʷֲУҲ洢ľֵǴ洢öһвϸڵȫְΧеֵɭʷֲǰ󣩣ȻٽHuffman.ÿɭʷֲӦŲͬHuffman.ÿɭʷֲĶλõı仯ͨȫԤֵһֵ.
3.2.3ֱPFSʽת
ֱתΪPFSʽõļ㷨ǻڱ۵edge collapse㷨Լб۵ı߽ӵԣͨԣб۵.ԷΪ١ñ߽۵µͨǷɼ򵥶ɣڡһΪ϶𰸣Ƿж㱻ڻֹͨ.ڶΪ񶨴𰸣ͨԣñ߿ɽ۵.۵ȶкݽṹ£½жбߵĲԣֱеԪȫΪ.ɭʷֲÿϸTɵT.ô̡ĴֻÿεõеĿԭʼһ.
PFS㷨һӦ֧۽洢ʹ䣬۽ȸӽʡ洢ռ.
4ᡡ
ѹּھԭԵ£ʹ弸ϢҪĴ洢ռΪС.ǰĽ֪ܿоԱоȡ˶оɹ.ǣе㷨ҲһЩ֮до֣̽
1 DeeringͨǽͨչΪһ4λĵַԼһµĲõ.4λĵַ16ʵĶѰַ²ֱӷЩɶ.DeeringѹʽϢʧˣԲܼ򵥵ͬЩϢѹȽ϶Դ洢ռ.⣬ڼѧϣͨͨľսԵļ㼸⣬ʵϣͨεĹܶ·ͼ֤һNPȫ.Ŀǰδйͨоķ.
2 ڷֲʽͼӦУԶֱģͣ۽һǳЧĴʹʩ.÷˼ȴLODһͷֱʵģͣȻڻƲʼͬʱһϵеϸ.ϸLODʾϸLODϢĴͬУ˲Աĵȴʱ.۽ȫ״̬õҪԼ۽ܵٶȵԼʹ۽оչΪ.
о룬ʹüѹ㷨ӳȽ缸ͼδ䡢ֲʽ⻷ӹȵӦ󣬽һƶͼѧǰչ.
߼飺ϼŮ197110ʿоҪоΪͼѧʵý弼.־У196512ڣʿʦоΪͼѧʵý弼.ʯӢУ1937ڣʿʦоΪͼѧѧӻʵý弰ϵṹ.
ߵλϼ־ʯӢ㽭ѧCAD & CGصʵҡݡ310027
ο
1Deering M. Geometry compression. In: Computer Graphics Proceedings, Annual Conference Series. New York: ACM SIGGRAPH, ACM Press, 1995. 1320
2Stefan Gumhold, Wolfgany Stro¡er. Real time compression of triangle mesh connectivity. In: Computer Graphics Proceedings, Annual Conference Series. New York: ACM SIGGRAPH, ACM Press, 1998. 133140
3Taubin G, Rossignac J. Geometry compression through topological surgery. ACM Transactions on Graphics, 1998, 17(2): 84115
4Stefan Gumhold, Reinhard Klein. Compression of discrete multiresolution models. Tech Rep: WSI-98-1. WSI-GRIS, 1998
5Taubin G, Andre Gueziec, William Horn et al. Progressive forest split compression. In: Computer Graphics Proceedings, Annual Conference Series. New York: ACM SIGGRAPH, ACM Press, 1998. 123132
6Hoppe H. Progressive meshes. In: Computer Graphics Proceedings, Annual Conference Series (Siggraph'96). New York: ACM SIGGRAPH, ACM Press, 1996. 99108
7Taubin G. A signal processing approach to fair surface design. In: Computer Graphics Proceedings, Annual Conference Series (Siggraph'95), New York: ACM SIGGRAPH, ACM Press, 1995. 351358
8Schroeder W, Zarge J, Lorensen W. Decimation of triangle meshes. In: Computer Graphics Proceedings, Annual Conference Series (Siggraph'92), New York: ACM SIGGRAPH, ACM Press, 1992. 26(2): 6570
9Hoppe H. Efficient implementation of progressive meshes. Computer & Graphics, 1998, 22(1): 2736
10Schroeder W, Zarge J, Lorensen W. Decimation of triangle meshes. In: Computer Graphics Proceedings, Annual Conference Series (Siggraph'92), New York: ACM SIGGRAPH, ACM Press, 1992, 26, 6570
11Garland M, Heckbert P. Surface simplification using quadric error metrics. In: Computer Graphics Proceedings, Annual Conference Series (Siggraph'97), New York: ACM SIGGRAPH, ACM Press, 1997. 209216
12ʯӢ. ʼͼѧ뽻., 1998-09-21(45)
(Shi Jiaoying. Brief introduction to international conf on computer graphics and interactive techniques. China Computer World, 1998-09-21(67))
13־ʯӢ. ֱģͺάѹ½չ. , 1998-09-21(67)
(Pan Zhigeng, Shi Jiaoying. Multi-resolution model and 3D geometry compression progress. China Computer World, 1998-09-21(67))
14С־ʯӢ. ȥ׼Ķ򻯷. ѧ1998, 21(6): 492498
(Ma Xiaohu, Pan Zhigeng, Shi Jiaoying. Polyhedral model simplification method based on triangle removal criterion. Chinese Journal of Computers(in Chinese). 1998, 21(6): 492498)
յڣ1998-12-15
޸ڣ1999-04-12
