Binary Space Partitioning: |
| The binary space partitioning algorithm is today still of interest to people involved in computer graphics. It is related to visible surface determining algorithms such as hidden surface removal, depth-sort (painter's) algorithm, which is discussed in this web site, area subdivision (the Warnock algorithm), culling, the scanline algorithm and the z-buffer algorithm. For a comparison of these algorithms in terms of complexity and in terms of in what case you might choose one over another, see: http://ironbark.bendigo.latrobe.edu.au/~fran/int32gp/wk09/lctr18.html. |
| People of The Graphics Team at Indian Institute of Technology: have been working on the improving algorithms for
viewing objects in 3D space in a runtime (dynamic) environment. Some of their work has been in developing a new
technique for dynamic binary space partitioning. They pay particular attention to dynamic hidden surface removal,
including sorting and accessing polygons in a 3D world which allow for a scene to be different at runtime than
it was at compiling time. In their work, they create a space partitioning structure called the "separating
plane partition tree". It is a variation of the "classic" binary space partition tree. In a separating plane partition tree, separating planes are used to split up the scenes. As in a regular bsp tree, the polygons are split and are stored at the leaves. This allows for easy access of split polygons for efficient insertion and deletion. The polygons are ordered in such a way as to make hidden surface removal efficient. To read more about this variation, please take a look at their technical papers, which can be downloaded from: http://www.cse.iitd.ernet.in/~skapoor/visualc/ |
|
|
|
This is an image from their site. |
