Computer Graphics & Visualization @ufrj.br
Public
Edited
Feb 2, 2023
1 fork
6 stars
Canvas primerCanvas primer IISVG IntroMinimal WebGL ProgramWebGL primer with reglShadertoy style drawingTransformation demoModelview DemoModel, View and Projection DemoWebGL CubeCatmull Clark SubdivisionThree.js basicsPhong Illumination modelHalf-edge data structureIterated Function SystemsRaytracingTextured sphereEnvironment mappingPhysical animation with shape matchingShape matching2D GJK and EPA algorithmsOmohundro balltree construction algorithmsPlatonic Solids PlaygroundElliptic billiards 3-periodics in space-time3D LabyrinthBrush drawingBump mappingFractal TerrainModel viewerKeyframe animationTextured planeSimple Adaptive Mosaic EffectsWallpaper GroupsRay marchingVolume rendering with slice compositingDisplaying 3D RBFs with ray marchingFunções 2D úteisRandom space-filling curvesGPU-IO3D Apollonian Sphere PackingsCircle inversion fractalsSmooth PolygonDocument image segmentationB-SplinesStencil bufferNoise LoopsSimplex noise exerciserDeformation with RBFsRandom shapes in a gridHobby curvesLane-Riesenfeld subdivision
Apollonian gasket construction by inversion
import { vec2 } from "@esperanc/vec2-utils"
//
// Returns the incenter of triangle ABC.
//
function incenter(A, B, C) {
const [[ax, ay], [bx, by], [cx, cy]] = [A, B, C];
const [a, b, c] = [
[B, C],
[C, A],
[A, B]
].map(([P, Q]) => Math.hypot(P[0] - Q[0], P[1] - Q[1]));
return [
(a * ax + b * bx + c * cx) / (a + b + c),
(a * ay + b * by + c * cy) / (a + b + c)
];
}
//
// Returns the orthogonal projection of a point P on line AB
//
function lineProj(P, A, B) {
const u = vec2.sub([], P, A);
const v = vec2.sub([], B, A);
const vnorm = vec2.normalize([], v);
const QA = vec2.scale([], vnorm, vec2.dot(vnorm, u));
return vec2.add([], A, QA);
}
//
// Returns the center and radius of circle inscribed in triangle ABC.
//
function inscribedCircle(A, B, C) {
const center = incenter(A, B, C);
const radius = vec2.length(vec2.sub([], center, lineProj(center, A, B)));
return [center, radius];
}
//
// Returns the three circles that touch each other and are centered at
// the vertices of triangle A, B, C
//
function threeTangentCircles(A, B, C) {
const center = incenter(A, B, C);
const [P, Q] = [lineProj(center, A, B), lineProj(center, B, C)];
return [
[A, vec2.distance(P, A)],
[B, vec2.distance(P, B)],
[C, vec2.distance(Q, C)]
];
}
//
// Returns the line segment AB extended by delta units
//
function extendLineSegment(A, B, delta) {
const u = vec2.sub([], B, A);
const unorm = vec2.length(u);
return [
vec2.lerp([], A, B, -delta / unorm),
vec2.lerp([], A, B, 1 + delta / unorm)
];
}
//
// Auxiliary points. Given two points A,B and a circle centered at C and radius r,
// returns two points of intersection between the circle and a line that is
// perpendicular to A,B and passes through C
//
function auxPoints(A, B, C, r) {
const P = lineProj(C, A, B);
const d = vec2.distance(P, C);
return [vec2.lerp([], P, C, (d - r) / d), vec2.lerp([], P, C, (d + r) / d)];
}
//
// Given a line passing through A and B, and a circle centered at C and radius r
// returns the two intersection points with the circumference.
//
function circleLineIntersection(A, B, C, r) {
const v = vec2.sub([], B, A);
const [[ax, ay], [bx, by], [cx, cy]] = [vec2.sub([], A, C), B, C];
const [vx, vy] = v;
const vnorm2 = vx * vx + vy * vy;
const d =
r * r * vnorm2 +
2 * vx * vy * ax * ay -
vy * vy * ax * ax -
vx * vx * ay * ay;
const delta = Math.sqrt(d);
const alpha = -(vx * ax + vy * ay);
const [t1, t2] = [(alpha - delta) / vnorm2, (alpha + delta) / vnorm2];
return [
vec2.add([], A, vec2.scale([], v, t1)),
vec2.add([], A, vec2.scale([], v, t2))
];
}
//
// Side lengths of a triangle given its vertices A, B, C
//
function triangleSides(A, B, C) {
return [
[B, C],
[C, A],
[A, B]
].map(([P, Q]) => vec2.dist(P, Q));
}
//
// circumCenter of a triangle given its vertices A, B, C
//
function circumCenter(A, B, C) {
const [a, b, c] = triangleSides(A, B, C);
const [ta, tb, tc] = // Trilinear coordinates of the circumcenter are the cosines of the inner angles
[
[a, b, c],
[b, c, a],
[c, a, b]
].map(([a, b, c]) => (b * b + c * c - a * a) / (2 * b * c));
const [bA, bB, bC] = [a * ta, b * tb, c * tc];
const S = bA + bB + bC;
return vec2.add(
[],
vec2.scale([], A, bA / S),
vec2.add([], vec2.scale([], B, bB / S), vec2.scale([], C, bC / S))
);
}
//
// Returns the outer and inner soddy circles given three mutually
// tangent circles
//
function soddyCircles([A, a], [B, b], [C, c]) {
const innerPoints = [],
outerPoints = [];
for (let i = 0; i < 3; i++) {
const auxpoints = auxPoints(A, B, C, c);
const tanPoint = vec2.lerp([], A, B, a / (a + b));
outerPoints.push(circleLineIntersection(tanPoint, auxpoints[0], C, c)[1]);
innerPoints.push(circleLineIntersection(tanPoint, auxpoints[1], C, c)[0]);
[[A, a], [B, b], [C, c]] = [
[C, c],
[A, a],
[B, b]
];
}
const innerCenter = circumCenter(...innerPoints);
const innerRadius = vec2.dist(innerCenter, innerPoints[0]);
const outerCenter = circumCenter(...outerPoints);
const outerRadius = vec2.dist(outerCenter, outerPoints[0]);
return [
[innerCenter, innerRadius],
[outerCenter, outerRadius],
innerPoints,
outerPoints
];
}
//
// Returns the inversion of a point centered at P
// with respect to the circle centered at C and radius r
//
function pointInverse(P, C, r) {
const v = vec2.sub([], P, C);
const d = vec2.length(v);
const dp = (r * r) / (d * d);
return vec2.add([], C, vec2.scale([], v, dp));
}
//
// Returns the inversion of a circle centered at A and radius
// a with respect to the circle centered at B and radius b
//
function circleInverse(A, a, B, b) {
const [ax, ay] = A,
[bx, by] = B;
const s = (b * b) / ((ax - bx) ** 2 + (ay - by) ** 2 - a * a);
return [[bx + s * (ax - bx), by + s * (ay - by)], Math.abs(s * a)];
}
//
// Assuming the 2 circles touch each other, returns
// the point of tangency
//
function tangencyPoint([A, a], [B, b]) {
if (a > b && vec2.sqrDist(A, B) < a * a)
return vec2.lerp([], A, B, a / (a - b)); // B inside A
if (b > a && vec2.sqrDist(A, B) < b * b)
return vec2.lerp([], B, A, b / (b - a)); // A inside B
return vec2.lerp([], A, B, a / (a + b));
}
//
// Assuming the 3 circles touch each other, returns
// the 3 points of tangency
//
function tangencyPoints(A, B, C) {
return [
[A, B],
[B, C],
[C, A]
].map(([A, B]) => tangencyPoint(A, B));
}
//
// Given 3 circles that are mutually tangent, returns an
// circle orthogonal to them
function orthoCircle([A, a], [B, b], [C, c]) {
const tpoints = tangencyPoints([A, a], [B, b], [C, c]);
const center = circumCenter(...tpoints);
const radius = vec2.distance(center, tpoints[0]);
return [center, radius];
}
//
// Given 4 circles, generates a 5th one buy inverting the fourth with
// respect to the circle which is orthogonal to the first three
//
function genInversion(A, B, C, D) {
const O = orthoCircle(A, B, C);
return circleInverse(...D, ...O);
}
//
// Recursively calls genInversions up to level n
//
function recursiveGenInversions(n, A, B, C, D, accum = []) {
if (--n < 0) return accum;
const E = genInversion(A, B, C, D);
//if (E[1] > Math.min(A[1], B[1], C[1], D[1])) return accum;
accum.push(E);
for (let abcd of [
[A, B, E, C],
[A, C, E, B],
[B, C, E, A]
]) {
recursiveGenInversions(n, ...abcd, accum);
}
}
defaultOptions = ({
width: 600,
points: [
[200, 150],
[200, 350],
[400, 200]
],
aspect: 4 / 3,
strokeWidth: 2,
stroke: "#111",
fill: "purple",
pointRadius: 5,
init: () => {},
update: () => {}
})
//
// Creates an svg with some points that may be dragged, calls the init
// function and every time a point is dragged, calls the update function.
// Both functions are passed theSvg - a d3 selection of the svg - and
// the modified points array.
//
function dragPoints(options = {}) {
options = { ...defaultOptions, ...options };
const {
width,
aspect,
strokeWidth,
stroke,
fill,
pointRadius,
init,
update
} = options;
const points = options.points.map(([x, y]) => [x, y]);
const height = width / aspect;
const theSvg = d3
.select(svg`<svg width=${width} height=${height}>`)
.attr("stroke-width", strokeWidth)
.attr("stroke", stroke)
.attr("fill", fill);
init(theSvg, points);
const pointSelect = theSvg
.selectAll("circle.anchor")
.data(points)
.join("circle")
.attr("class", "anchor")
.attr("cx", (d) => d[0])
.attr("cy", (d) => d[1])
.attr("r", pointRadius)
.call(
d3.drag().on("drag", function (event, d) {
d[0] = event.x;
d[1] = event.y;
d3.select(this).attr("cx", d[0]).attr("cy", d[1]);
update(theSvg, points);
})
);
return theSvg.node();
}
One platform to build and deploy the best data apps
Experiment and prototype by building visualizations in live JavaScript notebooks. Collaborate with your team and decide which concepts to build out.
Use Observable Framework to build data apps locally. Use data loaders to build in any language or library, including Python, SQL, and R.
Seamlessly deploy to Observable. Test before you ship, use automatic deploy-on-commit, and ensure your projects are always up-to-date.