CN1410948A

Movatterモバイル変換

Info

Publication number: CN1410948A
Application number: CN 02130945
Authority: CN
Inventors: 秦开怀
Original assignee: Tsinghua University
Current assignee: Tsinghua University
Priority date: 2002-09-23
Filing date: 2002-09-23
Publication date: 2003-04-16

Abstract

平面和球面非线性反射和折射的实时光线跟踪方法，属于计算机图形技术领域。其特征在于：对于被折射或反射的多面体，首先计算出各顶点的光学映射虚顶点，再根据多面体的拓扑关系依次把虚顶点连接成由若干虚面构成的虚物体；绘制时用递归算法把虚物体投射到相应的反射或折射表面上，通过与该表面本身的颜色值进行α混合，从而得到与光线跟踪算法类似的真实感图形。本专利同时给出了物体在平面折射体内或外、三维折射、球面反射和折射五种情况下场景中任一点P的虚顶点P′的计算公式、以及它们公用的递归算法及其绘制过程。对于中等复杂程度的场景，利用支持OpenGL编程的图形硬件的加速技术，解决了统一处理反射和折射平面场景的实时光线跟踪问题。

The invention discloses a real-time ray-tracing method for plane and spherical nonlinear reflection and refraction, belonging to the technical field of computer graphics. It is characterized in that: for the refracted or reflected polyhedron, the optical mapping virtual vertices of each vertex are firstly calculated, and then the virtual vertices are sequentially connected into a virtual object composed of several virtual faces according to the topological relationship of the polyhedron; The virtual object is projected onto the corresponding reflective or refractive surface, and is mixed with the color value of the surface itself by α, so as to obtain a photorealistic image similar to the ray tracing algorithm. This patent also gives the calculation formula of the virtual vertex P' of any point P in the scene under the five conditions of the object inside or outside the plane refraction, three-dimensional refraction, spherical reflection and refraction, as well as their common recursive algorithm and drawing process. For scenes with moderate complexity, the problem of real-time ray tracing for unified processing of reflection and refraction plane scenes is solved by using the acceleration technology of graphics hardware supporting OpenGL programming.

Description

Translated fromChinese

平面和球面非线性折射和反射的实时光线跟踪方法A real-time ray-tracing method for planar and spherical nonlinear refraction and reflection

技术领域technical field

平面和球面非线性折射和反射的实时光线跟踪方法属于计算机图形技术领域。A real-time ray-tracing method for planar and spherical nonlinear refraction and reflection belongs to the technical field of computer graphics.

背景技术Background technique

光线跟踪算法是生成三维真实感图形的最常用的算法之一，它是T.Whitted于1980年在国际杂志Comm.ACM，Vol.23，No.6上发表的论文“An improved Illumination Model forShaded Display”中提出来的一种真实感图形生成方法。它能够生成高质量的真实感图形，但是其计算速度比较慢，不能应用于实时交互的应用系统。为了提高光线跟踪的速度，多种改进方法应运而生。1984年P.S.Heckbert和P.Hanrahan等人在《Computer Graphics》上发表论文，首次提出了光束跟踪的方法。光束跟踪作为传统光线跟踪的一种改进，被用来提高渲染速度，处理走样问题，改善渲染质量及效率等等。但光束跟踪只能处理平面反射体的镜面反射，对于象厚玻璃一类的非线性折射问题以及曲面反射问题等等则不能处理，只能作线性近似。The ray tracing algorithm is one of the most commonly used algorithms for generating three-dimensional realistic graphics. It is the paper "An improved Illumination Model for Shaded Display" published by T. Whitted in the international journal Comm. A photorealistic graphics generation method proposed in ". It can generate high-quality realistic graphics, but its calculation speed is relatively slow, so it cannot be applied to real-time interactive application systems. In order to increase the speed of ray tracing, various improvement methods came into being. In 1984, P.S. Heckbert and P. Hanrahan published a paper on "Computer Graphics", and proposed the beam tracking method for the first time. As an improvement of traditional ray tracing, beam tracing is used to increase rendering speed, deal with aliasing problems, improve rendering quality and efficiency, and so on. However, beam tracing can only deal with specular reflection of plane reflectors, and cannot deal with nonlinear refraction problems such as thick glass and curved surface reflection problems, etc., and can only make linear approximations.

1996年，M.Levoy和P.Hanrahan.等人在SIGGRAPH上发表论文，提出了用4维光场来实现图形、图像的绘制的方法。在预处理中用多维光场计算图像的映像，然后当实时显示时，在每一帧中重新使用映像结果。但光场方法中仍有图像信息存储、走样和快速查找等问题有待进一步解决。In 1996, M.Levoy and P.Hanrahan. et al. published a paper on SIGGRAPH, and proposed a method of using 4-dimensional light field to realize the drawing of graphics and images. Compute the mapping of the image with the multidimensional light field in preprocessing, and then reuse the mapping result in each frame when displayed in real time. However, there are still problems such as image information storage, aliasing and fast search in the light field method to be further solved.

视点无关的环境映射的方法是W.Heidrich等人在1998年提出来的。利用环境映射，通过硬件的支持来实现真实感图形的显示，能达到交互的速率，但是却不能达到实时。它一般多用于处理反射现象，并且常常存在明显的误差。The method of viewpoint-independent environment mapping was proposed by W.Heidrich et al. in 1998. The use of environment mapping and the support of hardware to realize the display of realistic graphics can achieve the speed of interaction, but it cannot achieve real-time. It is generally used to deal with reflection phenomena, and there are often obvious errors.

1998年Ofek和Rappoport提出了利用反射虚物体和扩张映射(explosion map)来实现曲面反射的光线跟踪效果，它针对反射体将所有可能处在反射区域内的顶点进行变换，生成虚物体，然后同真实物体一样进行统一处理；但是他们不能处理折射问题，且扩张映射的误差较大，在递归过程中误差的累积和传播十分严重，生成的结果图像质量不高。虽然他们采用插值方法加以改进，但效果有限，却增加了不少计算量。In 1998, Ofek and Rappoport proposed the use of reflective virtual objects and expansion maps (explosion map) to achieve the ray tracing effect of surface reflection. It transforms all vertices that may be in the reflection area for the reflector to generate virtual objects, and then simultaneously Real objects are processed uniformly; but they cannot deal with the refraction problem, and the error of the expansion map is large, the accumulation and propagation of the error in the recursive process is very serious, and the resulting image quality is not high. Although they use interpolation method to improve, but the effect is limited, but it increases a lot of calculation.

目前有许多交互式图形系统利用硬件，每秒钟能处理大量的三维面片，但基本上都只能提供深度缓存(Z-Buffer)算法的绘制效果，不能处理反射和折射场景的实时真实感图形问题。At present, there are many interactive graphics systems that use hardware to process a large number of 3D patches per second, but basically they can only provide the rendering effect of the depth buffer (Z-Buffer) algorithm, and cannot handle the real-time realism of reflection and refraction scenes. Graphics problem.

发明内容Contents of the invention

本发明的目的在于提供既能统一解决非线性反射和折射问题，又能提高算法效率的平面和球面非线性折射和反射的实时光线跟踪方法。The purpose of the present invention is to provide a real-time ray tracing method of plane and spherical nonlinear refraction and reflection, which can not only solve the problem of nonlinear reflection and refraction uniformly, but also improve the algorithm efficiency.

本发明的特征在于：The present invention is characterized in that:

