Cipal
Adapted from a CFDG program contextfreeart.org/gallery2/#design/276
Cipal by Ferma, April 30th, 2006
Log in to post a comment.
// Cipal (ge1doot)
Canvas.setpenopacity(1);
const turtle = new Turtle();
turtle.pendown();
/////////////////////////////////////////////////////
const Mat2D = class {
constructor(m) {
this.m = m;
}
rotate(v) {
const rad = (Math.PI * v) / 180;
const cos = Math.cos(rad);
const sin = Math.sin(rad);
return new Mat2D([
cos * this.m[0] + sin * this.m[2],
cos * this.m[1] + sin * this.m[3],
cos * this.m[2] - sin * this.m[0],
cos * this.m[3] - sin * this.m[1],
this.m[4],
this.m[5],
]);
}
translate(x, y = 0) {
return new Mat2D([
this.m[0],
this.m[1],
this.m[2],
this.m[3],
this.m[4] + x * this.m[0] + y * this.m[2],
this.m[5] + x * this.m[1] + y * this.m[3],
]);
}
scale(x = 1, y = x) {
return new Mat2D([
this.m[0] * x,
this.m[1] * x,
this.m[2] * y,
this.m[3] * y,
this.m[4],
this.m[5],
]);
}
flip(v) {
const rad = (Math.PI * v) / 180;
const x = Math.cos(rad);
const y = Math.sin(rad);
const n = 1 / (x * x + y * y);
const b00 = (x * x - y * y) / n;
const b01 = (2 * x * y) / n;
const b10 = (2 * x * y) / n;
const b11 = (y * y - x * x) / n;
return new Mat2D([
b00 * this.m[0] + b01 * this.m[2],
b00 * this.m[1] + b01 * this.m[3],
b10 * this.m[0] + b11 * this.m[2],
b10 * this.m[1] + b11 * this.m[3],
this.m[4],
this.m[5],
]);
}
tooSmall() {
const x = this.m[0] * this.m[0] + this.m[1] * this.m[1];
const y = this.m[2] * this.m[2] + this.m[3] * this.m[3];
return x < minSize || y < minSize;
}
transform(x, y) {
const m0 = this.m[0] * zoom;
const m1 = this.m[1] * zoom;
const m2 = this.m[2] * zoom;
const m3 = this.m[3] * zoom;
const m4 = this.m[4] * zoom - ox;
const m5 = this.m[5] * zoom - oy;
return [m0 * x + m2 * y + m4, m1 * x + m3 * y + m5];
}
boundingBox(box) {
const p0 = this.transform(-0.5, -0.5);
const p1 = this.transform(0.5, -0.5);
const p2 = this.transform(0.5, 0.5);
const p3 = this.transform(-0.5, 0.5);
const minx = Math.min(p0[0], p1[0], p2[0], p3[0]);
const maxx = Math.max(p0[0], p1[0], p2[0], p3[0]);
const miny = Math.min(p0[1], p1[1], p2[1], p3[1]);
const maxy = Math.max(p0[1], p1[1], p2[1], p3[1]);
if (minx < box[0]) box[0] = minx;
else if (maxx > box[2]) box[2] = maxx;
if (miny < box[1]) box[1] = miny;
else if (maxy > box[3]) box[3] = maxy;
}
};
///////////////////////////////////////////////////////
const minSize = 0.01;
const shapes = [];
let zoom = 1,
ox = 0,
oy = 0;
const box = [100, 100, -100, -100];
const rect = (m, a = 0, s = 0) => {
m.boundingBox(box);
m.m[6] = a;
m.m[7] = s;
shapes.push(m);
};
const scale = (w, h, margin = 0.9) => {
zoom = Math.min(
(margin * w) / (box[2] - box[0]),
(margin * h) / (box[3] - box[1]),
);
ox = (box[0] + box[2]) * 0.5 * zoom;
oy = (box[3] + box[1]) * 0.5 * zoom;
};
const draw = (m) => {
const p0 = m.transform(-0.5, -0.5);
const p1 = m.transform(0.5, -0.5);
const p2 = m.transform(0.5, 0.5);
const p3 = m.transform(-0.5, 0.5);
clipper.drawPolygon([...p0, ...p1, ...p2, ...p3], {
outline: true,
hatch: m.m[7] ? { angle: m.m[6], pitch: m.m[7] } : null,
});
};
////////////////////////////////////////////////////
const branch = (m) => {
if (m.tooSmall() === true) return;
const r = Math.random() * 12.1;
switch (true) {
case r <= 0.4:
branch(m.scale(0.5).rotate(5));
return branch(m.scale(0.97).rotate(-0.9));
case r <= 1.3:
return branch(m.flip(50));
case r <= 2.3:
return branch(m.flip(20));
case r <= 4.1:
return branch(m.flip(99));
case r <= 8.1:
rect(m);
return branch(m.translate(0, -1).scale(0.99).rotate(-1));
default:
rect(m, Math.atan2(-m.m[3], m.m[2]), 0.1);
return branch(m.translate(0, -0.5).rotate(-1));
}
};
////////////////////////////////////////////////////
const clipper = PolyClip(turtle);
const tick = clipper.walk(() => {
const m = shapes.pop();
if (!m) return false;
draw(m);
return true;
}, 2); // tempo (milliseconds)
// run CFDG
branch(new Mat2D([1, 0, 0, -1, 0, 0]));
scale(200, 200, 0.95);
// Turtletoy walk function
function walk(i) {
return tick();
}
////////////////////////////////////////////////////
// PolyClip — analytic segment / polygon clipping
// Inspired by Reinder Nijhoff's Polygon Clipping Utility (2019, MIT)
// ge1doot — November 2026
function PolyClip(
turtle,
bounds = [-100, -100, 100, 100],
stroke = (x0, y0, x1, y1) => {
turtle.jump([x0, y0]);
turtle.goto([x1, y1]);
},
) {
const epsilon = 1e-9,
crossings = [],
spans = [],
layers = [],
[xmin, ymin, xmax, ymax] = bounds,
a = new Float64Array(2),
b = new Float64Array(2),
p0 = new Float64Array(2),
p1 = new Float64Array(2),
pieces = [],
masks = [],
occluders = [],
intersections = [];
let hx, hy, nx, ny;
function prepare(points) {
const flat = typeof points?.[0] === "number",
count = flat ? points.length / 2 : points?.length,
xy = new Float64Array(count * 2);
let minx = Infinity,
miny = Infinity,
maxx = -Infinity,
maxy = -Infinity;
for (let i = 0; i < count; i++) {
const x = flat ? points[2 * i] : points[i][0];
const y = flat ? points[2 * i + 1] : points[i][1];
xy[i * 2] = x;
xy[i * 2 + 1] = y;
if (x < minx) minx = x;
if (x > maxx) maxx = x;
if (y < miny) miny = y;
if (y > maxy) maxy = y;
}
return { xy, minx, miny, maxx, maxy };
}
function subtractRanges(a, b, ranges) {
const ax = a[0],
ay = a[1],
bx = b[0],
by = b[1],
dx = bx - ax,
dy = by - ay,
length = Math.hypot(dx, dy),
output = (lo, hi) => {
if (hi - lo > tEps)
emitBounded(ax + dx * lo, ay + dy * lo, ax + dx * hi, ay + dy * hi);
};
if (length <= epsilon) return;
const tEps = epsilon / length;
spans.length = 0;
for (let i = 0; i < ranges.length; i += 2) {
const lo = Math.max(0, Math.min(ranges[i], ranges[i + 1]));
const hi = Math.min(1, Math.max(ranges[i], ranges[i + 1]));
if (hi - lo > tEps) spans.push(lo, hi);
}
union(spans, tEps);
let at = 0;
for (let i = 0; i < spans.length; i += 2) {
output(at, spans[i]);
at = Math.max(at, spans[i + 1]);
}
output(at, 1);
}
function emitBounded(x0, y0, x1, y1) {
const dx = x1 - x0,
dy = y1 - y0;
let lo = 0,
hi = 1;
function trim(p, q) {
if (Math.abs(p) < 1e-12) return q >= 0;
const t = q / p;
if (p < 0) lo = Math.max(lo, t);
else hi = Math.min(hi, t);
return lo <= hi;
}
if (
!trim(-dx, x0 - xmin) ||
!trim(dx, xmax - x0) ||
!trim(-dy, y0 - ymin) ||
!trim(dy, ymax - y0)
)
return;
if (hi - lo <= epsilon / Math.max(1, Math.hypot(dx, dy))) return;
stroke(x0 + dx * lo, y0 + dy * lo, x0 + dx * hi, y0 + dy * hi);
}
function visible(x0, y0, x1, y1) {
p0[0] = x0;
p0[1] = y0;
p1[0] = x1;
p1[1] = y1;
if (!occluders.length) {
emitBounded(x0, y0, x1, y1);
return;
}
const dx = x1 - x0,
dy = y1 - y0,
len2 = dx * dx + dy * dy;
if (len2 <= epsilon * epsilon) return;
const minx = Math.min(x0, x1),
maxx = Math.max(x0, x1),
miny = Math.min(y0, y1),
maxy = Math.max(y0, y1);
masks.length = 0;
for (let j = 0; j < occluders.length; j++) {
const q = occluders[j];
if (!(q.maxx < minx || q.minx > maxx || q.maxy < miny || q.miny > maxy)) {
intersections.length = 0;
intersect(p0, p1, q, intersections);
for (let k = 0; k < intersections.length; k += 4) {
masks.push(
((intersections[k] - x0) * dx + (intersections[k + 1] - y0) * dy) /
len2,
((intersections[k + 2] - x0) * dx +
(intersections[k + 3] - y0) * dy) /
len2,
);
}
}
}
subtractRanges(p0, p1, masks);
}
function viewportLine(s) {
let lo = -Infinity,
hi = Infinity;
const cx = s * nx,
cy = s * ny;
if (Math.abs(hx) < 1e-12) {
if (cx < xmin || cx > xmax) return false;
} else {
const t0 = (xmin - cx) / hx,
t1 = (xmax - cx) / hx;
lo = Math.max(lo, Math.min(t0, t1));
hi = Math.min(hi, Math.max(t0, t1));
}
if (Math.abs(hy) < 1e-12) {
if (cy < ymin || cy > ymax) return false;
} else {
const t0 = (ymin - cy) / hy,
t1 = (ymax - cy) / hy;
lo = Math.max(lo, Math.min(t0, t1));
hi = Math.min(hi, Math.max(t0, t1));
}
if (!(hi - lo > epsilon)) return false;
a[0] = cx + lo * hx;
a[1] = cy + lo * hy;
b[0] = cx + hi * hx;
b[1] = cy + hi * hy;
return true;
}
function gather(ax, ay, bx, by, poly, length, out) {
if (
poly.maxx < Math.min(ax, bx) - epsilon ||
poly.minx > Math.max(ax, bx) + epsilon ||
poly.maxy < Math.min(ay, by) - epsilon ||
poly.miny > Math.max(ay, by) + epsilon
)
return;
const dx = bx - ax,
dy = by - ay,
invLength2 = 1 / (length * length),
sideEps = epsilon * length,
tEps = epsilon / length,
xy = poly.xy;
crossings.length = 0;
let x0 = xy[xy.length - 2],
y0 = xy[xy.length - 1],
s0 = dx * (y0 - ay) - dy * (x0 - ax);
if (Math.abs(s0) <= sideEps) s0 = 0;
let t0 = ((x0 - ax) * dx + (y0 - ay) * dy) * invLength2;
for (let i = 0; i < xy.length; i += 2) {
const x1 = xy[i],
y1 = xy[i + 1];
let s1 = dx * (y1 - ay) - dy * (x1 - ax);
if (Math.abs(s1) <= sideEps) s1 = 0;
const t1 = ((x1 - ax) * dx + (y1 - ay) * dy) * invLength2;
if (s0 === 0 && s1 === 0) {
const lo = Math.max(0, Math.min(t0, t1)),
hi = Math.min(1, Math.max(t0, t1));
if (hi - lo > tEps) out.push(lo, hi);
} else if (s0 > 0 !== s1 > 0)
crossings.push(t0 + ((t1 - t0) * s0) / (s0 - s1));
x0 = x1;
y0 = y1;
s0 = s1;
t0 = t1;
}
crossings.sort((a, b) => a - b);
for (let i = 0; i + 1 < crossings.length; i += 2) {
const lo = Math.max(0, crossings[i]),
hi = Math.min(1, crossings[i + 1]);
if (hi - lo > tEps) out.push(lo, hi);
}
}
function sortPairs(a, left, right) {
while (left < right) {
let i = left,
j = right;
const pivot = a[2 * ((left + right) >> 1)];
while (i <= j) {
while (a[2 * i] < pivot) i++;
while (a[2 * j] > pivot) j--;
if (i <= j) {
const lo = a[2 * i],
hi = a[2 * i + 1];
a[2 * i] = a[2 * j];
a[2 * i + 1] = a[2 * j + 1];
a[2 * j] = lo;
a[2 * j + 1] = hi;
i++;
j--;
}
}
if (j - left < right - i) {
if (left < j) sortPairs(a, left, j);
left = i;
} else {
if (i < right) sortPairs(a, i, right);
right = j;
}
}
}
function union(a, tEps) {
if (!a.length) return;
if (a.length > 2) sortPairs(a, 0, a.length / 2 - 1);
let lo = a[0],
hi = a[1],
w = 0;
for (let i = 2; i < a.length; i += 2) {
if (a[i] <= hi + tEps) hi = Math.max(hi, a[i + 1]);
else {
a[w++] = lo;
a[w++] = hi;
lo = a[i];
hi = a[i + 1];
}
}
a[w++] = lo;
a[w++] = hi;
a.length = w;
}
function intersect(a, b, poly, out) {
const ax = a[0],
ay = a[1],
bx = b[0],
by = b[1],
dx = bx - ax,
dy = by - ay,
length = Math.hypot(dx, dy);
if (length <= epsilon) return;
spans.length = 0;
gather(ax, ay, bx, by, poly, length, spans);
const tEps = epsilon / length;
union(spans, tEps);
for (let i = 0; i < spans.length; i += 2) {
const lo = spans[i],
hi = spans[i + 1];
if (hi - lo > tEps) {
out.push(ax + dx * lo, ay + dy * lo, ax + dx * hi, ay + dy * hi);
}
}
}
return {
drawPolygon(
points,
{ outline = false, hatch = null, segments = null, occlude = true } = {},
) {
const poly =
points && points.xy instanceof Float64Array
? points
: prepare(points),
minx = Math.max(xmin, poly.minx),
maxx = Math.min(xmax, poly.maxx),
miny = Math.max(ymin, poly.miny),
maxy = Math.min(ymax, poly.maxy),
pitch = hatch ? (hatch.pitch ?? hatch.step ?? 0) : 0,
angle = hatch ? (hatch.angle ?? 0) : 0;
if (minx < maxx && miny < maxy && (outline || pitch || segments)) {
occluders.length = 0;
for (let j = 0; j < layers.length; j++) {
const q = layers[j];
if (!(
q.maxx < minx ||
q.minx > maxx ||
q.maxy < miny ||
q.miny > maxy
))
occluders.push(q);
}
if (outline) {
const xy = poly.xy;
for (let q = 0; q < xy.length; q += 2) {
const n = (q + 2) % xy.length;
visible(xy[q], xy[q + 1], xy[n], xy[n + 1]);
}
}
if (segments) {
if (typeof segments[0] === "number") {
for (let q = 0; q < segments.length; q += 4)
visible(
segments[q],
segments[q + 1],
segments[q + 2],
segments[q + 3]
);
} else {
for (const [p, q] of segments)
visible(p[0], p[1], q[0], q[1]);
}
}
if (pitch > 0) {
hx = Math.cos(angle);
hy = Math.sin(angle);
nx = -hy;
ny = hx;
const sMin =
(nx > 0 ? nx * minx : nx * maxx) + (ny > 0 ? ny * miny : ny * maxy);
const sMax =
(nx > 0 ? nx * maxx : nx * minx) + (ny > 0 ? ny * maxy : ny * miny);
for (
let k = Math.ceil((sMin - 1e-10) / pitch);
k <= Math.floor((sMax + 1e-10) / pitch);
k++
) {
if (!viewportLine(k * pitch)) continue;
pieces.length = 0;
intersect(a, b, poly, pieces);
for (let q = 0; q < pieces.length; q += 4)
visible(
pieces[q],
pieces[q + 1],
pieces[q + 2],
pieces[q + 3]
);
}
}
}
if (occlude) layers.push(poly);
},
walk(draw, intervalMs = 0) {
let next = 0;
return function () {
const now = performance.now();
if (now < next) return true;
const more = draw();
next = now + intervalMs;
return more;
};
},
};
}