CN1410948A

CN1410948A - Real time light tracing method of non linear refraction and reflection on plane and spherical surfaces

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

The optical mapped virtual vertex for each vertex of the polyhedron to be refracted or reflected is calculated. Based on the topological relation of the polyhedron, each virtual vertex is connected to form the virtual object composed of several virtual faces. In rendering, the virtual object is projected to the relevant refraction or reflection surfaces by using recursive algorithm. With being mixed with the color value of the surface, the reality graphics, similar to the graphics obtained by the ray tracing method, is obtained. The invention gives the formula to calculate the virtual vertex P' for any point P in five circumstances: the object inside or outside the plane refractive body, the three-dimension refraction, the spherical surface reflection and refraction as well as the algorithm and drawing procedure.

Description

Real-time ray tracing method for plane and spherical non-linear refraction and reflection

Technical Field

A real-time ray tracing method for plane and spherical non-linear refraction and reflection belongs to the technical field of computer graphics.

Background

The ray tracing algorithm is one of the most commonly used algorithms for generating three-dimensional realistic graphics, and is a realistic graphics generation method proposed by t.whiteted in the paper "An impromoted animation Model for shaped Display" published in 1980 in international journal comm.acm, vol.23, No. 6. The method can generate high-quality realistic graphics, but the calculation speed is slow, and the method cannot be applied to a real-time interactive application system. To increase the speed of ray tracing, various improved methods have been developed. A paper was published in Computer Graphics by P.S. Heckbert and P.Hanrahan et al in 1984, which first proposed a method for beam tracking. Beam tracking is an improvement over traditional ray tracing and is used to increase rendering speed, deal with aliasing problems, improve rendering quality and efficiency, and so on. However, beam tracking can only deal with specular reflection from a planar reflector, and cannot deal with non-linear refraction problems such as thick glass, curved surface reflection problems, and the like, and can only do linear approximations.

In 1996, m.levoy and p.hanrahan et al published papers on SIGGRAPH, and proposed a method for realizing drawing of graphics and images using a 4-dimensional light field. The mapping of the image is computed in a pre-process using a multi-dimensional light field, and then the mapping results are reused in each frame when displayed in real time. However, the problems of image information storage, aliasing, fast search and the like in the light field method still need to be further solved.

A method of view-independent environment mapping was proposed by w.heidrich et al in 1998. The display of the realistic graph is realized by utilizing the environment mapping and the support of hardware, the interactive speed can be achieved, but the real-time effect cannot be achieved. It is generally used more to deal with the reflection phenomenon and there are often significant errors.

Ofek and Rappoport in 1998 proposed the use of reflection virtual objects and extended mapping (expansion map) to achieve the ray tracing effect of curved surface reflection, which transforms all the vertices that may be in the reflection area for the reflector to generate virtual objects, and then performs the same uniform processing as real objects; however, they cannot deal with the refraction problem, and the error of expansion mapping is large, the accumulation and propagation of the error in the recursion process are very serious, and the quality of the generated result image is not high. Although they improve by interpolation, the effect is limited, but the amount of calculation is increased.

At present, many interactive graphic systems utilize hardware, can process a large number of three-dimensional patches per second, but basically can only provide the drawing effect of a depth cache (Z-Buffer) algorithm and cannot process the real-time realistic graphic problem of a reflection scene and a refraction scene.

Disclosure of Invention

The invention aims to provide a plane and spherical nonlinear refraction and reflection real-time ray tracking method which can solve the problems of nonlinear reflection and refraction uniformly and improve the algorithm efficiency.

The invention is characterized in that:

for a refracted or reflected polyhedron, firstly calculating the virtual vertexes of all vertexes of the polyhedron, then sequentially connecting all the virtual vertexes according to the original topological relation between points and surfaces of the polyhedron to form a plurality of virtual surfaces and finally form a reflected or refracted optical mapping virtual object, which is called a virtual object for short; when displaying the image, the virtual object is recursively projected onto the reflecting or refracting surface by using a recursive algorithm, so that an image effect similar to ray tracing is obtained; wherein, the virtual vertex P' 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 sample 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 horizontal distance between the viewpoint V and the refraction body; d is point I₁A vertical distance from the viewpoint V; q is a point of the lower end of the incident surface of the refraction body and the viewpoint V on the same horizontal position; u is the intersection of the line VP and the refractive body entrance face,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 the light L and the plane of the plane refractor projection plane, namely the entrance and exit of the two refracting surfaces, and N is a point I₁The unit normal vector of (a).

