0. 實時渲染四大目標
? 更高的每秒幀數(shù)
? 更高的分辨率
? 渲染更多的物體與更具真實感的場景
? 實現(xiàn)更高的復雜度
1. 空間數(shù)據(jù)結構 | Spatial Data Structures
空間數(shù)據(jù)結構（Spatial Data Structures）是將幾何體組織在 N 維空間中的一系列數(shù)據(jù)結構戏锹，而
且我們可以很容易地將二維和三維的一些概念擴展到高維之中包警。這些空間數(shù)據(jù)結構可以用于
很多實時渲染相關操作的加速查詢中亭螟，如場景管理分预，裁減算法捎废、相交測試舒萎、光線追蹤、以及
碰撞檢測等鳍置。
空間數(shù)據(jù)結構的組織通常是層次結構的辽剧。寬泛地說，即最頂層包含它之下的層次税产，后者又包
含更下層的層次怕轿，以此類推。因此辟拷，這種結構具有嵌套和遞歸的特點撞羽。用層次結構的實現(xiàn)方
式對訪問速度的提升很有幫助，復雜度可以從 O(n)提升到 O(log n)衫冻。但同時放吩，使用了層次結構
的大多數(shù)空間數(shù)據(jù)結構的構造開銷都比較大，雖然也可以在實時過程中進行漸進更新羽杰，但是
通常需要作為一個預處理的過程來完成渡紫。
一些常見的空間數(shù)據(jù)結構包括：
? 層次包圍盒（Bounding Volume Hierachy，BVH）
? 二元空間分割樹（Binary Space Partitioning考赛，BSP）惕澎，
? 四叉樹 （QuadTree）
? kd 樹（k-dimensional tree）
? 八叉樹（Octree）
? 場景圖 （Scene Graphs）
其中，BSP 樹和八叉樹都是基于空間細分（Space Subdivision）的數(shù)據(jù)結構颜骤，這說明它們是對
整個場景空間進行細分并編碼到數(shù)據(jù)結構中的唧喉。例如，所有葉子節(jié)點的空間集合等同于整個
場景空間忍抽，而且葉子節(jié)點不相互重疊八孝。
1.1 層次包圍盒 | Bounding Volume Hierarchies , BVH
層次包圍盒（Bounding Volume Hierarchies, BVH）方法的核心思想是用體積略大而幾何特征簡
單的包圍盒來近似地描述復雜的幾何對象，從而只需對包圍盒重疊的對象進行進一步的相交
測試鸠项。此外干跛，通過構造樹狀層次結構，可以越來越逼近對象的幾何模型祟绊，直到幾乎完全獲得
對象的幾何特征楼入。
對于三維場景的實時渲染來說，層次包圍體（Bounding Volume Hierarchy牧抽，BVH）是最常使用
的一種空間數(shù)據(jù)結構嘉熊。例如，層次包圍體經(jīng)常用于層次視錐裁減扬舒。場景以層次樹結構進行組
織阐肤，包含一個根節(jié)點（root）、一些內部節(jié)點（internal nodes）讲坎，以及一些葉子節(jié)點
（leaves）孕惜。頂部的節(jié)點是根愧薛，其無父節(jié)點。葉子節(jié)點（leaf node）包含需渲染的實際幾何
體诊赊，且其沒有子節(jié)點。
相比之下府瞄，內部節(jié)點包含指向它子節(jié)點的指針碧磅。因此，只要根節(jié)點不是這顆樹唯一的一個節(jié)
點遵馆，那么它就是一個內部節(jié)點鲸郊。樹中的每一個節(jié)點，包括葉子節(jié)點货邓，都有一個包圍體可以將
其子樹中的所有幾何體包圍起來秆撮，這就是包圍體層次的命名來源，同時换况，也說明了根節(jié)點有
一個包含整個場景的包圍體职辨。
1.2 BSP 樹 | BSP Trees
BSP 樹(二叉空間分割樹，全稱 Binary Space Partitioning Tree)是一種常用于判別對象可見性的
空間數(shù)據(jù)結構戈二。類似于畫家算法舒裤，BSP 樹可以方便地將表面由后往前地在屏幕上渲染出來，
特別適用于場景中對象固定不變觉吭，僅視點移動的情況腾供。
其中，BSP 是 Binary SpacePartitioning（二叉空間劃分法）的縮寫鲜滩。這種方法遞歸地將空間使
用超平面劃分為凸面體集合伴鳖。而這種子劃分引出了借助于稱之為 BSP 樹的樹形數(shù)據(jù)結構的場
景表示。
1.3 八叉樹 | Octrees
八叉樹（octree）徙硅，或稱八元樹榜聂，是一種用于描述三維空間的樹狀數(shù)據(jù)結構。八叉樹的每個節(jié)
點表示一個正方體的體積元素嗓蘑，每個節(jié)點有八個子節(jié)點峻汉，這八個子節(jié)點所表示的體積元素加
在一起就等于父節(jié)點的體積。一般中心點作為節(jié)點的分叉中心脐往。
簡單來說休吠，八叉樹的空間劃分方式很簡單，即遞歸地進行規(guī)整地 1 分為 8 的操作业簿。如下圖瘤礁，
把一個立方體分割為八個同樣大小的小立方體，然后遞歸地分割出更的小立方體梅尤。這個就是
八叉樹的命名來源柜思。這種分割方式可以得到比較規(guī)則的結構岩调，從而使得查詢變得高效。
相似地赡盘，四叉樹是把一個二維的正方形空間分割成四個小正方形号枕。而八叉樹是四叉樹的三維
空間推廣。
1.4 場景圖 | Scene Graphs
BVH陨享、BSP 樹和八叉樹都是使用某種形式的樹來作為基本的數(shù)據(jù)結構葱淳，它們的具體區(qū)別在于
各自是如何進行空間分割和幾何體的存儲，且他們均是以層次的形式來保存幾何物體抛姑。然而
三維場景的繪制不僅僅是幾何體赞厕。
然而，渲染三維場景不僅僅只是渲染出幾何圖形定硝，對動畫皿桑，可見性，以及其他元素的控制蔬啡，
往往需要通過場景圖（Scene Graphs）來完成诲侮。
場景圖被譽為“當今最優(yōu)秀且最為可重用的數(shù)據(jù)結構之一∠潴。”Wiki 中的對場景圖的定義是
“場景圖（Scene Graph）是組織和管理三維虛擬場景的一種數(shù)據(jù)結構浆西，是一個有向無環(huán)圖
（Directed Acyclic Graph， DAG）顽腾。
場景圖是一個面向用戶的樹結構近零，可以通過紋理、變換抄肖、細節(jié)層次久信、渲染狀態(tài)（例如材質屬
性）、光源以及其他任何合適的內容進行擴充漓摩。它由一棵以深度優(yōu)先遍歷來渲染整個場景的
樹來表示裙士。
另外提一句，開源的場景圖有 Open Scene Graph 和 OpenSG 等管毙，有興趣的朋友們可以進行進一
步了解腿椎。
裁剪技術 | Culling Techniques
層次細節(jié) | LOD, Level of Detail
https://github.com/sp4cerat/Fast-Quadric-Mesh-Simplification 減面算法
