Thread: Input Spatial Data for BSP Tree

  1. #1
    Registered User
    Join Date
    Aug 2005

    Input Spatial Data for BSP Tree

    I'm trying to create a binary space partition tree for a space. I just want to input the space and have an algorithm partition it. How is the input spatial data represented? Is it just a set of polygons(described by a set of 2D points) with 3D coordinates, and then another set of coordinates for spatial orientation?

    Are there any tutorials or books on this that you would recommend?

  2. #2
    Crazy Fool Perspective's Avatar
    Join Date
    Jan 2003
    The input format can be anything you want. Most model formats have something like a vertex set, and then polys specified in terms of the vertices.

    edit: has file format specs for some 3D model formats.

  3. #3
    Super Moderator VirtualAce's Avatar
    Join Date
    Aug 2001
    Normally BSPs are based on planes created by vertices rather than just vertices. The vertices in themselves do not represent much. Remember that any 3 points in space are guaranteed to form a plane.

    Once you determine the planes and the plane you wish to use as the root of the BSP you can then decide which half-space other planes lie in relation to the root plane. This is how you would build your tree.

    There are several docs on the web about this. Now picking the correct starting plane so as to keep the tree as balanced as possible is quite complex.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. xor linked list
    By adramalech in forum C Programming
    Replies: 23
    Last Post: 10-14-2008, 10:13 AM
  2. problem collecting data from input file
    By gkoenig in forum C Programming
    Replies: 12
    Last Post: 03-30-2008, 07:40 AM
  3. I would love some input on my BST tree.
    By StevenGarcia in forum C++ Programming
    Replies: 4
    Last Post: 01-15-2007, 01:22 AM
  4. searching and insertion in a binary search tree
    By galmca in forum C Programming
    Replies: 1
    Last Post: 03-26-2005, 05:15 PM
  5. BST/Red and Black Tree
    By ghettoman in forum C++ Programming
    Replies: 0
    Last Post: 10-24-2001, 10:45 PM