opencv实现快速傅立叶变换和逆变换

发表于 2014-11-07 分类于图像处理， OpenCV 阅读次数： Valine：
本文字数： 3.1k 阅读时长 ≈ 3 分钟

说实话觉得网上很多人转载的文章的挺坑的，全部是opencv文档程序的翻译，看来看去都是那一
篇，真的没啥意思。文档的地址。
本来opencv实现dft就是一个函数的事情，但是很少有关于逆变换使用的资料。我这几天在翻译
matlab版本的L0Smooth到opencv上面，就碰到这样一件很坑爹的事情。
首先，很少有人说清楚这个函数的使用方法。还有，根据教程，dft之前最好扩充原矩阵到合适的尺
寸(2,3,5的倍数)，再调用dft会加快速度。那么，idft的时候了？如何恢复原有的尺寸？
在我的L0Smooth代码里，就碰到这样的事情了。如果，图片尺寸是2，3，5的倍数，那么能够得到
正确结果。否则得到是全黑的图片。如果，我不扩张矩阵，那么就能正确处理。
所以，到这里，我不推荐调用dft之前先扩充矩阵了。因为，我找了很久也没找到解决办法。
我数学水平有限，也分析不出原因，也没有时间去系统的学习这些了。
这里提供两个例子，说明dft和idft的使用。
例子一：类似于opencv官方文档的例子

#include "opencv2/core/core.hpp"
#include "opencv2/imgproc/imgproc.hpp"
#include "opencv2/highgui/highgui.hpp"
#include <iostream>

#ifdef _DEBUG
#pragma comment(lib, "opencv_core247d.lib")
#pragma comment(lib, "opencv_imgproc247d.lib")
#pragma comment(lib, "opencv_highgui247d.lib")
#else
#pragma comment(lib, "opencv_core247.lib")
#pragma comment(lib, "opencv_imgproc247.lib")
#pragma comment(lib, "opencv_highgui247.lib")
#endif // DEBUG

int main()
{
    // Read image from file
    // Make sure that the image is in grayscale
    cv::Mat img = cv::imread("lena.JPG",0);

    cv::Mat planes[] = {cv::Mat_<float>(img), cv::Mat::zeros(img.size(), CV_32F)};
    cv::Mat complexI;    //Complex plane to contain the DFT coefficients {[0]-Real,[1]-Img}
    cv::merge(planes, 2, complexI);
    cv::dft(complexI, complexI);  // Applying DFT

    //这里可以对复数矩阵comlexI进行处理

    // Reconstructing original imae from the DFT coefficients
    cv::Mat invDFT, invDFTcvt;
    cv::idft(complexI, invDFT, cv::DFT_SCALE | cv::DFT_REAL_OUTPUT ); // Applying IDFT
    cv::invDFT.convertTo(invDFTcvt, CV_8U); 
    cv::imshow("Output", invDFTcvt);

    //show the image
    cv::imshow("Original Image", img);

    // Wait until user press some key
    cv::waitKey(0);

    return 0;
}

代码意思很简单，dft之后再idft，注意参数额，必须有DFT_SCALE。代码中，先merge了个
复数矩阵，在例子2中可以看到，其实这一步可以去掉。
例子2：

#include "opencv2/core/core.hpp"
#include "opencv2/imgproc/imgproc.hpp"
#include "opencv2/highgui/highgui.hpp"
#include <iostream>

#ifdef _DEBUG
#pragma comment(lib, "opencv_core247d.lib")
#pragma comment(lib, "opencv_imgproc247d.lib")
#pragma comment(lib, "opencv_highgui247d.lib")
#else
#pragma comment(lib, "opencv_core247.lib")
#pragma comment(lib, "opencv_imgproc247.lib")
#pragma comment(lib, "opencv_highgui247.lib")
#endif // DEBUG

int main()
{
    // Read image from file
    // Make sure that the image is in grayscale
    cv:;Mat img = cv::imread("lena.JPG",0);

    cv::Mat dftInput1, dftImage1, inverseDFT, inverseDFTconverted;
    cv::img.convertTo(dftInput1, CV_32F);
    cv::dft(dftInput1, dftImage1, cv::DFT_COMPLEX_OUTPUT);    // Applying DFT

    // Reconstructing original imae from the DFT coefficients
    cv::idft(dftImage1, inverseDFT, cv::DFT_SCALE | cv::DFT_REAL_OUTPUT ); // Applying IDFT
    cv::inverseDFT.convertTo(inverseDFTconverted, CV_8U);
    cv::imshow("Output", inverseDFTconverted);

    //show the image
    cv::imshow("Original Image", img);

    // Wait until user press some key
    waitKey(0);
    return 0;
}

从代码中可以看到，dft时候添加参数DFT_COMPLEX_OUTPUT，就可以自动得到复数矩阵了，代码更加简洁。
注意，必须先将图片对应的uchar矩阵转换为float矩阵，再进行dft，idft，最后再转换回来。

cuda结合opencv实现简单的平滑滤波

发表于 2014-11-05 分类于图像处理， CUDA 阅读次数： Valine：
本文字数： 2.4k 阅读时长 ≈ 2 分钟

这次也是使用opencv的mat加载处理图像。唯一与上次有区别的是核函数的编写。
根据cuda的线程分配模型，每一个像素是分配单独的线程处理的。那么有这样的一个疑问？
像平滑滤波这些应用，如何在每一个线程中获取周围的像素了？
其实，这个问题很好解决。因为，在核函数中，我们能够根据线程id，块id，块尺寸等计算
出当前像素的位置。那么，自然能够得到其邻域的位置。从而实现了平滑滤波。
代码如下：

