画家算法

✍ dations ◷ 2025-09-10 03:30:25 #三维计算机图形学,算法

画家算法也叫作优先填充,它是三维计算机图形学中处理可见性问题的一种解决方法。当将三维场景投影到二维平面的时候,需要确定哪些多边形是可见的,哪些是不可见的。

“画家算法”表示头脑简单的画家首先绘制距离较远的场景,然后用绘制距离较近的场景覆盖较远的部分。画家算法首先将场景中的多边形根据深度进行排序,然后按照顺序进行描绘。这种方法通常会将不可见的部分覆盖,这样就可以解决可见性问题。

在有些场合下,画家算法可能无法解决可见性问题。在这个例子中,多边形 A、B、C 互相重叠,我们无法确定哪一个多边形在上面,哪一个在下面,我们也无法确定两个多边形什么时候在三维空间中交叉。在这种情况下必须用一些方法对这些多边形进行切分、排序。1972年提出的Newell算法就是切分类似多边形的一种方法,在计算几何领域人们已经提出了许许多多的解决方法。

一些基本的画家算法实现方法也可能效率很低,因为这将使得系统将可见多边形集合中的每个点都进行渲染,而没有考虑这些多变性在最终场景中可能被其它部分遮挡。这也就是说,对于细致的场景来说,画家算法可能会过度地消耗计算机资源。

人们有时候也使用逆向画家算法进行处理,这种算法首先绘制距离观察者较近的物体,已经进行绘制的部分不再进行其它的绘制过程。在计算机图形系统中,这种方法由于无需根据光照、纹理等参数计算被较近物体遮挡的远处物体的颜色,所以效率非常高。但是,这种方法也有许多与普通画家算法同样的问题。

画家算法的这些缺陷导致了深度缓冲技术的发展,深度缓冲技术可以看作是画家算法的一个发展,它根据逐个像素的信息解决深度冲突的问题,并且抛弃了对于深度渲染顺序的依赖。即使在这样的系统中,有时也使用画家算法的变体。由于深度缓冲实现通常是基于硬件中的固定精度深度缓冲寄存器,因此舍入误差就会带来一些显示问题,即在多边形连接的地方会出现重叠或者间隙。为了避免这种问题,一些图形处理引擎使用了“过度渲染”的方法,即根据画家算法的顺序绘制两个多边形中受影响的边界。这也就是说有些像素如同在画家算法中那样实际上绘制了两次,但是由于图像中只有很少的一部分才做这样的处理,因此对于性能的影响很小。

相关

  • 芭芭拉·麦克林托克芭芭拉·麦克林托克(英语:Barbara McClintock,1902年6月16日-1992年9月2日),美国著名女性细胞遗传学家。1983年获得诺贝尔生理学或医学奖,是首位没有共同得奖者、单独获得该奖项的
  • 职业指导职业(英语:job),是一种日常性的规律劳动,其目的在于换取劳动所得(也就是薪资),亦象征在社会上的地位和名誉等等。职场上的专门行业,是对劳动的分类。职业是社会分工的产物,西方商品经
  • 台湾保证法《台湾保证法》(英语:Taiwan Assurance Act of 2019),是一部正在立法程序中的准美国法律。2019年5月7日,美国众议院全票通过。目前等待美国参议院的立法程序并协调出两院统一的最
  • 爱德华王子岛爱德华王子岛省(英语:Prince Edward Island;法语:Île-du-Prince-Édouard;苏格兰盖尔语:Eilean a' Phrionns或Eilean Eòin;米克马克语:Apekweit或Epikwetk),简称爱省,也常被简称为皮
  • 纽阿福欧板块纽阿福欧板块(Niuafo'ou Plate)是汤加以西的小型板块,北面是太平洋板块,东面是汤加板块,西面是澳洲板块,主要被聚合板块边缘包围,这个地区经常发生地震。
  • 卢卢阿省卢卢阿省(法语:Province de la Lulua)是位于刚果民主共和国中南部的一个省,首府卡南加(Kananga),与安哥拉接壤,人口2,976,806(2005年),面积60,958 km²。
  • 鬣狗属鬣狗属(学名:Hyaena)是食肉目鬣狗科鬣狗亚科的一属,现存2种,即条纹鬣狗(Hyaena hyaena)和棕鬣狗(Hyaena brunnea),其中棕鬣狗有时也被单独划为一属,即棕鬣狗属(Parahyaena)。
  • 卢布林医科大学卢布林医学大学(波兰语:Uniwersytet Medyczny w Lublinie)是一所位于波兰卢布林的国立大学,成立于1944年。牙医学系成立于1973年。Tadeusz Krwawicz教授发展了眼冷冻手术和冷冻
  • 里奥·哈扬托12(里奥·哈扬托(印尼语:Rio Haryanto,1993年1月22日-)是一位印度尼西亚一级方程式赛车手,曾效力于马诺车队。他将成为印度尼西亚史上第一位一级方程式赛车手。哈扬托在他的家乡展
  • 质子自旋危机质子自旋危机(英语:Proton spin crisis),有时称作“质子自旋之谜”,是1987年的一次实验促成的理论危机,该实验试着测定质子自旋的组成结构,由欧洲μ子共同研究(英语:European Muon Co