CODEMYLIFE的部落格

转自中文编码杂谈，很好的一篇讲中文编码的文章，感谢原作者分享！

编码问题的例子
在windows自带的notepad（记事本）程序中输入“联通”两个字，保存后再次打开，会发现“联通”不见了，代之以“��ͨ”的乱码。这是windows平台上典型的中文编码问题。即文件保存的时候是按照ANSI编码（其实就是GB2312，后面会详细介绍）保存，打开的时候程序按照UTF-8方式对内容解释，于是就出现了乱码。避免乱码的方式很简单，在“文件”菜单中选择“打开”命令，选择保存的文件，然后选择“ANSI”编码，此时就能看到久违的“联通”两个字了。

在Linux平台上如果使用cat等命令查看文件中的中文内容时，可能出现乱码。这也是编码的问题。简单的说是文件时按照A编码保存，但是cat命令按照当前Locale设定的B编码去查看，在B和A不兼容的时候就出现了乱码。

为什么写这篇文章
中文编码由于历史原因牵扯到不少标准，在不了解的时候感觉一头雾水；但其实理解编码问题并不需要你深入了解各个编码标准，只要你明白了来龙去脉，了解了关键的知识点，就能分析和解决日常开发工作中碰到的大部分编码问题。有感于我看过的资料和文章要么不够全面，要么略显枯燥，所以通过这篇文章记录下笔者在日常工作中碰到的中文编码原理相关问题，目的主要是自我总结，如果能给读者提供一些帮助那就算是意外之喜了。由于严谨的编码标准对我来说是无趣的，枯燥的，难以记忆的，本文尝试用浅显易懂的生活语言解释中文编码相关的（也可能不相关的）一些问题，这也是为什么取名杂谈的原因。本文肯定存在不规范不全面的地方，我会在参考资料里给出官方文档的链接，也欢迎读者在评论中提出更好的表达方式&指出错误，不胜感激。

对编码问题的理解我认为分为三个层次，第一个层次：概念，知道各个编码标准的应用场景，了解之间的差异，能分析和解决常见的一些编码问题。第二个层次：标准，掌握编码的细节，如编码范围，编码转换规则，知道这些就能自行开发编码转换工具。第三个层次，使用，了解中文的编码2进制存储，在程序开发过程中选择合理的编码并处理中文。为了避免让读者陷入编码标准的黑洞无法脱身（不相信？看看unicode的规范就明白我的意思了），同时由于编码查询&转换工具等都有现成工具可以使用，本文只涉及第一个层次，不涉及第二层次，在第三层次上会做一些尝试。在本文的最后提供了相关链接供对标准细节感兴趣的同学继续学习。最后，本文不涉及具体软件的乱码问题解决，如ssh，shell，vim，screen等，这些话题留给剑豪同学专文阐述。

一切都是因为电脑不识字
电脑很聪明，可以帮我们做很多事情，最开始主要是科学计算，这也是为什么电脑别名计算机。电脑又很笨，在她的脑子里只有数字，即所有的数据在存储和运算时都要使用二进制数表示。这在最初电脑主要用来处理大量复杂的科学计算时不是什么大问题但是当电脑逐步走入普通人的生活时，情况开始变遭了。办公自动化等领域最主要的需求就是文字处理，电脑如何来表示文字呢？这个问题当然难不倒聪明的计算机科学家们，用数字来代表字符呗。这就是“编码”。

英文的终极解决方案：ASCII
每个人都可以约定自己的一套编码，只要使用方之间了解就ok了。比如说咱俩约定0×10表示a，0×11表示b。在一开始也的确是这样的，出现了各式各样的编码。这样有两个问题：1.各个编码的字符集不一样，有的多，有的少。2.相同字符的编码也不一样。你这里a是0×10.他那里a可能是0×30。于是你保存的文件他就不能直接用，必须要转换编码。随着沟通范围的扩大，采用不同编码的人们互相通信就乱套了，这就是我们常说的：鸡同鸭讲。如果要避免这种混乱，那么大家就必须使用相同的编码规则，于是美国有关的标准化组织就出台了ASCII（American Standard Code for Information Interchange）编码，统一规定了英文常用符号用哪些二进制数来表示。ASCII是标准的单字节字符编码方案，用于基于文本的数据。

ASCII最初是美国国家标准，供不同计算机在相互通信时用作共同遵守的西文字符编码标准，已被国际标准化组织（International Organization for Standardization, ISO）定为国际标准，称为ISO 646标准。适用于所有拉丁文字字母。ASCII 码使用指定的7 位或8 位二进制数组合来表示128 或256 种可能的字符。标准ASCII 码也叫基础ASCII码，使用7 位二进制数来表示所有的大写和小写字母，数字0 到9、标点符号， 以及在美式英语中使用的特殊控制字符。而最高位为1的另128个字符（80H—FFH）被称为“扩展ASCII”，一般用来存放英文的制表符、部分音标字符等等的一些其它符号。

