Computer Graphics & Visualization @ufrj.br
Published
Edited
Dec 20, 2021
Importers
9 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 matchingOmohundro 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 fractalsApollonian gasket construction by inversionSmooth PolygonDocument image segmentationB-SplinesStencil bufferNoise LoopsSimplex noise exerciserDeformation with RBFsRandom shapes in a gridHobby curvesLane-Riesenfeld subdivision
2D GJK and EPA algorithms
Also listed in…
Paper implementations
// Returns the point in 'pts' that maximizes the dot product with 'v'
function support(pts, v) {
let maxdot = Number.NEGATIVE_INFINITY;
let best;
for (let p of pts) {
let dot = vec2.dot(p, v);
if (dot > maxdot) [maxdot, best] = [dot, p];
}
return best;
}
// Returns the support point of the Minkowski difference pts1 - pts2 w.r.t. v
function support2(pts1, pts2, v) {
try {
return vec2.sub([], support(pts1, v), support(pts2, [-v[0], -v[1]]));
} catch (err) {
console.log("BUG Support2", pts1, pts2, v);
throw "BUG:" + err;
}
}
// Like support, but returns the index, rather than the point
function supportIndex(pts, v) {
let maxdot = Number.NEGATIVE_INFINITY;
let best = -1,
index = 0;
for (let p of pts) {
let dot = vec2.dot(p, v);
if (dot > maxdot) [maxdot, best] = [dot, index];
index++;
}
return best;
}
// The Gilbert-Johnson-Keerthi algorithm. Given two polygons (pts1, pts2), visits the
// convex hull of the Minkowski difference between them and locates a simplex (a triangle) within the hull
// that contains the origin. Returns an array [a,b,c] with the vertices of that simplex or false if
// the simplex can't be found, i.e., if the hull does not contain the origin.
function gjk(pts1, pts2) {
// First point of pts1-pts2
let a = support2(pts1, pts2, [1, 1]);
// First direction
let v = [-a[0], -a[1]];
// Second point
let b = support2(pts1, pts2, v);
if (vec2.dot(b, v) <= 0) return false; // Second point fails
// Second direction
let ab = vec2.sub([], b, a);
v = tripleProduct(ab, [-a[0], -a[1]], ab);
for (;;) {
// Third point
let c = support2(pts1, pts2, v);
if (vec2.dot(c, v) <= 0) return false; // Third point fails
let c0 = [-c[0], -c[1]];
let cb = vec2.sub([], b, c);
let ca = vec2.sub([], a, c);
let cbPerp = tripleProduct(ca, cb, cb);
let caPerp = tripleProduct(cb, ca, ca);
if (vec2.dot(caPerp, c0) > 0) {
b = c;
v = caPerp;
} else if (vec2.dot(cbPerp, c0) > 0) {
a = c;
v = cbPerp;
} else return [a, b, c];
}
}
// Given a polygon containing the origin, returns the closest edge to the origin as a data structure
// containg 'dist' (the distance), 'i' (the index of the first vertex of the edge),
// 'p' (the first vertex of the edge), 'q' (the second vertex of the edge), 'n' (the edge normal
// in the direction of the origin).
function closestEdge(polytope) {
let npts = polytope.length;
let dmin = Number.POSITIVE_INFINITY;
let closest;
for (let i = 0; i < npts; i++) {
let [p, q] = [polytope[i], polytope[(i + 1) % npts]];
let e = vec2.sub([], q, p);
let n = vec2.normalize([], tripleProduct(e, p, e));
let dist = vec2.dot(n, p);
if (dist < dmin) [dmin, closest] = [dist, { dist, i, p, q, n }];
}
return closest;
}
// The Expanding Polytope Algorithm. Starting from a triangle a,b,c within the convex hull of
// the Minkowski difference between pts1 and pts2, returns the closest edge of this hull
// as a data-structure containing 'p' (the first vertex of the edge), 'q' (the second vertex of the edge),
// 'n' (the edge normal in the direction of the origin) and 'dist' (the distance to the origin)
function epa(pts1, pts2, a, b, c) {
let polytope = [a, b, c];
for (;;) {
let { dist, i, p, q, n } = closestEdge(polytope);
let r = support2(pts1, pts2, n);
if (Math.abs(vec2.dot(n, r) - dist) < 0.001) return { p, q, dist, n };
polytope.splice(i + 1, 0, r);
}
}
// Like support, but returns not only the vertex of pts that maximizes the dot product with v,
// but also the next best contender, if sufficiently close. This is useful if v is perpendicular to one
// of the edges of pts, which is the case for the data returned by the EPA.
function supportEdge(pts, v) {
let maxdot = Number.NEGATIVE_INFINITY;
let maxdot2 = Number.NEGATIVE_INFINITY;
let best, best2;
for (let p of pts) {
let dot = vec2.dot(p, v);
if (dot > maxdot) {
[maxdot2, best2] = [maxdot, best];
[maxdot, best] = [dot, p];
} else if (dot > maxdot2) {
[maxdot2, best2] = [dot, p];
}
}
if (Math.abs(maxdot - maxdot2) < 0.01) return [best2, best];
return [best];
}
mutable changedPolygon = 0;
function minkDiff(a, b) {
let result = [];
for (let p of a) {
for (let q of b) {
result.push(vec2.sub([], p, q));
}
}
return result;
}
function minkPolygon(a, b) {
let result = [];
let prev = [Number.POSITIVE_INFINITY, Number.POSITIVE_INFINITY];
for (let ang = 0; ang < Math.PI * 2; ang += 0.05) {
let p = support2(a, b, [Math.cos(ang), Math.sin(ang)]);
if (vec2.dist(p, prev) > 0.0001) result.push(p);
prev = p;
}
return result;
}
// Returns an array of points with the vertices of a regular polygon
// centered at 'center', with the given radius and number of sides.
function regularPolygonPoints (center = [0,0], radius = 1, nsides=3) {
let poly = [];
let delta = Math.PI*2/nsides;
for (let i = 0; i < nsides; i++) {
poly.push([center[0]+radius*Math.cos(delta*i),center[1]+radius*Math.sin(delta*i)])
}
return poly
}
// Returns an array of 4 points, one for each corner of a rectangle
// having the given center and size
function rectanglePoints(center = [0, 0], size = [1, 1]) {
return [
[-0.5, -0.5],
[0.5, -0.5],
[0.5, 0.5],
[-0.5, 0.5]
].map(([dx, dy]) => [center[0] + size[0] * dx, center[1] + size[1] * dy]);
}
// Returns the center of mass of an array of 2d points
function centerOfMass(pts) {
let sum = pts.reduce((a, b) => [a[0] + b[0], a[1] + b[1]]);
return [sum[0] / pts.length, sum[1] / pts.length];
}
// Returns true iff p inside poly
function pointInPolygon(p, poly) {
let [x, y] = p;
let xLeft = Number.NEGATIVE_INFINITY,
xRight = Number.POSITIVE_INFINITY;
let leftSign = 0,
rightSign = 0;
let q = poly[poly.length - 1];
for (let p of poly) {
if (q[1] < y != p[1] < y) {
let alpha = (p[1] - y) / (p[1] - q[1]);
let xi = p[0] * (1 - alpha) + q[0] * alpha;
if (xi < x) {
if (xi > xLeft) {
xLeft = xi;
leftSign = Math.sign(p[1] - q[1]);
}
} else {
if (xi < xRight) {
xRight = xi;
rightSign = Math.sign(p[1] - q[1]);
}
}
}
q = p;
}
return (
xLeft != Number.NEGATIVE_INFINITY &&
xRight != Number.POSITIVE_INFINITY &&
leftSign < 0
);
}
// A canvas display helper class
class Display {
constructor(w = 640, h = 480) {
[this.w, this.h] = [w, h];
this.canvas = html`<canvas width=${w} height=${h} style="border:1px solid gray" />`;
this.canvas.value = this;
this.ctx = this.canvas.getContext('2d');
}
clear() {
this.ctx.clearRect(0, 0, this.w, this.h);
}
drawPoints(pts, options = {}) {
options = Object.assign(
{ radius: 4, fill: 'black', stroke: null },
options
);
this.ctx.save();
this.ctx.strokeStyle = options.stroke;
this.ctx.fillStyle = options.fill;
for (let p of pts) {
this.ctx.beginPath();
this.ctx.arc(p[0], p[1], options.radius, 0, Math.PI * 2);
if (options.fill) this.ctx.fill();
if (options.stroke) this.ctx.stroke();
}
this.ctx.restore();
}
drawPolygon(pts, options = {}) {
options = Object.assign(
{
radius: 4,
fill: null,
stroke: 'black',
lineWidth: 1,
dash: [],
close: true
},
options
);
this.ctx.save();
this.ctx.strokeStyle = options.stroke;
this.ctx.fillStyle = options.fill;
this.ctx.setLineDash(options.dash);
this.ctx.lineWidth = options.lineWidth;
this.ctx.beginPath();
this.ctx.moveTo(pts[0][0], pts[0][1]);
for (let p of pts) {
this.ctx.lineTo(p[0], p[1]);
}
if (options.close) this.ctx.closePath();
if (options.fill) this.ctx.fill();
if (options.stroke) this.ctx.stroke();
this.ctx.restore();
}
}
glmatrix = import('https://unpkg.com/gl-matrix@3.3.0/esm/index.js?module')
vec2 = glmatrix.vec2
import { combo } from "@esperanc/aggregated-inputs"
import { select } from "@jashkenas/inputs"
Purpose-built for displays of data
Observable is your go-to platform for exploring data and creating expressive data visualizations. Use reactive JavaScript notebooks for prototyping and a collaborative canvas for visual data exploration and dashboard creation.
