-
2020-07-07 10:16:20
多边形重心坐标求解
问题:异形柱咋在CAD图纸中准确放置,LocationPoint咋确定?
解决方法:通过重心求解定理一:已知三角形△A1A2A3的顶点坐标Ai ( xi, yi ) ( i =1, 2, 3) 。
它的重心坐标为:
xc = (x1+x2+x3) / 3 ; yc = (y1+y2+y3) / 3 ;定理二:已知三角形△A1A2A3的顶点坐标Ai ( xi , yi ) ( i =1, 2, 3) 。该三角形的面积为:
S = ( (x2 - x1) * (y3 - y1) - (x3 - x1) * (y2 - y1) ) / 2 ;
△A1A2A3 边界构成逆时针回路时取+ , 顺时针时取 -。
另外在求解的过程中,不需要考虑点的输入顺序是顺时针还是逆时针,相除后就抵消了。方法:
(1).以多边形的一个顶点O为原点(可以选输入的第一个点作为原点),作连接O与其他所有非相邻顶点的线段,将多边形(n条边)分为n-2个三角形。
多边形分解
(2).求每个三角形的面积和重心
设其中一个三角形的重心为G(cx,cy),顶点坐标分别为A1(x1,y1),A2(x2,y2),
A3(x3,y3),则有cx = (x1+x2+x3) / 3 ; cy = (y1+y2+y3) / 3 ;
面积为S = ( (x2 - x1) * (y3 - y1) - (x3 - x1) * (y2 - y1) ) / 2 ;
(3).求多边形的重心
公式:cx = (∑ cx[i]*s[i]) / ∑s[i] ; cy = (∑ cy[i]*s[i] ) / ∑s[i];其中(cx[i], cy[i]), s[i]分别是所划分的第i个三角形的重心坐标和面积。另外,在(2)中求每个重心坐标时要除以3,实际上不需要在求每个三角形坐标时都除以3,只需要求出∑ cx[i]*s[i]后一次性除以3即可。C#代码:
public class Point3D { public double X; public double Y; public double Z; public Point3D(double a = 0, double b = 0,double c=0) { X = a; Y = b; Z = c; } } class Program { static void Main(string[] args) { List<Point3D> list1 = new List<Point3D>() { new Point3D(0, 0, 0), new Point3D(0, 1, 0), new Point3D(1, 1, 0) , new Point3D(1, 0, 0) ,new Point3D (2,0.5,0)}; //S[i] List<double> list2 = new List<double>(); //Cx[i] List<double> list3 = new List<double>(); //Cx[i] List<double> list4 = new List<double>(); for (int i=1;i<(list1.Count()-1);i++) { double s = Area(list1[0], list1[i], list1[i+1]); list2.Add(s); double Cx = (list1[0].X+ list1[i].X+ list1[i+1].X) / 3; list3.Add(Cx); double Cy = (list1[0].Y + list1[i].Y + list1[i + 1].Y) / 3; list4.Add(Cy); } //三角形的个数n-2 double S = 0; //Cx[i]*S[i]和 double a = 0; //Cy[i]*S[i]和 double b = 0; double CCx = 0; double CCy = 0; for (int i=0;i<(list1.Count-2);i++) { S = S + list2[i]; a = a + list3[i] * list2[i]; b = b + list4[i] * list2[i]; } CCx = a / S; CCy = b / S; //输出多边形重心坐标(X,Y) Console.Write(CCy+"\n"+CCy+"\n"+list1[0].Z); Console.ReadKey(); } public static double Area(Point3D point3D1, Point3D point3D2, Point3D point3D3) { double S = ((point3D2.X - point3D1.X) * (point3D3.Y - point3D1.Y) - (point3D3.X - point3D1.X) * (point3D2.Y - point3D1.Y)) / 2; return S; } }
更多相关内容 -
四边形的重心坐标族的单调性
2021-02-25 21:48:04四边形的重心坐标族的单调性 -
图形学基础知识:重心坐标(Barycentric Coordinates)
2021-03-30 15:27:20前言 在前面的文章中我们经常...在讲三角形的重心坐标前,我们先来看一看直线上的重心坐标是怎么定义的。 在生活中想必大家都看过或挑过担子吧,人们在担子两边挂上重物,然后用肩膀扛起担子。如果担子两边的物体差.前言
在前面的文章中我们经常提到知道某个三角形三个顶点的属性,然后就可以求出三角形内部某一点对应的属性。例如深度缓存的时候,高洛德着色的时候等等,但是我们一直没有说具体应该如何计算,本文就来介绍一下这一部分内容。
想要计算三角形内部某一点对应的属性,也就是我们一直说的三角形的插值,就需要用到重心坐标的概念。
直线的重心坐标
在讲三角形的重心坐标前,我们先来看一看直线上的重心坐标是怎么定义的。
求直线上任意一点
设我们有两个点 A
和 B
,它们可以连成一条直线。那么该直线上的任意一点 P
必然满足:
k为一个常数,其值也很好求,取任意轴三个点值进行计算即可:
然后我们可得:
因为
即
。
而
通过向量的减法,我们可以理解为
,同样的
,那么就可得到
,然后可以得到
,最终简化可得:
而
,
,
分别代表的就是 P,A,B三个点的坐标,因此可得
P = (1 - k)A + kB
因为 P = ((1-k)+k)P 因此上面式子可以变为 (1-k)A+kB-((1-k)+k)P=0,化简为 (1-k)(A-P)+k(B-P),即:
几何意义
前面我们得到
,即AP的长度
为 AB的长度
的k倍。而 BP的长度
又等于
,因此
的长度为
的 1-k 倍。所以可得:
因为长度是没有正负的,然而实际上k可能为负数,就会导致上面的公式不对。我们先来看看下面三种情况:
0 <= k <= 1
此时P在AB之间,如下图
可得
k < 0
k < 0 ,也就是说
方向和
相反,此时P在AB之外,离A更近一些,如下图
可得
k > 0
和前者相反,如下图
可得
总结
可以发现我们只要取绝对值,就可以满足上面的各种情况了,因此
直线上的重心坐标
通过上面的推导,我们就知道直线AB上的任意一点P,都可以由一个k来计算出来的。当然了,也可以通过P来推出k的值,怎么求上面已经说明过了。
若我们设 j = 1 - k,那么
P = jA + kB
j + k = 1
这样的话我们P就可以使用 (j, k) 的方式来表示,这种表示方式就是我们的重心坐标。同时需要注意,因为重心坐标是根据某一条直线的AB两点所定义的,因此不同的直线各自会有各自的重心坐标。
为什么叫重心坐标
在生活中想必大家都看过或挑过担子吧,人们在担子两边挂上重物,然后用肩膀扛起担子。如果担子两边的物体差不多重,我们要保持担子的平衡只需要把肩膀撑在担子的中间即可。但如果担子有一头特别的重,我们需要把肩膀尽可能的往重的那头靠近,才能保持住担子的平衡。
我们假设有线段AB(也就是担子),在A下面挂了质量为
的物体,在B下面挂了质量为
的物体,如下图:
若
,那么重心P(肩膀的支撑点)应该在哪?自然线段的中心点了,如下图:
若
呢 ,那么P点的位置又应该在哪呢?通过常识我们应该知道,此时P点位置离A点更近一些,如下图:
那么如果
> 0,
= 0 呢?那不就变得担子一边没有重物,我们只需要扛有重物的那一边了,即P在A点上,如下图:
既然可以等于0了,那么能不能等于负数呢?即
> 0,
< 0,P会在哪呢?之前说
和
代表的质量,那么我们怎么理解负数的质量呢,我们知道挑担子的时候质量会造成向下的重力,那么负数的质量我们可以理解成在B点有一个向上的力,等于有人在担子的一边帮你搭把手,那就变成不是挑担子了,而是两个人抬东西了。两个人要用棍子抬一个东西,那么东西自然是在两个人中间了,因此P会在A的左边,如下图:
或
某个值小于0的情况,也就把我们的P的位置从线段AB拓展到直线AB上了。当然了,我们不能
< 0,
< 0,这样担子就飞起来了。
上面的例子说明了只要确定了
和
的值,也就确定了 重心P 的位置,怎么样是不是和前面所说的很像?事实上,只要保证
, 我们的
就是前面所说的 j 的值,而
就是 k 的值,所以称这样的坐标为重心坐标。
三角形上的重心坐标
定义
与直线上任意一点满足 P = jA + kB 一样,在三角形ABC所在平面上的任意一点P同样满足
P = iA + jB + kC
i + j + k = 1
那么P用 (i, j, k) 的方式表示,就是在三角形上的重心坐标。同样的,因为重心坐标是由三角形的三个顶点所定义的,因此不同的三角形有各自的重心坐标。
同样的,若点P要在三角形内部或边上,需要满足 i >= 0,j >= 0,k >= 0,否则点P在三角形所在平面外。
同样由于 P = (i+j+k)P = iP+jP+kP,因此我们可得到 iA+jB+kC-iP-jP-kP = 0 即:
和直线比喻成担子类似,对于三角形也是一样的,我们可以假设有个三角形,它本身是没有质量的,但是我们在它的三个顶点位置分别悬挂了不同质量的物体,如果我们能找到其中一个点,能够使三角形保持平衡,那么这个点就是三角形的重心,如下图。
三角形和直线的关系
我们将三角形ABC的某个顶点(例如C)和三角形内任意一点P连线,并衍生到三角形的某条边上,设交点为D,如下图:
那么D点在AB上的位置,我们不就可以用直线的重心坐标表示么,我们设:D = xA + yB,其中 x + y = 1
知道D点坐标后,那么P点在CD的坐标我们又可以用直线的重心坐标表示,我们设:P = wC + zD,其中 w + z = 1
把D带入得:P = wC + z(xA + yB) = zxA + zyB + wC,而 zx + zy + w = z(x + y) + w = z + w = 1
那么设 i = zx,j = zy,k = w,不就证明了 P = iA + jB + kC 成立。
解i,j,k的值
接下来,我们来看看i,j,k三个值怎么计算,因为 i+j+k=1,因此k=1-i-j,也就是只要求两个未知数i和j即可。那么我们只需要找到两个方程组,解二元一次方程式即可。
因为 P = iA + jB + kC 因此
,从中我们就可以取得两个方程式:
注:取x,y的话,也方便在二维空间中理解,当然也可以去x,z或y,z去计算。
解得
去 i ,得
此时方程式中只有一个 j 是变量,我们继续解,得
解得
解得
去分母,解得
即可求得 j 的值:
同理可解的 i 的值:
至于k的值,1-i-j 即可。
几何意义
我们将点P和三个顶点分别连线,可以得到三个新的三角形,如下图:
我们设三角形的总面积为 s,三角形PBC的面积为 a,三角形PAB的面积为 c,三角形PCA的面积为 b,那么可得:
也就是说重心坐标和每个顶点所相对的三角形(例如A对应的是PBC)的面积比有关。
我们来简单的推导一下:
前面我们知道
而
的值,不就是
的x值么,我们标记为
,其他项也同理,那么我们可以得到
不知道大家对上面的这种
式子熟不熟悉,它正是二维向量叉乘的模(不熟悉的可以看下叉乘相关知识)。因此我们可以得到
设夹角CBP为 α ,那么分子
,同理分母就是三角形ABC的面积,因此
成立,其他也同理。
三角形的重心
我们知道三角形的重心点为三条中线的交点,如下图:
中线即是将三角形分成面积相等的两部分,例如
。
我们来看下O点的重心坐标是多少,根据前面,我们知道我们可以通过三个三角形 AOB,AOC,BOC的面积比来求得重心坐标。那么我们就来看看这三个三角形的面积比。
首先因为
而他们的高相等,因此 BD = DC,可得
,那么
。同理我们可得
因此三角形的重心坐标即为
。同样的,关于重心O点的坐标我们可以通过下面公式计算:
实际应用场景
前面哔哔赖赖了一大堆,我们知道可以通过重心坐标来计算三角形内某点的坐标,即
P = iA + jB + kC
ABCP代表的都是位置信息,我们可以通过位置信息求出重心坐标。而重心坐标牛逼就牛逼在,我们可以把ABCD的信息用别的任何信息来代替,例如颜色,法线,uv,深度等,然后套用上面的公式即可求出P点对应的属性。
例如我们A点红色(1,0,0),B点绿色(0,1,0),C点蓝色(0,0,1),那么三角形内任何点的颜色就等于它的重心坐标,例如重心点颜色为
。
我们可以简单的用Unity写个demo验证一下
首先用下面脚本绘制一个三角形,三角形内部的颜色Unity已经为我们插值好了
[ExecuteInEditMode] public class Triangle : Graphic { Vector2 positionA = new Vector2(70, 40); Vector2 positionB = new Vector2(100, 100); Vector2 positionC = new Vector2(40, 70); protected override void OnPopulateMesh(VertexHelper vh) { vh.Clear(); vh.AddVert(positionA, Color.red, Vector2.zero); vh.AddVert(positionB, Color.green, Vector2.zero); vh.AddVert(positionC, Color.blue, Vector2.zero); vh.AddTriangle(0, 1, 2); } }
效果如下(注意color space要使用gamma的):
然后怎么验证呢,我们可以创个小Image,然后通过它的坐标和三个顶点的坐标,我们就可以计算出小Image所在点对应的重心坐标,知道重心坐标和三个顶点颜色后,就可以计算出对应颜色,赋值给小Image,然后对比下颜色即可。代码如下:
using UnityEngine; using UnityEngine.UI; public class NewBehaviourScript : MonoBehaviour { public Image self; Vector2 a = new Vector2(70, 40);//red Vector2 b = new Vector2(100, 100);//green Vector2 c = new Vector2(40, 70);//blue void Update() { Vector2 p = transform.position; float i = (-(p.x - b.x) * (c.y - b.y) + (p.y - b.y)*(c.x - b.x)) / (-(a.x - b.x)*(c.y - b.y) + (a.y - b.y)*(c.x - b.x)); float j = (-(p.x - c.x) * (a.y - c.y) + (p.y - c.y)*(a.x - c.x)) / (-(b.x - c.x)*(a.y - c.y) + (b.y - c.y)*(a.x - c.x)); float k = 1 - i - j; Debug.Log($"({i}, {j}, {k})"); self.color = new Color(i, j, k); } }
效果如下:
可以看出在三角形内部时,我们计算得到的颜色和Unity做好的插值是一样的。
至于除了颜色外的其他属性插值,原理也都是一样的,只要了解重心坐标了即可。也就是说我们只需要先通过四个点的位置信息算出重心坐标,然后就可以通过重心坐标来计算其他属性的插值。
重心坐标与投影
前面一套套下来,我们可能会有个疑惑,重心坐标的计算和z轴没有关系么?
注:其实更准确的说法是只和x,y,z中其中任意两项有关,具体可以看求i,j,k时,我们取的二元一次方程式是哪两个轴,当然通常情况下,就是取的x和y。
不考虑z,等于把空间中的三角形去掉z,即投影到平面xy上,即原本的A点
,B点
,C点
变成了A'点
,B'点
,C'点
。原本空间中三角形内的P点
,同样投影变成了 P' 点
。那么投影前后,P和P' 的重心坐标一样么?答案是一样的!
公式没考虑z其实就已经告诉我们答案了,那么几何上,我们怎么理解呢,我们可以看个最简单的例子,就是重心。
我们假设下图中的三角形是空间中的三角形,也就是ABC的z轴值不同,重心点O的重心坐标自然是
那么我们看看投影后还是不是
就可以了。
很简单,我们先来看边BC的投影,如下图,我们在yz平面看边BC的投影
可以发现投影后 D' 依旧是 B' 和 C' 的中心点(相似三角形原理),也就是说投影后的直线 A'D' 是三角形 A'B'C'的中线。其他中线同理,因此投影后 O' 的还是三角形A'B'C'的重心,其重心坐标还是
。
但是!有一种投影不行,就是透视投影,依旧是上面的三角形的边BC,我们来看看透视投影会发生什么,如下图:
很明显我们就可以看出来,此时 D' 不再是 B' 和 C' 的中心点。当然了,数学不能光用眼睛看,我们需要推导
为了方便计算,我们设O点为原点,O到投影屏幕的距离为 l (如上图所示),根据相似三角形可以得到:
,即:
。同理可得
,
由于D是BC的中心点,根据直线的重心坐标我们可以知道
,
,带入可得:
,而投影后B'C'的中点的y值应该是
,可以发现和
并不相等。但是有个前提,那就是
,否则
,上面的式子依旧相等。用图来看的话更直观,如下图(依旧是相似三角形):
emmm,好像直接看点D的重心坐标是否改变比看重心的更方便。
而且三角形重心坐标的这个变化同样适用于直线的重心坐标,事实上我们的举例就等于在看直线的重心坐标变化。
因此可以得出结论,在空间中的三角形或直线内的某个点,在投影变换前后,其的重心坐标可能会发生改变。因此有些计算,例如深度,一定要在投影变换前做,否则得到的结果可能是不对的。
矫正
但是前面那样太麻烦了,我们可不可以直接在知道变换前的重心坐标推出变换后的重心坐标,或者反过来呢?当然可以。
我们先从直线的重心坐标投影矫正开始,直接使用之前的图,如下:
此时D不再是BC的中心点了,而是当做BC中的任意一点。根据直线的重心坐标我们可以设: D = iB+(1-i)C,D的重心坐标即为(i, 1-i)。直线BC通过透视投影后得到直线B'C',点D变为D',我们知道透视投影后,重心坐标的值会变,所以我们设:D' = jB'+(1-j)C',D'的重心坐标即为(j, 1-j)。
那么我们只需要知道 i 和 j 的相对关系,不就可以在只知道 i 或 j 中一个的情况下推出另个的值了么?例如,我们假设 i = 2j,那么投影前的重心坐标 (0.6, 0.4)在投影后自然变成的了(0.3, 0.7),或者说投影后的重心坐标为(0.1, 0.9),那么投影前就是(0.2, 0.8)。这样即使碰见投影变换,我们也可以通过变换后的重心坐标去推导出原本的重心坐标,不用再通过逆变换去求原本的重心坐标了。
当然前面 i = 2j 是我们瞎鸡儿说的,我们来看看真正的值是多少。
根据直线的重心坐标,我们可以很容易求得 j 的值:
(其实 i 的值同样可以直接算出来,然后和 j 一除就知道了,但是我们这边要推导出一个更简单的公式)。
通过相似三角形可以得到:
,
,
,带入 j 中可得:
。
我们先来看分子项,即
,我们知道
,
,带入分子中,得到:
化简可得:
其中的
不就是分母中的那部分嘛,即可抵消掉,j 就可以简化为:
从这个式子也可以看出,z值相同时,则 i = j,重心坐标不变。也说明了之前一大串的
的值其实就是 i 。
做了个简单的验证,如下图,D点的重心坐标确实正好从 (1/3, 2/3) 变成了 (1/6, 5/6)。
接下来我们来讲讲三角形的重心坐标投影矫正
前面我们得到
,那么三角形内任意一点P,我们可以看作是AD上的任意一点,我们设 P = wA+(1-w)D,投影后w会变为z,套用上面的公式,我们可以得到
因为P = wA+(1-w)D,D = iB+(1-i)C,所以 P = wA+(1-w)(iB+(1-i)C),即:
P = wA+(i-iw)B+(1-i-w+iw)C
也就是P的重心坐标为(w, i-iw, 1-i-w+iw) 后面两项看着很复杂,我们先不管,写成 (w, ?, ?),那么我们就知道投影后重心坐标会变为
。
那后面两个怎么算呢?既然我们可以把D看成是BC上的一点,P是AD上的点,那么是不是可以再把D看成AB或AC上一点,P则是CD或BD上一点来推导上面的公式。
这样我们又会得到
和
因此得出结论,假设在透视投影前,P在三角形ABC的重心坐标为(i, j, k),那么投影后该坐标会变为
,而
。
-
图形学基础 (六)介绍重心坐标的应用
2021-12-09 09:23:11重心坐标插值得到三角形内部像素的属性三角形内部插值
-
为什么对三角形内部做插值?
因为我们得到的是三角形顶点的内容, 内部的像素的值需要插值得到且为平滑过渡
-
那插值什么内容呢?
三角形的顶点有许多内容, 比如它可以定义到它映射到texture上的不同的uv坐标, 颜色, 法线方向
#### 重心坐标
可以借助三个顶点的线性组合得到重心坐标, 而且着三个数加起来都是1,所以只要知道两个数就行了, 而且都是非负的
对于任意一个点的 α β γ \alpha \ β \ γ α β γ , 都是满足面积比关系的, 而对于重心这个数是1/3
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-77AtQu3N-1639012963444)(typora_pic/image-20211206173438602.png)]
- 下面是三角形的重心的重心坐标, 重心坐标和重心的重心坐标不是一回事, 因为重心坐标是一系列权重的组合, 重心的重心坐标是一个点的重心坐标
利用重心坐标
假如知道三角形三个点的值, 比如是颜色, 法线, 深度, texture 坐标。。。都可以通过插值的方式得到内部点的属性。
重心坐标局限性
-
投影变换下不能保证重心坐标不变, 比如从三维中的三角形投影到二维中, 因为三维中的三角形会变形, 其重心坐标的系数也变了
-
所以对于三维空间中的属性, 插值时应该用3维中的坐标进行插值, 简而言之, 你原本的属性定义在几维的点上, 就用几维中的坐标
-
假如你已经投影到二维空间中了, 那么就需要再变换回去
Textures 的应用
在这个部分暂时不考虑uv的位置在0到1之内, 因为是映射过去的嘛,这里是为了方便理解
比如屏幕上一个点,通过插值得到像素对应的uv坐标, 然后在uv 属性中一查,再用到屏幕上。
存在的问题:纹理的不匹配
纹理太小
想想我们把一张100x100的纹理贴图应用在一500x500的屏幕之上必然会导致走样失真,比如我查找的uv位置通过插值后是小数,我们可以把它round成整数, 然后再用到屏幕上,这样的话在一定范围内查找的是相同的像素。
- 纹理上的像素是有名字的,中文叫 纹理元素, 纹素
- 英文是 texel
这种用四舍五入的方法得到会比较模糊, 如下图:
双线性插值
比如我从屏幕上插值得到的像素是个小数, 这个得到小数的过程详细说一下,比如说我屏幕上有1到5这5个数, 我对应的纹理有1到5个值, 这是一一对应,假如说我的屏幕变为1到10这10个值,那不就是每个数递增0.5, 第一个1对应1, 2对应1.5, 这个1.5就查不到
我们可以找到距离这个小数距离最近的4个点, 这里把距离左下角的点的横向距离规定为s, 纵向距离规定为t, 也就是距离u00的距离, s和t在0到1之内
- 这里就可以使用线性插值了, 比如我有两个点v0和v1, x的值是0到1, 我就可以通过线性插值得到x对应的坐标
- 使用横向距离插值两次得到两个点的属性, 就得到下图的u0和u1的值
- 竖直方向上也可以做插值, 利用上面的到的u0和u1
因为水平和竖直做了两趟所以叫双线性插值, 其实是做了三次插值, 水平方向两次得到两个点, 竖直方向利用这两个点得到最后的值, 这个最后的结果还是不错的
- 当然更好的是Bicubic, 双三次插值,取附近16个, 每次用4个做插值,不是线性的
纹理大了的问题
其实这个一个像素对应的纹理区域大小不同的问题是透视投影带来的,假如是正交投影其实没这个问题
想象一张很大的地板,在上面铺满了重复的方格贴图,我们所期望看到的结果应该是这样的:
但是假如对应的投影到屏幕上会出现什么情况呢?
近处锯齿!远处摩尔纹!非常严重的走样现象,为什么会导致这样的一个现象呢?
-
如开头所说,地板上铺满了重复的方格贴图,根据近大远小,远处的一张完整的贴图可能在屏幕空间中仅仅是几个像素的大小,那么必然屏幕空间的一个像素对应了纹理贴图上的一片范围的点,这其实就是纹理过大所导致的,直观来说想用一个点采样的结果代替纹理空间一片范围的颜色信息,必然会导致严重失真!(从信号的角度来说就是,采样频率过低无法还原信号原貌)
-
换一种想法,考虑离相机很远的一个三角形面,假设该三角形面真正在纹理贴图上对应的一片区域有10个像素点。但是由于透视的关系,距离很远的三角形面投影到近平面时可能只有1个或2个像素点的大小(远远小于10个像素的原来大小),那么这1个或2个像素采样texture的结果就要代表原来这个三角形面10个像素点的颜色信息,自然会导致失真!
为什么1个屏幕空间像素点覆盖多个纹理空间像素就是纹理过大呢,想象一下纹理贴图大小500x500,屏幕空间100x100,将屏幕空间的像素点均匀分布在纹理空间之中,那么1个屏幕空间像素点所占的平均大小就是5x5=25个纹理空间像素,因此这就是纹理过大所导致的结果)
这种现象被形象的成为屏幕像素在texture空间的footprint。如上图所示一个屏幕空间的蓝色像素点离相机越远,对应在texture空间的范围也就越大。其实也就是越来越欠采样,那么一种直观的解决方法就是Supersampling,如果一个像素点不足以代表一个区域的颜色信息,那么便把一个像素细分为更多个小的采样点不就可以解决这个问题了吗?对,确实是这样,可以看看如下图512x超采样的结果
效果虽称不上完美但也极大缓解了走样现象,但问题是什么?计算量太大了,一个像素点被分为了512x512个采样点,计算量几乎多出了25万倍!这显然不是所希望看到的,并且随着屏幕空间的点离相机距离更远,更多的texels(纹理空间的像素)会在屏幕像素的一个footprint里面,会要更高的超采样频率。
- 后面的内容暂时用不到就不再推进了
-
-
重心坐标:重心坐标将给出矩阵 face_point 的坐标 alpha、beta、gama。-matlab开发
2021-05-30 14:14:49face_point 是来自人脸平均形状的点 [x,y]'。 dt 是 3 x 2 矩阵,其坐标对应于 2 个三角形的顶点。 例如,对于顶点为 [v1, v2, v3] 的三角形,v1 将具有坐标 [x1,y1],因此 dt 将包含矩阵 [x1 y1; x2 y2; x3 y3] -
计算机图形学六:正确使用重心坐标插值(透视矫正插值(Perspective-Correct Interpolation))和图形渲染管线...
2020-05-01 17:03:02正如上一文章中所提到的,我们的重心坐标往往都是在屏幕空间下所得到的,如果直接使用屏幕空间下的重心坐标进行插值会造成一定的误差,与在view space下是不一样的,那么本节内容就会具体介绍如何矫正这种误差,利用...透视矫正插值和图形渲染管线总结
(本篇文章同步发表于知乎专栏: https://zhuanlan.zhihu.com/p/144331875 欢迎三连关注)
正如上一文章中所提到的,我们的重心坐标往往都是在屏幕空间下所得到的,如果直接使用屏幕空间下的重心坐标进行插值会造成一定的误差,与在view space下是不一样的,那么本节内容就会具体介绍如何矫正这种误差,利用屏幕空间下的重心坐标达到正确的插值。在此之后也会对到目前为止的所有内容进行总结,即图形渲染管线。
1 透视矫正插值(Perspective-Correct Interpolation)
(为了证明的简便性,我们利用深度值Z的线性插值进行说明,重心坐标插值可以类比得到)
该问题可以很简单在上图之中表现出来,简单叙述一下,在屏幕空间进行线性插值得到点c的intensity为0.5,然而对于在view space之中正确的插值结果,可以很明显看到C的intensity绝不为0.5。这也就造成了插值的误差,应该去矫正!首先先分别定义屏幕空间的比例为s,view space中为t,其余符号含义如下图所示:
为了简便证明,将点的坐标用2维表示,第一维为图中所示的x轴,第二维为z轴。
简而言之,我们的目标就是得出t与s的关系式,这样就可以正确的利用屏幕空间的系数s插值到正确的view space的结果,推导过程如下。由上图所示的投影所造成的三角形相似性可以轻易得出如下几个式子:
X 1 Z 1 = u 1 d ⇒ X 1 = u 1 Z 1 d (1) \frac{X_{1}}{Z_{1}}=\frac{u_{1}}{d} \Rightarrow X_{1}=\frac{u_{1} Z_{1}}{d} \tag{1} Z1X1=du1⇒X1=du1Z1(1)
X 2 Z 2 = u 2 d ⇒ X 2 = u 2 Z 2 d (2) \frac{X_{2}}{Z_{2}}=\frac{u_{2}}{d} \Rightarrow X_{2}=\frac{u_{2} Z_{2}}{d} \tag{2} Z2X2=du2⇒X2=du2Z2(2)
X t Z t = u s d ⇒ Z t = d X t u s (3) \frac{X_{t}}{Z_{t}}=\frac{u_{s}}{d} \Rightarrow Z_{t}=\frac{d X_{t}}{u_{s}} \tag{3} ZtXt=dus⇒Zt=usdXt(3)同样,分别利用screen space 以及 view space的线性插值可以得到以下几个式子:
u s = u 1 + s ( u 2 − u 1 ) (4) u_{s}=u_{1}+s\left(u_{2}-u_{1}\right)\tag{4} us=u1+s(u2−u1)(4)
X t = X 1 + t ( X 2 − X 1 ) (5) X_{t}=X_{1}+t\left(X_{2}-X_{1}\right) \tag{5} Xt=X1+t(X2−X1)(5)
Z t = Z 1 + t ( Z 2 − Z 1 ) (6) Z_{t}=Z_{1}+t\left(Z_{2}-Z_{1}\right) \tag{6} Zt=Z1+t(Z2−Z1)(6)
将4式与5式代入3式得:
Z t = d ( X 1 + t ( X 2 − X 1 ) ) u 1 + s ( u 2 − u 1 ) (7) Z_{t}=\frac{d\left(X_{1}+t\left(X_{2}-X_{1}\right)\right)}{u_{1}+s\left(u_{2}-u_{1}\right)}\tag{7} Zt=u1+s(u2−u1)d(X1+t(X2−X1))(7)
再将1式与2式代入7式得:
Z t = d ( u 1 Z 1 d + t ( u 2 Z 2 d − u 1 Z 1 d ) ) u 1 + s ( u 2 − u 1 ) = u 1 Z 1 + t ( u 2 Z 2 − u 1 Z 1 ) u 1 + s ( u 2 − u 1 ) (8) \begin{aligned} Z_{t} &=\frac{d\left(\frac{u_{1} Z_{1}}{d}+t\left(\frac{u_{2} Z_{2}}{d}-\frac{u_{1} Z_{1}}{d}\right)\right)}{u_{1}+s\left(u_{2}-u_{1}\right)} \\ &=\frac{u_{1} Z_{1}+t\left(u_{2} Z_{2}-u_{1} Z_{1}\right)}{u_{1}+s\left(u_{2}-u_{1}\right)} \end{aligned} \tag{8} Zt=u1+s(u2−u1)d(du1Z1+t(du2Z2−du1Z1))=u1+s(u2−u1)u1Z1+t(u2Z2−u1Z1)(8)
最后将6式代入8式的左边得到:
Z 1 + t ( Z 2 − Z 1 ) = u 1 Z 1 + t ( u 2 Z 2 − u 1 Z 1 ) u 1 + s ( u 2 − u 1 ) (9) Z_{1}+t\left(Z_{2}-Z_{1}\right)=\frac{u_{1} Z_{1}+t\left(u_{2} Z_{2}-u_{1} Z_{1}\right)}{u_{1}+s\left(u_{2}-u_{1}\right)} \tag{9} Z1+t(Z2−Z1)=u1+s(u2−u1)u1Z1+t(u2Z2−u1Z1)(9)
仔细观察9式,我们已经成功得出了t与s的一个关系式,其中的其它参数都是已知,因此进一步化简不在这里展开,可以得到如下t与s关系:
t = s Z 1 s Z 1 + ( 1 − s ) Z 2 (10) t=\frac{s Z_{1}}{s Z_{1}+(1-s) Z_{2}} \tag{10} t=sZ1+(1−s)Z2sZ1(10)
如此就可以利用屏幕空间下的系数得到正确插值结果了,计算如下:
Z t = Z 1 + s Z 1 s Z 1 + ( 1 − s ) Z 2 ( Z 2 − Z 1 ) = 1 s Z 2 + ( 1 − s ) Z 1 (11) \begin{aligned} Z_{t}&=Z_{1}+\frac{s Z_{1}}{s Z_{1}+(1-s) Z_{2}}\left(Z_{2}-Z_{1}\right) \\ &=\frac{1}{\frac{s}{Z_2}+\frac{(1-s)}{Z_1}} \end{aligned} \tag{11} Zt=Z1+sZ1+(1−s)Z2sZ1(Z2−Z1)=Z2s+Z1(1−s)1(11)
以上证明虽然只是针对线性插值的矫正结果,对于重心坐标插值,我们可以类似类推得出:Z t = 1 α Z A + β Z B + γ Z C (12) Z_t=\frac{1}{\frac{\alpha}{Z_A}+\frac{\beta}{Z_B}+\frac{\gamma}{Z_C}} \tag{12} Zt=ZAα+ZBβ+ZCγ1(12)
正确得出深度的插值结果之后,再看看任意属性(法线向量,纹理坐标,view space 坐标)插值结果,依然以线性插值为例先进行推导:用 I I I代表任意属性
I t = I 1 + t ( I 2 − I 1 ) (13) I_{t}=I_{1}+t\left(I_{2}-I_{1}\right)\tag{13} It=I1+t(I2−I1)(13)
I t = I 1 + s Z 1 s Z 1 + ( 1 − s ) Z 2 ( I 2 − I 1 ) (14) I_{t}=I_{1}+\frac{s Z_{1}}{s Z_{1}+(1-s) Z_{2}}\left(I_{2}-I_{1}\right)\tag{14} It=I1+sZ1+(1−s)Z2sZ1(I2−I1)(14)
I t = ( I 1 Z 1 + s ( I 2 Z 2 − I 1 Z 1 ) ) / 1 Z t (15) I_{t}=\left(\frac{I_{1}}{Z_{1}}+s\left(\frac{I_{2}}{Z_{2}}-\frac{I_{1}}{Z_{1}}\right)\right) / \frac{1}{Z_{t}}\tag{15} It=(Z1I1+s(Z2I2−Z1I1))/Zt1(15)
(建议读者自行推导一遍上述所有过程,加深记忆)
不难看出插值的分母就是深度值的倒数,类推得出重心坐标任意属性的正确插值如下:
I t = ( α I A Z A + β I B Z B + γ I C Z C ) / 1 Z t (16) I_{t}=\left(\alpha\frac{I_{A}}{Z_{A}}+\beta\frac{I_{B}}{Z_{B}}+\gamma\frac{I_{C}}{Z_{C}}\right) / \frac{1}{Z_{t}}\tag{16} It=(αZAIA+βZBIB+γZCIC)/Zt1(16)
(tips:任意属性自然包括深度值,将深度值z代入16式可以得出与12式一样的结果)
至此,我们就可以利用16式进行所有的属性的重心坐标插值,并且保证结果正确了!2 图形渲染管线总结
所谓图形渲染管线指的是一系列操作的流程,这个流程具体来说就是将一堆具有三维几何信息的数据点最终转换到二维屏幕空间的像素。其实也就是本系列笔记之前的所有知识连贯起来。我们以如下图作为一个总结,再具体分步骤讲解:
(整个图形管线的步骤可能有不同的分法,不一定就是上图所述的5部分,但整体流程一定是一样的)
首先来看第一个,顶点处理:
顶点处理的作用是指对所有的顶点数据进行Model,View,和Projection的变换,最终得到投影到二维平面的坐标信息(同时为了Zbuffer保留深度z值)。当然如果超出观察空间的会被剪裁掉(关于剪裁的知识因为闫老师的课并没有多提,所以本系列笔记也暂未设及到,但是会在之后进行该部分知识的补充)。
而第二步三角形处理也十分容易理解,就是将所有的顶点按照原几何信息,变成三角面,每个面由3个顶点组成。得到了许许多多个三角形之后,接下来的操作自然就是三角形光栅化了,这也是前几节笔记之中的重点内容之一:
在进行完三角形的光栅化之后,知道了哪些在三角形内的点可以被显示,那么如何确定每个像素点或者说片元(Fragement)的颜色呢?[注:片元可能比像素更小,如MSAA抗拒齿操作的进一步细分得到的采样点]。那自然就是着色了,也就是片元处理阶段应该做的。
注意这阶段顶点处理也亮起来是因为我们需要顶点信息对三角形内的点进行属性插值(tips:当然也可以直接在顶点处理阶段就算出每个顶点的颜色值,如Gouraud Shading一样)。当然这一阶段也少不了Z-Buffer来帮助确定,哪些像素点应该显示在屏幕上,哪些点被遮挡了不应该显示(这一步也有不少书籍归结在最后一步中,个人感觉差求不多,重要在于理解整个过程吧):
最后一步!Framebuffer的处理,就是将所有的像素颜色信息整合在一起,输送给显示设备加以显示。这也就完成了整个图形渲染管线了。(tips:其实在片元处理阶段有一点还未叙述,我们也可以去做texture mapping,利用texture的信息来代替blinn-phong模型漫反射系数来当作颜色,这一部分的内容会在下一节笔记中叙述!)
在这里简单的提一下shader program,shader program分两种,分别是对顶点以及对片元的处理,程序员可以自行编程来代替原来固定的顶点处理和片元处理从而达到各种各样令人惊叹的效果!这也就是现在的可编程渲染管线。
总结
其实对于透视校正插值这一块确实是一个小坑,不少人应该在刚学习的时候都不会注意到,包括我也是,最后也是看知乎上一些大佬的回答才找了一些资料弄明白了这一块。对于图形渲染管线来说,其实就是对光栅化的一个总结,把整个流程拎出来能够有一个更加清晰的认识。
最后如果本文对你有帮助求点赞求收藏求一个大大的关注 😃 ,后序会持续更新,感谢阅读!
Reference
[1] Fundamentals of Computer Graphics 4th
[2] GAMES101-现代计算机图形学入门-闫令琪
[3] 透视矫正插值参考资料https://www.comp.nus.edu.sg/~lowkl/publications/lowk_persp_interp_techrep.pdf -
关于三角形重心坐标插值/锯齿/抗锯齿/延迟渲染中的抗锯齿问题
2021-01-02 23:16:42我们都知道,在渲染流水线中,顶点着色器对输入的顶点数据进行处理(如顶点的坐标变换和光照计算)以后,GPU会进行进行齐次除法并将顶点从三维空间转换到二维的屏幕坐标,接着将这些所需要的着色数据发送到光栅化... -
计算机图形学三(补充):重心坐标(barycentric coordinates)详解及其作用
2020-04-11 10:49:37重心坐标(Barycentric Coordinates) 1 重心坐标的定义及求解1.1 基础定义1.2 几何面积角度求解 本节会分两部分分别介绍重心坐标的定义以及解法和重心坐标在图形学中的运用 1 重心坐标的定义及求解 1.1 基础定义 ... -
[计算机图形学]绘制填充模型:重心坐标、z-buffer
2020-12-17 17:30:00计算机图形学基础 绘制填充图形:重心坐标、z-buffer -
现代计算机图形学笔记(七)——重心坐标、应用纹理&Mipmap
2021-04-04 15:47:43重心坐标(Barycentric Coordinates) 上几节课都提到了在三角形内部做插值,为了研究此问题,我们引入重心坐标(Barycentric Coordinates)。重心坐标的应用很广泛,如在像素着色器(Fragment shader)中我们已知三角形三... -
四边形的重心坐标族的极限
2021-02-26 08:51:43四边形的重心坐标族的极限 -
Catia重心坐标系的建立
2021-05-24 11:03:03Catia重心坐标系的建立一、自定义材料库1.自定义材料2.定义材料参数3.建立自定义材料库二、修改零部件参数1.添加材料属性三、建立坐标系1.惯性测量2.惯性测量参数3.建立坐标系 一、自定义材料库 1.自定义材料 2.... -
三角形重心坐标公式怎么推理
2020-12-21 00:42:532018-05-20解三角形的函数公式有哪些同角三角函数间的基本关系式: ·平方关系: sin^2α+cos^2α=1 1+tan^2α=sec^2α 1+cot^2α=csc^2α ·积的关系: sinα=tanα×cosα cosα=cotα×sinα tanα=sinα×... -
提高python中重心坐标计算的效率
2020-11-28 02:06:51我正在使用重心坐标系将三角形内的一个点映射到另一个三角形上相应的扭曲位置.我的第一种方法是用逆乘法求解系统Ax = b,其中A由三角形的三个角组成,b代表当前点,x代表该点的重心坐标(alpha,beta和gamma) ).我发现每... -
基于重心坐标且具有通信延迟和封装丢失的分布式定位算法
2021-03-27 19:43:51基于重心坐标表示,我们的工作在具有时延和丢包的通信环境中推广了DILOC算法。 首先,开发了一种同步通信协议,并将分布式定位算法数学建模为具有时变通信延迟的线性差分方程。 接下来,利用商图论证明了时变延迟... -
OPENCV之寻找并绘制轮廓以及提取轮廓重心坐标
2020-12-18 20:26:15OPENCV之寻找并绘制轮廓以及提取轮廓重心坐标 1、寻找轮廓 声明:在寻找图像轮廓之前需要对图像进行阈值分割或者Canny、拉普拉斯等边缘检测算子处理。 寻找轮廓的算子: findContours(InputOutputArray image, ... -
虎书学习笔记6:图形学基础数学(重心坐标系、三维三角形)
2021-05-28 10:06:03重心坐标系:设定坐标原点a,a到b和c为基向量。构成非直角坐标系 重心坐标系长这样 重心坐标系特点: 重心坐标系优点: 例如城市街道交叉不成为直角,这时候重心坐标系就管用 已知点p如何求重心坐标 变成这个... -
三角形重心坐标公式推导
2018-11-24 17:52:00则它的重心坐标为: xg = (x1+x2+x3) / 3 ; yg = (y1+y2+y3) / 3 ; 设三点为A(x1.y1)B(x2,y2)C(x3,y3)重心G点坐标(x,y)考虑xm任取两点(不妨设为A和B),则重心G在以AB为底的中线(CN)上... -
图形学笔记(八)着色2 —— 纹理映射、重心坐标、双线性插值、Mipmap、三线性插值、各向异性过滤、纹理的...
2021-10-26 18:01:001.2 纹理的坐标系 —— UV坐标 U和V的范围都在0到1内。三角形的三个顶点,每个顶点都对应一个UV。 纹理能被多次使用。如果纹理重复上下左右可以无缝衔接,则称这个纹理是tiled textures。(有一种算法叫Wang tiling... -
几何画板验证三角形重心坐标公式的详细步骤
2020-12-21 00:42:46最近一些用户们在使用几何画板的时候,不熟悉要如何来验证三角形重心坐标公式呢?今日在这里就为你们带来了几何画板验证三角形重心坐标公式的详细步骤。几何画板验证三角形重心坐标公式的详细步骤步骤一打开几何画板... -
三角形、四边形几何形心和重心坐标计算公式
2019-10-12 10:15:35面的形心为其几何中心,通常把三边形和四边形看成密度一致的平面薄片,均匀平面薄片的重心也叫做着平面薄片所占的平面图形的形心。 在平面几何中,三角形三顶点...多边形重心坐标的求法[J].高等数学研究,2005(02):... -
三角形的重心坐标系
2018-04-12 11:53:15重心坐标系介绍 看懂中文维基百科的第一段。https://zh.wikipedia.org/wiki/%E9%87%8D%E5%BF%83%E5%9D%90%E6%A0%87 三角形重心坐标推导源码使用上面推导的公式计算系数是否大于等于0.bool dtClosestHeightPoi... -
OpenCV计算物体重心坐标代码以及工程
2016-01-04 16:22:42说明: http://blog.csdn.net/wangyaninglm/article/details/49618769 -
利用opencv3.4.1和VS2017得到矩形轮廓和重心坐标
2020-02-13 17:34:27//输出重心坐标 //计算每条边的中点坐标 Point2f pointA = (P[0] + P[1]) / 2; Point2f pointB = (P[1] + P[2]) / 2; Point2f pointC = (P[2] + P[3]) / 2; Point2f pointD = (P[3] + P[0]) / 2; //画出... -
python效率计算-提高python中重心坐标计算的效率
2020-11-11 15:16:21我正在使用重心坐标系将三角形内的一个点映射到另一个三角形上相应的扭曲位置.我的第一种方法是用逆乘法求解系统Ax = b,其中A由三角形的三个角组成,b代表当前点,x代表该点的重心坐标(alpha,beta和gamma) ).我发现每... -
计算机图形学【GAMES-101】4、纹理映射(重心坐标插值、透视投影矫正、双线性插值MipMap、环境光遮蔽AO)
2021-12-07 18:33:36Lecture08~101 Texture Mapping2 Barycentric Coordinates2.1 重心坐标概念2.2 重心坐标计算方式2.3 重心坐标插值3 纹理映射产生的问题3.1 纹理太小3.1.1 Nearst3.1.2 Bilinear Interpolation3.1.3 Bicubic ... -
重心坐标
2010-02-05 14:18:00数学中,重心坐标是由单形(如三角形或四面体等)顶点定义的坐标。重心坐标是齐次坐标的一种。设 v1, ..., vn 是向量空间 V 中一个单形的顶点,如果 V 中某点 p 满足, 那么我们称系数 (λ1, ..., λn) 是 p 关于 v1... -
TIT 计算机图形学 实验三 使用重心坐标算法绘制颜色渐变的正六面体
2021-12-29 01:33:18TIT 计算机图形学 实验三 使用重心坐标算法绘制颜色渐变的正六面体 前言 参考视频计算机图形学全套算法讲解和C++编码实现(共23讲配套源码),计算机图形学案例视频讲解以及主页相关算法。孔老师是我的代课老师,孔... -
扫描线算法和重心坐标计算方法
2017-01-05 19:49:002017-01-0420:17:10 scan-line algorithm sweep algorithm ...求三角形的重心坐标 ...重心坐标的意义 ... 求重心坐标的快速算法,将图元用扫描线分割成垂直和水平的等分,然后生成一张“扫描边表”,通过这张... -
重心坐标差值
2020-06-28 15:56:01https://blog.csdn.net/silangquan/article/details/21990713