#include <stdlib.h>
#include <stdio.h>
#include <opencv/cv.h>
#include <opencv/highgui.h>
#include <opencv2/opencv.hpp>

#include "cuda_runtime.h"
#include "device_launch_parameters.h"

#ifdef _DEBUG
#pragma comment(lib, "opencv_core247d.lib")
#pragma comment(lib, "opencv_imgproc247d.lib")
#pragma comment(lib, "opencv_highgui247d.lib")
#else
#pragma comment(lib, "opencv_core247.lib")
#pragma comment(lib, "opencv_imgproc247.lib")
#pragma comment(lib, "opencv_highgui247.lib")
#endif // DEBUG

__global__ void smooth_kernel(const uchar3* src, uchar3* dst, int width, int height)
{
    int x = threadIdx.x + blockIdx.x * blockDim.x;
    int y = threadIdx.y + blockIdx.y * blockDim.y;

    if(x < width  y < height)
    {
        int offset = x + y * width;
        int left = offset - 1;
        if (x - 1 < 0)
        {
            left += 1;
        }
        int right = offset + 1;
        if (x + 1 >= width)
        {
            right -= 1;
        }
        int top = offset - width;
        if (y - 1 < 0)
        {
            top += width;
        }
        int bottom = offset + width;
        if (y + 1 >= height)
        {
            bottom -= width;
        }

        dst[offset].x = 0.125 * (4 * src[offset].x + src[left].x + src[right].x + src[top].x + src[bottom].x);
        dst[offset].y = 0.125 * (4 * src[offset].y + src[left].y + src[right].y + src[top].y + src[bottom].y);
        dst[offset].z = 0.125 * (4 * src[offset].z + src[left].z + src[right].z + src[top].z + src[bottom].z);
    }
}

void smooth_caller(const uchar3* src, uchar3* dst, int width, int height)
{
    dim3 threads(16, 16);
    dim3 grids((width + threads.x - 1) / threads.x, (height + threads.y - 1) / threads.y);

    smooth_kernel<< <grids, threads >> >(src, dst, width, height);
    cudaThreadSynchronize();
}

int main()
{
    cv::Mat image = cv::imread("lena.png");
    cv::imshow("src", image);

    size_t memSize = image.step * image.rows;
    uchar3* d_src = NULL;
    uchar3* d_dst = NULL;
    cudaMalloc((void**)d_src, memSize);
    cudaMalloc((void**)d_dst, memSize);
    cudaMemcpy(d_src, image.data, memSize, cudaMemcpyHostToDevice);

    smooth_caller(d_src, d_dst, image.cols, image.rows);

    cudaMemcpy(image.data, d_dst, memSize, cudaMemcpyDeviceToHost);
    cv::imshow("gpu", image);
    cv::waitKey(0);

    cudaFree(d_src);
    cudaFree(d_dst);

    return 0;
}

效果如图：

cuda和opencv混合使用

发表于 2014-11-03 分类于图像处理， CUDA 阅读次数： Valine：
本文字数： 2.4k 阅读时长 ≈ 2 分钟

这里我既不介绍opencv的基本使用，也更加不会介绍cuda的使用。推荐下cuda的一本书：GPU高性能编程CUDA实战。
opencv这么强大的工具不用肯定是浪费了，opencv也有gpu的部分，据说也是用cuda实现的，但是灵活性肯定不如直接用cuda吧。
所以，我觉得只需要使用opencv负责cpu的部分，比如加载图片，gui之类的，而cuda负责并行的处理。还有，本着方便的原则，
opencv使用cpp的版本，不想再去管内存分配释放了。虽然，Mat相对来说更难使用。
下面是一个简短的交换rb通道的cuda和opencv混合的程序。

#include <stdlib.h>
#include <stdio.h>
#include <opencv/cv.h>
#include <opencv/highgui.h>
#include <opencv2/opencv.hpp>

#include "cuda_runtime.h"
#include "device_launch_parameters.h"

#ifdef _DEBUG
#pragma comment(lib, "opencv_core247d.lib")
#pragma comment(lib, "opencv_imgproc247d.lib")
#pragma comment(lib, "opencv_highgui247d.lib")
#else
#pragma comment(lib, "opencv_core247.lib")
#pragma comment(lib, "opencv_imgproc247.lib")
#pragma comment(lib, "opencv_highgui247.lib")
#endif // DEBUG

__global__ void swap_rb_kernel(const uchar3* src, uchar3* dst, int width, int height)
{
    int x = threadIdx.x + blockIdx.x * blockDim.x;
    int y = threadIdx.y + blockIdx.y * blockDim.y;

    if(x < width  y < height)
    {
        int offset = x + y * width;
        uchar3 v = src[offset];
        dst[offset].x = v.z;
        dst[offset].y = v.y;
        dst[offset].z = v.x;
    }
}

void swap_rb_caller(const uchar3* src, uchar3* dst, int width, int height)
{
    dim3 threads(16, 16);
    dim3 grids((width + threads.x - 1) / threads.x, (height + threads.y - 1) / threads.y);

    swap_rb_kernel<<<grids, threads>>>(src, dst, width, height);
    cudaThreadSynchronize();
}