对于被折射或反射的多面体，首先计算出该多面体各个顶点的虚顶点，然后根据该多面体原有的点和面之间的拓扑关系依次把所有虚顶点连接成由许多虚面构成且最终形成反射或折射的光学映射虚物体，简称为虚物体；在显示图形时，把该虚物体用递归算法递归地投射到反射或折射表面上，从而得到与光线跟踪类似的图像效果；其中，虚顶点P′可表达为： $P^{'} = V + l \frac{B - V}{| B - V |},$ For the refracted or reflected polyhedron, the virtual vertices of each vertex of the polyhedron are calculated first, and then all the virtual vertices are sequentially connected according to the topological relationship between the original points and faces of the polyhedron to be composed of many virtual faces and finally form a reflection Or refracted optical mapping virtual object, referred to as virtual object; when displaying graphics, the virtual object is recursively projected onto the reflective or refracting surface with a recursive algorithm, so as to obtain an image effect similar to ray tracing; among them, the virtual vertex P ' can be expressed as: $P^{'} = V + l \frac{B - V}{| B - V |},$

其中V为视点，l为光线L经过折射或反射到达与该虚顶点对应的一个场景中的点P时所经过的路径的长度总和；B为投影平面上的一个采样点。Where V is the viewpoint, l is the sum of the lengths of the paths that light L passes through when it reaches a point P in a scene corresponding to the virtual vertex after refraction or reflection; B is a sampling point on the projection plane.

对于场景在折射体外的平面折射体而言，它依次含有如下步骤：For a plane refractor whose scene is outside the refractor, it contains the following steps in sequence:

(1)计算各虚顶点P′： $P^{'} = V + l \frac{I_{1} - V}{| I_{1} - V |};$ (1) Calculate each virtual vertex P': $P^{'} = V + l \frac{I_{1} - V}{| I_{1} - V |};$

l＝|V-I₁|+|I₁-I₂|+|I₂-P|， $I_{1} = Q + d \frac{U - Q}{| U - Q |},$ l=|VI₁ |+|I₁ -I₂ |+|I₂ -P|, $I_{1} = Q + d \frac{u - Q}{| u - Q |},$

Q＝V-w₁N， $U = V - \frac{C_{3} + C^{T} V}{C^{T} (P - V)} (P - V),$ Q=Vw₁ N, $u = V - \frac{C_{3} + C^{T} V}{C^{T} (P - V)} (P - V),$

其中，l为光线经过折射到达场景中的点P时所经过的路径的长度总和；w₁为视点V与折射体的水平距离；d为点I₁与视点V的垂直距离；Q为折射体入射面下端与视点V处于同一个水平位置上的一点；U为线VP与折射体入射面的交点，折射体入射面的方程设为C₀x+C₁y+C₂z+C₃＝0，并记C＝(C₀，C₁，C₂)^T；I₁、I₂分别为光线L与平面折射体投影平面即入、出两个折射面的交点，N为点I₁处的单位法向矢量。Among them, l is the sum of the lengths of the paths that the light passes through when reaching the point P in the scene through refraction; w₁ is the horizontal distance between the viewpoint V and the refraction body; d is the vertical distance between the point I₁ and the viewpoint V; Q is the refraction body A point at the same horizontal position as the lower end of the incident surface and the viewpoint V; U is the intersection point between the line VP and the incident surface of the refractor, and the equation of the incident surface of the refractor is set as C₀ x+C₁ y+C₂ z+C₃ = 0, and record C=(C₀ , C₁ , C₂ )^T ; I₁ and I₂ are respectively the intersection points of the light L and the projection plane of the plane refractor, that is, the entry and exit two refraction surfaces, and N is the point I₁ The unit normal vector of .

对于场景在折射体内的平面折射体而言，它依次含有如下步骤：For a planar refractor with the scene inside the refractor, it contains the following steps in order:

(1)计算各虚顶点P′： $P^{'} = V + l \frac{I - V}{| I - V |};$ (1) Calculate each virtual vertex P': $P^{'} = V + l \frac{I - V}{| I - V |};$

l＝|V-I|+|I-P|， $I = Q + d \frac{U - Q}{| U - Q |},$ l=|VI|+|IP|, $I = Q + d \frac{u - Q}{| u - Q |},$

其中，I为光线L与平面折射体的入射面的交点，该入射面的方程设为C₀x+C₁y+C₂z+C₃＝0，并记C＝(C₀，C₁，C₂)^T；N为点I处的单位法向矢量；d为点I₁与视点V的垂直距离；Q为折射体入射面下端与视点V处于同一个水平位置上的一点；U为线VP与折射体入射面的交点；Wherein, I is the intersection point of light L and the incident surface of the plane refractor, the equation of the incident surface is set as C₀ x+C₁ y+C₂ z+C₃ =0, and C=(C₀ , C₁ , C₂ )^T ; N is the unit normal vector at point I; d is the vertical distance between point I₁ and viewpoint V; Q is a point at the same horizontal position between the lower end of the incident surface of the refractor and viewpoint V; U is The intersection of the line VP and the incident surface of the refractor;

对于折射面相互垂直的三维平面折射而言，它依次含有如下步骤：For three-dimensional plane refraction where the refraction surfaces are perpendicular to each other, it contains the following steps in sequence:

(1)计算各虚顶点P′： $P^{'} = V + d \frac{I_{1} - V}{| I_{1} - V |};$ (1) Calculate each virtual vertex P': $P^{'} = V + d \frac{I_{1} - V}{| I_{1} - V |};$

d＝|V-I₁|+|I₁-I₂|+|I₂-P|，d=|VI₁ |+|I₁ -I₂ |+|I₂ -P|,

I₁＝V+dx+dy+dz，I₁ =V+dx+dy+dz,

dx＝xe_x，dy＝ye_y，dz＝ze_z，dx=xe_x , dy=ye_y , dz=ze_z ,

e_y＝N₂，e_z＝-N₁，e_y叉乘e_z再单位化得到e_x，e_y =N₂ , e_z =-N₁ , e_y is cross-multiplied by e_{z and} reunited to get e_x ,

其中，P是场景中即物体上的点，V是视点，N₁是入射面外法向量，N₂是出射面外法向量，入射面与出射面垂直，N₁、N₂是单位向量，e_x，e_y，e_z是局部坐标系下的基，x，y，z是局部坐标系下的坐标，dx，dy，dz是I₁点相对于视点的偏移量； $I_{2} = I_{1} - N_{1} C \sqrt{1 - \frac{x^{2} + y^{2}}{η^{2} (x^{2} + y^{2} + z^{2})}} - \hat{e} \frac{C \sqrt{x^{2} + y^{2}}}{η \sqrt{x^{2} + y^{2} + z^{2}}},$ 其中， $\hat{e} = \frac{V - I_{1} - N_{1} [(V - I_{1}) \cdot N_{1}]}{| V - I_{1} - N_{1} [(V - I_{1}) \cdot N_{1}] |}, C = \frac{η (a - y)}{y} \sqrt{x^{2} + y^{2} + z^{2}},$ η是三维折射体的折射率，α为视点到折射体出射面的垂直距离。对于球面反射体而言，它依次含有如下步骤：(1)计算各虚顶点P′： $P^{'} = V + (x + y) \frac{I - V}{| I - V |},$ Among them, P is the point on the object in the scene, V is the viewpoint, N₁ is the normal vector outside the incident plane, N₂ is the normal vector outside the exit plane, the incident plane is perpendicular to the exit plane, N₁ and N₂ are unit vectors, e_x , e_y , e_z are the bases in the local coordinate system, x, y, z are the coordinates in the local coordinate system, dx, dy, dz are the offsets of point I₁ relative to the viewpoint; $I_{2} = I_{1} - N_{1} C \sqrt{1 - \frac{x^{2} + {the y}^{2}}{η^{2} (x^{2} + {the y}^{2} + z^{2})}} - \hat{e} \frac{C \sqrt{x^{2} + {the y}^{2}}}{η \sqrt{x^{2} + {the y}^{2} + z^{2}}},$ in, $\hat{e} = \frac{V - I_{1} - N_{1} [(V - I_{1}) &Center Dot; N_{1}]}{| V - I_{1} - N_{1} [(V - I_{1}) &Center Dot; N_{1}] |}, C = \frac{η (a - the y)}{the y} \sqrt{x^{2} + {the y}^{2} + z^{2}},$ η is the refractive index of the three-dimensional refractor, and α is the vertical distance from the viewpoint to the exit surface of the refractor. For a spherical reflector, it contains the following steps in turn: (1) Calculate each virtual vertex P′: $P^{'} = V + (x + the y) \frac{I - V}{| I - V |},$

I为光线L照到球面时的反射点，它可表达为：I＝T·L_I，其中，L_I＝[L_Ix，L_Iy，P_z，1]^T，它是球面上点I在局部坐标系下的坐标；；T为从局部坐标系到世界坐标系的变换矩阵： $T = [\begin{matrix} u_{x} & v_{x} & w_{x} & 0 \\ u_{y} & v_{y} & w_{y} & 0 \\ u_{z} & v_{z} & w_{z} & 0 \\ 0 & 0 & 0 & 1 \end{matrix}],$ I is the reflection point when light L hits the spherical surface, it can be expressed as: I=T·_LI , where, L_I =[L_Ix , L_Iy , P_z , 1]^T , it is the point I on the spherical surface Coordinates in the local coordinate system; T is the transformation matrix from the local coordinate system to the world coordinate system: $T = [\begin{matrix} u_{x} & v_{x} & w_{x} & 0 \\ u_{the y} & v_{the y} & w_{the y} & 0 \\ u_{z} & v_{z} & w_{z} & 0 \\ 0 & 0 & 0 & 1 \end{matrix}],$

其中w_x＝N_x，w_y＝N_y，w_z＝N_z；N＝(N_x，N_y，N_z)^T为视点V、球面的球心O和场景中的点P组成的平面VPO的法向量；以O为原点，以N为z轴，以OP为y轴，以OP×N为x轴，建立局部坐标系；Where w_x = N_x , w_y = N_y , w_z = N_z ; N = (N_x , N_y , N_z )^T is the plane composed of the viewpoint V, the center O of the sphere and the point P in the scene The normal vector of VPO; with O as the origin, N as the z-axis, OP as the y-axis, and OP×N as the x-axis, establish a local coordinate system;

u_x＝v_yw_z-w_yv_z，u_y＝w_xv_z-v_xw_z，u_z＝v_xw_y-w_xv_y；u_x =v_y w_z -w_y v_z , u_y =w_x v_z -v_x w_z , u_z =v_x w_y -w_x v_y ;

v_x、v_y和v_z分别是单位矢量(P-O)/|P-O|的三个坐标分量；v_x , v_y and v_z are the three coordinate components of the unit vector (PO)/|PO| respectively;

x，y分别为球面上的点I到视点V和场景中的点P之间的距离：x＝|V-I|，y＝|I-P|；应用公式I＝T·L_I便可把L_I局部坐标系变换为世界坐标系。x and y are respectively the distances from point I on the sphere to the viewpoint V and the point P in the scene: x=|VI|, y=|IP|; apply the formula I=T L_I to localize L_I The coordinate system is transformed into the world coordinate system.

对于球面折射体而言，它依次含有如下步骤：For spherical refractors, it contains the following steps in sequence:

(1)计算各虚顶点P′： $P^{'} = V + (x + | I_{1} - I_{2} | + y) \frac{I_{1} - V}{{| I}_{1} - V |},$ (1) Calculate each virtual vertex P': $P^{'} = V + (x + | I_{1} - I_{2} | + the y) \frac{I_{1} - V}{{| I}_{1} - V |},$

其中，I₁、I₂分别是光线射到球面折射体的入射点和出射点，用公式I＝T·L_I，把I₁、I₂的局部坐标变换成世界坐标系的坐标；x，y分别为视点V到入射点I₁，以及出射点I₂到场景中的一点P的距离，即x＝|V-I₁|，y＝|I₂-P|；T为从局部坐标系到世界坐标系的变换矩阵： $T = [\begin{matrix} u_{x} & v_{x} & w_{x} & 0 \\ u_{y} & v_{y} & w_{y} & 0 \\ u_{z} & v_{z} & w_{z} & 0 \\ 0 & 0 & 0 & 1 \end{matrix}],$ 其中，Among them, I₁ and I₂ are respectively the incident point and the exit point of the light rays hitting the spherical refractor, and the local coordinates of I₁ and I₂ are transformed into the coordinates of the world coordinate system with the formula I=T L_I ; x, y are the distances from the viewpoint V to the incident point I₁ , and the exit point I₂ to a point P in the scene, that is, x=|VI₁ |, y=|I₂ -P|; T is from the local coordinate system to the world The transformation matrix of the coordinate system: $T = [\begin{matrix} u_{x} & v_{x} & w_{x} & 0 \\ u_{the y} & v_{the y} & w_{the y} & 0 \\ u_{z} & v_{z} & w_{z} & 0 \\ 0 & 0 & 0 & 1 \end{matrix}],$ in,

w_x＝N_x，w_y＝N_y，w_z＝N_z；w_x = N_x , w_y = N_y , w_z = N_z ;

N＝(N_x，N_y，N₂)^T为视点V、球面的球心O和场景中的点P组成的平面VPO的法向量；以O为坐标原点，以N为z轴，以OP为y轴，以OP×N为x轴，建立局部坐标系；N=(N_x , N_y , N₂ )^T is the normal vector of the plane VPO composed of the viewpoint V, the center O of the sphere and the point P in the scene; take O as the coordinate origin, take N as the z-axis, and take OP is the y-axis, takes OP×N as the x-axis, and establishes a local coordinate system;

所述的用递归算法来显示图形的过程，含有如下步骤：The process of displaying graphics with a recursive algorithm comprises the following steps:

算法1预处理Algorithm 1 preprocessing

第1步，对场景中的物体构造二叉空间剖分(BSP)树，如果场景中含有球形反射或折射体，则用紧密包容该球的正方体的6个面代替该球参与构造BSP树；The first step is to construct a binary space partition (BSP) tree for the objects in the scene. If the scene contains a spherical reflection or refraction body, replace the sphere with 6 faces of a cube that tightly contains the sphere to participate in the construction of the BSP tree;

第2步，收集场景中各种反射和折射体，并形成反射和折射体对象表；Step 2, collect various reflection and refraction objects in the scene, and form a reflection and refraction object table;

第3步，根据当前的视点，确定反射、折射体表中的各反射、折射体的先后顺序；由于BSP树与视点无关，因而能很快的得到反射、折射体的顺序；Step 3, according to the current viewpoint, determine the order of each reflection and refraction body in the reflection and refraction body table; since the BSP tree has nothing to do with the viewpoint, the order of reflection and refraction bodies can be quickly obtained;

第4步，计算虚顶点并生成所有的虚物体，产生虚场景；Step 4, calculate virtual vertices and generate all virtual objects, and generate virtual scenes;

算法2为折射体或反射体产生虚场景：Algorithm 2 generates virtual scenes for refractors or reflectors:

i)是否到达最大的递归层次？是则返回；i) Is the maximum level of recursion reached? is returned;

ii)如果为反射体，计算反射虚场景；如果为折射体，计算折射虚场景；ii) If it is a reflector, calculate the reflection virtual scene; if it is a refraction body, calculate the refraction virtual scene;

iii)根据视点对虚场景中的反射和折射体进行排序；iii) Sort the reflection and refraction volumes in the virtual scene according to the viewpoint;

iv)如果虚场景中还存在反射或折射体，则对虚场景中的反射、折射体递归调用本算法，转i)；否则转v)；iv) If there is still a reflection or refraction body in the virtual scene, then call this algorithm recursively for the reflection or refraction body in the virtual scene, and turn to i); otherwise, turn to v);

v)返回；v) return;

算法2有以下特点：Algorithm 2 has the following characteristics:

(1)上面的算法是一个递归算法，递归主要是针对场景中的反射、折射体进行的；(1) The above algorithm is a recursive algorithm, and the recursion is mainly for the reflection and refraction objects in the scene;

(2)对于反射体和折射体是统一处理的；(2) The reflector and refractor are treated uniformly;

(3)对于反射体，生成虚场景使用的是反射公式，对应的面片的顶点顺序要改变，即反射虚物体面片的顶点顺序与原来的顺序相反，以便确保平面的外法矢指向正确的方向；(3) For reflectors, the reflection formula is used to generate the virtual scene, and the order of vertices of the corresponding facets needs to be changed, that is, the order of vertices of the facets of the reflection virtual object is reversed from the original order, so as to ensure that the outer normal vector of the plane points correctly the direction of

(4)在任一虚场景中，都要根据视点和BSP树重新确定其中的反射和折射体的顺序，以便后面能够正确地实时显示；(4) In any virtual scene, the order of reflection and refraction bodies in it must be re-determined according to the viewpoint and BSP tree, so that it can be displayed correctly in real time later;

(5)如果场景中的反射或折射体的个数大于1算法的终止条件是递归深度不大于所给定的最大递归深度值；(5) If the number of reflection or refraction objects in the scene is greater than 1, the termination condition of the algorithm is that the recursion depth is not greater than the given maximum recursion depth value;

如果视点发生变化，对于纯反射虚场景，是不用重算的；但对于任意一个折射体及其以后的递归过程中出现的虚场景必须重新计算；下面是视点发生变化时重新计算虚场景的算法：If the viewpoint changes, there is no need to recalculate the pure reflection virtual scene; but for any refraction body and the virtual scene that appears in the subsequent recursive process, it must be recalculated; the following is the algorithm for recalculating the virtual scene when the viewpoint changes :

算法3视点位置改变时重新计算虚场景Algorithm 3 Recalculate the virtual scene when the viewpoint position changes

i)是否是折射体？i) Is it a refractor?

ii)是，调用算法2；ii) Yes, call Algorithm 2;

iii)否则，则递归调用本算法；iii) otherwise, then call this algorithm recursively;

要实现实时绘制场景，可以采用支持OpenGL编程(OpenGL-compatible)的三维图形加速卡进行硬件加速的办法；这时，我们要用到图形硬件的软件接口——OpenGL图形系统；前面的虚物体的生成，为我们实时绘制打下了基础；下面是我们使用的实时绘制算法；To achieve real-time rendering of scenes, a three-dimensional graphics accelerator card that supports OpenGL programming (OpenGL-compatible) can be used for hardware acceleration; at this time, we need to use the software interface of the graphics hardware——OpenGL graphics system; Generated, laying the foundation for our real-time rendering; the following is the real-time rendering algorithm we use;

算法4实时绘制和显示(本算法是针对真实场景中的某个反射体或折射体的)Algorithm 4 Real-time rendering and display (this algorithm is for a reflector or refractor in the real scene)

x)设置OpenGL的绘制参数(禁止颜色缓存写，禁止深度缓存写，禁止深度比较，禁止使用Alpha混合，使所绘制的模版缓冲区的值+1)；x) Set the drawing parameters of OpenGL (prohibit color buffer writing, prohibit depth buffer writing, prohibit depth comparison, prohibit using Alpha blending, and make the value of the drawn stencil buffer +1);

