按键盘上方向键 ← 或 → 可快速上下翻页，按键盘上的 Enter 键可回到本书目录页，按键盘上方向键 ↑ 可回到本页顶部！
————未阅读完？加入书签已便下次继续阅读！
是一种数据结构。算法是指对数据结构施加的一些操作，例如对一个线性表进行检索、插入、删除等操作。一个算法如果能在所要求的资源限制（Resource Constraints）范围内将问题解决好，则称这个算法是有效率（Efficient）的。例如一个资源限制可能是“用于存储数据的内存有限”，或者“允许执行每个子任务所需的时间有限”。一个算法如果比其它已知算法所需要的资源都少，这个算法也被称为是有效率的。算法的代价（Cost）是指消耗的资源量。一般说来，代价是由一个关键资源例如时间或空间来评估的。
毋庸置疑，人们编写程序是为了解决问题。只有通过预先分析问题来确定必须达到的性能目标，才有希望挑选出正确的数据结构。有相当多的程序员忽视了这一分析过程，而直接选用某一个他们习惯使用的，但是与问题不相称的数据结构，结果设计出一个低效率的程序。如果使用简单的设计就能够达到性能目标时，选用复杂的数据结构也是没有道理的。
人们对常用的数据结构与算法的研究已经相当透彻，可以归纳出一些设计原则：
（1）每一种数据结构与算法都有其时间、空间的开销和收益。当面临一个新的设计问题时，设计者要彻底地掌握怎样权衡时空开销和算法有效性的方法。这就需要懂得算法分析的原理，而且还需要了解所使用的物理介质的特性（例如，数据存储在磁盘上与存储在内存中，就有不同的考虑）。
（2）与开销和收益有关的是时间——空间的权衡。通常可以用更大的时间开销来换取空间的收益，反之亦然。时间——空间的权衡普遍地存在于软件开发的各个阶段中。
（3）程序员应该充分地了解一些常用的数据结构与算法，避免不必要的重复设计工作。
（4）数据结构与算法为应用服务。我们必须先了解应用的需求，再寻找或设计与实际应用相匹配的数据结构。＇Shaffer 1998＇
5。4 用 户 界 面 设 计
某个人总有办法让自己保持心情愉快、信心十足。有一天，他向一名围棋九段和一名乒乓球世界冠军挑战，结果他全胜了。因为他跟围棋九段打乒乓球，跟乒乓球冠军下围棋。用户界面的编程技术是人们熟悉得不得了的事，我决定讲一讲比较陌生的“用户界面设计美学”。
有位爱好书画的博士后请我欣赏钢琴演奏会。我从头到尾只听到“叮叮咚咚”的声音，实在享受不到“高雅”，就请这位朋友指点。他虽然也不懂钢琴，却从欣赏书法的角度设法解释如何欣赏音乐。可是我既不懂书法也不懂音乐，真是坐立不安。“美”似乎真的不可言传。我在读本科时，特别喜欢编写用户界面程序，并且常向同学演示、卖弄。我觉得还不过瘾，就写了一篇“用户界面设计美学”的短文＇林锐 1997＇。凡是路过我实验室的同学都被我逮住，被迫听完我得意之极的朗读，茫然者与痛苦者居多。不久我的朗读便所向披糜，闻声者逃之夭夭。现在我又把那篇短文摘录至此，请您忍着点吧。
5。4。1 界面设计中美的需求与导向作用
人们对美的向往和追求是与生俱有的。显然没有人愿意丑化自己的程序，也没有用户嗜好丑陋的界面。软件开发者要设计美，用户要享受美，所以界面的美是开发者与用户的共同需求。
界面美的概念很抽象，以致让人无法说清楚什么是界面的美。但它同时又很现实，以致人人都可以去欣赏和感受界面美，并且挑剔美中之不足。美学不是一种量化的学问，如果因此而轻视美学指导，必将导致在设计过程中光依赖程序员个人的经验与感觉。由于程序员接受的教育主要是如何使计算机完成工作，而不是人如何工作，因此仅靠程序员主观想象设计而成的界面往往得不到大众用户的认可。
美的界面能消除用户由感觉引起的乏味、紧张和疲劳（情绪低落），大大提高用户的工作效率，从而进一步为发挥用户技能和为用户完成任务作出贡献。从人机界面发展历史与趋势上可以看出人们对界面美的需求，以及美在界面设计中的导向作用。
界面设计已经经历了两个界限分明的时代。第一代是以文本为基础的简单交互，如常见的命令行，字符菜单等。由于第一代界面考虑人的因素太少，用户兴趣不高。随着技术的发展，出现了第二代直接操纵的界面。它大量使用图形、语音和其它交互媒介，充分地考虑了人对美的需求。直接操纵的界面使用视听、触摸等技术，让人可以凭借生活常识、经历和推理来操纵软件，愉快地完成任务。更高层次的界面甚至模拟了人的生活空间，例如虚拟现实环境。
界面的美充分体现了人机交互作用中人的特性与意图，越来越多的用户将通过具有吸引力而令人愉快的人机界面与计算机打交道。
5。4。2 界面美的内涵
本节从合适性、风格和广义美三个方面论述界面美的内涵。
一、界面的合适性
界面的合适性是指界面是否与软件功能相融洽。如果界面不适合于软件的功能，那么界面将毫无用处，界面美的内涵就无从谈起。所以界面的合适性是界面美的首要因素，它提醒设计者不要片面追求外观漂亮而导致失真或华而不实。界面的合适性既提倡外美内秀，又强调恰如其分。
合适性差的界面无疑会混淆软件意图，致使用户产生误解。即使它不损害软件功能与性能，也会使用户产生不该有的情绪波动。例如一些软件开发者喜欢为其作品加一段动画演示，以便吸引更多用户的关注。这本是无可非议的，问题在于这演示是否合情合理。如果运行一个程序，它首先表演一套复杂的动画，在后台演奏雄壮的进行曲，电闪雷鸣之后出来的却是一个普通的文本编辑器。整个过程让用户置身于云里雾里，而结果却让用户感到惊谔而不是惊喜。合适性差的界面只会给软件带来厄运。
二、界面的风格
界面的风格有两类，一是“一致性”，二是“个性化”。
商业应用软件的界面设计注重一致性。设计者必须密切注意在相同应用领域中最流行的软件的界面，必须尊重用户使用这些软件的习惯。例如商业软件习惯于设置F1键为帮助热键，如果某个设计者别出心裁地让F1键成为程序终止的热键，那么在用户渴望得到帮助而伸手击F1键的一刹那，他的工作就此完蛋。相信这个用户“一朝被蛇咬，十年怕井绳”。
目前流行的软件开发工具如Visual C＋＋、Visual Basic、Delphi、C＋＋ Builder、Power Builder等，都能够快速地开发出非常相似的图形用户界面。在Internet/Intranet领域，浏览器几乎成了唯一的客户机程序，因为用户希望用完全一致的软件来完成千变万化的应用任务。
在娱乐领域的软件中，有个性化的界面自然比泯然于众的界面更具有吸引力。一般说来，计算机专业人员玩过的软件不计其数。界面看多了，真有种“曾经沧海难为水”的感觉。不过当我看到一个叫Sonique的放音乐的软件时，不禁对其界面的创意啧啧称赞，忍不住象贴美女像那样把它贴到书中，如图5。7所示。
图5。7 Sonique软件的几种界面
人们经常搞不清楚什么情况下应该追求“一致性”或“个性化”。在大白天，当人们都穿戴整齐时，有些人喜欢只挂几片遮羞布。而当大家都赤条条地在共公浴室洗澡时，却也有人喜欢穿着衣服。
三、界面的广义美
尽管界面的美并没有增加软件的功能与性能，却又是必为可少的。用户使用界面时，除了直接的感官美感外，还有很大一部分美感是间接的，它们存在于人们的使用体验中，例如方便，实用等。与图形用户界面相比，命令行是最原始的界面，它难记又难看。但对于熟练的用户而言，他们乐于使用命令行以获得高效率。命令行因具有高效率而赢得了专业人士的喜爱，早期的Unix系统就是彻头彻尾的命令系统。可以说，一切有利于人机交互的界面设计因素都具有广义美。
界面设计的一些特殊考虑也体现了广义美，如设法使残障人也可以使用软件。IBM公司在1985年已经创建了残障人国家支持中心。Apple公司的专门教育办公室则提供了一些有利于残障人使用的计算机信息产品。
5。5 系统设计示例
——支持协同工作的交互式三维图形软件开发系统
本节论述“支持协同工作的交互式三维图形软件开发系统”的系统设计，作为本章的示例（ 取材于作者的博士论文工作＇林锐 2000＇）。
5。5。1 设计背景
图形标准在图形领域有着重要的地位，它不仅加速了3D应用程序的开发，而且使3D应用程序的可移植性更好。历史上曾出现的图形标准（或API）有Core、GKS、PHIGS、PEX、GL、Dore、RenderMan、Hoops、OpenGL等等。经过竞争与淘汰，目前OpenGL成为国际上公认的3D图形工业标准，在Unix与PC平台得到广泛应用。OpenGL提供了数百个库函数，可以方便地绘制具有真实感的3D图形。但是在开发交互式的3D图形应用程序时，图形的绘制只是一部分工作，更多的工作集中在场景数据结构、图形对象、三维交互和图形用户界面的设计上。
由于OpenGL与窗口系统无关，不提供任何交互手段，必须由程序员自己编写所有的交互功能。并且OpenGL 的编程接口是低级的C函数，不提供可复用的对象库或者应用程序框架，开发效率不高。为了克服这些困难，人们往往在图形标准之上再建立更高级的开发工具（3D Toolkit或3D Engine）。基于OpenGL的著名的开发工具有Open Inventor、IRIS Performer、Optimeizer/Cosmo3D以及GLUT等等。Open Inventor被誉为是交互式3D开发工具的“事实标准”，但显然没有一个3D开发工具能满足所有的应用需求，3D的广泛应用需要更多的开发工具支持。
随着计算机图形技术与网络技术的迅猛发展，两者的结合势在必行。在商业、科研、教育、娱乐等领域，用于分布式虚拟环境（Distributed Virtual Environments； DVEs）和计算机支持协同工作（puter Supported Cooperative Work； CSCW）的图形系统已成为研究与应用的热点。著名的DVEs系统有DIVE、dVS、MR、Repo…3D等。但是这些DVEs系统缺乏3D开发工具的交互式图形功能以及通用性，而通用的3D开发工具如Open Inventor则又不支持分布式计算和协同工作。由于在窗口系统、图形支撑库、编程语言等方面存在差异，上述DVEs系统和3D开发工具难以方便地结合使用。
我们多方面分析了3D需求及软硬件条件，研制完成运行于PC平台，支持协同工作的交互式三维图形软件开发系统，如图5。8所示。其中：
（1）Intra3D 2。0是基于OpenGL的通用交互式三维图形软件开发工具，可用于快速开发Window 9x/NT下的交互式三维图形应用软件。
（2）CNC 1。0是支持协同工作的网络通讯开发系统（Cooperative Network municator），其核心是支持“发布—订阅模式”与“组播模式”的服务器与API。
结合Intra3D 2。0和CNC 1。0，可以快速开发支持协同工作的交互式三维图形应用软件。
图5。8 支持协同工作的交互式三维图形软件开发系统
5。5。2 通用交互式三维图形软件开发工具 Intra3D 2。0
Intra3D 2。0的核心是集成了场景数据结构、图形对象、三维交互算法和图形用户界面的C＋＋类库与（ponent Object Model）对象库，支持Visual C＋＋、Visual Basic、Delphi等语言的应用编程。Intra3D的核心库分四层创建：
（1）第一层为“基础对象与函数”（Basic Objects and Functions）；
（2）第二层为“图形对象”（Graphical Objects）；
（3）第三层为“场景图与节点”（Scene Graph and Nodes）；
（4）第四层为“绘制与交互”（Rendering and Interaction）。
体系结构如图5。9所示，其中高层构件可以引用低层构件，但低层构件不能引用高层构件。
图5。9 Intra3D 2。0 的体系结构
Intra3D 2。0是免费软件，有配套书籍《交互式三维图形技术与程序设计》。标准版软件约25兆，核心库7万多行C＋＋代码全部公开，用户可以方便地修改内核以适应不同的需求。
5。5。2。1 主要模块和功能
一、基础对象与函数层
（1）定义了用于对象引用计数的内存管理基类；
（2）矢量、矩阵与四元组运算，鼠标跟踪球算法；
（3）点阵字体与三维矢量字体输出，常用于数据可视化图形的数据标注；
（4）图像输入输出以及纹理映射，支持BMP、GIF、JPEG、SGI、TGA等图像格式；
（5）常用几何图元的绘制，如锥、柱、球、环等，并支持Swept形体，螺旋体的绘制；
（6）提供450余种材质，在第四层中可以交互式编辑这些材质。
二、图形对象层
图形对象能将数据转化为几何模型并可以绘制出来。Intra3D 2。0版提供了三类图形对象：
（1）常用几何对象，如长方体、锥体、圆柱体、球体、圆环体、Swept形体等；
（2）多边形模型对象，可用于绘制Autodesk公司。3ds模型和Wavefront公司的。obj模型；
（3）商业统计图形对象，如柱形图、带状图、条形图、折线图、面积图、饼图、塔形图、曲线图、曲面图、进程图、股票图等。
图形对象的开发与应用问题密切相关，用户可以使用继承方法扩充新的图形对象，而不会影响到其它三层的构件。
三、场景图与节点
场景图（Scene Graph）是有向无环图，Scene Graph的主要节点有：（1）SceneNode是所有节点的基类。在SceneNode中定义了局部坐标系以及相应的图形变换，这样便于第四层以同样的操作方式实现三维交互。（2）相机节点（CameraNode）支持平行投影与透视投影，支持多个相机切换。（3）光源节点有三种：平行光源节点（DirLightNode）、点光源节点（PointLightNode）和锥光源节点（SpotLightNode）。（4）形体节点（ShapeNode）用于引用图形对象，有关图形对象的三维交互均由ShapeNode处理。
四、绘制与交互层
Intra3D的交互分两类：一类是对形体、光源和相机的直接操作，另一类是真实感属性的编辑。Intra3D的场景视图构件（SceneView）封装了交互式绘制的所有细节，如消息处理、场景节点的遍历绘制、多重采样消锯齿、鼠标交互等。为了便于编辑真实感属性，Intra3D定制了一些常用对话：矢量字体对话（FontDialog）、颜色对话（ColorDialog）、材质库对话（MaterialLibDialog）、材质对话（MaterialDialog）与光源对话（DirLightDialog； PointLightDialog； SpotLightDialog）。
5。5。2。2 用户界面设计
Intra3D的场景视图构件SceneView用于快速创建交互式3D应用程序的主界面。SceneView支持selecting、scaling、rotating、translating、creating、deleting等三十余种操作，并提供工具条方便于交互，如图5。10所示。
为了编辑真实感属性，常需在对话框中绘制3D 图形。Microsoft的窗口系统不提供3D的对话窗口。使用Intra3D的Window3D构件可在对话框中创建多个3D视图，图5。11的材质对话和图5。12的材质库对话都使用了Window3D构件。颜色编辑是3D图形程序中最常用的交互，材质与光源的编辑实际上是通过改变颜色分量来实现的。需要进行颜色编辑的交互均涉及HSV与RGB模式的颜色转换。Intra3D的“绘制与交互层”实现了这些计算，并且提供彩色的滑动条用于鼠标交互。图5。13、图5。14分别为点光源对话和颜色对话。
图5。10 用于直接操作的三维交互工具条
图5。11 材质对话 图5。12 材质库对话
图5。13 点光源对话 图5。14 颜色对话
5。5。3 支持协同工作的网络通讯开发系统 CNC 1。0
最简单的协同工作模式是让两个客户机直接通讯，可以用Socket编程实现。假设有 n 个客户机参加协同工作，每个客户机将与所有其它的客户机通讯。那么总共存在n（n…1）/2 个Socket直接通讯，并且每个客户机的变动将导致其它客户机的修改。这种Socket直接通讯使得协同工作的管理和客户机的程序设计变得非常困难。CNC系统提供了支持“发布—订阅（Publish…Subscribe）”与“组播（Multicast）” 模式的服务器与API，可以高效地管理多个组群的协同工作，并使得客户机的程序设计十分简单。CNC 1。0的系统结构如图5。15所示。
CNC 服务器将客户机分组管理。在“发布—订阅”模式中，将产生数据的进程称为生产者（Producer），将接受数据的进程称为消费者（Consumer）。生产者可以向服务器发布数据，服务器保存这些数据。消费者可以向服务器订阅数据。每个客户机可能是很多数据的生产者或消费者。同一时刻，CNC系统允许有任意多个生产者和消费者存在。CNC的“发布—订阅” 功能是用TCP协议实现的。
在“组播” 模式中，服务器动态地分配每个组的组播地址。客户机可以向服务器申请加入任意组，允许向任意组播放消息，服务器不保存这些组播消息。CNC的“组播”功能是用UDP协议实现的。
图5。15 CNC 1。0 的系统结构
5。5。3。1 CNC 客户机的API设计
类CNCClient客户机用来实现“发布—订阅”和“组播”功能，主要接口（公有函数）如下：
class CNCClient
｛public：
BOOL Connect（…）；// 连接服务器
BOOL Disconnect（）；// 与服务器断开连接
BOOL PublishData（…）；// 向服务器发布数据
BOOL QueryData（…）； // 向服务器查询数据
BOOL SubscribeData（…）；// 向服务器订阅数据
GROUPIP QueryGroupIP（…）； // 向服务器查询组播地址
DWORD MulticastMessage（…）；// 发送组播消息
virtual void Messa