2013腾讯实时面试记录

原文链接：http://blog.csdn.net/left_la/article/details/8851759

始于2013.04.20南大笔试

结束于2013.04.24天丰一面

主要的几个问题：

1、关于3D渲染管线

一个简单的例子，从游戏到多边形绘制的图形管线过程大致是这样:

· 游戏决定在游戏中有哪些对象，它们的模型，使用的纹理，他们可能在什么动画幀，以及它们在游戏世界里的位置。游戏也决定照相机的位置和方向。

· 游戏把这些信息传递给渲染器。以模型为例，渲染器首先要查看模型的大小，照相机的位置，然後决定模型在屏幕上是否全部可见，或者在观察者 (照相机视野) 的左边，在观察者的后面，或距离很远而不可见。它甚至会使用一些世界测定方式来计算出模型是否是可见的。 (参见下面这条)

· 世界可视化系统决定照相机在世界中的位置，并根据照相机视野决定世界的哪些区域 / 多边形是可见的。有许多方法可以完成这个任务，包括把世界分割成许多区域的暴力方法，每个区域直接为"我能从区域 D 看见区域 AB & C"，到更精致的 BSP(二叉空间分割)世界。所有通过这些剔除测试的多边形被传递给多边形渲染器进行绘制。

· 对於每一个被传递给渲染器的多边形，渲染器依照局部数学 ( 也就是模型动画) 和世界数学(相对于照相机的位置?)对多边形进行变换，并检查决定多边形是不是背对相机 (也就是远离照相机)。背面的多边形被丢弃。非背面的多边形由渲染器根据发现的附近灯光照亮。然后渲染器要看多边形使用的纹理，并且确定 API/ 图形卡正在使用那种纹理作为它的渲染基础。在这里，多边形被送到渲染 API，然后再送给显卡。

Dave Salvator's 3D 管线一文中的图表如下，可作为详细参考：

硬件中的渲染管线也称为渲染流水线，是显示芯片内部处理图形信号相互独立的的并行处理单元。一个流水线是一序列可以并行和按照固定顺序进行的阶段。每个阶段都从它的前一阶段接收输入，然后把输出发给随后的阶段。就像一个在同一时间内，不同阶段不同的汽车一起制造的装配线，传统的图形硬件流水线以流水的方式处理大量的顶点、几何图元和片段。基本过程如下：

Local Space -->World Space -->View Space -->Backface Culling -->Lighting -->Clipping -->Projection -->Viewport Space -->Rasterization
Local Space(本地空间):本地空间以叫建模空间,这是我们定义物体三角形列的坐标系。
World Space(世界空间):世界变换就是设置在世界中的各物体彼此的位置,大小和方向关系。
View Space(视图空间):视图空间变换就是世界坐标系中的所有物体随着摄像机的变换而做的相同的变换。
Backface Culling(背面拣选):背面拣选是指正面多边形挡住了在它后面的背面多边形,Direct3D将通过拣选(即删除多余的处理过程)背面多边形来提高效率的过程。
Lighting(光照):光源被定义在世界空间中,不是通过视图空间变换到视图空间中。
Clipping(裁剪):裁剪是拣选那些超出了可视体范围的几何图形的过程。有三种情况完全包含,完全在外,部分在内。
Projection(投影):从n维转换成n-1维的过程。
Viewport Transform(视口变换):视口变换是将投影窗口变换为屏幕上一个矩形区域的可靠的变换。
Rasterization(光栅化):光栅化过程是计算需要显示的每个三角形中每个点颜色值。

参考文章：

1.《游戏引擎剖析》第一部分

2.《3D管线教程 (一)》

2、纹理和材质的概念与区别、如何绑定、如何渲染出来

纹理更偏向于“图”，而材质更偏向于“属性”。
打个比方说，对同一个立方体模型进行处理：

加纹理信息，可以认为是贴上图，比如木头的纹理图，大理石的纹理图。
加材质信息，可以认为是为这个立方体加上属性（这些属性主要是指反射系数、折射系数等），比如木头的属性或大理石的属性。

纹理可以理解为是物体的外表图案。在3D场景中，它极大的增加了物体的真实性。例如，我们可以在显示屏上画上一系列组合的矩形来表示一堵墙，但这样的墙看起来光秃秃的，颜色也不真实。如果我们再在上面加上一些划痕，磨损，苔迹，还有标语，使它看起来更象一堵真实的墙，这就是纹理。
在D3D中，物体的这些外表图案是存储在一些二维的图片中的，纹理也即是指这些二维的图片，它一般采用bmp或 ppm的图片格式。纹理上的每一个像素称为纹理像素(Texel).

材质是指构成现实中物体的材料，它使一个物体看上去更象金属做的，陶瓷做的，还是塑料的。
在现实生活中，当我们看一个铅球，凭眼睛的观察，手的触摸，还有保存在我们头脑里的一些生活的常识，我们很容易判别该球是金属做的，同样看到一只足球，我们也很容易知道他是橡胶做的。
这样就会产生一个问题，对显示屏中虚拟的物体，光凭眼睛我们怎样辨别它使金属的，还是塑料的呢？或者说，在电脑上我们怎样表示一个物体材质属性呢？在微软Direct3D中，是用物体对光的反射属性来表达一个物体的材质的，很显然，金属的物体和塑料的物体对光的反射会有不同的反射效果。这样做虽然有时会产生失真，但对于屏幕渲染来说也是足够了。