int main()
{
    cv::Mat image = cv::imread("lena_1.jpg");
    cv::imshow("src", image);

    size_t memSize = image.step * image.rows;
    uchar3* d_src = NULL;
    uchar3* d_dst = NULL;
    cudaMalloc((void**)d_src, memSize);
    cudaMalloc((void**)d_dst, memSize);
    cudaMemcpy(d_src, image.data, memSize, cudaMemcpyHostToDevice);

    swap_rb_caller(d_src, d_dst, image.cols, image.rows);

    cudaMemcpy(image.data, d_dst, memSize, cudaMemcpyDeviceToHost);
    cv::imshow("gpu", image);
    cv::waitKey(0);

    cudaFree(d_src);
    cudaFree(d_dst);

    return 0;
}

运行效果：

opencv部分不用做过多解释了，cuda的那些内存操作函数也不用解释。唯一需要解释的是核函数里面的这两句：int x = threadIdx.x + blockIdx.x * blockDim.x;
int y = threadIdx.y + blockIdx.y * blockDim.y;千万别搞错x和y，否则效果就完全不对了。根据cuda的模型，线程是一块一块的。一个线程块里面有很多线程，那么如何索引这些线程了？
把线程块看作是是三维的（一般用到一维或者二维）数组，然后根据数组索引得到具体线程。至于blockDim指的是一共有多少线程块了，这个也是三维的，意思一个gpu格子里面，
会出现三维的线程块组合。gpu格子的大小，在cuda里面用gridDim指代。所以，从上到下就是三层模型吧，三维的grid->三维的block->三维的thread。具体的理解，参照书籍或者教程吧。

vs2013下设置cuda高亮

发表于 2014-11-03 分类于图像处理， CUDA 阅读次数： Valine：
本文字数： 572 阅读时长 ≈ 1 分钟

因为是最近才接触cuda，安装的是6.5版本，所以网上的教程都不是完全适用了。
总之，设置高亮大致分为四步，不限于vs2013，其他平台下也类似。
第一步，是在vs2013里面设置vc++文件支持.cu;cuh;文件。方法：工具->选项->文本编辑器->文件扩展名。
得到如图所示的界面：注意，在右侧可以添加vc++类型的文件扩展名，这是我的设置效果，操作就不用细说了。

第二步，是设置visual assist的目录。在va的C++directory里面，选择custom选项，然后包含你的cuda的sdk目录，效果如图：

第三步，是设置va的支持文件类型，类似于第一步。但是，这次是修改注册表的值。注册表目录：
HKEY_CURRENT_USER/Software/Whole Tomato/Visual Assist X/VANet12，修改属性ExtSource的值为：.c;.cpp;.cc;.cxx;.tli;.cu;.cuh;
意思就是添加上cuda的头文件和源文件类型，vs2010的改法类似。
第四步，完成以上步骤之后，还可能会发现一些内置变量下面是有波浪线的。怎么办了？
加上这句：#include “device_launch_parameters.h”，就行了。cuda 6.5估计把内置变量的声明放在该头文件下面了吧。
最终的效果：

main函数返回,exit,abort

发表于 2014-10-31 分类于编程语言， C++ 阅读次数： Valine：
本文字数： 360 阅读时长 ≈ 1 分钟

最近在看C++标准程序库，看到介绍这两个函数的地方，记起来刚上大学的时候用exit结束
程序。那个时候什么都不懂，程序能运行就行了。不过，也好奇过这些东西，到底有什么区别了。
书上说的很简单，exit会释放static对象(当然包括全局对象，函数static对象，类的static对象)，
清空缓冲区，关闭io，然后终止程序（如果atexit有登记函数，那么执行这些函数）。
abort则真的是什么都不干，就退出来了。
以上两者都没有解栈(stack unwinding），也就是栈里面的变量没有析构。这个只有从main函数返回才会正常解栈。
那么，考虑这样的一个问题，既然程序都要结束了，这些操作到底有没有区别了。进程介绍了，
所有的资源都是还给操作系统了吧。只是从程序设计角度来说，资源还是应该由申请者释放的，个人是从这个角度看的。

找工作的经历

发表于 2014-10-29 分类于生活阅读次数： Valine：
本文字数： 3.9k 阅读时长 ≈ 4 分钟

工作其实早就确定了，三方也接受入库了。成埃落定，也是时候扯两句了。
由于以前没打算去工作，所以就没参加实习的校园招聘。暑假7月份尝试找了一次实习，没成功。校园招聘面试了四家，拿到了两家。
找工作的时候，也看了一些别人的面经，抱着回馈社会的想法，也写写我碰到的问题。虽然三言两语很难描述清楚，权当随便扯扯吧。

第一家，2014.7月，AMD实习，结果：经理面没通过
参加的原因也莫名其妙，七月初，论文投出去了，导师给我发了个AMD科研小组实习招聘消息，我本着试一试的态度就试一试了。
1.科研小组实习面试
人家本来要的就是去做科研的，所以要求里面最好是发了文章，最好是博士生，硕士生也考虑。反正，当时我是做了英文版的简历投过去了。
过了几天hr确定电话面试的时候，那个小组的负责人就给我电话面试了。
大致问题：科研项目，C++(虚函数，多态)，算法(链表有环，数组中出现一次的数字，其余出现两次)，图形学(居然问我基本算法细节，只能说我简历写偏差了)。
大致就是问的这些吧，时间久了，也回忆不起来了。基本当然是最重要的，我暑假还没开始准备工作，所以也答得不怎么样。结果当时没有通过，虽然感觉面试官很热情，很有可能，
然后非常感谢他把我的简历给了驱动开发小组，所以我后面还有次机会。
2.OpenGL驱动开发小组面试
1>1面：一面的面试官好喜欢聊，巴拉巴拉的说了一大堆。我还是分块回忆下吧。C++（vector和list的使用场合，map的实现）,体系结构（cpu缓存更新算法），操作系统（用户态和内核态区别），
算法（快排），OpenGL（glsl常用细节，VBO）等等。
2>2面：二面面试官打电话一开始就跟我说一面反应非常好，也许是和一面面试官聊得很投缘吧，然后他要来确认下。所以，他就继续问了。大致问题：项目相关的东西，其余的和一面的差不多，
主要是根据简历问了下，记不起来了。
3>3面经理面试：这次谈了好久，问题也问了很多，也说到以后实习的细节，但是我最终还是傻逼了，经理问我，如果AMD给我offer，问我怎么选，我说我现在还不清楚，
还没考虑这件事情，然后是双方沉默了一会儿。最终估计是他们考虑到我从长沙去上海的成本问题，以及中途必须去参加校招耽误时间等等，就不搭理我了，也算是客气的拒绝吧。
问题也问了很多，以项目和图形学为主。图形学（OpenGL光照模型，VBO，normal map），界面（MFC/QT熟悉程度)，其余大致和前面的差不多。主要是时间长了，记不起来了。

