浏览量:413

several color model

The eye is a detector of light whose sensitivity to the quality or wavelength of the light has developed into color perception. Color is the only one of several qualities that go to make up our field of vision. The

spacer
浏览量:2,582

三维旋转

本篇文章谢绝转载,也禁止用于任何商业目的。 代码的下载地址为:https://github.com/twinklingstar20/orientation 本篇文章主要介绍三维空间下旋转的三种表示形式:四元数、矩阵和欧拉角,阐述了四元数、矩阵的数学原理和实现,在附录中描述了与四元数类和矩阵类相关的向量类的实现策略。三种旋转表示形式的优缺点对比,参见文章《欧拉角、四元数和矩阵的对比》。 特别说明:向量类、四元数类、矩阵类的实现,是由NVIDIA公司Physx物理引擎开源部分的源码修改而来的。 1. 四元数 四元数(Quaternion)是由爱尔兰数学家威廉•卢云•哈密顿在1843年发现的数学概念,在图形学中有重要的应用。在3D程序中,通常用四元数来计算3D物体的旋转角度,与矩阵相比,四元数更加高效,占用的储存空间更小,此外也更便于插值。 任意一个四元数可以表示为: \ = xi + yj + zk + w \tag{1}\] 其中,\({{i}^{2}}={{j}^{2}}={{k}^{2}}=ijk=-1,ij=k,jk=i,ki=j\),注意\(ij=k\),但是\(ji\ne k\)。四元数的长度(模长)表示为\(\left\| q \right\|=\sqrt{{{x}^{2}}+{{y}^{2}}+{{z}^{2}}+{{w}^{2}}}\),通常将四元数规一化(Normalized),即: \ \tag{2}\]

spacer
浏览量:615

高动态范围光

本篇文章谢绝转载,也禁止用于任何商业目的。文章中的源码实现的下载地址参见https://github.com/twinklingstar20/hdr_demo 1. 色阶重建 色阶重建(Tone Mapping)是什么样的一个技术呢,它与高动态光照渲染(High Dynamic Range, HDR)又有什么关系呢?,且听我娓娓道来。 假设你是一名摄影爱好者,一定听过HDR这个词,它的专业称法为高动态范围成像(High Dynamic Range Image, HDRI),是用来实现比普通图像(每个颜色通道占8位)表示的曝光范围更大的一种技术,高动态范围成像的目的就是要正确地表示真实世界中从太阳光直射到最暗的阴影这样大的范围亮度。举个例子来解释,大晴天出门去摄(zhuang)影(bi),拍摄了图1所示的一张图,一定会被人喷不专业,因为你这是想证明你对自然景色更感兴趣呢,还是对中国的文化遗产更感兴趣呢?照顾了天空的曝光,就使得暗部欠缺曝光。 图1. 想更准确的拍摄天空 你为了证明你是爱中国的文化遗产,你想重点关注建筑物,于是你拍摄了另外一张图,如图2所示,确实证明了你的爱,但是背景又是什么鬼,那是霾吗,大北京这么难能可贵的大晴天,却拍出了雾霾的效果。 分析下造成这个问题的原因,简单来说,照相机拍摄的亮度(Luminance)范围是有限的,如果想要亮部更加清晰,特别暗的区域就显得比较黑;相反,如果想要暗部更加清晰,特别亮的区域就会被截断(Clamp to white)成白色,显得特别的亮。我们想要的结果如图3所示,不仅能清楚的显现出建筑的模样,同时还有一个比较清晰的背景,这就是色阶重建技术达到的效果,它把一个高动态范围的亮度,变换为低动态范围(Low Dynamic Range)的亮度,使仅用低动态范围的亮度能清晰、有效地还原场景的效果,PERFECT!!! 图3. 高动态范围成像技术达到的效果图 再举个例子,如图4所示,我们可以用不同的曝光度,拍摄一组图片,由暗到亮,然后采用色阶重建技术把它变换为一组明暗协调的图片,如图5所示。色阶重建技术,又可以细分为全局色阶重建和局部色阶重建,想要了解各种色阶重建技术可以参见Reinhard etc。 图4. 不同曝光度的一组图像 图5. 全局和局部色阶重建后的图像 至此,介绍了高动态范围成像(HDRI)和色阶重建之间的关系,可以简单把色阶重建技术划分为全局色阶重建和局部色阶重建。接下来,又提出一个问题,在实时渲染中,特别在多光源的光照计算中,为什么存在无法渲染高动态范围的问题呢? 在计算机的颜色缓冲区中,存储的颜色范围是\(\),当多光源的光照计算,由于亮度的叠加,容易导致亮度超过1.0,此时,硬件设备(GPU)会把它截断至亮度1.0,大部分情况下做这样一种截断处理是没有问题的。但是如果一个场景中绝大部分的片断(像素)经过多光源的光照叠加,它的亮度都超过1.0,简单的把颜色截断至\(\)范围内,那么整个场景有会显得曝光过度,物体的细节无法有效的得到呈现,如图6所示,整块区域就显得白花花的。可以模仿摄影中的色阶重建技术,同时渲染多张不同曝光度的高动态范围的图像,再通过色阶重建技术得到低动态范围的图像。那么问题来了,在实时渲染中,颜色缓冲区会把亮度超过1.0的图像自动截断至1.0,换句话说,就是GL_RGB类型的颜色缓冲区是无法存储高动态范围的帧,此时又如何存储渲染出来的高动态范围的帧呢? 图6. 曝光过度的渲染效果 这就有了新的图像存储格式的诞生,最早由Greg Ward在1985年提出了RGBE 32位的图像存储格式,RGB表示颜色值,E(Exponent)表示RBG颜色的指数系数,通过指定不同的E,就能有效的存储不同高动态范围的图像。后续又出现了多种不同的HDR格式的标准,例如Pixar Log Encoding(TIFF)、Radiance RGBE

