如果我地每render一次 都要去每pair polygon去計下邊個先邊個後 又要分割下 再做個topology sort 係會用好多時間計
我地可以預先計一個BSP tree
(再次由於手巴懶 只會帶出concept 唔會optimize)
首先我地random揀一個polygon A 用佢既plane去將其他polygon分開做兩set 如果有橫跨既polygon就做埋分割
呢個polygon A就係root node 左右children就係個兩set polygon
之後就左右children分別各自recursively做同樣既步驟 build晒成棵tree出黎
build_bsp_tree(polygons):
if polygons is empty: return null
root = random_pick(polygons)
plane = root.plane
cut_polygons = (polygons - root).cut_by(plane)
pos_polygons = cut_polygons.filter(p => plane(p) > 0)
neg_polygons = cut_polygons.filter(p => plane(p) < 0)
root.pos_child = build_bsp_tree(pos_polygons)
root.neg_child = build_bsp_tree(neg_polygons)
return root
render個時都係recursive render
given view point 我地計view point係個root plane既邊一方
首先render另一方 然後render root polygon本身 最後render 同view point同方
render_bsp_tree(view_point, bsp_tree_node):
if (bsp_tree_node.plane(view_point) > 0):
render_bsp_tree(view_point, bsp_tree_node.neg_child)
render_polygon(view_point, bsp_tree_node)
render_bsp_tree(view_point, bsp_tree_node.pos_child)
else:
render_bsp_tree(view_point, bsp_tree_node.pos_child)
render_polygon(view_point, bsp_tree_node)
render_bsp_tree(view_point, bsp_tree_node.neg_child)
用bsp tree 我地每render一次 只需要對每個polygon既plane計一次個view point 而唔駛再每對polygon判斷先後 唔駛再每frame做分割