第二家，2014.9月，阿里巴巴，结果：一面挂了
通过这次面试，我终于感受到了阿里的火爆程度和神奇程度。本来就打算去做游戏的，所以也没不是很在意结果，只是跑了一次武汉，等了那么久。
阿里是在线笔试，通过的人比较多。记得笔试题里面有个dp的最长连续子串。
从长沙跑去武汉，住了一晚。我选了11点的时间，但是9点多去的，结果一直在那里等，问了无数次hr，一直是再等15分钟，结果就真的等到11点了。
好吧，终于能够面试了。我面的方向是C++，但是一进去发现面试官的桌子上摆着java的牌子。无所谓了，开始面吧。
面试题目：C++（野指针有哪些情况，内存泄漏，怎么理解面向对象），数据结构和算法（B树，B+树，还有个简单的手写算法题，忘记了），操作系统（进程和线程的区别），
其余的就是我简历上的科研项目，
说了一大堆，自我感觉良好了，感觉面试官也有兴趣。只是最后，他问了句，你对互联网其他的方向了解不，我说不了解，听说过大数据什么的，然后就让等消息去了。
坐在外面等了一会儿，就有通知说你可以回去等消息了，意思是你玩完了。后面才知道，我和同学是同一个面试官一面刷的，他也是面c++，然后两个人还问了类似的题目，
只是刷的莫名其妙的。。。好吧，就这样吧。

第三家，2014.9月，腾讯游戏，结果：终于拿到offer了
只能说幸福来的太突然。阿里挂了之后，就和同学去找另外的同学了。他们要去华科参加腾讯笔试，我腾讯选的地点是长沙，所以不怎么想笔试了。但是，既然来了就去霸笔下吧。
腾讯笔试的选择题范围比较广，也很基础，大家学好基础就什么都不怕了。大题一个进制转换，还有个进程通信，还有个好像是ios的。
说说面试吧。笔试完了之后就回长沙了，也没报希望，毕竟是霸笔的。大概是17号半夜1点多给我发的短信和邮件，呵呵，我早上9点多一到实验室才发现。hr工作时间挺晚的额，
让我10点钟赶到武汉面试，这是不可能的。然后，我就咨询同学怎么办，有人说打电话问，有人说发邮件问。我就抱着试一试的态度，发邮件到校招邮箱说明了情况。腾讯的效率真高，马上就有hr
打电话问我了。然后，商量好时间调到下午2点。唉，既然说话了，我只能再次踏上去武汉的征途了。
一面：两点多才赶到地点，找到之后去大厅问问，还以为我错过时间了，hr打电话问面试官，然后就让我马上去房间面试了。一面的估计是小boss。我说明了下从长沙赶来的情况，
面试官表示清楚，然后就开始面试了。题目：话说我记得的不多了，智力题（分油，这类题大家可以好好学学，我没做出来，我只是提出可以用搜索状态解决，然后面试官说不用这么麻烦，
让我再想，只是没思路了），算法题（有序数组构建搜索二叉树），图形学（直线和球求交点），其余的，我确实记得不清楚了。。。最后问了下，我这几年碰到什么过不去的难事没，
还有工作地点的倾向。然后面试官直接让我拿着草稿纸去二面面试官的房间了。
二面：二面感觉也是大boss了。二面问的问题更多，一开始是针对我的简历问我的科研项目，讲了好多，感觉面试官很多东西也懂，一直到后面问到无法问了，才问其他内容。
图形学（渲染管线，ogl或者dx都行，点关于平面对称点怎么求），智力题（显示读数的称，一次称重，区分不同的堆，具体的忘记了），算法题（用尽可能少的队列实现一个栈），C++（static的
用法，异常的初次处理和二次处理的区别），大概就这些吧，很多也忘记了。面试官人挺好的，给我安排第二天最早的hr，非常感谢额。
三面：第二天9点的hr面，基本上是自我介绍，然后问了我一个关于逻辑的智力题（如何处理城市拥堵与汽车发展的矛盾）。然后谈谈对腾讯氛围的感受之类的，问问就业地点意向。
回到长沙之后收到电话通知了，确认知道是一个游戏工作室，虽然在二面时候也询问了。再次感谢面试官的照顾，让我不用在武汉呆那么久。

第四家，2014.9月，美团网，结果：拿到offer
在学校参加了美团的笔试和面试，过程挺顺利的。美团笔试毕竟变态，全部是写代码的大题，貌似大家也就能写完几个，时间也就90分钟。面试是在学校的一间教室。
一面、二面、三面，都是在教室一上午面完的，挺累的。
一面：先是问简历，问得比较详细，甚至到一些实现细节，这个得准备充分。算法（一个大数组找出一个重复出现的数字），操作系统（程序的堆和栈等信息，进程和线程的区别），
网络（四次挥手），其余的记不起来了。
二面：简历没怎么问了。C++（虚函数表），算法（两个矩形求交，顺子和同花计算概率），其余的也记不起来了。
三面：问了下就业意向，还有如何说明自己学习能力好。算法（大数组找中位数），其余的题目也记不起来了。
因为没抱什么希望，所以对offer也没什么感觉。因为不想去北京，后面hr叫过去谈offer的时候，差不多直接拒绝了，后面还是发了电子档的offer。

第五家，2014.10月，网易游戏，结果：终面挂了
参加笔试和面试一共跑了武汉两趟，也是悲剧。笔试是9月底，在华科。笔试很长的试卷，貌似是150分钟。前面是变态的基础题，后面是变态的算法题。笔试是通过了，
虽然做的乱七八糟了。最难看的是我的字迹。算法题：记得有个递归改非递归，四叉树，dp，还有k-d tree等等。。
面试一共是两面，一个上午面完的，面完之后感觉还不错，只是后面就没消息了。一面之前先手写了个代码题（我的是合并字符串，类似于归并排序的合并部分），
再拿过去给一面面试官，话说我硬是在那里等了一个小时，别人只需要等20分钟左右，真的很无解额。
一面：先也是针对简历，然后是c++，设计模式，算法，图形学之类的。C++（多态…），设计模式（貌似是个状态模式还是啥，我设计模式很渣），
算法（概率类dp，最优化搜索二叉树），图形学（glsl常识），更多的忘记了，过了一会儿就去二面了。
二面：二面面试官感觉人很和善，一直笑眯眯的。也问了很多问题，最后还聊了腾讯和网易这两家。开始也先是问简历，只是这次我说的不多，感觉不给力，说实话得注意突出自己。
C++（实现类的set和get），图形学（光照模型，glsl片元获得实际位置等），算法题（手写数组去重，线段树实现区间覆盖查询，我当时居然没说清楚线段树实现，败了），
感觉问题不多，聊得也不错。后面就问我拿到什么offer，我说了有腾讯的。然后，他就开始比较腾讯了，说了一些某些公司怎么样的话，进行了一些对比，也说了网易的培训机制。
这样一说，我就感觉我通过的可能性很大的。而且，最后他还送我出门，握手了，受宠若惊。只是最后居然没通知，非常意外的感觉。只能说，我还是太年轻了，很多准备没做充分，好好努力吧。
PS：说实话，即使过了我也不一定去，因为我爸爸和叔叔在深圳那边上班。也感觉腾讯氛围和平台确实更舒服，虽然网易多几万的工资，也号称工资和奖金分开算。
不过，我既然去不了就永远不会知道内幕了。
这就是我找工作的整个过程，因为时间有点久了，记不起那么多了，再不写估计就忘记完了。感谢碰到的每个面试官，是你们让我成长和得到承认额，
尤其感觉腾讯的面试官，给了我人生的这次非常重要的机会。

OpenGL立即模式必须先指定纹理坐标

发表于 2014-10-27 分类于图形学， OpenGL 阅读次数： Valine：
本文字数： 558 阅读时长 ≈ 1 分钟

说实话，立即模式用了一年多了，还是犯了这个错误。因为很多代码例子里面都是先指定法线，再指定位置，结果添加纹理坐标的时候就变成了指定纹理坐标在最后。
错误的写法：

1
2
3

glNormal3f(n.x(), n.y(), n.z());
glVertex3f(p.x(), p.y(), p.z());
glTexCoord1f(g_p_DisFromFile->norm_dis[g_denoted_point_id][he->vertex()->tag()]);

不要以为这个bug很简单，说实话这种绘制的bug，不知道真的无从调试起来。。。这样写出现什么样子的bug，看下图吧。。。

面片是不是很恶心的块状物？？？我这里绘制的是三维属性场，肯定是连续的，我无论怎么改插值模式，都没有用。。。
后面才回想起以前遇到过这个bug，所以改过来了。正确的代码应该是：

1
2
3

glTexCoord1f(g_p_DisFromFile->norm_dis[g_denoted_point_id][he->vertex()->tag()]);
glNormal3f(n.x(), n.y(), n.z());
glVertex3f(p.x(), p.y(), p.z());

正确的显示结果是：

如此简单的事情，能造成这样大的差距。

快排的N种写法

发表于 2014-10-09 分类于算法阅读次数： Valine：
本文字数： 3.2k 阅读时长 ≈ 3 分钟

