gdalgorithms-list

[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

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
> 

[Algorithms] Re: line trace against parametric surface

[<gd...@er...>]

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

You might want to google for "Bezier Clipping method". Here are a few papers 
on intersecting a ray against various implicit representations: 

ray intersection bezier patch:
http://www.tricity.wsu.edu/~bobl/personal/mypubs/2002_raybez.pdf 

ray intersection implicit convex objects:
http://www.dtecta.com/papers/jgt04raycast.pdf 

ray intersection on implicit csg surface:
http://www.win.tue.nl/vis/papers/2001/lipschitz.pdf 

graphics gem:
http://www1.acm.org/pubs/tog/GraphicsGems/gemsiv/curve_isect/ 

Erwin Coumans
http://www.continuousphysics.com 

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
>