Databases
StackOverflow2013
Postsdbo
PO
 

Note that there are some explanatory texts on larger screens.

plurals
  1. PO
    primarykey
    data
    text
    <p>BSP trees can be abstracted to any N-dimensional space since by definition a N-dimensional hyperplane will bisect a space into two parts. In other words, for a given point in N-dimensional space, it must either be on the hyperplane, or in one of the bisected spaces that the hyperplane creates in the N-dimensional space.</p> <p>For 2D, a BSP tree would be created by drawing a line, and then testing on what side of that line a point was. This is because a line bisects a 2D-space. For 3D, you would need a plane, which would typically be formed from the normal to the polygonal surface that you're using as the test.</p> <p>So your algorithm would be something like the following:</p> <ol> <li>Create a queue containing all the polys from the cube. It would be best to randomly add the polys to the queue rather than in some order.</li> <li>Pop a poly from the front of the queue ... make this the "root" of the BSP tree.</li> <li>Create a normal from that poly</li> <li>Pop another poly from the queue</li> <li>Test whether all the points in that poly are in front of or behind the normal created from the root.</li> <li>If they are all in-front, then make that poly the right-child of the root. If they are all behind, make that poly the left-child of the root.</li> <li>If all the points in the poly are not in front or behind the plane defined by the root polygon's normal, then you'll need to split the poly into two parts for the portions that are in-front and behind the plane. For the two new polys created from this split, add them to the back of the queue, and repeat from step #4.</li> <li>Pop another poly from the queue.</li> <li>Test this poly against the root. Since the root has a child, once you test whether the poly is in-front or behind the root (keeping in mind step #7 that may require a split), test the poly against the child node that is on the right if it's in-front, or the child node on the left if it's behind. If there is no child-node, then you can stop moving through the tree, and add the polygon as to the tree as that child.</li> <li>For any child node you run into where the current poly is not in-front or behind, you'll need to perform the split in step #7 and then go back to step #4.</li> <li>Keep repeating this process until the queue is empty.</li> </ol> <p>Code for this algorithm would conceptually look something like:</p> <pre><code>struct bsp_node { std::vector&lt;poly_t&gt; polys; bsp_node* rchild; bsp_node* lchild; bsp_node(const poly_t&amp; input): rchild(NULL), lchild(NULL) { polys.push_back(input); } }; std::queue&lt;poly_t&gt; poly_queue; //...add all the polygons in the scene randomly to the queue bsp_node* bsp_root = new bsp_node(poly_queue.front()); poly_queue.pop(); while(!poly_queue.empty()) { //grab a poly from the queue poly_t current_poly = poly_queue.front(); poly_queue.pop(); //search the binary tree bsp_node* current_node = bsp_root; bsp_node* prev_node = NULL; bool stop_search = false; while(current_node != NULL &amp;&amp; !stop_search) { //use a plane defined by the current_node to test current_poly int result = test(current_poly, current_node); switch(result) { case COINCIDENT: stop_search = true; current_node-&gt;polys.push_back(current_poly); break; case IN_FRONT: prev_node = current_node; current_node = current_node-&gt;rchild; break; case BEHIND: prev_node = current_node; current_node = current_node-&gt;lchild; break; //split the poly and add the newly created polygons back to the queue case SPLIT: stop_search = true; split_current_poly(current_poly, poly_queue); break; } } //if we reached a NULL child, that means we can add the poly to the tree if (!current_node) { if (prev_node-&gt;rchild == NULL) prev_node-&gt;rchild = new bsp_node(current_poly); else prev_node-&gt;lchild = new bsp_node(current_poly); } } </code></pre> <p>Once you've completed the creation of the tree, you can then do an in-order search of the tree and get the polygons sorted from back-to-front. It won't matter if the objects are transparent or not, since you're sorting based on the polys themselves, not their material properties.</p>
    singulars
    1. This table or related slice is empty.
    1. POWill BSP trees work on single, transparent objects?
      singulars
      1. PTQuestion
    1. PTAnswer
    1. USJason
    1. USJason
    plurals
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. POWill BSP trees work on single, transparent objects?
      singulars
      1. PTQuestion
    1. This table or related slice is empty.
    1. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    2. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    3. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    1. COThanks, Jason. That's a great explanation.
      singulars
      1. PO
      1. USFish
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload