Now, path ops natively intersect conics, quads, and cubics in any combination. There are still a class of cubic tests that fail and a handful of undiagnosed failures from skps and fuzz tests, but things are much better overall.

Extended tests (150M+) run to completion in release in about 6 minutes; the standard test suite exceeds 100K and finishes in a few seconds on desktops.

TBR=reed
BUG=skia:3588

Review URL: https://codereview.chromium.org/1037953004

1 files changed, 227 insertions, 256 deletions

diff --git a/tools/pathops_sorter.htm b/tools/pathops_sorter.htm
index 1ed3a2cfce..145b09cbe1 100644
--- a/tools/pathops_sorter.htm
+++ b/tools/pathops_sorter.htm
@@ -5,207 +5,10 @@
     <meta charset="utf-8" />
     <title></title>
 <div style="height:0">
-<div id="sect1">
-{{{1.80943513, 3.0778243500000002}, {1.66686702, 2.1680693600000001}, {1.68301272, 0}, {3, 0}}} id=1
-{{{0, 1}, {0, 2}, {0.75, 2.25}, {1.75, 2.25}}} id=2
-{{{1.75, 2.25}, {2.75, 2.25}, {4, 2}, {5, 2}}} id=4
-</div>
-
-<div id="sect2">
-{{{1.80943513, 3.0778243500000002}, {1.66686702, 2.1680693600000001}, {1.68301272, 0}, {3, 0}}} id=1
-{{{0, 1}, {0, 2}, {0.75, 2.25}, {1.75, 2.25}}} id=2
-{{{1.75, 2.25}, {2.2500000000000018, 2.25}, {2.8124999999999991, 2.1875}, {3.375, 2.125}}} id=4
-</div>
-
-<div id="sect3">
-{{{1.80943513, 3.0778243500000002}, {1.738151075, 2.6229468550000004}, {1.7065454725, 1.8534907675000001}, {1.85738429375, 1.19775405375}}} id=1
-{{{0, 1}, {0, 2}, {0.75, 2.25}, {1.75, 2.25}}} id=2
-{{{1.75, 2.25}, {2.2500000000000018, 2.25}, {2.8124999999999991, 2.1875}, {3.375, 2.125}}} id=4
-</div>
-
-<div id="sect4">
-{{{1.80943513, 3.0778243500000002}, {1.7737931025, 2.8503856025000003}, {1.7480706881249999, 2.5443022068750003}, {1.7501136332812499, 2.2131114089062502}}} id=1
-{{{0, 1}, {0, 2}, {0.75, 2.25}, {1.75, 2.25}}} id=2
-{{{1.75, 2.25}, {2.2500000000000018, 2.25}, {2.8124999999999991, 2.1875}, {3.375, 2.125}}} id=4
-</div>
-
-<div id="sect5">
-{{{1.80943513, 3.0778243500000002}, {1.7737931025, 2.8503856025000003}, {1.7480706881249999, 2.5443022068750003}, {1.7501136332812499, 2.2131114089062502}}} id=1
-{{{0.5, 2}, {0.81249999999999956, 2.1874999999999987}, {1.2500000000000009, 2.2500000000000013}, {1.75, 2.25}}} id=8
-{{{1.75, 2.25}, {2.2500000000000018, 2.25}, {2.8124999999999991, 2.1875}, {3.375, 2.125}}} id=4
-</div>
-
-<div id="sect6">
-{{{1.80943513, 3.0778243500000002}, {1.7737931025, 2.8503856025000003}, {1.7480706881249999, 2.5443022068750003}, {1.7501136332812499, 2.2131114089062502}}} id=1
-{{{0.5, 2}, {0.81249999999999956, 2.1874999999999987}, {1.2500000000000009, 2.2500000000000013}, {1.75, 2.25}}} id=8
-{{{1.75, 2.25}, {1.9999999999999976, 2.25}, {2.2656250000000022, 2.234375}, {2.5390625, 2.2109375}}} id=4
-</div>
-
-<div id="sect7">
-{{{1.80943513, 3.0778243500000002}, {1.7737931025, 2.8503856025000003}, {1.7480706881249999, 2.5443022068750003}, {1.7501136332812499, 2.2131114089062502}}} id=1
-{{{1.0546875, 2.1953125}, {1.2656250000000009, 2.2343750000000009}, {1.4999999999999996, 2.2499999999999996}, {1.75, 2.25}}} id=12
-{{{1.75, 2.25}, {1.9999999999999976, 2.25}, {2.2656250000000022, 2.234375}, {2.5390625, 2.2109375}}} id=4
-</div>
-
-<div id="sect8">
-{{{1.7656425168945311, 2.6843748983789064}, {1.7550120280078125, 2.5380253562890633}, {1.7490921607031253, 2.3787068078906248}, {1.7501136332812499, 2.2131114089062502}}} id=7
-{{{1.0546875, 2.1953125}, {1.2656250000000009, 2.2343750000000009}, {1.4999999999999996, 2.2499999999999996}, {1.75, 2.25}}} id=12
-{{{1.75, 2.25}, {1.9999999999999976, 2.25}, {2.2656250000000022, 2.234375}, {2.5390625, 2.2109375}}} id=4
-</div>
-
-<div id="sect9">
-{{{1.7656425168945311, 2.6843748983789064}, {1.7550120280078125, 2.5380253562890633}, {1.7490921607031253, 2.3787068078906248}, {1.7501136332812499, 2.2131114089062502}}} id=7
-{{{1.0546875, 2.1953125}, {1.2656250000000009, 2.2343750000000009}, {1.4999999999999996, 2.2499999999999996}, {1.75, 2.25}}} id=12
-{{{1.75, 2.25}, {1.8750000000000016, 2.2499999999999991}, {2.0039062499999982, 2.2460937500000004}, {2.1357421875, 2.2392578125}}} id=4
-</div>
-
-<div id="sect10">
-{{{1.7656425168945311, 2.6843748983789064}, {1.7550120280078125, 2.5380253562890633}, {1.7490921607031253, 2.3787068078906248}, {1.7501136332812499, 2.2131114089062502}}} id=7
-{{{1.3876953125, 2.2373046875}, {1.50390625, 2.24609375}, {1.625, 2.25}, {1.75, 2.25}}} id=16
-{{{1.75, 2.25}, {1.8750000000000016, 2.2499999999999991}, {2.0039062499999982, 2.2460937500000004}, {2.1357421875, 2.2392578125}}} id=4
-</div>
-
-<div id="sect11">
-{{{1.7535085895385742, 2.4559603499780276}, {1.7508274956738286, 2.3771375952441409}, {1.7496028969921869, 2.2959091083984369}, {1.7501136332812499, 2.2131114089062502}}} id=9
-{{{1.3876953125, 2.2373046875}, {1.50390625, 2.24609375}, {1.625, 2.25}, {1.75, 2.25}}} id=16
-{{{1.75, 2.25}, {1.8750000000000016, 2.2499999999999991}, {2.0039062499999982, 2.2460937500000004}, {2.1357421875, 2.2392578125}}} id=4
-</div>
-
-<div id="sect12">
-{{{1.7535085895385742, 2.4559603499780276}, {1.7508274956738286, 2.3771375952441409}, {1.7496028969921869, 2.2959091083984369}, {1.7501136332812499, 2.2131114089062502}}} id=9
-{{{1.3876953125, 2.2373046875}, {1.50390625, 2.24609375}, {1.625, 2.25}, {1.75, 2.25}}} id=16
-{{{1.75, 2.25}, {1.8124999999999989, 2.2499999999999996}, {1.8759765625000011, 2.2490234374999996}, {1.9403076171875, 2.2471923828125}}} id=4
-</div>
-
-<div id="sect13">
-{{{1.7535085895385742, 2.4559603499780276}, {1.7508274956738286, 2.3771375952441409}, {1.7496028969921869, 2.2959091083984369}, {1.7501136332812499, 2.2131114089062502}}} id=9
-{{{1.5655517578125, 2.2469482421875}, {1.6259765625, 2.2490234375}, {1.6875, 2.25}, {1.75, 2.25}}} id=20
-{{{1.75, 2.25}, {1.8124999999999989, 2.2499999999999996}, {1.8759765625000011, 2.2490234374999996}, {1.9403076171875, 2.2471923828125}}} id=4
-</div>
-
-<div id="sect14">
-{{{1.7506141751022339, 2.3360264837265015}, {1.7500367307348632, 2.2955168052368169}, {1.7498582651367187, 2.2545102586523438}, {1.7501136332812499, 2.2131114089062502}}} id=11
-{{{1.5655517578125, 2.2469482421875}, {1.6259765625, 2.2490234375}, {1.6875, 2.25}, {1.75, 2.25}}} id=20
-{{{1.75, 2.25}, {1.8124999999999989, 2.2499999999999996}, {1.8759765625000011, 2.2490234374999996}, {1.9403076171875, 2.2471923828125}}} id=4
-</div>
-
-<div id="sect15">
-{{{1.7506141751022339, 2.3360264837265015}, {1.7500367307348632, 2.2955168052368169}, {1.7498582651367187, 2.2545102586523438}, {1.7501136332812499, 2.2131114089062502}}} id=11
-{{{1.5655517578125, 2.2469482421875}, {1.6259765625, 2.2490234375}, {1.6875, 2.25}, {1.75, 2.25}}} id=20
-{{{1.75, 2.25}, {1.7812500000000011, 2.2500000000000004}, {1.8127441406249989, 2.2497558593749991}, {1.8444671630859375, 2.2492828369140625}}} id=4
-</div>
-
-<div id="sect16">
-{{{1.7506141751022339, 2.3360264837265015}, {1.7500367307348632, 2.2955168052368169}, {1.7498582651367187, 2.2545102586523438}, {1.7501136332812499, 2.2131114089062502}}} id=11
-{{{1.6569976806640625, 2.2492523193359375}, {1.687744140625, 2.249755859375}, {1.71875, 2.25}, {1.75, 2.25}}} id=24
-{{{1.75, 2.25}, {1.7812500000000011, 2.2500000000000004}, {1.8127441406249989, 2.2497558593749991}, {1.8444671630859375, 2.2492828369140625}}} id=4
-</div>
-
-<div id="sect17">
-{{{1.7500515994997787, 2.274902385537529}, {1.7499667235723877, 2.2544121828619379}, {1.7499859492089846, 2.2338108337792986}, {1.7501136332812499, 2.2131114089062502}}} id=13
-{{{1.6569976806640625, 2.2492523193359375}, {1.687744140625, 2.249755859375}, {1.71875, 2.25}, {1.75, 2.25}}} id=24
-{{{1.75, 2.25}, {1.7812500000000011, 2.2500000000000004}, {1.8127441406249989, 2.2497558593749991}, {1.8444671630859375, 2.2492828369140625}}} id=4
-</div>
-
-<div id="sect18">
-{{{1.7500515994997787, 2.274902385537529}, {1.7499667235723877, 2.2544121828619379}, {1.7499859492089846, 2.2338108337792986}, {1.7501136332812499, 2.2131114089062502}}} id=13
-{{{1.6569976806640625, 2.2492523193359375}, {1.687744140625, 2.249755859375}, {1.71875, 2.25}, {1.75, 2.25}}} id=24
-{{{1.75, 2.25}, {1.7656249999999989, 2.25}, {1.7813110351562511, 2.24993896484375}, {1.7970561981201172, 2.2498188018798828}}} id=4
-</div>
-
-<div id="sect19">
-{{{1.7500515994997787, 2.274902385537529}, {1.7499667235723877, 2.2544121828619379}, {1.7499859492089846, 2.2338108337792986}, {1.7501136332812499, 2.2131114089062502}}} id=13
-{{{1.7033100128173828, 2.2498149871826172}, {1.7188110351562504, 2.2499389648437504}, {1.7343749999999991, 2.2499999999999991}, {1.75, 2.25}}} id=28
-{{{1.75, 2.25}, {1.7656249999999989, 2.25}, {1.7813110351562511, 2.24993896484375}, {1.7970561981201172, 2.2498188018798828}}} id=4
-</div>
 
