摘要
我的研究方向为基于离散点的真实感图形绘制的研究，是庞云阶教授博士点基金项目的一个组成部分。本文对传统的真实感图形生成过程进行了深入的研究，分析了其中的缺点与不足，并在此基础上采用了基于离散点造型和基于点域法绘制的新方法。本文所做的工作包括：在实现基于离散点的造型、取景变换、消隐、光照、阴影等基础工作之上，实现了基于离散点的光线跟踪算法、基于离散点的简单动画制作和一些应用方面的尝试，在许多不同的场景中都取得不错的效果。本文的重点是实现基于离散点的光线跟踪算法，在把离散点造型与传统光线跟踪算法相结合、跟踪过程中加速求交运算等方面做了一定的工作，提出了新的算法，并且在实践中得到了验证。
本文首先实现了基于离散点的造型，这是进行真实感图形绘制的基础与核心。该方法改变了传统的面片存储，而是将场景中所有曲面上所求得的离散点存储起来。首先我们用均匀参数化的方法将曲面剖分成若干小多边形，然后将每个小多边形投影到屏幕上得到相应的投影区域，再对投影区域中的每个象素点找到它所对应的空间曲面上的点，最后根据这些离散点在屏幕上的投影排列成若干序列，每个序列中的点都按照它们在观察坐标下的Z值从小到大排序。最终在曲面上显示的是每个序列中的第一个点的颜色值，很自然的实现了消隐，而其它点则用于计算阴影、透明以及光线跟踪时光线与物体求交运算等。
本文实现的重点是基于离散点的光线跟踪算法，传统光线跟踪技术是基于多边形对光线的反射、透射及相互之间的幅射关系建立的光照模型，通过计算每一个多边形小平面的法向量和光照效果来确定曲面的整体明暗效果，本文从离散点表示法着手，提出基于离散点的光线跟踪绘制方
法如下：
由于我们采用了基于离散点造型的数据结构，在进行光线跟踪运算时，需要对屏幕上所有像素点对应点序列中第一个点，即可见点执行光线跟踪算法，逐点扫描屏幕上所有像素点，由视点向像素发出一根射线，该射线在点序列中第一个点处与第一个物体相交，在其反射与折射方向上进行跟踪，判断反射方向与折射方向是否与其他物体相交，如相交则继续在交点的反射方向与折射方向上跟踪下去，重复这个过程，直到光线满足跟踪终止条件。
基于离散点的绘制方法与传统方法的一个很大的区别就是在于交点计算，以线线求交为例，传统方法可以用现成公式得出，而在离散点模型中得到确定交点是不现实的，我们的方法是假定有交点，求出一条线上与该假定交点最近的点，判断此交点与另一条线的距离是否小于某动态确定的阈值来得出相交关系。在判断交点的计算中，我们借用阴影测试线的思想：场景中反射光线路径上第一个交点在屏幕上的投影一定位于反射光线在屏幕上的投影所形成的线段上；反过来，交点一定位于投影线段上某点所对应的点序列中，即只有投影线段上的点所对应的序列中的点才有可能为跟踪交点，所以现在只需考虑投影线段上所有点所对应的点序列中的点，判断是否确定在反射光线上即可，这样计算量大大减小。按照数学公式计算出点序列所在直线和反射光线的公垂线，然后再计算出公垂线与点序列所在直线的交点；逐点判断当前象素点序列中所有点的Z值，由于我们的数据结构是视点方向上的按照Z值进行排序的点序列，所以与交点的Z值最近的点就是直线上最有可能与反射光线相交的点，判断该点与反射光线的距离，如果小于阈值则相交，否则继续考察其它点序列。在判断每一个点序列时，该方法都需要计算反射光线与点序列所在直线的公垂线，并求出公垂线与直线的交点，增加了系统的运算负担，但是对应于每一个点序列，我们只需要做一次公垂线计算，找到公垂线与直线交点之后，通
过比较Z值我们可以快速的找到点序列中符合交点条件的点，再做一次点线距离计算判断其是否为真正的交点；而传统方法需要计算点序列中每一个点与光线的距离并做出判断，如果场景比较复杂，其中物体比较多的情况下，点序列中的点的个数会大大增加，点线距离的计算将成为运算的主要负担，而我们的方法对应一个点序列只做一次点线距离计算，与点序列中点的个数无关。这样，通过计算公垂线与直线的交点，并用交点的Z值与点序列中点的Z值做判断的方法，找到点序列上与反射光线距离最近的点，非常有效的减少了点线求交的次数，尤其是在场景比较复杂的情况下，极大的提高了求交的运算速度。
由于我们采取了基于离散点造型的数据结构，这种存储结构的一个突出优点就是可以很方便的在场景中增删实体，每次只单独考虑一个曲面，一个曲面的增删对其它曲面没什么影响，只需对存储结构中属于该曲面的点进行增删即可。基于这个特性，我们实现了简单的基于离散点的动画演示。如果某个曲面的位置有所改变，那么，首先我们需要从原来的存储结构中删除该曲面上的所有离散点；然后，重新求出该曲面在新的位置上的离散点；再将这些离散点重新插入到存储结构中对应序列中的适当位置。由于整个过程中只涉及到了有所变动的曲面，而保留了原来的计算结果，所以该算法计算速度较快，手续简单有效；同时基于相同原理，我们实现了用鼠标键盘操纵场景中单个物体的移动、旋?
My research direction is generating realistic image based on discrete points, a part of Specialized Research Fund for the Doctoral Program of Higher Education leading by Prof Pang YunJie. This paper has carried on deep research to the generating course of realistic image and has analyzed its shortcoming and insufficient. Then a kind of new method of modeling on the basis of discrete points and drawing on the basis of dot domain is proposed. The content of this text include: with some basal work such as modeling on the basis of discrete points、 transformation of coordinate、blanking, realizing of illumination、generating of shadow and transparent, we have realized the arithmetic of ray tracing on the basis of discrete points, simple animation on the basis of discrete points and some attempt of application, all have made the good result in a lot of different scenes. The focal point that this text realized is ray tracing on the basis of discrete points, in the parts of the combining of modeling on the basis of discrete points and traditional ray tracing、the accelerating operation in getting point of intersection, quantity of work has been done and new algorithm has been proposed, and this algorithm has been verified in practice.
This text has realized the modeling on the basis of discrete points at first, which is the foundation and core of generating realistic image. In this method the discrete points on curved faces in the scene but not the traditional small plane are stored. First of all, we need to subdivide curved face into several small polygons using uniform parameterized method. Now we project every small polygon on the screen to form corresponding area in which we must find corresponding space point to each pixel. According to the projected position of these discrete points, they were arranged into several arrays, and according to the distance between point and eye we arrange the points in each array in the order from near to far. At last the points displayed on the screen are the first one of each array by which blanking is realized naturally. And other points in each array are used for computing shadow, transparent and operation in getting point of intersection between ray and object in ray tracing.
The focal point that this text realized is ray tracing on the basis of discrete points, traditional ray-tracing technology is based on the illuminance modeling, which set up by the relation of the light reflected, refracted by the polygon and radiated each other. The whole effect of surface is calculated by calculating the
normal vector and illumination each polygon, and this paper centers on using discrete points to generate realistic images, and brought forward the ray-tracing rending method based on discrete points:
Because of using the data-structure of modeling on the basis of discrete points, when operating ray-tracing, we need to begin ray-tracing operating to the first dot in each arrays on the screen, namely, the point can be displayed; scan all the pixels on the screen and send out a radial from eye to the pixel, the ray is intersected with the first object at the first dot in the array, tracking out in the direction of reflect director and refracted director, judging whether the ray is intersected in the two directions. As soon as being intersected, we should keep tracking in the nodical reflect direction and refract direction, and repeats above-mentioned operation until ray-tracing is over.
A different between drawing on the basis of discrete points and traditional method is operation of calculating points of intersect. Such as between lines, we can use present formula by traditional method to get the point, but it's unpractical to get certain point in the modeling based on discrete points. During the course of computing the point of intersection, a kind of new method on the basis of discrete points is proposed utilizing the thought of shadow checking line: on the screen, the coordinate of the first point of intersection in the direction of reflect ray must be on the line segment which i
引文
[1] 《计算机图形学(新版)》，孙家广、杨长贵编著，清华大学出版社，1995。
[2] 《计算机图形学教程》，唐荣锡、汪嘉业、彭群生等编著，科学出版社，1999。
[3] 《计算机真实感图形的算法基础》，彭群生、鲍虎军、金小刚等编著，科学出版社，1999。
[4] 《计算机图形学教程》，李文辉、钟慧湘、王钲旋、卢奕南编著，吉林大学出版社，1997。
[5] 《最新VC++绘图程序设计技巧与实例教程》，刘静华、王永生编著，科学出版社，2001
[6] 《计算机辅助几何设计与非均匀有理B样条》，施法中编著，北京航天航空大学出版社，1994。
[7] 《数字图像处理》，K.R.Castleman 著，朱志刚、林学訚、石定机等译，电子工业出版社，1999。
[8] 《Visual C++ 6.0编程》，胡海生、李升亮编著，清华大学出版社，2003。
[9] “A framework for realistic image synthesis”，Donald P. Greenberg, Kenneth Torrance, Peter Shirley, James Arvo, James Ferwerda, Sumanta Pattanaik, Eric Lafortune, Bruce Walter, Sing-Choong Foo, and Ben Trumbore. SIGGRAPH 97 Conference Proceedings, Annual Conference Series, pages 477--494. ACM SIGGRAPH, Addison Wesley, August 1997.
[10] “Non-linear approximation of reflectance functions”，Eric P. F. Lafortune, Sing-Choong Foo, Kenneth E. Torrance, and Donald P. Greenberg. In Turner Whitted, editor, SIGGRAPH 97 Conference Proceedings, Annual Conference Series, pages 117--126. ACM SIGGRAPH, Addison Wesley, August 1997.
[11] “Adaptive shadow maps”，Randima Fernando, Sebastian Fernandez, Kavita Bala, and Donald P. Greenberg. In Eugene Fiume, editor, SIGGRAPH 2001 Conference Proceedings, Annual Conference Series. ACM SIGGRAPH, Addison Wesley, August 2001.
[12] John C. Hart ，"Ray Tracing Implicit Surfaces" ，{SIGGRAPH} 93 Modeling, Visualizing, and Animating Implicit Surfaces course notes ，pp 13-1 to 13-15，1993。
[13] Dinesh Manocha and James Demmel. “Algorithms for intersecting parametric and algebraic curves I: Simple intersections” ，ACM Trans. Graphics, 13(1):73-- 100, January 1994。