How to raytrace Bezier surfaces?

Question

I tried this question on math.SE and surprisingly, the answer was "the equations are too nasty, just feed the function it to a numerical root-finder". But if you consider yourself "a graphics guy" like me, and have played extensively with Bezier curves for design work, I got to believe that better can be done. There is a published algorithm by Kajiya that I don't have the background to understand (Sylvester Matrices), but the related advice on math.SE was that the result is a degree-18 polynomial in t, and you still need to solve that numerically. I had another idea with similar result.

So, is it a total pipe dream to hope to solve the Ray/Bezier-surface intersection algebraically, thus making it possible to code explicitly and have super-fast super-smoothness?

Barring that, what's the fastest method for performing this calculation? Can you "find the wiggles" to get a tight bound (and target) for recursive subdivision? If you have to use a numerical root-finder (sigh), what properties does it need and is there a best choice for speed?

My original thought was about preparing for a specific surface, similar to Laplace expansion as described in the answer to my other math question about triangles. But I'd be interested in general methods, too. I'm just thinking of a fixed set of shapes, like the Utah teapot. But I'd be very interested in ways of optimizing for temporal coherence across animated frames.

Answer 1

First off, here's the Kajiya method I think you're thinking of: Kajiya, Ray Tracing Parametric Patches, SIGGRAPH 82. The tech report version might be more informative.

What I hope you get from that is that it's not impossible and it's not conceptually difficult if you don't mind getting your hands dirty with some algebraic geometry and complex numbers. However, doing it directly is absurdly expensive.

"Real" ray tracers tend to do some combination of two things:

• Placing a bounding hierarchy (e.g. AABBs) on the patch to get a good "initial value" for a numeric root finder. If you do this well, you can avoid the "wrinkle" problem.
• Tesselating the patch into DDG shells and ray tracing them like polygon meshes.

That last point sounds like it kills the "super-smoothness" requirement, but it isn't nearly as bad as that if you're using ray differentials. Matching the tessellation level to the "size" of the ray bounds the error nicely. Besides, you probably need differentials for texture coordinates anyway, so you might as well use it to control the accuracy of the intersection test too.

Exploiting temporal coherence isn't a bad idea, but exactly how you'd do that depends a lot on your scene graph representation. You might want to look at ray coherence. Ask your favourite search engine about ray packet tracing and ray reordering.

Answer 2

is it a total pipe dream to hope to solve the Ray/Bezier-surface intersection algebraically

Yes, it's a pipe dream. A bicubic Bezier patch is an algebraic surface of degree 18. To intersect a ray with this surface, you have to find the roots of a polynomial of degree 18. There is no formula for these roots -- you have to find them by numerical methods. In fact, there are mathematical results (the Abel-Ruffini theorem) telling us that there can never be formulae for roots of equations beyond degree 4. The math doesn't just say that the formulae have not yet been found; it says that they never will be found, because they can't exist.

If you really want to do analytical (algebraic) ray-tracing of curvaceous shapes, you might try using Steiner patches. These have degree 4, so the ray-patch intersection can be computed by finding the roots of a quartic (i.e. a polynomial of degree 4). There are formulae for finding roots of quartics, but they're pretty nasty, and it's surprisingly hard to write code that implements the formulae reliably.

Answer 3

Another option, which I used a couple of decades ago (yikes!), is to use Toth's scheme from 1985 that employed interval arithmetic to narrow down the search space. IIRC, eventually it will resort to Newton-Rhapson but, again IIRC, I think it rarely required more than one or two steps to get to a good solution.

Though I haven't looked at it (well, apart from a quick glance) Mitchell has published some more recent work on ray tracing with interval maths.

(I should add that, if you are only doing Bezier surfaces, then the interval method might be a bit "overkill" since you can use tricks like blossoming to get bounds and derivatives. If, however, you combine Bezier curves with other functions, e.g. rotation around an axis, then its generality is more useful.)

Answer 4

https://www.shadertoy.com/results?query=bezier sort by age, in case of compatibility issues:

,...shows many solutions of many spline-subsets, either returning the distance to a 2d spline, or tracing a 3d patch. Splines and patches come in many forms. heavensine beind simplest, bezier being simple, nurbs being overly complex. The more constrains yo add to your spline, the simpler it gets. NURBS is extension overkill; - its Non-Uniform-ness of weights (the "NU") diminishes efficiency in comparison to to more symmetric splines - its Ration-al-ness (the R) also adds some complexity, for segmenting (rationing) and mixing with nearby segments (recursively solved).

bezier-patch-tracing is root-solving and with that comes contextual prioritization on precision; in what order to solve the quadratic equation. this becomes impractical on higher exponents than cubic, due to exponential complexity and precision loss.

ray-marching==sphere-tracking is the simpler heuristic approach to root-solving, which seems to be the simple and most efficient solution to rendering most splines patches.

Lagrange-representation simplifies tracing/marching (as the L-points are ON the spline while the ControlVector-points (of the exact same spline) are rarely on the spline)

The special case of a heavensine-spline, where first derivatives of stat and end are ==0. simplifies continuity and involves less differentials (less subtraction). A heavensine-patch can be traced efficiently in a single pass: https://www.shadertoy.com/view/4djfW3 while other cubic (or higher) splines make the heuristic sphere-tracking/ray-marching approach more efficient (and "precise enough") than daring to analytically calculate all the roots to keep the smallest positive root (with exponentially accumulating precision errors for each root).

---

In computer graphics, splines and patches have been nearly completely replaced by z-brushing by 2006. z-brushing uses displacement maps with homogeneous coordinates, or even using a "type" that us a union of sphere and linesegments (linesegments have a radius of 0, spheres have a length of 0, a union is simple and useful). For a minor loss in precision for a big gain in performance at relatively low memory cost for a look-up-table, that is easily made dynamic on a gpu.

Answer 5

https://www.shadertoy.com/view/MldczM Is ANALYTIC intersection of a ray with a triangular b-spline, 3 quadratic bezier splines, 3 CVs for each spline, 3 corner CVs are shared by 2 splines. All cv heights are orthogonal to the triangle plane. It solves for <=2 roots in barycentric coordinates. There's never 3 intersections, so this is a surprisingly simple tracing of a curved function. The first derivative is super short, too.

ESDF keys for camera movement The parent shader in the comments has less optimized, less precise, more repetitive, naive simpler code.

It still has the error of rendering the negative surface if the camera is inside the prism of the triangle (above or below triangle). This seems to be a simpler special case, with only 1 root, where it fails to ignore the other root. The branch to solve this may be rather simple.