xi)绘制反射、折射体本身；xi) Draw reflection, refraction body itself;

xii)如果其虚场景中含有反射或折射体，则转i)，递归地绘制虚场景中的反射、折射体；xii) If the virtual scene contains reflection or refraction bodies, then turn to i), recursively draw the reflection and refraction bodies in the virtual scene;

xiii)设置OpenGL的绘制参数(使所绘制的模版缓冲区的值不变，颜色缓存可写，深度缓存可写，深度比较生效，其他的绘制参数不变)；xiii) Set the drawing parameters of OpenGL (keep the value of the drawn stencil buffer unchanged, the color buffer can be written, the depth buffer can be written, the depth comparison takes effect, and other drawing parameters remain unchanged);

xiv)在当前模板缓冲区中绘制当前虚场景中的其它虚物体；xiv) Draw other virtual objects in the current virtual scene in the current stencil buffer;

xv)设置OpenGL的绘制参数(颜色缓存可写，深度缓存可写，深度比较生效，Alpha混合生效，使所绘制的模版缓冲区的值-1)；xv) Set the drawing parameters of OpenGL (the color buffer can be written, the depth buffer can be written, the depth comparison is valid, the Alpha mixing is valid, and the value of the drawn template buffer is -1);

xvi)绘制反射、折射体本身；xvi) Draw the reflection and refraction body itself;

xvii)设置OpenGL的绘制参数(恢复深度缓存可写，颜色缓存可写，禁止Alpha混合，禁止摸板操作)；xvii) Set the drawing parameters of OpenGL (restore the depth buffer to be writable, the color buffer to be writable, prohibit Alpha blending, and prohibit touch panel operation);

xviii)返回。xviii) Return.

实验证明：它达到了预期目的。The experiment proves that it has achieved the expected purpose.

附图说明Description of drawings

图1利用光线跟踪计算虚顶点的示意图。Figure 1 is a schematic diagram of computing virtual vertices using ray tracing.

图2任意平面反射的示意图。Figure 2. Schematic diagram of arbitrary plane reflection.

图3折射第一种情况--场景在折射体外的示意图。Figure 3 The first case of refraction—a schematic diagram of the scene outside the refractor.

图4折射第二种情况--场景在折射体内的示意图。Figure 4 shows the second case of refraction—a schematic diagram of the scene inside the refractor.

图5折射面相互垂直的三维折射光路图。Figure 5 is a three-dimensional refraction light path diagram in which the refraction planes are perpendicular to each other.

图6球面反射的光路示意图。Figure 6 Schematic diagram of the optical path of spherical reflection.

图7球面折射的光路示意图。Figure 7 Schematic diagram of the optical path of spherical refraction.

图8确定球面的入射点和出射点示意图。Fig. 8 is a schematic diagram of determining the incident point and the outgoing point of the spherical surface.

图9方盒子(a)及其虚物体(b)示意图。Figure 9 is a schematic diagram of a square box (a) and its virtual object (b).

图10为算法1预处理框图。Figure 10 is a block diagram of Algorithm 1 preprocessing.

图11为算法2平面折射体或反射体产生虚场景的程序流程框图。Fig. 11 is a block diagram of the procedure for generating a virtual scene by a planar refractor or reflector in Algorithm 2.

图12为算法3视点位置改变时重新计算虚场景的程序流程框图。Fig. 12 is a flow chart of the procedure for recalculating the virtual scene when the viewpoint position of Algorithm 3 changes.

图13为算法4实时绘制和显示的程序流程框图。Fig. 13 is a program flow diagram of real-time drawing and display of Algorithm 4.

具体实施方式Detailed ways

1、基本思想1. Basic idea

如图1所示，光线L从视点A出发，经过折射和反射后到达V点，这是光线跟踪的基本思路。然而给定任意一点V，要准确地得到从视点A出发经过折射到达V点的光线L’，在理论上却是很难计算的，因为折射问题一般是非线性的。As shown in Figure 1, light L starts from viewpoint A and reaches point V after refraction and reflection. This is the basic idea of ray tracing. However, given any point V, it is theoretically difficult to accurately obtain the ray L' from the viewpoint A to the point V through refraction, because the refraction problem is generally nonlinear.

当一条L经过若干次反射或折射，与某一物体的平面M相交于V点时，与传统光线跟踪算法不同，我们不是利用光照模型计算对应象素点的颜色值，而是计算点V的光学映射虚顶点V’。假设光线L经过若干次反射或折射到达V时，经过的路径的长度总和为：d＝d₁+d₂+Λ+d₅When a piece of L passes through several reflections or refractions and intersects the plane M of an object at point V, unlike the traditional ray tracing algorithm, we do not use the illumination model to calculate the color value of the corresponding pixel point, but calculate the color value of the point V Optically map the virtual vertex V'. Assume that when the ray L reaches V after several reflections or refractions, the sum of the lengths of the paths passed is: d=d₁ +d₂ +Λ+d₅

则虚顶点V’的计算公式为： $V^{'} = A + d \frac{B - A}{| B - A |},$ 其中A是视点，B是投影平面上一个采样点。这就是我们提出的“光学映射虚对象的概念”。Then the calculation formula of the virtual vertex V' is: $V^{'} = A + d \frac{B - A}{| B - A |},$ Where A is the viewpoint, and B is a sampling point on the projection plane. This is the "Concept of Optical Mapping Virtual Objects" proposed by us.

对于被反射或折射的多面体，我们首先计算出每个顶点的虚顶点，然后根据拓扑关系依次将虚顶点连接成虚物体的边，最终形成反射或折射的光学映射虚物体(简称虚物体)。例如一个方盒子，见图9(a)，其顶点P₁，P₂，...，P₈的虚顶点依次为P′₁，p′₂，...，P′₈，则我们可以得到该方盒子对应的虚物体，如图9(b)所示。在显示图形时，将这些虚物体投影到反射或折射表面上。这个过程可以递归地进行，从而得到与光线跟踪类似的图像效果。为了得到高质量的真实感图像，被反射或折射的平面的尺寸不能太大，否则应当将平面细分成更小的矩形或三角形。对于场景中被反射或折射的曲面物体，则应当先将曲面离散成若干小平面，用多面体近似表示曲面物体。For the reflected or refracted polyhedron, we first calculate the virtual vertex of each vertex, and then connect the virtual vertices to form the edges of the virtual object in turn according to the topological relationship, and finally form a reflective or refracted optically mapped virtual object (virtual object for short). For example, a square box, see Fig. 9(a), the virtual vertices of its vertices P₁ , P₂ , ..., P₈ are P′₁ , p′₂ , ..., P′₈ in sequence, then we can Get the virtual object corresponding to the square box, as shown in Figure 9(b). Project these virtual objects onto reflective or refractive surfaces when displaying graphics. This process can be done recursively, resulting in image effects similar to ray tracing. In order to obtain high-quality realistic images, the size of the reflected or refracted plane should not be too large, otherwise the plane should be subdivided into smaller rectangles or triangles. For the surface object that is reflected or refracted in the scene, the surface should be discretized into several small planes first, and the surface object should be approximated by a polyhedron.

2、虚顶点的计算公式2. Calculation formula of virtual vertices

对于平面反射问题，我们可以采用类似光束跟踪算法的思想计算各个顶点的虚顶点：For the plane reflection problem, we can use an idea similar to the beam tracing algorithm to calculate the virtual vertices of each vertex:

假设有一个过点R＝[V_x，V_y，V_z，1]^T的平面，如图2所示，其单位法矢量为N＝[a，b，c，0]^T，N^TN＝1，其平面方程为Suppose there is a plane passing through the point R=[V_x , V_y , V_z , 1]^T , as shown in Figure 2, its unit normal vector is N=[a, b, c, 0]^T , N^T N =1, its plane equation is

ax+by+cz+d＝0ax+by+cz+d=0

其中，d＝-N^T R，V为视点。Among them, d=-N^T R, V is the viewpoint.

三维场景中的任意一个点P＝[P_x，P_y，P_z，1]^T相对于该平面作反射变换后到达P′＝[P′_x，P′_y，P′_z，1]^T。根据几何关系，可以得到：Any point P=[P_x , P_y , P_z , 1]^T in the three-dimensional scene reaches P′=[P′_x , P′_y , P′_z , 1]^T after reflection transformation relative to the plane . According to the geometric relationship, we can get:

P′＝T_mPP'=T_m P

其中， $T_{m} = [\begin{matrix} 1 - {2 a}^{2} & - 2 ab & - 2 ac & - 2 ad \\ - 2 ab & 1 - 2 b^{2} & - 2 bc & - 2 bd \\ - 2 ac & - 2 bc & 1 - 2 c^{2} & - 2 cd \\ 0 & 0 & 0 & 1 \end{matrix}],$ in, $T_{m} = [\begin{matrix} 1 - {2 a}^{2} & - 2 ab & - 2 ac & - 2 ad \\ - 2 ab & 1 - 2 b^{2} & - 2 bc & - 2 bd \\ - 2 ac & - 2 bc & 1 - 2 c^{2} & - 2 cd \\ 0 & 0 & 0 & 1 \end{matrix}],$

P′是P点的反射虚顶点。P' is the reflection virtual vertex of point P.

折射问题比平面反射问题要复杂得多。平面折射体的非线性折射有两种情况：物体在折射体外(如图3所示)和物体在折射体内(见图4)两种。下面我们分别予以讨论。Refraction problems are much more complicated than planar reflection problems. There are two cases of nonlinear refraction of a plane refractor: the object is outside the refractor (as shown in Figure 3) and the object is inside the refractor (see Figure 4). Let's discuss them separately below.

1)二维平面折射1) Two-dimensional plane refraction

(a)物体在折射体外(a) The object is outside the refractor

如图3所示，V是视点，P是场景中任意选取的一点，它在折射体的外面，P′是与P对应的虚顶点。求其虚物体的公式推导如下：As shown in Figure 3, V is the viewpoint, P is an arbitrarily selected point in the scene, which is outside the refractor, and P′ is the virtual vertex corresponding to P. The formula for finding its virtual object is derived as follows:

已知：w₁，w₂，w₃，h，令η＝Sinα/Sinβ＝η₂/η₁，ξ＝1+w₃/w₁，根据几何关系，可得Given: w₁ , w₂ , w₃ , h, let η=Sinα/Sinβ=η₂ /η₁ , ξ=1+w₃ /w₁ , according to the geometric relationship, we can get

Ad⁴+Bd³+Cd²+Dd+E＝0 (1)Ad⁴ +Bd³ +Cd² +Dd+E=0 (1)

其中，in,

A＝(1-η²)ξ²，A=(1-η² )ξ² ,

B＝2η²hξ-2hξ，B=2η² hξ-2hξ,

C＝h²+w₂²-η²h²-w₁²η²ξ²，C=h² +w₂² -η² h² -w₁² η² ξ² ,

D＝2η²hξw₁²，D=2η² hξw₁² ,

E＝-w₁²η²h²。E=-w₁² η² h² .

从(1)式中可以解出d。根据d的值，然后可以计算出折射光线和折射平面的交点I₁和I₂，从而求出虚顶点P′。From (1) formula can solve d. From the value of d, the intersection points I₁ and I₂ of the refracted ray and the refracted plane can then be calculated, thereby finding the virtual vertex P'.

虚顶点P′求解过程如下：The solution process of the virtual vertex P' is as follows:

(1)连接V和P，求出VP与平面的交点U： $U = V - \frac{C_{3} + C^{T} V}{C^{T} (P - V)} (P - V),$ (1) Connect V and P, find the intersection point U between VP and the plane: $u = V - \frac{C_{3} + C^{T} V}{C^{T} (P - V)} (P - V),$

其中，该平面的方程为C₀x+C₁y+C₂z+C₃＝0，另外，C＝(C₀，C₁，C₂)^T；Wherein, the equation of the plane is C₀ x+C₁ y+C₂ z+C₃ =0, in addition, C=(C₀ , C₁ , C₂ )^T ;

(2)Q＝V-w₁N； $(3) - - - I_{1} = Q + d \frac{U - Q}{| U - Q |} .$ (2) Q=Vw₁ N; $(3) - - - I_{1} = Q + d \frac{u - Q}{| u - Q |} .$

同理，可以求出I₂。Similarly, I₂ can be calculated.

令l＝|V-I₁|+|I₁-I₂|+|I₂-P|，则P点的虚顶点 $P^{'} = V + l \frac{I_{1} - V}{| I_{1} - V |} .$ Let l＝|VI₁ |+|I₁ -I₂ |+|I₂ -P|, then the virtual vertex of point P $P^{'} = V + l \frac{I_{1} - V}{| I_{1} - V |} .$

