# Ray intersecting a quad mesh

I am trying to solve the math behind rendering a quad-mesh surface. MatLab for instance can take a regularly spaced (x,y) grid with arbitrary third-dimension (z) values, treat each four neighbouring coordinates as 3d quadrilaterals, and render each of them as a facet of the surface.

I'm trying to do this with ray tracing which would be easy if the quads were planar (all corners on the same plane), but since every coordinate can be arbitrary most quads will likely not be on the same plane, a so-called "skew-quadrilateral" (you can see how most quads in the above MatLab image "twist and turn"). Does anyone know the steps or pseudocode to intersect a ray with a skew quadrilateral, I've tried looking around but couldn't find it?

I don't even know if such a thing could be possible since you could have three corners of a quadrilateral with z-coordinates of 0 and suddenly the last corner with a very high z-coordinate, implying some sort of bending or breaking of the surface. I mean what would the following grid even look like, perhaps four quadrilaterals that start on the same level and bend towards a high point in the middle?

(0,0,0) (0,0,0) (0,0,0)
(0,0,0) (0,0,5) (0,0,0)   ===>    ?
(0,0,0) (0,0,0) (0,0,0)


I suppose the main difference could be that MatLab does not use ray tracing to render each quadrilateral, but rather some type of 3d to 2d reprojection. If so, does anyone know the usual non-raytracing way of rendering a quad mesh surface?

On the other hand I have read somewhere that quadrilateral surface meshes are indeed used in 3d movie or game developing where ray tracing is certainly used, so it should be possible.

Here are some relevant quotes and links that describe how MatLab treats the surface:

http://se.mathworks.com/help/matlab/visualize/representing-a-matrix-as-a-surface.html

"The plot is formed by joining adjacent points with straight lines."

"Mesh plots are wire-frame surfaces that color only the lines connecting the defining points. Surface plots display both the connecting lines and the faces of the surface in color."

"...generates a colored, faceted view of the surface and displays it in a 3-D view. Ordinarily, the facets are quadrilaterals, each of which is a constant color..."

http://se.mathworks.com/help/matlab/ref/surf.html

"Each point in the rectangular grid can be thought of as connected to its four nearest neighbors."

