inside-testing operators for ray-bezier-surface intersection.

[luser- -droog]

I've been struggling with these Bezier surfaces for some time now, and I think there may be a novel shortcut for find the intersection point.

First project the surface onto a plane whose normal coincides with the ray.

Iterate through a single parametrization, drawing the initial boundary curve and the moving curve connected by lineto in a single path.

Test the projected eye-point for insidedness wrt each closed path in the parametrization. The first path to yield true, indicates a solution for that parameter. I think I can then solve for the second parameter algebraically.

It works in my imagination, but I may be deluded.

[John Reiser]

On 03/26/2013 08:33 PM, luser- -droog wrote:
> I've been struggling with these Bezier surfaces for some time now, and I think there may be a novel shortcut for find the intersection point.
>
> First project the surface onto a plane whose normal coincides with the ray.

Is the projection always one-to-one? Can there be a cusp, tangent, etc?
If the math is OK, does it still work in floating point arithmetic using
a precision of 6 to 7 decimal digits? (Does it matter in practice?)

>
> Iterate through a single parametrization, drawing the initial boundary curve and the moving curve connected by lineto in a single path.
>
> Test the projected eye-point for insidedness wrt each closed path in the parametrization. The first path to yield true, indicates a solution for that parameter. I think I can then solve for the second parameter algebraically.

Is it simple to determine those closed paths, and are they nice?

[luser- -droog]

On Wednesday, March 27, 2013 11:04:36 AM UTC-5, John Reiser wrote:
> On 03/26/2013 08:33 PM, luser- -droog wrote:
>
> > I've been struggling with these Bezier surfaces for some time now, and I think there may be a novel shortcut for find the intersection point.
>
> >
>
> > First project the surface onto a plane whose normal coincides with the ray.
>
>
>
> Is the projection always one-to-one? Can there be a cusp, tangent, etc?
>
> If the math is OK, does it still work in floating point arithmetic using
>
> a precision of 6 to 7 decimal digits? (Does it matter in practice?)
>

All good things to consider. The Beziers in the Utah teapot are fairly well behaved. But the idea of projection is to simplify. I can drop one of the equations right off the bat. Beziers preserve their properties under affine transformations, but I only hope they do the same under, say, orthogonal projection. The teapot occupies -4 < x,y,z < 4, and I've got the camera at a distance of about 10, so I think the precision should be sufficient (for 320x200 image).

>
>
> >
>
> > Iterate through a single parametrization, drawing the initial boundary curve and the moving curve connected by lineto in a single path.
>
> >
>
> > Test the projected eye-point for insidedness wrt each closed path in the parametrization. The first path to yield true, indicates a solution for that parameter. I think I can then solve for the second parameter algebraically.
>
>
>
> Is it simple to determine those closed paths, and are they nice?
>

One curve is fixed.

With a Bezier patch,

[ p00 p01 p02 p03
p10 p11 p12 p13
p20 p21 p22 p23
p30 p31 p32 p33 ]

The closed curve is
p00 moveto p10 p20 p30 curveto
p(t,p31,p32,p33) lineto
p(t,p21,p22,p23)
p(t,p11,p12,p13)
p(t,p01,p02,p03) curveto
closepath

where p(...) is evaluating a Bezier curve.

Do this for t=0..1 step delta (TBD). Draw curves, test point.

I have no idea how "efficient" this may be.

[Ross Presser]

On Tuesday, March 26, 2013 11:33:09 PM UTC-4, luser- -droog wrote:
> I've been struggling with these Bezier surfaces for some time now, and I think there may be a novel shortcut for find the intersection point.

Would it help to rotate so that the ray coincides with the x-axis? Then the y and z coordinates of the function are both zero?

[luser- -droog]

Very possibly! I've hit a sort of dead-end with my usual approach: chasing references through bibliographies. I just got the IEEE tutorial with a reprint of the Catmull paper that everybody cites. But he appears to be doing the same subdivision scheme that everybody else is.

Not a total waste, though. it does have the Sutherland Man-Machine paper.

[luser- -droog]

First draft of the projected-Bezier closed-curve inside-testing ray tracer.

