anchor.diff:  
   我们已经讨论过几次光线追踪和栅格化的不同之处。为什么选择这个而不是那个？正如之前提及，可见性排序，栅格化比光线追踪快。究竟为什么呢？转换几何体方式的栅格化终究需要花一系时间，但投影几何体本身很快速（只需要少数乘法、加法和减法）。相比起来，计算光线和几何体相交所需要很多的指令和更多的消耗。最主要的是光线追踪的渲染时间会随着场景中的内容成线性增长。因为必须要检测光线和场景中所有三角形是否相交。幸运的是这个问题可以利用*加速结构*得以缓解。加速结构背后的想法是，空间可以被分解（比如把一个包含所有几何体的盒子分解成几格，每格描述成盒子的子空间）物体存储在子空间。见示意图5
   
  -image::http://www.scratchapixel.com/images/upload/rendering-3d-scene-overview/gridaccel.png[caption="图5：", title="加速结构的原则就是分解空间到子领域。光线从一个子领域穿梭到下一个时，我们只需要检测当前子领域里可能会产生相交的几何体，而不是所有几何体。这就节省了极大的消耗", alt="加速结构"]
  +image::http://www.scratchapixel.com/images/upload/rendering-3d-scene-overview/gridaccel.png[caption="alt="加速结构"]
  +^图5：加速结构的原则就是分解空间到子领域。光线从一个子领域穿梭到下一个时，我们只需要检测当前子领域里可能会产生相交的几何体，而不是所有几何体。这就节省了极大的消耗^
   
   如果子空间比物体平均尺寸要大很多，意味着子空间包含了不止一个物体（当然这取决于物体是如何分布的）。我们不再检测场景内所有物体，而是先检测光线是否有相交的子空间（也就是，光线穿过的子空间），如果有，检测光线和该子空间中包含的所有物体是否相交，如果没有，直接跳过所有检测。这样只需要检测场景的一部分，节省很多时间。
   
  
