A Bit of Fun

/* 转载请注明出处：http://www.cnblogs.com/Martinium/articles/a_bit_of_fun.html */

OK, 先上一张很有喜感的图片~~

Morphing 关于图像的渐变的原理很简单。找准对应的锚点，即从源图中的点对应目标图中的点（比如眼睛、鼻子、嘴巴、脸的轮廓等那些高频分量地方），高频区域取锚点稠密点、低频区域取锚点稀疏些，这样使得撒的锚点少并且得到的效果好。然后根据公式

out = t*dst + (1-t)*src,(0 <= t <= 1)

参数 t 取值从 0 变化到 1的时候，得到的图像就是从 src 渐变到 dst，取一些关于 t 的值生成的中间图像，调用 giflib 的 API 写入 GIF 格式图像中。关于 t=f(x), (0 <= x <= 1) 的取值，你也可以作点文章。线性函数 f(x)=x，可以得到均匀变化的效果；二次函数 f(x)=x²，可以得到渐快的效果；三次函数 f(x)=4*(x-0.5)³+0.5，你可以得到类似子弹时间的效果，一种先变慢然后又加快的效果。

稍微讨论一下上面的公式，3D 图像的 Alpha Blending 以及一般的图像处理软件里面的图层叠加都有它的影子。

factor*dst + (1-factor)*src = src + factor*(dst-src)

这里稍微变形一下，省去了一个乘法。对一个像素来说简直微不足道，想想处理一个上百万像素的图片，这个省略还是可观的。毕竟乘法比加法“贵”多了。省去一个乘法能降低算法的复杂度。例如：Gauss 的复数乘法算法、大数乘法的分而治之把复杂度从O(n^2)降到O(n^log(3))、矩阵乘法的分而治之把复杂度从O(n^3)降到O(n^log(7)) 等。请参考文件 Divide-and-conquer algorithms。

现在切入主题。其实我要讲的是位操作——一个与上面的公式极类似的式子。它用在 3D 图像的模板缓冲(stencil buffer)中，模板测试的通过或失败决定了像素的颜色值是否要被写入到渲染目标(render target)。

src&~mask | dst&mask = src^((src^dst)&mask)

鉴于 C 语言运算符优先级顺序从大到小依次为 ~ & ^ |，所以左边没有加括号。式子的意思是根据掩码 mask 合并 src 和 dst 的 bit 位。公式左边 4 个位操作运算，右边 3 个位操作运算，节约了一个。虽然实际用意不大，但是已经找到乐趣了。当然，如果 mask 是个常数的话，就没有优势了，编译器会直接计算出 ~mask，从而左边也是3个位操作符。

稍微证明了下倒数第二步多出的项 src&dst 有一部分在 src&~mask，另一部分在 dst&mask，可以添上或抹掉。
证明可真繁琐，还是上文氏图吧。图中斜线部分表示的就是等式的值。

意犹未尽，再补充一下 xor。

1. 字符串的大小写转换 toupper/tolower 存在于 ctype.h 头文件。

#define _tolower(_Char) ( (_Char)-'A'+'a' )
#define _toupper(_Char) ( (_Char)-'a'+'A' )

有了异或操作，你可以这么写：
小写变大写 ch &= ~(‘a’^'A');
大写变小写 ch |= ‘a’^'A';
大小写切换 ch ^= ‘a’^'A';

2. 交换两个整形。

void swap1(int &a, int &b)
{
    int tmp = a;
    a = b;
    b = tmp;
}

void swap2(int &a, int &b)
{
    a += b;
    b = a - b;
    a -= b;
}

void swap3(int &a, int &b)
{
    a ^= b ^= a ^= b;
}

swap1 占用一个临时空间来交换。swap2 和 swap3 没有使用临时空间。
swap2 用自己当临时空间，似乎有整形溢出的危险，但是不影响结果的正确性。（如果溢出，第一步的溢出会在第二步拾回来。）
swap3 使用 ^= 操作符一气呵成，从右向左计算，与 swap2 思想相同，但不会让你有种溢出的感觉:-)

在 OpenGL 中，可以利用 glCopyPixels() 函数（使用XOR操作）交换相同大小的图像。因为 glCopyPixels() 函数不需要 format 或 data 参数，所以数据不会复制到内存中。通过这种方法，可以避免把图像读回到处理器内存的开销。如果 A 和 B 表示两幅图像，图像交换操作可以写成 A=A XOR B, B=A XOR B, A=A XOR B; 也就是上面的 swap3。