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

Hi everyone!

Please check the following reasoning, and if you have any comments about it,
please **MAIL** it to me...

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  
 
 [ 1 post ] 

 Relevant Pages 

1. ***HELP*** with CYRUS-BECK algorithm

2. What's wrong with this EPS ???

3. What's wrong with this simple script?

4. what's wrong in this check?

5. What's wrong with window.find()?

6. what's wrong with psutils?

7. Newbie: What's wrong with this code?

8. What's wrong with my PS file?

9. What's wrong with This !!!!

10. What's wrong with the radio button

11. What's wrong with this source code?

12. What's wrong with JScript?

 

 
Powered by phpBB® Forum Software