-<div id="sect20">
-{{{1.7500515994997787, 2.274902385537529}, {1.7500091615360831, 2.2646572841997337}, {1.7499927489633849, 2.2543843962601757}, {1.7500029063906433, 2.2440853555459359}}} id=13
-{{{1.7033100128173828, 2.2498149871826172}, {1.7188110351562504, 2.2499389648437504}, {1.7343749999999991, 2.2499999999999991}, {1.75, 2.25}}} id=28
-{{{1.75, 2.25}, {1.7656249999999989, 2.25}, {1.7813110351562511, 2.24993896484375}, {1.7970561981201172, 2.2498188018798828}}} id=4
-</div>
-
-<div id="sect21">
-{{{1.7500515994997787, 2.274902385537529}, {1.7500091615360831, 2.2646572841997337}, {1.7499927489633849, 2.2543843962601757}, {1.7500029063906433, 2.2440853555459359}}} id=13
-{{{1.7033100128173828, 2.2498149871826172}, {1.7188110351562504, 2.2499389648437504}, {1.7343749999999991, 2.2499999999999991}, {1.75, 2.25}}} id=28
-{{{1.75, 2.25}, {1.7578125000000004, 2.25}, {1.7656402587890616, 2.2499847412109375}, {1.7734830379486084, 2.2499544620513916}}} id=4
-</div>
-
-<div id="sect22">
-{{{1.7500515994997787, 2.274902385537529}, {1.7500091615360831, 2.2646572841997337}, {1.7499927489633849, 2.2543843962601757}, {1.7500029063906433, 2.2440853555459359}}} id=13
-{{{1.7266085147857666, 2.2499539852142334}, {1.7343902587890614, 2.2499847412109362}, {1.7421875000000011, 2.2500000000000013}, {1.75, 2.25}}} id=32
-{{{1.75, 2.25}, {1.7578125000000004, 2.25}, {1.7656402587890616, 2.2499847412109375}, {1.7734830379486084, 2.2499544620513916}}} id=4
-</div>
-
-<div id="sect23">
-{{{1.7500075296736033, 2.2595140978078994}, {1.749999391463374, 2.2543778580665053}, {1.7499978276770138, 2.2492348759030554}, {1.7500029063906433, 2.2440853555459359}}} id=17
-{{{1.7266085147857666, 2.2499539852142334}, {1.7343902587890614, 2.2499847412109362}, {1.7421875000000011, 2.2500000000000013}, {1.75, 2.25}}} id=32
-{{{1.75, 2.25}, {1.7578125000000004, 2.25}, {1.7656402587890616, 2.2499847412109375}, {1.7734830379486084, 2.2499544620513916}}} id=4
-</div>
-
-<div id="sect24">
-{{{1.7500075296736033, 2.2595140978078994}, {1.749999391463374, 2.2543778580665053}, {1.7499978276770138, 2.2492348759030554}, {1.7500029063906433, 2.2440853555459359}}} id=17
-{{{1.7266085147857666, 2.2499539852142334}, {1.7343902587890614, 2.2499847412109362}, {1.7421875000000011, 2.2500000000000013}, {1.75, 2.25}}} id=32
-{{{1.75, 2.25}, {1.7539062499999991, 2.25}, {1.7578163146972661, 2.2499961853027344}, {1.7617301642894745, 2.2499885857105255}}} id=4
-</div>
-
-<div id="sect25">
-{{{1.7500075296736033, 2.2595140978078994}, {1.749999391463374, 2.2543778580665053}, {1.7499978276770138, 2.2492348759030554}, {1.7500029063906433, 2.2440853555459359}}} id=17
-{{{1.7382927238941193, 2.2499885261058807}, {1.7421913146972665, 2.2499961853027353}, {1.7460937499999996, 2.2499999999999996}, {1.75, 2.25}}} id=36
-{{{1.75, 2.25}, {1.7539062499999991, 2.25}, {1.7578163146972661, 2.2499961853027344}, {1.7617301642894745, 2.2499885857105255}}} id=4
-</div>
-
-<div id="sect26">
-{{{1.7500002616856762, 2.2518047069078144}, {1.7499994883020116, 2.2492332413546396}, {1.7500003670338282, 2.2466601157244943}, {1.7500029063906433, 2.2440853555459359}}} id=19
-{{{1.75, 2.25}, {1.7539062499999991, 2.25}, {1.7578163146972661, 2.2499961853027344}, {1.7617301642894745, 2.2499885857105255}}} id=4
-</div>
-
-<div id="sect27">
-{{{1.7500002616856762, 2.2518047069078144}, {1.7499994883020116, 2.2492332413546396}, {1.7500003670338282, 2.2466601157244943}, {1.7500029063906433, 2.2440853555459359}}} id=19
-{{{1.75, 2.25}, {1.7519531250000011, 2.2499999999999991}, {1.7539072036743153, 2.249999046325684}, {1.7558622322976589, 2.2499971427023411}}} id=4
-</div>
-
-<div id="sect28">
-{{{1.7500002616856762, 2.2518047069078144}, {1.749999874993843, 2.2505189741312273}, {1.7499999013308822, 2.2492328263353962}, {1.7500003417604797, 2.2479462667113941}}} id=19
-{{{1.75, 2.25}, {1.7519531250000011, 2.2499999999999991}, {1.7539072036743153, 2.249999046325684}, {1.7558622322976589, 2.2499971427023411}}} id=4
-</div>
-
-<div id="sect29">
-{{{1.7500002616856762, 2.2518047069078144}, {1.749999874993843, 2.2505189741312273}, {1.7499999013308822, 2.2492328263353962}, {1.7500003417604797, 2.2479462667113941}}} id=19
-{{{1.75, 2.25}, {1.7509765624999989, 2.2499999999999996}, {1.7519533634185802, 2.2499997615814205}, {1.752930402290076, 2.249999285209924}}} id=4
-</div>
-
-<div id="sect30">
-{{{1.7500002616856762, 2.2518047069078144}, {1.7500000683397601, 2.2511618405195208}, {1.7499999782510609, 2.2505188703764163}, {1.7499999915525417, 2.2498757968773848}}} id=19
-{{{1.75, 2.25}, {1.7509765624999989, 2.2499999999999996}, {1.7519533634185802, 2.2499997615814205}, {1.752930402290076, 2.249999285209924}}} id=4
-</div>
-
-<div id="sect31">
-{{{1.7500002616856762, 2.2518047069078144}, {1.7500000683397601, 2.2511618405195208}, {1.7499999782510609, 2.2505188703764163}, {1.7499999915525417, 2.2498757968773848}}} id=19
-{{{1.75, 2.25}, {1.7504882812500011, 2.2500000000000004}, {1.7509766221046437, 2.2499999403953543}, {1.7514650225057267, 2.2499998212442733}}} id=4
-</div>
-
-<div id="sect32">
-{{{1.7500000491263352, 2.2508403295591259}, {1.7500000040986061, 2.2505188445374351}, {1.7499999849018013, 2.2501973336269003}, {1.7499999915525417, 2.2498757968773848}}} id=25
-{{{1.75, 2.25}, {1.7504882812500011, 2.2500000000000004}, {1.7509766221046437, 2.2499999403953543}, {1.7514650225057267, 2.2499998212442733}}} id=4
-</div>
-
-<div id="sect33">
-{{{1.7500000491263352, 2.2508403295591259}, {1.7500000040986061, 2.2505188445374351}, {1.7499999849018013, 2.2501973336269003}, {1.7499999915525417, 2.2498757968773848}}} id=25
-{{{1.75, 2.25}, {1.7502441406249989, 2.25}, {1.7504882961511623, 2.2499999850988388}, {1.7507324665712076, 2.2499999553037924}}} id=4
-</div>
-
-<div id="sect34">
-{{{1.7500000009600125, 2.2503580826161893}, {1.7499999913636877, 2.2501973271671556}, {1.7499999882271713, 2.2500365652521426}, {1.7499999915525417, 2.2498757968773848}}} id=27
-{{{1.75, 2.25}, {1.7502441406249989, 2.25}, {1.7504882961511623, 2.2499999850988388}, {1.7507324665712076, 2.2499999553037924}}} id=4
-</div>
-
-<div id="sect35">
-{{{1.7500000009600125, 2.2503580826161893}, {1.7499999913636877, 2.2501973271671556}, {1.7499999882271713, 2.2500365652521426}, {1.7499999915525417, 2.2498757968773848}}} id=27
-{{{1.75, 2.25}, {1.7501220703125004, 2.25}, {1.7502441443502894, 2.2499999962747097}, {1.7503662221124614, 2.2499999888250386}}} id=4
-</div>
-
-<div id="sect36">
+<div id="sect1">
+{{{3, 0}, {0, 1}, {1, 2}}},
+{{{1, 1}, {0, 2}, {3, 3}}},
 </div>
 
 </div>
