Vertex Hierarchy & Truly selective refinement of Progressive meshes

Vertex hierarchy

所谓的vertex hierarchy就是一个由Node节点组成的forest，这个森林在简化时候建立，森林里面有N课树。
每一棵树的root代表一个简化最后的base mesh上的一个vertex，而它的所有leaf notes都表示形成root note是从哪些vertices来的。也就是说一棵树的节点表示了root节点是怎么形成的，一个树就记录了简化的细节。从一个parent note向下分裂成两个child notes就是vertex split过程，而从两个child notes向上形成一个parent note就是一个halfedge collapse的过程！
vertex hierarchy的结构和简化的过程密切相关，简化过程之后选择的半边的次序不一样的话，最后形成的vertex hierarchy当然也不一样。一旦简化结束之后，这个相应的vertex hierarchy也就是构建完毕了。此后，这个vertex hierarchy可以供selective refinement使用，方便地形成各个level下的mesh，和多分辨率有关系。

Truly selective refinement of Progressive meshes

目的：为了能够任意选择当前level下的一个顶点进行vsplit操作，而且每次vsplit只增加一个顶点。
将原来的PM结构中使用的两个关键的原子操作ecol(vs, vt, vu, vl, vr)和vsplit(vs, vt, vu, vl, vr)，改为ecol(vs, vt, vu, vl^, vr^)和vsplit(vs, vt, vu, vl^, vr^).
其中vl^和vr^是original mesh上的原始顶点, 而vl = active ancestor(vl^), vr = active ancestor(vr^). 这个active ancestor的函数是关键，但其实就在vertex hierarchy中体现了！要找一个节点的当前有效的祖先，只需要从这个节点出发，往上找它的当前有效的父节点就可以了。 所谓的“当前有效”，也就是在当前这个分辨率中，在这个level中。

Reference:
[1]Garland97, QEM
[2]Kim, Lee 2001. Truly selective refinement of progressive meshes.

Quadric Error Metric (QEM), Preserving Boundaries -网格简化

Garland97的论文中提到为了保护边界在简化的过程当中能尽量幸免，在计算每一个顶点的quadric的时候，是将边界面F沿其边界边e生成一个垂直面，这个垂直面的quadric也加入到e的两个端点的quadric中。详细请看原文的第六节。
下图是我对一个平面过简化效果图：

左图是1089个顶点的原图, 中间是没有加入preserving boundaries控制的100个点的简化图，第三图加入控制后的100个点的简化图，第四图是加入控制后简化为4个顶点的图。
其实加入垂直面的意义是使得边界点更趋向于往尽量成一条直线上的边界点做收缩。也就是说这将要被收缩的两个边界点所在的各自直线（这两直线当然是相连的）尽量不要成90度。因为90度的时候，点到垂直面的距离最大，收缩代价最大（这就是quadric的意义）。
> 2007.12.01
从上面的简化图中，可以看出有些三角形是发生了overlapping，后来加入的防止方法是检测一邻域里面的面的normal的方向的变化，如果变化例如大于90度就当作翻转。

"Mean Saliency", siggraph2005的论文

下面左边是mesh saliency化, 右边是的mean curvature颜色化

"Mean Saliency", siggraph2005的论文。

概述
将Image中找寻关键部位的概念引入了3D的mesh。所谓关键部位，是指容易吸引人注意力的地方，也许更准确的说是特征部位。在image中，那些部位是shape和lighting的function， 而在mesh中，暂时只考虑geometry/shape。
那么怎么表示mesh中哪些顶点是特征的是关键的呢？它是给每一个顶点一个标量值，也就是saliency(vi)。值大的表示这个点“突出”，值小的表示这个点“一般”。举个例子，一个球形的mesh，其surface上的所有顶点的saliency值都是一样的。

