Content deleted Content added
m updated Fuch's reference to include journal |
m fix low contrast between images and background in dark mode |
||
Line 68:
|
| Start with a list of lines, (or in 3D, polygons) making up the scene. In the tree diagrams, lists are denoted by rounded rectangles and nodes in the BSP tree by circles. In the spatial diagram of the lines, the direction chosen to be the 'front' of a line is denoted by an arrow.
| style="text-align:right;" | [[File:Example of BSP tree construction - step 1.svg|class=skin-invert]]
|- valign="top"
| style="text-align:right;" | '''i.'''
Line 77:
# We first process the lines in front of A (in steps ii–v),...
# ...followed by those behind (in steps vi–vii).
| style="text-align:right;" | [[File:Example of BSP tree construction - step 2.svg|class=skin-invert]]
|- valign="top"
| style="text-align:right;" | '''ii.''' || We now apply the algorithm to the list of lines in front of A (containing B2, C2, D2). We choose a line, B2, add it to a node and split the rest of the list into those lines that are in front of B2 (D2), and those that are behind it (C2, D3). || style="text-align:right;" | [[File:Example of BSP tree construction - step 3.svg|class=skin-invert]]
|- valign="top"
| style="text-align:right;" | '''iii.'''
| Choose a line, D2, from the list of lines in front of B2 and A. It is the only line in the list, so after adding it to a node, nothing further needs to be done.
| style="text-align:right;" | [[File:Example of BSP tree construction - step 4.svg|class=skin-invert]]
|- valign="top"
| style="text-align:right;" | '''iv.'''
| We are done with the lines in front of B2, so consider the lines behind B2 (C2 and D3). Choose one of these (C2), add it to a node, and put the other line in the list (D3) into the list of lines in front of C2.
| style="text-align:right;" | [[File:Example of BSP tree construction - step 5.svg|class=skin-invert]]
|- valign="top"
| style="text-align:right;" | '''v.'''
| Now look at the list of lines in front of C2. There is only one line (D3), so add this to a node and continue.
| style="text-align:right;" | [[File:Example of BSP tree construction - step 6.svg|class=skin-invert]]
|- valign="top"
| style="text-align:right;" | '''vi.''' || We have now added all of the lines in front of A to the BSP tree, so we now start on the list of lines behind A. Choosing a line (B1) from this list, we add B1 to a node and split the remainder of the list into lines in front of B1 (i.e. D1), and lines behind B1 (i.e. C1). || [[File:Example of BSP tree construction - step 7.svg|class=skin-invert]]
|- valign="top"
| style="text-align:right;" | '''vii.''' || Processing first the list of lines in front of B1, D1 is the only line in this list, so add this to a node and continue. || style="text-align:right;" | [[File:Example of BSP tree construction - step 8.svg|class=skin-invert]]
|- valign="top"
| style="text-align:right;" | '''viii.''' || Looking next at the list of lines behind B1, the only line in this list is C1, so add this to a node, and the BSP tree is complete. || style="text-align:right;" | [[File:Example of BSP tree construction - step 9.svg|class=skin-invert]]
|}
| |||