AngelCode.com > Reference Database

Computer Science/Algorithms & data structures/BSP trees

.NET  7
Artificial Intelligence  7
  Group behavior  2
  Path finding  16
    A* and its derivatives  6
  Pattern recognition  1
  Steering behavior  2
  World interaction  4
Audio  0
  DirectX  8
  DSP  5
  Ogg Vorbis  2
  OpenAL  1
  Windows  1
Computer Science  2
  Algorithms & data structures  12
    BSP trees  8
  Encryption  12
  Randomness & noise  11
Data storage  4
  File formats  14
    Image  10
  Resource files  2
Game Development  20
  Cheat & crack prevention  10
  Input  3
  Timing  4
Graphics  27
  Character animation  6
  DirectX  24
    Optimizing  8
  Illumination  5
    Deferred lighting  7
    Global illumination  8
    Lighting models  6
    Screen Space Ambient Occlusion  4
    Shadow maps  18
    Shadow volumes  15
  Image processing & synthesizing  19
  Non-polygonal rendering  3
    Ray tracing  3
  OpenGL  12
  Particle systems  7
  Shaders  32
  Simulation  4
    Cloth  2
    Clouds & sky light  7
    Fire & smoke  4
    Liquids  12
  Surfaces & Meshes  7
    Implicit surfaces  6
    Parametric curves & surfaces  7
    Polygon reduction & LOD  3
    Subdivision surfaces  7
  Terrain  7
    Continuous LOD  12
    Generating data  4
    Voxel engines  2
  Text  6
  Transparency  1
  Visibility determination  16
Languages  5
  Assembler  20
  C & C++  25
    C++ exceptions  5
    Calling conventions  11
    Debugging  5
    Memory management  7
    Optimizations  6
  C#  4
  Creating your own language  13
    Garbage collection  7
  D  2
  Java  4
  Scripting  3
    JScript & VBScript  1
    Lua  6
    Other languages  8
    Perl  2
    Python  5
    Ruby  4
Mathematics  3
  Fourier transform  4
  Geometry  6
  Linear algebra, vectors & matrices  9
  Wavelet transform  5
Object design  3
Physics  5
  Body dynamics  8
  Collision detection  10
    Polytopes  6
Platform  2
  Linux  1
  Mac  2
  Windows  13
    COM, ATL & WTL  8
    Dynamically loaded libraries  6
    Hooks  5
    Input  2
    Networking  6
    Screensavers  3
    Services  1
    Shell  2
    Small executables  3
    Windows  8
Web Technologies  8

Binary Space Partitioning Trees
Gerald Filimonov

BSP Tree Algorithm in 3 Dimensions
December 15, 2000 - Kevin Meinert
This article is very basic and doesn't go into much details about the BSP structure. But it comes with full source code and a very good reference list.

BSP Tree FAQ
This article is fairly introductory. It explains how to construct a BSP tree and how to use it when rendering. It does not explain about PVS. It does however show how to perform boolean operations with BSP trees.

Graphics Programming Black Book
Michael Abrash
This book on 153 MB (divided into one file per chapter) is a bit outdated but some algorithms never die such as BSP, PVS, and the likes. I don't know how useful the information here is but I keep the reference just in case.

An Investigation into Real-time 3D Polygon Rendering using BSP Trees
April 1999 - Andrew Steven Winter

Fast BSP Tree Generation Using Binary Searches
Paul Nettle
This article presents an idea for an algorithm that is able to quickly choose splitting planes when constructing BSP trees so that good balance between few splits and tree depth are produced. Although the article mentions it as just an unproven idea the author have since implemented it and proved it successful.

BSP Tree Thesis
Jan 2001 - Samuel Ranta-Eskola
This excellent paper describes the BSP tree and its applications. It includes construction and traversal of the BSP tree, portal rendering and automatic placement through BSP trees, PVS computation, radiosity computation, and collision detection and handling against BSP trees. In addition to that it has lots of internet links to references used.

BSP Trees: Theory and Implementation
Sep, 2003 - Samuel Ranta-Eskola