《图形程序开发人员指南》求取 ⇩

第1章 大脑是最好的优化器1

1．1 代码优化中人的因素1

1．2 何谓高性能1

1．3 编写高性能代码的原则2

1．3．1 明确目的2

1．3．2 制定总体规划3

1．3．3 制定大量的小规划3

1．3．4 明确布局7

1．3．5 知道重要部分8

1．3．6 考虑多种方法9

1．3．7 知道应付意义11

1．4 小结14

第2章 汇编优化15

2．1 汇编语言最优化的独特性15

2．2 指令：个别与整体15

2．3 汇编的特征16

2．3．1 低效转化16

2．3．2 独立性17

2．3．3 学无止境18

2．4 开动脑筋18

第3章 综计时器20

3．1 掌握和使用综计时20

3．2 粗心的代价20

3．3 综计时器21

3．3．1 综计时器是一种手段不是目标30

3．3．2 综计时器的开始30

3．4 计时与PC机31

3．5 停止综计时器33

3．6 报告计时结果33

3．7 关于综计时器的几点说明34

3．8 综计时器使用举例35

3．9 长周期综计时器36

3．10 长周期综计时器的使用举例54

3．11 在C中使用综计时器58

3．12 仔细优化汇编程序60

3．13 综计时器是一种好的工具61

第4章 时钟周期耗费的本质62

4．1 PC硬件如何影响代码性能62

4．2 时钟周期耗费的因素62

4．3 时钟周期耗费的特点63

4．4 8位数据总线时钟周期耗费64

4．4．1 8位数据总线的限制65

4．4．2 如何克服8位总线时钟周期耗费66

4．5 指令预取队列时钟周期耗费68

4．5．1 不要相信技术手册上的执行时间69

4．5．2 指令执行时间是不定的70

4．5．3 估计全面执行时间74

4．5．4 如何克服指令队列的时钟周期耗费74

4．5．5 继续讨论808875

4．6 DRAM刷新75

4．6．1 PC中DRAM刷新的方式76

4．6．2 DRAM刷新的影响77

4．6．3 如何克服DRAM刷新的时钟周期耗费78

4．7 等待状态79

4．8 显示适配器时钟周期耗费80

4．8．1 显示适配器时钟周期耗费的影响82

4．8．2 如何克服显示适配器时钟周期耗费85

4．8．3 时钟周期耗费总结86

4．8．4 结束语86

第5章 使用可重用块进行优化87

5．1 使用可重用块搜索文件87

5．3 采取强制技术88

5．2 避开字符串88

5．4 使用memchr（）89

5．5 明确重点94

5．6 跟踪执行95

第6章 透过表面价值96

6．1 机器指令无所不能96

6．2 通过内存寻址进行数学运算98

6．3 使用LEA指令倍乘，无需使用2的幂次运算100

第7章 局部优化101

7．1 介于算法一级和时钟周期计算一级的优化101

7．3 LOOP指令与JCXZ指令的教训102

7．2 不需要LOOP102

7．4 局部优化103

7．5 展开循环105

7．5．1 使用表进行循环移位和偏移109

7．5．2 关于NOT指令110

7．5．3 带/不带进位标志增加110

第8章 使用汇编语言加速C程序112

8．1 如果有助于加快速度，不妨换一种语言112

8．4 多段处理问题113

8．2 尽量不在汇编中使用函数调用113

8．3 栈帧（Stack frame）速度太慢113

8．5 使速度到达极致115

第9章 读者使我成功128

9．1 从另一个角度看LEA指令128

9．2 Kennedy的工作129

9．3 加速乘法操作131

9．4 不断优化搜索代码131

9．5 快速排序138

9．6 全32位除法139

9．7 重新讨论最佳位置（Sweet Spot）142

9．8 核心时钟周期计算143

9．9 硬件相关的远程跳转144

9．10 设置32位寄存器，时间因素和空间因素的权衡145

第10章 耐心编码，使速度更快146

10．1 草率编码导致性能低下146

10．2 笨拙的直接求解方法147

10．3 递归152

第11章 286和386的研究157

11．1 新的寄存器、新的指令、新的速度、新的复杂度157

11．2 我们熟悉的Intel处理器157

11．3 286和386的保护模式158

11．4 时钟周期耗费的本质——讨论之二158

11．4．1 系统等待状态159

11．4．2 数据对齐161

11．5 代码对齐163

11．5．2 对齐方式和栈165

11．5．1 386上的对齐方式165

11．5．3 DRAM刷新的时钟周期耗费——不可改变166