材质可以看成是材料和质感的结合。在渲染程式中，它是表面各可视属性的结合，这些可视属性是指表面的色彩、纹理、光滑度、透明度、反射率、折射率、发光度等。

从另一个角度来看，加了纹理的模型是静态的和表面的，不会因为外界环境变化而变化（比如光照）。但是加了材质的模型是动态的和本质的，当外界环境变化的时候能做出相应的变化，所以更真实。
最简单的例子就是，我们可以做出有木头光泽的大理石模型，有大理石光泽的木头模型，有木头光泽的木头模型，有大理石光泽的大理石模型。在上面的描述中，有“什么光泽”的“什么”，这是材质信息；“什么模型”的“什么”，这是纹理信息。

6、关于RTTI

Runtime Type identificaion(运行时类型识别，RTTI)，程序能够使用基类的指针或引用来检索这些指针或引用所指对象的实际派生类型。

通过下面两个操作符提供RTTI

（1）typeid操作符，返回指针或引用所指对象的实际类型。

typeid表达式如下：

typeid(e)

这里e是任意表达式或者是类型名。

如果操作数不是类类型或者是没有虚函数的类，则typeid操作符指出操作数的静态类型；如果操作数是定义了至少一个虚函数的类类型，则在运行时计算类型。即：只有当typeid的操作数是带虚函数的类类型的对象的时候，才返回动态类型信息。

讲到运行时识别，这就想到了虚函数，虚函数的动态调用时通过虚函数表vrbl来实现的，那么typeid是如何实现的呢？

要想让任何一个内含虚函数的对象都有能力取得其专属信息的能力，于是乎，可以同样依靠虚函数表vrbl来实现，将RTTI信息的地址放到虚函数表中第一个虚函数的前面，这个RTTI信息为Derive::`RTTI Complete Object Locator。示意图如下：

（2）dynamic cast操作符，将基类类型的指针或引用安全得转换为派生类类型的指针或引用，基于RTTI数据信息，在执行时先验证被请求的转换是否有效，只有有效，操作符才能实际进行转换。

参考文章：

1.《如何在运行时确定对象类型（RTTI）》

2.《浅议 Dynamic_cast 和 RTTI》

7、编程实现统计整形数组中各个数字出现的次数

7.1 使用计数排序的方法，先找出这堆整形数组中的数字大小范围，然后新建一个同等大小的数组来存放每个数字对应的次数，遍历一遍原数组来统计次数，遍历一遍新数组来输出统计。此方法适用于数字范围小，但个数多的情况，不然空间复杂度和时间复杂度会过多消耗。实现过程如下：

[cpp] view plain copy

// 1.0 使用计数排序  
void fun(int a[], int n)  
{  
    int i;  
    int max = -10000000;    
    int min = 10000000;    
      
    // 查找数列最大最小值    
    for (i=0; i<n-1; i=i+2)    
    {    
        if (a[i]>a[i+1])    
        {    
            if (a[i]>max)    
                max = a[i];    
            if (a[i+1]<min)    
                min = a[i+1];    
        } else {    
            if (a[i+1]>max)    
                max = a[i+1];    
            if (a[i]<min)    
                min = a[i];    
        }    
    }    
    if (i == n-1)    
    {    
        if (a[i]>max)    
            max = a[i];    
        else if(a[i]<min)    
            min = a[i];    
    }    
  
    // 先计数后输出  
    int lenb = max-min+1;  
    int *b = new int[lenb];  
    memset(b, 0, lenb*sizeof(int));  
    for (i=0; i<n; i++)  
        b[a[i]-min]++;  
    for (i=0; i<lenb; i++)  
    {  
        if (b[i]!=0)  
            cout<<i+min<<":"<<b[i]<<endl;  
    }  
  
    delete []b;  
}

7.2 使用STL中的map来进行数据的存放和查找计数，数字为键值，次数为对应数据，map利用树结构来动态管理插入和查找，效率较高

[cpp] view plain copy

    // 2.0 利用map  
    void fun2(int a[], int n)  
    {  
        map<int, int> b;  
        for (int i=0; i<n; i++)  
            b[a[i]]++;  
        for (map<int,int>::iterator iter = b.begin(); iter!=b.end(); iter++)  
            cout<<iter->first<<":"<<iter->second<<endl;  
    }

7.3 先将原数据进行快排，然后遍历一遍统计个数，但若不备份会破坏原数据

[cpp] view plain copy

int compare (const void * a, const void * b)  
{  
    return ( *(int*)a - *(int*)b );  
}  
  
void fun3(int a[], int n)  
{  
    qsort(a, n, sizeof(int), compare);  
    int temp = a[0];  
    int count = 1;  
    for (int i=1; i<n; i++)  
    {  
        if (temp == a[i])  
            count ++;  
        else  
        {  
            cout<<temp<<":"<<count<<endl;  
            temp = a[i];  
            count = 1;  
        }  
    }  
    cout<<temp<<":"<<count<<endl;  
}