GNOME.org
 

[LIBART] art_svp_intersect BUG

I'm using the latest CVS version which I think is marked 2.3.10 in a python extension.

The problem I'm having is numerical instability in intersecting thin horizontal strips and a triangle. In
renderPM we use intersection to provide clipping path capabilities.


To avoid possible problems of interpretation etc I made a small addition
to testart.c and the output is shown below also included is a small gif
showing the effect of the 'BUG'. The two stripes are about halfway up the
 side of the clipping triangle and cover a vertical height span of two pixels
 the resultant intersects have very different sizes when they should be
 similar. Using my debugger I trace this to different behaviour near the lines

  if (y == left_seg->y0)
    {
      if (y != right_seg->y0)
        {
#ifdef VERBOSE
          art_dprint ("art_svp_intersect_test_cross: intersection (%g, %g) matches former y0 of %lx, %lx\n",
                    x, y, (unsigned long)left_seg, (unsigned long)right_seg);
#endif

in the 'bad' case y-right_seg->y0=7.10543e-015 in the ok case this is zero.
This is clearly a numerical problem in that the original data was manipulated
using transforms before we got to this condition, but surely a production library
should not rely on exactness of floating point arithmetic to such an extent.


##################################################################
#  test function
static void
test_intersect1(void)
{
  ArtVpath vp0[] = {
    { ART_MOVETO, 10, 10},
    { ART_LINETO, 60, 60},
    { ART_LINETO, 110, 10},
    { ART_LINETO, 10, 10},
    { ART_END, 0, 0}
        }, 
        vp1[]= {
                        {ART_MOVETO, 110,34.999999999999993},
                        {ART_LINETO, 10,35},
                        {ART_LINETO, 10,36},
                        {ART_LINETO, 110,35.999999999999993},
                        {ART_LINETO, 110,34.999999999999993},
                        {ART_END, 0,0}
        },
        vp2[]={
                {ART_MOVETO, 110,35.999999999999993},
                {ART_LINETO, 10,36},
                {ART_LINETO, 10,37},
                {ART_LINETO, 110,36.999999999999993},
                {ART_LINETO, 110,35.999999999999993},
                {ART_END, 0,0}
                },
        *vp[] = {vp0, vp1, vp2};
  ArtSVP *svp[3], *svpi;
  int i;
  for(i=0;i<3;i++){
        svp[i]=art_svp_from_vpath(vp[i]);
        printf("vpath[%d]\n", i);
        print_vpath(vp[i]);
        printf("svp[%d]\n", i);
        print_svp(svp[i]);
        }
  for(i=1;i<3;i++){
        svpi = art_svp_intersect(svp[i],svp[0]);
        printf("svp[%d] & svp[0]\n", i);
        print_svp(svpi);
        art_svp_free(svpi);
        }

  for(i=0;i<3;i++){
        art_svp_free(svp[i]);
        }
}

###############################################################################
# test output
vpath[0]
10 10 moveto
60 60 lineto
110 10 lineto
10 10 lineto
stroke
svp[0]
segment 0, dir = down (10.000000, 10.000000) - (60.000000, 60.000000)
  (10, 10)
  (60, 60)
segment 1, dir = up (10.000000, 10.000000) - (110.000000, 60.000000)
  (10, 10)
  (110, 10)
  (60, 60)
vpath[1]
110 35 moveto
10 35 lineto
10 36 lineto
110 36 lineto
110 35 lineto
stroke
svp[1]
segment 0, dir = down (10.000000, 35.000000) - (110.000000, 36.000000)
  (110, 35)
  (10, 35)
  (10, 36)
segment 1, dir = up (10.000000, 35.000000) - (110.000000, 36.000000)
  (110, 35)
  (110, 36)
  (10, 36)
vpath[2]
110 36 moveto
10 36 lineto
10 37 lineto
110 37 lineto
110 36 lineto
stroke
svp[2]
segment 0, dir = down (10.000000, 36.000000) - (110.000000, 37.000000)
  (110, 36)
  (10, 36)
  (10, 37)
segment 1, dir = up (10.000000, 36.000000) - (110.000000, 37.000000)
  (110, 36)
  (110, 37)
  (10, 37)
svp[1] & svp[0]
segment 0, dir = down (35.000000, 35.000000) - (85.000000, 35.000000)
  (85, 35)
  (35, 35)
segment 1, dir = up (84.000000, 35.000000) - (85.000000, 36.000000)
  (85, 35)
  (84, 36)
segment 2, dir = down (10.000000, 35.000000) - (35.000000, 36.000000)
  (35, 35)
  (10, 36)
segment 3, dir = down (10.000000, 36.000000) - (84.000000, 36.000000)
  (10, 36)
  (84, 36)
svp[2] & svp[0]
segment 0, dir = down (10.000000, 36.000000) - (37.000000, 37.000000)
  (10, 36)
  (37, 37)
segment 1, dir = up (10.000000, 36.000000) - (84.000000, 36.000000)
  (10, 36)
  (84, 36)
segment 2, dir = up (84.000000, 36.000000) - (110.000000, 37.000000)
  (84, 36)
  (110, 37)
segment 3, dir = up (37.000000, 37.000000) - (110.000000, 37.000000)
  (110, 37)
  (37, 37)

#########################################################################
# the real problem in action
[ Section: 1/1 File: shobj.gif UUencoded by: Turnpike Integrated Version 5.01 U ]

begin 644 shobj.gif
M1TE&.#=A>`!X`(<``/____S[^O?U\??T\/+NZ/+MYNWHW^WFW>CAUNC?T^/;
MS>+7R=_4Q-W0O]K.N]C)M=7'LM/"K,_`J(B\@(6]@(._@(#`@'^_?X2\?X&]
M?\Z[HLJZG\BSF,6SEIVR@)^P@)NP?Y6V@)>T@):S?YFQ?Y"X@(VY@(RX?XJ[
M@(:[?XFY?Y*W@)&U?XZW?Y.T?\.LCL"MC;NFA+ZEA+BB?[V??[J ?\ =?\">
M?[B=>]"8 - 6@-"6?\V7?\N:@,B;@,B:?\J9?\6;?[&G *VG?ZRJ@*NH?ZBJ
M?Z:K?Z2N **O@*.L?Z"N?YZO?[2F + D?["F?[6C?[:?>[&8<K.6<?]_?_R`
M?_F!?_>"?_2$?_&%?^^&?^R(?^J)?^>*?^2,?^*-?]N2 ->2?]63?]*5?]J1
M?]V/?]^.?ZR2::Z/9Z>+8*B'7:*%5Z.`4YQ^39YY2I=W1)ER0))Q.Q]P`!IR
M``]X``IZ``5]`!1U`)1K-HYJ,HED*8YC+(E<(H1=($A;`$->`#EC`#Y `#1E
M`"YH`"EK`"1M`(15&7]7%WI0#G].#W5*!6U)`&A+`'I'!7)&`'=#`&).`%U0
M`%A3`%-6`$Y8`+`G`*LI`*8L`*$O`)PQ`)8T`)$V`(PY`(<\`((^`'Q!`/\`
M`/D"`/0%`.\'`.H*`.0-`-\/`-H2`-44`-`7`,H:`,`?`+LA`+8D`,4<````
M````````````````````````````````````````````````````````````
M````````````````````````````````````````````````````````````
M````````````````````````````````````````````````````````````
M````````````````````````````````````````````````````````````
M````````````````````````````````````````````````````````````
M`````````````````````"P`````>`!X`$`(_P`!"!Q(L*#! P@3*ES(L*'#
MAQ`C2IQ(L:+%BQ S:MS(L:/'CR!#BAQ)LJ3)DRA3JES),B.*.S!CPE0!H*;-
MFSASZMS)LZ?/GT!]? A$M*C1HTB+,@'`M*G3IU"C2IU*M:I5J4T8:=W*M:O7
MKV"Y  %`MJS9LVC3JEW+MJU9'YOBRIU+MZ[=NWCS;OH!H*_?OX`#"QY,F'`9
M5H 3*U[,N+'CQY`C,RX#H++ERY S:]Y<.4NISZ!#BQY-NK3ITZA3G\X"H+7K
MU[!CRYY-N[;MV[ASZ][-N[?OW\"#"Q].O+CQX\B3*U_.O+GSY]"C2Y].O;KU
MZ]<M7`#`O;OW[^##B_\?3[Z\^?/HOX<@Q+Z]^_>$7`"83[^^_?OX\^O?S[^_
M?X``!!J95-# 080)%1XT`L#A0X 1)4ZD6-'B18PT/FWDV-'C1Y`A17*D`<#D
M290I5:YDV=+E2AV79,ZD6=/F39PY=>8<`\#G3Z!!A0XE6A1`EU1)E2YEVM3I
M4ZA1I4Y-V 7`5:Q9M6[E>K5**+!AQ8XE6];L6;1IU:X=6P7`6[AQY<ZE6]?N
M7;QY]>[EV]?O7\"!!0\F7-CP8<2)%2]FW-CQ8\B1)4^F7-GR9<R9-6_FW-GS
M9]"A18\F7=KT:=2I5:^&3*'.ZSH8`,RF7=OV;=RY=>_FW=OW;]LEY`PG7GS_
M>`L`R94O9][<^7/HT:5/IRZ=A"#LV;5OWTX"P'?PX<6/)U_>_'GTZ=6#1^+'
M_7OX\>7/5P+`_GW\^?7OY]_?/T```@<2+&CPX,`AD18R;.CP(<2(0P!0K&CQ
M(L:,&C=R[.AQAJ.0(D>2+&GRY$E%B`[UT9,GSILV:]*<D1(E!HP.&R1`<,!`
M`0(#!`0$`&#T*-*D2I<R76JC$]2H4J=2K6KU:E4;`+9R[>KU*]BP8L>"Y9'I
M+-JT:M>R;>OVK5H>`.;2K6OW+MZ\>O6&J>3W+^#`@@<3+FSXL-\P`!8S;NSX
M,>3(D %\<67Y,N;,FC=S[NSYL^<O`$:3+FWZ-.K4_Z.WG&KM^C7LV+)GTZYM
M^W;L+0!V\^[M^S?PW5=&$2]N_#CRY,J7,V_N_/FH*P"F4Z]N_3KV[-JW<^_N
M_3OX\.+'DR]O_CSZ].K7LV_O_CW\^/+GTZ]O_S[^_/KW\^_O'R`` 0,)%C1X
M$&%"A0L9-G3X$&)$B1,I5K1X$6-&C1LY=O3X$61(D2-)EC1Y$F5*E2M9MG3Y
M$F9,F3-IUK1Y$V=.G3MY]O3Y$VA0H4.)%C5Z%&E2I4N9&JU QTX&`%.I5K5Z
M%6M6K5NY=O7Z5>L$.F/)I !P%FU:M6O9MG7[%FY<N7/5FIAS%V_>$P#X]O7[
M%W! P8,)%S9\&#&`%848-_]V[)@%`,F3*5>V?!ES9LV;.7?>+&)0:-&C28L>
M`0!U:M6K6;=V_1IV;-FS6WL`=!MW;MV[`8$`\!MX<.'#B1<W?AQY<N7`D_QQ
M_AQZ=.G1EP"P?AU[=NW;N7?W_AT\^".4R)<W?QY]>O)'`+1W_QY^?/GSZ=>W
M?W\^$4G[^??W#U"2P($$"Q(L`B"APH4,&SI\"#&BQ(D+A4"ZB#&CQHT<.UY\
M`B"DR)$D2YH\B3*ERI50%KE\"3.FS)DT94(! # GSIT\>_K\"32HSQJ/BAH]
MBC2ITJ5,BS9*9(C/'CQPW+!1 V8*#ADO &B(\*#!@@0'"@P(`""MVK5LV[I]
M^_;_AJ>Y=.O:O8LWKUZ[-P#X_0LXL.#!A`L;/AR$D^+%C!L[? PY<N0 `"I;
MOHPYL^;-G#MK[J$IM.C1I$N;/HTZM6@@`%J[? T[MNS9M&N[SH$IM^[=O'O[
M_ T\N \=`(H;/XX\N?+ES)F+L00]NO3IU*M;OXX]NQ `W+M[_PX^O/CQW\&T
M.H\^O?KU[-N[?P\_/1D`].O;OX\_O_[]`,RL`KA*X$""!0T>1)A0X<*#9 `\
MA!A1XD2*%2=Z4951XT:.'3U^!!E2Y$ O`$R>1)E2Y4J6)KF@@AE3YDR:-6W>
MQ)E3ITPN`'S^!!I4Z%"A6DP=19I4Z5*F39T^A1JUJ18`=56M7L6:56M5+*2\
M? 4;5NQ8LF7-GD6+% L`MFW=OH7[UHHHNG7MWL6;5^]>OGW]_JUK!<! PH4-
M'P9`!=1BQHT=/X8<6?)DRI4M0Z8"0/-FSIT]?P8=6O1HTJ5-GT:=6O5JUJU=
2OX8=6_9LVK5MW\:=6_?I ``[
`
end

sum -r/size 46554/3400 section (from "begin" to "end")
sum -r/size 57951/2448 entire input file

-- 
Robin Becker
[Date Prev][Date Next]   [Thread Prev][Thread Next]   [Thread Index] [Date Index] [Author Index]