我们用光线跟踪的方法产生了两组点，然后用上面的公式，反算I₁，显然，如果I₁相同，则I₂也相同，具体的结果如下表所示。光线跟踪产生的点用公式反算的点视点V 场景中的点P I₁ I₂ I₁ I₂ xyz -3.486133-91.011276-30.972000 -286.265348137.319548-64.033415 -247.000000110.000000-59.442668 -270.903693150.000000-62.237392 -247.000000110.000000-59.442668 -270.903693150.000000-62.237392 xyz -3.486133-91.011276-30.972000 -275.475363136.992740-59.345723 237.000000110.000000-55.332001 -260.364890150.000000-57.769409 237.000000110.000000-55.332001 -260.364890150.000000-57.769409We generated two sets of points by ray tracing, and then used the above formula to inversely calculate I₁ . Obviously, if I₁ is the same, then I₂ is also the same. The specific results are shown in the table below. Points generated by ray tracing Points inversely calculated using the formula Viewpoint V Point P in the scene I₁ I₂ I₁ I₂ xyz -3.486133-91.011276-30.972000 -286.265348137.319548-64.033415 -247.000000110.000000-59.442668 -270.903693150.000000-62.237392 -247.000000110.000000-59.442668 -270.903693150.000000-62.237392 xyz -3.486133-91.011276-30.972000 -275.475363136.992740-59.345723 237.000000110.000000-55.332001 -260.364890150.000000-57.769409 237.000000110.000000-55.332001 -260.364890150.000000-57.769409

(b)物体在折射体内(b) The object is inside the refractor

如鱼缸中的鱼，物体(鱼)是在折射体(鱼缸)内面。这种情况的计算公式应该与第一钟情况是不同的。如图4所示，图中V是视点，P是场景中任意选取的点，它在折射体内部，P′是P对应的虚顶点。类似地，我们可以根据几何关系得到如下一元四次方程：Like the fish in the fish tank, the object (fish) is inside the refracting body (fish tank). The calculation formula for this case should be different from the first case. As shown in Figure 4, V in the figure is the viewpoint, P is an arbitrarily selected point in the scene, which is inside the refractor, and P′ is the virtual vertex corresponding to P. Similarly, we can get the following one-variable quartic equation according to the geometric relationship:

Ad⁴+Bd³+Cd²+Dd+E＝0 (2)Ad⁴ +Bd³ +Cd² +Dd+E=0 (2)

其中，in,

A＝η²-1，A=η² -1,

B＝-2hA，B=-2hA,

C＝h²A+η²w₁²-w₂²，C=h² A+η² w₁² -w₂² ,

D＝-2η²hw₁²，D=-2η² hw₁² ,

E＝w₁²η²h²。E=w₁² η² h² .

从(2)式中可以解出d，然后便可以计算出折射光线和折射平面的交点I，从而求出虚顶点P′。虚顶点P′求解过程如下：From formula (2), d can be solved, and then the intersection point I of the refracted ray and the refracted plane can be calculated, so as to obtain the virtual vertex P'. The solution process of the virtual vertex P' is as follows:

(1)连接V和P，VP与镜平面相交于U，U可照搬前面的公式得到；(1) Connect V and P, VP intersects the mirror plane at U, and U can be obtained by copying the previous formula;

(2)Q＝V-w₁N； $(3) - - - I = Q + d \frac{U - Q}{| U - Q |};$ (2) Q=Vw₁ N; $(3) - - - I = Q + d \frac{u - Q}{| u - Q |};$

$(4) - - - p^{'} = V + l \frac{I - V}{| I - V |},$ 其中，l＝|V-I|+|I-P|。 $(4) - - - p^{'} = V + l \frac{I - V}{| I - V |},$ Among them, l=|VI|+|IP|.

我们用光线跟踪的方法产生了两组点，然后用上面的公式，反算出交点I。具体的结果如下表所示。光线跟踪产生的点用公式反算的点视点V 场景中的点P I I xyz -3.486133-91.011276-30.972000 -286.265348137.319548-64.033415 -252.000000110.000000-61.498001 -252.000000110.000000-61.498001 xyz -3.486133-91.011276-30.972000 -275.475363136.992740-59.345723 -237.000000110.000000-55.332001 -237.000000110.000000-55.332001We use ray tracing method to generate two sets of points, and then use the above formula to inversely calculate the intersection point I. The specific results are shown in the table below. Points generated by ray tracing Points inversely calculated using the formula Viewpoint V Point P in the scene I I xyz -3.486133-91.011276-30.972000 -286.265348137.319548-64.033415 -252.000000110.000000-61.498001 -252.000000110.000000-61.498001 xyz -3.486133-91.011276-30.972000 -275.475363136.992740-59.345723 -237.000000110.000000-55.332001 -237.000000110.000000-55.332001

(c)解的选取(c) Selection of solutions

显然，(1)式和(2)式都是多解的方程，它们都至多有4个实根。因此，解方程后，将要对解的结果进行选择。根据光学的原理，光在介质中从一点到达另一点时，将选择最短路径传播。这样，我们连接视点V和场景中的点P，得到一条直线，离该直线最近的解，就是我们所求的点。Obviously, both equations (1) and (2) are multi-solution equations, and they both have at most 4 real roots. Therefore, after solving the equation, a selection will be made on the result of the solution. According to the principle of optics, when light travels from one point to another in a medium, it will choose the shortest path to propagate. In this way, we connect the viewpoint V and the point P in the scene to get a straight line, and the solution closest to the straight line is the point we are looking for.

2)三维平面折射2) Three-dimensional plane refraction

如图5，已知：视点V，场景中任意选取的点P，折射率η，AD＝a，VA＝z，PF＝b， $e = | {(\overset{&RightArrow;}{VP})}_{x} |, f = | {(\overset{&RightArrow;}{VP})}_{y} |, g = | {(\overset{&RightArrow;}{VP})}_{z} | .$ 在图5中，光线从视点V出发，经过介质上表面I₁点折射进入介质，然后到达介质右侧面，从I₂点折射进入空气，并最终达到场景中的点P。As shown in Figure 5, it is known that: viewpoint V, point P randomly selected in the scene, refractive index η, AD=a, VA=z, PF=b, $e = | {(\overset{&Right Arrow;}{VP})}_{x} |, f = | {(\overset{&Right Arrow;}{VP})}_{the y} |, g = | {(\overset{&Right Arrow;}{VP})}_{z} | .$ In Figure 5, light starts from the viewpoint V, refracts through the upper surface of the medium at point_I1 and enters the medium, then reaches the right side of the medium, refracts from point_I2 into the air, and finally reaches point P in the scene.

由Snell折射定律和几何关系，我们就可以得到下面的两个方程：From Snell's law of refraction and geometric relations, we can get the following two equations:

根据上面的两个方程可以求出x和y，然后由x、y以及z和折射率η的值就可以依次算出I₁和I₂的三维坐标，从而得到P的虚顶点P’的位置。According to the above two equations, x and y can be obtained, and then the three-dimensional coordinates of I₁ and I₂ can be calculated sequentially from the values of x, y, z and the refractive index η, so as to obtain the position of the virtual vertex P' of P.

(3)和(4)式是一个二元4次非线性方程组，为了提高计算速度，我们采用下面的方法进行近似处理：(3) and (4) are a binary quadruple nonlinear equation system, in order to improve the calculation speed, we use the following method for approximate processing:

首先，用下式计算出d：f₀+f₁d+f₂d²+f₃d³+f₄d⁴＝0，忽略d的高阶(＞2)项，得First, use the following formula to calculate d: f₀ +f₁ d+f₂ d² +f₃ d³ +f₄ d⁴ =0, ignoring the high-order (>2) terms of d, we get

f₀+f₁d+f₂d²＝0，f₀ +f₁ d+f₂ d² =0,

其中， $f_{0} = {(\frac{1}{4} C_{7} - \frac{1}{4} C_{1} - C_{2} C_{1})}^{2} {(C_{4} - C_{7})}^{2} - {2 b}^{2} C_{1} (C_{7} - C_{1}) (C_{4} - C_{7}) (\frac{1}{4} C_{7} - \frac{1}{4} C_{1} + C_{2} C_{1}) +$ $b^{4} {C_{1}}^{2} {(C_{7} - C_{1})}^{2},$ $f_{1} = - 2 C_{9} b^{2} C_{1} (C_{4} - C_{7}) (C_{2} C_{5} + \frac{1}{4} C_{6} - \frac{1}{4} C_{5} + C_{7} - C_{1}) + {2 b}^{4} {C_{1}}^{2} C_{9} (C_{6} - C_{5}) -$ ${2 C_{9} b^{2} C_{1} (2 C_{5} - C_{6}) + [2 C_{9} b^{2} C_{5} + (2 C_{6} - {2 C}_{5}) b^{2} C_{1}] C_{8}} (\frac{1}{4} C_{7} - \frac{1}{4} C_{1} + C_{2} C_{1}) +$ ${2 b}^{4} C_{1} C_{5} {(C_{7} - C_{1})}^{2} + 2 (C_{4} - C_{7}) ({2 C}_{5} - C_{6}) {(\frac{1}{4} C_{7} - \frac{1}{4} C_{1} - C_{2} C_{1})}^{2} +$ $2 (\frac{1}{4} C_{7} - \frac{1}{4} C_{1} - C_{2} C_{1}) {(C_{4} - C_{7})}^{2} (C_{7} - C_{1} - C_{2} C_{5} + \frac{1}{4} C_{6} - \frac{1}{4} C_{5}),$ $f_{2} = {(\frac{1}{4} C_{7} - \frac{1}{4} C_{1} - C_{2} C_{1})}^{2} [2 (C_{4} - C_{7}) (2 - η^{2}) + {({2 C}_{5} - C_{6})}^{2}] + 4 (\frac{1}{4} C_{7} - \frac{1}{4} C_{1} - C_{2} C_{1}) (\frac{1}{4} C_{6} -$ $\frac{1}{4} C_{5} - C_{2} C_{5} + C_{7} - C_{1}) (C_{4} - C_{7}) ({2 C}_{5} - C_{6}) + [2 (\frac{C_{7} - C_{1}}{4} - C_{2} C_{1}) (C_{7} - C_{1} - C_{2} + \frac{1}{4} η^{2} +$ $C_{6} - C_{5} - \frac{1}{4}) + {(C_{7} - C_{1} - C_{2} C_{5} + \frac{C_{6} - C_{5}}{4})}^{2}] {(C_{4} - C_{7})}^{2} - 2 (C_{7} - C_{1}) b^{2} C_{1} (C_{4} - C_{7}) (- \frac{1}{4} +$ $C_{2} + \frac{1}{4} η^{2} + C_{6} - C_{5} + C_{7} - C_{1}) - {(2 C_{7} - {2 C}_{1}) b^{2} C_{1} ({2 C}_{5} - C_{6}) + (C_{4} - C_{7}) [({2 C}_{7} - {2 C}_{1}) b^{2} C_{5} +$ $2 {(C_{6} - C_{5}) b}^{2} C_{1}]} (C_{2} C_{5} + \frac{C_{6} - C_{5}}{4} + C_{7} - C_{1}) - {2 (C_{7} - C_{1}) b^{2} C_{1} ({2 - η}^{2}) + [2 (C_{7} - C_{1}) b^{2} C_{5} +$ $2 (C_{6} - C_{5}) b^{2} C_{1}] ({2 C}_{5} - C_{6}) + [2 (C_{7} - C_{1}) b^{2} + 2 (C_{6} - C_{5}) b^{2} C_{5} + ({2 η}^{2} - 2) b^{2} C_{1}] (C_{4} - C_{7})} (\frac{1}{4} C_{7} +$ $C_{2} C_{1} - \frac{1}{4} C_{1}) + b^{4} {C_{1}}^{2} [2 {(C_{7} - C_{1}) (η^{2} - 1) + (C_{6} - C_{5})}^{2}] + {4 b}^{4} C_{1} C_{5} (C_{7} - C_{1}) (C_{6} - C_{5}) +$ $b^{4} ({2 C}_{1} + {C_{5}}^{2}) {(C_{7} - C_{1})}^{2} .$ in, $f_{0} = {(\frac{1}{4} C_{7} - \frac{1}{4} C_{1} - C_{2} C_{1})}^{2} {(C_{4} - C_{7})}^{2} - {2 b}^{2} C_{1} (C_{7} - C_{1}) (C_{4} - C_{7}) (\frac{1}{4} C_{7} - \frac{1}{4} C_{1} + C_{2} C_{1}) +$ $b^{4} {C_{1}}^{2} {(C_{7} - C_{1})}^{2},$ $f_{1} = - 2 C_{9} b^{2} C_{1} (C_{4} - C_{7}) (C_{2} C_{5} + \frac{1}{4} C_{6} - \frac{1}{4} C_{5} + C_{7} - C_{1}) + {2 b}^{4} {C_{1}}^{2} C_{9} (C_{6} - C_{5}) -$ ${2 C_{9} b^{2} C_{1} (2 C_{5} - C_{6}) + [2 C_{9} b^{2} C_{5} + (2 C_{6} - {2 C}_{5}) b^{2} C_{1}] C_{8}} (\frac{1}{4} C_{7} - \frac{1}{4} C_{1} + C_{2} C_{1}) +$ ${2 b}^{4} C_{1} C_{5} {(C_{7} - C_{1})}^{2} + 2 (C_{4} - C_{7}) ({2 C}_{5} - C_{6}) {(\frac{1}{4} C_{7} - \frac{1}{4} C_{1} - C_{2} C_{1})}^{2} +$ $2 (\frac{1}{4} C_{7} - \frac{1}{4} C_{1} - C_{2} C_{1}) {(C_{4} - C_{7})}^{2} (C_{7} - C_{1} - C_{2} C_{5} + \frac{1}{4} C_{6} - \frac{1}{4} C_{5}),$ $f_{2} = {(\frac{1}{4} C_{7} - \frac{1}{4} C_{1} - C_{2} C_{1})}^{2} [2 (C_{4} - C_{7}) (2 - η^{2}) + {({2 C}_{5} - C_{6})}^{2}] + 4 (\frac{1}{4} C_{7} - \frac{1}{4} C_{1} - C_{2} C_{1}) (\frac{1}{4} C_{6} -$ $\frac{1}{4} C_{5} - C_{2} C_{5} + C_{7} - C_{1}) (C_{4} - C_{7}) ({2 C}_{5} - C_{6}) + [2 (\frac{C_{7} - C_{1}}{4} - C_{2} C_{1}) (C_{7} - C_{1} - C_{2} + \frac{1}{4} η^{2} +$ $C_{6} - C_{5} - \frac{1}{4}) + {(C_{7} - C_{1} - C_{2} C_{5} + \frac{C_{6} - C_{5}}{4})}^{2}] {(C_{4} - C_{7})}^{2} - 2 (C_{7} - C_{1}) b^{2} C_{1} (C_{4} - C_{7}) (- \frac{1}{4} +$ $C_{2} + \frac{1}{4} η^{2} + C_{6} - C_{5} + C_{7} - C_{1}) - {(2 C_{7} - {2 C}_{1}) b^{2} C_{1} ({2 C}_{5} - C_{6}) + (C_{4} - C_{7}) [({2 C}_{7} - {2 C}_{1}) b^{2} C_{5} +$ $2 {(C_{6} - C_{5}) b}^{2} C_{1}]} (C_{2} C_{5} + \frac{C_{6} - C_{5}}{4} + C_{7} - C_{1}) - {2 (C_{7} - C_{1}) b^{2} C_{1} ({2 - η}^{2}) + [2 (C_{7} - C_{1}) b^{2} C_{5} +$ $2 (C_{6} - C_{5}) b^{2} C_{1}] ({2 C}_{5} - C_{6}) + [2 (C_{7} - C_{1}) b^{2} + 2 (C_{6} - C_{5}) b^{2} C_{5} + ({2 η}^{2} - 2) b^{2} C_{1}] (C_{4} - C_{7})} (\frac{1}{4} C_{7} +$ $C_{2} C_{1} - \frac{1}{4} C_{1}) + b^{4} {C_{1}}^{2} [2 {(C_{7} - C_{1}) (η^{2} - 1) + (C_{6} - C_{5})}^{2}] + {4 b}^{4} C_{1} C_{5} (C_{7} - C_{1}) (C_{6} - C_{5}) +$ $b^{4} ({2 C}_{1} + {C_{5}}^{2}) {(C_{7} - C_{1})}^{2} .$