11．5．4 显示适配器的时钟周期耗费166

11．6 286的新指令和新特性167

11．7 386的新指令和新特性168

11．7．1 286和386的优化规则讨论之一169

11．7．2 286和386的优化规则讨论之二169

11．8 286的POPE指令171

12．1 486不仅仅是个快速的386176

第12章 486的研究之一176

12．2 优化的规则177

12．2．1 变址寻址的弊端177

12．2．2 提前计算指针178

12．3 给程序员的告诫180

12．3．1 栈寻址以及地址流水线181

12．3．2 使用字节寄存器的问题之一182

12．3．3 使用字节寄存器的问题之二183

12．3．4 计算486程序运行的时间184

12．4 补充说明185

第13章 486的研究之二186

13．1 流水线及损耗186

13．2 BSWAP比读者想象的更有用188

13．3 存储器数据的压栈和弹栈190

13．4 最佳的1位平移和循环移位191

13．5 32位寻址模式192

第14章 Boyer-Moore串搜索方法194

14．1 一个最佳搜索算法的实现194

14．2 串搜索回顾194

14．3 Boyer-Moore算法195

14．4 Boyer-Moore算法的优缺点198

14．5 Boyer-Moore算法的进一步优化206

第15章 链表211

15．1 链表前言211

15．2 链表212

15．3 哑元和标记214

15．4 循环链表216

15．5 24个字节编程221

16．2 快速统计单词数223

第16章 代码的优化永无止境223

16．1 结果比手段重要223

16．3 挑战和冒险232

16．3．1 选择最好的算法232

16．3．2 不要想当然233

16．4 巧妙优化的奇迹233

16．5 优化的级别238

16．6 二级优化：新视角241

16．6．1 三级优化：突破242

16．6．2 小结245

第17章 游戏Life的优化246

17．1 算法优化246

17．2 Conway的游戏246

17．3 运行时间分布252

17．4 抽象的优缺点253

17．5 C++优化的重要性259

17．6 创造性思维262

17．6．1 再次分析任务262

17．6．2 相邻单元记录方法的实现263

17．6．3 一生的挑战270

第18章 奇妙的Life271

18．1 优化的限制条件271

18．2 打破限制条件271

18．3 神奇的驱动表272

18．4 使用变化表跟踪变化287

18．5 外行对QLIFE的看法289

第19章 Pentium291

19．1 优化的历史291

19．2 优化作为艺术的回归291

19．3 Pentium综述292

19．3．1 跨越cache块取指292

32．2 扩展的256色模式293

19．3．2 cache的组织方式293

19．4 更快地寻址294

19．5 分枝预测295

19．6 Pentium的各种特点296

19．6．1 比较486与Pentium的优化296

19．6．2 超标量297

20．2 流水线并行298

第20章Pentium优化规则298

20．1 在超标量体系结构中的优化298

20．3 V流水线能执行的指令300

20．4 执行的一致性303

20．5 超标量的注意事项307

第21章 充分利用V流水线309

21．1 充分利用两条流水线309

21．2 地址相关（AGI）309

21．3 寄存器冲突312

21．4 确定指令运行所在的流水线313

21．5 在运行中优化314

第22章 综级优化321

22．1 简要回顾321

22．2 综级优化321

23．2 VGA327

第23章 VGA的硬件结构和特性327

23．1 标准PC图形的重点327

23．3 介绍VGA编程328

23．4 VGA内核328

23．4．1 线性位面和真VGA模式330

23．4．2 平滑绘制343

23．4．3 颜色位面操作345

23．4．4 页面翻转346

23．5 VGA的不兼容性348

23．6 一切还刚刚开始348

23．7 关于宏汇编348

24．1 一次从图形存储器中取出4个字节349

24．2 VGA的编程；运用ALU和锁存器349

第24章 使用VGA进行并行处理349

24．3 ALU/锁存器演示程序注意事项356

第25章 VGA中的数据控制部件359

25．1 桶形移位器、位屏蔽和设置/复位部件359

25．2 VGA的数据循环移位359

25．3 位屏蔽部件360

25．4 VGA的设置/复位电路367

25．4．1 设置所有位面以形成一种颜色370

25．4．2 各位面独立操作373

25．5 设置/复位部件注意事项375

25．6 双字节OUT指令注意事项376

26．1 关于写模式3377

26．2 陌生的写模式3377

第26章 VGA的写模式3377

26．3 保存寄存器位的注意事项393

第27章 VGA的写模式2394

27．1 写模式2，大位图块以及文本一图形共存394

27．2 写模式2和设置/复位部件394