@@ -214,44 +17,8 @@
 
 var testDivs = [
 sect1,
-sect2,
-sect3,
-sect4,
-sect5,
-sect6,
-sect7,
-sect8,
-sect9,
-sect10,
-sect11,
-sect12,
-sect13,
-sect14,
-sect15,
-sect16,
-sect17,
-sect18,
-sect19,
-sect20,
-sect21,
-sect22,
-sect23,
-sect24,
-sect25,
-sect26,
-sect27,
-sect28,
-sect29,
-sect30,
-sect31,
-sect32,
-sect33,
-sect34,
-sect35,
-sect36,
 
-
-    ];
+];
 
     var decimal_places = 3;
 
@@ -270,6 +37,7 @@ sect36,
     var screenWidth, screenHeight;
     var drawnPts;
     var curveT = 0;
+    var curveW = -1;
 
     var lastX, lastY;
     var activeCurve = [];
@@ -278,11 +46,12 @@ sect36,
 
     var focus_on_selection = 0;
     var draw_t = false;
+    var draw_w = false;
     var draw_closest_t = false;
     var draw_cubic_red = false;
     var draw_derivative = false;
     var draw_endpoints = 2;
-    var draw_id = false;
+    var draw_id = 0;
     var draw_midpoint = 0;
     var draw_mouse_xy = false;
     var draw_order = false;
