RE: [Algorithms] line trace against parametric surface

[Tom F. <tom...@ee...>]

> 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?

For anything more complex than a quadratic surfaces (spheres, conic
sections, etc), the explicit methods get really hairy. Specifically, for a
surface that is qudric (i.e. most Bezier-like formulations), you need to
find the roots of an 18-degree polynomial. That gets very expensive, very
quickly.

In practice I believe it's cheaper (and simpler) to check for intersections
with the bouding volume of the surface, and if you get one, subdivide and
check with the two new bounding volumes, etc.

TomF.


> -----Original Message-----
> From: gda...@li... 
> [mailto:gda...@li...] On 
> Behalf Of Kyle Davis
> Sent: 02 November 2005 21:35
> To: gda...@li...
> Subject: [Algorithms] line trace against parametric surface
> 
> 
> 
> 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
> 
> 
> -------------------------------------------------------
> SF.Net email is sponsored by:
> Tame your development challenges with Apache's Geronimo App 
> Server. Download
> it for free - -and be entered to win a 42" plasma tv or your very own
> Sony(tm)PSP.  Click here to play: http://sourceforge.net/geronimo.php
> _______________________________________________
> GDAlgorithms-list mailing list
> GDA...@li...
> https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
> Archives:
> http://sourceforge.net/mailarchive/forum.php?forum_id=6188
>