For a planar refractor with a scene within the refractor, 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 being at point IA unit normal vector; d is point I₁A vertical distance from the viewpoint V; q is a point of the lower end of the incident surface of the refraction body and the viewpoint V on the same horizontal position; u is the intersection point of the line VP and the incident plane of the refraction body;

for the refraction of three-dimensional planes with mutually perpendicular refraction surfaces, 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_ycross multiplication by e_zRe-unitization to obtain e_x，

Where P is a point in the scene, i.e. on an object, 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 the base in the local coordinate system, x, y, z are the coordinates in the local coordinate system, dx, dy, dz are I₁The offset of a point from a viewpoint;

wherein,

η 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 comprises the following steps in sequence: (1) calculating each virtual vertex P':

i is the reflection point of the light L on the sphere, which can be expressed as: i is T.L_IWherein L is_I＝[L_Ix，L_Iy，P_z，1]^TThe coordinate of the point I on the spherical surface under the local coordinate system; (ii) a 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 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 an origin, N as a z axis, OP as a y axis and OP multiplied by N as an x axis;

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;

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_IThe local coordinate system is transformed into a world coordinate system.

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；

N＝(N_x，N_y，N₂)^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;

the process for displaying graphics using a recursive algorithm comprises the steps 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 various reflecting and refracting bodies in the scene and forming a reflecting and refracting 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;

algorithm 2 has the following characteristics:

(1) the above algorithm is a recursive algorithm, and the recursion is mainly performed on the reflection and refraction bodies in the scene;

(2) the reflector and the refractor are treated uniformly;

(3) for the reflector, a reflection formula is used for generating the virtual scene, and the vertex sequence of the corresponding surface patches is changed, namely the vertex sequence of the surface patches of the reflection virtual objects is opposite to the original sequence, so that the plane external normal vector is ensured to point to the correct direction;

(4) in any virtual scene, the sequence of the reflecting and refracting bodies in the virtual scene is determined again according to the viewpoint and the BSP tree so as to be displayed correctly in real time;

(5) if the number of reflectors or refractors 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, recalculation is not needed for the pure reflection virtual scene; but the virtual scene appearing in any refraction body and 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;

to realize real-time scene rendering, a method of hardware acceleration by using a three-dimensional graphics acceleration card supporting OpenGL programming (OpenGL-compatible) can be adopted; at this time, a software interface of graphics hardware, namely an OpenGL graphics system, is used; the generation of the virtual object lays a foundation for real-time drawing of people; the real-time rendering algorithm we use is as follows;

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

x) 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);

xi) rendering the reflecting and refracting body itself;

xii) 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;

xiii) setting drawing parameters of OpenGL (making the value of the drawn stencil buffer constant, color cache writable, depth comparison valid, and other drawing parameters constant);

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

xv) setting drawing parameters of OpenGL (color cache writable, depth comparison valid, Alpha mixed valid, making the value of the drawn stencil buffer area-1);

xvi) rendering the reflecting, refracting body itself;

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

xviii) back.

Experiments prove that: it achieves the intended purpose.

Drawings

FIG. 1 is a schematic diagram of computing a virtual vertex using ray tracing.

FIG. 2 is a schematic illustration of arbitrary planar reflection.

FIG. 3 is a schematic representation of a first case of refraction-the scene being outside the refractor.

FIG. 4 is a schematic view of a second case of refraction-the scene being inside the refractor.

Fig. 5 is a three-dimensional refractive optical path diagram with mutually perpendicular refractive surfaces.

Fig. 6 is a schematic diagram of the optical path of the spherical reflection.

Fig. 7 is a schematic diagram of the optical path of spherical refraction.

Fig. 8 is a schematic diagram of determining the incident and exit points of a sphere.