在上面的3个式子当中， $C_{1} = {(a - \frac{1}{2})}^{2}, C_{2} = {(g - z)}^{2}, C_{3} = C_{1} + z^{2}, C_{4} = {2 C}_{1} + z^{2}, C_{5} = - 2 a + 1,$ $C_{6} = η^{2} C_{5}, C_{7} = η^{2} C_{3}, C_{8} = C_{4} - C_{7}, C_{9} = C_{7} - C_{1} .$ Among the above three formulas, $C_{1} = {(a - \frac{1}{2})}^{2}, C_{2} = {(g - z)}^{2}, C_{3} = C_{1} + z^{2}, C_{4} = {2 C}_{1} + z^{2}, C_{5} = - 2 a + 1,$ $C_{6} = η^{2} C_{5}, C_{7} = η^{2} C_{3}, C_{8} = C_{4} - C_{7}, C_{9} = C_{7} - C_{1} .$

然后将d代入下式，便可以计算出当x＝0时y的值，我们把它记为y₀，即Then substituting d into the following formula can calculate the value of y when x=0, we record it as y₀ , that is

y₀＝a-(0.5+d)。y₀ =a-(0.5+d).

通常d是一个很小的量，|d|≤0.5；在上面的计算中，我们忽略了d的高阶(≥3)项，如果保留d的更高阶(3、4阶)项，可以提高计算精度，但是这也会使计算量略有增加。将(4)式在x＝0点展开并作线性近似：Usually d is a very small quantity, |d|≤0.5; in the above calculation, we ignore the higher-order (≥3) items of d, if we keep the higher-order (3, 4th) items of d, we can Improve calculation accuracy, but this will also slightly increase the amount of calculation. Expand the formula (4) at x=0 and make a linear approximation:

y＝y₀+y₁x，y=y₀ +y₁ x,

其中，

in,

将y＝y₀+y₁x代入(3)式，得

Substituting y=y₀ +y₁ x into formula (3), we get

从上式中求出x，并将x的值代入式(4)并求解一个关于y的四次方程，该方程经过整理为：Find x from the above formula, and substitute the value of x into formula (4) and solve a quartic equation about y, which is organized as:

H₄y⁴+H₃y³+H₂y²+H₁y+H₀＝0，H₄ y⁴ +H₃ y³ +H₂ y² +H₁ y+H₀ =0,

其中，in,

H₄＝e²(2-η²)，H₄ =e² (2-η² ),

H₃＝-2aex(2-η²)，H₃ =-2aex(2-η² ),

H₂＝a²x²(2-η²)+e²(1-η²)(x²+z²)-b²x²，H₂ =a² x² (2-η² )+e² (1-η² )(x² +z² )-b² x² ,

H₁＝-2aex(1-η²)(x²+z²)，H₁ =-2aex(1-η² )(x² +z² ),

H₀＝a²x²(1-η²)(x²+z²)。H₀ =a² x² (1-η² )(x² +z² ).

再由x、y和z以及η可以计算出点I₁和I₂的三维坐标，从而求出虚顶点P′。Then the three-dimensional coordinates of points I₁ and I₂ can be calculated from x, y, z and η, so as to obtain the virtual vertex P'.

由式(3)和式(4)组成的方程组来求解x和y的时候，还有另一种方案：在前面得到y₀后，将(3)式在x＝0点展开并作线性近似，得到：When solving x and y by the equation system composed of formula (3) and formula (4), there is another scheme: after obtaining y₀ in the front, expand the formula (3) at x=0 and make a linear Approximately, we get:

y＝y₀+y₁x，y=y₀ +y₁ x,

其中， $y_{1} = \frac{(η^{2} - 1) y_{0}^{2} + η^{2} z^{2}}{e (η^{2} - 1) y_{0}};$ in, ${the y}_{1} = \frac{(η^{2} - 1) {the y}_{0}^{2} + η^{2} z^{2}}{e (η^{2} - 1) {the y}_{0}};$

然后，将y＝y₀+y₁x代入(4)式，整理得到Then, substituting y=y₀ +y₁ x into the formula (4), we get

T₄x⁴+T₃x³+T₂x²+T₁x+T₀＝0，T₄ x⁴ +T₃ x³ +T₂ x² +T₁ x+T₀ = 0,

其中

e^{2} y_{0}^{2} [(1 - η^{2}) + (2 - η^{2}) y_{1}^{2}] - b^{2} y_{0}^{2},

从上式中求出x，并将x的值代入式(3)，可直接求解出y：

y = &PlusMinus; \sqrt{\frac{x^{2} + \frac{{(g - z)}^{2} x^{2}}{{(e - x)}^{2}} - η^{2} (x^{2} + z^{2})}{η^{2} - 1}} .

in

e^{2} {the y}_{0}^{2} [(1 - η^{2}) + (2 - η^{2}) {the y}_{1}^{2}] - b^{2} {the y}_{0}^{2},

Calculate x from the above formula, and substitute the value of x into formula (3), then y can be directly solved:

the y = &PlusMinus; \sqrt{\frac{x^{2} + \frac{{(g - z)}^{2} x^{2}}{{(e - x)}^{2}} - η^{2} (x^{2} + z^{2})}{η^{2} - 1}} .

在后面的计算实验中采用的是前一种方案。The former scheme is adopted in the subsequent calculation experiments.

具体计算I₁、I₂及虚顶点P’的过程如下：：The specific calculation process of I₁ , I₂ and virtual vertex P' is as follows:

a).求I₁a). Find I₁

设物体上的点是P，视点是V，入射面外法向量n₁，出射面外法向量n₂，入射面与出射面垂直，n₁，n₂是单位向量。局部坐标系的基是e_x，e_y，e_z，其中e_y＝n_z，e_x＝-n₁，e_y叉乘e_z，再单位化可得e_x。Suppose the point on the object is P, the viewpoint is V, the normal vector outside the incident plane n₁ , the normal vector outside the exit plane n₂ , the incident plane is perpendicular to the exit plane, n₁ and n₂ are unit vectors. The basis of the local coordinate system is e_x , e_y , e_z , where e_y = n_z , e_x = -n₁ , e_y is cross-multiplied by e_z , and then unitized to obtain e_x .

计算出的x，y，z是局部坐标系下的坐标。设dx，dy，dz是I₁点相对于视点的偏移量，有：The calculated x, y, z are the coordinates in the local coordinate system. Let dx, dy, dz be the offset of point I₁ relative to the viewpoint, there are:

dx＝xe_x，dx=xe_x ,

dy＝ye_y，dy=ye_y ,

dz＝ze_z，dz=ze_z ,

则I₁＝V+dx+dy+dz。Then I₁ =V+dx+dy+dz.

b).求I₂b). Find I₂

已知入射光线方向矢量IN＝I₁-V，折射面法矢量n₁，折射率η，可计算折射光线方向矢量OUT。由折射光线上一点I₁以及其方向，和出射面法向量n₂及面上一点，可以求出折射光线与出射平面的交点I₂。我们可以给出I₂的公式如下： $I_{2} = I_{1} - n_{1} C \sqrt{1 - \frac{x^{2} + y^{2}}{η^{2} (x^{2} + y^{2} + z^{2})}} - \hat{e} \frac{C \sqrt{x^{2} + y^{2}}}{η \sqrt{x^{2} + y^{2} + z^{2}}},$ Knowing the incident ray direction vector IN=I₁ -V, the normal vector n₁ of the refracted surface, and the refractive index η, the refracted ray direction vector OUT can be calculated. From the point I₁ on the refracted ray and its direction, the normal vector n₂ of the exit surface and a point on the surface, the intersection point I₂ of the refracted ray and the exit plane can be obtained. We can give the formula for_I2 as follows: $I_{2} = I_{1} - {no}_{1} C \sqrt{1 - \frac{x^{2} + {the y}^{2}}{η^{2} (x^{2} + {the y}^{2} + z^{2})}} - \hat{e} \frac{C \sqrt{x^{2} + {the y}^{2}}}{η \sqrt{x^{2} + {the y}^{2} + z^{2}}},$

其中 $\hat{e} = \frac{V - I_{1} - n_{1} [({V - I}_{1}) \cdot n_{1}]}{| V - I_{1} - n_{1} [({V - I}_{1}) \cdot n_{1}] |}, C = \frac{η (a - y)}{y} \sqrt{x^{2} + y^{2} + z^{2}} .$ in $\hat{e} = \frac{V - I_{1} - {no}_{1} [({V - I}_{1}) &Center Dot; {no}_{1}]}{| V - I_{1} - {no}_{1} [({V - I}_{1}) &Center Dot; {no}_{1}] |}, C = \frac{η (a - the y)}{the y} \sqrt{x^{2} + {the y}^{2} + z^{2}} .$

c).求P’c). Find P'

从视点到物点，光线走过的距离是d＝‖V-I₁‖I₁-I₂‖+‖I₂-P‖，于可以得到虚顶点P’的计算公式： $P^{,} = V + \frac{d (I_{1} - V)}{| | I_{1} - V | |} .$ From the viewpoint to the object point, the distance traveled by the light is d=‖VI₁ ‖I₁ -I₂ ‖+‖I₂ -P‖, so the calculation formula of the virtual vertex P' can be obtained: $P^{,} = V + \frac{d (I_{1} - V)}{| | I_{1} - V | |} .$

我们用光线跟踪的方法产生了两组点，然后用上面的公式，反算I₁，显然，如果I₁相近，则I₂也相近。具体的结果如下表所示，其中ε为相对误差，即：用近似公式反算的虚顶点P’到精确的虚顶点p’的距离与视点到虚顶点的距离之比We use ray tracing to generate two sets of points, and then use the above formula to inversely calculate I₁ . Obviously, if I₁ is similar, then I₂ is also similar. The specific results are shown in the following table, where ε is the relative error, that is, the ratio of the distance from the virtual vertex P' to the exact virtual vertex p' calculated by the approximate formula and the distance from the viewpoint to the virtual vertex

