Friday, November 17, 2006

Ray tracing bilinear patches

I'm going to try to reimplement the displacement map method I did with Brian Smits and Mike Stark a few years ago. A key part of that method is intersecting bilinear patches. Given a ray o+tv and a patch with vertices p00, p01, p11, and p10 we have

o + tv = (1-u)(1-v)p00 + u(1-v)p10 + (1-u)v p01 + uv p11

This is three equations (x, y, and z) and three unknowns (t, u, v). The way Brian and I solved this was to eliminate t by using 2 of the equations and then solve the uv system directly. A similar approach is used in Shaun Ramsey et al.'s jgt paper. This has always been unsatisfactory to me because it chooses an arbitrary ordering of the dimensions. Perhaps a numeric solution would be more robust?

Another possibility is to use Kajiya's old trick. Consider the ray as the intersection of two planes

(p - p0) dot N0 = 0
(p - p1) dot N1 = 0

If you substitute
p = (1-u)(1-v)p00 + u(1-v)p10 + (1-u)v p01 + uv p11

into both the plane equations above then you get two equations in uv of the form:
Auv + Bu + Cv + D = 0 (1)
auv + bu + cv + d = 0 (2)

If you solve one of those for u and then plug it into the other, you get a quadratic in v. That leaves four possibilities of what to do first:

solve (1) for u
solve (1) for v
solve (2) for u
solve (2) for v

There is also a degree of freedom for which planes to use. In any case seems more stable than the three equations, 2 unknowns method above.