Restricted Quadtree

Restricted Quadtree

Quadtree主要用于在2D和2.5D的一种划分方法。

比如：

这是一个Quadtree的划分

在Terrain中如果直接使用Quadtree来进行划分，会产生Crack问题，其原因就是在相邻的两个节点的共用边上，Level高的顶点数比Level低得顶点数多。

比如

Restricted Quadtree可以用来解决上面的问题。

Restricted Quadtree的相邻节点最多只能相差一级。

对于上面的这个Quadtree结构他就不是一个Restricted Quadtree

其中：对于不能再细分的Node称为Atomic Node。

在一个Restricted Quadtree中，一个节点(Square)由九个点来代表，分别是四个Corner Vertex和5个Middle Vertex。

Persistent Vertice : 一个子节点和直接父节点共享的顶点称为Persistent Vertex

Non-Persistent  Vertices : 除了Persistent Vertice的就是Non-Persistent Vertice

Quadtree的Triangulation

构建了Quadtree过后，需要将其三角面化(Triangulation)，这个过程通过对上面的九个点构造三角形

在一个节点(叶节点)当中，每一条边对应一个三角形，如果该边对应的相邻节点存在并且Level高于自己的Level，那么这个三角形被二分。

如图所示：

对于一个Square的邻接情况如上左图所示，对于case 0, 1, 3都不会有划分，而Case 2对该边对应的三角形进行了划分。这四种情况就是一个Square的边的所有情况。

Reference

Ron Sivan, Hanan Samet. "Algorithms for constructing quadtree surface maps"