Posts Tagged ‘算法’

该问题来自于《Cracking the Coding Interview 5th edition》练习题9.6。原题描述如下:“Implement an algorithm to print all valid (i.e., properly opened and closed) combinations of n-pairs of parentheses.”

该问题是典型的递归问题,有点类似于全排列算法,不同之处在于这里含有重复元素,而且需要验证左右的括号是否正确匹配。我在这里给出的代码和书上给的第二种解法原理基本相同,不过我觉得我的代码更简洁和易懂一点,所以发出来以备有需要的人参考。

Read the rest of this entry »

在网上有很多讲如何实现Tiled Matrix Multiplication的文章,不过大部分只对方阵且尺寸等于Tile尺寸整倍数的矩阵有效。我在这里贴出实现任意尺寸矩阵乘法的代码。

Read the rest of this entry »

三角形光栅化是传统图形渲染管线的最后一步,也是最重要的一步,需要插值计算出三角形内部每个像素的颜色值,并根据z值进行深度测试以决定像素的远近关系。

光栅化的算法用掉了我好几天的时间,一开始是用Barycentric Coordinates算法进行的,结果帧率只有杯具的3,想办法把很多的乘除法改成了加减法还是没有起色,看来浮点数运算还是坑爹啊,于是决定用经典的Bresenham算法了。但是Bresenham算法是用来画线的,对于光栅化三角形来说还要考虑三角形内部针对顶点颜色的插值,于是我将其变成了Bresenham插值算法……

Read the rest of this entry »

好久没玩PSP编程,昨天这学期的图形学结课,昨晚也把最后的作业submit了,于是这学期也就差不多结束了。虽然课时不多,但是图形学课的作业设计得确实不错,首先实现了完整的图形渲染流水线(矩阵变换->相机变换->透视映射变换->三角形光栅化与纹理映射),然后做了一些简单的光线追踪算法(反射、硬阴影与折射)。我打算把这学期在PC上实现的这些算法应用到PSP上面,这样就相当于做一个最简单的3D图形引擎了,以后可以在这个基础上再做扩展。

上次简单研究了下SDK自带的GU函数库,现在不打算用了,既然有了VRAM的指针,那干脆就从最底层开始玩吧!而且,为了提高编程效率,我决定在C的基础上加入C++的代码,不然光是C不支持运算符重载这一点就会让向量和矩阵运算痛苦万分的。另外不得不说的是,PSP编程不能直接使用C函数库,于是连sin、cos这种函数都浮云了,需要自己实现,sigh。

Read the rest of this entry »

纹理映射是光栅化过程中重要的一步。由于众所周知的原因,透视投影是非线性变换,因此顶点原始的uv坐标在变换之后不可以直接使用线性插值计算新的uv坐标。例如,矩形四个顶点的uv坐标分别为(0,0),(0,1),(1,0),(1,1),矩形中点的uv坐标按照线性插值的话等于(0.5,0.5),但是若矩形不是正对观察点的话,透视变换后中点的uv坐标就不一定等于(0.5,0.5)。

例如:

纹理贴图:

线性插值结果->错误:

透视矫正插值结果->正确:

Read the rest of this entry »

Barycentric Coordinates算法,即“重心坐标系插值算法”,本质是通过计算2D空间中任意一点到三角形三边的相对距离,来确定点是否在三角形内部。这个算法比起常见的扫描线插值算法,编程更容易(不需要判断三角形类型),而且具有更高的精确度(避免了计算斜率时带来的误差)。Barycentric Coordinates算法不但可以判断像素点是否需要绘制,而且可以直接插值计算出需要绘制的像素点的颜色或纹理映射坐标。不过,我不知道计算量是否要比扫描线插值算法大,希望有感兴趣的朋友能比较一下。

本文首先简单讲一下算法的原理,然后给出代码实现。

Read the rest of this entry »

网上有很多“绕任意轴的旋转矩阵”的文章,不过要么限定了所谓“任意轴”必须经过原点,要么只有推导没有结论。最近在完成图形学作业的时候正好用到了这个算法,通过Google娘找到了一篇名叫Glenn Murray的老外的文章,于是直接拿来用了。以下直接放结论,详细推导过程可以参考原文[1]。

算法的输入参数分别是旋转轴上的任意一点P(a,b,c),单位化后的旋转轴方向向量V(u,v,w),旋转角度θ。

Read the rest of this entry »

World Line
Time Machine
Online Tools