16/PCGPE10/BSP.TXT

   1                  ÚÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ¿\r
   2                  ³ A Simple Explanation of BSP Trees ³\r
   3                  ÀÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÙ\r
   4 \r
   5             Written for the PC-GPE by Mark Feldman\r
   6             e-mail address : u914097@student.canberra.edu.au\r
   7                              myndale@cairo.anu.edu.au\r
   8 \r
   9              ÚÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ¿\r
  10              ³      THIS FILE MAY NOT BE DISTRIBUTED     ³\r
  11              ³ SEPARATE TO THE ENTIRE PC-GPE COLLECTION. ³\r
  12              ÀÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÙ\r
  13 \r
  14 \r
  15 ÚÄÄÄÄÄÄÄÄÄÄÄÄÂÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ\r
  16 ³ Disclaimer ³\r
  17 ÀÄÄÄÄÄÄÄÄÄÄÄÄÙ\r
  18 \r
  19 I assume no responsibility whatsoever for any effect that this file, the\r
  20 information contained therein or the use thereof has on you, your sanity,\r
  21 computer, spouse, children, pets or anything else related to you or your\r
  22 existance. No warranty is provided nor implied with this information.\r
  23 \r
  24 ÚÄÄÄÄÄÄÄÄÄÄÄÂÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ\r
  25 ³ BSP Trees ³\r
  26 ÀÄÄÄÄÄÄÄÄÄÄÄÙ\r
  27 \r
  28 Binary Space Partition trees are handy for drawing 3D scenes where the\r
  29 positions of objects are fixed and the user's viewing coordinate changes\r
  30 (flight simulators being a classic example).\r
  31 \r
  32 BSP's are an extention of the "Painter's Algorithm". The painter's algorithm\r
  33 works by drawing all the polygons (or texture maps) in a scene in back-to-\r
  34 front order, so that polygon's in the background are drawn first, and\r
  35 polygons in the foreground are drawn over them. The "classic" painter's\r
  36 algorithm does have a few problems however:\r
  37 1) polygon's will not be drawn correctly if they pass through any other\r
  38 polygon\r
  39 2) it's difficult and computationally expensive calculating the order that\r
  40 the polygons should be drawn in for each frame\r
  41 3) the algorithm cannot handle cases of cyclic overlap such as the\r
  42 following :\r
  43                            ___       ___\r
  44                           |   |     |   |\r
  45                         __|   |_____|___|___\r
  46                        |  |   |             |\r
  47                        |__|   |_____________|\r
  48                           |   |     |   |\r
  49                         __|___|_____|   |___\r
  50                        |            |   |   |\r
  51                        |____________|   |___|\r
  52                           |   |     |   |\r
  53                           |___|     |___|\r
  54 \r
  55 In this case it doesn't matter which order you draw the polygon's it still\r
  56 won't look right!\r
  57 \r
  58 BSP's help solve all these problems.\r
  59 \r
  60 Ok, so let's get down to business. BSP's work by building an ordered tree of\r
  61 all the objects in a scene. Let's imagine we live in a 2D world and we have\r
  62 a scene like this:\r
  63 \r
  64              ÚÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ¿\r
  65              ³                                    ³\r
  66              ³                                    ³\r
  67              ³              ÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ  ³\r
  68              ³                    line 1          ³\r
  69              ³           \                        ³\r
  70              ³             \                      ³\r
  71              ³               \ line 2             ³\r
  72              ³                 \                  ³\r
  73              ³                   \                ³\r
  74              ³   ÄÄÄÄÄÄÄÄ          \              ³\r
  75              ³   line 3              \            ³\r
  76              ³                                    ³\r
  77              ÀÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÙ\r
  78 \r
  79                               ^\r
  80                               viewpoint (assume the viewpoint is the\r
  81                                          origin for this example)\r
  82 \r
  83 \r
  84 Now if we were to draw this scene using the painters algorithm we would\r
  85 draw line 1 first, then line 2, finally line 3. Using BSP's we can figure\r
  86 out the order beforehand and create a tree. First we note that any\r
  87 arbitrary point <x,y> can be on either of it's 2 sides or on the line (which\r
  88 can be regarded as being on either of the sides). When we build our tree, we\r
  89 take a line and put all the lines on one side of it to the left and all the\r
  90 nodes on the other side on the right. So for the above example could wind up\r
  91 with the following tree:\r
  92 \r
  93           1\r
  94          /\r
  95         2\r
  96        /\r
  97       3\r
  98 \r
  99 Alternatively, we could also wind up with this tree:\r
 100 \r
 101         2\r
 102        / \\r
 103       3   1\r
 104 \r
 105 Notice that line 2 is the head node, line 3 is on the same side of line 2\r
 106 as the origin is and line 1 is on the opposite side.\r
 107 \r
 108 Now, I hear you say "but hang on a tic, what if line 3 is the head node? What\r
 109 side of it is line 2 on?". Yes boys and girls, there had to be a catch\r
 110 somewhere and this is it. What you have to do here is split line 2 into\r
 111 *TWO* lines so that each portion falls nice and neatly onto either side of\r
 112 line 3, so you get a tree like this:\r
 113 \r
 114        3\r
 115       / \\r
 116     2a   2b\r
 117           \\r
 118            1\r
 119 \r
 120 The lines 2a and 2b are portions of the original line 2. If you draw *BOTH*\r
 121 of them on the screen it will look as though you've drawn the entire original\r
 122 line.\r
 123 \r
 124 You don't have to worry about balancing a BSP tree, since you have to\r
 125 traverse every node in it every time you draw the scene anyway. The trick\r
 126 is to figure out how to organise the tree so that you get the *least* number\r
 127 of polygon splits. I tackled this by looking at each polygon yet to be\r
 128 inserted into the tree, calculating how many splits it will cause if it\r
 129 is inserted next and selecting the one which will cause the fewest. This\r
 130 is a very slow way of going about things, O(N^2) I think, but for most games\r
 131 you only need to sort the tree once when you are developping the game and not\r
 132 during the game itself.\r
 133 \r
 134 Extending these concepts to 3D is pretty straight-forward. Let's say that\r
 135 polygon 1 is at the top of the BSP tree and we want to insert polygon 2. If\r
 136 all the points in polygon 2 fall on one side or the other of polygon 1 then\r
 137 you insert it into polygon 2's left or right node. If some points fall on\r
 138 one side and the rest fall on the other, then you have to figure out the line\r
 139 of intersection formed by the planes that each polygon lies in and split\r
 140 polygon 2 along this line. Each of these 2 new polygons will then fall on\r
 141 either side of polygon 1.\r
 142 \r
 143 \r
 144 To draw the objects in a BSP tree you start at the top node and figure out\r
 145 which side of the object your view coordinate is on. You then traverse the\r
 146 node for the *other* side, draw the current object, then traverse the node\r
 147 for the side the view coordinate is on.\r
 148 \r
 149 \r