27．2．1 写模式2处理举例394

27．2．2 写模式2拷贝大位图块396

27．2．3 写模式2绘制基于颜色模板的线条402

27．3 写模式2和设置/复位部件的权衡409

27．4 VGA模式13H简介409

27．5 文本模式/图形模式切换410

28．2 读模式0416

28．1 读模式简介416

第28章 读VGA显存416

28．3 读模式1422

28．4 读模式1特殊情况426

第29章 屏幕保存和其他VGA内幕431

29．1 VGA操作综述431

29．2 保存和恢复431

29．3 从64种颜色中选取16种颜色439

29．4 越界颜色446

29．5 一个好的清屏器447

29．6 修改VGA寄存器449

第30章 拆分屏幕451

30．1 拆分屏幕简介451

30．2 拆分屏幕的工作原理451

30．2．1 拆分屏幕的实现452

30．2．2 不要混淆两种拆分屏幕操作461

30．3 设置相关寄存器461

30．4 EGA拆分屏幕的问题462

30．5 拆分屏幕和绘制462

30．6 设置/读出寄存器注意事项472

30．7 其他模式的拆分屏幕474

30．8 拆分屏幕的安全性474

第31章 VGA更高的256色分辨率475

31．1 到底是320×200还是320×400？475

31．2 为什么是320×200？475

31．3 320×400的256色模式476

31．3．1 320×400模式中显存结构476

31．3．2 像素读、写478

31．4 两个256色页面486

31．5 其他的思考492

32．1 使256色模式和标准VGA模式一样快493

第32章 360×480 256色模式493

32．3 360×480 256色模式494

32．4 360×480 256色模式工作原理504

32．4．1 每屏480个扫描行504

32．4．2 每个扫描行360个像素504

32．4．3 在360×480 256色模式中访问显存505

33．2 VGA颜色产生原理507

第33章 调色板RAM及DAC寄存器507

33．1 VGA颜色产生的基础507

33．2．1 调色板RAM508

33．2．2 DAC509

33．2．3 颜色选择寄存器的颜色页面调度509

33．2．4 256色模式510

33．2．5 设置调色板RAM510

33．2．6 DAC设置511

33．3 不能调用BIOS时的处理511

33．4 举例说明DAC的设置512

第34章 不通过写像素改变颜色518

34．1 实时操作DAC颜色的特殊效果518

34．2 颜色循环518

34．3 核心问题519

34．3．1 通过BIOS装载DAC519

34．3．2 直接装载DAC520

34．4 颜色循环的测试程序521

34．5 有效的颜色循环方法528

34．6 补充说明529

34．6．1 DAC屏蔽529

34．6．2 读DAC529

34．6．3 结束语530

第35章 Bresenham线段绘制算法531

35．1 Bresenham线段绘制算法的实现与优化531

35．2 关于线段绘制531

35．3 Bresenham的线段绘制算法532

35．4 使用C语言实现535

35．4．1 分析EVGALine函数541

35．4．2 绘制每一条线段543

35．4．3 绘制每一个像素543

35．5 C语言实现程序的讨论544

35．6 汇编语言实现的Bresenham算法545

第36章Bresenham步距长度片算法554

36．1 采用步距长度片方法的快速Bresenham算法554

36．2 步距长度片原理555

36．3 步距长度片的实现557

36．4 步距长度片的详细讨论558

第37章 步距长度片绘制算法的优化567

37．1 对步距长度片绘制算法的大力优化567

37．2 快速步距长度片方法567

37．2．1 步距长度片方法的速度575

37．2．2 进一步的优化576

38．1 高效快速地绘制多边形577

38．2 填充的多边形577

第38章 多边形原操作577

38．3如何拼接多边形579

38．4 填充不重叠的凸多边形580

第39章 快速的凸多边形填充算法580

38．5 其它589

39．1 多边形的快速填充590

39．2 快速凸多边形填充591

39．2．1 快速绘制592

39．2．2 快速边扫描594

39．3 最后的方法：汇编语言597

39．4 更快的边扫描方法600

第40章 复杂多边形的简化605

40．1 处理不规则的多边形区域605

40．2 填充任意的多边形605

40．3 复杂多边形填充的实现614

40．3．1 关于活跃边的再讨论618

40．3．2 关于性能的讨论618

40．4 非凸多边形620

第41章 多边形命名的重要性622

41．1 把一个数据结构概念化时名称很重要622

41．2 术语的使用622

第42章 Wu的反走样算法636

42．1 使用Wu的算法的反走样线快速绘制636

