[SVG] Fix infinite curveLength() loop.

[SVG] Fix infinite curveLength() loop.

Some degenerate curves may not split, forcing curveLength() into an
infinite loop.

The CL catches this condition and allows the computation to progress.

BUG=349873
R=schenney@chromium.org,pdr@chromium.org,fs@opera.com

[Stephen Chennney, 2014-03-07 16:25:31]

There is a much better way to fix this. And the test.

https://codereview.chromium.org/190943002/diff/1/LayoutTests/svg/custom/infin...
File LayoutTests/svg/custom/infinite-path-traversal.svg (right):

https://codereview.chromium.org/190943002/diff/1/LayoutTests/svg/custom/infin...
LayoutTests/svg/custom/infinite-path-traversal.svg:3: <path class="path"
d="M0,545.0565630820508C1.410179640718563,545.0565630820508,5.640718562874252,545.0565630820508,8.461077844311378,545.0565630820508S14.10179640718563,545.0565630820508,16.922155688622755,545.0565630820508S24.640831568216868,348.1219602687166,25.38323353293413,346.87991373394766S33.80457352895588,516.4132039204021,33.84431137724551,516.745613175179S39.48502994011976,488.4346632683071,42.30538922155689,488.4346632683071S50.024065101150995,517.9876597099478,50.76646706586826,516.745613175179S59.2192417940836,460.2765165970338,59.227544910179645,460.12371336143514S67.64888490620139,204.99275494481137,67.68862275449102,205.32516419958824S76.12928529944081,601.4393777758272,76.1497005988024,601.6784628957945S84.54917627836032,403.91405790534435,84.61077844311377,403.50181354769137S93.04414124151963,488.156457834885,93.07185628742516,488.4346632683071S101.47133196698307,573.7797573465757,101.53293413173652,573.3675129889227S109.96325106733464,375.4837980718618,109.99401197604791,375.19086364081954S117.4540267497611,402.15228390698314,118.45508982035929,403.50181354769137S126.88794866020186,432.0934615467429,126.91616766467065,431.8127634545633S135.3156433442286,6.736270493832191,135.37724550898204,7.148514851485174S143.83385203749947,544.9443546851512,143.83832335329342,545.0565630820508S151.55699923288753,433.0548099893322,152.2994011976048,431.8127634545633S160.69887687716272,516.333368817526,160.76047904191617,516.745613175179S166.4011976047904,545.0565630820508,169.22155688622755,545.0565630820508S177.4513792856326,517.519398907553,177.68263473053892,516.745613175179S185.91245712994402,487.6608775359331,186.14371257485033,488.4346632683071S194.5843751198001,573.1284278689554,194.60479041916167,573.3675129889227S202.83461281856674,685.8375268840362,203.06586826347305,686.6113126164101S211.41926053108688,630.529890214116,211.52694610778445,629.9894128026664S217.16766467065872,601.6784628957945,219.98802395209583,601.6784628957945S225.62874251497004,601.6784628957945,228.44910179640718,601.6784628957945S236.67892419581227,574.1412987212967,236.91017964071858,573.3675129889227S242.55089820359285,545.0565630820508,245.37125748502996,545.0565630820508S253.601079884435,572.5937272565487,253.8323353293413,573.3675129889227S262.0621577287464,600.9046771634205,262.2934131736527,601.6784628957945S270.0120890532468,631.2314593374352,270.7544910179641,629.9894128026664S279.1078832855779,573.9079904003723,279.21556886227546,573.3675129889227S286.9342447418696,543.814516547282,287.67664670658684,545.0565630820508S296.0979867026086,602.0108721505713,296.1377245508982,601.6784628957945S304.3675469503033,404.27559928006536,304.5988023952096,403.50181354769137S312.82862479461465,544.2827773496768,313.05988023952096,545.0565630820508S321.41327250713476,459.5832359499855,321.52095808383234,460.12371336143514S329.92043376339024,629.5771684450134,329.9820359281437,629.9894128026664S335.622754491018,573.3675129889227,338.4431137724551,573.3675129889227S344.08383233532936,573.3675129889227,346.90419161676647,573.3675129889227S355.13401401617153,404.27559928006536,355.36526946107784,403.50181354769137S363.8106902791361,516.5360581780021,363.8263473053893,516.745613175179S372.247687301411,629.6570035478895,372.28742514970065,629.9894128026664S380.6408174173144,658.8408401209879,380.748502994012,658.3003627095383S386.38922155688624,545.0565630820508,389.20958083832335,545.0565630820508S394.8502994011976,545.0565630820508,397.6706586826347,545.0565630820508S406.0701343621926,601.2662185381415,406.1317365269461,601.6784628957945S414.3615589263512,659.0741484419123,414.59281437125753,658.3003627095383S423.04558909947286,545.2093663176495,423.0538922155689,545.0565630820508S431.4072844831827,346.33943632249805,431.5149700598803,346.87991373394766S437.15568862275455,629.9894128026664,439.97604790419166,629.9894128026664S445.6167664670659,629.9894128026664,448.437125748503,629.9894128026664S456.1558016280971,574.6095595236916,456.89820359281435,573.3675129889227S464.4333421764908,603.002894046664,465.35928143712573,601.6784628957945S473.81334355054815,545.1970538691115,473.82035928143716,545.0565630820508S481.5390351610313,204.08311766481933,482.28143712574854,205.32516419958824S490.70265620741026,573.0346056290978,490.7425149700599,573.3675129889227S499.1154673904722,545.5472557219865,499.2035928143713,545.0565630820508S506.92226869396524,345.6378671991787,507.6646706586826,346.87991373394766S516.0860106547044,573.0351037341459,516.125748502994,573.3675129889227S521.7664670658683,488.4346632683071,524.5868263473054,488.4346632683071S533.0081663433272,573.6999222436996,533.0479041916168,573.3675129889227S541.5030322263132,347.00931698172707,541.5089820359282,346.87991373394766S549.8367256350783,205.92372284745935,549.9700598802395,205.32516419958824S558.3965788178492,233.3258332413716,558.4311377245509,233.63611410646013S566.885235362681,431.6726279272638,566.8922155688623,431.8127634545633S575.2916912484202,572.9552686312697,575.3532934131737,573.3675129889227S580.9940119760479,545.0565630820508,583.814371257485,545.0565630820508S589.4550898203593,573.3675129889227,592.2754491017964,573.3675129889227S600.6288413694102,544.5160856706012,600.7365269461078,545.0565630820508S609.1916549808042,658.4297659573177,609.1976047904192,658.3003627095383S617.6486420717158,177.18219400037106,617.6586826347306,177.01421429271647S626.1114573629459,375.0380604052209,626.1197604790419,375.19086364081954S634.5604230239917,488.1955781483398,634.5808383233533,488.4346632683071S642.2995142029474,574.6095595236916,643.0419161676647,573.3675129889227S651.3953084352785,460.66419077288475,651.502994011976,460.12371336143514S659.2216698915702,489.676709803076,659.9640718562874,488.4346632683071S665.6047904191616,431.8127634545633,668.4251497005988,431.8127634545633S674.065868263473,431.8127634545633,676.8862275449102,431.8127634545633S685.307567540932,346.5475044791708,685.3473053892217,346.87991373394766S693.7801082448957,573.0865394107108,693.8083832335329,573.3675129889227S701.3340976390372,543.7287241635447,702.2694610778443,545.0565630820508S708.9597596024524,600.3151674433656,710.7305389221557,601.6784628957945S719.1637393471847,573.6465240777877,719.1916167664671,573.3675129889227S727.545009034081,234.17659151790977,727.6526946107786,233.63611410646013S736.0740346068002,488.1022540135302,736.1137724550898,488.4346632683071S744.4671647227037,374.65038622937,744.5748502994013,375.19086364081954S752.9743259789591,572.9552686312697,753.0359281437126,573.3675129889227S761.4765906886623,488.67374838827436,761.497005988024,488.4346632683071S767.1377245508983,375.19086364081954,769.9580838323354,375.19086364081954S775.5988023952095,375.19086364081954,778.4191616766467,375.19086364081954S786.8525244750526,346.60170830052556,786.8802395209582,346.87991373394766S795.3136023193639,573.0893075555006,795.3413173652694,573.3675129889227S803.0599932448637,517.9876597099479,803.8023952095809,516.745613175179S812.2018708891387,545.4688074397038,812.2634730538922,545.0565630820508S819.9821489334862,402.2597670129224,820.7245508982036,403.50181354769137S826.3652694610779,573.3675129889227,829.1856287425151,573.3675129889227S834.8263473053892,573.3675129889227,837.6467065868263,573.3675129889227S846.0800693852323,545.334768515473,846.1077844311378,545.0565630820508S853.8264603107317,402.2597670129224,854.5688622754491,403.50181354769137S862.8754328651294,572.7257237104872,863.0299401197606,573.3675129889227S871.4576444281744,545.3615410629357,871.4910179640718,545.0565630820508S879.9489892230822,262.0406163292597,879.9520958083833,261.947064013332S888.3515714879412,35.871709116010045,888.4131736526947,35.45946475835706S896.8538361976443,148.4641792658772,896.874251497006,148.70326438584448S905.2955914930278,233.30370485168325,905.3353293413174,233.63611410646013S910.9760479041915,290.2580139202037,913.7964071856287,290.25801392020395S921.1515468529717,235.01308315143984,922.2574850299402,233.63611410646013S930.6904191020445,261.66673656686186,930.7185628742515,261.947064013332S939.1399028702733,459.79130410665823,939.179640718563,460.12371336143514S947.5330329861767,404.042290959141,947.6407185628743,403.50181354769137S955.994110830488,374.65038622936993,956.1017964071856,375.19086364081954S964.3316188065908,489.208449000681,964.5628742514971,488.4346632683071S972.2815501310909,317.32691729230675,973.0239520958083,318.5689638270758S981.2537744952135,517.519398907553,981.4850299401198,516.745613175179S987.125748502994,261.947064013332,989.9461077844312,261.947064013332S998.4012358191276,516.6162099273995,998.4071856287426,516.745613175179S1006.1258615083367,628.7473662678974,1006.868263473054,629.9894128026664S1014.5869393526478,543.8145165472819,1015.3293413173652,545.0565630820508S1020.9700598802395,658.3003627095385,1023.7904191616767,658.3003627095383S1029.431137724551,545.0565630820508,1032.251497005988,545.0565630820508S1040.3054333061627,657.3091406375975,1040.7125748502995,658.3003627095383S1049.144223532952,630.2760043825732,1049.1736526946108,629.9894128026664S1057.5731283741688,318.98120818472876,1057.6347305389222,318.5689638270758S1066.055949620584,516.412705815354,1066.0958083832336,516.745613175179S1074.4687608036459,487.94397062837146,1074.556886227545,488.4346632683071S1082.275562107139,631.2314593374352,1083.0179640718563,629.9894128026664S1091.4707388000718,460.2765165970338,1091.4790419161677,460.12371336143514S1099.8324341837815,318.02848641562616,1099.940119760479,318.5689638270758S1108.339595440037,544.6443187243979,1108.4011976047905,545.0565630820508S1116.8563256394868,431.9421667023427,1116.8622754491018,431.8127634545633S1125.2534074604773,177.45282569199063,1125.3233532934132,177.01421429271647S1133.7392625340317,204.97111407899092,1133.7844311377246,205.32516419958824S1142.2160798203772,459.8371217815283,1142.245508982036,460.12371336143514S1150.2994452822106,432.8039855265041,1150.7065868263473,431.8127634545633S1159.1060625059054,403.0895691900384,1159.1676646706587,403.50181354769137S1166.8863405502527,543.814516547282,1167.62874251497,545.0565630820508S1175.8585649143752,432.5865491869373,1176.0898203592815,431.8127634545633S1184.4432126268953,488.9751406797567,1184.5508982035929,488.4346632683071S1192.780720602998,347.65369946632165,1193.0119760479042,346.87991373394766S1198.6526946107786,431.8127634545633,1201.4730538922156,431.8127634545633S1207.11377245509,431.8127634545633,1209.934131736527,431.8127634545633S1218.3554717325487,601.3460536410176,1218.3952095808384,601.6784628957945S1226.6250319802434,574.1412987212967,1226.8562874251497,573.3675129889227S1235.2096796927635,545.5970404935005,1235.317365269461,545.0565630820508S1243.5471876688662,487.6608775359331,1243.7784431137725,488.4346632683071S1252.1590346280232,601.2088648563085,1252.2395209580839,601.6784628957945S1260.65895222881,630.3295949057522,1260.7005988023952,629.9894128026664S1269.1577460247147,403.6070291189143,1269.1616766467066,403.50181354769137S1276.8803525263006,175.77216775794759,1277.622754491018,177.01421429271647S1286.0558428894255,431.53319792654725,1286.0838323353294,431.8127634545633S1293.1330723267893,461.5338920272182,1294.5449101796407,460.12371336143514S1302.9443858591987,403.91405790534435,1303.005988023952,403.50181354769137S1311.4273280199739,346.5475044791708,1311.4670658682635,346.87991373394766S1319.1857417478575,546.2986096168197,1319.9281437125749,545.0565630820508S1328.3840898725978,318.6891589152826,1328.3892215568862,318.5689638270758S1336.1078974364802,149.9453109206134,1336.8502994011976,148.70326438584448S1345.2989918313726,290.07152553120665,1345.311377245509,290.25801392020395S1353.7567980635672,403.2922585505146,1353.7724550898204,403.50181354769137S1362.0022774892254,515.971827442805,1362.2335329341317,516.745613175179S1370.5869252017458,460.66419077288475,1370.6946107784433,460.12371336143514S1379.048003046057,431.2722860431137,1379.1556886227545,431.8127634545633S1387.3855110221596,544.2827773496768,1387.6167664670659,545.0565630820508S1396.0381064630876,488.1022540135302,1396.0778443113772,488.4346632683071S1404.3076667107823,685.8375268840362,1404.5389221556886,686.6113126164101S1412.9949797184927,545.1405529358781,1413,545.0565630820508"
fill="none" stroke="#f2a2d0" stroke-width="2"/>
Can't you construct a path that is simpler and makes it clear what the
degeneracy is?

