From 1049f1246e7be4ccb68001361efceb8933e6f81c Mon Sep 17 00:00:00 2001 From: caryclark Date: Mon, 20 Apr 2015 08:31:59 -0700 Subject: 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 --- tools/pathops_sorter.htm | 483 ++++++++++++++++++++++------------------------- 1 file changed, 227 insertions(+), 256 deletions(-) (limited to 'tools/pathops_sorter.htm') 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 @@
-
-{{{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 -
- -
-{{{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 -
- -
-{{{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 -
- -
-{{{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 -
- -
-{{{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 -
- -
-{{{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 -
- -
-{{{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 -
- -
-{{{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 -
- -
-{{{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 -
- -
-{{{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 -
- -
-{{{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 -
- -
-{{{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 -
- -
-{{{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 -
- -
-{{{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 -
- -
-{{{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 -
- -
-{{{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 -
- -
-{{{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 -
- -
-{{{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 -
- -
-{{{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 -
-
-{{{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 -
- -
-{{{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 -
- -
-{{{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 -
- -
-{{{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 -
- -
-{{{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 -
- -
-{{{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 -
- -
-{{{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 -
- -
-{{{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 -
- -
-{{{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 -
- -
-{{{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 -
- -
-{{{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 -
- -
-{{{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 -
- -
-{{{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 -
- -
-{{{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 -
- -
-{{{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 -
- -
-{{{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 -
- -
+
+{{{3, 0}, {0, 1}, {1, 2}}}, +{{{1, 1}, {0, 2}, {3, 3}}},
@@ -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; -- cgit v1.2.3