ε＝|P′-p′|/|V-p′|。光线跟踪产生的点用公式反算的点 V P I₁ I₂ p’ I₁ I₂ P’ ε 10010050 217.123957210.684713102.631579 17515080 200.000000176.81417590.000000 200.000000176.81417590.000000 174.540108150.00000079.788060 200.000000177.39973689.962460 236.239496191.386704104.4446530.002957 10610656 217.123957210.249311106.231579 18115686 200.000000176.37877393.600000 235.378947192.252632107.751579 173.321464150.00000083.009974 200.000000178.30877493.713641 235.760911190.809209108.0612390.009305ε=|P'-p'|/|Vp'|. Points generated by ray tracing Points inversely calculated using the formula V P I₁ I₂ p' I₁ I₂ P' ε 10010050 217.123957210.684713102.631579 17515080 200.000000176.81417590.000000 200.000000176.81417590.000000 174.540108150.00000079.788060 200.000000177.39973689.962460 236.239496191.386704104.444653 0.002957 10610656 217.123957210.249311106.231579 18115686 200.000000176.37877393.600000 235.378947192.252632107.751579 173.321464150.00000083.009974 200.000000178.30877493.713641 235.760911190.809209108.061239 0.009305

3)球面反射和折射3) Spherical reflection and refraction

(1)球面反射(1) spherical reflection

已知：视点V，场景中任意选取的点P，设反射球的半径为r，球心在0点，如图6所示。令a＝|V-P|，b＝|V-O|，c＝|O-P|。It is known: the viewpoint V, the point P randomly selected in the scene, the radius of the reflective sphere is r, and the center of the sphere is at point 0, as shown in Figure 6. Let a=|V-P|, b=|V-O|, c=|O-P|.

根据几何光学原理可以得到：According to the principle of geometric optics, we can get:

2bcxyzcos(α+β)＝bcxysin²(α+β)-b²y²z-c²x²z (5)2bcxyzcos(α+β)＝bcxysin² (α+β)-b² y² zc² x² z (5)

x(r²+y²-c²)＝y(x²+r²-b²) (6)x(r² +y² -c² )=y(x² +r² -b² ) (6)

其中，z＝(a²-(x-y)²)/(4abc)。Wherein, z=(a² −(xy)² )/(4abc).

取视点V为坐标原点，视点到球心0的距离为单位长度。从(6)式可以解出y，它可以看成是x的函数。将y在x＝b-r处作泰勒展开，并取线性近似Take the viewpoint V as the coordinate origin, and the distance from the viewpoint to the center of the sphere 0 as the unit length. From (6) formula can solve y, it can regard as the function of x. Take Taylor expansion of y at x=b-r and take a linear approximation

y＝A+Bx， (7)y=A+Bx,

其中， $A = (c - b) (c - r) / c, B = \frac{b (c - r)}{c (b - r)} .$ in, $A = (c - b) (c - r) / c, B = \frac{b (c - r)}{c (b - r)} .$

将(7)代入(5)式，可以得到如下四次方程：Substituting (7) into (5), the following quartic equation can be obtained:

x(A+Bx)[a²-(x-A-Bx)²]cos(α+β)＝x(A+Bx)[a² -(xA-Bx)² ]cos(α+β)＝

2bcx(A+Bx)sin²(α+β)-[b²(A+Bx)²+c²x²][(a²-(x-A-Bx)²]/(2bc)，(8)2bcx(A+Bx)sin² (α+β)-[b² (A+Bx)² +c² x² ][(a² -(xA-Bx)² ]/(2bc), (8)

解出x，然后代入(7)可以求出y，从而计算出虚顶点P’。Solve x, and then substitute into (7) to find y, so as to calculate the virtual vertex P'.

下面介绍如何计算虚顶点P’：The following describes how to calculate the virtual vertex P':

I.由于V，0，P三点在一个平面上，我们以0点为原点，平面VP0的法向量N＝[N_x，N_y，N_z]^T为z轴，以0P为y轴，0P×N为x轴，建立局部坐标系。这样我们可以得到从世界坐标系到局部坐标系的转换矩阵： $T = [\begin{matrix} u_{x} & v_{x} & w_{x} & 0 \\ u_{y} & v_{y} & w_{y} & 0 \\ u_{z} & v_{z} & w_{z} & 0 \\ 0 & 0 & 0 & 1 \end{matrix}],$ I. Because V, 0, and P three points are on a plane, we take 0 as the origin, and the normal vector N=[N_x , N_y , N_z ]^T of the plane VP0 is the z axis, and 0P is the y axis, 0P×N is the x-axis, and the local coordinate system is established. In this way we can get the transformation matrix from the world coordinate system to the local coordinate system: $T = [\begin{matrix} u_{x} & v_{x} & w_{x} & 0 \\ u_{the y} & v_{the y} & w_{the y} & 0 \\ u_{z} & v_{z} & w_{z} & 0 \\ 0 & 0 & 0 & 1 \end{matrix}],$

其中，w_x＝N_x，w_y＝N_y，w_z＝N_z；Among them, w_x =N_x , w_y =N_y , w_z =N_z ;

x，y分别为球面上的点I到视点V和场景中的点P之间的距离：x＝|V-I|，y＝|I-P|；应用公式I＝T.L_I便可把L_I从局部坐标系变换为世界坐标系下的坐标。x and y are respectively the distances from point I on the sphere to the viewpoint V and the point P in the scene: x=|VI|, y=|IP|; applying the formula I=TL_I can transform L_I from the local coordinates system into coordinates in the world coordinate system.

II.在局部坐标系中，分别以0，V，P为圆心，R(球的半径)，x，y为半径做三个圆，分别记为c₁，c₂，c₃。II. In the local coordinate system, make three circles with 0, V, and P as the centers, R (the radius of the ball), x, and y as the radii, and record them as c₁ , c₂ , and c₃ .

III.求出c₁和c₂的两个交点p₁，p₃，c₁和c₃的两个交点p₃，p₄。分别计算p₁p₃，p₁p₄，p₂p₃和p₂P₄的距离，取距离最小的一对点坐标的平均值，即为球面上点I在局部坐标系上的坐标，记为LI[L_Ix，L_Iy，P_z，1]^T。应用公式I＝T·L_I将L_I的局部坐标变换成世界坐标系下的坐标，结果记为I。IV.计算 $P^{'} = V + (x + y) \frac{I - V}{| I - V |} .$ III. Find the two intersection points p₁ and p₃ of c₁ and c₂ , and the two intersection points p₃ and p₄ of c₁ and c₃ . Calculate the distances of p₁ p₃ , p₁ p₄ , p₂ p₃ and p₂ P₄ respectively, and take the average value of the coordinates of a pair of points with the smallest distance, which is the coordinates of point I on the spherical surface in the local coordinate system, Denote as LI[L_Ix , L_Iy , P_z , 1]^T . Apply the formula I=T·L_I to transform the local coordinates of L_I into coordinates in the world coordinate system, and record the result as I. IV. Calculation $P^{'} = V + (x + the y) \frac{I - V}{| I - V |} .$

我们用光线跟踪的方法产生了两组点，然后用上面的公式，反算I₁和I₂。具体的结果如下表所示。光线跟踪产生的点用公式反算的点视点场景中的点 I 精确虚顶点 I 近似虚顶点相对偏差ε -116.99539996.421837-31.162001 270.1289681170.523969124.238610 -81.65019734.787454-38.100506 512.488025-1001.261011-154.733903 -81.65188034.786900-38.100637 512.460899-1001.275845-154.7367980.000024 -116.99539996.421837-31.162001 -488.154348602.063430-436.722567 -87.32875632.818073-42.643174 246.401988-682.683540-171.799019 -87.32858032.818149-42.642386 246.404709-682.683837-171.7895920.000011We use ray tracing method to generate two sets of points, and then use the above formula to inversely calculate I₁ and I₂ . The specific results are shown in the table below. Points generated by ray tracing Points inversely calculated using the formula point of view points in the scene I exact virtual vertices I Approximate Virtual Vertex relative deviation ε -116.99539996.421837-31.162001 270.1289681170.523969124.238610 -81.65019734.787454-38.100506 512.488025-1001.261011-154.733903 -81.65188034.786900-38.100637 512.460899-1001.275845-154.736798 0.000024 -116.99539996.421837-31.162001 -488.154348602.063430-436.722567 -87.32875632.818073-42.643174 246.401988-682.683540-171.799019 -87.32858032.818149-42.642386 246.404709-682.683837-171.789592 0.000011

(2)球面折射(2) spherical refraction

如图7所示，球的半径为r，根据几何光学可以得到： ${\frac{(a^{2} + r^{2} - x^{2}) (b^{2} + r^{2} - y^{2}) x^{2} \cos θ}{{4 abr}^{2}} - [x^{2} - \frac{{(x^{2} + r^{2} - a^{2})}^{2}}{{4 r}^{2}}] (\frac{xy \cos θ}{ab} +$ (9) $\frac{2}{η^{2}}) + x^{2}}^{2} = \frac{x^{2} \sin^{2} θ {[r^{2} x + y] (a^{2} - x^{2})]}^{2}}{a^{2} b^{2} r^{2}} [x^{2} - \frac{{(x^{2} + r^{2} - a^{2})}^{2}}{{4 r}^{2}}],$ y(x²+r²-a²)＝x(y²+r²-b)。 (10)不失一般性，取视点V为坐标原点，视点到球心0的距离为单位长度。令x＝a-r+t， (11)对(10)式在t＝0处作泰勒展开，并作线性近似，可得： $y = b - r + \frac{a (b - r)}{b (a - r)} t,$ 将(11)和(12)式代入(9)式，并忽略t的(5次以上的)高阶项，得y＝G₀+G₁t+G₂t²+G₃t³+G₄t⁴， (13)其中，G₀＝T₀²-C₁S₀R₀；G₁＝2T₀T₁-C₁(S₀R₁+S₁R₀)；G₂＝2T₀T₂+T₁T₁-C₁(S₀R₂+S₁R₁+S₂R₀)；G₃＝2T₀T₃+2T₁T₂-C₁(S₀R₃+S₁R₂+S₂R₁+S₃R₀)；G₄＝2T₀T₄+2T₁T₃+T₂²-C₁(S₀R₄+S₁R₃+S₂R₂+S₃R₁+S₄R₀)；C₀＝a-r；C₁＝sin²θ/(a²b²r²)；C₂＝-1/(4r²)；C₃＝cosθ/(4abr²)；C₄＝cosθ/(ab)；C₅＝2/η²+C₄AC₀；C₆＝C₄(A+BC₀)；C₇＝C₄B；S₀＝C₀²+C₂(C₀²-a²+r²)²；S₁＝2C₀+4C₂C₀(C₀²-a²+r²)；S₂＝1+2C₂(3C₀²-a²+r²)；S₃＝4C₂C₀；S₄＝C₂；Q₀＝r²C₀+A(a²-C₀²)；Q₁＝r²-2AC₀+B(a²-C₀²)；As shown in Figure 7, the radius of the sphere is r, and according to geometric optics: ${\frac{(a^{2} + r^{2} - x^{2}) (b^{2} + r^{2} - {the y}^{2}) x^{2} \cos θ}{{4 abr}^{2}} - [x^{2} - \frac{{(x^{2} + r^{2} - a^{2})}^{2}}{{4 r}^{2}}] (\frac{xy \cos θ}{ab} +$ (9) $\frac{2}{η^{2}}) + x^{2}}^{2} = \frac{x^{2} \sin^{2} θ {[r^{2} x + the y] (a^{2} - x^{2})]}^{2}}{a^{2} b^{2} r^{2}} [x^{2} - \frac{{(x^{2} + r^{2} - a^{2})}^{2}}{{4 r}^{2}}],$ y(x² +r² −a² )=x(y² +r² −b). (10) Without loss of generality, the viewpoint V is taken as the coordinate origin, and the distance from the viewpoint to the center of the sphere 0 is taken as the unit length. Let x=a-r+t, (11) make Taylor expansion on formula (10) at t=0, and make linear approximation, we can get: $the y = b - r + \frac{a (b - r)}{b (a - r)} t,$ Substituting equations (11) and (12) into equation (9), and ignoring the higher-order terms of t (more than 5 degrees), we get y=G₀ +G₁ t+G₂ t² +G₃ t³ +G₄ t⁴ , (13) Among them, G₀ =T₀² -C₁ S₀ R₀ ; G₁ =2T₀ T₁ -C₁ (S₀ R₁ +S₁ R₀ ); G₂ =2T₀ T₂ +T₁ T₁ -C₁ (S₀ R₂ +S₁ R₁ +S₂ R₀ ); G₃ =2T₀ T₃ +2T₁ T₂ -C₁ (S₀ R₃ +S₁ R₂ +S₂ R₁ +S₃ R₀ ); G₄ =2T₀ T₄ +2T₁ T₃ +T₂² -C₁ (S₀ R₄ +S₁ R₃ +S₂ R₂ +S₃ R₁ +S₄ R₀ ); C₀ =ar; C₁ =sin² θ/(a² b² r² ); C₂ =-1/(4r² ); C₃ =cos θ/(4abr² ); C₄ =cosθ/(ab); C₅ =2/η² +C₄ AC₀ ; C₆ =C₄ (A+BC₀ ); C₇ =C₄ B; S₀ =C₀² + C₂ (C₀² -a² +r² )² ; S₁ =2C₀ +4C₂ C₀ (C₀² -a² +r² ); S₂ =1+2C₂ (3C₀² -a² +r² ); S₃ =4C₂ C₀ ; S₄ =C₂ ; Q₀ =r² C₀ +A(a² -C₀² ); Q₁ =r² -2AC₀ +B(a² -C₀² );

Q₂＝-A-2BC₀；Q₂ =-A-2BC₀ ;

Q₃＝-B；Q₃ =-B;

