Rogers' CYRUS-BECK ***WRONG***???!!
Author Message Rogers' CYRUS-BECK ***WRONG***???!!

Hi everyone!

After examining with more attention the Rogers' 2D CYRUS-BECK algorithm I realised
it is WRONG, as far as I can see. Well, the proof is given below. Assume all
uppercase letters as vectors and lowercase as points. I give an exemple where it's
trivial that the line is outside a polygon and the algorithm says it is inside:

+------+--------+-----+-------+---------+-----+----+
| Ppol |   N    | D.N |  fi   |   W     | W.N |  t |
+------+--------+-----+-------+---------+-----+----+
|(0,-2)| (2,0)  |  1  | (0,0) | (1,-1)  |  2  | -2 |
+------+--------+-----+-------+---------+-----+----+
|(-3,0)| (0,-3) |-1.5 | (0,2) | (1,-3)  |  9  |  6 |
+------+--------+-----+-------+---------+-----+----+
|(0,2) | (-2,0) | -1  | (3,2) | (-2,-3) |  4  |  4 |
+------+--------+-----+-------+---------+-----+----+
|(3,0) | (0,3)  | 1.5 | (3,0) | (-2,-1) | -3  |  2 |
+------+--------+-----+-------+---------+-----+----+

Ppol= vector defined by 2 points of an edge the polygon to be tested
N   = normal vector to the edges
D.N = dot product between the direction vector of the line and the normal
(written DxN in the program given before)
fi  = points of the polygon
W   = vector defined between p1 (see below) and fi
W.N = dot product between W and N
t   = parameter of the straight line to be checked where an intersection occurs

==> p1=(1,-1), p2=(1.5,-1.5) <-- straight line between this 2 points is the one
tested
==> D= p2-p1 ==> D=(0.5,0.5)
==> W= p1-fi

Try the algorithm with this example (SEE: Procedural Elements for CG,
David Rogers)

****SOLUTION****

After knowing that a line is theoretically (given by the algorithm) trivially
"IN" that is, "tu=1.0 and tl=0.0", check if any W.N was negative. If at least one
was negative, the line is TOTALLY out since p1 is out. This happens because the
algorithm can't distinguish between a trivially inside line and a line that is
totally out. All the other cases the algorithm is OK.

I've created an "outside" variable:

==>  int i,j, invisible, outside;  /* locate this line in the program given
before */

and:

tl=0; tu=1;
==>     outside=invisible=0;

and:

if(DxN==0)
{ if(WxN<0) {invisible=1; break;}
else continue;
}
==>   if(WxN<0) outside=1;
t= -WxN/DxN;

and:

if((invisible)||(tl>tu)) continue;
==>    if(outside && (tl==0.0) && (tu==1.0)) continue;
free(N);

With this, the program works.
The following cases were tested (postscript file), and it worked with these
cases:

%!
/draw_poly
{ /np exch 1 sub def
/arr exch def arr 0 get aload pop
moveto
1 1 np { arr exch get aload pop lineto } for
arr 0 get aload pop lineto
} bind def

50 250 translate
0.0 0.0 moveto
30 30 scale
[[0.0 0.0]
[0.0 11.5942033161315301]
[11.0267417074506913 15.1770101134445046]
[17.8416437317122387 5.7971037060037176]
[11.0267436001553065 -3.58280423799886671]
] 5 draw_poly stroke

[[9.46295800062754111 -1.68660282956325003]
[8.34492405265779347 -2.0498742051597274]
[8.1588315109105416 -1.79373984591598745]
[8.596064646583363 -0.732205638202209741]
[8.73641538272597451 -0.686602903976572199]
] 5 draw_poly stroke

[[9.07146667055936007 -3.04987413074640568]
[9.22951138053090325 -2.99852227394333948]
[9.6588315321551601 -1.95619956363750225]
[9.46295800062754111 -1.68660282956325003]
[8.34492405265779347 -2.0498742051597274]
] 5 draw_poly stroke

[[9.07146667055936007 -3.04987413074640568]
[9.22951138053090325 -2.99852227394333948]
[9.15883165188115278 -3.17012168769358782]
] 3 draw_poly stroke

[[0.575126459104368992 -0.866231306382081678]
[0.726550103311835338 -0.817030764995151926]
[0.658831404687457045 -0.981441257308409254]
] 3 draw_poly stroke

0.0 -2.0 moveto
0.0 15.0 lineto stroke
-1.0 0.0 moveto
18.0 0.0 lineto stroke
showpage

Thu, 17 Aug 1995 21:57:56 GMT

 Page 1 of 1 [ 1 post ]

Relevant Pages