Re: [Algorithms] line trace against parametric surface

[Mark D. <duc...@ll...>]

Hi Kyle,

The most general, fast and robust algorithm that I know for
ray-versus parametric patch is this:

http://portal.acm.org/citation.cfm?doid=97916

Nishita, T., Sederberg, T. W., and Kakimoto, M. 1990. Ray tracing trimmed 
rational surface patches. In Proceedings of the 17th Annual Conference on 
Computer Graphics and interactive Techniques (Dallas, TX, USA). SIGGRAPH '90. 
ACM Press, New York, NY, 337-345. DOI= http://doi.acm.org/10.1145/97879.97916

The basic process involved is Bezier clipping, to produce a kind of
interval Newton iteration.  Of course you still need the usual space
partitioning hierarchy to decide which patches to test against.

Cheers,

--Mark D.

Kyle Davis wrote:
> 
> 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
>