FIG. 9 is a schematic view of a square box (a) and its virtual object (b).

Fig. 10 is a block diagram of algorithm 1 preprocessing.

Fig. 11 is a block flow diagram of a process for algorithm 2 to generate virtual scenes with planar refractors or reflectors.

Fig. 12 is a block diagram of the process flow for recalculating virtual scenes when the viewpoint location changes for algorithm 3.

Fig. 13 is a flow chart of the process for rendering and displaying algorithm 4 in real time.

Detailed Description

1. Basic idea

As shown in fig. 1, a ray L is emitted from a viewpoint a, refracted and reflected to reach a point V, which is a basic idea of ray tracing. However, given any point V, it is theoretically difficult to accurately obtain the ray L' from the viewpoint A that reaches point V through refraction, because the refraction problem is generally non-linear.

When an L is reflected or refracted several times and intersects with a plane M of an object at a point V, unlike the conventional ray tracing algorithm, we calculate a color value of a corresponding pixel point not by using an illumination model, but an optically mapped virtual vertex V' of the point V. Assuming that the light L reaches V after several reflections or refractions, the sum of the lengths of the paths is: d ═ d₁+d₂+Λ+d₅

The formula for the virtual vertex V' is:

where A is the viewpoint and B is a sample point on the projection plane. This is the "concept of optically mapping virtual objects" we propose.

For the reflected or refracted polyhedron, the virtual vertex of each vertex is first calculated, and then the virtual vertices are connected into the edges of virtual objects in sequence according to the topological relation, and finally the reflected or refracted optical mapping virtual object (called virtual object for short) is formed. E.g. a square box, see fig. 9(a), with its vertex P₁，P₂，...，P₈The virtual vertex of (A) is sequentially P'₁，p′₂，...，P′₈Then we can get the corresponding virtual object of the square box, as shown in fig. 9 (b). These virtual objects are projected onto a reflective or refractive surface when the graphics are displayed. This process can be performed recursively, resulting in an image effect similar to ray tracing. To obtain a high quality realistic image, the size of the plane that is reflected or refracted cannot be too large, otherwise the plane should be subdivided into smaller rectangles or triangles. For a curved object that is reflected or refracted in a scene, a curved surface should be first discretized into a plurality of facets, and the curved object is approximately represented by a polyhedron.

2. Formula for calculating virtual vertex

For the planar reflection problem, we can use the idea similar to the beam tracking algorithm to calculate the virtual vertices of each vertex:

suppose there is one over point R ═ V_x，V_y，V_z，1]^TAs shown in fig. 2, the unit normal vector of (a), (b), (c), (0) is N ═ a, b, c, 0]^T，N^TN is 1, and the plane equation is

ax+by+cz+d＝0

Wherein d is-N^TR and V are viewpoints.

Any point in the three-dimensional scene P ═ P_x，P_y，P_z，1]^TIs reflected and converted on the plane to reach P '═ P'_x，P′_y，P′_z，1]^T. From the geometric relationship, one can obtain:

P′＝T_mP

wherein,

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' is the reflection imaginary vertex of point P.

The refraction problem is much more complex than the planar reflection problem. There are two cases of non-linear refraction of planar refractors: the object is both outside the refractor (as shown in figure 3) and inside the refractor (see figure 4). We discuss below separately.

1) Two-dimensional planar refraction

(a) The object being outside the refractive body

As shown in FIG. 3, V is the viewpoint, P is an arbitrarily chosen point in the scene that is outside the refractive body, and P' is the imaginary vertex corresponding to P. The formula for finding its virtual object is derived as follows:

it is known that: w is a₁，w₂，w₃H, let eta equal to Sin alpha/Sin beta equal to eta₂/η₁，ξ＝1+w₃/w₁From the geometric relationship, it is possible to obtain

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

Wherein,

A＝(1-η²)ξ²，

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

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

D＝2η²hξw₁ ²，

E＝-w₁ ²η²h²。

d can be solved from the formula (1). From the value of d, the intersection point I of the refracted ray and the refracted plane can then be calculated₁And I₂Thereby, a virtual vertex P' is obtained.