U₀＝Q₀C₀²；U₀ =Q₀ C₀² ;

U₁＝2Q₀C₀+Q₁C₀²；U₁ =2Q₀ C₀ +Q₁ C₀² ;

U₂＝Q₀+2Q₁C₀+Q₂C₀²；U₂ =Q₀ +2Q₁ C₀ +Q₂ C₀² ;

U₃＝Q₁+2Q₂C₀+Q₃C₀²；U₃ =Q₁ +2Q₂ C₀ +Q₃ C₀² ;

U₄＝Q₂+2Q₃C₀；U₄ =Q₂ +2Q₃ C₀ ;

R₀＝Q₀U₀；R₀ =Q₀ U₀ ;

R₁＝Q₀U₁+Q₁U₀；R₁ =Q₀ U₁ +Q₁ U₀ ;

R₂＝Q₀U₂+Q₁U₁+Q₂U₀；R₂ =Q₀ U₂ +Q₁ U₁ +Q₂ U₀ ;

R₃＝Q₀U₃+Q₁U₂+Q₂U₁+Q₃U₀；R₃ =Q₀ U₃ +Q₁ U₂ +Q₂ U₁ +Q₃ U₀ ;

R₄＝Q₀U₄+Q₁U₃+Q₂U₂+Q₃U₁；R₄ =Q₀ U₄ +Q₁ U₃ +Q₂ U₂ +Q₃ U₁ ;

P₀＝(a²+r²-C₀²)(b²+r²-A²)；P₀ =(a² +r² -C₀² )(b² +r² -A² );

P₁＝-2AB(a²+r²-C₀²)-2C₀(b²+r²-A²)；P₁ =-2AB(a² +r² -C₀² )-2C₀ (b² +r² -A² );

P₂＝-B²(a²+r²-C₀²)+4C₀AB-(b²+r²-A²)；P₂ =-B² (a² +r² -C₀² )+4C₀ AB-(b² +r² -A² );

P₃＝2C₀B²+2AB；P₃ =2C₀ B² +2AB;

P₄＝BB；P₄ =BB;

T₀＝C₃C₀²P₀-C₅S₀+C₀²；T₀ =C₃ C₀² P₀ -C₅ S₀ +C₀² ;

T₁＝C₃(C₀²P₁+2C₀P₀)-C₅S₁-C₆S₀+2C₀；T₁ =C₃ (C₀² P₁ +2C₀ P₀ )-C₅ S₁ -C₆ S₀ +2C₀ ;

T₂＝C₃(C₀²P₂+2C₀P₁+P₀)-C₅S₂-C₆S₁-C₇S₀+1；T₂ =C₃ (C₀² P₂ +2C₀ P₁ +P₀ )-C₅ S₂ -C₆ S₁ -C₇ S₀ +1;

T₃＝C₃(C₀²P₃+2C₀P₂+P₁)-C₅S₃-C₆S₂-C₇S₁；T₃ =C₃ (C₀² P₃ +2C₀ P₂ +P₁ )-C₅ S₃ -C₆ S₂ -C₇ S₁ ;

T₄＝C₃(C₀²P₄+2C₀P₃+P₂)-C₅S₄-C₆S₃-C₇S₂；T₄ =C₃ (C₀² P₄ +2C₀ P₃ +P₂ )-C₅ S₄ -C₆ S₃ -C₇ S₂ ;

从(13)式可以计算出t，将t代入(11)和(12)式即可分别求出x和y，这样就可以求出虚顶点P’。t can be calculated from formula (13), and x and y can be obtained by substituting t into formulas (11) and (12), so that the virtual vertex P' can be obtained.

确定I₁和I₂的方法：Method to determine I₁ and I₂ :

得到x和y后，分别以V和P为圆心，x和y为半径画圆，在折射平面里和球面分别交于I₁′，I₁″和I₂′，I₂″，见图8。球面的入射点I₁取自I₁′和I₁″中的某一个，出射点I₂取自I₂′和I₂″中的某一个。也就是说，I₁和I₂有四种可能的取法。此时，我们将应用折射定律，选取出我们所要的那一种可能情况。注意到，如果I₁和I₂是精确的入射点和出射点，则 $\frac{\sin β}{\sin α} = \frac{1}{η},$ 或者说， $\frac{1 - \cos^{2} β}{1 - \cos^{2} α} = \frac{1}{η^{2}},$ 同时， $\cos β = \frac{| | I_{1} I_{2} | |}{2 r}, \cos α = - \frac{x^{2} + r^{2} - a^{2}}{2 xr} = - \frac{y^{2} + r^{2} - b^{2}}{2 yr},$ 因而 $\frac{1 - \frac{{| | I_{1} I_{2} | |}^{2}}{{4 r}^{2}}}{1 - {(\frac{x^{2} + r^{2} - a^{2}}{2 xr})}^{2}} = \frac{1}{η^{2}}, \frac{1 - \frac{{| | I_{1} I_{2} | |}^{2}}{{4 r}^{2}}}{1 - {(\frac{y^{2} + r^{2} - b^{2}}{2 yr})}^{2}} = \frac{1}{η^{2}} .$ 于是，我们的选取准则是，取使得 $| \frac{1 - \frac{{| | I_{1} I_{2} | |}^{2}}{{4 r}^{2}}}{1 - {(\frac{x^{2} + r^{2} - a^{2}}{2 xr})}^{2}} - \frac{1}{η^{2}} | + | \frac{1 - \frac{{| | I_{1} I_{2} | |}^{2}}{{4 r}^{2}}}{1 - {(\frac{y^{2} + r^{2} - b^{2}}{2 yr})}^{2}} - \frac{1}{η^{2}} |$ After obtaining x and y, draw a circle with V and P as the center and x and y as the radius, and intersect the spherical surface at I₁ ′, I₁ ″ and I₂ ′, I₂ ″ in the refraction plane, see Figure 8 . The incident point I₁ of the spherical surface is taken from one of I₁ ′ and I₁ ″, and the outgoing point I₂ is taken from one of I₂ ′ and I₂ ″. That is, there are four possible ways of taking I₁ and I₂ . At this point, we'll apply the laws of refraction to pick out the one possibility we want. Note that if I₁ and I₂ are exact ingress and egress points, then $\frac{\sin β}{\sin α} = \frac{1}{η},$ Or, $\frac{1 - \cos^{2} β}{1 - \cos^{2} α} = \frac{1}{η^{2}},$ at the same time, $\cos β = \frac{| | I_{1} I_{2} | |}{2 r}, \cos α = - \frac{x^{2} + r^{2} - a^{2}}{2 xr} = - \frac{{the y}^{2} + r^{2} - b^{2}}{2 yr},$ thus $\frac{1 - \frac{{| | I_{1} I_{2} | |}^{2}}{{4 r}^{2}}}{1 - {(\frac{x^{2} + r^{2} - a^{2}}{2 xr})}^{2}} = \frac{1}{η^{2}}, \frac{1 - \frac{{| | I_{1} I_{2} | |}^{2}}{{4 r}^{2}}}{1 - {(\frac{{the y}^{2} + r^{2} - b^{2}}{2 yr})}^{2}} = \frac{1}{η^{2}} .$ Therefore, our selection criterion is to take $| \frac{1 - \frac{{| | I_{1} I_{2} | |}^{2}}{{4 r}^{2}}}{1 - {(\frac{x^{2} + r^{2} - a^{2}}{2 xr})}^{2}} - \frac{1}{η^{2}} | + | \frac{1 - \frac{{| | I_{1} I_{2} | |}^{2}}{{4 r}^{2}}}{1 - {(\frac{{the y}^{2} + r^{2} - b^{2}}{2 yr})}^{2}} - \frac{1}{η^{2}} |$

最小的那一组I₁I₂。The smallest set I₁ I₂ .

I.由于V，O，P，I₁，I₂五点在一个平面上，我们以O点为原点，平面VPO的法向量N＝[N_x，N_y，N_z]^T为z轴，以OP为y轴，N×OP为x轴，建立局部坐标系。这样我们可以得到从局部坐标系到世界坐标系的变换矩阵： $T = [\begin{matrix} u_{x} & v_{x} & w_{x} & 0 \\ u_{y} & v_{y} & w_{y} & 0 \\ u_{z} & v_{z} & w_{z} & 0 \\ 0 & 0 & 0 & 1 \end{matrix}],$ I. Because V, O, P, I₁ , I₂ five points are on a plane, we take O point as the origin, and the normal vector N=[N_x , N_y , N_z ]^T of the plane VPO is the z axis, With OP as the y-axis and N×OP as the x-axis, a local coordinate system is established. In this way we can get the transformation matrix from the local coordinate system to the world coordinate system: $T = [\begin{matrix} u_{x} & v_{x} & w_{x} & 0 \\ u_{the y} & v_{the y} & w_{the y} & 0 \\ u_{z} & v_{z} & w_{z} & 0 \\ 0 & 0 & 0 & 1 \end{matrix}],$

其中，in,

w_x＝N_x，w_y＝N_y，w_z＝N_z；w_x = N_x , w_y = N_y , w_z = N_z ;

u_z＝v_yw_z-w_yv_z，u_y＝w_xv_z-v_xw_z，u_z＝v_xw_y-w_xv_y；u_z =v_y w_z -w_y v_z , u_y =w_x v_z -v_x w_z , u_z =v_x w_y -w_x v_y ;

v_x、v_y和v_z分别是单位矢量的三个坐标分量。v_x , v_y and v_z are unit vectors The three coordinate components of .

II.应用公式I＝T·L_I将I₁和I₂的局部坐标转换成世界坐标系的坐标，结果仍然用I₁和I₂表示。II. Apply the formula I=T·L_I to transform the local coordinates of I₁ and I₂ into the coordinates of the world coordinate system, and the result is still represented by I₁ and I₂ .

III.计算 $P^{'} = V + (x + | I_{2} - I_{1} | + y) \frac{I_{1} - V}{| I_{1} - V |} .$ III. Calculation $P^{'} = V + (x + | I_{2} - I_{1} | + the y) \frac{I_{1} - V}{| I_{1} - V |} .$

我们用光线跟踪的方法产生了两组点，然后用上面的公式，反算I₁和I₂。具体的结果如下表所示。光线跟踪产生的点用公式反算的点视点场景中的点 I₁ I₂ 精确虚顶点 I₁ 近似虚顶点相对偏差 -116.99539996.421837-31.162001 -50.186456-53.644613-41.899063 -84.35257034.299263-41.259456 -72.4581227.408969-43.096134 -40.861831-48.467971-54.712513 -84.35202334.299371-41.260124 -40.860776-48.467295-54.7140010.000012 -116.99539996.421837-31.162001 -56.922493-35.934910-58.193442 -83.72148332.225986-32.146602 -72.5981887.090201-38.115781 -47.772221-37.131448-33.210370 -83.71290632.219162-32.131935 -47.762689-37.129611-33.1796130.000214We use ray tracing method to generate two sets of points, and then use the above formula to inversely calculate I₁ and I₂ . The specific results are shown in the table below. Points generated by ray tracing Points inversely calculated using the formula point of view points in the scene I₁ I₂ exact virtual vertices I₁ Approximate Virtual Vertex Relative deviation -116.99539996.421837-31.162001 -50.186456-53.644613-41.899063 -84.35257034.299263-41.259456 -72.4581227.408969 -43.096134 -40.861831-48.467971-54.712513 -84.35202334.299371-41.260124 -40.860776-48.467295-54.714001 0.000012 -116.99539996.421837-31.162001 -56.922493-35.934910-58.193442 -83.72148332.225986-32.146602 -72.5981887.090201 -38.115781 -47.772221-37.131448-33.210370 -83.71290632.219162-32.131935 -47.762689-37.129611-33.179613 0.000214

3、算法实现3. Algorithm implementation

算法1：预处理，如图10所示。Algorithm 1: Preprocessing, as shown in Figure 10.

第2步，收集场景中所有的反射和折射体，并形成反射和折射体对象表；Step 2, collect all reflection and refraction bodies in the scene, and form a reflection and refraction body object table;

第4步，计算虚顶点并生成所有的虚物体，产生虚场景。Step 4: Calculate virtual vertices and generate all virtual objects to generate a virtual scene.

算法2为平面折射体或反射体产生虚场景，如图11所示。有以下特点：Algorithm 2 generates virtual scenes for plane refractors or reflectors, as shown in Figure 11. Has the following characteristics:

算法3为视点位置改变时重新计算虚场景，如图12所示。Algorithm 3 recalculates the virtual scene when the viewpoint position changes, as shown in Figure 12.

要实现实时绘制场景，就必须采用硬件加速的办法。这时，我们要用到图形硬件的公用的软件接口OpenGL。前面的虚物体的生成，为我们实时绘制打下了基础。下面是我们使用的实时绘制算法。To achieve real-time rendering of scenes, hardware acceleration must be adopted. At this time, we need to use the common software interface OpenGL of the graphics hardware. The generation of the previous virtual objects laid the foundation for our real-time rendering. Below is the real-time rendering algorithm we use.

算法4为实时绘制和显示，如图13所示。Algorithm 4 is real-time rendering and display, as shown in Figure 13.

Claims