首先声明下，只扯面试时候容易手写出来的代码。不写类似于stl里面实现sort的优化部分，包括递归层次太深了改用堆排序，还有当序列长度小于一定值，改用插排，等等。
这里只讲快排主函数的三种写法和partion的两种写法，加上轴元素的选择。
为了兼容stl，假设传入的参数是指针(直接可以换成迭代器了)。
所以主函数应该是这样的接口:void QSort(intbeg, int end);
主函数写法1—-分治递归，也就是常用的写法。

void QSort(int* beg, int* end)
{
    if (beg >= end)
    {
        return;
    }

    int* middle = Partion(beg, end);
    QSort(beg, middle);
    QSort(middle + 1, end);

}

这个是最直观，最简单的写法，至于快排的思路就不介绍了。下面是将其改成循环形式的递归，也有人说这是尾递归，但是当前栈不能完全消除额。所以，到底是不是尾递归了？

void QSort(int* beg, int* end)
{
    if (beg >= end)
    {
        return;
    }

    while (beg < end)
    {
        int* middle = Partion(beg, end);
        QSort(beg, middle);
        beg = middle + 1;
    }
}

说下我对这种写法的理解。其实，推广一下，分治造成的多次递归调用都可以改成这种循环形式。这样的话，双支就变成单支了，至少能减少爆栈的可能性。其余的好处，应该不大吧。问题是，如何将其改成这种循环形式了。额，其实可以这样想。分治的话，是划分为多个子问题，那么循环尾递归的话，是一次处理原问题的一部分，不断减少原问题，那么代码思路就顺理成章的出来了。上面的代码[beg,end)就代表的是问题空间，每次循环一直在减小这个空间。
下面说一个更少见的写法，就是将递归改成非递归。其实了，这种写法，会的人觉得很简单，不会的人就会觉得少见。递归改循环，大家都知道是加个栈，问题是如何用栈模拟递归了。

void QSort(int* beg, int* end)
{
    if (beg >= end)
    {
        return;
    }

    struct Infor
    {
        int* beg;
        int* end;
        Infor(int* b = 0, int* e = 0) : beg(b), end(e) {}
    };

    stack<Infor> si;
    si.push(Infor(beg, end));

    while (si.size())
    {
        Infor in = si.top();
        si.pop();

        int* middle = Partion(in.beg, in.end);

        if (middle > in.beg)
        {
            si.push(Infor(in.beg, middle));
        }

        if (middle  + 1 < in.end)
        {
            si.push(Infor(middle + 1, in.end));
        }
    }
}

从上面的代码中，能够体会到，其实在栈里面存储下递归的参数就行了。栈反正是先入后出的，递归不也是这样么？那么，我们可以采用模拟先序，中序，或者后序遍历树的方法，任何递归都能够模拟出来吧，只是代码复杂程度的问题了。只是真正理解这个，需要一点点时间而已。上面的代码，其实就是用栈模拟了先序遍历二叉树吧。
那么剩下的就是partion函数了。
先来一个教科书版本的代码。

int* Partion(int* beg, int* end)
{
    --end;
    int tmp = *end;
    while (beg < end)
    {
        while (beg < end  *beg <= tmp) ++beg;
        *end = *beg;

        while (beg < end  *end >= tmp) --end;
        *beg = *end;
    }
    *end = tmp;

    return end;
}

这个代码应该非常常见，大部分写法就是这种。首先，看到轴元素是在end处。所以了，将end处的元素暂存，所以end就空出来了。因此，先从头开始遍历到第一个大于*end的元素，然后将其放入end。剩下的一个循环就是从后面往前面遍历了。最后大循环结束时候，beg必定等于end，而且必定放的是一个重复的元素，所以了，放入轴元素就行了。
下面介绍种更简便的写法。

int* Partion(int* beg, int* end)
{
    --end;
    int* small = beg;
    while (beg < end)
    {
        if (*beg < *end)
        {
            if (beg != small)
            {
                swap(*beg, *small);
            }

            ++small;
        }

        ++beg;
    }
    swap(*end, *small);

    return small;
}

这个代码只要一个循环，思路是[0,small)中放小于轴元素的数字，保持这个集合就行了。那么，最终轴元素就应该放在small处。理解下吧，这个代码更方面手写出来。
现在还剩个更严重的问题，如何消除快排的最坏情况出现的可能。最坏情况出现在输入数据本身有序的时候。
如果听说过随机算法，那么这个问题就知道怎么轻松解决了。在算法中，加入随机性操作吧。在partion，可以随机选择轴元素，也可以采用三点取中法选择轴元素。至于证明，参加算法导论。

int* Partion(int* beg, int* end)
{
    int len = end - beg;

    swap(beg[rand() % len], *(end - 1));//随机选取轴元素

    --end;
    int* small = beg;
    while (beg < end)
    {
        if (*beg < *end)
        {
            if (beg != small)
            {
                swap(*beg, *small);
            }

            ++small;
        }

        ++beg;
    }
    swap(*end, *small);

    return small;
}

三点取中法。

int* Partion(int* beg, int* end)
{
    int len = end - beg;
    int* middle = beg + len / 2;
    --end;
    if (*middle < *beg)
    {
        swap(*middle, *beg);
    }
    if (*end < *beg)//最小
    {
        swap(*beg, *end);
    }
    else if (*end > *middle)//最大
    {
        swap(*middle, *end);
    }

    int* small = beg;
    while (beg < end)
    {
        if (*beg < *end)
        {
            if (beg != small)
            {
                swap(*beg, *small);
            }

            ++small;
        }

        ++beg;
    }
    swap(*end, *small);

    return small;
}