The solving process of the virtual vertex P' is as follows:

(1) connecting V and P, finding the intersection point U of VP and the plane:

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

wherein the equation of the plane is C₀x+C₁y+C₂z+C₃0, and further, C ═ C₀，C₁，C₂)^T；

(2)Q＝V-w₁N；

(3) - - - I_{1} = Q + d \frac{U - Q}{| U - Q |} .

Similarly, can find I₂。

Let l be | V-I₁|+|I₁-I₂|+|I₂-P |, then the imaginary vertex of P point

We generate two sets of points by ray tracing and then back calculate I by the above formula₁Obviously, if I₁Same, then I₂Also, the specific results are shown in the following table.

	Ray tracing generated points				Points back calculated by formula
	Ray tracing generated points				Points back calculated by formula		Viewpoint V	Point P in a 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	Viewpoint V	Point P in a scene	I₁	I₂	I₁	I₂	-270.903693150.000000-62.237392
xyz	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	-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	-270.903693150.000000-62.237392

(b) The object being in a refractive body

For example, a fish in a fish tank, the object (fish) is on the inner surface of the refractor (fish tank). The calculation formula for this case should be different from that for the first clock case. As shown in FIG. 4, where V is the viewpoint, P is an arbitrarily chosen point in the scene that is inside the refractive body, and P' is the imaginary vertex to which P corresponds. Similarly, we can get the following one-dimensional quadratic equation from the geometric relationship:

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

wherein,

A＝η²-1，

B＝-2hA，

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

D＝-2η²hw₁ ²，

E＝w₁ ²η²h²。

d can be solved from the equation (2), and then the intersection point I of the refracted ray and the refracted plane can be calculated to obtain the imaginary vertex P'. The solving process of the virtual vertex P' is as follows:

(1) connecting V and P, wherein VP and the mirror plane are intersected in U which can be obtained by moving the previous formula;

(2)Q＝V-w₁N；

(3) - - - I = Q + d \frac{U - Q}{| U - Q |};

wherein l ═ V-I | + | I-P |.

We generate two sets of points by ray tracing and then use the above formula to back-calculate the intersection point I. Specific results are shown in the following table.

	Ray tracing generated points			Points back calculated by formula
	Ray tracing generated points			Points back calculated by formula	Viewpoint V	Point P in a scene	I	I
	xyz	-3.486133-91.011276-30.972000	-286.265348137.319548-64.033415	-252.000000110.000000-61.498001	Viewpoint V	Point P in a scene	I	I	-252.000000110.000000-61.498001
xyz	xyz	-3.486133-91.011276-30.972000	-286.265348137.319548-64.033415	-252.000000110.000000-61.498001	-3.486133-91.011276-30.972000	-275.475363136.992740-59.345723	-237.000000110.000000-55.332001	-237.000000110.000000-55.332001	-252.000000110.000000-61.498001

(c) Selection of solutions

It is obvious that both the formula (1) and the formula (2) are multi-solution equations, and they have at most 4 real roots. Therefore, after solving the equation, the result of the solution will be selected. According to the optical principle, the shortest path will be chosen for light to travel when it reaches from one point to another in the medium. Thus, we connect the viewpoint V with the point P in the scene to get a straight line, and the solution closest to this line is the point we are asking for.

2) Three-dimensional planar refraction

As in fig. 5, it is known that: a viewpoint V, an arbitrarily selected point P in the scene, refractive indices η, AD ═ a, VA ═ z, PF ═ b,

<math> <mrow> <mi>e</mi> <mo>=</mo> <mo>|</mo> <msub> <mrow> <mo>(</mo> <mover> <mi>VP</mi> <mo>&RightArrow;</mo> </mover> <mo>)</mo> </mrow> <mi>x</mi> </msub> <mo>|</mo> <mo>,</mo> <mi>f</mi> <mo>=</mo> <mo>|</mo> <msub> <mrow> <mo>(</mo> <mover> <mi>VP</mi> <mo>&RightArrow;</mo> </mover> <mo>)</mo> </mrow> <mi>y</mi> </msub> <mo>|</mo> <mo>,</mo> <mi>g</mi> <mo>=</mo> <mo>|</mo> <msub> <mrow> <mo>(</mo> <mover> <mi>VP</mi> <mo>&RightArrow;</mo> </mover> <mo>)</mo> </mrow> <mi>z</mi> </msub> <mo>|</mo> <mo>.</mo> </mrow> </math>