1. A real-time ray tracing method for plane and spherical non-linear refraction and reflection comprises a method for realizing real-time ray tracing by using a virtual object, and is characterized in that: for a refracted or reflected polyhedron, firstly calculating the virtual vertexes of all vertexes of the polyhedron by using a computer, then sequentially connecting all the virtual vertexes into an optical mapping virtual object which is formed by a plurality of virtual surfaces and finally forms reflection or refraction according to the original topological relation between points and surfaces of the polyhedron, and the optical mapping virtual object is called as a virtual object for short; when displaying graphics, the virtual object is recursively projected by using a recursive algorithm using a graphics hardware acceleration techniqueThe light is emitted to a reflecting or refracting surface, and alpha mixing is carried out on the light and the brightness value of the refracting surface, so that an image effect similar to ray tracing is obtained; the virtual vertex P' of any point P in the three-dimensional scene can be expressed as:

wherein V is a viewpoint and L is the sum of the lengths of paths through which the light L reaches the point P after being refracted or reflected; b is a sampling point on the projection plane;

for a planar refractor whose scene is outside the refractor, it comprises the following steps in sequence:

(1) calculating each virtual vertex P':

l＝|V-I₁|+|I₁-I₂|+|I₂-P|，

I_{1} = Q + d \frac{U - Q}{| U - Q |},

Q＝V-w₁N，

U = V - \frac{C_{3} + C^{T} V}{C^{T} (P - V)} (P - V),

wherein l is the sum of the lengths of paths through which the light rays pass when refracted to reach a point P in the scene; w is a₁Is the distance from the viewpoint V to the incident surface of the refractor; q is a vertical foot of a viewpoint V on an incident surface of the refraction body; d is from point Q to point I₁The distance of (d); u is the intersection point of the straight line VP and the incident plane of the refraction body; the equation for the incident surface of the refractive body is set to C₀x+C₁y+C₂z+C₃0, and C ═ C₀，C₁，C₂)^T；I₁、I₂Respectively, the intersection point of two surfaces corresponding to the light L and the plane refractor, namely the entrance and exit of the two refracting surfaces, and N is a point I₁The unit normal vector of (d);

(2) connecting all the virtual vertexes into the edges of the virtual objects in sequence according to the original topological relation of the objects in the scene, wherein the corresponding surfaces form all the virtual surfaces;

(3) the virtual object is projected onto the refractive surface using a recursive algorithm and displayed with a resulting image after alpha blending with the local luminance values of the refractive surface itself.

2. A real-time ray tracing method for plane and spherical non-linear refraction and reflection comprises a method for realizing real-time ray tracing by using a virtual object, and is characterized in that: for a refracted or reflected polyhedron, firstly calculating the virtual vertexes of all vertexes of the polyhedron by using a computer, then sequentially connecting all the virtual vertexes into an optical mapping virtual object which is formed by a plurality of virtual surfaces and finally forms reflection or refraction according to the original topological relation between points and surfaces of the polyhedron, and the optical mapping virtual object is called as a virtual object for short; when displaying the graph, using a graph hardware acceleration technology to recursively project the virtual object onto a reflecting or refracting surface by using a recursive algorithm, and performing alpha mixing with the brightness value of the refracting surface to obtain an image effect similar to ray tracing; the virtual vertex P' of any point P in the three-dimensional scene can be expressed as:

for planar refraction of a scene within a refractive body, it comprises the following steps in sequence:

(1) calculating each virtual vertex P':

l＝|V-I|+|I-P|，

I = Q + d \frac{U - Q}{| U - Q |},

Q＝V-w₁N，

U = V - \frac{C_{3} + C^{T} V}{C^{T} (P - V)} (P - V),

wherein I is the intersection point of the light L and the incident plane of the planar refractor, and the equation of the incident plane is set as C₀x+C₁y+C₂z+C₃0, and C ═ C₀，C₁，C₂)^T(ii) a N is the unit normal vector at point I; q is a vertical foot of a viewpoint V on an incident surface of the refraction body; d is from point Q to point I₁The distance of (d); u is straight line VP and incident plane of refraction bodyThe intersection point of (a);

(2) connecting all the virtual vertexes into the edges of the virtual objects in sequence according to the original topological relation of the objects in the scene, wherein the corresponding surfaces form virtual surfaces;

3. The real-time ray tracing method of plane and spherical nonlinear refraction and reflection is characterized in that: for a refracted or reflected polyhedron, firstly calculating the virtual vertexes of all vertexes of the polyhedron by using a computer, then sequentially connecting all the virtual vertexes into an optical mapping virtual object which is formed by a plurality of virtual surfaces and finally forms reflection or refraction according to the original topological relation between points and surfaces of the polyhedron, and the optical mapping virtual object is called as a virtual object for short; when displaying the graph, using a graph hardware acceleration technology to recursively project the virtual object onto a reflecting or refracting surface by using a recursive algorithm, and performing alpha mixing with the brightness value of the refracting surface to obtain an image effect similar to ray tracing; the virtual vertex P' of any point P in the three-dimensional scene can be expressed as:

wherein V is a viewpoint, L is the sum of the lengths of paths through which the light L passes when being refracted or reflected to reach a point P in a scene corresponding to the virtual vertex; b is a sampling point on the projection plane;

for the refraction of a three-dimensional plane with two mutually perpendicular refraction surfaces of a light ray incoming and outgoing refraction body, the method sequentially comprises the following steps:

(1) calculating each virtual vertex P':

d＝|V-I₁|+|I₁-I₂|+|I₂-P|，

I₁＝V+dx+dy+dz，

dx＝xe_x，dy＝ye_y，dz＝ze_z，

e_y＝N₂，e_z＝-N₁，e_x＝e_y×e_z，

where P is a point on an object in the scene, V is a viewpoint, N₁Is the normal vector outside the incident plane, N₂Is the outer normal vector of the exit surface, the entrance surface is perpendicular to the exit surface, N₁、N₂Is a unit vector, e_x，e_y，e_zIs a base vector under a local coordinate system, x, y and z are coordinates under the local coordinate system, and dx, dy and dz are offset of the point I1 relative to the viewpoint;

wherein,

eta is the refractive index of the three-dimensional refractor, and alpha is the vertical distance from a viewpoint to the emergent surface of the refractor;

4. The real-time ray tracing method of plane and spherical nonlinear refraction and reflection is characterized in that: for a refracted or reflected polyhedron, firstly, the computer is used to calculate the virtual vertexes of each vertex of the polyhedron, then all the virtual vertexes are connected in turn according to the topological relation between the original points and the faces of the polyhedron to form an optical mapping virtual object which is composed of a plurality of virtual faces and finally forms the reflection or refraction, and the optical mapping virtual object is called as the virtual object for shortAn object; when displaying the graph, using a graph hardware acceleration technology to recursively project the virtual object onto a reflecting or refracting surface by using a recursive algorithm, and performing alpha mixing with the brightness value of the refracting surface to obtain an image effect similar to ray tracing; the virtual vertex P' of any point P in the three-dimensional scene can be expressed as:

for a spherical reflector, it comprises the following steps in sequence:

(1) calculating each virtual vertex P':

i is the incident point of the ray L on the sphere, which can be expressed as: i is T.L_IWherein L is_I＝[L_Ix，L_Iy，P_z，1]^TIt is the coordinate of the point I on the sphere under the local coordinate system; t is a transformation matrix from the local coordinate system to the world coordinate system:

T = [\begin{matrix} u_{x} & v_{x} & w_{x} & 0 \\ u_{y} & v_{y} & w_{y} & 0 \\ u_{z} & v_{z} & w_{z} & 0 \\ 0 & 0 & 0 & 1 \end{matrix}],

wherein,

u_x＝v_yw_z-w_yv_z，u_y＝w_xv_z-v_xw_z，u_z＝v_xw_y-w_xv_y；

v_x、v_yand v_zThree coordinate components of unit vector (P-O)/| P-O | respectively;

w_x＝N_x，w_y＝N_y，w_z＝N_z；

N＝(N_x，N_y，N_z)^Ta normal vector of a plane VPO consisting of a viewpoint V, a sphere center O of the spherical surface and a point P in the scene; establishing a local coordinate system by taking O as a coordinate origin, N as a z axis, OP as a y axis and OP multiplied by N as an x axis;

x, y are the distances from point I on the sphere to point V and point P in the scene, respectively: x ═ V-I |, y ═ I-P |; using the formula I ═ T · L_ICan be handled L_ITransforming from the local coordinate system to a world coordinate system;

(3) the virtual object is projected onto the reflecting surface by a recursive algorithm and displayed as a result after alpha blending with the local luminance values of the reflecting surface itself.

5. The real-time ray tracing method of plane and spherical nonlinear refraction and reflection is characterized in that: for the polyhedron to be refracted or reflected, first, a computer is usedCalculating the virtual vertexes of all vertexes of the polyhedron, and then sequentially connecting all the virtual vertexes into an optical mapping virtual object which is formed by a plurality of virtual surfaces and finally forms reflection or refraction according to the original topological relation between points and surfaces of the polyhedron, wherein the optical mapping virtual object is simply called as a virtual object; when displaying the graph, using a graph hardware acceleration technology to recursively project the virtual object onto a reflecting or refracting surface by using a recursive algorithm, and performing alpha mixing with the brightness value of the refracting surface to obtain an image effect similar to ray tracing; the virtual vertex P' of any point P in the three-dimensional scene can be expressed as:

for spherical refractors, it comprises the following steps in sequence:

(1) calculating each virtual vertex P':

wherein, I₁、I₂The incident point and the exit point of the light ray to the spherical refractor are respectively expressed by the formula I ═ T.L_IHandle I₁、I₂The local coordinates of (a) are transformed into coordinates of a world coordinate system; x and y are respectively from a viewpoint V to an incident point I₁And point of emergence I₂Distance to a point P in the scene, i.e. x ═ V-I₁|，y＝|I₂-P |; t is a transformation matrix from the local coordinate system to the world coordinate system:

T = [\begin{matrix} u_{x} & v_{x} & w_{x} & 0 \\ u_{y} & v_{y} & w_{y} & 0 \\ u_{z} & v_{z} & w_{z} & 0 \\ 0 & 0 & 0 & 1 \end{matrix}],

wherein,

u_x＝v_yw_z-w_yv_z，u_y＝w_xv_z-v_xw_z，u_z＝v_xw_y-w_xv_y；

w_x＝N_x，w_y＝N_y，w_z＝N_z；

6. A method for real-time ray tracing of planar and spherical nonlinear refraction and reflection according to claim 1 or 2, or 3, or 4, or 5, wherein: the process for displaying graphics using a recursive algorithm comprises the steps and algorithms of:

algorithm 1 preprocessing

Constructing a binary space subdivision (BSP) tree for objects in a scene, and if the scene contains spherical reflecting or refracting bodies, replacing 6 surfaces of a cube which closely contains the ball with the ball to participate in constructing the BSP tree;

step 2, collecting all reflection and refraction bodies in the scene and forming a reflection and refraction body object table;

step 3, determining the sequence of each reflector and refractor in the reflector and refractor body surface according to the current viewpoint; because the BSP tree is irrelevant to the viewpoint, the sequence of the reflecting body and the refracting body can be obtained quickly;

step 4, calculating a virtual vertex and generating all virtual objects to generate a virtual scene;

algorithm 2 generates a virtual scene for a refractive or reflective body:

i) is the maximum recursion level reached? If yes, returning;

ii) if it is a reflector, calculating a reflected virtual scene; if the virtual scene is a refraction body, calculating a refraction virtual scene;

iii) ordering the reflexes and refracts in the virtual scene according to the viewpoint;

iv) if a reflection or refraction body still exists in the virtual scene, recursively calling the algorithm for the reflection or refraction body in the virtual scene, and turning to i); otherwise, turning v);

v) returning;

if the viewpoint changes, recalculation is not needed for the plane reflection virtual scene; but the virtual scene of any refractor or spherical reflector and all the virtual scenes appearing in the subsequent recursion process must be recalculated; the following is an algorithm for recalculating virtual scenes when the viewpoint changes:

algorithm 3 recalculation of virtual scenes when viewpoint position changes

i) Is it a refractive body?

ii) is, calling Algorithm 2;

iii) if not, recursively calling the algorithm;

algorithm 4 real-time rendering and display (the algorithm is for a certain reflector or refractor in a real scene)

i) Setting drawing parameters of OpenGL (color cache write forbidding, depth comparison forbidding, Alpha mixing forbidding, and enabling the value of a drawn template buffer area to be + 1);

ii) rendering the reflecting, refracting body itself;

iii) if the virtual scene contains the reflection or refraction body, turning to i), and recursively drawing the reflection or refraction body in the virtual scene; otherwise, go to iv);

iv) setting drawing parameters of OpenGL (making the value of a template buffer area drawn unchanged, color cache writable, depth effective, and other drawing parameters unchanged);

v) drawing other virtual objects in the current virtual scene in the current template buffer area;

vi) setting drawing parameters of OpenGL (color cache writable, depth comparison effective, Alpha mixed effective, and making the value of a drawn template buffer area-1);

vii) rendering the reflecting, refracting body itself;

viii) setting drawing parameters of OpenGL (recover depth cache writable, color cache writable, Alpha mixing forbidden, template operation forbidden);

ix) returning.