
Computer Engineering
1999ꡡ259ڡVol.25 No.9  1999



й߸еݻֲ
ӹ
ժҪһµĳݷָԴصݵЧָ˷äĿָĹڴƵӶСͨſ
ؼʣй߸٣Чʣݷָ
Data Partition Strategy for Parallel Ray Tracing
Liu Min Dong Yuyu Zhang Yanyuan Hu Zhengguo
(Software Engineering Center, Northwestern Polytechnical University, Xian 710072)
AbstractFor the purpose of improving the efficiency of parallel ray tracing, the authors proposed a new strategy for scene data distribution according to the traced pixel. This method lowered the frequency of data exchanges between processors, and then reducced communication overhead.
Key wordsParallel ray tracing; Parallel efficiency; Data partition
߸ΪһʵͼεĻƼܹɴͳͼѧ㷨ģЧ㷨򵥣ʵ֡Ȼͳ㷨ټεĹ뾰㣬ŻߣӴļķҲ֮80ڣŲдķٷչ۴ǴӲ϶ΪͼɵĲдṩǿ֧֡߸㷨ĲлǲдʵͼϵĲ
ڶӵ㵽صĸߵĸٶԶ߸ٵĲлǺȻġоصŻص㡢ڲлڵϵķԣԴ߲Чʡݹ۽10ϽϳĹ߸ٲ㷨,ҪΪࣺһݵĲлصǹڴڵ֮ÿص㣨һģƵĲлڴ䶯̬طصĲص㣬һвֳݡ
DidierKadi1994ƵĲй߸㷨УռݽطеĴԼĳҪʵݲڱľִʱͱԶ̷ʴϵݡDidierȻCacheԼԶ̷ʵĴۣǴһԵȱݣݷָäĿԡָòãڼ£ܻصĶ󣺴֮Ƶؽݣʱòȶϵͳͨſ
ͨоص賡֮ڹϵһµݻֲԣȷһĹҪôһڱִеĳǵӿռУҪôռ䡣
1µݻֲ
ͼ1չʾ˴ص볡֮Ŀռϵ

ͼ1ص볡ݵĿռϵ

ͼ2ռĲ״ָ
Զ׼ӵ㷢ĵһ߾ĻӰһصͶϵռУֻֿܣҪôڳռеӰϣҪôռ䡣ۣ
(1)ǹԣӵߣĻڵصʱܿ볡ͬһཻ
(2)ĳĻӰصļִУͱӵгռӰǲ㳡ݿռ֧صĹ߸ټ㡣
ɴˣɵõһݻֲԣĻص볡ռڶĶӦϵв״ָȻѸ˳
ʵӦУӵ㡢Ļռߵλùϵͼ1ʾйɡӵλϵеһ㣬ĻλúͷλҲġһΪ˾ʵʼֵĻλӵǰˣͬһӵλõĲͬĻϳֲͬĻ档ͳõĳΧͼ2ʾĳ塣Ϊ˱ڳռĲ״ָռǷλӵλõĲͬͬͼ2ʾӵλûȷԺ󣬳ռʵʾ壨볤ļιϵԽȣӵͬһ򣬹ʿɳ徭򵥼α任ãĻһƽ棨Ʀƽ棩ƽСʱӵ㡢Ļռ2λùϵͼ1ͬԷضԳռв״ָ
ʱɾʵǰݻֲԡȶĻصΪλλ֣Ӳ벢дĴnĻֳnݣ϶ΰص㼯˳ŵĴӵĻϸֱ߽߹ɵƽ潻һϵнߣЩߣԴֱڦķԽռ2ָɲ㣬ÿһ㶼ӦĻ֮Ӧͬǰn㳡ռ˳nݷָ䣬ʹñϷصһڽмʱʵһڱľִУԽоֲʣԶ̷ʡ
ݿռ䱻ָɿ飬ÿֻӵռһ֣һȻȷ뱾ĳӿռ䣬ཻ󣬽һߣ͸䷽Ĺߺط䷽ĹߣҪǷֱй߸٣ЩĶ߾пĳӿռ䣬洢ڱĴϵһӿռ䡣ҪһٵĹߴݸһԱ١
˳ĳӿռ֮ŶӦϵԼ򵥵ΪiŴϴ洢˵i㳡ӿռ䡣׿Ӳֻϴ洢ĳӿռĻЩ˳͹ռ䡣ˣ
(1)iŴݿռϱʱùҪôռ䣨ڵ1ŴԣҪôi-1Ŵ洢ǲֳݿռ䣻
(2)iŴݿռ±ʱҪôռ䣨ڵnŴԣҪôi+1Ŵ洢ǲֳݿռ䣻
(3)ϳݿռʱǰұ棩һռˡ
3㣬ݿռʱ˹ߴݸĸһӭжˡ
2
ĳݻֲо˴ص賡֮ڹϵĻģ˷äĿָĹڴ֮ƵС˲й߸㷨еͨſһӦһЩ򵥵ĲͼδϵͳУЧܺáϵͳ죬ԽһĽԲͬ˽ṹĲмӦͨԽõߡ
߼飺(1970)ŮʦҪо򣺲д
ߵλҵѧģ710072
ο
1 Didier B. Distributing Data and Control for Ray Racing in Parallel. IEEE CG&A, 1994, (7):69-77
2 Chuang Junghong. A New Space Subdivision for Ray Tracing CSG Solids. IEEE CG&A , 1995, (11):56-62
3 Scott W. Recent Developments in Parallel Rendering. IEEE CG& A, 1994,(7):21-22
ոڣ1998-12-15