in FIG. 5, the light ray from viewpoint V passes through the top surface I of the medium₁The point refracts into the medium and then to the right side of the medium, from I₂The point refracts into the air and eventually reaches point P in the scene.

From Snell's law of refraction and geometric relationships, we can obtain the following two equations:

from the above two equations, x and y can be obtained, and then from the values of x, y and z and the refractive index η, I can be calculated in turn₁And I₂To obtain the position of the imaginary vertex P' of P.

(3) And (4) the formula is a binary 4-degree nonlinear equation system, and in order to improve the calculation speed, the following method is adopted for approximation:

first, d is calculated using the following formula: f. of₀+f₁d+f₂d²+f₃d³+f₄d⁴Neglecting the higher order (> 2) term of d to obtain

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

Wherein,

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}),

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} +

b^{4} ({2 C}_{1} + {C_{5}}^{2}) {(C_{7} - C_{1})}^{2} .

among the above 3 expressions, the expression,

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,

then, by substituting d into the following equation, the value of y when x is 0 can be calculated, and it is denoted as y₀I.e. by

y₀＝a-(0.5+d)。

Usually d is a small amount, | d | ≦ 0.5; in the above calculation, we neglect the higher order (≧ 3) term of d, and if the higher order (3, 4) term of d is retained, the calculation accuracy can be improved, but this also increases the calculation amount slightly. And (4) expanding the formula at the point x being 0 and performing linear approximation:

y＝y₀+y₁x，

wherein,

changing y to y₀+y₁Substituting x into formula (3) to obtain

Finding x from the above equation and substituting the value of x into equation (4) and solving a fourth order equation for y, which is organized as:

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

wherein,

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

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

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

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

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

then, the point I can be calculated from x, y, z and eta₁And I₂To find the virtual apex P'.

When x and y are solved by the system of equations consisting of equations (3) and (4), there is another scheme: obtaining y in the foregoing₀Then, the equation (3) is expanded and linearly approximated at a point where x is 0 to obtain:

y＝y₀+y₁x，

wherein,

then, y is equal to y₀+y₁Substituting x into formula (4) to obtain

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

Wherein

By calculating x from the above equation and substituting the value of x into equation (3), y can be directly calculated:

<math> <mrow> <mi>y</mi> <mo>=</mo> <mo>&PlusMinus;</mo> <msqrt> <mfrac> <mrow> <msup> <mi>x</mi> <mn>2</mn> </msup> <mo>+</mo> <mfrac> <mrow> <msup> <mrow> <mo>(</mo> <mi>g</mi> <mo>-</mo> <mi>z</mi> <mo>)</mo> </mrow> <mn>2</mn> </msup> <msup> <mi>x</mi> <mn>2</mn> </msup> </mrow> <msup> <mrow> <mo>(</mo> <mi>e</mi> <mo>-</mo> <mi>x</mi> <mo>)</mo> </mrow> <mn>2</mn> </msup> </mfrac> <mo>-</mo> <msup> <mi>η</mi> <mn>2</mn> </msup> <mrow> <mo>(</mo> <msup> <mi>x</mi> <mn>2</mn> </msup> <mo>+</mo> <msup> <mi>z</mi> <mn>2</mn> </msup> <mo>)</mo> </mrow> </mrow> <mrow> <msup> <mi>η</mi> <mn>2</mn> </msup> <mo>-</mo> <mn>1</mn> </mrow> </mfrac> </msqrt> <mo>.</mo> </mrow> </math>

the former scheme was used in the following calculation experiments.

Specific calculation of I₁、I₂And the process of the virtual vertex P' is as follows: :

a) find I₁

Let P be the point on the object, V be the viewpoint, n be the normal vector outside the incident plane₁Outer normal vector n of the exit surface₂The incident surface is perpendicular to the exit surface, n₁，n₂Is a unit vector. The basis of the local coordinate system being e_x，e_y，e_zWherein e is_y＝n_z，e_x＝-n₁，e_yCross multiplication by e_zAnd then unitized to obtain e_x。

