Page 118 - DCAP313_LAB_ON_COMPUTER_GRAPHICS

Lab on Computer Graphics

Notes Figure 7.1: Building a BSP Tree (in 2D)

Building a BSP Tree (in 2D)

Choose a polygon P from L to serve as root
Split all polygons in L according to P

return new Tree Node(
P,
Make BSP( polygons on negative side of P ),

Make BSP( polygons on positive side of P ))
}
Splitting polygons is expensive! It helps to choose P wisely at each step.

choose five candidates; keep the one that splits the fewest polygons

Figure 7.2: Alternate BSP Tree

Alternate BSP Tree

1 1
5 back
2
4 3
back
2
3
front
4
back
5

112 LOVELY PROFESSIONAL UNIVERSITY