怎么求顶点的saliency值
论文中给出的算法是：首先假设是在scale 1下，这时，参数sigma_1 = 2 * epsilon, epsilon = 0.3% * 模型的bounding box的对角线长度。
1.求出每一个顶点的mean curvature，这些标量值是不变的了。2. 求出每一个顶点在sigma_1下的gaussion-weighted average mean curvature，G(vi, sigma_1)。这个公式详细请看论文。其中有个注意的地方是，使用都了当前顶点两倍sigma_1距离之内的邻居顶点。然后再求出G(vi, 2*sigma_1)。3。 求出每一个顶点的saliency值，saliency(vi) = abs(G(vi, sigma_1) - G(vi, 2*sigma_1)).
将上面的过程重复5次，也就是scale 1, scale 2, scale 3, scale 4 , scale 5这论文中所谓的multi-scales。其中，scale 2时，sigma_2 = 3 * epsion; scale 3: sigma_3 = 4 * epsilon; scale 4: sigma_4 = 5 * epsilon.
最后一步是将每一个顶带你在5个scales下的saliency值做非线性的求和。具体公式也请看论文。

应用
其中一个应用就是改进Quadric error metric （QEM）简化算法。在每一个顶点的quadrc上乘以自己的saliency值，当然了这个saliency值已经过放大的。这其中体现了：saliency值大的顶点，更能表现重要性，应该在更后面被收缩。这和quadric(vi)值大的顶点推后被收缩是一致的。

Laplacian Operators

一般遇到的laplacian operators有两个：
(1).[Taubin 95] "A Signal Processing Approach to Fair Surfac Design"中提出的Uniform Laplacian, also known as Tuttle Laplacian.使用的就是uniform weighted,将邻域顶点的坐标加和再平均。这是最简单的拉普拉斯算子。
(2) [Desbrun 99] "implicit fairing of irregular meshes using diffusion and curvature flow"中提出的Cotangent Laplacian. 使用的正是常说的Cotangent weight.

Laplacian Coordinate将一个laplacian operator应用到一个vertex就获得这个vertex的laplacian coordiante(这是一个向量),而这个laplacian operator的系数, 也就是the so-called laplacian coefficients.我的感觉是：某个vertex上的laplacian值反映了这个顶点于其邻域(neighborhood vertices)的关系。PS. 所谓的邻域，常见的为一个顶点的one-ring neigborhood.

我所come across的应用：
(1)利用Cotangent weight求Discrete Mean Curvature Normal of a vertex(这也是一个向量值)。H(vi) = (1/Area(vi) * [laplacian coordinate(vi)]；其的大小(标量值)就是某个顶点的mean curvature.这好像是反应了mesh model的固有特征。通过求解model中的顶点mean curvature值，可以直观的看到这个model的光顺性(这是我以为的,现不知对否）。在许多论文中，提到Laplacian operator的时候都常提到Mean Curvature.
(2)Laplacian smoothing常说的平滑smoothing可能包括了denoise and fairing两种。我暂时取狭义的denoise为smoothing。Laplacian smoothing：the classical Laplacian smoothing, where every new vertex of the meshis moved to the barycenter of its neighbors.vertex_new_position(vi) = vertex_old_position(vi) + laplacian_normal(vi);
(3)laplacian surface editting[O.Sorkine 2004].其实我正是看此paper的时候才开始认真查阅laplacian的信息的。当中拟合surface editting前后的laplacian coordiante of vertices来达到目的。可惜自己理解不够。

Progressive Mesh

刚完成了使用了OpenMesh library完成了Progressive Mesh的写出，明天要完成对其的重新读入。
有兴趣的可以讨论一下。
---------------------------------------
2007-11-12
Hoppe论文中是使用最小化energy来简化mesh的，而我很惭愧地至今没有对mesh上energy的conception有清晰的理解，所以我是通过QEM算法来简化得到PM结构的。
但是我还希望能做到在PM结构上进行任意点的truely select refinement。在2001年的一paper"Truly selective refinement Of Progressive Meshes"中，似乎证明了对任意点的selective refine是可以进行的。当中引入了两个concept，dual piece of a vertex 以及 cut vertex of Vs。从中，我对QEM中的edge contract简化过程有个一个新的理解，整个simplification process中，其实就是mesh中某些三角形的扩张过程！扩张的结果？:-) think about it yourself