The calculated x, y, z are coordinates in the local coordinate system. Let dx, dy, dz be I₁The amount of dot offset from the viewpoint is:

dx＝xe_x，

dy＝ye_y，

dz＝ze_z，

then I₁＝V+dx+dy+dz。

b) Find I₂

Knowing the incident ray direction vector IN ═ I₁V, normal vector n of the refracting surface₁And refractive index η, the refracted ray direction vector OUT can be calculated. By refracting a point I on the light₁And its direction, and the normal vector n of the exit face₂And a point on the surface, and calculating the intersection point I of the refracted ray and the emergent plane₂. We can give I₂The formula of (1) is as follows:

wherein

c) Ask for P'

From the viewpoint to the object point, the distance traveled by the light ray is d ═ V-I₁‖I₁-I₂‖+‖I₂-P |, where the formula for the calculation of the virtual apex P' can be found:

P^{,} = V + \frac{d (I_{1} - V)}{| | I_{1} - V | |} .

we generate two sets of points by ray tracing and then back calculate I by the above formula₁Obviously, if I₁Close, then I₂As well as similar. Specific results are shown in the following table, where ε is the relative error, i.e.: the ratio of the distance from the virtual vertex P 'to the exact virtual vertex P' to the distance from the viewpoint to the virtual vertex, which is back-calculated by the approximation formula

ε＝|P′-p′|/|V-p′|。

Ray tracing generated points					Points back calculated by formula
Ray tracing generated points					Points back calculated by 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	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) Spherical reflection and refraction

(1) Spherical reflection

It is known that: the viewpoint V, a point P arbitrarily selected in the scene, is set as the radius of the reflection sphere r, and the center of the sphere is at 0 point, as shown in fig. 6. Let a be | V-P |, b be | V-O |, and c be | O-P |.

According to the geometrical optics principle, the following can be obtained:

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

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

wherein z is (a)²-(x-y)²)/(4abc)。

And taking the viewpoint V as a coordinate origin, and taking the distance from the viewpoint to the sphere center 0 as a unit length. From equation (6), y can be solved and can be considered as a function of x. Taylor expansion is carried out on y at x-b-r, and linear approximation is taken

y＝A+Bx， (7)

Wherein,

A = (c - b) (c - r) / c, B = \frac{b (c - r)}{c (b - r)} .

substituting (7) into equation (5) can obtain the following fourth-order equation:

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

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

the imaginary vertex P' is calculated by solving x and substituting it into (7) to obtain y.

How to calculate the imaginary vertex P' is described below:

I. since the three points V, 0 and P are on a plane, we use point 0 as the origin, and the normal vector N of plane VP0 is [ N ═ N_x，N_y，N_z]^TA local coordinate system is established with 0P as the y-axis and 0P N as the x-axis. So 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_{y} & v_{y} & w_{y} & 0 \\ u_{z} & v_{z} & w_{z} & 0 \\ 0 & 0 & 0 & 1 \end{matrix}],

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

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

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 formula I-T.L_ICan be handled L_IFrom the local coordinate system to coordinates in the world coordinate system.

In the local coordinate system, three circles are made with 0, V and P as the center of the circle, R (radius of the sphere) and x and y as the radius, and are respectively marked as c₁，c₂，c₃。

Calculating c₁And c₂Two intersection points p of₁，p₃，c₁And c₃Two intersection points p of₃，p₄. Respectively calculate p₁p₃，p₁p₄，p₂p₃And p₂P₄The distance of (2) is an average value of a pair of point coordinates with the minimum distance, namely the coordinate of the point I on the spherical surface on the local coordinate system, and is marked as LI [ L ]_Ix，L_Iy，P_z，1]^T. Using the formula I ═ T · L_IMixing L with_IThe local coordinates of (2) are transformed into coordinates in the world coordinate system, and the result is denoted as I. IV, calculating

We generate two sets of points by ray tracing and then back calculate I by the above formula₁And I₂. Specific results are shown in the following table.