Unfortunately there are no rays yet. And no tracing. And no output, either (but it did stop crashing!).

%!
(mat.ps) run
[
/n 10
/Cam [0 0 -10]
/Eye [0 0 -10]
/Rot 3 ident
>>begin

[
/proj {
Cam {sub} vop % translate to camera coords
Rot matmul % perform camera rotation
0 get % extract vector from 1x3 matrix
aload pop Eye aload pop % extract dot x,y,z and eye xyz
4 3 roll div exch neg % perform perspective projection
4 3 roll add 1 index mul
4 1 roll 3 1 roll sub mul exch % (ez/dz)(dx-ex) (ez/dz)(dy-ey)
exch
} bind def
/eval-bezier{ % [curve]
dup { v 0 get } forall
4 array astore 1 array astore transpose
TN exch matmul 0 get 0 get exch
dup { v 1 get } forall
4 array astore 1 array astore transpose
TN exch matmul 0 get 0 get exch
{ v 2 get } forall
4 array astore 1 array astore transpose
TN exch matmul 0 get 0 get
3 array astore
}

/N[[-1 3 -3 1][3 -6 3 0][-3 3 0 0][1 0 0 0]]
/t-array { % t
dup dup mul % t t^2
2 copy mul % t t^2 t^3
3 1 roll exch 1 4 array astore % [t^3 t^2 t 1]
}
/v{vert exch 1 sub get}

/tok{token pop exch pop}
/s{(,){search{tok 3 1 roll}{tok exit}ifelse}loop}
/readlist{token pop{[f 100 string readline pop s]}repeat}
/f(teapot)(r)file
>>begin currentdict{dup type/arraytype eq
1 index xcheck
and{bind def}{pop pop}ifelse}forall

/patch [ f readlist ] def
/vert [ f readlist ] def

patch {
/p exch def
p 0 get v proj moveto
p 4 get v proj p 8 get v proj p 12 get v proj curveto
0 1 n div 1 {
dup /t exch def
t-array /T exch def
/TN T N matmul def
gsave
p 12 4 getinterval eval-bezier proj moveto
p 8 4 getinterval eval-bezier proj
p 4 4 getinterval eval-bezier proj
p 0 4 getinterval eval-bezier proj curveto
closepath

%Check Point Here

grestore
} for
} forall

[luser- -droog]

On Saturday, March 30, 2013 11:31:02 PM UTC-5, luser- -droog wrote:
> First draft of the projected-Bezier closed-curve inside-testing ray tracer.
>
>
>
> Unfortunately there are no rays yet. And no tracing. And no output, either (but it did stop crashing!).
>

Added some output, and some fixes. Uploaded to
http://code.google.com/p/xpost/downloads/detail?name=tearay0.ps

And a png of the output:
http://code.google.com/p/xpost/downloads/detail?name=teapot-bezier-closed-curves-n-10.PNG

It's obvious from the picture that using the same starting curve is wrong. Each new curve should be connected to the previous curve.

[luser- -droog]

I think I've got it written. But it is slooooooooooooooooooow.

[luser- -droog]

On Thursday, March 28, 2013 1:28:43 AM UTC-5, Ross Presser wrote:

I found instructions on doing this at math.stackexchange:
http://math.stackexchange.com/questions/114512/how-to-find-the-orthonormal-transformation-that-will-rotate-a-vector-to-the-x-ax

And I went ahead and asked the Big Question:
http://math.stackexchange.com/questions/348806/intersect-a-line-with-a-bezier-surface-patch

I was strongly encouraged to use a "numerical method" rather than attempt to solve for the parameters. But I can be very stubborn. Rotating seems like it should help immensely. And in addition to rotating, I think I need to translate the origin to the line.

The equation for the intersection is
F(u,v) = R(t)

But rotating and translating makes R(t) just a unit vector in the +x direction. So F_x(u,v) = 1, and F_y(u,v) = 0, and F_z(u,v) = 0.
So we've dropped a parameter! And we've got equations relating u and v.

The size of the problem is smaller. Ergo progress. :)

[luser- -droog]

I think it may help to further rotate around the x-axis so that f(0,0) is "lower" than f(1,1).