Geometry
🥏

Geometry

Tags
GAMES101
Published
May 11, 2022
Author
 
notion image

Implicit

隐式的集合,拿了空间中的一个点,为了表示集合的一个面。不会告诉点具体在哪,会告诉点所满足的关系。满足一定关系的点,都在一个表面上,把点做个归类,例如球的公式。

DIstance Function

notion image
对于一个集合,不描述表面,而表述一个点的最近距离。对距离函数做融合、Blend。
距离函数:空间中任何一个点、到表述的集合形体上的任意一个点的最小距离,距离可正可负。如果点在物体外,距离为正,如果点在物体内,则可以算出点到表面的最小距离,且距离为负。可以把空间中任意一个点都定义成一个值。
如上图,如果把两个球的距离函数都算出来,就可以做个Blending。再恢复成原来的物体。
notion image
第一行假设A左边三分之一是黑的,右边是白的,B同理,左边三分之二是黑的,那么Blending之后希望得到的是左边三分之一平均后是黑的,中间三分之一是灰的,右边三分之一是白的。怎么求Blending呢?可以Blend 两个距离函数。
第二行0左边是距离为负,右边是距离为正。Blend之后,0的位置就是边界,也就是我们求出来BLend形状的边界。
notion image
得到Blend之后的距离函数,怎么样恢复成表面呢?那就把0的位置全找出来
notion image
距离函数可能不太好用式子来表达,还可以通过某种方法来表达,例如水平集。函数的表述写在格子上,在中间0的地方,就可以把整个函数试图描述的物体表面提出来。
函数为0可以得到一条曲线,0.1 处也可以得到一条曲线。这种概念在地理得到广泛应用:等高线。水平集关注的是在哪里等于0,例如双线性插值来求。
水平集也可以定义三维中的格子,这就和纹理联系上了。如果我们有个三维的纹理,或者是人体的不同位置、密度。那么怎么提取出物体的表面呢,我们可以根据密度等于某个密度,找到所有的对应的位置,从而找到表面。
notion image
notion image
水花也可以通过水平集/距离函数来描述。

Fractals (分型)

notion image
分型是指自相似,自己的一个部分和整体长得像,和递归概念类似。例如雪花、六边形的边上又有六边形。
中间的是一种植物、西兰花。凸起里放大看又有凸起。是自然界分型的一个例子。在渲染的时候会引起强烈的走样,因为变化的频率实在太高。

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

 
notion image
需要特别多的点,三维扫描的输出一般都是点云。这样就会涉及一个问题:给一个点云,如何将其变为三角形面?有很多研究在做。
点云密度低就很难画,所以不会很多用点云。有不同的Shading方法,就会看到不同连续的面。
 

Polygon Mesh

notion image

The Wavefront Object File (.obj) Format

我们经常在图形学中是如何表示这种三角形面形成的物体的?
notion image
文本里面有一堆点、纹理坐标和法线来组织起来。左图描述的是一个立方体,前八行空间中有八个点。右边vn开头是法线,立方体有六个面、六个法线,自动建模有很多冗余的地方(右图有八行),例如29、30行是一回事,不考虑数字精度问题。再定义12个纹理坐标,也有冗余。
连接方式通过 f(face)来定义,哪三个点连接形成三角形。(5/1/1)(v 顶点, vt 纹理坐标,vn 法线)。而一行有三个点,来描述一个三角形。

Curves

notion image
notion image
无限放大区域,会看到都是光滑的。

Bézier Curves(贝赛尔曲线)

用一系列的控制点,去控制某一个曲线。
notion image
通过四个点,可以定义曲线的起始点和终点一定在P0和P3上,并且起始切线在P0 P1方向,结束切线在 P2 P3方向。曲线不一定要经过控制点。
怎么画呢?
notion image
用任意多个点,怎么画出贝赛尔曲线?
notion image
在任意一个时间 t (0~1之间),找出曲线的点在平面上哪一个位置即可。将画曲线的事情转化为找一个点的算法。
左边的 b10 点在时间 t 时点的位置,右边b11则是同一时刻另外一个点的位置。
notion image
将其连起来,再在线段上面找 t 时间的位置,点上一个点,这个点就是贝塞尔曲线在时间 t 所在的位置。
notion image
 
notion image
因为显式表示要么是直接定义,要么参数定义,所以 t 是参数,所以贝塞尔曲线是显式表示。
notion image
原本四个点,在这四个点三个线段上面再找 t 时刻的位置,b10 b11 b12,再连起来。这样就将问题规模变成了三个点。递归的解出最后一条线段的时候 t 时刻的点的位置。
notion image
notion image
notion image
notion image
notion image
画一条竖线,四条线的交点坐标加起来都等于1
 
通过定义一系列跟时间有关的多项式,来对不同的控制点进行插值(组合也是插值),得出一个新的点,这个点就是曲线上的点。这个概念不仅被应用在贝赛尔曲线上,也应用在其他更复杂的曲线上。
 
四个控制点贝塞尔曲线的性质:
notion image
📖
简单来说,“仿射变换”就是:“线性变换”+“平移”。
贝塞尔曲线在仿射变换下有很好的性质:
贝塞尔曲线可以在不同的顶点做仿射变换,再重新对变换之后的顶点再画一个贝赛尔曲线,这个贝塞尔曲线一定和以前的贝塞尔曲线一样。
这给了我们一个很好的性质:
如果我们想对贝塞尔曲线做仿射变换,那只需对几个控制点做仿射变换,对仿射变换后的控制点重新画一条贝赛尔曲线即可。这样我们不需要对曲线每个点都记录着。但不一定对其他变换也如此,例如投影就不一样。
 
