人工智能、数理算法

oraclelang

最优化
在计算机图形学里，我们常常为了期望的目标寻求一种合适的描述对象或者对象集的方法。例如安排灯的位置使得房间的照明看起来有种特殊的“感觉”，动画里的人物要怎样活动四肢才能实现一个特殊的动作，怎样排版才不会使页面混乱。以上这些例子可以归结为最优化问题。十年前的计算机图形学几乎没有最优化技术的文献，不过最近这个领域越来越重视最优化理论。我认为在计算机图形学里，最优化的重要性将会日益增加。

概率论与统计学

oraclelang

计算机图形学的许多领域都要用到概率论与统计学。当研究者涉足人类学科时，他们当然需要统计学来分析数据。图形学相关领域涉及人类学科，例如虚拟现实和人机交互(HCI)。另外，许多用计算机描绘真实世界的问题牵涉到各种未知事件的概率。两个例子：一棵成长期的树,它的树枝分杈的概率；虚拟的动物如何决定它的行走路线。最后，一些解高难度方程组的技巧用了随机数来估计方程组的解。重要的例子：蒙特卡罗方法经常用于光如何传播的问题。以上仅是一部分在计算机图形学里使用概率论和统计学的方法。

oraclelang

计算几何学
计算几何学研究如何用计算机高效地表示与操作几何体。典型问题如，碰撞检测，把多边形分解为三角形，找出最靠近某个位置的点，这个学科包括了运算法则，数据结构和数学。图形学的研究者，只要涉足创建形体（建模），就要大量用到计算几何学。
推荐的参考书:
Computational Geometry in C
Joseph O'Rourke
Cambridge University Press
[大学教材]
Computational Geometry: An Introduction
Franco Preparata and Michael Shamos
Springer-Verlag
[很经典，不过有点旧了]

oraclelang

总结：数学应用和数学理论
对于图形学来说，以上提到的许多数学学科都有个共同点：比起这些数学的理论价值，我们更倾向于发掘它们的应用价值。不要惊讶。图形学的许多问题和物理学者与工程师们研究的问题是紧密联系的，并且物理学者与工程师们使用的数学工具正是图形学研究者们使用的。多数研究纯数学理论的学科从不被用于计算机图形学。不过这不是绝对的。请注意这些特例：分子生物学正利用节理论来研究DNA分子动力学，亚原子物理学用到了抽象群论。也许有一天，纯数学理论也能推动计算机图形学的发展，谁知道呢？
有些看来重要的数学实际上在计算机图形学里不常被用到。可能拓扑学是此类数学中最有意思的。用一句话来形容拓扑学，它研究油炸圈饼与咖啡杯为什么在本质上是相同的。答案是他们都是只有一个洞的曲面。我们来讨论一下拓扑学的思想。虽然曲面是计算机图形学的重要成分，不过微分几何学的课程已经涵盖了多数对图形学有用的拓扑学知识。微分几何学研究曲面的造型，可是拓扑学研究曲面的相邻关系。我觉得拓扑学对于图形学来说几乎没用，这是由于拓扑学关心抽象的事物，而且拓扑学远离了多数图形学的核心——三维欧氏空间的概念。对于图形学来说，拓扑学的形式（符号表示法）是表达思想的简便方法，不过图形学很少用到抽象拓扑学的实际工具。对图形学来说，拓扑学像一个好看的花瓶，不过别指望它能立即带给你回报。
有人曾经这么问我，计算机图形学是否用到了抽象代数（群论，环，等等….）或者数论。我没怎么遇到过。和拓扑学一样，这些学科有很多美好的思想。可是很不幸，这些思想很少用于计算机图形学。

oraclelang

求射线和面的交点
wtitten by silodiq
参考《Introduction to 3D Game Programming with DirectX® 9.0》


1.        射线的表示方法

p(t) = p0 + tu;
其中p0是射线的起始点，u是射线的方向向量（需要单位化），t在[0，+无穷]

2.        面的表示方法

由上图可以知道
n(p-p0) = 0;
设d = -np0
所以有：np+d = 0;为平面方程，其中p为平面上的任意一点，n为平面的单位法向量，
如果空间中一点Px,如果nPx + d = 0,那么Px在（np+d=0）表示的平面上，如果大于0，该点在平面的上面（法线所指的方向），如果小于0，该点在平面的下面。

3．求射线和平面的交点

要求利用上面所介绍的射线和面的交点只要把p(t)代入（np+d=0）这个方程，这样我们就得到
np(t)+d=0;
n(p0+tu)+d=0;
np0+tnu+d=0;
t=(-d-np0)/nu;
如果t大于等于0说明射线和面有交点，根据p(t)=p0+tu;

oraclelang

寻路算法新思维
作者：刘晶
2004-6-17
目前常用寻路算法是A*方式，原理是通过不断搜索逼近目的地的路点来获得。

如果通过图像模拟搜索点，可以发现：非启发式的寻路算法实际上是一种穷举法，通过固定顺序依次搜索人物周围的路点，直到找到目的地，搜索点在图像上的表现为一个不断扩大的矩形。如下：

oraclelang

很快人们发现如此穷举导致搜索速度过慢，而且不是很符合逻辑，试想：如果要从（0，0）点到达（100，0）点，如果每次向东搜索时能够走通，那么干吗还要搜索其他方向呢？所以，出现了启发式的A*寻路算法，一般通过 已经走过的路程 + 到达目的地的直线距离 代价值作为搜索时的启发条件，每个点建立一个代价值，每次搜索时就从代价低的最先搜索，如下：

oraclelang

综上所述，以上的搜索是一种矩阵式的不断逼近终点的搜索做法。优点是比较直观，缺点在于距离越远、搜索时间越长。

现在，我提出一种新的AI寻路方式——矢量寻路算法。

通过观察，我们可以发现，所有的最优路线，如果是一条折线，那么、其每一个拐弯点一定发生在障碍物的突出边角，而不会在还没有碰到障碍物就拐弯的情况：如下图所示：

oraclelang

我们可以发现，所有的红色拐弯点都是在障碍物（可以认为是一个凸多边形）的顶点处，所以，我们搜索路径时，其实只需要搜索这些凸多边形顶点不就可以了吗？如果将各个顶点连接成一条通路就找到了最优路线，而不需要每个点都检索一次，这样就大大减少了搜索次数，不会因为距离的增大而增大搜索时间

oraclelang

这种思路我尚未将其演变为算法，姑且提出一个伪程序给各位参考：
1．        建立各个凸多边形顶点的通路表TAB，表示顶点A到顶点B是否可达，将可达的顶点分组保存下来。如: ( (0,0) (100,0) ),这一步骤在程序刚开始时完成，不要放在搜索过程中空耗时间。
2．        开始搜索A点到B点的路线
3．        检测A点可以直达凸多边形顶点中的哪一些，挑选出最合适的顶点X1。
4．        检测与X1相连（能够接通）的有哪些顶点，挑出最合适的顶点X2。
5．        X2是否是终点B？是的话结束，否则转步骤4（X2代入X1）