home *** CD-ROM | disk | FTP | other *** search
/ RISC DISC 3 / RISC_DISC_3.iso / resources / etexts / gems / gemsi / interleave.c < prev    next >
C/C++ Source or Header  |  1992-09-08  |  6KB  |  169 lines
  1. /*
  2. Bit Interleaving for Quad- or Octrees
  3. by Clifford A. Shaffer
  4. from "Graphics Gems", Academic Press, 1990
  5. */
  6.  
  7. #include "GraphicsGems.h"
  8. #define B_MAX_DEPTH 14    /* maximum depth allowed */
  9.  
  10. /* byteval is the lookup table for coordinate interleaving.  Given a
  11.    4 bit portion of the (x, y) coordinates, return the bit interleaving.
  12.    Notice that this table looks like the order in which the pixels of
  13.    a 16 X 16 pixel image would be visited. */
  14. int byteval[16][16] = 
  15.     {  0,  1,  4,  5, 16, 17, 20, 21, 64, 65, 68, 69, 80, 81, 84, 85,
  16.        2,  3,  6,  7, 18, 19, 22, 23, 66, 67, 70, 71, 82, 83, 86, 87,
  17.        8,  9, 12, 13, 24, 25, 28, 29, 72, 73, 76, 77, 88, 89, 92, 93,
  18.       10, 11, 14, 15, 26, 27, 30, 31, 74, 75, 78, 79, 90, 91, 94, 95,
  19.       32, 33, 36, 37, 48, 49, 52, 53, 96, 97,100,101,112,113,116,117,
  20.       34, 35, 38, 39, 50, 51, 54, 55, 98, 99,102,103,114,115,118,119,
  21.       40, 41, 44, 45, 56, 57, 60, 61,104,105,108,109,120,121,124,125,
  22.       42, 43, 46, 47, 58, 59, 62, 63,106,107,110,111,122,123,126,127,
  23.      128,129,132,133,144,145,148,149,192,193,196,197,208,209,212,213,
  24.      130,131,134,135,146,147,150,151,194,195,198,199,210,211,214,215,
  25.      136,137,140,141,152,153,156,157,200,201,204,205,216,217,220,221,
  26.      138,139,142,143,154,155,158,159,202,203,206,207,218,219,222,223,
  27.      160,161,164,165,176,177,180,181,224,225,228,229,240,241,244,245,
  28.      162,163,166,167,178,179,182,183,226,227,230,231,242,243,246,247,
  29.      168,169,172,173,184,185,188,189,232,233,236,237,248,249,252,253,
  30.      170,171,174,175,186,187,190,191,234,235,238,239,250,251,254,255};
  31.  
  32. /* bytemask is the mask for byte interleaving - masks out the 
  33.    non-significant bit positions.  This is determined by the
  34.    depth of the node. For example, a node of depth 0 is at the root.
  35.   Thus, there are no branchs and no bits are significant. 
  36.   The bottom 4 bits (the depth) are always retained. 
  37.   Values are in octal notation. */
  38. int bytemask[B_MAX_DEPTH + 1] = {017,
  39.      030000000017,036000000017,037400000017,037700000017,
  40.      037760000017,037774000017,037777000017,037777600017,
  41.      037777740017,037777770017,037777776017,037777777417,
  42.      037777777717,037777777777};
  43.  
  44.  
  45. long *interleave(addr, x, y, depth, max_depth)
  46. /* Return the interleaved code for a quadtree node at depth depth 
  47. whose upper left hand corner has coordinates (x, y) in a tree with maximum
  48. depth max_depth.  This function receives and returns a 
  49. pointer to addr, which is either a long integer or (more typically)
  50. an array of long integers whose first integer contains the 
  51. interleaved code. */
  52.  long *addr;
  53.  int max_depth, depth;
  54.  int x, y;
  55. {
  56.  
  57. /* Scale x, y values to be consistent with maximum coord size */
  58. /* and depth of tree */
  59.  x <<= (B_MAX_DEPTH - max_depth);
  60.  y <<= (B_MAX_DEPTH - max_depth);
  61.  
  62. /* calculate the bit interleaving of the x, y values that have now
  63.    been appropriately shifted, and place this interleave in the address
  64.    portion of addr.  Note that the binary representations of x and y are
  65.    being processed from right to left */
  66.  
  67.  *addr = depth;
  68.  *addr |= byteval[y & 03][x & 03] << 4;
  69.  *addr |= byteval[(y >> 2) & 017][(x >> 2) & 017] << 8;
  70.  *addr |= byteval[(y >> 6) & 017][(x >> 6) & 017] << 16;
  71.  *addr |= byteval[(y >> 10) & 017][(x >> 10) & 017] << 24;
  72.  *addr &= bytemask[depth];
  73.  
  74. /* if there were unused portions of the x and y addresses then  */
  75. /* the address was too large for the depth values given.  */
  76. /*  Return address built */
  77.  return (addr);
  78. }
  79.  
  80.  
  81.  
  82. /* The next two arrays are used in calculating the (x, y) coordinates
  83.    of the upper left-hand corner of a node from its bit interleaved
  84.    address.  Given an 8 bit number, the arrays return the effect of
  85.    removing every other bit (the y bits precede the x bits). */
  86.  
  87. int xval[256] = { 0, 1, 0, 1, 2, 3, 2, 3, 0, 1, 0, 1, 2, 3, 2, 3,
  88.                  4, 5, 4, 5, 6, 7, 6, 7, 4, 5, 4, 5, 6, 7, 6, 7,
  89.                  0, 1, 0, 1, 2, 3, 2, 3, 0, 1, 0, 1, 2, 3, 2, 3,
  90.                  4, 5, 4, 5, 6, 7, 6, 7, 4, 5, 4, 5, 6, 7, 6, 7,
  91.                  8, 9, 8, 9,10,11,10,11, 8, 9, 8, 9,10,11,10,11,
  92.                 12,13,12,13,14,15,14,15,12,13,12,13,14,15,14,15,
  93.                  8, 9, 8, 9,10,11,10,11, 8, 9, 8, 9,10,11,10,11,
  94.                 12,13,12,13,14,15,14,15,12,13,12,13,14,15,14,15,
  95.                  0, 1, 0, 1, 2, 3, 2, 3, 0, 1, 0, 1, 2, 3, 2, 3,
  96.                  4, 5, 4, 5, 6, 7, 6, 7, 4, 5, 4, 5, 6, 7, 6, 7,
  97.                  0, 1, 0, 1, 2, 3, 2, 3, 0, 1, 0, 1, 2, 3, 2, 3,
  98.                  4, 5, 4, 5, 6, 7, 6, 7, 4, 5, 4, 5, 6, 7, 6, 7,
  99.                  8, 9, 8, 9,10,11,10,11, 8, 9, 8, 9,10,11,10,11,
  100.                 12,13,12,13,14,15,14,15,12,13,12,13,14,15,14,15,
  101.                  8, 9, 8, 9,10,11,10,11, 8, 9, 8, 9,10,11,10,11,
  102.                 12,13,12,13,14,15,14,15,12,13,12,13,14,15,14,15};
  103.  
  104.  
  105. int yval[256] = { 0, 0, 1, 1, 0, 0, 1, 1, 2, 2, 3, 3, 2, 2, 3, 3,
  106.               0, 0, 1, 1, 0, 0, 1, 1, 2, 2, 3, 3, 2, 2, 3, 3,
  107.               4, 4, 5, 5, 4, 4, 5, 5, 6, 6, 7, 7, 6, 6, 7, 7,
  108.               4, 4, 5, 5, 4, 4, 5, 5, 6, 6, 7, 7, 6, 6, 7, 7,
  109.               0, 0, 1, 1, 0, 0, 1, 1, 2, 2, 3, 3, 2, 2, 3, 3,
  110.               0, 0, 1, 1, 0, 0, 1, 1, 2, 2, 3, 3, 2, 2, 3, 3,
  111.               4, 4, 5, 5, 4, 4, 5, 5, 6, 6, 7, 7, 6, 6, 7, 7,
  112.               4, 4, 5, 5, 4, 4, 5, 5, 6, 6, 7, 7, 6, 6, 7, 7,
  113.               8, 8, 9, 9, 8, 8, 9, 9,10,10,11,11,10,10,11,11,
  114.               8, 8, 9, 9, 8, 8, 9, 9,10,10,11,11,10,10,11,11,
  115.              12,12,13,13,12,12,13,13,14,14,15,15,14,14,15,15,
  116.              12,12,13,13,12,12,13,13,14,14,15,15,14,14,15,15,
  117.               8, 8, 9, 9, 8, 8, 9, 9,10,10,11,11,10,10,11,11,
  118.               8, 8, 9, 9, 8, 8, 9, 9,10,10,11,11,10,10,11,11,
  119.              12,12,13,13,12,12,13,13,14,14,15,15,14,14,15,15,
  120.              12,12,13,13,12,12,13,13,14,14,15,15,14,14,15,15};
  121.  
  122.  
  123.  
  124.  
  125.  
  126. int getx(addr, max_depth)
  127. /* Return the x coordinate of the upper left hand corner of addr for a
  128.    tree with maximum depth max_depth. */
  129.  long *addr;
  130.  int max_depth;
  131. {
  132.  register x;
  133.  
  134.  x = xval[(*addr >> 4) & 017];
  135.  x |= xval[(*addr >> 8) & 0377] << 2;
  136.  x |= xval[(*addr >> 16) & 0377] << 6;
  137.  x |= xval[(*addr >> 24) & 0377] << 10;
  138.  x >>= B_MAX_DEPTH - max_depth;
  139.  return (x);
  140. }
  141.  
  142.  
  143.  
  144. int QKy(addr, max_depth)
  145. /* Return the y coordinate of the upper left hand corner of addr for a
  146.    tree with maximum depth max_depth. */
  147.  
  148.  long *addr;
  149.  int max_depth;
  150. {
  151.  register y;
  152.  
  153.  y = yval[(*addr >> 4) & 017];
  154.  y |= yval[(*addr >> 8) & 0377] << 2;
  155.  y |= yval[(*addr >> 16) & 0377] << 6;
  156.  y |= yval[(*addr >> 24) & 0377] << 10;
  157.  y >>= B_MAX_DEPTH - max_depth;
  158.  return (y);
  159. }
  160.  
  161. int getdepth(addr)
  162. /* Return the depth of the node.  Simply return the bottom 4 bits. */
  163.  
  164.  long *addr;
  165. {
  166.  
  167.  return(*addr & 017);
  168. }
  169.