凸包(Convex Hull)
贝赛尔曲线一定在所有的控制点的凸包内。在二维欧几里得空间中,凸包可想象为一条刚好包著所有点的橡皮圈。
如果所有控制点都在一条线上,那么贝塞尔曲线可以根据凸包性质可得,那么贝塞尔曲线一定被限制在这条线上,一定是这条线自己。
notion image

Piecewise Bézier Curves

notion image
曲线不直观,不好被控制点控制。因此可以用很少的点来定义一段曲线,再把这些曲线连起来。
逐段的贝赛尔曲线每一段曲线都可以由四个控制点控制。
notion image
notion image
那么怎么保证曲线是光滑的?要保证导数连续
notion image
 
notion image
notion image
notion image
C1 连续也可称为一阶导数连续。C2 连续则为二阶导数连续。

其他种类的曲线

notion image
在任意的一个地方都满足一定的连续性。
上图是拿一个树枝一样的东西,再拿其他东西固定住,保证样条会经过固定的点。可控的曲线成为样条。

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

notion image
怎么用贝赛尔曲线来得到贝塞尔曲面呢?
notion image
notion image
相当于双线性插值的理解,在两个方向上分别应用贝赛尔曲线即可。
  1. 首先,在平面上定义 4*4 个控制点,每一行四个控制点能得到一条曲线。
  1. 在这个曲线上,在不同的时间 t 会在不同的位置
  1. 如果把四个不同的点,认为是另一条贝塞尔曲线的控制点(图中蓝色的线)。
  1. 再给定时间 t (不同的时间 t),线不断地扫,就会得到一个曲面。
notion image
notion image
水平方向上需要一个时间 t,四个点连成一个曲线还要有一个时间 t,所以它是一个二维的(u,v)控制的东西。
notion image
因此我们可以用某一个 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 正规化 让三角形不会出现特别尖特别长的三角形,这样会有很不错的性质。
notion image

Mesh subdivision 网格细分

Common subdivision rule for triangle meshes
  1. First, create more triangles (vertices)
  1. Second, tune their positions
Loop 细分其中的Loop跟循环没关系,是发明人的姓。
notion image

Loop Subdivision - Loop 细分

notion image
细分之后,就要调整三角形的位置。对于Loop细分,把三角形顶点区分成新顶点和老顶点。
对于新顶点,被两个三角形共享的顶点,可以通过下图公式来进行加权平均。A和B离白点近,因此贡献更多一些。
notion image
对于旧的顶点,原来周围旧的顶点都会有贡献,自己也会有贡献。
定义两个值:
  • n:顶点的度(图论中的度,下图中度为6,连接了六个顶点)
  • u:考虑到顶点的度,定义了一个公式。
下图的公式(1-n*u)是指这个顶点连的三角形越多,自己越不重要
notion image
一个三角形分成四个,顶点位置都经过细微调整。越细分,越密越光滑。
notion image
⚠️
如果模型原先是三角形网格,才能用 Loop 细分。如果不是,下面 Catmull-Clark 细分的非常好。

Catmull-Clark Subdivision (General Mesh)

notion image
  • quad face:四边形面
  • Non-quad face:非四边形面
  • Extraordinary vertex(奇异点):度不为四的点,都是奇异点。
细分步骤:
每一条边取中点,每一个面也取中点,将他们都连起来。
下图左上角的大四边形被分成了四个四边形
notion image
引入的新的点,度为3。因此细分后引入多两个奇异点,现在一共四个奇异点。
细分后,所有非四边形面都消失了。也就是说奇异点数不可能再增加。
notion image
notion image
现在知道了如何增加新的点,下面讲讲怎么调整点。
点被区分为三类:面中心的点(下图左上)、边中心的点(下图右上)、老的点(下图下方)。
老的点根据四边面中心的点来调整。
notion image
notion image

Mesh Simplification 曲面简化

Goal: reduce number of mesh elements while maintaining the overall shape
(下图 Flat Shading)
notion image
  1. 可能不得不简化模型,例如在移动端平台上
  1. 要看场合用相应复杂度的模型。下图下方,如果我们很远去观察骷髅,就不需要太多三角形,例如三千个的三角形和三万个三角形没啥区别,三百个三角形的也不错。
Mipmap 给了我们图像层次结构,如果我们用了简化的模型,用 Mipmap 较高层的像素点就行,就不需要把最底层最细的像素点都平均出来。这个意义来看,层次结构的几何,和层次结构的图像是差不多的。
但几何的层次结构是很难做的,特别是涉及到不同类型的几何之间,相互变化的时候。例如近了用三万个远了用三千个,那什么时候切换,切换的时候变化会不会太大?需要做过渡的话,过渡要怎么做?从一个几何形状到另一个几何形状,没有什么三线性插值,这块是图形学界造成困难的话题。

Collapsing An Edge 边坍缩

简化的其中一种方法。
就好像把两个点捏成一个点,这个边就不存在了。
notion image
要坍缩哪些边?哪些边是重要的?
二次误差指的是平方
notion image
上图左下中,对五个点求平均得到的点来代替,或者上面三个点求平均得出的点,都不太能用,因此使用误差度量来做。
二次误差:找一个最优的位置,使得新顶点到几个面距离的平方和达到最小。
对于整个模型,有这么多的边,我都假设如果我坍缩这条边,并且我把坍缩后的点放在最佳位置上,会达到多大的二次度量误差。也就是说每一条边,我都可以假设如果我坍缩它,有多大的误差。
这样我可以先坍缩误差最小的,然后坍缩第二小的......
notion image
于是有了下面的算法:
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)
notion image
奶牛眼镜处较平缓,因此坍缩的地方的多。