A complete test would check very small curves and very large curves with the
control point very close to the start point, then very close to the end point,
then all points very close together.

https://codereview.chromium.org/190943002/diff/1/Source/platform/graphics/Pat...
File Source/platform/graphics/PathTraversalState.cpp (right):

https://codereview.chromium.org/190943002/diff/1/Source/platform/graphics/Pat...
Source/platform/graphics/PathTraversalState.cpp:147: if ((length -
distanceLine(curve.start, curve.end)) > kPathSegmentLengthTolerance
The real problem is that tolerance is a fixed value that fails to account for
the scale of the values. You should compare fabs(((length -
distanceLine(...))/length) > kPathSegLengthTolerance. You might even be able to
adjust kPathSegLengthTolerance in that case to a higher value. 0.001 bounds your
error to 0.1%.

[pdr., 2014-03-07 17:59:12]

I think I agree with Stephen. Unfortunately this patch is now unreviewable due
to Stephen's reply :P

Do you mind uploading to a different issue?

[pdr., 2014-03-07 18:00:37]

On 2014/03/07 17:59:12, pdr wrote:
> I think I agree with Stephen. Unfortunately this patch is now unreviewable due
> to Stephen's reply :P
> 
> Do you mind uploading to a different issue?

No need; once I replied, Stephen's response is now collapsed so this patch is
reviewable again.

I agree with Stephen's response.

[f(malita), 2014-03-07 18:02:26]

https://codereview.chromium.org/190943002/diff/1/LayoutTests/svg/custom/infin...
File LayoutTests/svg/custom/infinite-path-traversal.svg (right):

https://codereview.chromium.org/190943002/diff/1/LayoutTests/svg/custom/infin...
LayoutTests/svg/custom/infinite-path-traversal.svg:3: <path class="path"
d="M0,545.0565630820508C1.410179640718563,545.0565630820508,5.640718562874252,545.0565630820508,8.461077844311378,545.0565630820508S14.10179640718563,545.0565630820508,16.922155688622755,545.0565630820508S24.640831568216868,348.1219602687166,25.38323353293413,346.87991373394766S33.80457352895588,516.4132039204021,33.84431137724551,516.745613175179S39.48502994011976,488.4346632683071,42.30538922155689,488.4346632683071S50.024065101150995,517.9876597099478,50.76646706586826,516.745613175179S59.2192417940836,460.2765165970338,59.227544910179645,460.12371336143514S67.64888490620139,204.99275494481137,67.68862275449102,205.32516419958824S76.12928529944081,601.4393777758272,76.1497005988024,601.6784628957945S84.54917627836032,403.91405790534435,84.61077844311377,403.50181354769137S93.04414124151963,488.156457834885,93.07185628742516,488.4346632683071S101.47133196698307,573.7797573465757,101.53293413173652,573.3675129889227S109.96325106733464,375.4837980718618,109.99401197604791,375.19086364081954S117.4540267497611,402.15228390698314,118.45508982035929,403.50181354769137S126.88794866020186,432.0934615467429,126.91616766467065,431.8127634545633S135.3156433442286,6.736270493832191,135.37724550898204,7.148514851485174S143.83385203749947,544.9443546851512,143.83832335329342,545.0565630820508S151.55699923288753,433.0548099893322,152.2994011976048,431.8127634545633S160.69887687716272,516.333368817526,160.76047904191617,516.745613175179S166.4011976047904,545.0565630820508,169.22155688622755,545.0565630820508S177.4513792856326,517.519398907553,177.68263473053892,516.745613175179S185.91245712994402,487.6608775359331,186.14371257485033,488.4346632683071S194.5843751198001,573.1284278689554,194.60479041916167,573.3675129889227S202.83461281856674,685.8375268840362,203.06586826347305,686.6113126164101S211.41926053108688,630.529890214116,211.52694610778445,629.9894128026664S217.16766467065872,601.6784628957945,219.98802395209583,601.6784628957945S225.62874251497004,601.6784628957945,228.44910179640718,601.6784628957945S236.67892419581227,574.1412987212967,236.91017964071858,573.3675129889227S242.55089820359285,545.0565630820508,245.37125748502996,545.0565630820508S253.601079884435,572.5937272565487,253.8323353293413,573.3675129889227S262.0621577287464,600.9046771634205,262.2934131736527,601.6784628957945S270.0120890532468,631.2314593374352,270.7544910179641,629.9894128026664S279.1078832855779,573.9079904003723,279.21556886227546,573.3675129889227S286.9342447418696,543.814516547282,287.67664670658684,545.0565630820508S296.0979867026086,602.0108721505713,296.1377245508982,601.6784628957945S304.3675469503033,404.27559928006536,304.5988023952096,403.50181354769137S312.82862479461465,544.2827773496768,313.05988023952096,545.0565630820508S321.41327250713476,459.5832359499855,321.52095808383234,460.12371336143514S329.92043376339024,629.5771684450134,329.9820359281437,629.9894128026664S335.622754491018,573.3675129889227,338.4431137724551,573.3675129889227S344.08383233532936,573.3675129889227,346.90419161676647,573.3675129889227S355.13401401617153,404.27559928006536,355.36526946107784,403.50181354769137S363.8106902791361,516.5360581780021,363.8263473053893,516.745613175179S372.247687301411,629.6570035478895,372.28742514970065,629.9894128026664S380.6408174173144,658.8408401209879,380.748502994012,658.3003627095383S386.38922155688624,545.0565630820508,389.20958083832335,545.0565630820508S394.8502994011976,545.0565630820508,397.6706586826347,545.0565630820508S406.0701343621926,601.2662185381415,406.1317365269461,601.6784628957945S414.3615589263512,659.0741484419123,414.59281437125753,658.3003627095383S423.04558909947286,545.2093663176495,423.0538922155689,545.0565630820508S431.4072844831827,346.33943632249805,431.5149700598803,346.87991373394766S437.15568862275455,629.9894128026664,439.97604790419166,629.9894128026664S445.6167664670659,629.9894128026664,448.437125748503,629.9894128026664S456.1558016280971,574.6095595236916,456.89820359281435,573.3675129889227S464.4333421764908,603.002894046664,465.35928143712573,601.6784628957945S473.81334355054815,545.1970538691115,473.82035928143716,545.0565630820508S481.5390351610313,204.08311766481933,482.28143712574854,205.32516419958824S490.70265620741026,573.0346056290978,490.7425149700599,573.3675129889227S499.1154673904722,545.5472557219865,499.2035928143713,545.0565630820508S506.92226869396524,345.6378671991787,507.6646706586826,346.87991373394766S516.0860106547044,573.0351037341459,516.125748502994,573.3675129889227S521.7664670658683,488.4346632683071,524.5868263473054,488.4346632683071S533.0081663433272,573.6999222436996,533.0479041916168,573.3675129889227S541.5030322263132,347.00931698172707,541.5089820359282,346.87991373394766S549.8367256350783,205.92372284745935,549.9700598802395,205.32516419958824S558.3965788178492,233.3258332413716,558.4311377245509,233.63611410646013S566.885235362681,431.6726279272638,566.8922155688623,431.8127634545633S575.2916912484202,572.9552686312697,575.3532934131737,573.3675129889227S580.9940119760479,545.0565630820508,583.814371257485,545.0565630820508S589.4550898203593,573.3675129889227,592.2754491017964,573.3675129889227S600.6288413694102,544.5160856706012,600.7365269461078,545.0565630820508S609.1916549808042,658.4297659573177,609.1976047904192,658.3003627095383S617.6486420717158,177.18219400037106,617.6586826347306,177.01421429271647S626.1114573629459,375.0380604052209,626.1197604790419,375.19086364081954S634.5604230239917,488.1955781483398,634.5808383233533,488.4346632683071S642.2995142029474,574.6095595236916,643.0419161676647,573.3675129889227S651.3953084352785,460.66419077288475,651.502994011976,460.12371336143514S659.2216698915702,489.676709803076,659.9640718562874,488.4346632683071S665.6047904191616,431.8127634545633,668.4251497005988,431.8127634545633S674.065868263473,431.8127634545633,676.8862275449102,431.8127634545633S685.307567540932,346.5475044791708,685.3473053892217,346.87991373394766S693.7801082448957,573.0865394107108,693.8083832335329,573.3675129889227S701.3340976390372,543.7287241635447,702.2694610778443,545.0565630820508S708.9597596024524,600.3151674433656,710.7305389221557,601.6784628957945S719.1637393471847,573.6465240777877,719.1916167664671,573.3675129889227S727.545009034081,234.17659151790977,727.6526946107786,233.63611410646013S736.0740346068002,488.1022540135302,736.1137724550898,488.4346632683071S744.4671647227037,374.65038622937,744.5748502994013,375.19086364081954S752.9743259789591,572.9552686312697,753.0359281437126,573.3675129889227S761.4765906886623,488.67374838827436,761.497005988024,488.4346632683071S767.1377245508983,375.19086364081954,769.9580838323354,375.19086364081954S775.5988023952095,375.19086364081954,778.4191616766467,375.19086364081954S786.8525244750526,346.60170830052556,786.8802395209582,346.87991373394766S795.3136023193639,573.0893075555006,795.3413173652694,573.3675129889227S803.0599932448637,517.9876597099479,803.8023952095809,516.745613175179S812.2018708891387,545.4688074397038,812.2634730538922,545.0565630820508S819.9821489334862,402.2597670129224,820.7245508982036,403.50181354769137S826.3652694610779,573.3675129889227,829.1856287425151,573.3675129889227S834.8263473053892,573.3675129889227,837.6467065868263,573.3675129889227S846.0800693852323,545.334768515473,846.1077844311378,545.0565630820508S853.8264603107317,402.2597670129224,854.5688622754491,403.50181354769137S862.8754328651294,572.7257237104872,863.0299401197606,573.3675129889227S871.4576444281744,545.3615410629357,871.4910179640718,545.0565630820508S879.9489892230822,262.0406163292597,879.9520958083833,261.947064013332S888.3515714879412,35.871709116010045,888.4131736526947,35.45946475835706S896.8538361976443,148.4641792658772,896.874251497006,148.70326438584448S905.2955914930278,233.30370485168325,905.3353293413174,233.63611410646013S910.9760479041915,290.2580139202037,913.7964071856287,290.25801392020395S921.1515468529717,235.01308315143984,922.2574850299402,233.63611410646013S930.6904191020445,261.66673656686186,930.7185628742515,261.947064013332S939.1399028702733,459.79130410665823,939.179640718563,460.12371336143514S947.5330329861767,404.042290959141,947.6407185628743,403.50181354769137S955.994110830488,374.65038622936993,956.1017964071856,375.19086364081954S964.3316188065908,489.208449000681,964.5628742514971,488.4346632683071S972.2815501310909,317.32691729230675,973.0239520958083,318.5689638270758S981.2537744952135,517.519398907553,981.4850299401198,516.745613175179S987.125748502994,261.947064013332,989.9461077844312,261.947064013332S998.4012358191276,516.6162099273995,998.4071856287426,516.745613175179S1006.1258615083367,628.7473662678974,1006.868263473054,629.9894128026664S1014.5869393526478,543.8145165472819,1015.3293413173652,545.0565630820508S1020.9700598802395,658.3003627095385,1023.7904191616767,658.3003627095383S1029.431137724551,545.0565630820508,1032.251497005988,545.0565630820508S1040.3054333061627,657.3091406375975,1040.7125748502995,658.3003627095383S1049.144223532952,630.2760043825732,1049.1736526946108,629.9894128026664S1057.5731283741688,318.98120818472876,1057.6347305389222,318.5689638270758S1066.055949620584,516.412705815354,1066.0958083832336,516.745613175179S1074.4687608036459,487.94397062837146,1074.556886227545,488.4346632683071S1082.275562107139,631.2314593374352,1083.0179640718563,629.9894128026664S1091.4707388000718,460.2765165970338,1091.4790419161677,460.12371336143514S1099.8324341837815,318.02848641562616,1099.940119760479,318.5689638270758S1108.339595440037,544.6443187243979,1108.4011976047905,545.0565630820508S1116.8563256394868,431.9421667023427,1116.8622754491018,431.8127634545633S1125.2534074604773,177.45282569199063,1125.3233532934132,177.01421429271647S1133.7392625340317,204.97111407899092,1133.7844311377246,205.32516419958824S1142.2160798203772,459.8371217815283,1142.245508982036,460.12371336143514S1150.2994452822106,432.8039855265041,1150.7065868263473,431.8127634545633S1159.1060625059054,403.0895691900384,1159.1676646706587,403.50181354769137S1166.8863405502527,543.814516547282,1167.62874251497,545.0565630820508S1175.8585649143752,432.5865491869373,1176.0898203592815,431.8127634545633S1184.4432126268953,488.9751406797567,1184.5508982035929,488.4346632683071S1192.780720602998,347.65369946632165,1193.0119760479042,346.87991373394766S1198.6526946107786,431.8127634545633,1201.4730538922156,431.8127634545633S1207.11377245509,431.8127634545633,1209.934131736527,431.8127634545633S1218.3554717325487,601.3460536410176,1218.3952095808384,601.6784628957945S1226.6250319802434,574.1412987212967,1226.8562874251497,573.3675129889227S1235.2096796927635,545.5970404935005,1235.317365269461,545.0565630820508S1243.5471876688662,487.6608775359331,1243.7784431137725,488.4346632683071S1252.1590346280232,601.2088648563085,1252.2395209580839,601.6784628957945S1260.65895222881,630.3295949057522,1260.7005988023952,629.9894128026664S1269.1577460247147,403.6070291189143,1269.1616766467066,403.50181354769137S1276.8803525263006,175.77216775794759,1277.622754491018,177.01421429271647S1286.0558428894255,431.53319792654725,1286.0838323353294,431.8127634545633S1293.1330723267893,461.5338920272182,1294.5449101796407,460.12371336143514S1302.9443858591987,403.91405790534435,1303.005988023952,403.50181354769137S1311.4273280199739,346.5475044791708,1311.4670658682635,346.87991373394766S1319.1857417478575,546.2986096168197,1319.9281437125749,545.0565630820508S1328.3840898725978,318.6891589152826,1328.3892215568862,318.5689638270758S1336.1078974364802,149.9453109206134,1336.8502994011976,148.70326438584448S1345.2989918313726,290.07152553120665,1345.311377245509,290.25801392020395S1353.7567980635672,403.2922585505146,1353.7724550898204,403.50181354769137S1362.0022774892254,515.971827442805,1362.2335329341317,516.745613175179S1370.5869252017458,460.66419077288475,1370.6946107784433,460.12371336143514S1379.048003046057,431.2722860431137,1379.1556886227545,431.8127634545633S1387.3855110221596,544.2827773496768,1387.6167664670659,545.0565630820508S1396.0381064630876,488.1022540135302,1396.0778443113772,488.4346632683071S1404.3076667107823,685.8375268840362,1404.5389221556886,686.6113126164101S1412.9949797184927,545.1405529358781,1413,545.0565630820508"
fill="none" stroke="#f2a2d0" stroke-width="2"/>
On 2014/03/07 16:25:31, Stephen Chenney wrote:
> Can't you construct a path that is simpler and makes it clear what the
> degeneracy is?
> 
> A complete test would check very small curves and very large curves with the
> control point very close to the start point, then very close to the end point,
> then all points very close together.

This is intended as a litmus test for the fix, and not as a getTotalLength()
unit test. I don't think we need full coverage if we can prove/convince
ourselves that the fix guarantees algorithmic progression (which I believe is
the case with the current approach).

But I can certainly try to reduce it, although the degeneracy happens pretty far
down the road.

https://codereview.chromium.org/190943002/diff/1/Source/platform/graphics/Pat...
File Source/platform/graphics/PathTraversalState.cpp (right):

https://codereview.chromium.org/190943002/diff/1/Source/platform/graphics/Pat...
Source/platform/graphics/PathTraversalState.cpp:147: if ((length -
distanceLine(curve.start, curve.end)) > kPathSegmentLengthTolerance
On 2014/03/07 16:25:31, Stephen Chenney wrote:
> The real problem is that tolerance is a fixed value that fails to account for
> the scale of the values. You should compare fabs(((length -
> distanceLine(...))/length) > kPathSegLengthTolerance. You might even be able
to
> adjust kPathSegLengthTolerance in that case to a higher value. 0.001 bounds
your
> error to 0.1%.

I disagree: the immediate problem is that the algorithm gets stuck trying to
split curves and not making any progress. We can detect and avoid this condition
easily.

Now maybe (**) the updated tolerance test you suggest guarantees a significant
split, but it's not obvious and I would much rather have a direct check for that
condition instead of relying on inference subject to numerical stability issues.

(**) Turns out it doesn't: the issue repro still gets stuck, even with a
tolerance increased to 1%.

It's probably still a good idea to update the tolerance test (although I think
we can assert length >= distanceLine and skip fabs), but not as a replacement
for the split test. What do you think?

[f(malita), 2014-03-07 19:14:08]

https://codereview.chromium.org/190943002/diff/1/Source/platform/graphics/Pat...
File Source/platform/graphics/PathTraversalState.cpp (right):

https://codereview.chromium.org/190943002/diff/1/Source/platform/graphics/Pat...
Source/platform/graphics/PathTraversalState.cpp:147: if ((length -
distanceLine(curve.start, curve.end)) > kPathSegmentLengthTolerance
On 2014/03/07 16:25:31, Stephen Chenney wrote:
> You should compare fabs(((length -
> distanceLine(...))/length) > kPathSegLengthTolerance.

Come to think of it, it's obvious this would not work as a fix: for very small
curve segments (length << 1) this is *increasing* the metric value and making us
try to split even further than before.

Case in point: splitting falls apart for [(786.879395,346.877930)
(786.879395,346.877930) (786.879395,346.877899) (786.879456,346.877899)]

because (346.877930f + 346.877899f) / 2 == 346.877930f.

We're hitting this numerical precision wall for an original metric value (length
- distanceLine(curve.start, curve.end)) of 0.000023. When switching to a metric
of fabs((length - distanceLine(curve.start, curve.end)) / length), we're going
to hit this at a much higher value: 0.254644 <- if anything, we've made things
(much) worse.

[Stephen Chennney, 2014-03-07 19:56:13]

On 2014/03/07 19:14:08, Florin Malita wrote:
>
https://codereview.chromium.org/190943002/diff/1/Source/platform/graphics/Pat...
> File Source/platform/graphics/PathTraversalState.cpp (right):
> 
>
https://codereview.chromium.org/190943002/diff/1/Source/platform/graphics/Pat...
> Source/platform/graphics/PathTraversalState.cpp:147: if ((length -
> distanceLine(curve.start, curve.end)) > kPathSegmentLengthTolerance
> On 2014/03/07 16:25:31, Stephen Chenney wrote:
> > You should compare fabs(((length -
> > distanceLine(...))/length) > kPathSegLengthTolerance.
> 
> Come to think of it, it's obvious this would not work as a fix: for very small
> curve segments (length << 1) this is *increasing* the metric value and making
us
> try to split even further than before.
> 
> Case in point: splitting falls apart for [(786.879395,346.877930)
> (786.879395,346.877930) (786.879395,346.877899) (786.879456,346.877899)]
> 
> because (346.877930f + 346.877899f) / 2 == 346.877930f.
> 
> We're hitting this numerical precision wall for an original metric value
(length
> - distanceLine(curve.start, curve.end)) of 0.000023. When switching to a
metric
> of fabs((length - distanceLine(curve.start, curve.end)) / length), we're going
> to hit this at a much higher value: 0.254644 <- if anything, we've made things
> (much) worse.

Wrong metric on my part. Should be something that captures the size of the
numbers: ((length - distanceLine(...))^2 / (sum_of_controls)^2) >
kPathSegLengthTolerance^2

That is, squared difference divided by squared average of the control points
(centroid distance form origin). Although you have to check for sum_of_controls
== 0, but in that case you have no curve anyway.

[f(malita), 2014-03-07 20:52:58]

On 2014/03/07 19:56:13, Stephen Chenney wrote:
> On 2014/03/07 19:14:08, Florin Malita wrote:
> >
>
https://codereview.chromium.org/190943002/diff/1/Source/platform/graphics/Pat...
> > File Source/platform/graphics/PathTraversalState.cpp (right):
> > 
> >
>
https://codereview.chromium.org/190943002/diff/1/Source/platform/graphics/Pat...
> > Source/platform/graphics/PathTraversalState.cpp:147: if ((length -
> > distanceLine(curve.start, curve.end)) > kPathSegmentLengthTolerance
> > On 2014/03/07 16:25:31, Stephen Chenney wrote:
> > > You should compare fabs(((length -
> > > distanceLine(...))/length) > kPathSegLengthTolerance.
> > 
> > Come to think of it, it's obvious this would not work as a fix: for very
small
> > curve segments (length << 1) this is *increasing* the metric value and
making
> us
> > try to split even further than before.
> > 
> > Case in point: splitting falls apart for [(786.879395,346.877930)
> > (786.879395,346.877930) (786.879395,346.877899) (786.879456,346.877899)]
> > 
> > because (346.877930f + 346.877899f) / 2 == 346.877930f.
> > 
> > We're hitting this numerical precision wall for an original metric value
> (length
> > - distanceLine(curve.start, curve.end)) of 0.000023. When switching to a
> metric
> > of fabs((length - distanceLine(curve.start, curve.end)) / length), we're
going
> > to hit this at a much higher value: 0.254644 <- if anything, we've made
things
> > (much) worse.
> 
> Wrong metric on my part. Should be something that captures the size of the
> numbers: ((length - distanceLine(...))^2 / (sum_of_controls)^2) >
> kPathSegLengthTolerance^2
> 
> That is, squared difference divided by squared average of the control points
> (centroid distance form origin). Although you have to check for
sum_of_controls
> == 0, but in that case you have no curve anyway.

Wouldn't the squared centroid distance totally destroy the approximation even
for reasonably-sized curves if positioned far away? Besides, how does the above
guarantee a significant split anyway? Can we prove that it is numerically stable
vs. split()?

A possible improvement would be to re-position each curve ('s center) onto
origin - it shouldn't affect the length but helps mitigate some of the precision
issues.

But I don't understand why we wouldn't want to address the actual issue here and
enforce a non-null loop predicate, instead of tweaking a metric that affects the
predicate in indirect/non-obvious ways. It seems we're constructing these
arbitrary tests trying to predict IEEE-754 precision issues, instead of
observing and reacting to them.

I think part of the confusion is that kPathSegmentLengthTolerance serves a dual
purpose: ensure a minimum precision for the length approximation *and* guard
against IEEE-754 precision issues. I'm fine with tweaking the metric for the
former (separate CL), but conflating the two looks intractable to me.

[Stephen Chennney, 2014-03-07 21:38:20]

On 2014/03/07 20:52:58, Florin Malita wrote:
> On 2014/03/07 19:56:13, Stephen Chenney wrote:
> > On 2014/03/07 19:14:08, Florin Malita wrote:
> > >
> >
>
https://codereview.chromium.org/190943002/diff/1/Source/platform/graphics/Pat...
> > > File Source/platform/graphics/PathTraversalState.cpp (right):
> > > 
> > >
> >
>
https://codereview.chromium.org/190943002/diff/1/Source/platform/graphics/Pat...
> > > Source/platform/graphics/PathTraversalState.cpp:147: if ((length -
> > > distanceLine(curve.start, curve.end)) > kPathSegmentLengthTolerance
> > > On 2014/03/07 16:25:31, Stephen Chenney wrote:
> > > > You should compare fabs(((length -
> > > > distanceLine(...))/length) > kPathSegLengthTolerance.
> > > 
> > > Come to think of it, it's obvious this would not work as a fix: for very
> small
> > > curve segments (length << 1) this is *increasing* the metric value and
> making
> > us
> > > try to split even further than before.
> > > 
> > > Case in point: splitting falls apart for [(786.879395,346.877930)
> > > (786.879395,346.877930) (786.879395,346.877899) (786.879456,346.877899)]
> > > 
> > > because (346.877930f + 346.877899f) / 2 == 346.877930f.
> > > 
> > > We're hitting this numerical precision wall for an original metric value
> > (length
> > > - distanceLine(curve.start, curve.end)) of 0.000023. When switching to a
> > metric
> > > of fabs((length - distanceLine(curve.start, curve.end)) / length), we're
> going
> > > to hit this at a much higher value: 0.254644 <- if anything, we've made
> things
> > > (much) worse.
> > 
> > Wrong metric on my part. Should be something that captures the size of the
> > numbers: ((length - distanceLine(...))^2 / (sum_of_controls)^2) >
> > kPathSegLengthTolerance^2
> > 
> > That is, squared difference divided by squared average of the control points
> > (centroid distance form origin). Although you have to check for
> sum_of_controls
> > == 0, but in that case you have no curve anyway.
> 
> Wouldn't the squared centroid distance totally destroy the approximation even
> for reasonably-sized curves if positioned far away? Besides, how does the
above
> guarantee a significant split anyway? Can we prove that it is numerically
stable
> vs. split()?

I'm reasonably sure it is numerically stable. Ratio tests for numerical
tolerance are the most reliable when dealing with multi-scale content.

> A possible improvement would be to re-position each curve ('s center) onto
> origin - it shouldn't affect the length but helps mitigate some of the
precision
> issues.
> 
> But I don't understand why we wouldn't want to address the actual issue here
and
> enforce a non-null loop predicate, instead of tweaking a metric that affects
the
> predicate in indirect/non-obvious ways. It seems we're constructing these
> arbitrary tests trying to predict IEEE-754 precision issues, instead of
> observing and reacting to them.

We shouldn't be making up resolution where it doesn't exist. At some fundamental
level we are respecting the developer's decision to design svg content at a
scale where they get only a couple of decimal places precision. If they design
content at that scale, I think it's perfectly reasonable to answer their length
questions at that scale and precision. Expecting more than 0.01 units of length
accuracy for something positioned at 1000 units from the origin is unreasonable
(using floats). If all your content is out there you should define it at the
origin and use higher level mechanisms to put it at 1000,1000 on the page.

There's no way we actually render things at 1000,1000 with any more than 1 unit
of accuracy.
 
> I think part of the confusion is that kPathSegmentLengthTolerance serves a
dual
> purpose: ensure a minimum precision for the length approximation *and* guard
> against IEEE-754 precision issues. I'm fine with tweaking the metric for the
> former (separate CL), but conflating the two looks intractable to me.

Yes, the precision is serving a dual purpose, but if we actually respect that
precision then the degenerate case would always be within tolerance, so wouldn't
really be a special case at all. I do want to change the precision computation
regardless. Even if it doesn't fix the degeneracy, I would be OK with the
special test for a valid split.

[f(malita), 2014-03-08 05:10:43]

On 2014/03/07 21:38:20, Stephen Chenney wrote:
> I'm reasonably sure it is numerically stable. Ratio tests for numerical
> tolerance are the most reliable when dealing with multi-scale content.

I meant that the split() code has very little in common with the heuristic, and
is bound to hit different rounding errors, etc. Unless you bake assumptions
about all split() floating point operations into the heuristic, I fail to see
how it can be used to guard against precision issues arising within the actual
method. Of course we could aggressively pad up the tolerance, but that would
then hurt the result accuracy.


> > I think part of the confusion is that kPathSegmentLengthTolerance serves a
> dual
> > purpose: ensure a minimum precision for the length approximation *and* guard
> > against IEEE-754 precision issues. I'm fine with tweaking the metric for the
> > former (separate CL), but conflating the two looks intractable to me.
> 
> Yes, the precision is serving a dual purpose, but if we actually respect that
> precision then the degenerate case would always be within tolerance, so
wouldn't
> really be a special case at all.

But the degenerate case for split() is dependent on the actual operations
performed in that method (a quick glance => two cascading midpoint computations
=> I'm guessing we want the distances to be at least 4 * epsilon, lest things
start getting weird?). Estimating the needed precision beforehand seems quite
tricky and error prone.


> I do want to change the precision computation
> regardless.

1) Do you see a problem with the current heuristic for approximation accuracy
purposes? If I'm not mistaking, it does pretty much what we want: split the
curve until it turns into little line segments (the approximated length is
effectively equal to the linear distance between the endpoints: len ~= distance,
or (len - distance) < epsilon, where epsilon == kPathSegmentLengthTolerance).

2) I still think we should not try to overload the heuristic with numerical
precision semantics: those are dependent on the actual split() implementation,
and we can detect degenerate cases within the method instead of trying to
predict them. If you're OK with introducing the split test (catches degenerates
and fixes the infinite loop issue) then I would rather leave the heuristic
update for someone more masochistic :)

[Stephen Chennney, 2014-04-10 17:50:25]

Alternate fix at https://codereview.chromium.org/233063003

[Daniel Bratell, 2014-07-02 17:00:54]

On 2014/04/10 17:50:25, Stephen Chenney wrote:
> Alternate fix at https://codereview.chromium.org/233063003

It looks like it landed. Time to close this one or is there something that
remains here?

[f(malita), 2014-07-02 17:03:15]

On 2014/07/02 17:00:54, Daniel Bratell wrote:
> On 2014/04/10 17:50:25, Stephen Chenney wrote:
> > Alternate fix at https://codereview.chromium.org/233063003
> 
> It looks like it landed. Time to close this one or is there something that
> remains here?

Good to close.