42．2 Wu的反走样算法636

42．3 绘制以及亮度和为1638

42．4 Wu反走样算法的样本641

43．1 有限颜色的简单和快速动画方法655

第43章 位面动画655

43．2 基本概念——位面656

43．3 位面动画的实现659

43．4 位面动画的局限671

43．5 剪切和页面翻转673

43．6 关于PC上的动画673

44．2 计算机动画的几个问题675

44．3 一个页面翻转动画演示675

44．1 页面翻转的局限675

第44章 使用拆分屏幕的页面翻转675

44．3．1 写模式3689

44．3．2 文本绘制691

44．3．3 页面翻转691

44．4 引入拆分屏幕693

第45章 “脏矩形”动画695

45．1 小狗Sam的故事695

45．2 狗的启迪695

45．3 VGA访问696

45．4 “脏矩形”动画697

45．5 “脏矩形”动画的实现699

45．6 高分辨率的VGA页面翻转705

45．7 页面翻转的另一改进709

第46章 使用屏蔽图像的“脏矩形”动画711

46．1 优化“脏矩形”动画711

46．2 “脏矩形”动画探讨之二711

46．3 屏蔽图像723

46．4 内部的动画723

46．5 绘制顺序和显示质量724

47．2 模式X的特性725

第47章 模式X：神奇的256色VGA模式725

47．1 VGA松布的“动画优化”模式介绍725

47．3 选择320×240 256色模式726

47．4 从模式X的角度进行设计733

47．5 硬件加速738

第48章 模式X对锁存器的使用743

48．1 动画的最好视频显示模式743

48．2 模式X中的显存分配749

48．3 在显存中拷贝像素块751

48．4 小结758

49．1 如何充分发挥VGA的性能759

49．2 屏蔽拷贝759

第49章 模式X的256色动画759

49．2．1 快速屏蔽拷贝762

49．2．2 注意事项769

49．3 动画769

49．4 模式X动画的实现769

49．5 模式X印象776

50．1 使用模式X的3D动画778

第50章 三维动画778

50．2 3D绘制的参考文献779

50．3 3D绘制流水线779

50．3．1 投影781

50．3．2 平移781

50．3．3 旋转781

50．4 3D编程举例783

50．5 小结794

51．2 有一个可见面的多边形795

第51章 背面删除方法795

51．1 使用背面删除方法消去不可见面795

51．3 递增变换805

51．4 对象表示808

第52章 快速3D动画：使用X-Sharp810

52．1 一个通用的3D动画软件包810

52．2 本章的演示程序810

52．3 一个新的动画框架：X- Sharp826

52．4 实时动画的三个关键之处826

52．4．1 缺点827

52．4．2 运行时间分配828

第53章 最高速度及其它829

53．1 提高3D动画速度的真理829

53．2 最高速度第一部分：汇编语言829

53．3 最高速度第二部分：查找表837

53．3．1 不可见面838

53．3．2 舍入841

53．4 球的3D动画841

54．2 对以前处理器的支持842

第54章 3D浓淡处理842

54．1 使3D动画对象具有真实表面842

54．3 浓淡861

54．3．1 环境浓淡862

54．3．2 漫反射浓淡862

54．4 浓淡的实现865

第55章 256色模式中的颜色表示868

55．1 用RGB模式表示X- Sharp中的颜色868

55．2 颜色模型868

55．3 从Bit Man那里得到收益873

第56章 纹理映射880

56．1 使用快速纹理映射880

56．2 快速的脏纹理映射原理881

56．2．1 使纹理映射更容易881

56．2．2 DDA纹理映射注意事项883

56．3 快速纹理映射方法的实现884

57．2 视觉效果892

57．1实现快速、光滑纹理映射的经验规则892

第57章 多边形纹理映射的优化892

57．3 定点算法的缺陷893

57．4 纹理映射，与方向无关894

57．5 把纹理映射到多边形896

第58章 纹理映射的优化905

58．1 使用最佳方法优化纹理映射905

58．2 纹理映射的缺陷906

58．2．1 固定思维的优化906

58．2．2 完全不同的角度908

58．3 最终的优化910

58．4 关于纹理映射的几点说明916

第59章 BSP树918

59．1 BSP树的概念918

59．2 BSP树919

59．2．1 可见性判别919

59．2．2 BSP树的局限920

59．3 建立BSP树921

59．4 BSP树的顺序遍历925

59．4．1 完全了解927

59．4．2 测量与学习929

59．5 BSP树参考资料931

第60章 编译BSP树933

60．1 BSP树的实现933

60．2 编译BSP树934

