[概念] [CG] 鳩噏下painter

由於手巴懶 所以呢個po唔會有圖 唔會處理corner case 只會講concept 大家將就下


上次開po講左pointer 所以就講埋佢個friend painter
painter's algorithm係一個3d rendering既做法: 將polygon由遠到近咁render
咁樣後render既近polygon就自然咁cover到先render既遠polygon

可能大家會覺得
1. 超 鬼唔知咩
2. 多此一舉 用depth buffer咪得囉
painter's algorithm適用既場合 而家的確係好少了
以前當記憶體好珍貴 根本無資源去做足夠precision既depth buffer
或者而家你係好少ram既embedded system做3d rendering
或者你有現成既2d rendering acceleration (eg HTML5 svg/canvas before webgl)
咁先會考慮painter's algo

具體點樣判斷邊個polygon叫遠 邊個叫近呢
用頂點距離係唔work既 反例係一個好大但近既polygon vs 一個細但遠既polygon

  |
  |
| |  viewer
  |
  |

用最短距離都係唔work既 反例係一個好大而遠既polygon vs 一個細而depth近不過好偏既polygon

| |
|
|   viewer
|
|

要判斷邊個polygon畫先 邊個polygon畫後 我地要用啲數學

係R3到 一個平面可以用Ax+By+Cz+D=0去表達 平面上所有既點都係呢條equation既solution
如果我地將空間上任何一點既座標代入去Ax+By+Cz+D到 平面以外既點就會計到非0既數出黎
其實計出黎既結果 正正將空間分開做三part
1. 平面本身(計出黎係0)
2. 平面既"上"方空間(計出黎係正數)
3. 平面既"下"方空間(計出黎係負數)

所以given viewer point同埋兩個polygon A同B 可以用下面既步驟:
1. 用B plane去考慮 如果A polygon既所有點係B plane既一方 而viewer係另一方 咁就先畫A 後畫B
2. 用A plane去考慮 如果B polygon既所有點係A plane既一方 而viewer係另一方 咁就先畫B 後畫A
3. 如果(用A plane去考慮 B polygon同viewer係同方 && 用B plane去考慮 A polygon同viewer係同方) 咁就邊個先邊個後無所謂
實務上唔駛做晒三步 由於第三個case係咩次序畫都得 所以可以第一步既else直接先畫B後畫A

可能你會問 咁如果A polygon橫跨B place既兩方呢
好簡單 將A polygon斬開做A1同A2就得了

如果我地每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做分割

painter + bsp tree係現代其實都仲有啲用途
例如可能你部device只有有限既3d加速 唔可以下下炸晒depth buffer
咁你就可以係bsp tree到加啲假想面 (ie 無actual polygon要render既plane) 圍住你想精細render既部分 個部分就用shader堆一堆資源比佢render 其他部分就普通咁畫個polygon出黎
所以佢唔係完全被淘汰 係睇你諗唔諗到點用佢

屌 唔記得改返標題做講下
呢個係懶既簡略學術po 唔係鳩噏po

難度暴增

pointer同painter差唔多啫

如果有polygon完全被另一個polygon mask out左 咁gen出黎咪會晒左computation work
如果加埋check overlapped效果會點

有個variant係reverse painter
做法係你有一個1 bit buffer 由近到遠畫落個buffer到 如果個polygon cover既部分係完全painted by nearer polygon 咁你就可以mark discard佢
之後再正常用painter去render skip marked polygon
咁雖然都係要畫落個buffer到 但係如果你啲polygon有texture呀 奇怪既shading呀 咁會慳左唔少資源

同時1bit buffer比起16bit depth buffer significantly用少好多資源

1 bit咁細應該會成個mon都z fighting
同埋non opaque polygons又可以點處理

1 bit唔係for depth係for mark drawn or not

Painter本身無non opaque polygon既問題
Reverse painter你咪唔mark drawn bit for non opaque polygon

下一回講printer運作原理?!

都係唔係幾明個1 bit buffer點work你意思係每個polygon有個drawornot嘅boolean

如果non opaque情況下 應該永遠只會喺一個pixel generate黎自最近polygon嘅顏色? 點解唔直接由近到遠store個pixel嘅value喺個array度就算 最後一次過render 就搞掂 除非會喺同一個位gen多於一個polygon嘅non opaque case就需要


但都有個問題 有個實色嘅polygon擋住n個opaque嘅都會浪費computation work

有個variant係reverse painter
做法係你有一個1 bit buffer 由近到遠畫落個buffer到 如果個polygon cover既部分係完全painted by nearer polygon 咁你就可以mark discard佢
之後再正常用painter去render skip marked polygon
咁雖然都係要畫落個buffer到 但係如果你啲polygon有texture呀 奇怪既shading呀 咁會慳左唔少資源

同時1bit buffer比起16bit depth buffer significantly用少好多資源

1 bit咁細應該會成個mon都z fighting
同埋non opaque polygons又可以點處理

1 bit唔係for depth係for mark drawn or not

Painter本身無non opaque polygon既問題
Reverse painter你咪唔mark drawn bit for non opaque polygon

都係唔係幾明個1 bit buffer點work你意思係每個polygon有個drawornot嘅boolean

如果non opaque情況下 應該永遠只會喺一個pixel generate黎自最近polygon嘅顏色? 點解唔直接由近到遠store個pixel嘅value喺個array度就算 最後一次過render 就搞掂 除非會喺同一個位gen多於一個polygon嘅 opaque case就需要


但都有個問題 有個實色嘅polygon擋住n個opaque嘅都會浪費computation work

上面打多左個non

LM

SPLM

1 bit precision whole scene buffer
Polygon可以係好expensive既 例如做texture 做shading 唔係淨係畫單色
咁既情況下 用1bit buffer係一個valid既optimization 因為先係1bit buffer做單色render 然後就可以skip completely covered既polygon