组合这些不同的写法，确实可以出现很多个版本的快排算法了。。。

top k算法和partial_sort

发表于 2014-10-08 分类于算法阅读次数： Valine：
本文字数： 1.5k 阅读时长 ≈ 1 分钟

最近因为准备找工作的东西，看了不少书，感悟也挺多的。stl源码剖析，effective c++，面试宝典，剑指offer，大话设计模式，编程精粹，还有很多想看的还没看完了。。。这段时间，看完这些书后，真的发现，看书是一件很棒的事情，不仅仅是知识的学习，查漏补缺，思维的体验也是一件让人觉得满心愉悦的事情。有点明白古人雪夜读书的感觉，那时候没有电脑可以玩，没有那么多娱乐的游戏，读书确实是一件让人愉悦的事情。
很久没有更新博客了，随便扯扯吧。
所谓的top k算法，意思就是求n个数字的最大k个或者最小k个，大概也是个比较常见的面试题了。一般有两种思路，第一种是利用快排里面的partion函数，不断用轴元素分割数组，直到分割出前k个或者后k个，迭代或者递归都是很方便的；stl里面有个nth_element泛函做的就是这件事情。第二种思路，则是假定有一个容量为k的容器，存储了当前的top k元素，当处理下一个元素的时候，判断当前处理元素是否可能是top k元素，比如如果求最大的k个元素，则判断当前处理元素是否比容器里面最小元素大，如果大的话，则需要加入当前元素，并且删除容器里面最小的元素，反之亦然。现在的问题是，如何选取一个很好的容器了。能够使得这些操作尽可能快。其实大家知道的容器也就那几种类型，基本上是stl里面已经实现了的。线性？搜索树？hash？
hash的话，没法快速查找极值，线性结构的话，插入新元素，保持有序结构的话，也需要O(n)。那么，搜索树结构了，查找和删除都是log(n)，stl里面有现成的红黑树实现set容器。另外，还有个更奇葩的用数组表示的完全二叉树结构，最大堆和最小堆。可以满足O(1)查找极值元素和log(n)插入删除操作，最终还可以排序元素。综上所说，堆结构是在时间和空间上最佳的满足要求的容器了。
刚好stl里面有个partial_sort函数也是用这个思路实现的，而且最后还排了一个序，所以，实际开发的时候多了解下标准库是值得投入的一件事情。
下面是用stl的heap操作实现的top k算法。

#include <cstdlib>
#include <iostream>
#include <vector>
using namespace std;

int main()
{
    vector<int> vi;
    const int NUM = 100;

    for (int i = 0; i < NUM; ++i)
    {
        vi.push_back(rand() % NUM);
        printf("%d ", vi[i]);
    }
    printf("\n");

    //求最小k个数字
    const int K = 10;

    make_heap(vi.begin(), vi.begin() + K);
    for (int i = K; i < NUM; ++i)
    {
        if (vi[i] < vi[0])
        {
            pop_heap(vi.begin(), vi.begin() + K);
            vi[K - 1] = vi[i];
            push_heap(vi.begin(), vi.begin() + K);
        }
    }

    sort_heap(vi.begin(), vi.begin() + K);
    for (int i = 0; i < K; ++i)
    {
        printf("%d ", vi[i]);
    }
    printf("\n");

    return 0;
}

多态的内存结构

发表于 2014-08-17 分类于编程语言， C++ 阅读次数： Valine：
本文字数： 4.9k 阅读时长 ≈ 4 分钟

这里的多态指的是动态多态，不包括函数重装和模版的静态多态内容。多态所代表的特性，才是面向对象的真正表现。具体行为其实就是用基类的指针或者引用调用虚函数，得到的结果跟指针指向对象的具体类型有关，而跟指针的静态类型无关。比如说，基类指针指向派生类A的对象，那么调用的其实是派生类A里面实现的虚函数，如果是派生类B的对象，那么则是B类里面实现的虚函数。
我们先定义一个接口。也就是一个包含纯虚函数的类，这种类不能用于构造对象。其实，接口才是我们最关心的。

#define interface struct
interface IAnimal
{
    virtual void Eat() = 0;
    virtual void Drink() = 0;
    virtual void Sleep() = 0;
};

然后定义2个类继承这个接口。

class  CMonkey : public IAnimal
{
public:
    CMonkey()
    {
        m_nSex = 0;
    }

    virtual void Eat()
    {
        cout << "Monkey Eat" << endl;
    }

    virtual void Drink()
    {
        cout << "Monkey Drink" << endl;
    }

    virtual void Sleep()
    {
        cout << "Monkey Sleep" << endl;
    }

    enum SEX
    {
        MALE = 0,
        FEMALE = 1
    };

    int GetSex() const { return m_nSex; }
    void SetSex(int nSex) { m_nSex = nSex; }

private:
    int m_nSex;//0:male,1:female
};

class  CMonster : public IAnimal
{
public:
    CMonster()
    {
        m_nEvil = NO;
    }

    virtual void Eat()
    {
        cout << "Monster Eat" << endl;
    }

    virtual void Drink()
    {
        cout << "Monster Drink" << endl;
    }

    virtual void Sleep()
    {
        cout << "Monster Sleep" << endl;
    }

    enum EVIL
    {
        NO = 0,
        YES = 1
    };