Ray tracing generated points				Points back calculated by formula
Ray tracing generated points				Points back calculated by formula			Viewpoint	Points in a scene	I	Exact virtual vertex	I	Approximate imaginary vertex	Relative deviation epsilon
-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	Viewpoint	Points in a scene	I	Exact virtual vertex	I	Approximate imaginary vertex	Relative deviation epsilon
-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) Spherical refraction

As shown in fig. 7, the radius of the sphere is r, which can be obtained from geometrical optics:

(9)

y(x²+r²-a²)＝x(y²+r²-b). (10) taking the viewpoint V as the origin of coordinates and the distance from the viewpoint to the sphere center 0 as the unit length without loss of generality. Let x be a-r + t, (11) taylor expansion of formula (10) at t 0, and linear approximation, we can obtain:

y = b - r + \frac{a (b - r)}{b (a - r)} t,

substituting expressions (11) and (12) into expression (9), and ignoring higher-order terms (more than 5 th order) of t to obtain y ═ G₀+G₁t+G₂t²+G₃t³+G₄t⁴(13) wherein, 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₀ ²)；

Q₂＝-A-2BC₀；

Q₃＝-B；

U₀＝Q₀C₀ ²；

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

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

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

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

R₀＝Q₀U₀；

R₁＝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₁；

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

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

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

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

P₄＝BB；

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

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₁；

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

T can be calculated from equation (13), and x and y can be obtained by substituting t into equations (11) and (12), respectively, whereby the imaginary vertex P' can be obtained.

Determination of I₁And I₂The method of (1):

after x and y are obtained, respectively using V and P as centre of circle, x and y as radius to draw a circle, in the refraction plane and spherical surface respectively intersecting with I₁′，I₁"and I₂′，I₂See FIG. 8. Incident point I of sphere₁Is taken from I₁' and I₁"one of, point of emergence I₂Is taken from I₂' and I₂"is used in the specification. That is, I₁And I₂There are four possible approaches. At this point we will apply the law of refraction to pick out the one possible case we want. Note that if I₁And I₂Are the exact points of incidence and emergence, then

In other words,

at the same time, the user can select the desired position,

thus, it is possible to provide

Thus, our selection criteria are such that

The smallest group I₁I₂。

How to calculate the imaginary vertex P' is described below:

I. due to V, O, P, I₁，I₂Five points are on a plane, and the normal vector N of the plane VPO is [ N ] by taking the point O as an origin_x，N_y，N_z]^TA local coordinate system is established with OP as the y-axis and N x OP as the x-axis. So 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_{y} & v_{y} & w_{y} & 0 \\ u_{z} & v_{z} & w_{z} & 0 \\ 0 & 0 & 0 & 1 \end{matrix}],

wherein,

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；

v_x、v_yand v_zAre unit vectors respectivelyThree coordinate components.

Using the formula I ═ T · L_IWill I₁And I₂Is converted into coordinates of the world coordinate system, the result is still I₁And I₂And (4) showing.

III. calculation

Ray tracing generated points					Points back calculated by formula
Ray tracing generated points					Points back calculated by formula			Viewpoint	Points in a scene	I₁	I₂	Exact virtual vertex	I₁	Approximate imaginary vertex	Relative deviation of
-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	Viewpoint	Points in a scene	I₁	I₂	Exact virtual vertex	I₁	Approximate imaginary vertex	Relative deviation of
-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. Algorithm implementation

Algorithm 1: pretreatment, as shown in fig. 10.

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

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

Algorithm 2 generates a virtual scene for a planar refractive body or reflector as shown in fig. 11. Has the following characteristics:

(2) the reflector and the refractor are treated uniformly;

algorithm 3 recalculates the virtual scene for a change in viewpoint position as shown in fig. 12.

To render a scene in real time, a hardware acceleration method must be used. At this time, we need a common software interface OpenGL to graphics hardware. The generation of the virtual object lays a foundation for real-time drawing. The following is the real-time rendering algorithm we use.

Algorithm 4 is a real-time rendering and display as shown in fig. 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;

(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；

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':

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

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

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

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;

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.