31:Tff3,class Mesh { constructor({ positions, faces, cells, modelMatrix, color = "white" }) { this.color = parseColor(color); this.linearColor = this.color.map(srgbToLinear); Object.defineProperties(this, { modelMatrix: { enumerable: true, get: function () { return this._model; }, set: function (m) { delete this._normalMatrix; Object.defineProperty(this, "_model", { value: modelMatrix ? mat4copy([], modelMatrix) : mat4create(), enumerable: false }); } }, normalMatrix: { enumerable: true, get: function () { if (!this._normalMatrix) { this._normalMatrix = mat3normalFromMat4([], this.modelMatrix); } return this._normalMatrix; } }, positions: { enumerable: true, get: function () { return this._positions; }, set: function (p) { delete this._faceCentroids; delete this._faceNormals; Object.defineProperty(this, "_positions", { value: p, enumerable: false }); } }, faces: { enumerable: true, get: function () { return this._faces; }, set: function (f) { delete this._faceCentroids; delete this._faceNormals; Object.defineProperty(this, "_faces", { value: f, enumerable: false }); } }, faceCentroids: { enumerable: true, get: function () { if (!this._faceCentroids) { const centroids = []; Object.defineProperty(this, "_faceCentroids", { enumerable: false, value: centroids }); for (const face of this._faces) { let xsum = 0; let ysum = 0; let zsum = 0; for (let i = 0; i < face.length; i++) { const p = this._positions[face[i]]; xsum += p[0]; ysum += p[1]; zsum += p[2]; } xsum /= face.length; ysum /= face.length; zsum /= face.length; centroids.push([xsum, ysum, zsum]); } } return this._faceCentroids; } }, faceNormals: { enumerable: true, get: function () { if (!this._faceNormals) { const normals = []; Object.defineProperty(this, "_faceNormals", { enumerable: false, value: normals }); for (const face of this._faces) { let nx = 0; let ny = 0; let nz = 0; const n = face.length; for (let i = 0; i < n; i++) { const [x0, y0, z0] = this._positions[face[i]]; const [x1, y1, z1] = this._positions[face[(i + 1) % n]]; nx += (y0 - y1) * (z0 + z1); ny += (z0 - z1) * (x0 + x1); nz += (x0 - x1) * (y0 + y1); } const length = Math.hypot(nx, ny, nz); if (length === 0) return [0, 0, 0]; normals.push([nx / length, ny / length, nz / length]); } } return this._faceNormals; } } }); this.positions = positions; this.faces = faces || cells; this.modelMatrix = [1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1]; } static cube(args = {}) { return new Mesh({ ...args, positions: [ [-1, -1, -1], [1, -1, -1], [-1, 1, -1], [1, 1, -1], [-1, -1, 1], [1, -1, 1], [-1, 1, 1], [1, 1, 1] ], faces: [ [0, 1, 3, 2].toReversed(), [1, 5, 7, 3].toReversed(), [5, 4, 6, 7].toReversed(), [4, 0, 2, 6].toReversed(), [2, 3, 7, 6].toReversed(), [1, 0, 4, 5].toReversed() ] }); } }32:Tcd1,function drawScene( meshes, { projection = mat4create(), lights = [], useJoinKey = false } = {} ) { const renderFaces = []; const line = d3.line(); const N = [0, 0, 0]; return function (selection, {} = {}) { renderFaces.length = 0; const MAX_MESHES = 1 << 16; for (const [meshIndex, mesh] of Object.entries(meshes)) { const faces = mesh.faces; const indexedVertices = mesh.positions; const modelMatrix = mesh.modelMatrix; const normalMatrix = mesh.normalMatrix; const mvc = mat4multiply([], projection, mesh.modelMatrix); const projectedVertices = mesh.positions.map((v) => vec3transformMat4([], v, mvc) ); const transformedNormals = mesh.faceNormals.map((n) => vec3transformMat3([], n, normalMatrix) ); const transformedCentroids = mesh.faceCentroids.map((p) => vec3transformMat4([], p, modelMatrix) ); for (const [faceIndex, face] of Object.entries(mesh.faces)) { const frontFacing = isFrontFacing(face, projectedVertices); if (!frontFacing) continue; let depth = 0; for (const index of face) depth += projectedVertices[index][2]; depth /= face.length; const key = meshIndex * MAX_MESHES + faceIndex; const centroid = transformedCentroids[faceIndex]; const normal = transformedNormals[faceIndex]; const accumColor = [0, 0, 0]; const materialColor = mesh.linearColor; for (const light of lights) { switch (light.type) { case "ambient": vec3add( accumColor, accumColor, vec3mul([], light.linearColor, materialColor) ); break; case "point": const V = vec3sub([], light.position, centroid); const VdotN = Math.max(0, vec3dot(vec3normalize(V, V), normal)); vec3scaleAndAdd( accumColor, accumColor, vec3mul([], light.linearColor, materialColor), VdotN ); break; } } const color = `rgb(${accumColor .map((c) => Math.max(0, Math.min(255, Math.floor(255 * linearToSrgb(c)))) ) .join(",")})`; renderFaces.push({ key, projectedVertices, face, depth, frontFacing, color }); } renderFaces.sort(({ depth: d1 }, { depth: d2 }) => d2 - d1); } selection .selectAll("path") .data(renderFaces, useJoinKey ? ({ key }) => key : null) .join( (enter) => enter .append("path") .attr( "d", ({ face, projectedVertices }) => line(face.map((i) => projectedVertices[i])) + "Z" ), (update) => update.attr( "d", ({ face, projectedVertices }) => line(face.map((i) => projectedVertices[i])) + "Z" ), (exit) => exit.remove() ); selection .selectAll("path") .style("stroke", "black") .style("stroke-width", 0.5) .style("fill", ({ color }) => color); }; }33:[] 2f:{"title":"Drawing 3D Objects with SVG","cells":[{"id":0,"value":"# Drawing 3D Objects with SVG","pinned":false,"hidden":false,"mode":"md"},{"id":7,"value":"figure = d3\n .create(\"svg\")\n .attr(\"viewBox\", [0, 0, ...shape])\n .attr(\"width\", shape[0])\n .attr(\"height\", shape[1])\n .call(drawScene([cube1, cube2, icosphere], { projection, lights }))\n .node()","pinned":true,"hidden":false,"mode":"ojs"},{"id":534,"value":"viewof rotation = Scrubber([...Array(360).keys()])","pinned":false,"hidden":false,"mode":"ojs"},{"id":1088,"value":"viewof cpuTemperature = Inputs.range([0, 6], {\n label: \"CPU Temperature\",\n step: 1,\n value: 2\n})","pinned":false,"hidden":false,"mode":"ojs"},{"id":959,"value":"Unless you've worked in 3D environments before, it's not initially obvious that although GPUs and OpenGLs and shader whatnots are extremely powerful environments for creating 3D graphics, all that has little to do with the relatively simple math of projecting 3D objects to a 2D screen. This notebook strips out all the power and implements a simple, naïve function that renders 3D polygonal faces to SVG `` elements.","pinned":false,"hidden":false,"mode":"md"},{"id":1062,"value":"\nTwo reasons you *might* want to do this is that WebGL and WebGPU contexts are expensive and limited in number before older contexts are lost. SVG figures are bit friendlier. And for everything you lose with shaders and performance, you also get object picking and SVG styling features which are somewhat more involved to implement in a proper 3D context.","pinned":false,"hidden":false,"mode":"md"},{"id":1065,"value":"And, really, because you *can*.","pinned":false,"hidden":false,"mode":"md"},{"id":997,"value":"\n\nThe basic pipeline is:","pinned":false,"hidden":false,"mode":"md"},{"id":961,"value":"1. Collect faces across all meshes\n2. Project vertices to screen by arbitrary 4×4 projection matrix\n3. Cull back-faces\n4. Sort faces by centroid using the [painter's algorithm](https://en.wikipedia.org/wiki/Painter%27s_algorithm)\n5. Compute per-face lighting\n6. Update SVG path elements with D3 data join","pinned":false,"hidden":false,"mode":"md"},{"id":984,"value":"Not yet implemented are:\n- material properties\n- face/object picking\n- a scene graph, maybe? Or is that scope creep?","pinned":false,"hidden":false,"mode":"md"},{"id":966,"value":"You should probably be using WebGL or WebGPU though.","pinned":false,"hidden":false,"mode":"md"},{"id":1147,"value":"### Addendum\n\nI constructed the drawScene function to be idempotent using D3 joins, that is, it mutates the content to update the scene rather than re-creating a new SVG element for each update. Surprisingly—to me, at least—this is somewhat *slower* than just re-creating a new SVG for each frame.","pinned":false,"hidden":false,"mode":"md"},{"id":1202,"value":"It appears the culprit is a linear search for keyed elements to be updated, which becomes ${tex`\\mathcal{O}(n^2)`} when updating ${tex`n`} elements. I added a `useJoinKey` flag which may be set `false` to improve performance by electing not to match up keyed elements.","pinned":false,"hidden":false,"mode":"md"},{"id":1156,"value":"The following re-uses elements and is idempotent when operating on the same SVG element, but it's significantly slower. ","pinned":false,"hidden":false,"mode":"md"},{"id":1196,"value":"/*((this && d3.select(this)) || d3.create(\"svg\"))\n .attr(\"viewBox\", [0, 0, ...shape])\n .attr(\"width\", shape[0])\n .attr(\"height\", shape[1])\n .call((el) =>\n el\n .selectAll(\"g\")\n .data([null])\n .join(\"g\")\n .call(\n drawScene([cube1, cube2, icosphere], {\n projection,\n lights,\n useJoinKey: true\n })\n )\n )\n .node()*/","pinned":true,"hidden":false,"mode":"ojs"},{"id":1050,"value":"## Scene definition","pinned":false,"hidden":false,"mode":"md"},{"id":680,"value":"shape = [Math.min(640, width), Math.floor(Math.min(640, width) * (3 / 4))]","pinned":false,"hidden":false,"mode":"ojs"},{"id":627,"value":"icosphere = new Mesh({\n ...createIcosphere(cpuTemperature),\n color: \"#33ff88\",\n modelMatrix: mat4fromRotation([], rotation * (Math.PI / 180), [0, 1, 0])\n})","pinned":false,"hidden":false,"mode":"ojs"},{"id":425,"value":"cube1 = Mesh.cube({\n color: \"#ff3388\",\n modelMatrix: mat4translate(\n [],\n mat4rotate(\n [],\n mat4fromRotation([], rotation * (Math.PI / 180), [0, 1, 0]),\n -1.5 * rotation * (Math.PI / 180),\n [1, 0, 0]\n ),\n [3, 0, 0]\n )\n})","pinned":false,"hidden":false,"mode":"ojs"},{"id":581,"value":"cube2 = Mesh.cube({\n color: \"#3388ff\",\n modelMatrix: mat4translate(\n [],\n mat4rotate(\n [],\n mat4fromRotation([], rotation * (Math.PI / 180), [0, 1, 0]),\n 1.5 * rotation * (Math.PI / 180),\n [1, 0, 0]\n ),\n [-3, 0, 0]\n )\n})","pinned":false,"hidden":false,"mode":"ojs"},{"id":794,"value":"ambientLight = Light.ambient()","pinned":false,"hidden":false,"mode":"ojs"},{"id":797,"value":"pointLight = Light.point()","pinned":false,"hidden":false,"mode":"ojs"},{"id":678,"value":"projection = {\n const persp = mat4perspective([], Math.PI / 4, shape[0] / shape[1], 0.1, 10);\n const view = mat4lookAt([], [0, 3.5, 8], [0, 0, 0], [0, 1, 0]);\n const clip = mat4clip([], shape[0], shape[1]);\n return mat4multiply([], clip, mat4multiply([], persp, view));\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":1106,"value":"lights = [ambientLight, pointLight]","pinned":false,"hidden":false,"mode":"ojs"},{"id":1054,"value":"## Renderer Implementation","pinned":false,"hidden":false,"mode":"md"},{"id":332,"value":"$31","pinned":false,"hidden":false,"mode":"ojs"},{"id":743,"value":"Light = {\n return class Light {\n constructor({ position = null, color = \"white\" } = {}) {\n this.position = position;\n this.color = parseColor(color);\n this.linearColor = this.color.map(srgbToLinear);\n }\n\n get type() {\n return this.position ? \"point\" : \"ambient\";\n }\n\n static ambient({ color = \"#333\" } = {}) {\n return new Light({ color });\n }\n\n static point({ color = \"#ccc\", position = [0, 10, 0] } = {}) {\n return new Light({ color, position });\n }\n };\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":472,"value":"$32","pinned":false,"hidden":false,"mode":"ojs"},{"id":288,"value":"function isFrontFacing(face, vertices) {\n let area = 0;\n for (let i = 0; i < face.length; i++) {\n const [x0, y0] = vertices[face[i]];\n const [x1, y1] = vertices[face[(i + 1) % face.length]];\n area += x0 * y1 - x1 * y0;\n }\n return area < 0;\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":358,"value":"function computeFaceNormal(vertices) {\n let nx = 0,\n ny = 0,\n nz = 0;\n const n = vertices.length;\n\n for (let i = 0; i < n; i++) {\n const [x0, y0, z0] = vertices[i];\n const [x1, y1, z1] = vertices[(i + 1) % n];\n\n nx += (y0 - y1) * (z0 + z1);\n ny += (z0 - z1) * (x0 + x1);\n nz += (x0 - x1) * (y0 + y1);\n }\n\n // Normalize the result\n const length = Math.hypot(nx, ny, nz);\n if (length === 0) return [0, 0, 0]; // Degenerate case\n return [nx / length, ny / length, nz / length];\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":127,"value":"function mat4clip(out, w, h, x0 = 0, y0 = h) {\n out[0] = w / 2;\n out[1] = 0;\n out[2] = 0;\n out[3] = 0;\n\n out[4] = 0;\n out[5] = -h / 2;\n out[6] = 0;\n out[7] = 0;\n\n out[8] = 0;\n out[9] = 0;\n out[10] = 0.5;\n out[11] = 0;\n\n out[12] = x0 + w / 2;\n out[13] = y0 - h / 2;\n out[14] = 0.5;\n out[15] = 1;\n return out;\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":759,"value":"parseColor = {\n const canvas = document.createElement(\"canvas\");\n canvas.width = canvas.height = 1;\n const ctx = canvas.getContext(\"2d\");\n\n return function parseColor(color) {\n ctx.fillStyle = color;\n ctx.fillRect(0, 0, 1, 1);\n const [r, g, b] = ctx.getImageData(0, 0, 1, 1).data;\n return [r / 255, g / 255, b / 255];\n };\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":778,"value":"function linearToSrgb(c) {\n return c <= 0.0031308\n ? 12.92 * c\n : 1.055 * Math.pow(c, 1 / 2.4) - 0.055;\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":776,"value":"function srgbToLinear(c) {\n return c <= 0.04045 ? c / 12.92 : Math.pow((c + 0.055) / 1.055, 2.4);\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":620,"value":"import { createIcosphere } from \"@rreusser/icosphere\"","pinned":false,"hidden":false,"mode":"ojs"},{"id":95,"value":"import {\n mat4ortho,\n mat4lookAt,\n mat4perspective,\n mat4multiply,\n mat4create,\n mat4fromTranslation,\n mat4copy,\n mat4fromRotation,\n mat4translate,\n mat4rotate\n} from \"@rreusser/gl-mat4\"","pinned":false,"hidden":false,"mode":"ojs"},{"id":828,"value":"import { mat3normalFromMat4 } from \"@rreusser/gl-mat3\"","pinned":false,"hidden":false,"mode":"ojs"},{"id":105,"value":"import {\n vec3transformMat4,\n vec3transformMat3,\n vec3add,\n vec3sub,\n vec3normalize,\n vec3dot,\n vec3scaleAndAdd,\n vec3mul\n} from \"@rreusser/gl-vec3\"","pinned":false,"hidden":false,"mode":"ojs"},{"id":1080,"value":"import { Scrubber } from \"@mbostock/scrubber\"","pinned":false,"hidden":false,"mode":"ojs"}],"files":"$W33","stdlib":"1","titling":"auto"}