Gitiles
Code Review Sign In
gerrit-public.fairphone.software / platform / external / skia / c09df2c32e0a1375dbacec1ff40c1a74bcdebc01 / . / experimental / Intersection / hg.htm
blob: 32f49a74469550f082357b46bc506699fabe2c48 [file] [log] [blame]
caryclark@google.comc83c70e2013-02-22 21:50:07 +0000[diff] [blame]1<html>
2<head>
3<div style="height:0">
4
5<div id="cubic1">
6{{3.13,2.74}, {1.08,4.62}, {3.71,0.94}, {2.01,3.81}}
7{{6.71,3.14}, {7.99,2.75}, {8.27,1.96}, {6.35,3.57}}
8{{9.45,10.67}, {10.05,5.78}, {13.95,7.46}, {14.72,5.29}}
9{{3.34,8.98}, {1.95,10.27}, {3.76,7.65}, {4.96,10.64}}
10</div>
11
12</div>
13
14<script type="text/javascript">
15
16var testDivs = [
17 cubic1,
18];
19
20var scale, columns, rows, xStart, yStart;
21
22var ticks = 10;
23var at_x = 13 + 0.5;
24var at_y = 23 + 0.5;
25var decimal_places = 3;
26var tests = [];
27var testTitles = [];
28var testIndex = 0;
29var ctx;
30var minScale = 1;
31var subscale = 1;
32var curveT = -1;
33var xmin, xmax, ymin, ymax;
34
35var mouseX, mouseY;
36var mouseDown = false;
37
38var draw_deriviatives = false;
39var draw_endpoints = true;
40var draw_hodo = false;
41var draw_hodo2 = false;
42var draw_hodo_origin = true;
43var draw_midpoint = false;
44var draw_tangents = true;
45var draw_sequence = true;
46
47function parse(test, title) {
48 var curveStrs = test.split("{{");
49 if (curveStrs.length == 1)
50 curveStrs = test.split("=(");
51 var pattern = /[a-z$=]?-?\d+\.*\d*e?-?\d*/g;
52 var curves = [];
53 for (var c in curveStrs) {
54 var curveStr = curveStrs[c];
55 var points = curveStr.match(pattern);
56 var pts = [];
57 for (var wd in points) {
58 var num = parseFloat(points[wd]);
59 if (isNaN(num)) continue;
60 pts.push(num);
61 }
62 if (pts.length > 2)
63 curves.push(pts);
64 }
65 if (curves.length >= 1) {
66 tests.push(curves);
67 testTitles.push(title);
68 }
69}
70
71function init(test) {
72 var canvas = document.getElementById('canvas');
73 if (!canvas.getContext) return;
74 canvas.width = window.innerWidth - 20;
75 canvas.height = window.innerHeight - 20;
76 ctx = canvas.getContext('2d');
77 xmin = Infinity;
78 xmax = -Infinity;
79 ymin = Infinity;
80 ymax = -Infinity;
81 for (var curves in test) {
82 var curve = test[curves];
83 var last = curve.length;
84 for (var idx = 0; idx < last; idx += 2) {
85 xmin = Math.min(xmin, curve[idx]);
86 xmax = Math.max(xmax, curve[idx]);
87 ymin = Math.min(ymin, curve[idx + 1]);
88 ymax = Math.max(ymax, curve[idx + 1]);
89 }
90 }
91 xmin -= 1;
92 var testW = xmax - xmin;
93 var testH = ymax - ymin;
94 subscale = 1;
95 while (testW * subscale < 0.1 && testH * subscale < 0.1) {
96 subscale *= 10;
97 }
98 while (testW * subscale > 10 && testH * subscale > 10) {
99 subscale /= 10;
100 }
101 calcFromScale();
102}
103
104function hodograph(cubic) {
105 var hodo = [];
106 hodo[0] = 3 * (cubic[2] - cubic[0]);
107 hodo[1] = 3 * (cubic[3] - cubic[1]);
108 hodo[2] = 3 * (cubic[4] - cubic[2]);
109 hodo[3] = 3 * (cubic[5] - cubic[3]);
110 hodo[4] = 3 * (cubic[6] - cubic[4]);
111 hodo[5] = 3 * (cubic[7] - cubic[5]);
112 return hodo;
113}
114
115function hodograph2(cubic) {
116 var quad = hodograph(cubic);
117 var hodo = [];
118 hodo[0] = 2 * (quad[2] - quad[0]);
119 hodo[1] = 2 * (quad[3] - quad[1]);
120 hodo[2] = 2 * (quad[4] - quad[2]);
121 hodo[3] = 2 * (quad[5] - quad[3]);
122 return hodo;
123}
124
125function quadraticRootsReal(A, B, C, s) {
126 if (A == 0) {
127 if (B == 0) {
128 s[0] = 0;
129 return C == 0;
130 }
131 s[0] = -C / B;
132 return 1;
133 }
134 /* normal form: x^2 + px + q = 0 */
135 var p = B / (2 * A);
136 var q = C / A;
137 var p2 = p * p;
138 if (p2 < q) {
139 return 0;
140 }
141 var sqrt_D = 0;
142 if (p2 > q) {
143 sqrt_D = sqrt(p2 - q);
144 }
145 s[0] = sqrt_D - p;
146 s[1] = -sqrt_D - p;
147 return 1 + s[0] != s[1];
148}
149
150function add_valid_ts(s, realRoots, t) {
151 var foundRoots = 0;
152 for (var index = 0; index < realRoots; ++index) {
153 var tValue = s[index];
154 if (tValue >= 0 && tValue <= 1) {
155 for (var idx2 = 0; idx2 < foundRoots; ++idx2) {
156 if (t[idx2] != tValue) {
157 t[foundRoots++] = tValue;
158 }
159 }
160 }
161 }
162 return foundRoots;
163}
164
165function quadraticRootsValidT(a, b, c, t) {
166 var s = [];
167 var realRoots = quadraticRootsReal(A, B, C, s);
168 var foundRoots = add_valid_ts(s, realRoots, t);
169 return foundRoots != 0;
170}
171
172function find_cubic_inflections(cubic, tValues)
173{
174 var Ax = src[2] - src[0];
175 var Ay = src[3] - src[1];
176 var Bx = src[4] - 2 * src[2] + src[0];
177 var By = src[5] - 2 * src[3] + src[1];
178 var Cx = src[6] + 3 * (src[2] - src[4]) - src[0];
179 var Cy = src[7] + 3 * (src[3] - src[5]) - src[1];
180 return quadraticRootsValidT(Bx * Cy - By * Cx, (Ax * Cy - Ay * Cx),
181 Ax * By - Ay * Bx, tValues);
182}
183
184function dx_at_t(cubic, t) {
185 var one_t = 1 - t;
186 var a = cubic[0];
187 var b = cubic[2];
188 var c = cubic[4];
189 var d = cubic[6];
190 return 3 * ((b - a) * one_t * one_t + 2 * (c - b) * t * one_t + (d - c) * t * t);
191}
192
193function dy_at_t(cubic, t) {
194 var one_t = 1 - t;
195 var a = cubic[1];
196 var b = cubic[3];
197 var c = cubic[5];
198 var d = cubic[7];
199 return 3 * ((b - a) * one_t * one_t + 2 * (c - b) * t * one_t + (d - c) * t * t);
200}
201
202function x_at_t(cubic, t) {
203 var one_t = 1 - t;
204 var one_t2 = one_t * one_t;
205 var a = one_t2 * one_t;
206 var b = 3 * one_t2 * t;
207 var t2 = t * t;
208 var c = 3 * one_t * t2;
209 var d = t2 * t;
210 return a * cubic[0] + b * cubic[2] + c * cubic[4] + d * cubic[6];
211}
212
213function y_at_t(cubic, t) {
214 var one_t = 1 - t;
215 var one_t2 = one_t * one_t;
216 var a = one_t2 * one_t;
217 var b = 3 * one_t2 * t;
218 var t2 = t * t;
219 var c = 3 * one_t * t2;
220 var d = t2 * t;
221 return a * cubic[1] + b * cubic[3] + c * cubic[5] + d * cubic[7];
222}
223
224function calcFromScale() {
225 xStart = Math.floor(xmin * subscale) / subscale;
226 yStart = Math.floor(ymin * subscale) / subscale;
227 var xEnd = Math.ceil(xmin * subscale) / subscale;
228 var yEnd = Math.ceil(ymin * subscale) / subscale;
229 var cCelsW = Math.floor(ctx.canvas.width / 10);
230 var cCelsH = Math.floor(ctx.canvas.height / 10);
231 var testW = xEnd - xStart;
232 var testH = yEnd - yStart;
233 var scaleWH = 1;
234 while (cCelsW > testW * scaleWH * 10 && cCelsH > testH * scaleWH * 10) {
235 scaleWH *= 10;
236 }
237 while (cCelsW * 10 < testW * scaleWH && cCelsH * 10 < testH * scaleWH) {
238 scaleWH /= 10;
239 }
240
241 columns = Math.ceil(xmax * subscale) - Math.floor(xmin * subscale) + 1;
242 rows = Math.ceil(ymax * subscale) - Math.floor(ymin * subscale) + 1;
243
244 var hscale = ctx.canvas.width / columns / ticks;
245 var vscale = ctx.canvas.height / rows / ticks;
246 minScale = Math.floor(Math.min(hscale, vscale));
247 scale = minScale * subscale;
248}
249
250function drawLine(x1, y1, x2, y2) {
251 var unit = scale * ticks;
252 var xoffset = xStart * -unit + at_x;
253 var yoffset = yStart * -unit + at_y;
254 ctx.beginPath();
255 ctx.moveTo(xoffset + x1 * unit, yoffset + y1 * unit);
256 ctx.lineTo(xoffset + x2 * unit, yoffset + y2 * unit);
257 ctx.stroke();
258}
259
260function drawPoint(px, py) {
261 var unit = scale * ticks;
262 var xoffset = xStart * -unit + at_x;
263 var yoffset = yStart * -unit + at_y;
264 var _px = px * unit + xoffset;
265 var _py = py * unit + yoffset;
266 ctx.beginPath();
267 ctx.arc(_px, _py, 3, 0, Math.PI*2, true);
268 ctx.closePath();
269 ctx.stroke();
270}
271
272function drawPointSolid(px, py) {
273 drawPoint(px, py);
274 ctx.fillStyle = "rgba(0,0,0, 0.4)";
275 ctx.fill();
276}
277
278function drawLabel(num, px, py) {
279 ctx.beginPath();
280 ctx.arc(px, py, 8, 0, Math.PI*2, true);
281 ctx.closePath();
282 ctx.strokeStyle = "rgba(0,0,0, 0.4)";
283 ctx.lineWidth = num == 0 || num == 3 ? 2 : 1;
284 ctx.stroke();
285 ctx.fillStyle = "black";
286 ctx.font = "normal 10px Arial";
287 // ctx.rotate(0.001);
288 ctx.fillText(num, px - 2, py + 3);
289 // ctx.rotate(-0.001);
290}
291
292function drawLabelX(ymin, num, loc) {
293 var unit = scale * ticks;
294 var xoffset = xStart * -unit + at_x;
295 var yoffset = yStart * -unit + at_y;
296 var px = loc * unit + xoffset;
297 var py = ymin * unit + yoffset - 20;
298 drawLabel(num, px, py);
299}
300
301function drawLabelY(xmin, num, loc) {
302 var unit = scale * ticks;
303 var xoffset = xStart * -unit + at_x;
304 var yoffset = yStart * -unit + at_y;
305 var px = xmin * unit + xoffset - 20;
306 var py = loc * unit + yoffset;
307 drawLabel(num, px, py);
308}
309
310function drawHodoOrigin(hx, hy, hMinX, hMinY, hMaxX, hMaxY) {
311 ctx.beginPath();
312 ctx.moveTo(hx, hy - 100);
313 ctx.lineTo(hx, hy);
314 ctx.strokeStyle = hMinY < 0 ? "green" : "blue";
315 ctx.stroke();
316 ctx.beginPath();
317 ctx.moveTo(hx, hy);
318 ctx.lineTo(hx, hy + 100);
319 ctx.strokeStyle = hMaxY > 0 ? "green" : "blue";
320 ctx.stroke();
321 ctx.beginPath();
322 ctx.moveTo(hx - 100, hy);
323 ctx.lineTo(hx, hy);
324 ctx.strokeStyle = hMinX < 0 ? "green" : "blue";
325 ctx.stroke();
326 ctx.beginPath();
327 ctx.moveTo(hx, hy);
328 ctx.lineTo(hx + 100, hy);
329 ctx.strokeStyle = hMaxX > 0 ? "green" : "blue";
330 ctx.stroke();
331}
332
333function logCurves(test) {
334 for (curves in test) {
335 var curve = test[curves];
336 if (curve.length != 8) {
337 continue;
338 }
339 var str = "{{";
340 for (i = 0; i < 8; i += 2) {
341 str += curve[i].toFixed(2) + "," + curve[i + 1].toFixed(2);
342 if (i < 6) {
343 str += "}, {";
344 }
345 }
346 str += "}}";
347 console.log(str);
348 }
349}
350
351function scalexy(x, y, mag) {
352 var length = Math.sqrt(x * x + y * y);
353 return mag / length;
354}
355
356function drawArrow(x, y, dx, dy) {
357 var unit = scale * ticks;
358 var xoffset = xStart * -unit + at_x;
359 var yoffset = yStart * -unit + at_y;
360 var dscale = scalexy(dx, dy, 1);
361 dx *= dscale;
362 dy *= dscale;
363 ctx.beginPath();
364 ctx.moveTo(xoffset + x * unit, yoffset + y * unit);
365 x += dx;
366 y += dy;
367 ctx.lineTo(xoffset + x * unit, yoffset + y * unit);
368 dx /= 10;
369 dy /= 10;
370 ctx.lineTo(xoffset + (x - dy) * unit, yoffset + (y + dx) * unit);
371 ctx.lineTo(xoffset + (x + dx * 2) * unit, yoffset + (y + dy * 2) * unit);
372 ctx.lineTo(xoffset + (x + dy) * unit, yoffset + (y - dx) * unit);
373 ctx.lineTo(xoffset + x * unit, yoffset + y * unit);
374 ctx.strokeStyle = "rgba(0,75,0, 0.4)";
375 ctx.stroke();
376}
377
378function draw(test, title) {
379 ctx.fillStyle = "rgba(0,0,0, 0.1)";
380 ctx.font = "normal 50px Arial";
381 ctx.fillText(title, 50, 50);
382 ctx.font = "normal 10px Arial";
383 var unit = scale * ticks;
384 // ctx.lineWidth = "1.001"; "0.999";
385 var xoffset = xStart * -unit + at_x;
386 var yoffset = yStart * -unit + at_y;
387
388 for (curves in test) {
389 var curve = test[curves];
390 if (curve.length != 8) {
391 continue;
392 }
393 ctx.lineWidth = 1;
394 if (draw_tangents) {
395 ctx.strokeStyle = "rgba(0,0,255, 0.3)";
396 drawLine(curve[0], curve[1], curve[2], curve[3]);
397 drawLine(curve[2], curve[3], curve[4], curve[5]);
398 drawLine(curve[4], curve[5], curve[6], curve[7]);
399 }
400 if (draw_deriviatives) {
401 var dx = dx_at_t(curve, 0);
402 var dy = dy_at_t(curve, 0);
403 drawArrow(curve[0], curve[1], dx, dy);
404 dx = dx_at_t(curve, 1);
405 dy = dy_at_t(curve, 1);
406 drawArrow(curve[6], curve[7], dx, dy);
407 if (draw_midpoint) {
408 var midX = x_at_t(curve, 0.5);
409 var midY = y_at_t(curve, 0.5);
410 dx = dx_at_t(curve, 0.5);
411 dy = dy_at_t(curve, 0.5);
412 drawArrow(midX, midY, dx, dy);
413 }
414 }
415 ctx.beginPath();
416 ctx.moveTo(xoffset + curve[0] * unit, yoffset + curve[1] * unit);
417 ctx.bezierCurveTo(
418 xoffset + curve[2] * unit, yoffset + curve[3] * unit,
419 xoffset + curve[4] * unit, yoffset + curve[5] * unit,
420 xoffset + curve[6] * unit, yoffset + curve[7] * unit);
421 ctx.strokeStyle = "black";
422 ctx.stroke();
423 if (draw_endpoints) {
424 drawPoint(curve[0], curve[1]);
425 drawPoint(curve[2], curve[3]);
426 drawPoint(curve[4], curve[5]);
427 drawPoint(curve[6], curve[7]);
428 }
429 if (draw_midpoint) {
430 var midX = x_at_t(curve, 0.5);
431 var midY = y_at_t(curve, 0.5);
432 drawPointSolid(midX, midY);
433 }
434 if (draw_hodo) {
435 var hodo = hodograph(curve);
436 var hMinX = Math.min(0, hodo[0], hodo[2], hodo[4]);
437 var hMinY = Math.min(0, hodo[1], hodo[3], hodo[5]);
438 var hMaxX = Math.max(0, hodo[0], hodo[2], hodo[4]);
439 var hMaxY = Math.max(0, hodo[1], hodo[3], hodo[5]);
440 var hScaleX = hMaxX - hMinX > 0 ? ctx.canvas.width / (hMaxX - hMinX) : 1;
441 var hScaleY = hMaxY - hMinY > 0 ? ctx.canvas.height / (hMaxY - hMinY) : 1;
442 var hUnit = Math.min(hScaleX, hScaleY);
443 hUnit /= 2;
444 var hx = xoffset - hMinX * hUnit;
445 var hy = yoffset - hMinY * hUnit;
446 ctx.moveTo(hx + hodo[0] * hUnit, hy + hodo[1] * hUnit);
447 ctx.quadraticCurveTo(
448 hx + hodo[2] * hUnit, hy + hodo[3] * hUnit,
449 hx + hodo[4] * hUnit, hy + hodo[5] * hUnit);
450 ctx.strokeStyle = "red";
451 ctx.stroke();
452 if (draw_hodo_origin) {
453 drawHodoOrigin(hx, hy, hMinX, hMinY, hMaxX, hMaxY);
454 }
455 }
456 if (draw_hodo2) {
457 var hodo = hodograph2(curve);
458 var hMinX = Math.min(0, hodo[0], hodo[2]);
459 var hMinY = Math.min(0, hodo[1], hodo[3]);
460 var hMaxX = Math.max(0, hodo[0], hodo[2]);
461 var hMaxY = Math.max(0, hodo[1], hodo[3]);
462 var hScaleX = hMaxX - hMinX > 0 ? ctx.canvas.width / (hMaxX - hMinX) : 1;
463 var hScaleY = hMaxY - hMinY > 0 ? ctx.canvas.height / (hMaxY - hMinY) : 1;
464 var hUnit = Math.min(hScaleX, hScaleY);
465 hUnit /= 2;
466 var hx = xoffset - hMinX * hUnit;
467 var hy = yoffset - hMinY * hUnit;
468 ctx.moveTo(hx + hodo[0] * hUnit, hy + hodo[1] * hUnit);
469 ctx.lineTo(hx + hodo[2] * hUnit, hy + hodo[3] * hUnit);
470 ctx.strokeStyle = "red";
471 ctx.stroke();
472 drawHodoOrigin(hx, hy, hMinX, hMinY, hMaxX, hMaxY);
473 }
474 if (draw_sequence) {
475 var ymin = Math.min(curve[1], curve[3], curve[5], curve[7]);
476 for (var i = 0; i < 8; i+= 2) {
477 drawLabelX(ymin, i >> 1, curve[i]);
478 }
479 var xmin = Math.min(curve[0], curve[2], curve[4], curve[6]);
480 for (var i = 1; i < 8; i+= 2) {
481 drawLabelY(xmin, i >> 1, curve[i]);
482 }
483 }
484 }
485}
486
487function drawTop() {
488 init(tests[testIndex]);
489 redraw();
490}
491
492function redraw() {
493 ctx.beginPath();
494 ctx.rect(0, 0, ctx.canvas.width, ctx.canvas.height);
495 ctx.fillStyle="white";
496 ctx.fill();
497 draw(tests[testIndex], testTitles[testIndex]);
498}
499
500function doKeyPress(evt) {
501 var char = String.fromCharCode(evt.charCode);
502 switch (char) {
503 case '2':
504 draw_hodo2 ^= true;
505 redraw();
506 break;
507 case 'd':
508 draw_deriviatives ^= true;
509 redraw();
510 break;
511 case 'e':
512 draw_endpoints ^= true;
513 redraw();
514 break;
515 case 'h':
516 draw_hodo ^= true;
517 redraw();
518 break;
519 case 'N':
520 testIndex += 9;
521 case 'n':
522 if (++testIndex >= tests.length)
523 testIndex = 0;
524 drawTop();
525 break;
526 case 'l':
527 logCurves(tests[testIndex]);
528 break;
529 case 'm':
530 draw_midpoint ^= true;
531 redraw();
532 break;
533 case 'o':
534 draw_hodo_origin ^= true;
535 redraw();
536 break;
537 case 'P':
538 testIndex -= 9;
539 case 'p':
540 if (--testIndex < 0)
541 testIndex = tests.length - 1;
542 drawTop();
543 break;
544 case 's':
545 draw_sequence ^= true;
546 redraw();
547 break;
548 case 't':
549 draw_tangents ^= true;
550 redraw();
551 break;
552 }
553}
554
555function calcXY() {
556 var e = window.event;
557 var tgt = e.target || e.srcElement;
558 var left = tgt.offsetLeft;
559 var top = tgt.offsetTop;
560 var unit = scale * ticks;
561 mouseX = (e.clientX - left - Math.ceil(at_x) + 1) / unit + xStart;
562 mouseY = (e.clientY - top - Math.ceil(at_y)) / unit + yStart;
563}
564
565var lastX, lastY;
566var activeCurve = [];
567var activePt;
568
569function handleMouseClick() {
570 calcXY();
571}
572
573function initDown() {
574 var unit = scale * ticks;
575 var xoffset = xStart * -unit + at_x;
576 var yoffset = yStart * -unit + at_y;
577 var test = tests[testIndex];
578 var bestDistance = 1000000;
579 activePt = -1;
580 for (curves in test) {
581 var testCurve = test[curves];
582 if (testCurve.length != 8) {
583 continue;
584 }
585 for (var i = 0; i < 8; i += 2) {
586 var testX = testCurve[i];
587 var testY = testCurve[i + 1];
588 var dx = testX - mouseX;
589 var dy = testY - mouseY;
590 var dist = dx * dx + dy * dy;
591 if (dist > bestDistance) {
592 continue;
593 }
594 activeCurve = testCurve;
595 activePt = i;
596 bestDistance = dist;
597 }
598 }
599 if (activePt >= 0) {
600 lastX = mouseX;
601 lastY = mouseY;
602 }
603}
604
605function handleMouseOver() {
606 if (!mouseDown) {
607 activePt = -1;
608 return;
609 }
610 calcXY();
611 if (activePt < 0) {
612 initDown();
613 return;
614 }
615 var unit = scale * ticks;
616 var deltaX = (mouseX - lastX) /* / unit */;
617 var deltaY = (mouseY - lastY) /*/ unit */;
618 lastX = mouseX;
619 lastY = mouseY;
620 activeCurve[activePt] += deltaX;
621 activeCurve[activePt + 1] += deltaY;
622 redraw();
623}
624
625function start() {
626 for (i = 0; i < testDivs.length; ++i) {
627 var title = testDivs[i].id.toString();
628 var str = testDivs[i].firstChild.data;
629 parse(str, title);
630 }
631 drawTop();
632 window.addEventListener('keypress', doKeyPress, true);
633 window.onresize = function() {
634 drawTop();
635 }
636}
637
638</script>
639</head>
640
641<body onLoad="start();">
642<canvas id="canvas" width="750" height="500"
643 onmousedown="mouseDown = true"
644 onmouseup="mouseDown = false"
645 onmousemove="handleMouseOver()"
646 onclick="handleMouseClick()"
647 ></canvas >
648</body>
649</html>