60．2．1 参数线段934

60．2．3 BSP编译器936

60．2．2 参数线段裁剪936

60．3 优化BSP树943

60．4 有待研究的BSP优化944

第61章 参照物945

61．1 3D图形的数学基础945

61．1．1 3D数学945

61．1．2 基本定义946

61．2 点积946

61．3 叉积和多边形法向量948

61．4 利用点积的符号950

61．5 点积用于投影951

第62章BSP绘制算法954

62．1 优化被编译的BSP树954

62．2 基于BSP的绘制955

62．3 绘制流水线965

62．3．1 观察者移动965

62．3．2 变换到视空间966

62．3．3 裁剪966

62．3．4 投影到屏幕空间967

62．3．5 遍历、背面删除及绘制968

62．4 关于BSP绘制程序的几点说明969

第63章 实时3D处理的浮点操作970

63．1 紧急事件的处理970

63．2 浮点操作的新概念971

63．3 Pentium的FP优化971

63．4 FXCH指令973

63．5 点积优化974

63．6 叉积优化975

63．7 变换优化976

63．9 舍入控制978

63．8 投影优化978

63．10 不再使用3D定点979

第64章 Quake的可视表面判别980

64．1 可见性判别980

64．2 VSD：最难的三维问题981

64．3 Quake级的结构981

64．4 背面删除和可视表面判别982

64．5 重复绘制983

64．6 beam树984

64．7．1 光线投射子划分985

64．7 三维引擎985

64．7．2 不需要顶点的表面986

64．7．3 绘制缓存986

64．7．4 基于段的绘制986

64．7．5 孔洞986

64．8 突破986

64．9 简化并不断尝试新事物987

64．11 参考书988

64．10 学以致用988

第65章 3D裁剪989

65．1 信息交流989

65．2 3D裁剪的基础990

65．3 多边形裁剪992

65．3．1 裁剪到视体内995

65．3．2 程序65-3的技巧1001

65．4 视空间裁剪的优点1002

65．5 进一步学习1003

第66章Quake中面的消隐1004

66．1 不可见面的Z序消隐1004

66．2 创造性的变化和不可见表面1004

66．2．1 绘制运动对象1004

66．2．2 性能影响1005

66．2．3 改进与均衡性能1005

66．3 跨度排序1006

66．4 边排序关键值1010

66．4．2 Quake和Z排序1011

66．4．1 1/z方程的推导1011

66．5 排序方法的取舍1012

第67章 实现跨度排列1013

67．1 实现独立的跨度排序1013

67．2 Quake和跨度排序1013

67．3 按1/z进行跨度排序的类型1015

67．3．1 相交跨度排序1015

67．3．2 邻接跨度排序1015

67．3．3 独立跨度排序1016

67．4 1/z跨度排序的实现1017

第68章Quake的光照模型1029

68．1 做感兴趣的事1029

68．2 光照难题1029

68．3Gouraud浓淡方法1030

68．3．1 Gouraud浓淡方法的问题1030

68．3．2 透视校正1031

68．4 寻求其他光照方法1032

68．4．1 分离光照和光栅化1033

68．4．2 尺寸和速度1034

68．5 表面cache1035

68．5．1 均值映射(Mipmapping)1035

68．5．2 关于表面cache的最后两点说明1036

第69章 表面cache和 Quake的三角形模型1037

69．1 保持理智1037

69．2 与硬件相关的表面cache1038

69．2．1 使用图形卡构造纹理1038

69．3．1 快速绘制三角形模型1039

69．3 绘制三角形模型1039

69．2．2 作为Alpha纹理的光照图1039

69．3．2 子像素的精度换取速度1041

69．3．3 一种无效的方法1041

69．3．4 一种有效的方法1042

69．3．5 其他可能有效的方法1046

第70章 Quake: 回顾和展望1047

70．1 预处理基本空间1048

70．2 可能可见集（PVS）1049

70．4 绘制基本空间1050

70．3 几乎发生的改变1050

70．5．1 光照1052

70．5．2 动态光照1052

70．5 光栅化1052

70．6 实体1053

70．6．1 BSP模型1053

70．6．2 多边形模型和Z-buffer1054

70．6．3 再分割光栅化程序1055

70．6．4 特殊效果1055

70．7．1 Verite Quake1056

70．6．5 粒子1056

70．7 Quake推入市场后我们的计划1056

70．7．2 GL Quake1057

70．7．3 WinQuake1058

70．7．4 QuakeWorld1058

70．7．5 Quake 21060

70．8 展望1061

著后语1063