首页 > 编程语言 > 详细

消隐算法

时间:2018-09-26 00:39:55      阅读:82      评论:0      收藏:0      [点我收藏+]

标签:角度   pan   改进   处的   情况   war   遮挡   不可   色值   

消隐算法

一、消隐

当我们观察空间任何一个不透明的物体时,只能看到该物体朝向我们的那些表面,其余的表面由于被物体所遮挡我们看不到。

若把可见的和不可见的线都画出来,对视觉会造成多义性。

技术分享图片会有后边两种情况

要消除二义性,就必须在绘制时消除被遮挡的不可见的线或面,习惯上称作消除隐藏线和隐藏面,简称为消隐。

消隐不仅与消隐对象有关,还与观察者的位置有关。

二、消隐的分类

1>按消隐对象分类

线消隐:消隐对象是物体的边

面消隐:消隐对象是物体上的面

2>按消隐空间分类

物体空间的消隐算法:

以场景中的物体为处理单位。假设场景中有k个物体,将其中一个物体与其余k-1个物体逐一比较,仅显示它可见表面已达到消隐的目的。(此类算法通常用于线框图的消隐!)

图像空间的消隐算法:

以屏幕窗口内的每个像素为处理单元。对屏幕上每个像素进行判断,决定哪个多边形在该像素可见(这类算法是消隐算法的主流

三、图像空间的消隐算法:

1>Z-buffer算法

2>扫描线算法

3>Warnock消隐算法

画家算法:去除隐藏面最简单的算法

原理:若场景中有许多物体,就是先画远的物体,再画近的物体。这样一来,近的物体自然就会盖住远的物体。

 技术分享图片

但实际情况并不理想,在三维场景中,一个物体可能有些部分远,有些部分近,所以不管用什么顺序画,都无法得到正确的结果,所以画家算法只能解决简单场景的消隐问题。

 技术分享图片技术分享图片

Z-buffer算法

1、也称Z缓冲区算法和深度缓冲器算法(能跟踪屏幕上每个像素深度的算法),让计算机生成复杂图形成为可能。

2、该算法有帧缓冲器和深度缓冲器,对应两个数组:

Intensity(x,y)-属性数组(帧缓冲器),存储图像空间每个可见像素的光强或颜色

Depth(x,y)-深度数组(Z-buffer),存放图像空间每个可见像素的Z坐标。

Z-buffer保存的是经过投影变换后的z坐标,距离眼睛近的地方z坐标的分辨率比较大,远处的分辨率小。

 技术分享图片

3、Z-buffer算法思想

(开一个和帧缓存一样大小的存储空间,利用空间上的牺牲换区算法上的简洁)

(1)先将z缓冲器中各单元的初始值置为最小值

(2)当要改变某个像素的颜色值时,首先检查当前多边形的深度值是否大于该像素原来的深度值

(3)如果大于原来的z值,说明当前多边形更靠近观察点,用它的颜色替换像素原来的颜色。

4、伪代码

Z-buffer算法(){

帧缓存全置为背景色

深度缓存全置为最小z值(比如赋一个10^-8次方)

For(每一个多边形){

扫描转换该多边形

For(该多边形所覆盖的每个像素(x,y){

计算该多边形在该像素的深度值Z(x,y);

If(Z(x,y)大于Z缓存在(x,y)的值){

Z(x,y)存入Z缓存中(x,y)

把多边形在(x,y)处的颜色值存入帧缓存的(x,y)

}

}

}

}

 技术分享图片

5、优点:

(1)算法简单直观

(2)在像素级上以近物取代远物。与物体在屏幕上的出现顺序是无关紧要的,有利于硬件实现

(3)内存容量不再是问题后很受欢迎

6、缺点

(1)占空间大(因为要开一个和帧缓冲器一样大的数组,多了z缓存)

(2)没有利用图形的相关性和连续性(提高算法的效率要利用图形的相关性和连续性)

(3)是在像素级上的消隐算法

Z-buffer算法的改进(只用一个深度缓存变量zb的改进算法)

1、将缓存数组zb改为一个深度缓存变量zb

2、伪代码

Z-buffer算法(){

帧缓存全置为背景色

For(屏幕上的每个像素(i,j)){

深度缓存变量zb置最小值MinValue

For(多面体上的每个多边形Pk){

If(像素点(i,j)Pk的投影多边形之内){

计算Pk(i,j)处的深度值depth;

If(depth>zb){

Zb=depth;

Index=k;(记录多边形的序号)

}

}

}

If(zb!=MinValue)

计算多边形Pindex在交点(i,j)处的光照颜色并显示

}

}

关键问题:判断像素点(i,j)Pk的投影多边形之内不容易

深度如何求?多边形的平面方程为ax+by+cz+d=0,可得出z

点与多边形的包含性检测

一、射线法

1、由被测点P处向y=-无穷方向作射线

2、交点个数是奇数,则被测点在多边形内部,交点个数是偶数,则被测点在多边形外部

 技术分享图片

3、若射线正好经过多边形的顶点,则采用“左开右闭”的原则来实现

即:当射线与某边的顶点相交时,若边在射线的左侧,交点有效,计数;若边在射线的右侧,交点无效,不计数;

4、用射线法来判断一个点是否在多边形内的弊端:

1)计算量大(因为要大量求交)

2)不稳定(左开右闭有误差,在左边但由于误差算在了右边,不计数了)

二、弧长法

P点为圆心作单位圆,把边投影到单位圆上,对应一段段弧长,规定逆时针为正,顺时针为负,计算弧长代数和

 技术分享图片

代数和为0,点在多边形外部;代数和为2π,点在多边形内部;代数和为π,点在多边形边上

算法为什么稳定?即使算出来后代数和不为0,而是0.10.2,那么基本可以断定这个点在外部,可以认为是有计算误差引起的。

但是算弧长并不容易,因此派生出一个新的方法-

以顶点符号为基础的弧长累加方法

1、不计算角度,用一个规定取代原先的计算

 技术分享图片

3、同一个象限认为是0,跨过一个象限是π/2,跨过两个象限是π。这样当要计算代数和的时候,就不用投影了,只要根据点所在的象限一下子就判断出多少度,这样几乎没什么计算量,只有一些简单的判断,效率高。

区间扫描线算法

1、该算法放弃了z-buffer算法,是一个新的算法,这个算法被认为是消隐算法中最快的之一,因为不管是哪一种z-buffer算法,都是在像素级上处理问题,每个像素都要进行判断,甚至一个像素要进行多次(一个像素可能会被多个多边形覆盖)

2、

 技术分享图片

3、主要思想:如果把扫描线和多边形的交点求出来,对每个区间,只要判断像素画什么颜色,那么整个区间的颜色都解决了(单位是区间

4、如何确定小区间的颜色?

(1)小区间上没有任何多边形,如[a4,a5],用背景色显示

(2)小区间上只有一个多边形,如[a1,a2],显示该多边形的颜色

(3)小区间上存在两个或两个以上的多边形,如[a6,a7],必须通过深度测试判断哪个多边形可见

消隐算法

标签:角度   pan   改进   处的   情况   war   遮挡   不可   色值   

原文:https://www.cnblogs.com/keguniang/p/9704338.html

(0)
(0)
   
举报
评论 一句话评论(0
0条  
登录后才能评论!
© 2014 bubuko.com 版权所有 鲁ICP备09046678号-4
打开技术之扣,分享程序人生!
             

鲁公网安备 37021202000002号