其中：0～31及127(共33个)是控制字符或通信专用字符（其余为可显示字符），32～126(共95个)是字符(32是空格），其中48～57为0到9十个阿拉伯数字，65～90为26个大写英文字母，97～122号为26个小写英文字母，其余为一些标点符号、运算符号等。

现在所有使用英文的电脑终于可以用同一种编码来交流了。理解了ASCII编码，其他字母型的语言编码方案就触类旁通了。

一波三折的中文编码
第一次尝试：GB2312
ASCII这种字符编码规则显然用来处理英文没有什么问题，它的出现极大的促进了信息在西方尤其是美国的传播和交流。但是对于中文，常用汉字就有6000以上，ASCII 单字节编码显然是不够用。为了粉碎美帝国主义通过编码限制中国人民使用电脑的无耻阴谋，中国国家标准总局发布了GB2312码即中华人民共和国国家汉字信息交换用编码，全称《信息交换用汉字编码字符集——基本集》，1981年5月1日实施，通行于大陆。GB2312字符集中除常用简体汉字字符外还包括希腊字母、日文平假名及片假名字母、俄语西里尔字母等字符，未收录繁体中文汉字和一些生僻字。 EUC-CN可以理解为GB2312的别名，和GB2312完全相同。

GB2312是基于区位码设计的，在区位码的区号和位号上分别加上A0H就得到了GB2312编码。这里第一次提到了“区位码”，我就连带把下面这几个让人摸不到头脑的XX码一锅端了吧：

区位码，国标码，交换码，内码，外码

区位码：就是把中文常用的符号，数字，汉字等分门别类进行编码。区位码把编码表分为94个区，每个区对应94个位，每个位置就放一个字符（汉字，符号，数字都属于字符）。这样每个字符的区号和位号组合起来就成为该汉字的区位码。区位码一般用10进制数来表示，如4907就表示49区7位，对应的字符是“学”。区位码中01-09区是符号、数字区，16-87区是汉字区，10-15和88-94是未定义的空白区。它将收录的汉字分成两级：第一级是常用汉字计3755个，置于16-55区，按汉语拼音字母/笔形顺序排列；第二级汉字是次常用汉字计3008个，置于56-87区，按部首/笔画顺序排列。在网上搜索“区位码查询系统”可以很方便的找到汉字和对应区位码转换的工具。为了避免广告嫌疑和死链，这里就不举例了。

国标码： 区位码无法用于汉字通信，因为它可能与通信使用的控制码（00H~1FH）（即0~31，还记得ASCII码特殊字符的范围吗？）发瑞脑消金兽生冲帘卷西风突。于是ISO2022规定每个汉字的区号和位号必须分别加上32（即二进制数00100000，16进制20H），得到对应的国标交换码，简称国标码，交换码，因此，“学”字的国标交换码计算为：

00110001 00000111
+ 00100000 00100000
-------------------
01010001 00100111
用十六进制数表示即为5127H。

交换码：即国标交换码的简称，等同上面说的国标码。

内码：由于文本中通常混合使用汉字和西文字符，汉字信息如果不予以特别标识，就会与单字节的ASCII码混淆。此问题的解决方法之一是将一个汉字看成是两个扩展ASCII码，使表示GB2312汉字的两个字节的最高位都为1。即国标码加上128（即二进制数10000000,16进制80H）这种高位为1的双字节汉字编码即为GB2312汉字的机内码，简称为内码。20H+80H=A0H。这也就是常说的在区位码的区号和位号上分别加上A0H就得到了GB2312编码的由来。

00110001 00000111
+ 10100000 10100000
-------------------
11010001 10100111
用十六进制数表示即为D1A7H。

外码：机外码的简称,就是汉字输入码，是为了通过键盘字符把汉字输入计算机而设计的一种编码。 英文输入时，相输入什么字符便按什么键，外码和内码一致。汉字输入时，可能要按几个键才能输入一个汉字。 汉字输入方案有成百上千个，但是这千差万别的外码输入进计算机后都会转换成统一的内码。
最后总结一下上面的概念。中国国家标准总局把中文常用字符编码为94个区，每个区对应94个位，每个字符的区号和位号组合起来就是该字符的区位码, 区位码用10进制数来表示，如4907就表示49区7位，对应的字符是“学”。 由于区位码的取值范围与通信使用的控制码（00H~1FH）（即0~31）发瑞脑消金兽生冲帘卷西风突。每个汉字的区号和位号分别加上32（即16进制20H）得到国标码，交换码。“学”的国标码为5127H。由于文本中通常混合使用汉字和西文字符，为了让汉字信息不会与单字节的ASCII码混淆，将一个汉字看成是两个扩展ASCII码，即汉字的两个字节的最高位置为1，得到的编码为GB2312汉字的内码。“学”的内码为D1A7H。无论你使用什么输入法，通过什么样的按键组合把“学”输入计算机，“学”在使用GB2312（以及兼容GB2312）编码的计算机里的内码都是D1A7H。

第二次尝试：GBK
GB2312的出现基本满足了汉字的计算机处理需要，但由于上面提到未收录繁体字和生僻字，从而不能处理人名、古汉语等方面出现的罕用字，这导致了1995年《汉字编码扩展规范》（GBK）的出现。GBK编码是GB2312编码的超集，向下完全兼容GB2312，兼容的含义是不仅字符兼容，而且相同字符的编码也相同，

中文二进制存储
同时在字汇一级支持ISO/IEC10646—1和GB 13000—1的全部中、日、韩（CJK）汉字，共计20902字。GBK还收录了GB2312不包含的汉字部首符号、竖排标点符号等字符。CP936和GBK的有些许差别，绝大多数情况下可以把CP936当作GBK的别名。

第三次尝试：GB18030
GB18030编码向下兼容GBK和GB2312。GB18030收录了所有Unicode3.1中的字符，包括中国少数民族字符，GBK不支持的韩文字符等等，也可以说是世界大多民族的文字符号都被收录在内。GBK和GB2312都是双字节等宽编码，如果算上和ASCII兼容所支持的单字节，也可以理解为是单字节和双字节混合的变长编码。GB18030编码是变长编码，有单字节、双字节和四字节三种方式。

其实，这三个标准并不需要死记硬背，只需要了解是根据应用需求不断扩展编码范围即可。从GB2312到GBK再到GB18030收录的字符越来越多即可。万幸的是一直是向下兼容的，也就是说一个汉字在这三个编码标准里的编码是一模一样的。这些编码的共性是变长编码，单字节ASCII兼容，对其他字符GB2312和GBK都使用双字节等宽编码，只有GB18030还有四字节编码的方式。这些编码最大的问题是2个。1.由于低字节的编码范围和ASCII有重合，所以不能根据一个字节的内容判断是中文的一部分还是一个独立的英文字符。2.如果有两个汉字编码为A1A2B1B2，存在A2B1也是一个有效汉字编码的特殊情况。这样就不能直接使用标准的字符串匹配函数来判断一个字符串里是否包含某一个汉字，而需要先判断字符边界然后才能进行字符匹配判断。

最后，提一个小插曲，上面讲的都是大陆推行的汉字编码标准，使用繁体的中文社群中最常用的电脑汉字字符集标准叫大五码（Big5），共收录13,060个中文字，其中有二字为重覆编码(实在是不应该)。Big5虽普及于中国的台湾、香港与澳门等繁体中文通行区，但长期以来并非当地的国家标准，而只是业界标准。倚天中文系统、Windows等主要系统的字符集都是以Big5为基准，但厂商又各自增删，衍生成多种不同版本。2003年，Big5被收录到台湾官方标准的附录当中，取得了较正式的地位。这个最新版本被称为Big5-2003。

天下归一Unicode
看了上面的多个中文编码是不是有点头晕了呢？如果把这个问题放到全世界n多个国家n多语种呢？各国和各地区自己的文字编码规则互相冲突的情况全球信息交换带来了很大的麻烦。

要真正彻底解决这个问题，上面介绍的那些通过扩展ASCII修修补补的方式已经走不通了，而必须有一个全新的编码系统，这个系统要可以将中文、日文、法文、德文……等等所有的文字统一起来考虑，为每一个文字都分配一个单独的编码。于是，Unicode诞生了。Unicode（统一码、万国码、单一码）为地球上（以后会包括火星，金星，喵星等）每种语言中的每个字符设定了统一并且唯一的二进制编码，以满足跨语言、跨平台进行文本转换、处理的要求。在Unicode里，所有的字符被一视同仁，汉字不再使用“两个扩展ASCII”，而是使用“1个Unicode”来表示，也就是说，所有的文字都按一个字符来处理，它们都有一个唯一的Unicode码。Unicode用数字0-0x10FFFF来映射这些字符，最多可以容纳1114112个字符，或者说有1114112个码位（码位就是可以分配给字符的数字）。

提到Unicode不能不提UCS（通用字符集Universal Character Set）。UCS是由ISO制定的ISO 10646（或称ISO/IEC 10646）标准所定义的标准字符集。UCS-2用两个字节编码，UCS-4用4个字节编码。Unicode是由unicode.org制定的编码机制，ISO与unicode.org是两个不同的组织, 虽然最初制定了不同的标准; 但目标是一致的。所以自从unicode2.0开始, unicode采用了与ISO 10646-1相同的字库和字码, ISO也承诺ISO10646将不会给超出0x10FFFF的UCS-4编码赋值, 使得两者保持一致。大家简单认为UCS等同于Unicode就可以了。

在Unicode中：汉字“字”对应的数字是23383。在Unicode中，我们有很多方式将数字23383表示成程序中的数据，包括：UTF-8、UTF-16、UTF-32。UTF是“UCS Transformation Format”的缩写，可以翻译成Unicode字符集转换格式，即怎样将Unicode定义的数字转换成程序数据。例如，“汉字”对应的数字是0x6c49和0x5b57，而编码的程序数据是：

这里用BYTE、WORD、DWORD分别表示无符号8位整数，无符号16位整数和无符号32位整数。UTF-8、UTF-16、UTF-32分别以BYTE、WORD、DWORD作为编码单位。“汉字”的UTF-8编码需要6个字节。“汉字”的UTF-16编码需要两个WORD，大小是4个字节。“汉字”的UTF-32编码需要两个DWORD，大小是8个字节。根据字节序的不同，UTF-16可以被实现为UTF-16LE或UTF-16BE，UTF-32可以被实现为UTF-32LE或UTF-32BE。

下面介绍UTF-8、UTF-16、UTF-32、BOM。

UTF-8

UTF-8以字节为单位对Unicode进行编码。从Unicode到UTF-8的编码方式如下：

Unicode编码(16进制)	UTF-8 字节流(二进制)
000000 – 00007F	0xxxxxxx
000080 – 0007FF	110xxxxx 10xxxxxx
000800 – 00FFFF	1110xxxx 10xxxxxx 10xxxxxx
010000 – 10FFFF	11110xxx 10xxxxxx 10xxxxxx 10xxxxxx

UTF-8的特点是对不同范围的字符使用不同长度的编码。对于0×00-0x7F之间的字符，UTF-8编码与ASCII编码完全相同。UTF-8编码的最大长度是4个字节。从上表可以看出，4字节模板有21个x，即可以容纳21位二进制数字。Unicode的最大码位0x10FFFF也只有21位。总结了一下规律：UTF-8的第一个字节开始的1的个数代表了总的编码字节数，后续字节都是以10开始。由上面的规则可以清晰的看出UTF-8编码克服了中文编码的两个问题。

例1：“汉”字的Unicode编码是0x6C49。0x6C49在0×0800-0xFFFF之间，使用3字节模板了：1110xxxx 10xxxxxx 10xxxxxx。将0x6C49写成二进制是：0110 1100 0100 1001， 用这个比特流依次代替模板中的x，得到：11100110 10110001 10001001，即E6 B1 89。

例2：Unicode编码0x20C30在0×010000-0x10FFFF之间，使用用4字节模板了：11110xxx 10xxxxxx 10xxxxxx 10xxxxxx。将0x20C30写成21位二进制数字（不足21位就在前面补0）：0 0010 0000 1100 0011 0000，用这个比特流依次代替模板中的x，得到：11110000 10100000 10110000 10110000，即F0 A0 B0 B0。

UTF-16

UTF-16编码以16位无符号整数为单位。我们把Unicode编码记作U。编码规则如下：　　如果U<0×10000，U的UTF-16编码就是U对应的16位无符号整数（为书写简便，下文将16位无符号整数记作WORD）。中文范围 4E00-9FBF，所以在UTF-16编码里中文2个字节编码。如果U≥0×10000，我们先计算U’=U-0×10000，然后将U’写成二进制形式：yyyy yyyy yyxx xxxx xxxx，U的UTF-16编码（二进制）就是：110110yyyyyyyyyy 110111xxxxxxxxxx。

UTF-32

UTF-32编码以32位无符号整数为单位。Unicode的UTF-32编码就是其对应的32位无符号整数

字节序

根据字节序(对字节序不太了解的同学请参考http://en.wikipedia.org/wiki/Endianness)的不同，UTF-16可以被实现为UTF-16LE（Little Endian）或UTF-16BE（Big Endian），UTF-32可以被实现为UTF-32LE或UTF-32BE。例如：

Unicode编码	UTF-16LE	UTF-16BE	UTF-32LE	UTF-32BE
0x006C49	49 6C	6C 49	49 6C 00 00	00 00 6C 49
0x020C30	43 D8 30 DC	D8 43 DC 30	30 0C 02 00	00 02 0C 30

那么，怎么判断字节流的字节序呢？Unicode标准建议用BOM（Byte Order Mark）来区分字节序，即在传输字节流前，先传输被作为BOM的字符”零宽无中断空格”。这个字符的编码是FEFF，而反过来的FFFE（UTF-16）和FFFE0000（UTF-32）在Unicode中都是未定义的码位，不应该出现在实际传输中。下表是各种UTF编码的BOM：

UTF编码	Byte Order Mark
UTF-8	EF BB BF
UTF-16LE	FF FE
UTF-16BE	FE FF
UTF-32LE	FF FE 00 00
UTF-32BE	00 00 FE FF

总结一下，ISO与unicode.org都敏锐的意识到只有为世界上每种语言中的每个字符设定统一并且唯一的二进制编码才能彻底解决计算机世界信息交流中编码冲突的问题。由此诞生了UCS和unicode，而这两个规范是一致的。在Unicode里，所有的字符被一视同仁，也就是说，所有的文字都按一个字符来处理，它们都有一个唯一的Unicode码。UTF-8、UTF-16、UTF-32分别定义了怎样将Unicode定义的数字转换成程序数据。UTF-8以字节为单位对Unicode进行编码，一个英文字符占1个字节，汉字占3个字节；UTF-16以16位无符号整数为单位对Unicode进行编码，中文英文都占2个字节；UTF-32以32位无符号整数为单位对Unicode进行编码，中文英文都占4个字节。可以在http://www.unicode.org/charts/unihan.html 查看汉字的unicode码以及UTF-8、UTF-16、UTF-32编码。

中文二进制存储
介绍了这么多的编码知识，真正的文件内容是什么样子的呢？下面我们就通过实验看看在笔者Linux机器上 “中文”这两个字在不同的编码下保存的文件内容。下面是我的实验过程，有兴趣的同学可以在自己的机器上重做一下。window平台上的情况类似这里就不赘述了。

实验需要需要使用2个工具：

1. od 查看文件内容：http://www.gnu.org/software/coreutils/manual/html_node/od-invocation.html
2. iconv 编码转换工具：http://www.gnu.org/software/libiconv/

汉字	Unicode（ucs-2）10进制表示	Utf-8	Utf-16	Utf32	区位码	GB2312/GBK/GB18030
中	20013	E4 B8 AD	4E2D	00004E2D	5448	D6D0
文	25991	E6 96 87	6587	00006587	4636	CEC4

机器环境：
os: Red Hat Enterprise Linux AS release 4
Cpu: Intel(R) Xeon(R) CPU
locale：LC_ALL=zh_CN.utf-8

C语言中文处理
先明确一个概念：程序内部编码和程序外部编码。程序内部编码指的是中文字符在程序运行时在内存中的编码形式。程序外部编码则是中文字符在存储或者传输时的编码形式。程序外部编码的最直观的例子就是当把中文存储到硬盘文件中时选择的编码。

根据程序内部编码和程序外部编码是否一致，C/C++的中文处理有两种常见的方式：

1. 内外编码相同。输入输出时不需要考虑编码转换，程序内部处理时把中文字符当做普通的2进制数据流进行处理。
2. 内外编码不同。输入输出的时候根据应用需要选择合适的编码格式进行编码转换；程序内部统一编码处理。

方法1的优点不言而喻，由于内外统一，不需要进行转换。不足是如果不是C标准库支持的编码方式，那么字符串处理函数需要自己实现。比如说标准strlen函数不能计算中文编码&UTF-8等的字符串长度，而需要根据编码标准自行实现。GBK等中文编码除了计算字符串长度的函数外，字符串匹配函数也要自己实现（原因看上文中文编码总结）。当需要支持的编码格式不断增多时，处理函数的开发和维护就需要付出更大的代价。

方法2针对方法1的不足加以改进。在程序内部可以优先选择C标准库支持的编码方式，或者根据需要自己实现对某一特定编码格式的完整支持，这样任何编码都可以先转换为支持的编码，代码通用性比较好。

那么C标准库对中文编码的支持如何呢？目前Linux平台一般使用GNU C library，内建了对单字节的char和宽字符wchar_t的支持。Char大家都很熟悉了，处理中文需要的wchar_t要重点介绍一下。从实现上来说在linux平台上可以认为wchar_t是4byte的int，内部存储字符的UTF32编码。由于标准库已经内建了对wchar_t比较完备的支持，如使用wcslen 计算字符串长度，使用wcscmp进行字符串比较等等。所以比较简单的方式是使用上面的方法2，同时选择wchar_t作为内部字符的表示。做到这一点还是比较容易的，在输入输出的时候通过mbrtowc/wcrtomb 进行单个字符的内外编码转换，以及通过mbsrtowcs/wcsrtombs 进行字符串的内外编码转换即可。这里需要注意两点：

1. 代码中字符串常量的表示不同。举例说明：Char c=’a’; Wchar_t wc=L’中’;
2. 上面两组函数的转换是依赖locale设置的，即locale决定了外部编码的类型。确切的说是LC_CTYPE决定了外部编码的类型。默认情况下程序启动时使用标准“C”locale，而不是LC系列的环境变量指定的。所以需要首先调用下面的函数：setlocale (LC_ALL, “”);这样程序就使用了用户通过设置LC系列环境变量选择的Locale。

关于locale的话题比较大，这里就不深入了，留待下一篇文章吧.

上面的方法很完美，是吗？不是吗？得到这么多的好处不是无代价的，最明显的代价就是内存，任何一个字符，不管中文还是英文如果保持在wchar_t里就需要4个byte，就这一个理由就足以限制了这个方案在关注内存使用的应用场景下的使用。

Python的中文处理
对Python来说由于内建unicde的支持，所以采用输入输出的时候进行转换，内部保持unicode的方式使用是个不错的方案。http://docs.python.org/tutorial/introduction.html#unicode-strings这里作为起点，有兴趣的同学自学吧。

编码选择建议：

1. 只有英文：毫不犹豫选择内外编码都选择ASCII，通用且存储代价小。
2. 主要存中文，对存储大小比较敏感：内外部编码根据文字使用范围选择GB2312或者GBK，自行实现使用到的字符串处理函数。
3. 通用性第一，处理简单：外部选择UTF-8，内部可以使用UTF-8或者UTF-32（即wchar_t）

君，当如竹，坚韧挺拔显气概。

平移

平移就是将一个对象或一个点从一个地方移动到另一个地方。设点(x, y)，将其平移一定距离(dx, dy)，移动到新位置(xt, yt)，则其计算过程：

• xt = x + dx;
• yt = y + dy;

平移整个对象时，如果你有对象中心的坐标，而且所有点有对应中心的相对坐标，那么只需要对对象的中心应用平移变换即可。如果对象没有自己的坐标，那么你就必须对组成整个多边形的所有点运用公式。

本地坐标和世界坐标：通常在2D或3D计算机图像里，你至少需要给所有对象确定本地坐标和世界坐标。一个对象的本地坐标是相对于 (0, 0) 或 (0, 0, 0)，然后给每个本地坐标位置加上世界坐标方位(x0, y0) 或 (x0, y0, z0)，就可以找到对象的世界坐标位置。实际上，也就是通过把每个本地坐标转换，来重新放置对象。

旋转

三角函数：

常用公式：

• 毕达哥拉斯定理：sinΘ² + cosΘ² = 1
• 变换恒等式：sinΘ = cos(Θ - Π/2)
• 负角公式：sin(-Θ) = - sinΘ, cos(-Θ) = cosΘ
• 和差化积公式：sin(α + β) = sinα * cosβ + cosα * sinβ, cos(α + β) = cosα * cosβ - sinα * sinβ, sin (α - β)  = sinα * cosβ  -  cosα * sinβ, cos(α - β)  = cosα * cosβ + sinα * sinβ

绕点旋转公式的推导：

设点 p1(x1, y1) 绕点 p0(x0, y0) 逆时针旋转 α 度之后为 p2(x2, y2)，那么在p0(x0, y0) 建立一个直角坐标系，设 p0p1 线段成为 r，与 x 轴夹角为 Θ，那么可以得出以下等式：

• x1 = r * cos Θ, y1 = r * sinΘ
• x2 = r * cos(Θ + α), y2 = r * sin(Θ + α)

将2 式使用和差化积转换为：
x2 = r * cosΘ * cosα - r * sinΘ * sinα
y2 = r * sinΘ * cosα + r * cosΘ * sinα

将1式代入，得：
x2 = x1 * cosα - y1 * sinα
y2 = x1 * sinα + y1 * cosα

由于之前有过平移，平移因子(x0, y0)，故：
x2 - x0 = (x1 - x0) * cosα - (y1 - y0) * sinα 即：x2 = (x1 - x0) * cosα - (y1 - y0) * sinα + x0
y2 - y0 = (x1 - x0) * sinα + (y1 - y0) * cosα即：y2 = (x1 - x0) * sinα + (y1 - y0) * cosα + y0

缩放

缩放几乎和平移一样，要将对象进行缩放，只需要将每个坐标都乘以缩放因子即可。当然，你可以在不同的轴上的数值采用不同比例的缩放。

寻找本身就是一种幸福。

Cohen-Sutherland 算法是一种很有效的裁剪算法，其整体思想是：每一条线或整体的位于窗口的内部，或者能够被分割而使其中的一部分很快的被删去。

Cohen-Sutherland 算法将平面划分成9个区域，每个区域分配一个4位的代码，代码是根据裁剪矩形的边定义的外半平面和各区域的相对关系来决定的。

简记：“1上2下，3左4右”，（位是从左至右）。

这样的划分，可以得到一个简单的计算外码的方式：各位的值可分别根据(y_max - y), (y - _min), (x_max - x), (x - x_min)的符号决定，然后线段的每个端点可以根据它所在的区域被赋予该区域的代码。

《计算机图形学导论》上介绍的算法，是这样的：

• 从上到下，从左至右去检测哪条边会与这条线相交。外码的特点是非零位对应于这条线会相交的边。
• 计算线段的两个端点的外码，并检测它们是否能简单接受或拒绝。
• 如果不能，选择一个在外面的点，然后找出会与该线相交的边，求出交点。
• 去掉外面点到交点的这一段，并将交点作为裁剪后的线段的一个新的端点。
• 计算新的端点的外码，并进行下一次检测。

《Windows 游戏编程大师技巧》里面介绍的算法本质上是一样的，只是根据实际情况：比如线段ED，HD这一部分肯定只与裁剪矩形的一条边延长线相交，那么按照从上到下，从左到右的步骤，分别裁剪掉FD，再裁剪掉HF。这样就不用循环了，其实本质还是一样的。

如下裁剪Demo：

由于检测和裁剪是按照一个固定的次序运行的，所以该算法有时会做一些不必要的裁剪。

孤单是一个人的狂欢，狂欢是一群人的孤单。

圆的八方向对称性，使得我们只需要计算0 - 45度之间的一段圆弧，就能得到整个圆。

基础算法

根据圆的方程：x² + y² = R²。可表示为：y = 正负根号下 (R² - x²)。我们可以将 x 一个单位一个单位地从 0 递增到 R ，并求出每一步的 +y 值，但是当 x 靠近 R 时，圆会有很大间隔。另一种效率差不多的算法，是将 θ 从 0 增长到 90，并画出点 (Rcosθ, Rsinθ)，可以避免出现较大的间隔，但效率差不多。

中点圆算法

考虑角度为45度的一段圆弧，即从x = 0 到 x = y = R / √2 。与中点算法类似，这里所给出的方法是在 2 个像素的中点处给一个评估函数值，并据此在 2 个像素之间选择更靠近圆的那个像素。

设函数F(x, y) = x² + y² - R²。对圆上的点，此函数值是0；对于圆内的点，函数值是正的；对于圆外的点，函数值是负的。

和画线类似，我们选择像素是根据判定变量 d 的值，即函数F(x, y)在中点处的值：d_old = F(x_p+1, y_p - 1/2) = (x_p + 1)² + (y_p - 1/2)² - R²。如果 d_old < 0，就选择像素 P1，并将当前中点d的x坐标增加一个单位，以得到下一个中点：d_new = F(x_p+2, y_p - 1/2) = (x_p + 2)² + (y_p - 1/2)² - R²。

d_new = d_old + (2 x_p + 3)，因此ΔP1 = 2 x_p + 3。同理可推导出ΔP2 = 2 x_p - 2y_p + 5。

计算初始值：限定该算法处理的圆半径是整数，并只画第二个八分圆弧，因此，圆的像素起始像素点是(0, R)，下一个中点位置是 (1, R - 1/2)，因此F(1, R - 1/2)  = 1 + (R² - R + 1/4) - R² = 5/4 - R。于是判定变量 d = 5/4 - R，那么  d < 0时选择 P1，否则选择P2。为了避免小数的出现，定义新的判定变量 h = d - 1/4，这样d < 0 变成了比较 h < -1/4。由于 h 是一个整数，增量（ΔP1 和 ΔP2）也是整数，所以可将比较改为h < 0，于是得到整数型算法：

[c]
void MidCircle(int r, int color)
{
int x, y, d;
x = 0;
y = r;
d = 1 - r;
CirclePoints(x, y, color);
while (y > x) {
if (d < 0) {
d += x * 2 + 3;
x++;
}
else {
d += (x - y) * 2;
x++;
y--;
}
CirclePoints(x, y, color);
}
}
[/c]

二阶差分
Δ函数是线性方程，可以直接计算，然而任意一个多项式都可以按增量的方式计算，如同我们处理线和圆的判定变量一样，事实上我们是在计算一阶和二阶的偏差分，其基本思想是计算函数在其两个临近点的值，以及这两个值的差分值（对于多项式而言，常常是一个低次多项式的值），并且在程序的每一次迭代中运用这个差分值。

题外话：小时候，我做个这种事情，就是将一列数（比如 x²）进行相减，计算出了差值序列，看有无什么规律，没规律再将得到的差值序列再相减……，那个时候幻想自己发现什么定律，成为数学家，后来才知道这叫差分。

在前面的迭代中，我们选择p1，那么估值点从 (x_p, y_p)  变化到 (x_p + 1, y_p)，显然在点 (x_p, y_p) 处的一阶差分ΔP_1old = 2x_p + 3，因此点 (x_p+1, y_p) 处的一阶差分ΔP_1new = 2(x_p + 1) + 3，因此其二阶差分是ΔP_1new - ΔP_1old = 2。类似地，在点(x_p, y_p)处的ΔP_2old = 2x_p - 2y_p + 5。在点 (x_p+1, y_p)处的ΔP_2new = 2x(_p + 1) - 2y_p + 5，从而二阶差分ΔP_2new - ΔP_2old = 2。

同理可计算选择p2后，估值点从 (x_p, y_p) 变化到 (x_p + 1, y_p - 1)，因此在点(x_p + 1, y_p - 1) 处ΔP_1new = 2x(_p + 1) + 3，而二阶差分是ΔP_1new - ΔP_1old = 2。类似地，在点(x_p + 1, y_p - 1)处的ΔP_2new = 2(x_p + 1) - 2(y_p - 1) + 5 ，相应的二阶差分是ΔP_2new - ΔP_2old = 4。

这里可能会有这样的疑问，为什么选择了p1后，我们还需要计算ΔP_2new ，进而计算其二阶差分ΔP_2new - ΔP_2old 。类似的，为什么选择p2后，还需要计算ΔP_1new - ΔP_1old ？

可以这样理解，对比圆的整数中点算法，可知，每次 d 都会加上一个线性函数（ΔP1 或 ΔP2），当我们采用二阶差分算法时，d 的增量，是加上这个线性函数在邻近两点的差值（相当于间接计算了线性函数），这样我们必须在选择了p1后，还需要计算ΔP_2new ，是为了以后若选p2这样的圆内点的时候，其线性函数的值是正确的！

[c title="以deltaE、deltaSE 代表 P1、P2处的二阶差分"]
void MidCircle(int r, int color)
{
int x, y, d, deltaE, deltaSE;
x = 0;
y = r;
d = 1 - r;
deltaE = 3; // 2 * xp + 3 = 3
deltaSE = 5 - 2 * r; // 2 * xp - 2 * yp + 5 = 5 - 2r
CirclePoints(x, y, color);
while (y > x) {
if (d < 0) {
d += deltaE;
deltaE += 2;
deltaSE += 2;
x++;
}
else {
d += deltaSE;
deltaE += 2;
deltaSE += 4;
x++;
y++;
}
CirclePoints(x, y, color);
}
}
[/c]
画圆效果图：见中点圆算法Demo

一艺之成，当尽毕生之力。

之前的 直线DDA算法 的缺点在于，对y值取整需要时间，而且斜率是一个小数，y 和 k 须是实数或者二进制小数。另外，实数的精度有限，且不精确的 k 重复叠加会产生累积误差。当然，我在实现中由于采取了直接计算该点在 video buffer 中的位置，所以每次描点都有一次乘法运算，可以通过采取相对计算来消除乘法。

Bresenham 算法思想：

假设我们已经选着像素p，那么下一步要选择的像素可能是右边的 E 像素，也可能是右上的 NE 像素，设 Q 为直线与栅格线的交点，那么我们可以计算 E 和 NE 到 Q 的垂直距离，选择离 Q 近的点。

对 Bresenham 算法的描述主要是对其误差判别式的推导，不同的资料有不同推导形式：

《计算机图形学导论》上的推导过程如下：

设直线方程 F(x, y) = ax + by + c = 0，dy = y₁ - y_0，dx = x₁ - x_0，则其斜截式可以写成：y = dy / dx × x + B，因此：F(x, y) = dy • x+ dx • y + B • dx= 0，其中 a = dy，b = -dx，c = B • dx。

容易证明，对于线上面的点，F(x, y) 等于 0；对于线下方的点， F(x, y)是正数；对于线上方的点，F(x, y)是负数。运用中点法则，我们只需要计算F(M) = F(x_p+1, y_p+1/2)，并考察它是正数还是负数。

定义判定变量 d = F(x_p+1, y_p+1/2)。那么d = a (x_p + 1) + b( y_p+1/2 ) + c。对于d >0 和 d < 0，分别选择 NE 和 E。d = 0时，两者都可选，约定选择 E 。

当栅格线移动到下一条时，如果我们选择 E ，M点就在x方向递增一步，那么：d_new = F(x_p+2, y_p+1/2) = a (x_p + 2) + b( y_p+1/2 ) + c，又因为 d_old = a (x_p + 1) + b( y_p+1/2 ) + c，从而 d_new = d_old + a。

将选择 E 后的增量称为 ΔE = a = dy。 同理可推，选择 NE 后 ΔNE = a + b = dy - dx。

基于上面的讨论，增量的中点技术可以概括为：在每一步，我们可根据上一步所得的判定变量值的符号去选择下一个像素；然后根据所选像素，用ΔE 或ΔNE 去递增判定变量的值。

计算判定变量的初始值：第一个像素就是第一个端点，那么第一个中点坐标是(x₀+1, y₀+1/2)，因此：F(x₀+1, y₀+1/2) = a (x₀ + 1) + b( y₀+1/2 ) + c = F(x₀, y₀) + a + b/2。由于(x₀, y₀)是线上的点，所以F(x₀, y₀) = 0。因此：d_start = a + b/2 = d_y - d_x/2。我们对其两边乘2，新的初始值 d_start = 2dy - dx，且不影响中点检测效果，因为未改变 d_start 的符号。

《计算机图形学导论》所给出的 Bresenham 算法描述 和 《Windows 游戏编程大师技巧》中所给出的Bresenham算法描述，是等价的。只不过后者扩充到了其他象限。

上海交大图形学网的 Bresenham算法 用图形化的方式形象表现了改算法，对初始值的设定：初值Error =∆y/∆x-0.5，可以通过图像观察得出来的，我在这里纠结了好一会。

伪代码描述：
[c]
//Bresenham's integer line resterization algorithm for the first octal.
//The line end points are (xs,ys) and (xe,ye) assumed not equal.
//All variables are assumed integer.
//initialize variables
x=xs
y=ys
∆x = xe -xs
∆y = ye -ys
//initialize e to compensate for a nonzero intercept
NError =2*∆y-∆x //Error =∆y/∆x-0.5
//begin the main loop
for i=1 to ∆x
WritePixel (x, y)
if (NError >=0) then
y=y+1
NError = NError –2*∆x //Error = Error -1
end if
x=x+1
NError = NError +2*∆y //Error = Error +∆y/∆x
next i
finish
[/c]
这里的 Error = Error -1 同样可以根据图像得出。

如果说《计算图形学导论》对 Bresenham 算法描述是根据选择的方向的不一样，得出下一个光删点与前一个光栅点的判定变量的增量，上海交大图形学网则是根据图形的方式得出其 Error 值，那么下面一个版本的描述则是根据 QE 与 QNE 距离差来推导的，见：算法描述一。

我推导了一下，虽然比上两个算法描述麻烦点，却也得出了同样的判别式。

下面是用Bresenham算法 和 DDA算法画的一个圆（左半圆 DDA，右半圆 Bresenham）。

代码见：Bresenham算法