@@ -348,7 +117,7 @@ sect36,
         ymax = -Infinity;
         for (var curves in test) {
             var curve = test[curves];
-            var last = curve.length;
+            var last = curve.length - (curve.length % 2 == 1 ? 1 : 0);
             for (var idx = 0; idx < last; idx += 2) {
                 xmin = Math.min(xmin, curve[idx]);
                 xmax = Math.max(xmax, curve[idx]);
@@ -405,6 +174,17 @@ function dxy_at_t(curve, t) {
         var c = t;
         dxy.x = a * curve[0] + b * curve[2] + c * curve[4];
         dxy.y = a * curve[1] + b * curve[3] + c * curve[5];
+    } else if (curve.length == 7) {
+        var p20x = curve[4] - curve[0];
+        var p20y = curve[5] - curve[1];
+        var p10xw = (curve[2] - curve[0]) * curve[6];
+        var p10yw = (curve[3] - curve[1]) * curve[6];
+        var coeff0x = curve[6] * p20x - p20x;
+        var coeff0y = curve[6] * p20y - p20y;
+        var coeff1x = p20x - 2 * p10xw;
+        var coeff1y = p20y - 2 * p10yw;
+        dxy.x = t * (t * coeff0x + coeff1x) + p10xw;
+        dxy.y = t * (t * coeff0y + coeff1y) + p10yw;
     } else if (curve.length == 8) {
         var one_t = 1 - t;
         var a = curve[0];
@@ -529,7 +309,7 @@ function dxy_at_t(curve, t) {
             roots.push(r);
             if (approximately_zero(R2 - Q3)) {
                 r = -A / 2 - adiv3;
-                if (!approximately_zero(s[0] - r)) {
+                if (!approximately_zero(roots[0] - r)) {
                     roots.push(r);
                 }
             }
@@ -591,7 +371,8 @@ function dxy_at_t(curve, t) {
         var adj = endPt[0] - startPt[0];
         var opp = endPt[1] - startPt[1];
         var r = [];
-        for (var n = 0; n < curve.length / 2; ++n) {
+        var len = (curve.length == 7 ? 6 : curve.length) / 2;
+        for (var n = 0; n < len; ++n) {
             r[n] = (curve[n * 2 + 1] - startPt[1]) * adj - (curve[n * 2] - startPt[0]) * opp;
         }
         if (curve.length == 6) {
@@ -602,6 +383,14 @@ function dxy_at_t(curve, t) {
             B -= C;  // B = -(b - c)
             return quad_roots(A, 2 * B, C);
         }
+        if (curve.length == 7) {
+            var A = r[2];
+            var B = r[1] * curve[6];
+            var C = r[0];
+            A += C - 2 * B;  // A = a - 2*b + c
+            B -= C;  // B = -(b - c)
+            return quad_roots(A, 2 * B, C);
+        }
         var A = r[3];       // d
         var B = r[2] * 3;   // 3*c
         var C = r[1] * 3;   // 3*b
@@ -622,6 +411,13 @@ function dxy_at_t(curve, t) {
         if (curve.length == 6) {
             return one_t2 * curve[0] + 2 * one_t * t * curve[2] + t2 * curve[4];
         }
+        if (curve.length == 7) {
+            var numer = one_t2 * curve[0] + 2 * one_t * t * curve[2] * curve[6]
+                    + t2 * curve[4];
+            var denom = one_t2            + 2 * one_t * t            * curve[6]
+                    + t2;
+            return numer / denom;
+        }
         var a = one_t2 * one_t;
         var b = 3 * one_t2 * t;
         var c = 3 * one_t * t2;
@@ -639,6 +435,13 @@ function dxy_at_t(curve, t) {
         if (curve.length == 6) {
             return one_t2 * curve[1] + 2 * one_t * t * curve[3] + t2 * curve[5];
         }
+        if (curve.length == 7) {
+            var numer = one_t2 * curve[1] + 2 * one_t * t * curve[3] * curve[6]
+                    + t2 * curve[5];
+            var denom = one_t2            + 2 * one_t * t            * curve[6]
+                    + t2;
+            return numer / denom;
+        }
         var a = one_t2 * one_t;
         var b = 3 * one_t2 * t;
         var c = 3 * one_t * t2;
@@ -728,6 +531,77 @@ function dxy_at_t(curve, t) {
         return closest / 16;
     }
 
+    var kMaxConicToQuadPOW2 = 5;
+
+    function computeQuadPOW2(curve, tol) {
+        var a = curve[6] - 1;
+        var k = a / (4 * (2 + a));
+        var x = k * (curve[0] - 2 * curve[2] + curve[4]);
+        var y = k * (curve[1] - 2 * curve[3] + curve[5]);
+
+        var error = Math.sqrt(x * x + y * y);
+        var pow2;
+        for (pow2 = 0; pow2 < kMaxConicToQuadPOW2; ++pow2) {
+            if (error <= tol) {
+                break;
+            }
+            error *= 0.25;
+        }
+        return pow2;
+    }
+
+    function subdivide_w_value(w) {
+        return Math.sqrt(0.5 + w * 0.5);
+    }
+
+    function chop(curve, part1, part2) {
+        var w = curve[6];
+        var scale = 1 / (1 + w);
+        part1[0] = curve[0];
+        part1[1] = curve[1];
+        part1[2] = (curve[0] + curve[2] * w) * scale;
+        part1[3] = (curve[1] + curve[3] * w) * scale;
+        part1[4] = part2[0] = (curve[0] + (curve[2] * w) * 2 + curve[4]) * scale * 0.5;
+        part1[5] = part2[1] = (curve[1] + (curve[3] * w) * 2 + curve[5]) * scale * 0.5;
+        part2[2] = (curve[2] * w + curve[4]) * scale;
+        part2[3] = (curve[3] * w + curve[5]) * scale;
+        part2[4] = curve[4];
+        part2[5] = curve[5];
+        part1[6] = part2[6] = subdivide_w_value(w);
+    }
+
+    function subdivide(curve, level, pts) {
+        if (0 == level) {
+            pts.push(curve[2]);
+            pts.push(curve[3]);
+            pts.push(curve[4]);
+            pts.push(curve[5]);
+        } else {
+            var part1 = [], part2 = [];
+            chop(curve, part1, part2);
+            --level;
+            subdivide(part1, level, pts);
+            subdivide(part2, level, pts);
+        }
+    }
+
+    function chopIntoQuadsPOW2(curve, pow2, pts) {
+        subdivide(curve, pow2, pts);
+        return 1 << pow2;
+    }
+
+    function drawConic(curve, srcLeft, srcTop, scale) {
+        var tol = 1 / scale;
+        var pow2 = computeQuadPOW2(curve, tol);
+        var pts = [];
+        chopIntoQuadsPOW2(curve, pow2, pts);
+        for (var i = 0; i < pts.length; i += 4) {
+            ctx.quadraticCurveTo(
+                (pts[i + 0] - srcLeft) * scale, (pts[i + 1] - srcTop) * scale,
+                (pts[i + 2] - srcLeft) * scale, (pts[i + 3] - srcTop) * scale);
+        }
+    }
+
     function draw(test, title) {
         ctx.font = "normal 50px Arial";
         ctx.textAlign = "left";
@@ -756,7 +630,7 @@ function dxy_at_t(curve, t) {
             if (curve.length == 4) {
                 endPt.push(curve[2]);
                 endPt.push(curve[3]);
-            } else if (curve.length == 6) {
+            } else if (curve.length == 6 || curve.length == 7) {
                 endPt.push(curve[4]);
                 endPt.push(curve[5]);
             } else if (curve.length == 8) {
@@ -788,7 +662,7 @@ function dxy_at_t(curve, t) {
         var maxWidth = Math.max(xmax - xmin, ymax - ymin);
         for (var curves in test) {
             var curve = test[curves];
-            if (curve.length == 6 || curve.length == 8) {
+            if (curve.length >= 6 && curve.length <= 8) {
                 var opp = curves == 0 || curves == 1 ? 0 : 1;
                 var sects = ray_curve_intersect(origin, hullEnds[opp], curve);
                 intersect.push(sects);
@@ -805,7 +679,7 @@ function dxy_at_t(curve, t) {
                         var iDist = Math.sqrt(ix * ix + iy * iy);
                         var eDist = Math.sqrt(ex * ex + ey * ey);
                         var delta = Math.abs(iDist - eDist) / maxWidth;
-                        if (delta > (curve.length == 6 ? 1e-5 : 1e-4)) {
+                        if (delta > (curve.length != 8 ? 1e-5 : 1e-4)) {
                             useIntersect ^= true;
                         }
                     }
@@ -847,8 +721,8 @@ function dxy_at_t(curve, t) {
   //      console.log("midLeft=" + midLeft + " startCross=" + startCross);
         var intersectIndex = 0;
         for (var curves in test) {
-            var curve = test[curves];
-            if (curve.length != 4 && curve.length != 6 && curve.length != 8) {
+            var curve = test[draw_id != 2 ? curves : test.length - curves - 1];
+            if (curve.length != 4 && curve.length != 6 && curve.length != 7 && curve.length != 8) {
                 continue;
             }
             ctx.lineWidth = 1;
@@ -861,10 +735,12 @@ function dxy_at_t(curve, t) {
                 drawLine(curve[0], curve[1], curve[2], curve[3]);
                 if (draw_tangents != 2) {
                     if (curve.length > 4) drawLine(curve[2], curve[3], curve[4], curve[5]);
-                    if (curve.length > 6) drawLine(curve[4], curve[5], curve[6], curve[7]);
+                    if (curve.length == 8) drawLine(curve[4], curve[5], curve[6], curve[7]);
                 }
                 if (draw_tangents != 1) {
-                    if (curve.length == 6) drawLine(curve[0], curve[1], curve[4], curve[5]);
+                    if (curve.length == 6 || curve.length == 7) {
+                        drawLine(curve[0], curve[1], curve[4], curve[5]);
+                    }
                     if (curve.length == 8) drawLine(curve[0], curve[1], curve[6], curve[7]);
                 }
             }
@@ -876,6 +752,8 @@ function dxy_at_t(curve, t) {
                 ctx.quadraticCurveTo(
                     (curve[2] - srcLeft) * scale, (curve[3] - srcTop) * scale,
                     (curve[4] - srcLeft) * scale, (curve[5] - srcTop) * scale);
+            } else if (curve.length == 7) {
+                drawConic(curve, srcLeft, srcTop, scale);
             } else {
                 ctx.bezierCurveTo(
                     (curve[2] - srcLeft) * scale, (curve[3] - srcTop) * scale,
@@ -893,7 +771,8 @@ function dxy_at_t(curve, t) {
                 if (draw_endpoints > 1 || curve.length == 4) {
                     drawPoint(curve[2], curve[3]);
                 }
-                if (curve.length == 6 || (draw_endpoints > 1 && curve.length == 8)) {
+                if (curve.length == 6 || curve.length == 7 ||
+                        (draw_endpoints > 1 && curve.length == 8)) {
                     drawPoint(curve[4], curve[5]);
                 }
                 if (curve.length == 8) drawPoint(curve[6], curve[7]);
@@ -944,7 +823,7 @@ function dxy_at_t(curve, t) {
             }
             if (draw_ray_intersect != 0) {
                 ctx.strokeStyle = "rgba(75,45,199, 0.6)";
-                if (curve.length == 6 || curve.length == 8) {
+                if (curve.length >= 6 && curve.length <= 8) {
                     var intersections = intersect[intersectIndex];
                     for (var i in intersections) {
                         var intersection = intersections[i];
@@ -998,7 +877,7 @@ function dxy_at_t(curve, t) {
             if (draw_t) {
                 drawPointAtT(curve);
             }
-            if (draw_id) {
+            if (draw_id != 0) {
                 var id = -1;
                 for (var i = 0; i < ids.length; i += 2) {
                     if (ids[i + 1] == curve) {
@@ -1028,6 +907,9 @@ function dxy_at_t(curve, t) {
         if (draw_t) {
             drawCurveTControl();
         }
+        if (draw_w) {
+            drawCurveWControl();
+        }
     }
 
     function drawCurveTControl() {
@@ -1050,6 +932,42 @@ function dxy_at_t(curve, t) {
         ctx.fillText(num, screenWidth - 78, ty);
     }
 
+    function drawCurveWControl() {
+        var w = -1;
+        var choice = 0;
+        for (var curves in tests[testIndex]) {
+            var curve = tests[testIndex][curves];
+            if (curve.length != 7) {
+                continue;
+            }
+            if (choice == curveW) {
+                w = curve[6];
+                break;
+            }
+            ++choice;
+        }
+        if (w < 0) {
+            return;
+        }
+        ctx.lineWidth = 2;
+        ctx.strokeStyle = "rgba(0,0,0, 0.3)";
+        ctx.beginPath();
+        ctx.rect(screenWidth - 40, 40, 28, screenHeight - 80);
+        ctx.stroke();
+        var ty = 40 + w * (screenHeight - 80);
+        ctx.beginPath();
+        ctx.moveTo(screenWidth - 40, ty);
+        ctx.lineTo(screenWidth - 45, ty - 5);
+        ctx.lineTo(screenWidth - 45, ty + 5);
+        ctx.lineTo(screenWidth - 40, ty);
+        ctx.fillStyle = "rgba(0,0,0, 0.6)";
+        ctx.fill();
+        var num = w.toFixed(decimal_places);
+        ctx.font = "normal 10px Arial";
+        ctx.textAlign = "left";
+        ctx.fillText(num, screenWidth - 38, ty);
+    }
+
     function ptInTControl() {
         var e = window.event;
         var tgt = e.target || e.srcElement;
@@ -1070,6 +988,38 @@ function dxy_at_t(curve, t) {
         return true;
     }
 
+    function ptInWControl() {
+        var e = window.event;
+        var tgt = e.target || e.srcElement;
+        var left = tgt.offsetLeft;
+        var top = tgt.offsetTop;
+        var x = (e.clientX - left);
+        var y = (e.clientY - top);
+        if (x < screenWidth - 40 || x > screenWidth - 10) {
+            return false;
+        }
+        if (y < 40 || y > screenHeight - 80) {
+            return false;
+        }
+        var w = (y - 40) / (screenHeight - 120);
+        if (w < 0 || w > 1) {
+            throw "stop execution";
+        }
+        var choice = 0;
+        for (var curves in tests[testIndex]) {
+            var curve = tests[testIndex][curves];
+            if (curve.length != 7) {
+                continue;
+            }
+            if (choice == curveW) {
+                curve[6] = w;
+                break;
+            }
+            ++choice;
+        }
+        return true;
+    }
+
     function drawTop() {
         init(tests[testIndex]);
         redraw();
@@ -1085,7 +1035,7 @@ function dxy_at_t(curve, t) {
                     continue;
                 }
                 var curve = tests[testIndex][curves];
-                var last = curve.length;
+                var last = curve.length - (curve.length % 2 == 1 ? 1 : 0);
                 for (var idx = 0; idx < last; idx += 2) {
                     focusXmin = Math.min(focusXmin, curve[idx]);
                     focusXmax = Math.max(focusXmax, curve[idx]);
@@ -1255,6 +1205,26 @@ function dxy_at_t(curve, t) {
                 draw_tangents = (draw_tangents + 1) % 4;
                 redraw();
                 break;
+            case 'w':
+                ++curveW;
+                var choice = 0;
+                draw_w = false;
+                for (var curves in tests[testIndex]) {
+                    var curve = tests[testIndex][curves];
+                    if (curve.length != 7) {
+                        continue;
+                    }
+                    if (choice == curveW) {
+                        draw_w = true;
+                        break;
+                    }
+                    ++choice;
+                }
+                if (!draw_w) {
+                    curveW = -1;
+                }
+                redraw();
+                break;
             case 'x':
                 draw_point_xy ^= true;
                 redraw();
@@ -1276,7 +1246,7 @@ function dxy_at_t(curve, t) {
                 redraw();
                 break;
             case '.':
-                draw_id ^= true;
+                draw_id = (draw_id + 1) % 3;
                 redraw();
                 break;
         }
@@ -1335,7 +1305,7 @@ function dxy_at_t(curve, t) {
     }
 
     function handleMouseClick() {
-        if (!draw_t || !ptInTControl()) {
+        if ((!draw_t || !ptInTControl()) && (!draw_w || !ptInWControl())) {
             calcXY();
         } else {
             redraw();
@@ -1348,10 +1318,11 @@ function dxy_at_t(curve, t) {
         activePt = -1;
         for (var curves in test) {
             var testCurve = test[curves];
-            if (testCurve.length != 4 && testCurve.length != 6 && testCurve.length != 8) {
+            if (testCurve.length != 4 && (testCurve.length < 6 || testCurve.length > 8)) {
                 continue;
             }
-            for (var i = 0; i < testCurve.length; i += 2) {
+            var testMax = testCurve.length == 7 ? 6 : testCurve.length;
+            for (var i = 0; i < testMax; i += 2) {
                 var testX = testCurve[i];
                 var testY = testCurve[i + 1];
                 var dx = testX - mouseX;