动机
三角形可能横跨相机视域的边界。只因一个顶点在外便整个拒绝,会失去可见部分;完全保留它,则可能在投影时遇到零分母。裁剪位于两者之间:精确留下图元在允许区域内的部分。结果未必仍是三角形,所以必须保留多边形连接次序,以及新顶点的属性意义。
前面的几何与光栅笔记建立了坐标变换及透视商式。本节把它们组成一个有限程序:位置与属性一起裁剪,再把保留的凸多边形三角化,使用一致边界归属,最后比较深度。若交点位置正确但纹理坐标错误,画出的仍是错误表面;几何与属性不能分开随意处理。
以下先证明精确算术及非退化输入的结果。实现仍要指定近边界数值策略、共同边的一致计算及深度相等时的规则。对每条不等式各自加一个小容差,并不自动证明没有裂缝或重叠。我们会区分几何结论与额外数值要求。
定义
定义 7.2.1
(齐次半空间与携带数据)
裁剪位置为 ,半空间写成 ,其中 固定且非零。惯用对称视域采用 、、。顶点记录包括位置、所有假定在除法前仿射变化的属性,并可携带相对原三角形的重心坐标。
这些齐次不等式在四维空间形成凸锥。一般具有正近面距离的透视相机,其有效保留几何具有正 ,可作透视除法。单看六条不等式亦会接受零向量,但零向量不是射影点;输入须来自有效非零几何表示,不能任意以四个零当作顶点。
定义 7.2.2
(有向多边形与采样规则)
凸多边形以循环排序顶点表示,相邻顶点相连,最后一点亦连回第一点。裁剪及除法后,图像三角形使用一致逆时针绕序。有向边 的函数为 ;内部要求三条边值为正,零值则依一个一致半开规则决定归属。
凸性是下述单一顶点列表算法的条件。非凸多边形裁剪后可能分成不相连部分,未必能用一条普通封闭顶点列表正确表示。三角形本身是凸的,而凸集合与半空间的交集仍凸,因此逐面裁剪始终留在安全输入类别内。
定理 / 命题
定理 7.2.3
(单一平面的凸多边形裁剪)
设非退化凸多边形的循环顶点为 ,保留半空间为 。这里在内包含边界,即 。对每条有向边 ,四种输出为:两端在内,输出 ;只有 在内,输出交点;只有 在内,先输出交点再输出 ;两端在外,不输出。跨界边的交点是
边界端点可与计算交点重合。删除连续重复顶点及末尾重复的首点后,所得正是原多边形与半空间的交集,亦可能为空或降维。
定理 7.2.4
(裁剪与重新三角化保留仿射属性)
假设属性在原三角形重心参数上仿射变化。每次产生裁剪交点时,使用与位置相同的参数 插值其原重心坐标,便保留了原表面的属性。对所得多边形作任意非退化三角化,在齐次分母为正的共同图像点使用透视修正插值,结果皆相同。
定理没有保证不同原三角形之间的属性平滑,只保证细分同一仿射表面模型不会改变它。材质接缝、面法向量及类别标签应使用各自的边界或平面着色约定,不能把离散标签任意解释成线性变化数值。
证明思路
证明
(沿边界遍历与四种边情况)
沿边有 。两端严格异侧时,唯一零点给出公式,而且位于零与一之间;边界端点亦可由同一公式得到。两端在外时,两个负值的凸组合仍为负,故整条边不可能进入。
沿多边形循环边界前进,内部边段保留原次序。离开半空间后,交集边界沿裁剪平面返回下一个进入点;凸性保证这段连线位于原多边形内。四种情况正好按顺序建立这些边界片段。因此输出是交集;若不再有面积,结果可能是空、点或线段,不应当作非退化三角形填色。只要结果的仿射维度仍为二,便可继续论证;中途若降维,对填色表面直接丢弃,因后续交集不能恢复面积。这便证明六个半空间的填色程序。
证明
(携带的重心坐标重现原表面)
设原属性为 ,原顶点重心向量为三个标准基底。交点携带 ,其分量和仍为一,位置及 都符合原模型。归纳可知每轮皆保留此关系。在新三角形内,两个仿射重建若于三顶点相同,便处处相同,因此重新三角化不改原重心坐标。透视只改图像参数,修正商式会恢复同一表面值。
证明透视
不变量是原表面的坐标描述
携带重心坐标不只是携带最后颜色,而是记录每个新点在原三角形的来源。每次裁剪都维持分量和及位置对应,所以改变计算分解不会改变表面。这亦提供直接调试方法:在裁剪边先检查属性与来源是否一致,比等到纹理画错才猜测原因容易得多。
例题详解
例题 7.2.5
(三角形裁剪成四边形)
令 ,顶点为 、、,保留 。三个值为负一、一、一,两交点参数皆为 。保留多边形为 ,维持原顺时针绕序。若光栅测试要求逆时针,须反转次序或调整符号。只保留原内部顶点,会错误地只剩线段 ;扇形三角化则给出两个三角形。
概念视角几何
把裁剪看作对重心坐标三角形的切割
把原三角形的点写成 ,其中 且 。由线性可知, 变成 ,即对 三角形的一次半平面切割。所以裁剪就是重心空间中的多边形切割,保留下来的坐标正是携带的坐标。在四边形的例子中,、,得 ,其边界在 与 的中点与两边相交。
例题 7.2.6
(裁剪属性须用原边参数)
若 、、属性为零及四,进入交点参数是 ,因此 。其屏幕参数却是 。若用此屏幕参数裁剪属性,会得到二而不是一。以屏幕权重作透视修正则得 ,与携带值一致。
例题 7.2.7
(共同对角线只有一个拥有者)
把顶点为 的正方形沿上升对角线分开。样本 对两三角形的共同边值皆为零。向上图像轴下,零边只在垂直增量为正,或水平而向左时接受。故 拥有此样本,其反向不拥有。一致绕序的两三角形恰好覆盖一次;两边皆闭则画两次,即使不透明颜色恰巧相同,混合或样本计数仍会受影响。
完整程序与可见性
每个裁剪面开始时建立空输出列表,把 初始化为输入最后一点。依次把每点当作 ,套四种情况,再设 。结果送入下一面;空列表或仿射维度低于二便停止,因本文处理填色面积。循环初始化不能省略,否则最后到第一点的边没有被测试。少于三个相异非共线图像点的结果,不贡献填色面积。
凸多边形 的扇形三角化使用 ,其中 。除 外,每点沿由 出发的射线,会落在某条相对边与该顶点形成的三角形内;先丢弃零面积扇形三角形,其余内部互不重叠,除边界外覆盖原多边形。内部对角线也必须采相同半开规则。覆盖用的边界偏置不应加到插值重心值上,两者用途不同。
对正面积图像三角形,边函数除以面积分母得到屏幕权重。正齐次分母下,表面属性为
常见错误
(对除法后的深度再作透视修正)
除法后深度 本身在屏幕上仿射,不应修正两次。
每个不透明样本保留最小有效深度,对片段数目归纳可证它始终是已见最小值。相等深度的颜色及有限精度舍入仍须另定;理想最小值与次序无关,没有消除这些实现问题。
裁剪移除视域之外的几何,深度比较处理视域内的遮挡,背面剔除则另依朝向、拓扑及材质假设。薄双面片不能只因为已三角化,便当成封闭单面实体。
常见错误
反例模式
所有顶点在外,仍可能有可见部分
三角形 的顶点全部在正方形 外,却包含原点并覆盖正方形部分。没有原顶点在内,不足以安全拒绝。所有顶点违反同一半空间,是安全简单拒绝的充分条件,并非完全在外的必要条件;其他完全在外的三角形会由裁剪化为空;对部分可见三角形,保留部分的顶点可能全是新交点。
裁剪命题中的凸性假设不能随意去掉。
反例模式
U 形多边形使单一列表规则失效
对非凸的 U 形多边形 套用四种情况,保留 。真正的交集是两个互不相交的单位正方形 与 。沿边走一遍得到单一循环 ,它以沿 的零宽度桥把两个正方形连起来。由 作扇形三角化会产生三角形 ,它包含点 ,但该点位于两个正方形之间的空隙。补救办法是先把非凸输入分成凸块,或使用能输出多个循环的裁剪器。
常见错误
(把每个三角形放大一个 )
浮点实现若反向处理同一条共同边,独立求交可能略有不同。精确证明只指定目标,不是一个完整无裂缝数值实现。重用共同几何、规范边的计算次序或采用明确定点覆盖方案,可建立一致性;任意扩大所有三角形则可能产生重叠,并改变正在画的表面。
总结
半空间裁剪由四种边情况构成。携带原重心坐标让位置与仿射属性同步,并证明重新三角化不改变表面。半开覆盖指定共同样本唯一归属,不透明深度测试再选最近贡献。各步有自己的不变量与数值条件。
练习
快速检查
(线段满足 ,位置为 ,属性为二及十。求离开交点及属性。)
解答 · 答案
参数为 ,交点为 ,属性为 。位置与属性使用同一参数,不能把最终坐标值擅自当成权重。
快速检查
(把逆时针三角形 按 裁剪,列循环结果及两三角形分解。)
解答 · 答案
交点为 。循环结果是 。扇形分解为 及 ,面积为一及 ,总保留面积为 。
快速检查
(新顶点原重心坐标为 ,原属性为 ,求属性。之后再裁剪,为何仍要携带重心向量?)
解答 · 答案
值为 。原重心向量标示同一原表面模型;再次插值它便维持不变量。只相对最新多边形另造权重,可能失去与原顶点属性的关联。
快速检查
(初深度为一,片段深度依次为 。严格小于测试接受哪些?交换两个相等深度的颜色,会发生什么?)
解答 · 答案
第一个 更新,第二个相等值失败,最后 更新。近片段到来前,先到的相等深度颜色胜出;交换它们会改变此中间颜色,最终最近颜色则不变。最小深度的次序独立性,不表示重合表面的颜色必然唯一。