• Typically in raytracing, quads (as well as other surface meshes like Bézier patches are converted to triangular meshes first. You can compute the intersection between a ray and any quadrilateral, but the equation is nasty (slow to calculate), whereas the intersection between a ray and a triangle is easy. Parametric patches like Bézier surfaces are even worse. Commented Apr 9, 2016 at 15:23
• When your world has millions of triangles, there are many options how to limit to intersection tests to a smaller set of triangles. Typically, you "bound" each triangle by a box or a sphere (to minimize the effort needed to discard surely-not-intersecting triangles), and sort these spatially. There are many ways to do that, but octrees, binary space partitioning, and nested bounding volumes are the most typical approaches taken. Commented Apr 9, 2016 at 15:29
• Thats also what i heard, so i also made a version that divides each four neighbouring points into two triangles and intersects the triangles as you said, but its sort of arbitrary in which direction the quad is split. How are the quads typically converted to triangles? Also, the results look like quads broken into two triangles instead of the preferred whole quads shown in the matlab example image, and matlab claim they use a quadmesh instead of a triangle mesh, so im sure there must be something im missing here. I will optimize with spatial indexing in the end. Commented Apr 9, 2016 at 16:03
• Most commonly in the same direction. Yes, it does look bad, but the idea is to use so many triangles you do not notice. Matlab does not do raytracing, it just draws polygons (with a surface normal calculated as the average of vertex normals, or as the average of the triangle normals if the quad were to split into triangles, I think) with flat shading. You could split each quad into four triangles, computing a new center vertex (at center of the four quad vertices), if you dislike the quads-to-two-triangles look. Commented Apr 9, 2016 at 16:16

In practice, raytracers tend to decompose surfaces into triangular meshes first, because the math needed is so much simpler.

However, you asked how to calculate the intersection between a line and a quadrilateral in 3D, so here goes.

Let's define your ray using an unit vector $\hat{n}$ (unit referring to unit length, $\lvert\hat{n}\rvert=1$) that passes through some point $\vec{p}_0$, $$\vec{p}_{RAY}(t) = \vec{p}_0 + t\,\hat{n}$$

The quadrilateral is a bit more complicated. Let's say the four corners are $\vec{p}_1$, $\vec{p}_2$, $\vec{p}_3$, and $\vec{p}_1$, with $\vec{p}_1$ and $\vec{p}_4$ diagonally across from each others. We can trace the surface using two variables, $0 \le u, v \le 1$, where $u=0,v=0$ refers to $\vec{p}_1$, $u=1,v=0$ to $\vec{p}_2$, $u=0,v=1$ to $\vec{p}_3$, and $u=1,v=1$ to $\vec{p}_4$, using bilinear interpolation of the coordinates: $$\vec{p}_{QUAD}(u,v) = \left ( \vec{p}_1 (1-u) + u \vec{p}_2 \right ) (1-v) + v \left ( \vec{p}_3 (1-u) + u \vec{p}_4 \right )$$ which is, after rearranging the terms, the same as $$\vec{p}_{QUAD}(u,v) = \vec{p}_1 + u \; v \; ( \vec{p}_4 - \vec{p}_3 - \vec{p}_2 + \vec{p}_1 ) + u \; ( \vec{p}_2 - \vec{p}_1 ) + v \; ( \vec{p}_3 - \vec{p}_1 )$$

The intersection is, of course, $$\vec{p}_{RAY}(t) = \vec{p}_{QUAD}(u,v)$$ In three dimensions, that is actually three equations with three unknowns, $$\begin{cases} x_0 + t n_x = x_1 + u \; v \; ( x_4 - x_3 - x_2 + x_1 ) + u \; ( x_2 - x_1 ) + v \; ( x_3 - x_1 ) \\ y_0 + t n_y = y_1 + u \; v \; ( y_4 - y_3 - y_2 + y_1 ) + u \; ( y_2 - y_1 ) + v \; ( y_3 - y_1 ) \\ z_0 + t n_z = z_1 + u \; v \; ( z_4 - z_3 - z_2 + z_1 ) + u \; ( z_2 - z_1 ) + v \; ( z_3 - z_1 ) \end{cases}$$ This can be solved, but the solution contains dozens of terms, and is therefore terribly slow to compute. (I asked Maple for the exact solution. There are two (i.e., $(t_1,u_1,v_1)$ and $(t_2,u_2,v_2)$, but as they don't fit in one screenful, I decided they are way too long to reproduce here.)

Biquadratic and bicubic Bézier surfaces can be solved the exact same way, it's just that there are more terms (up to $u^3$ and $v^3$, and 9 (biquadratic) 16 (bicubic) coordinates per dimension), and thus the result is even more complicated and slow to compute.

• Makes sense now. I guess i was simply asking the wrong question, based on your demonstration that calculating the intersection with a skew quad is so expensive/complicated. Commented Apr 18, 2016 at 7:38

There are many questions, here. I'll take stab at a few of them.

The easiest way to render a set of triangles is a z-buffer algorithm. You paint each triangle into a pixel array, and you keep track of z-depth at each pixel. Pixels that are in front over-write pixels that are behind. Most graphics packages (like OpenGL or DirectX) will do this for you; all you have to do is give them the list of triangles.

Another option is the so-called "painter's algorithm". You sort the triangles by z-depth, and then paint them in order. Again, the front triangles over-write the back ones.

Ray-tracing is typically the slowest algorithm, and most people don't use it unless they want some very sophisticated graphical effects, like inter-object reflection, or refraction through a translucent material. Ray tracing is not typically used in games. It's used in movie animation, where image quality is more important than speed of computation.

How to break a quadrilateral into a triangle: there are two choices. Choose the one that produces the least deviation between the triangles and the original quad.

Intersecting a ray with a "skew" quadrilateral. The quadrilateral is actually a hyperbolic paraboloid, which is a quadric surface (of degree 2). So, in general, any ray will intersect the quad in two places. The points of intersection can be found by solving a quadratic equation where the variable is the parameter value on the ray. That's what's described in the other answer. I'm surprised that it's so complicated. I would expect that you can eliminate the surface parameter values, leaving just a quadratic in the ray parameter. But, I haven't tried to do this, so maybe it's harder than I think.

I think decomposing into triangles is the right approach. If you want the graph to look more smooth and less "tesselated", you can vary the shade across each triangle. Instead of the color being constant on the triangle, you can linearly vary the color (Gouraud shading) or linearly vary the surface normal (Phong shading). Or if you want a "quad" appearance as opposed to a "triangulated" appearance, just make sure you use the same color to paint the two triangles that came from one original quad.

• I think that was what i was missing. I thought raytracing was the only way and didnt know about the z buffer algorithm. So was then able to know what to search for, and found eg this great tutorial: scratchapixel.com/lessons/3d-basic-rendering/… Commented Apr 28, 2016 at 8:08