cullip@sargent.cs.unc.edu (Timothy Cullip) (11/16/90)
Has anyone heard of any efficient ways of rotating a 3D data set in a massively parallel SIMD type machine that has both nearest neighbor and global communications capability? I am specifically working with a 4096 processing element MasPar machine (16Kbytes of ram per 4 bit PE), but I would be willing to hear from others. The MasPar connects each PE to its eight nearest neighbors with what it calls an xnet communication network. It also allows PE's to communicate with arbitrary PE's using a global router network (which is slower due to collision contentions). I have been doing some visualization work (volume rendering) using a MasPar SIMD machine that has relied on rotating the data set into the proper view orientation so that the rays could be traced within a PE. The original unrotated 3D data is spread across the PEs local ram in what is called a cut and stack mapping. For example consider a 128x128x128 data set mapped onto a 64x64 PE array. Four entire Z columns of data would map to each PE. For example, PE 0 would get columns (0,0,z), (64,0,z), (0,64,z), and (64,64,z). Each PE is then responsible for tracing rays through its Z columns of data. This way the rays stay within a PE. The problems is when you want to render from some arbitrary angle other than straight down the original Z axis, the data no longer resides where I want it. I solve it by physically rotating the data so that I can render parallel to the Z axis. My basic approach has each PE decide where the data he needs resides and then uses the router to fetch it (actually, he has to fetch 4 values [for a single axis rotation] and do a bilinear interpolation since "where" his data comes from isn't likely to be integer coordinates). This router communication is the slowest part of the renderer and I was wondering if anyone has seen a better way to do such a task. It seems like rotating 3D data sets would be useful in many fields (beyond just rendering) so I thought maybe others have tackled the problem. My current routine can rotate a 128x128x128 byte sized dataset around one major axis in anywhere from 0.5 sec to 1.0 sec depending on the rotation angle (90 degree rotation causes a lot of router conflict). It would be nice if someone has come up with an efficient way of doing it, for example by using nearest neighbor communication. By the way, there is an algorithm that can do a single axis rotation by using a shear along one dimension with compression, followed by a shear along another dimension with expansion, but I haven't gotten it to map to the MasPar's architecure in a satifactory manner yet - if anyone is familiar with this technique and has applied it to a SIMD 2D mesh, I would be very interested. Tim Cullip cullip@cs.unc.edu Tim Cullip cullip@cs.unc.edu