home *** CD-ROM | disk | FTP | other *** search
/ Virtual Reality Homebrewer's Handbook / vr.iso / rend386 / doc / splits.doc < prev    next >
Text File  |  1996-03-19  |  5KB  |  112 lines
  1.                    Depth Sorting and Splitting Planes
  2.                   Written by Bernie Roehl, August 1992
  3.  
  4. Version 4.00 of the REND386 package has support for binary trees of
  5. "splitting planes" to help reduce the number of visibility errors.
  6.  
  7. Visibility errors occur when polygons are not rendered in the proper
  8. order.  This is an inherent limitation of the depth-sorting approach, and
  9. since depth-sorting is the only technique that will let us achieve
  10. reasonable rendering speeds, visibility errors are a fact of life.
  11.  
  12. Splitting planes give you more precise control over rendering order,
  13. and can get rid of some (but not all) object-object visibility errors.
  14.  
  15. To understand how visibility errors occur, and how splitting planes can help,
  16. consider the following situation:
  17.  
  18.                  /
  19.         object1 /
  20.                /
  21.               /
  22.              /
  23.             / object2
  24.            /
  25.           /
  26.          /
  27.         /
  28.  
  29.             ^observer
  30.  
  31. There are two objects (object1 and object2), one on each side of an opaque
  32. wall.
  33.  
  34. From the position of the observer in the above diagram, object1 should be
  35. obscured behind the wall, and object2 should be visible.  The correct
  36. drawing order is "object1, wall, object2".
  37.  
  38. However, since the farthest point on the wall is farther away than object1,
  39. the depth-sorting algorithm will cause the wall to get drawn first; the
  40. resulting order is "wall, object1, object2" (which is incorrect, since
  41. object1 appears to be on the near side of the wall when it's not).
  42.  
  43. We can modify the depth sorting; let's say we sort by nearest point rather
  44. than farthest.  Clearly this will help in some cases; however, it
  45. doesn't work for the situation above.  What we'd have is just the opposite
  46. of the original situation; the order would be "object1, object2, wall", so
  47. object2 (which should be visible) isn't.
  48.  
  49. This is a situation where splitting planes can help.  A splitting plane
  50. is an infinite mathematical plane that breaks space into two areas, one
  51. on each side of the plane.  When we go to render the scene, we draw the
  52. objects on the far side of the plane first, then objects "on" the plane,
  53. then objects on the near side of the plane.
  54.  
  55. By introducing a splitting plane that runs along the wall, and rendering
  56. objects on the "far" side of the wall first, we eliminate the problem in
  57. the situation above; from where the observer is, object1 is on the "far"
  58. side of the plane and therefore gets drawn first.  The wall is "on" the
  59. plane, and gets drawn next.  Finally, object2 (which is on the "near"
  60. side of the plane) gets drawn.  The order is "object1, wall, object2",
  61. which is what we want.  If the observer moves to the other side of the
  62. wall, the solution still works; object2 will be on the far side, and
  63. will therefore be drawn first (followed by the wall, followed by object1).
  64.  
  65. Note that a splitting plane is a true mathematical plane (i.e. it's
  66. infinitely large, and has no boundaries).  It is *not* a polygon!
  67. A splitting plane is defined by a point in the plane and by a normal to
  68. the plane.  The normal is a line pointing away from the plane: i.e. a
  69. normal to a floor or ceiling (i.e. constant z coords) might be 0,0,1.
  70. For a wall with constant x-coordinates, it would be 1,0,0.  Any angle
  71. can be specified.
  72.  
  73. A single splitting plane divides space into two "areas"; we can further
  74. subdivide either or both of these with additional splitting planes.  The
  75. planes therefore define a binary tree, whose non-leaf nodes are the planes
  76. and whose leaf nodes are "areas" (with which we can associate various
  77. properties, including lists of objects in that area).
  78.  
  79. Note that the order of split definition is important.  For example, four
  80. splits would perhaps form the pattern:
  81.  
  82.     2     3                       1      
  83.     2444443         or          1222222
  84.     2     3                     1     3
  85. 111111111111                    1444443 
  86.                                 1
  87. depending on the order in which they're defined.
  88.  
  89. Also, you should try to keep walls, ceilings, floors, etc. confined within
  90. the area defined by their split.  Otherwise vis errors are likely.  It is
  91. possible to write a program to define splits automatically, and divide walls;
  92. so far this hasn't been done.  (any volenteers?)
  93.  
  94. When an object moves, it has to be removed from its current location in the
  95. splitting tree and re-inserted at the correct place; this imposes a (small)
  96. overhead.  Because the object is not actually divided, but "exists" on the
  97. side determined by its center, the overhead is much smaller than with true
  98. BSP trees; however, it means that split trees are not foolproof when it comes
  99. to eliminating vis errors.
  100.  
  101. It's important to keep in mind that splitting planes are not a cure-all; even
  102. with clever use of splitting planes one can still have visibility errors.
  103. However, they can be drastically reduced.
  104.  
  105. By breaking non-convex objects into smaller, separate pieces, you can
  106. eliminate some errors.  By carefully setting the depth-sorting type field
  107. for certain objects, you can eliminate still more errors.  And by using
  108. splitting planes, you can remove most of the remaining errors.
  109.  
  110. The combination of these techniques can result in scenes that can be rendered
  111. at high speeds, with relatively few vis errors.
  112.