[Algorithms] line trace against parametric surface

[Kyle D. <ky...@3d...>]

Do there exist any algorithms or papers relating to finding the first 
point of intersection between a ray/line segment and a curved surface 
that don't involve any tesselation of the surface?

Specifically, the inputs I've got are either a point and a direction 
(infinite ray) or two points (line segment) for the former and a 
collection of connected 3x3 3D Bezier patches for the latter. The only 
essential output I'm looking for is a contact position and the surface 
normal of the curve at that point.

(In case my curve description is unclear, I've got a set of data that 
looks like:

  x...*...x...*...x.
  .   .   .   .   .
  .   .   .   .   .
  *...*...*...*...*.
  .   .   .   .   .
  .   .   .   .   .
  x...*...x...*...x.
  .   .   .   .   .

...where 'x' specifies an edge control point of a surface and '*' 
specifies an internal control point. The control points aren't 
guaranteed to be regular or aligned on any sort of grid, but I fear 
attempting any more complex with my meager ASCII art skills.)

While it would be less useful for my current problem, I'd also be very 
interested in any generalized line/curve intersection methods, 
especially those that don't involve tesselation of the curves.

  - Kyle