positive.code: = 可见性问题
  :hp-tags: graphic
  :hp-alt-title: The Visibility Problem
  
  http://www.scratchapixel.com/lessons/3d-basic-rendering/rendering-3d-scene-overview/visibility-problem[原文出处]
  
  在前一章节里，我们已经解释了什么事可见性问题。为了创建一个逼真的图像，我们需要从给定的观察点来决定一个对象的哪些部分是可见的。问题就是当我们按例去投影一个盒子的所有顶点，并且连接所有投影点绘制成盒子边，则盒子的所有面都是可见的。不管怎么说，真实情况下只有盒子的正面是可见的，其他面应该看不到。
  
  在图形学中，解决可见性问题主要有两个方法：*光线追踪*和*栅格化*。我们会快速的解释他们是如何工作的。如今已很难搞清楚哪个方法更古老，只不过在图形学早期，栅格化更流行点。光线追踪比栅格化计算量大（使用内存多）是出了名的，比较下来会慢很多。以前的电脑也不快（内存也少），所以渲染图像基本不考虑使用光线追踪，至少在生产环境下如此（比如制作电影）。因此，几乎每个渲染器使用的都是栅格化（光线追踪一般仅限于研究项目）。但是，光线追踪在类似反射、柔和阴影等效果模拟上比栅格化好，原因我们下一章节解释。总的来说，用光线追踪比较容易创建逼真的图像，比起栅格化适用于渲染几何图形，光线追踪更适合模拟真实的着色和光阴效果。我们会在下一章节解释为什么。即时渲染API和显卡通畅使用栅格化，因为速度才是选择算法的决定因素。不过对于光线追踪的说法，80、90年代正确的，在今天就不一定是正确的。现如今电脑非常强大，光线追踪经常用于离线渲染器（至少，两种算法的混合方法已经被实现了）。为什么？还是因为对于模拟类似刺眼的光泽的反射，柔和的阴影等效果，光线追踪是最简单的方法。当速度不再是问题，那么在很多地方都比栅格化来的卓越（让光线追踪有效率的运作仍需要大量的工作）。Pixar的PhotoRealistic RenderMan，是Pixar开发的一个基于栅格化算法的渲染器（该算法被称为REYES，是Renders Everything You Ever Saw【渲染一切所见】的缩写，其构思深远，几乎是最好的可见面判定算法，连显卡的渲染管线都诸多类似REYES），制作过很多早期的电影(玩具总动员、海底总动员、虫虫特工队)。但目前Pixar的渲染器RIS是一个纯粹的光线追踪器。引入光线追踪使得工作室这几年内，极大的推动了写实化以及复杂图像的制作。
  
  == 栅格化如何解决可见性问题？
  
  我们已经把栅格化和光线追踪的区别清晰的解释过了（阅读上一章节）。让我们回顾一下，栅格化可以看作是，位于几何图形表面的一点P，沿着连接到眼睛的一条直线移动，直到碰到画布表面为止。当然，这条直线是隐藏的，实际上根本不需要去构造它，在此，我们是为了可以直观的去解释投影过程。
  
  image::http://www.scratchapixel.com/images/upload/rendering-3d-scene-overview/projection3.png[caption="图1：", title="投影过程可以被看成是一个点沿着它和眼睛的连线一直向下移动，当碰到画布所在平面时停止移动。显然我们不必真的去滑动这个点，只是以此解释投影过程。", alt="投影过程"]
  
  我们需要解决的是可见性问题。换句话说，在场景上可能会有很多点P,P1,P2等等，它们都投影在画布的同一点P'上（画布即是场景）。而在连接到眼睛的同一条直线上的所有点里，只有一个点能被摄影机看到，就是离眼睛最近的那个，参考图2.
  
  image::http://www.scratchapixel.com/images/upload/rendering-3d-scene-overview/projection2.png[caption="图2：", title="场景上多个点可能会投影在场景的同一点上。摄影机能看到的是对齐的店中，离眼睛最近的那个点", alt="可见点"]
  
  要解决可见性问题，首先要找出图中P'所在位置的表达式，即图像的像素坐标是什么，P'落在哪里？还记得投影一个点到画布表面，给定另一个点P'的实数坐标么。P'必须落在最终图像给定的像素上。因此，如何通过画布表面上一点P'的表达式，来定义其在最终图像上的位置（像素坐标）？这里涉及一个简单的坐标系变换。
  
  * 首先定义的坐标系称为*场景空间*（或图像空间），其原点在画布中心。这个2D坐标系的所有轴都是单位长度（长度为1）。注意x或y轴上的点可以是负数，x轴向左以及向y轴向上即为负。
  
  * 以格子形式定义的图像像素坐标系称为*栅格空间*，其原点通常位于图像的左上角，轴也是单位长度，一个像素为一单位长度。因此，画布在该坐标系中的实际尺寸由图像的垂直（高）和水平（宽）的维度决定（即像素表达式）。
  
  image::http://www.scratchapixel.com/images/upload/rendering-3d-scene-overview/screentoraster.png[caption="图3：", title="计算一个画布上的点所处的像素值，需要把点从场景空间转换到NDC空间后，再从NDC空间转换到栅格空间。", alt="空间转换"]
  
  将点从场景空间转换到栅格空间非常简单。因为在栅格空间中的点P'只会是正数，我们首先把P'归一化。换句话说，使其范围在0,1之间（当点被如此定义时，我们称点被定义在NDC空间中，NDC全称是Normalized Device Coordinates【归一设备空间】）。一旦转换到NDC空间，再把点转换到栅格空间就很简单了。只需乘以图像尺寸，然后四舍五入即可（像素坐标永远是整数）P'坐标的范围取决于场景中画布的尺寸。为了简单起见，假设画布的宽高都只有2个单位长度，也就是说P'在场景中的坐标范围是[-1,1]。以下是把P'坐标从场景空间转换到栅格空间的伪码：
  
  [source,linenums]
  int width = 64, height = 64; // 以像素为单位的图像尺寸
  
negative.code: Vec2f P_proj; 
  P_proj.x = P.x / P.z; // -0.1 
  P_proj.y = P.y / P.z; // 0.2 
  // 屏幕空间转换到归一空间
  Vec2f P_proj_nor; 
  P_proj_nor.x = (P_proj.x + 1) / 2; // (-0.1 + 1) / 2 = 0.45 
  P_proj_nor.y = (1 - P_proj.y ) / 2; // (1 - 0.2) / 2 = 0.4 
  