Implicit
隐式的集合,拿了空间中的一个点,为了表示集合的一个面。不会告诉点具体在哪,会告诉点所满足的关系。满足一定关系的点,都在一个表面上,把点做个归类,例如球的公式。
DIstance Function
对于一个集合,不描述表面,而表述一个点的最近距离。对距离函数做融合、Blend。
距离函数:空间中任何一个点、到表述的集合形体上的任意一个点的最小距离,距离可正可负。如果点在物体外,距离为正,如果点在物体内,则可以算出点到表面的最小距离,且距离为负。可以把空间中任意一个点都定义成一个值。
如上图,如果把两个球的距离函数都算出来,就可以做个Blending。再恢复成原来的物体。
第一行假设A左边三分之一是黑的,右边是白的,B同理,左边三分之二是黑的,那么Blending之后希望得到的是左边三分之一平均后是黑的,中间三分之一是灰的,右边三分之一是白的。怎么求Blending呢?可以Blend 两个距离函数。
第二行0左边是距离为负,右边是距离为正。Blend之后,0的位置就是边界,也就是我们求出来BLend形状的边界。
得到Blend之后的距离函数,怎么样恢复成表面呢?那就把0的位置全找出来
距离函数可能不太好用式子来表达,还可以通过某种方法来表达,例如水平集。函数的表述写在格子上,在中间0的地方,就可以把整个函数试图描述的物体表面提出来。
函数为0可以得到一条曲线,0.1 处也可以得到一条曲线。这种概念在地理得到广泛应用:等高线。水平集关注的是在哪里等于0,例如双线性插值来求。
水平集也可以定义三维中的格子,这就和纹理联系上了。如果我们有个三维的纹理,或者是人体的不同位置、密度。那么怎么提取出物体的表面呢,我们可以根据密度等于某个密度,找到所有的对应的位置,从而找到表面。
水花也可以通过水平集/距离函数来描述。
Fractals (分型)
分型是指自相似,自己的一个部分和整体长得像,和递归概念类似。例如雪花、六边形的边上又有六边形。
中间的是一种植物、西兰花。凸起里放大看又有凸起。是自然界分型的一个例子。在渲染的时候会引起强烈的走样,因为变化的频率实在太高。
Implicit Representations - Pros & Cons
Pros:
- compact description (e.g., a function)
- 对于存储有利,一个公式就能描述形状
- certain queries easy (inside object, distance to surface)
- 小于0还是大于0
- good for ray-to-surface intersection (more later)
- 很容易求与光线的求交
- for simple shapes, exact description / no sampling error
- easy to handle changes in topology (e.g., fluid)
Cons:
- difficult to model complex shapes
Explicit
Point Cloud
需要特别多的点,三维扫描的输出一般都是点云。这样就会涉及一个问题:给一个点云,如何将其变为三角形面?有很多研究在做。
点云密度低就很难画,所以不会很多用点云。有不同的Shading方法,就会看到不同连续的面。
Polygon Mesh
The Wavefront Object File (.obj) Format
我们经常在图形学中是如何表示这种三角形面形成的物体的?
文本里面有一堆点、纹理坐标和法线来组织起来。左图描述的是一个立方体,前八行空间中有八个点。右边vn开头是法线,立方体有六个面、六个法线,自动建模有很多冗余的地方(右图有八行),例如29、30行是一回事,不考虑数字精度问题。再定义12个纹理坐标,也有冗余。
连接方式通过 f(face)来定义,哪三个点连接形成三角形。(5/1/1)(v 顶点, vt 纹理坐标,vn 法线)。而一行有三个点,来描述一个三角形。
Curves
无限放大区域,会看到都是光滑的。
Bézier Curves(贝赛尔曲线)
用一系列的控制点,去控制某一个曲线。
通过四个点,可以定义曲线的起始点和终点一定在P0和P3上,并且起始切线在P0 P1方向,结束切线在 P2 P3方向。曲线不一定要经过控制点。
怎么画呢?
用任意多个点,怎么画出贝赛尔曲线?
在任意一个时间 t (0~1之间),找出曲线的点在平面上哪一个位置即可。将画曲线的事情转化为找一个点的算法。
左边的 b10 点在时间 t 时点的位置,右边b11则是同一时刻另外一个点的位置。
将其连起来,再在线段上面找 t 时间的位置,点上一个点,这个点就是贝塞尔曲线在时间 t 所在的位置。
因为显式表示要么是直接定义,要么参数定义,所以 t 是参数,所以贝塞尔曲线是显式表示。
原本四个点,在这四个点三个线段上面再找 t 时刻的位置,b10 b11 b12,再连起来。这样就将问题规模变成了三个点。递归的解出最后一条线段的时候 t 时刻的点的位置。
画一条竖线,四条线的交点坐标加起来都等于1
通过定义一系列跟时间有关的多项式,来对不同的控制点进行插值(组合也是插值),得出一个新的点,这个点就是曲线上的点。这个概念不仅被应用在贝赛尔曲线上,也应用在其他更复杂的曲线上。
四个控制点贝塞尔曲线的性质:
简单来说,“仿射变换”就是:“线性变换”+“平移”。
贝塞尔曲线在仿射变换下有很好的性质:
贝塞尔曲线可以在不同的顶点做仿射变换,再重新对变换之后的顶点再画一个贝赛尔曲线,这个贝塞尔曲线一定和以前的贝塞尔曲线一样。
这给了我们一个很好的性质:
如果我们想对贝塞尔曲线做仿射变换,那只需对几个控制点做仿射变换,对仿射变换后的控制点重新画一条贝赛尔曲线即可。这样我们不需要对曲线每个点都记录着。但不一定对其他变换也如此,例如投影就不一样。
凸包(Convex Hull)
贝赛尔曲线一定在所有的控制点的凸包内。在二维欧几里得空间中,凸包可想象为一条刚好包著所有点的橡皮圈。
如果所有控制点都在一条线上,那么贝塞尔曲线可以根据凸包性质可得,那么贝塞尔曲线一定被限制在这条线上,一定是这条线自己。
Piecewise Bézier Curves
曲线不直观,不好被控制点控制。因此可以用很少的点来定义一段曲线,再把这些曲线连起来。
逐段的贝赛尔曲线每一段曲线都可以由四个控制点控制。
那么怎么保证曲线是光滑的?要保证导数连续
C1 连续也可称为一阶导数连续。C2 连续则为二阶导数连续。
其他种类的曲线
在任意的一个地方都满足一定的连续性。
上图是拿一个树枝一样的东西,再拿其他东西固定住,保证样条会经过固定的点。可控的曲线成为样条。
Other types of splines
B-splines(极其复杂)
- Short for basis splines
- 可以理解成:用伯恩斯坦多项式,在时间 t ,在几个不同的项,对不同的控制点做加权平均
- 也可以理解成:用控制点的位置对伯恩斯坦多项式进行加权求和。
- Bernstein多项式在这里充当着基函数的角色。
- Require more information than Bezier curves
- B样条是对贝赛尔曲线的一个扩展,比贝塞尔能力更强。
- 对于贝赛尔曲线,如果有十个点,如果动了一个点,那么曲线的其他部分也会发生变化。这对其他一些设计不太友好。可能只需改一些地方,希望有局部性的性质。局部性是指:改了一个点,我知道这个曲线最多改的范围内。(分段贝赛尔曲线就有这种性质)
- Satisfy all important properties that Bézier curves have (i.e. superset)
- 与贝塞尔曲线分析方法完全一样。算起来更复杂,还有一种样条叫 NURBS,相当于B样条更延伸的一部分。
To learn more / deeper, you are welcome to refer to Prof. Shi-Min Hu’s(胡事民) course:
曲线曲面方面说的透彻,也非常难。
Bézier Surfaces
怎么用贝赛尔曲线来得到贝塞尔曲面呢?
相当于双线性插值的理解,在两个方向上分别应用贝赛尔曲线即可。
- 首先,在平面上定义 4*4 个控制点,每一行四个控制点能得到一条曲线。
- 在这个曲线上,在不同的时间 t 会在不同的位置
- 如果把四个不同的点,认为是另一条贝塞尔曲线的控制点(图中蓝色的线)。
- 再给定时间 t (不同的时间 t),线不断地扫,就会得到一个曲面。
水平方向上需要一个时间 t,四个点连成一个曲线还要有一个时间 t,所以它是一个二维的(u,v)控制的东西。
因此我们可以用某一个 u 沿着四条得到的曲线上,得到时间 u 点在哪,就可以得到四个蓝色的点。再给一个 v,在四个点的曲线上找时间 v,就可以找到这个曲面在 u,v 参数下的位置。参数 u,v 在 0,1中就可以映射到曲面上任何一个点,因此贝塞尔曲线是显式地表示,因为是由参数控制的。
当然面的几何形状,用的最普遍的方法,还是 mesh 网格。对网格的操作,就是几何处理。
Mesh Operations: Geometry Processing
- Mesh subdivision 网格细分,图2→图3
- Mesh simplification 网格简化 图3→图4
- Mesh regularization 正规化 让三角形不会出现特别尖特别长的三角形,这样会有很不错的性质。
Mesh subdivision 网格细分
Common subdivision rule for triangle meshes
- First, create more triangles (vertices)
- Second, tune their positions
Loop 细分其中的Loop跟循环没关系,是发明人的姓。
Loop Subdivision - Loop 细分
细分之后,就要调整三角形的位置。对于Loop细分,把三角形顶点区分成新顶点和老顶点。
对于新顶点,被两个三角形共享的顶点,可以通过下图公式来进行加权平均。A和B离白点近,因此贡献更多一些。
对于旧的顶点,原来周围旧的顶点都会有贡献,自己也会有贡献。
定义两个值:
- n:顶点的度(图论中的度,下图中度为6,连接了六个顶点)
- u:考虑到顶点的度,定义了一个公式。
下图的公式(1-n*u)是指这个顶点连的三角形越多,自己越不重要
一个三角形分成四个,顶点位置都经过细微调整。越细分,越密越光滑。
如果模型原先是三角形网格,才能用 Loop 细分。如果不是,下面 Catmull-Clark 细分的非常好。
Catmull-Clark Subdivision (General Mesh)
- quad face:四边形面
- Non-quad face:非四边形面
- Extraordinary vertex(奇异点):度不为四的点,都是奇异点。
细分步骤:
每一条边取中点,每一个面也取中点,将他们都连起来。
下图左上角的大四边形被分成了四个四边形
引入的新的点,度为3。因此细分后引入多两个奇异点,现在一共四个奇异点。
细分后,所有非四边形面都消失了。也就是说奇异点数不可能再增加。
现在知道了如何增加新的点,下面讲讲怎么调整点。
点被区分为三类:面中心的点(下图左上)、边中心的点(下图右上)、老的点(下图下方)。
老的点根据四边面中心的点来调整。
Mesh Simplification 曲面简化
Goal: reduce number of mesh elements
while maintaining the overall shape
(下图 Flat Shading)
- 可能不得不简化模型,例如在移动端平台上
- 要看场合用相应复杂度的模型。下图下方,如果我们很远去观察骷髅,就不需要太多三角形,例如三千个的三角形和三万个三角形没啥区别,三百个三角形的也不错。
Mipmap 给了我们图像层次结构,如果我们用了简化的模型,用 Mipmap 较高层的像素点就行,就不需要把最底层最细的像素点都平均出来。这个意义来看,层次结构的几何,和层次结构的图像是差不多的。
但几何的层次结构是很难做的,特别是涉及到不同类型的几何之间,相互变化的时候。例如近了用三万个远了用三千个,那什么时候切换,切换的时候变化会不会太大?需要做过渡的话,过渡要怎么做?从一个几何形状到另一个几何形状,没有什么三线性插值,这块是图形学界造成困难的话题。
Collapsing An Edge 边坍缩
简化的其中一种方法。
就好像把两个点捏成一个点,这个边就不存在了。
要坍缩哪些边?哪些边是重要的?
二次误差指的是平方
上图左下中,对五个点求平均得到的点来代替,或者上面三个点求平均得出的点,都不太能用,因此使用误差度量来做。
二次误差:找一个最优的位置,使得新顶点到几个面距离的平方和达到最小。
对于整个模型,有这么多的边,我都假设如果我坍缩这条边,并且我把坍缩后的点放在最佳位置上,会达到多大的二次度量误差。也就是说每一条边,我都可以假设如果我坍缩它,有多大的误差。
这样我可以先坍缩误差最小的,然后坍缩第二小的......
于是有了下面的算法:
Iteratively collapse edges
Which edges? Assign score with quadric error metric*
- approximate distance to surface as sum of distances to planes containing triangles
- 为每一条边都打上分数,分数就是其二次度量误差。
- iteratively collapse edge with smallest score
- 从误差小的开始,一个一个地坍缩。
- 注意:坍缩了一条边之后,会影响其他边的二次度量误差。
- 最好有某种数据结构可以取最小值(O1),有可以动态地以最小的代价去更新其他受影响的元素。——优先队列(堆)
- greedy algorithm... great results!
- 我们以不断的对局部做最优解的方式,试图找到全局的最优解。——贪心算法
(Garland & Heckbert 1997)
奶牛眼镜处较平缓,因此坍缩的地方的多。