spacer
浏览量:881

伽马校正

本篇文章谢绝转载,也禁止用于任何商业目的。 首先,解释下伽马(Gamma)是什么鬼。 以一个数字照相机为例,光子打到传感器上,显现出图像,如果有双倍的光子打到传感器,就会有双倍的电子信号,它是一个线性的关系。但是,人眼对光的感知并不是一个线性的关系,与照相机相比,人眼对暗色调会更加敏感些,使得人眼能感知的光照范围更加广(我也不知道为什么!!!)。如图1所示,图(1)人眼观测到的50%亮度的,实际上只有百分之二十多;图(2)是照相机捕获的50%亮度的颜色,明显比图(1)更亮。 图1. 人眼观测到的与照相机检测到的亮度对比 这与伽马又有什么关系呢?伽马建立起了一个照相机捕获的亮度与人眼观察到的亮度的对应关系,称之为伽马编码。设输入和输出的光照分别表示为\({{L}_{in}},{{L}_{out}}\),伽马系数为\(gamma\),得到关系等式(1),等式(1)的函数示意图如图2所示。\(gamma\succ 1\)的函数变化曲线如图中的红色曲线所示,\(gamma\prec 1\)的函数变化曲线如图中的蓝色曲线所示。 \({{L}_{out}}={{L}_{in}}^{gamma} \tag{1}\) 图2. 幂函数的示意图 因为人眼对暗色调(Dark Tone)更敏感,我们在存储图像文件的时候,对颜色进行伽马编码(Gamma Encoding),如图3所示,伽马编码产生的颜色带中暗色范围更宽。以相同的位数来表示颜色(例如8位),线性编码(Linear Encoding)可能需要更多的位数才能表现与伽马编码相同的效果。 图3. 以2.2伽马系数进行编码的颜色表对比图 伽马编码可以使得8位就能有效的描述绝大部分场景,但是它使得图像的存储和呈现过程变得更加复杂。(1)图像的存储过程,颜色通过系数为\(1/gamma\)的幂函数进行处理;(2)图像的显示,存储的颜色,需要通过显示器采用系数\(gamma\)的幂函数进行处理,即与图像存储相反的过程,它是显示设备内置的处理过程,我们可以把它理解为所有的显示设备都会行进伽马编码的逆处理。如图4所示,(1)图像伽马处理,把图像保存为JPEG或TIFF,(所有的JPEG格式的文件都会进行伽马编码)会采用系数为\(1/gamma\)的幂函数进行预校正,使得指定的位数有效的表示图像;(2)显示伽马处理,是显示设备对颜色进行的校正,两个过程中和后能有效的呈现的颜色。绝大部分显示设备采用的伽马系数为2.2。 图4. 伽马编码和显示 如果图像伽马处理与显示伽马处理不能达到中和,就会使得呈现出来的图像过暗或者过亮。如图5所示,蓝色表示图像伽马处理曲线,红色表示显示伽马处理曲线,紫色表示两者叠加处理后的函数曲线图,不同的中和结果就会产生不同的效果。 图5. 设图像伽马系数为2.2,与不同的显示伽马系数中和作后呈现出来的效果对比图 至此,我们知道,伽马是什么,为什么需要伽马编码,不同的伽马处理对呈现出来的图像的影响。前面阐述的是伽马编码在摄像机(照相机)从现实生活中捕获图像数据,再呈现到显示设备上影响。而在实时渲染的过程中,图像数据的捕获过程就相当于GPU的渲染过程,它可能没有涉及伽马编码,但是显示设备仍然会偷偷滴地帮我们完成伽马编码的逆处理,那么它会引发什么样的问题呢?很多时候,我们渲染出一帧的图像,都会通过显示设备调整渲染出的效果至到它符合我们预期,其实这个过程也考虑到了显示设备隐藏的逆处理,虽然它调试的显示器上显示正常,可能在不同的伽马系数的显示器就会有不同的呈现效果,而且有些情况,我们需要在渲染上对输出到显示设备的帧数据进行校正,特别是有大量动态范围光照的渲染中。这里引入一个概念,伽马校正(Gamma Correction),它是对显示设备对最终输出颜色逆处理的逆处理过程,没有写错,是逆处理的逆处理。 举个例子来阐述下伽马校正的原理,设颜色\(c=\left( 0.5,0,0 \right)\),显示设备的伽马系数为\(gamma=2.2\)经过显示设备的幂函数处理,实际上我们看到它呈现出来的颜色为\({{\left( 0.5,0,0 \right)}^{2.2}}=\left( 0.218,0,0 \right)\)。但是如果在输出到显示设备前,对它进行伽马校正,即\({{\left( 0.5,0,0 \right)}^{1/2.2}}=\left( 0.730,0,0 \right)\),那么,我们在显示设备上实际看到的颜色为 \({{\left( 0.730,0,0 \right)}^{2.2}}=\left(

spacer
浏览量:269

C++11 note

list initialization Initializes an object from braced-init-list. int list_initialization = { 100 }; int list_initialization{ 100 }; int list_initialization(100); int list_initialization = 100; null pointers nullptr int * p = nullptr; constexpr and constant expressions A constant expression is an

spacer
浏览量:331

前言

前言 版权说明 本作品版权归TwinklingStar所有,允许你自由的下载、打印、复制、转载本作品,但需要注明来源,禁止用于任何商业目的。 版本说明 Beta版 内容概要 本作品提供网页版和PDF版: 网页版:http://www.twinklingstar.cn/category/computational-geometry PDF版:https://github.com/twinklingstar20/Programmers_Computational_Geometry 本作品中介绍的绝大部分算法,都有与之相对应的C++源码实现: 源码:https://github.com/twinklingstar20/Programmers_Computational_Geometry 本作品包括九个章节,第1章主要介绍计算几何相关的数学概念,主要涉及向量和矩阵,例如在计算凸包的最小包围盒中就应用了矩阵的特征向量。第2、3、4、5章,分别介绍了几何中的四种基础图元:面、线、三角形和矩形,以及与之相关的计算几何算法。第6章介绍更复杂的图元:多边形,涉及点与多边形的关系判定、多边形类型判定等。第7章介绍旋转测径法,它能高效地解决计算凸多边形的宽、凸多边形间距离等问题。第8、9章分别介绍三维空间下的凸包算法和包围体相关的算法。 修改记录 由于作者能力有限,作品中定有缺点和错误,欢迎读者的批评指正,可以在个人网站留言或者发电子邮件,不胜感激。 网页版将会实时的更进并修改发现的错误,但PDF版的错误修改将需要较长的时间周期。 2016.10.06    发布Beta版,未经过严格校正的不稳定版本 个人信息 电子邮箱:zhangjianlong20@gmail.com 个人网站:www.twinklingstar.cn github:https://github.com/twinklingstar20 致谢 感谢胡凯博对第1章的审校,王莹对第3章的审校。 推荐书籍 推荐几本与计算几何相关的书籍: Philip J. Schneider, and David H. Eberly. Geometric Tools for Computer Graphics. Morgan Kaufmann,

spacer
浏览量:95

参考

       Joseph O'Rourke. "Finding minimal enclosing boxes." International journal of computer & information sciences, vol.14, no.3, pp.183-199, 1985.        David H. Eberly. 3D game engine design: a practical approach to real-time computer graphics. CRC Press, 2006.        Gill Barequet, and

spacer
浏览量:359

9.3. 包围球

本篇文章禁止用于任何商业目的,版权申明、版本说明等见《前言》。 PDF文档和源码下载地址:https://github.com/twinklingstar20/Programmers_Computational_Geometry 9.3. 包围球 9.3.1. 最小包围球的创建 问题描述:给定一个点集\(S = \left\{ {{P_0},{P_1}, \cdots ,{P_{n - 1}}} \right\}\),求包围该点集的最小包围球。 早在1982年,Megiddo提出了第一个在三维空间下求最小包围球的线性算法,但是该算法实现难度较大。 Ritter(1990)提出了一种估计算法,该算法非常简单,但并不能得到最小包围球。主要思想是从点集\(S\)中,找到\(x\)值、\(y\)值、\(z\)值最小和最大的点,从这三组点对中找出距离最大的一组点对,取这组点对的中心作为球体的中心\(c\),取点对距离的一半作为球的半径\(r\)。接着,再次遍历点集\(S\),检查点\({{p}_{k}}\)与中心的距离\(d\),如果\(d\succ r\),说明点在球外,将半径更新为\(r'=(d+r)/2\),并将球心向该点移动\((d-r)/2\),即新的球心为\(c'=c+({{p}_{k}}-c)\cdot (d-r)/(2d)\),重复这个过程,直至点集\(S\)中所有的点都包含在球内。 Welzl(1991)提出了一种通过使用随机化的方法来解决问题,算法复杂度的期望是线性的,且算法相对简单、易实现。该算法不仅能得到二维、三维的最小包围球,而且能扩展到更高维的情况,通过“重要点前移”的优化步骤,能显著的提高算法的效率。Gärtner详细地描述了该算法的实现,并提供了C++的代码实现,在CGAL也有该算法的实现,本节将介绍该算法。 以三维空间下的最小包围球为例,定义\(\text{MB}\left( S \right)\)表示点集\(S\)的最小包围球,显然,\(\text{MB}\left( S \right)\)是唯一的。设\({{D}_{1}}\)和\({{D}_{2}}\)是点集\(S\)的两个最小包围球,半径都是\(r\),球心分别是\({{c}_{1}}\)和\({{c}_{2}}\)。有\(S\subset {{D}_{1}}\)且\(S\subset {{D}_{2}}\),所以有\(S\subset {{D}_{1}}\bigcap {{D}_{2}}\),\({{D}_{1}}\bigcap {{D}_{2}}\)被包含在以\(({{c}_{1}}+{{c}_{2}})/2\)为球心,\(\sqrt{{{r}^{2}}-{{a}^{2}}}\)为半径的球内,其中\(a\)表示两个球心距离的一半。若\(a\ne 0\),则存在半径更小的、包含点集\(S\)的球,与假设条件矛盾,因此\(a=0\),\({{D}_{1}}\)和\({{D}_{2}}\)是重合的。 设\(P,R\)是点集\(S\)的两个子集,且满足\(P \cup R = S,P \cap R = \emptyset

spacer
浏览量:592

9.2. 包围盒

本篇文章禁止用于任何商业目的,版权申明、版本说明等见《前言》。 PDF文档和源码下载地址:https://github.com/twinklingstar20/Programmers_Computational_Geometry 9.2. 包围盒 9.2.1. 最小有向包围盒的创建 问题描述:给定一个点集\(S=\left\{ {{P}_{0}},{{P}_{1}},\cdots ,{{P}_{n-1}} \right\}\),求包围该点集的最小有向包围盒。 通常这个问题可以简化为求凸多面体的最小有向包围盒问题,关于最小有向包围盒的创建方法有很多,O'Rourke在1985年提出了一种复杂度是\(O({{n}^{3}})\)的精确算法。包围盒在碰撞检测中有很重要的应用,为了提高效率,可以采用更高效的有向包围盒估计算法,评价最小有向包围盒估计算法有两个非常重要的指标:效率和紧密度,即要在尽可能短的时间内,创建出尽可能紧密的拟合点集的包围盒。Barequet和Har-Peled(2001)提出了两种估计算法,一种实现难度较大、复杂度是\(O(n+1/{{\varepsilon }^{4.5}})\)的算法(其中\(0\prec \varepsilon \le 1\)),另外一种相对较容易实现、复杂度是\(O(n\log n+n/{{\varepsilon }^{4.5}})\)的算法。而Gottschalk则提出了一种线性的估计算法,虽然不是最优拟合,但是紧密度上也表示很好,本节将介绍该算法。 首先计算出点集的三维凸包,参见第九章,可以得到\(n\)个三角形,记为\(\Delta {{p}^{k}}{{q}^{k}}{{r}^{k}},0\le k\prec n\),其中\({{p}^{k}}\)、\({{q}^{k}}\)、\({{r}^{k}}\)分别是三角形的3个顶点,三角形的面积记为\({{A}^{k}}\),凸包的整个面积就记作 \ 此外,三角形的质心记为\({{m}^{k}}=({{p}^{k}}+{{q}^{k}}+{{r}^{k}})/3\),也就是3个顶点的平均值,整个凸多面体的质心的加权平均值记为 \

spacer
浏览量:146

9.1. 包围体简介

本篇文章禁止用于任何商业目的,版权申明、版本说明等见《前言》。 PDF文档和源码下载地址:https://github.com/twinklingstar20/Programmers_Computational_Geometry 9.1. 包围体简介 在计算机图形学与计算几何领域,包围体(Bounding Volume)就是指把自然物体包容起来的密闭空间。如图9.1所示,就是两类包围体:包围球和包围盒。通常,物体的空间结构比较复杂,需要有上百个顶点组成。如果需要判断两个物体是否发生碰撞,直接采用物体的结构来检测,会使计算量非常的大,而采用包围体,则可以有效的排除不相交的不重叠的情况,降低计算机的开销。 图9.1 包围体 包围体最主要的用途是降低碰撞检测的开销,评价包围体性能的好坏,可以依据如下几个指标: 创建开销; 紧密度; 相交测试; 内存占用性况; 是否容易旋转和变换; 如果一个包围体的创建开销越低,紧密度越好,相交测试简单,内存占用低,容易做旋转和变换,那么这种类型的包围体性能就越好。 常用的包围体有,轴对齐包围盒(AABB),有向包围盒(OBB),包围球,k-离散有向多面体(k-DOP)。其中,轴对齐包围盒创建较为简单,只要将物体的顶点沿着三维空间的3个坐标轴做投影,取得最小值和最大值即可。k-离散有向多面体是轴对齐包围盒的扩展,只要将物体的顶点沿着面的法向量\({{\vec{n}}_{i}}\)做投影,取得最小值和最大值即可创建出k-离散有向多面体。

spacer
浏览量:96

参考

      Joseph O'Rourke. Computational geometry in C. Cambridge university press, 1998.       Stefan Gottschalk. "Collision queries using oriented bounding boxes." PhD diss., The University of North Carolina, 2000.       Donald R. Chand, and Sham S. Kapur. "An algorithm for convex

spacer
浏览量:482

8.5. 快速凸包算法

本篇文章禁止用于任何商业目的,版权申明、版本说明等见《前言》。 PDF文档和源码下载地址:https://github.com/twinklingstar20/Programmers_Computational_Geometry 8.5. 快速凸包算法 8.5.1. 基本思想 快速凸包算法也可以看成是增量算法的一种变种,与随机增量算法相比,它们的不同就在于每次迭代从面的外部点集中选择的点不同。随机增量算法从外部点集中随机的选择一个点,但是快速凸包算法是选择距离最远的一个点,著名的开源代码Qhull、 CGAL都有快速凸包算法的C++实现。 在介绍快速三维凸包算法前,先介绍算法中会频繁使用到的两个基本的几何操作: 1.     给定3个三维空间上的点,确定一个平面。 平面可以用方程\(\vec{n}\cdot P+d=0\)表示,设3个点分别是\(\{{{v}_{0}},{{v}_{1}},{{v}_{2}}\}\),则有\(\vec{n}=({{v}_{1}}-{{v}_{0}})\times ({{v}_{2}}-{{v}_{0}})\),\(d=-\vec{n}\cdot {{v}_{0}}\),叉积的顺序影响法向量的方向,若\(\vec{n}\)是零向量,说明\({{v}_{0}},{{v}_{1}},{{v}_{2}}\)三点共线。 2.     计算三维空间上的点到平面的有符号距离。 设三维点为\(P\),平面为\(\Gamma :\vec{n}\cdot P+d=0\),那么点\(P\)到平面\(\Gamma \)的有符号距离表示为\(dist(P)=(\vec{n}\cdot P+d)/\left\| {\vec{n}} \right\|\)。若\(dist(P)\succ 0\),称点P在平面上方(Above the Plane),;若\(dist(P)\prec 0\),称点P在平面下方(Below the Plane);若\(dist(P)\text{=}0\),称点P在平面上(On the Plane)。 快速凸包算法是基于Beneath Beyond理论,增量算法也同样基于该理论,该理论如下所示,这里只考虑三维空间下的凸包: 设\(H\)是一个\({{R}^{3}}\)空间上的凸包,\(p\)是\({{R}^{3}}-H\)上的一个点。\(F\)是凸包\(conv(p\bigcup H)\)上的面,当且仅当

spacer
浏览量:233

8.4. 礼物包裹算法

本篇文章禁止用于任何商业目的,版权申明、版本说明等见《前言》。 PDF文档和源码下载地址:https://github.com/twinklingstar20/Programmers_Computational_Geometry 8.4. 礼物包裹算法 8.4.1. 基本思想 礼物包裹算法最早由Chand&Kapur (1970)提出的,它不仅可以实现二维、三维凸包,还可以实现更高维的凸包,算法复杂度是\(O(hn)\),\(h\)表示输出的面的数量,\(n\)表示点集的个数,算法复杂度跟输出面相关。直观上,三维的礼物包裹算法,可以看做是在点集的外面包围了一张纸,每次更新一个新的顶点,用纸覆盖住它,就像包裹礼物一样,直至覆盖整个点集。本小节只描述三维的礼物包裹算法,对于更高维的情况,可以参考Chand&Kapur (1970)以及Preparata&Shamos(1985)的描述。 礼物包裹算法基于一个简单的理论:任意一个三维凸包的每一条边有且只有两个相邻面。三维凸包上的每个面用三角形面片表示,若一个凸包有\(h\)个面,则凸包共有\(3h/2\)条边,根据欧拉公式可知,顶点的个数是\(n=h/2+2\)。 设三维凸包上的面用三角形面片表示,本节暂不考虑各种退化情况,三维凸包的礼物包裹算法的算法伪码如下所示: 三维空间下点集\(S=\{{{p}_{0}},{{p}_{1}},...,{{p}_{n-1}}\}\)的凸包 1.    面集合为Q,存储边的集合\(T\); 2.    \(Q \leftarrow \emptyset \); 3.    \(T \leftarrow \emptyset \); 4.    找到一个初始的凸包面\(F\); 5.    \(Q\leftarrow F\); 6.    \(T\leftarrow \)面\(F\)的每条边信息和计数器;   //计数器初始值为1 7.    while( \(Q\)非空 ) 8.          

spacer