3D Rendering with Binary Space Partitions

in this video we'll learn how to program 3d graphics with binary space partition z' will learn the basics of 3d rendering such as how to build a binary space tree and how to render a scene by means of a tree traversal 3d rendering is a wide variety of applications these include graphic artwork first-person games such as doom and quake real-time 3d simulations such as virtual reality and flight simulations animations and movies well first take a look at some other 3d rendering algorithms and see how they compare to a binary space partition in terms of efficiency and rendering speed the two we'll look at are the painters algorithm and a ray casting algorithm the basic requirement common to all these algorithms is that the objects to be rendered be kept in a data file for simplicity we'll look at only how a set of walls can be rendered from a two-dimensional map shown here from overhead the black dot represents the viewer and the two lines represent the field of vision so how might we render a 3d scene based on this data in a moment we'll see how this is done with a binary space partition but let's first look at how this is handled in the painters algorithm and the painters algorithm the most distant wall is rendered first following that closer and closer walls are rendered until eventually the entire scene is painted you the painters algorithm goes from back to front and every wall line within the field of vision of the viewer is drawn as a consequence there's lots of over drawing this consumes CPU cycles and slows down the rendering process look how many walls we had to paint before we finally replace them with a green wall raycasting doesn't suffer from the same penalty in this algorithm we fire a beam at the left side of the screen until it hits a wall we then continue firing beams toward the right until the entire scene is drawn using a longer stripe for a closer wall into shorter stripe for a farther wall raycasting goes from left to right while it requires no over drawing we must obtain the closest wall for each being fired this typically involves checking the intersection of each beam with every wall in the viewing area to find which wall is closest additionally one beam must be fired for every x-coordinate on the screen making ray casting slower on high resolution systems now we'll see how a binary space partition overcomes the difficulties associated with the painters algorithm and raycasting what we'd like to do is paint every wall from front to back so that the rendering process looks something like this the number of CPU cycles used is highly reduced which makes a binary space partition a fast and efficient approach to 3d rendering because we paint only the walls that are visible no over drawing is needed so how do we get this to work in order to inform our engine of which walls to draw first we take our map file before the engine has started and used the existing walls to divide space into halves as we're doing this we're also keeping a record of the way space is being divided into a tree data structure this data structure when completed is what is formally known as a binary space partition the result is that space is partitioned into a collection of disjoint polygonal regions represented by the nodes on the bottom of the tree now we watch how this tree is used to render walls in front to back order we begin by finding out which region of space the viewer resent this is accomplished with a binary search in this example we found the viewer at node 42 now we move upward to node to this node contains a wall immediately adjacent to note 42 the green wall of our earlier illustration we paint the wall and move down to node 43 node 43 has two children node 44 into node 45 our task now is to determine which of the two nodes is closer to the viewer after a simple calculation we determined that node 44 is closer we perform the same test again and again down the tree until a note of the bottom is reached this gives us the next closest region of space now we move up to node 46 this contains the back of the green wall since we already painted over this region of the visual field there is no need to draw it we continue this process by stepping through all nodes of the tree drawing any visible walls that are encountered notice how the traversal carefully fans out from a location of the viewer the binary space partition is specially designed to draw the closest wall first followed by remaining walls and greasing order of distance you after painting the yellow wall we stopped the entire field of vision has been uncommon we repeat this process for every frame of animation on a sidenote you may be wondering how we drew the walls in such a way as not to overlap and how we knew when to finish to do this we keep an ongoing list of horizontal scanlines to indicate which parts of the screen have already been drawn over anytime we draw a new wall we draw only the section of the wall visible through the existing scan lines and then merge that scan line with the list when we end up with a single scanline spanning the entire screen our rendering is finished this concludes our introduction to 3d rendering with binary space partition z' much of what we've discussed here extends by analogy to higher dimensions for a more detailed account check out developing games in Java by David Bracken

Channel: Quothmar

Views: 82,065

Keywords: Binary Space Partition, 3D Rendering, 3D Game Programming, 3D Graphics, 3D Computer Graphics, First-Person Rendering, First-Person Graphics

Id: yTRzfKh4Tg0

Length: 6min 39sec (399 seconds)

Published: Mon Apr 28 2014