    int GetEvil() const { return m_nEvil; }
    void SetEvil(int nEvil) { m_nEvil = nEvil; }

private:
    int m_nEvil;//0:no,1:yes
};

再定义CPeople多重继承上面2个类。

class CPeople : public CMonkey, public CMonster
{
public:
    virtual void Eat()
    {
        cout << "People Eat" << endl;
    }

    virtual void Drink()
    {
        cout << "People Drink" << endl;
    }

    virtual void Sleep()
    {
        cout << "People Sleep" << endl;
    }

    virtual void Name()
    {
        cout << "People Name" << endl;
    }

    const char* GetName() const { return m_szName; }
    void SetName(char* pszName) { strcpy(m_szName, pszName); }

private:
    char m_szName[12];
};

我们先来测试多态是如何表现的。

CMonkey monkey;
monkey.SetSex(CMonkey::MALE);

CMonster monster;
monster.SetEvil(CMonster::YES);

CPeople people;
people.SetName("Jack");

//下面代码用于展示多态
IAnimal* pAnimal[3];
pAnimal[0] = monkey;
pAnimal[1] = monster;
pAnimal[2] = (CMonkey*)people;
for (int i = 0; i < 3; ++i)
{
    pAnimal[i]->Eat();
    pAnimal[i]->Drink();
    pAnimal[i]->Sleep();
}
cout << endl;

这段代码的输出如下：

从代码的输出可以看到，pAnimal[i]是根据所指向的数据类型确定该调用什么函数的。这就是多态的意思。相同的接口，不同的表现。
下面我们来推测这几个对象的内存布局。首先是monkey。
假设，对象monkey的内存布局，如图：
也就是，monkey保护2个成员，一个虚函数表指针和一个int成员。虚函数表指针指向一个表，前面3项是函数地址，第四项是NULL，第五项根据有些书籍的说法是type_info对象的地址。
我用下面的代码来验证这个内存布局。

typedef void (*FunType) ();
FunType p;
int nSex;
int* vtbl = NULL;
cout << "sizeof(monkey): " << sizeof(monkey) << endl;
vtbl = (int*)(*(int*)monkey);//虚函数指针
cout << "vtbl address:" << (int)vtbl << endl;
p = (FunType)vtbl[0];
p();
p = (FunType)vtbl[1];
p();
p = (FunType)vtbl[2];
p();
cout << "vtbl[3]:" << vtbl[3] << endl;
cout << "vtbl[4]:" << vtbl[4] << endl;
nSex = *((int*)monkey + 1);
cout << "nSex: " << nSex << endl << endl;

输出如同：
从输出可以看到，monkey大小为8字节，刚好是一个指针和一个int的大小。而且，monkey的地址转换为int*之后，再取值就可以得到虚函数表的地址。用vtbl[0]到vtbl[2]调用刚好是调用接口里面定义的三个虚函数。vtbl[3]为0，vtbl[4]为一个地址。为什么，这里推断vtbl里面含有5项了，而不是4项了。下面再说明。
monster的内存布局类似，就不说明了。
最关键的是people的内存布局。推测如下图所示：
用下面的代码，来验证这个假设。

cout << "sizeof(people): " << sizeof(people) << endl;
vtbl = (int*)(*(int*)people);//虚函数指针
cout << "vtbl address:" << (int)vtbl << endl;
p = (FunType)vtbl[0];
p();
p = (FunType)vtbl[1];
p();
p = (FunType)vtbl[2];
p();
p = (FunType)vtbl[3];
p();
cout << "vtbl[4]:" << vtbl[4] << endl;
cout << "vtbl[5]:" << vtbl[5] << endl;

nSex = *((int*)people + 1);
cout << "nSex: " << nSex << endl << endl;

vtbl = (int*)(*((int*)people + 2));//虚函数指针
cout << "vtbl address:" << (int)vtbl << endl;
p = (FunType)vtbl[0];
p();
p = (FunType)vtbl[1];
p();
p = (FunType)vtbl[2];
p();
cout << "vtbl[3]:" << vtbl[3] << endl;
cout << "vtbl[4]:" << vtbl[4] << endl;
nEvil = *((int*)people + 3);
cout << "nEvil: " << nEvil << endl << endl;

char* pszName = (char*)((int*)people + 4);
cout << pszName << endl;

输出如同：
people大小为28字节，符合假设。第一个成员为继承自CMonkey的虚函数表指针，符合假设。虚函数表的前三项，是在CPeople类中实现的接口里面虚函数地址，接下来CPeolple里面定义的虚函数Name的地址，最后是NULL和type_info obj的地址。people的第三个成员为继承自CMonster的虚函数指针，指向虚函数表的第七项。从第七项开始，可以看作继承自CMonster的虚函数表。
从输出可以看出，CPeople里面新定义的虚函数，放到第一个虚函数指针所指向的虚表里面了。并且，由于一个类只有只有一张虚表，所以不同的虚函数指针所指向的其实是虚表的不同部分。这些表可以看作是独立的，也可以看作是地址上面连续的。
前面说过，为什么猜测虚函数表里面还有一个NULL项了，然后才跟随一个type_info obj的地址？由于，在上面的输出中，2个虚函数指针相差是24。所以，我猜测第一个虚表里面含有6项。经过代码测试，第五项也是0。
至于为什么猜测内存布局里面先是虚函数表的指针，再是数据成员，这个是我通过代码测试得来的。环境是vs2013。