http://danlucraft.com/blog/Nuclear Nutcracker2016-12-10T00:00:00ZDaniel Lucrafthttp://danlucraft.comtag:danlucraft.com,2016-12-10:/blog/blog/2016/12/3d-from-scratch-day-2/3D from Scratch - Day 22016-12-10T00:00:00Z2016-12-10T00:00:00Z<p><em>This is my attempt to figure out enough 3D graphics from scratch to clone the original Elite. The start of the series is here: <a href="/blog/2016/12/3d-from-scratch-intro/">3D from Scratch - Intro</a>.</em></p>
<h2 id="weird-cube-bug">Weird Cube Bug</h2>
<p>When I presented Day 1 at our work Breakfast Club this week, the first thing someone did is grab the controls and instantly find a bug. š </p>
<p>Here it is: if you move the cube directly towards the camera, at some point you see strange lines that cross the screen. And then if you keep moving the cube back, it reappears moving forward from again!</p>
<p><img src="/images/3fs/day-2-bug.gif" class="nofloat" alt="" /></p>
<p>So first I removed all but one edge of the cube, to get a clearer idea whats happening:</p>
<p><img src="/images/3fs/day-2-bug-reduced.gif" class="nofloat" alt="" /></p>
<p>And it seems that the points are transposed to the position that they would be in if I turned around, and turned upside down.</p>
<p>I think the lines that unaccountably cross the screen are just an artefact of this ā when one point is in normal view and one point is in upside-down-reverse view it still tries to draw a line between them.</p>
<p>That means I can remove all but one point to debug it:</p>
<p><img src="/images/3fs/day-2-bug-reduced-2.gif" class="nofloat" alt="" /></p>
<p>My normal debugging strategy at this point is to add a shit-ton of logging to everything, but first letās just look at the point drawing code and <em>think</em> about what it might be:</p>
<pre class="prettyprint"><code>function drawPoint3d(ctx, p) {
var x = Math.round(p.x * (screen_dist / p.z))
var y = Math.round(p.y * (screen_dist / p.z))
setPixel(ctx, x + PIXEL_WIDTH/2, y + PIXEL_HEIGHT/2)
}
</code></pre>
<p>First thing to notice is that <code>p.z</code> will turn negative when the point comes towards the camera and then passes it. That will make <em>x</em> and <em>y</em> negative too. The <em>x</em> value is then <em>subtracted</em> from <code>PIXEL_WIDTH/2</code> rather than added to it, which is why it appears reversed! Solved!</p>
<p>So the obvious thing to do is to add a guard that just bails on drawing the point if <code>p.z</code> is negative. That would probably work here, but in general it is quite possible to have one end of a line be behind the camera, and the other end in front of it, and still want to draw the line.</p>
<p>Also, the criteria as to whether a point is drawn or not is <em>not</em> actually whether itās behind the camera, but whether itās inside the cameraās view of the screen, and a point leaves that field of view well before <code>p.z</code> turns negative.</p>
<p>So to do this right Iāll have to figure out what appears in the field of view of the camera.</p>
<p>This has turned into a larger task than I was expecting.</p>
<h2 id="task-dont-display-things-not-in-the-cameras-field-of-view">Task: Donāt display things not in the cameraās field of view</h2>
<p>I knew this was going to be an issue eventually, so might as well get right into it. This was a bit tricky to figure out, I had to break out the old Maths textbooks and everything.</p>
<p>How to decide whether the camera can see something? Here are two diagrams I drew while thinking about this.</p>
<p>This one depicts a side view of the camera and screen, with two lines that do or do not appear in view:</p>
<p><img src="/images/3fs/day-2-crossing-view.jpg" class="nofloat" alt="" /></p>
<p>This one is my attempt to draw the camera, screen and field of view in 3d, again with one line that is not visible and one that is, partially:</p>
<p><img src="/images/3fs/day-2-crossing-view-3d.jpg" class="nofloat" alt="" /></p>
<p>After half an hour of staring at these diagrams, here are the observations I made:</p>
<ul>
<li>the field of view of the camera is a pyramid, with the apex centred on the camera. This space is defined as the interior of the shape formed by 4 planes, each of which contain the camera and two (different) corners of the screen.</li>
<li>a point is visible if it is on the inside of all four planes</li>
<li>a line with both points inside the field of view is entirely visible</li>
<li>a line with both points outside the field of view <em>may still be</em> partially visible <em>if</em> it intersects the field of view (the second line in both diagrams)</li>
<li>itās fairly easy to tell which side of a plane a point lies on, using Mathsā¦ so for any point you can tell if it is inside the field of view by checking it against the four planes and seeing if it is inside all of them.</li>
</ul>
<p>Now practically you could exclude from drawing any line that doesnāt have both ends inside the field of view. This is tempting as most things will be composed of many fairly short lines, and it is not common to fly right into thingsā¦</p>
<p>But this is not good enough in the long run, as there are real world cases where a line might cross the vision and you still want to draw itā¦ for instance you might be docking with a space station and only be able to see part of the docking port:</p>
<p><img src="/images/3fs/day-2-crossing-view-spaceport.jpg" class="nofloat" alt="" /></p>
<h2 id="subtask-dont-draw-a-line-with-either-end-offscreen">Subtask: donāt draw a line with either end offscreen</h2>
<p>However, itās a good first step, so thatās what Iām going to focus on first. (Only drawing a line if both ends are inside the field of view.)</p>
<p>Hereās where it gets mathsy. I had to look a bunch of this up but itās all coming back to me now. Maths concepts, with code:</p>
<p><strong>A plane</strong>. A plane can be defined as a single point (which is in that plane) and a single ānormalā vector, which is perpendicular to the plane. There are infinite points and vectors which work for this, so we will pick ones that make things easy for us.</p>
<p><img src="/images/3fs/day-2-plane-normal-rep.jpg" class="nofloat" alt="" /></p>
<p><strong>Dot product</strong>. This is the sort-of multiplication of two vectors to give a single number. It shows sort-of āhow much in the same direction they are but multipliedā. Vectors at right angles have a zero dot product, and as will become important in a moment, if two vectors are in opposite directions the dot product is negative. Itās written as <em>nā¢v</em> if <em>n</em> and <em>v</em> are vectors.</p>
<pre class="prettyprint"><code>// u and v are vectors with x,y,z components
function dot(u, v) {
return u[0]*v[0] + u[1]*v[1] + u[2]*v[2]
}
</code></pre>
<p><strong>Cross product</strong>. Taking the cross product of two vectors gives you another vector that is at right angles to the plane formed by them. </p>
<p><img src="/images/3fs/day-2-cross-product.jpg" alt="" /></p>
<p>Itās defined like this, donāt ask me why:</p>
<pre class="prettyprint"><code>function cross(u, v) {
return [
u[1]*v[2] - u[2]*v[1],
u[2]*v[0] - u[0]*v[2],
u[0]*v[1] - u[1]*v[0],
]
}
</code></pre>
<div style="clear:both;"></div>
<p>Now hereās the plan. Weāre going to:</p>
<ul>
<li>find normal vectors for the four planes that define the field of view, and in particular, theyāre going to be normal vectors that point āinwardsā towards the field of view, not ones that point āoutwardsā.</li>
<li>each normal vector will be calculated by taking the cross product of two vectors that we know are in the plane. In this case, thatās the two vectors from the camera to the corners of the screen.</li>
<li>for any point we care about, check which side of each of the four planes it is on.</li>
</ul>
<p>This is pictured in top-down view here (with only the two side planes):</p>
<p><img src="/images/3fs/day-2-point-in-field-of-view.jpg" class="nofloat" alt="" /></p>
<p>How do we tell which side of the planes the point is on? Well, this is what the dot product is for. Look at this next diagram. <em>p</em> and <em>q</em> are the normal vectors of the two planes. The vector <em>a</em> is to a point that is in view, and the vector <em>b</em> is to a point that is not.</p>
<p><img src="/images/3fs/day-2-point-in-field-of-view-simple.jpg" class="nofloat" alt="" /></p>
<p>The dot product of <em>a</em> with <em>p</em> will be positive, as they are both pointing inwards from the left plane. Same for <em>q</em>. So since the dot products are both positive, we know the point at <em>a</em> is in view.</p>
<p>The dot product of <em>b</em> with <em>p</em> will also be positive BUT the dot product of <em>b</em> with <em>q</em> is negative, as <em>b</em> and <em>q</em> are pointing different ways away from the plane on the right.</p>
<p>So you can see, if we take the dot products of the point with each of the four normals, we need them <em>all</em> to be positive to know that the point is in view.</p>
<p>Letās code that up. Here are the coordinates of the four corners of the screen:</p>
<pre class="prettyprint"><code>// clockwise from bottom right
var screen_coords = [
[ PIXEL_WIDTH/2, PIXEL_HEIGHT/2, screen_dist],
[-PIXEL_WIDTH/2, PIXEL_HEIGHT/2, screen_dist], // bottom left
[-PIXEL_WIDTH/2, -PIXEL_HEIGHT/2, screen_dist], // top left
[ PIXEL_WIDTH/2, -PIXEL_HEIGHT/2, screen_dist], // top right
]
</code></pre>
<p>And here are the inward-pointing normals. This is done by taking the cross product of two vectors in each plane to get a new vector at right angles to both of them, and because the camera is at (0,0,0) the points at the corners represent vectors straightaway. (I actually did these in the opposite order first, and that produced outward-pointing normals āĀ once I noticed it was the wrong way round I just flipped the order):</p>
<pre class="prettyprint"><code>var view_plane_normals = [
cross(screen_coords[0], screen_coords[1]), // bottom plane
cross(screen_coords[1], screen_coords[2]), // left plane
cross(screen_coords[2], screen_coords[3]), // top plane
cross(screen_coords[3], screen_coords[0]), // right plane
]
</code></pre>
<p>Now the code that actually checks if a point is in view. All it does is check that the dot product of the point with each normal is positive, as we discussed before:</p>
<pre class="prettyprint"><code>function isPointInView(p) {
for (var i = 0; i < view_plane_normals.length; i++)
if (dot([p.x, p.y, p.z], view_plane_normals[i]) < 0)
return false
return true
}
</code></pre>
<p>And now we can adjust <code>drawFrame</code> to not draw any line where both points are not in view:</p>
<pre class="prettyprint"><code> ...
if (isPointInView(newP1) && isPointInView(newP2))
drawLine3d(ctx, newP1, newP2)
...
</code></pre>
<p>And run it:</p>
<p><img src="/images/3fs/day-2-bug-fixed-1.gif" class="nofloat" alt="" /></p>
<p>And that looks much better! Our weird bug is fixed, and you can see it is correctly removing any line with an end offscreen.</p>
<h2 id="subtask-draw-the-part-of-the-line-that-appears-onscreen">Subtask: Draw the part of the line that appears onscreen</h2>
<p>However, you can now see that we are having lines disappear when they should still be partially visible. This means that when we have a line that has one or both ends offscreen, we should figure out <em>exactly</em> what part of it is visible and draw that.</p>
<p>Itās clear that weāre going to need a way to compute the intersection of a line with a plane, to be able to figure out exactly the point on the edge of the view to draw the lines from and to. For instance, in this diagram the line goes across the view so we need to know the two intersection points with the left and right side of the view:</p>
<p><img src="/images/3fs/day-2-line-crosses-view.jpg" class="nofloat" alt="" /></p>
<p>So first letās figure out how to do that. /Daunting</p>
<p>Every so often in this series, Iām going to say something like ā<em>and then I sat and stared into space for three solid hours</em>ā. This is one of those times.</p>
<p>Hereās what I came up with. </p>
<p><strong>Representation of the line</strong>. What we have is two points <em>p = (a,b,c)</em> and <em>q = (d,e,f)</em> that are the start and the end of the line (these are the corners of the cube). The line runs from one point to the other. So the representation of the line is as the three equations:</p>
<ul>
<li><em>x = a + t(d-a)</em>, </li>
<li><em>y = b + t(e-b)</em>, </li>
<li><em>z = c + t(f-c)</em>. </li>
</ul>
<p>This is called the <strong>parametric representation</strong>. <em>t</em> runs from zero to one and is āthe proportion we are along from one end to the otherā. To see that these are the right equations, notice how when <em>t = 0</em> that <em>x</em>, <em>y</em> and <em>z</em> are just <em>a</em>, <em>b</em> and <em>c</em>, and when <em>t = 1</em> they are <em>d</em>, <em>e</em>, <em>f</em>. So the ends are right. And since the equations are linear they describe a straight line, no curving going on. So if the ends are right and the line is straight this must be the right equations.</p>
<p><strong>Representation of the plane</strong>. Now, there are <em>three</em> ways to represent a plane. One is the <strong>normal vector and point</strong> representation we already discussed. One is a <strong>parametric representation</strong>, but using three points in the plane and <em>two</em> variables instead of one. And one is the <strong>equation of the plane</strong>: <em>ax + by + cz = d</em></p>
<p>Now I could see how to find the intersection point by plugging the equations of the parametric representation of the line into the equation of the plane. </p>
<p>However, we donāt actually have the equation of the plane. What we have is the parametric representation. And blowed if I could figure out how to go from one to the other.</p>
<p>Iām afraid I had to look this up (Iām allowed to look up maths, though Iām trying not to). Once I had, it seems so obvious and Iām a bit annoyed at myself for not figuring this out.</p>
<p>We actually have two representations of the plane already, the parametric representation and the normal & point representation. And going from the normal & point representation to the equation of the plane is really easy.</p>
<p>What does every vector in the plane have in common? They are all at right angles to the planeās normal vector. And we said earlier that the dot product of two vectors at right angles is zero. Therefore, if <em>v</em> is a vector in the plane, and <em>n</em> is the plane normal, <em>nā¢v = 0</em>.</p>
<p>From this we can get the equation of the plane. Letās pick a point in the plane <em>p = (a, b, c)</em>. For all points <em>q = (x, y, z)</em>, the vector <em>q - p</em> is in the plane if and only if <em>n ā¢(q-p) = 0.</em> If <em>n=(n,m,o)</em> then by the definition of the dot product this gives us an equation of the plane <em>n(x-a) + m(y-b) + o(z-c) = 0</em></p>
<p>This is even easier in our case, because the camera is in all our planes, and the camera is at <em>(0,0,0)</em>, we can just use that point as our <em>p</em> and the equation is just <em>nx + my + oz = 0</em>.</p>
<p>So now we can work out an formula for <em>t</em> that we can use to give us the intersection point of a line and a plane, by substituting the parametric representation of the line into the equation of the plane. Hereās my derivation, with different constant names:</p>
<p><img src="/images/3fs/day-2-intersection-formula-derivation.jpg" class="nofloat" alt="" /></p>
<p>And hereās the code for it:</p>
<pre class="prettyprint"><code>// takes two points that define a line and a plane normal
// and returns where the line intersects the plane
// (assumes (0,0,0) is in the plane)
function linePlaneIntersection(p, q, n) {
var v = [q.x - p.x, q.y - p.y, q.z - p.z]
var t = -1*(n[0]*p.x + n[1]*p.y + n[2]*p.z) /
(n[0]*v[0] + n[1]*v[1] + n[2]*v[2])
if (t < 0 || t > 1)
return null
return {x: p.x + t*v[0], y: p.y + t*v[1], z: p.z + t*v[2]}
}
</code></pre>
<p><strong>Clamping the line to the view</strong></p>
<p>Ok! Now we know how to compute intersections, we are very close to being able to truncate the lines by finding their intersection points with the viewplanes! Problem is, how do we know which planes to compute the intersections of the line with?</p>
<p>There are quite a few cases here depending on where the line starts and finishes, and indeed I spent quite a long time drawing lines across squares to try to figure out a neat way of figuring out exactly which planes the lines will intersect with.</p>
<p><img src="/images/3fs/day-2-plane-intersection-scribblings.jpg" class="nofloat" alt="" /></p>
<p>This went nowhere, because of the case where the line goes from the top offscreen to the side offscreen. This might or might not intersect the view depending on the exact start and end points:</p>
<p><img src="/images/3fs/day-2-plane-intersection-scribbling-detail.jpg" class="nofloat" alt="" /></p>
<p>So then I thought, letās just brute force it: for any line, collect <em>all</em> the points of intersection with the planes that define the view, and then just pick whichever two are visible (a point on the exact edge of the view weāll define as visible). And if none are visible, then the line doesnāt intersect the view.</p>
<p><img src="/images/3fs/day-2-brute-force-illustration.jpg" class="nofloat" alt="" /></p>
<p>And if one end of the line is visible to begin with, then you only need one of those points of intersection to be visible.</p>
<p>So, that gives us a plan, and we can code it up. This function returns false if none of the line is visible, and otherwise returns the two points that define the part of the line that <em>is</em> visible:</p>
<pre class="prettyprint"><code>// Returns false if the line between p and q is not
// visible at all. If it is, returns the points for the
// part of the line that is visible.
function clampLineToView(p, q) {
var p_in = isPointInView(p)
var q_in = isPointInView(q)
// if both visible, we're done
if (p_in && q_in)
return [p, q]
// we need two visible endpoints. Include p or q
// if either of them is visible
var visible_a = p_in ? p : (q_in ? q : null)
var visible_b = null
// now find the intersections and keep going until we
// have two visible points
for (var i = 0; i < view_plane_normals.length; i++) {
var ip = linePlaneIntersection(p, q, view_plane_normals[i])
if (ip && isPointInView(ip)) {
if (visible_a == null) {
visible_a = ip
} else if (visible_b == null) {
visible_b = ip
break
}
}
}
// if we have found two visible points, return them,
// otherwise return false, meaning none of the line
// is visible.
if (visible_a != null && visible_b != null)
return [visible_a, visible_b]
else
return false
}
</code></pre>
<p>To demo this Iāve done a few things. First I moved the edges of the view inwards a few pixels so we can see the lines vanish (otherwise Iād never be sure if it wasnāt getting the visible portion wrong but just drawing it off canvas):</p>
<pre class="prettyprint"><code>// clockwise from bottom right
var screen_coords = [
[ PIXEL_WIDTH/2 - 15, PIXEL_HEIGHT/2 - 15, screen_dist], // bottom rt
[-PIXEL_WIDTH/2 + 15, PIXEL_HEIGHT/2 - 15, screen_dist], // bottom left
[-PIXEL_WIDTH/2 + 15, -PIXEL_HEIGHT/2 + 15, screen_dist], // top left
[ PIXEL_WIDTH/2 - 15, -PIXEL_HEIGHT/2 + 15, screen_dist], // top right
]
</code></pre>
<p>Then change <code>drawFrame</code> again to only draw the right part of the line, and to draw the intersection points too so we can see it clearly:</p>
<pre class="prettyprint"><code> ā¦
// draw edges
for (var j = 0; j < edges.length; j++) {
var p1 = cube[edges[j][0]]
var p2 = cube[edges[j][1]]
var newP1 = {x: p1.x + transform.x, y: p1.y + transform.y, z: p1.z + transform.z}
var newP2 = {x: p2.x + transform.x, y: p2.y + transform.y, z: p2.z + transform.z}
var clampedLine = clampLineToView(newP1, newP2)
if (clampedLine) {
ctx.fillStyle = "blue"
drawLine3d(ctx, clampedLine[0], clampedLine[1])
ctx.fillStyle = "red"
drawPoint3d(ctx, clampedLine[0])
drawPoint3d(ctx, clampedLine[1])
}
}
ā¦
</code></pre>
<p>And now to run it and seeā¦</p>
<p><img src="/images/3fs/day-2-trim-lines-with-flickering.gif" class="nofloat" alt="" /></p>
<p>And that shows clearly that the lines are being truncated only to the visible portion!</p>
<h2 id="bug-flickering-lines">Bug: flickering lines</h2>
<p>However, we do have a bug here. The truncated lines sometimes flicker as they move. I made another video so it was clear:</p>
<p><img src="/images/3fs/day-2-flickering-lines.gif" class="nofloat" alt="" /></p>
<p>This is very strange.</p>
<p>The debugging process was to remove all but one line, and add logging extensively until it became clear what was going on.</p>
<p>If you open up the JavaScript console and run this calculation:</p>
<p><img src="/images/3fs/day-2-javascript-calculation.png" class="nofloat" alt="" /></p>
<p>thereās a chance that instead of getting <code>27.45</code> as your answer, youāll in fact get <code>27.4500000000003</code>. This is because floating point calculations that look as though they should be precise to us humans can have drift due to representational inaccuracies. In fact on my other laptop this was happening consistently, but not here, so I guess itās due to system specific stuff exactly when this happens.</p>
<p>The problem is that our <code>isPointInView</code> function compares the value of the dot product against 0. And the intersection points weāve been calculating are actually on the planes in question, so the dot product is often exactly 0 when this function is called. So a slight inaccuracy in the value of the coordinate is enough to render the point not visible when it is in fact on the plane.</p>
<p>The line flickers because this inaccuracy only occurs some of the time, again based on system specific factors.</p>
<p>Thereās probably a better way of doing this, but Iāve fixed it by adding a fudge factor to the comparison in <code>isPointOfView</code>:</p>
<pre class="prettyprint"><code>function isPointInView(p) {
for (var i = 0; i < view_plane_normals.length; i++)
if (dot([p.x, p.y, p.z], view_plane_normals[i]) < -0.001)
return false
return true
}
</code></pre>
<p>And the result, no flickering!</p>
<p><img src="/images/3fs/day-2-no-flickering.gif" class="nofloat" alt="" /></p>
<h2 id="conclusion">Conclusion</h2>
<p>Now Iāve got this all working, Iāve removed the extra space, and the drawing of the intersection and corner points to show what we should really see:</p>
<p><img src="/images/3fs/day-2-conclusion.gif" class="nofloat" alt="" /></p>
<p>And thatās it! This looks very similar to yesterdayās final demo, and indeed if the cube stays within the view it is <em>identical</em>. But although you canāt see it, it is properly not drawing lines that it canāt see.</p>
<p>So, there are two things that still bug me about todays work:</p>
<ol>
<li>computing the intersection of every line with every plane. If we assume there are going to be many many lines in the simulation, this might add up to a lot of work. I have an idea how to optimize this if need be though.</li>
<li>the assumption that the camera is at <em>(0,0,0)</em>. This has been very handy but Iām starting to suspect that weāre going to have to move the camera eventually (as opposed to moving the <em>entire rest of the world</em>), which means revisiting some of these formulae.</li>
</ol>
<p>But, for now, itās all working, so letās press on and come back to these when we have to!</p>
<ul>
<li><a href="https://github.com/danlucraft/3d-from-scratch/blob/master/src/day2.js">Source code</a></li>
<li><a href="/3d-from-scratch/demos/day2.html">Demo</a></li>
</ul>
<p>On to <a href="/blog/2016/12/3d-from-scratch-day-3/">Day Three</a>ā¦</p>
tag:danlucraft.com,2016-12-10:/blog/blog/2016/12/3d-from-scratch-day-3/3D from Scratch Day 3 - TypeScript, Refactoring, more Cubes!2016-12-10T00:00:00Z2016-12-10T00:00:00Z<p><em>This is my attempt to figure out enough 3D graphics from scratch to clone the original Elite. The start of the series is here: <a href="/blog/2016/12/3d-from-scratch-intro/">3D from Scratch - Intro</a>.</em></p>
<p>Some smaller bits and bobs today.</p>
<h2 id="fixes-for-chrome-firefox">Fixes for Chrome, Firefox</h2>
<p>The demos only worked in Safari, because Safari does stuff weirdly and Iād coded for that weirdness (Iām a Safari user). In particular this code doesnāt work in Chrome or Firefox:</p>
<pre class="prettyprint"><code>document.addEventListener('keydown', function(e) {
if (e.keyIdentifier == "Up")
keyState.up = true
...
}
</code></pre>
<p>This is because <code>keyIdentifier</code> is not standard, itās only in Safari. And <code>"Up"</code> is not standard, in Chrome and Firefox itās <code>"ArrowUp"</code>. </p>
<p>So to make this code portable Iāve changed it to:</p>
<pre class="prettyprint"><code>document.addEventListener('keydown', function(e) {
var keyName = e.key || e.keyIdentifier
if (keyName == "ArrowUp" || keyName == "Up")
keyState.up = true
...
}
</code></pre>
<p>Iāve also gone back and changed this code in the Day 1 and Day 2 demos.</p>
<h2 id="typescript">TypeScript</h2>
<p>Iāve ported the code to TypeScript because I wanted to try out the language and it changes almost nothing except give me better error messages. It was basically trivial to do so.</p>
<p>Step one was just to create a few types:</p>
<pre class="prettyprint"><code>interface Point {
x: number,
y: number,
z: number
}
type Vector = number[]
</code></pre>
<p>And then to update function signatures like so:</p>
<pre class="prettyprint"><code>function setPixel(ctx, x, y)
function setPixel(ctx: CanvasRenderingContext2D, x: number, y: number): void
function linePlaneIntersection(p, q, n)
function linePlaneIntersection(p: Point, q: Point, n: Vector): Point
</code></pre>
<p>There werenāt a ton of surprises here, it all just worked straight away (and didnāt miraculously surface any bugs ā¦ though I suppose it is only a 350 line file).</p>
<p>One annoyance is that the built in type definitions for the <code>KeyboardEvent</code> didnāt take Safari into account, so this code I just mentioned raised a TypeScript error saying that <code>keyIdentifier</code> wasnāt a thing.</p>
<pre class="prettyprint"><code> var keyName = e.key || e.keyIdentifier
</code></pre>
<p>This isnāt a great sign for TypeScript, really, as Iād like to be able to write portable code in it (I know Safari is in the wrong here but really TypeScript should take that into account in its type definitions).</p>
<p>I didnāt see an obvious way to fix this (say by adding to the built-in type definition) so I just did this to make it work:</p>
<pre class="prettyprint"><code> var keyName = e.key || e["keyIdentifier"]
</code></pre>
<p>One neat thing was using TypeScript destructuring to replace the long-winded variable swapping code in the <code>drawLine</code> function:</p>
<pre class="prettyprint"><code> // old
if (x2 < x1) {
var xt = x1
var yt = y1
x1 = x2
y1 = y2
x2 = xt
y2 = yt
}
// new
if (x2 < x1) {
[x1, x2, y1, y2] = [x2, x1, y2, y1]
}
</code></pre>
<p>As to the performance of this, is it making two new arrays on each invocation?? Or is it smart enough not to? The generated javascript is this:</p>
<pre class="prettyprint"><code>if (x2 < x1) {
_b = [x2, x1, y2, y1], x1 = _b[0], x2 = _b[1], y1 = _b[2], y2 = _b[3];
}
</code></pre>
<p>So it is creating <em>one</em> new array each time. Are the JavaScript VMs smart enough to optimize that object creation away, seeing that it is only used on that one line? Who knowsā¦.</p>
<h2 id="refactoring">Refactoring</h2>
<p>Writing down the exact types of things made me feel a little uncomfortable that I was slinging around Arrays for Vectors, Objects (with x,y,z fields) for Points, and separate x and y variables for 2D points! So Iāve refactored to make them all objects with classes:</p>
<pre class="prettyprint"><code>class Point2D {
constructor(public x: number, public y: number) {}
}
class Point {
constructor(public x: number, public y: number, public z: number) {}
}
class Vector {
constructor(public x: number, public y: number, public z: number) {}
}
</code></pre>
<p>So for instance the <code>drawLine</code> function signature has changed like this:</p>
<pre class="prettyprint"><code>function drawLine(ctx: CanvasRenderingContext2D, x1: number, y1: number, x2: number, y2: number)
function drawLine(ctx: CanvasRenderingContext2D, p: Point2D, q: Point2D): void
</code></pre>
<p>and the <code>dot</code> function like this:</p>
<pre class="prettyprint"><code>function dot(u: number[], v: number[]) {
return u[0]*v[0] + u[1]*v[1] + u[2]*v[2]
}
function dot(u: Vector, v: Vector): number {
return u.x*v.x + u.y*v.y + u.z*v.z
}
</code></pre>
<p>Itās worth noting that thereās absolutely nothing in TypeScript that stops you passing in a Vector or Point to an argument of type Point2D, as all that is required is that the object have both an <code>x</code> and a <code>y</code> field.</p>
<p>For instance, this is valid code even though <code>cross</code> takes two Vectors not two points, because Points and Vectors have identical fields:</p>
<pre class="prettyprint"><code>cross(new Point(1, 2, 3), new Point(4, 5, 6))
</code></pre>
<p>This is the principle of āduck typingā, that says that as long as an object fulfils the interface it doesnāt have to be of the same type. Usually I like this, but in the case of this project I was really hoping for a bit more type safety around when I wasĀ using a Point versus a Vector.</p>
<p>However, as soon as the Point and Vector classes diverge with unique properties of their own, I will get this. Itās just that at the moment they are identical so I donāt.</p>
<p><strong>We probably canāt keep it.</strong> Although all these objects make the code lovely indeedā¦ we may have to undo it all later. This is because I foresee a time when weāll want to represent all our data as much as possible as arrays of bytes ā JavaScript VMs are optimised to operate on that kind of thing <em>very</em> fast and weāre probably going to need the speed.</p>
<h2 id="clearrect">ClearRect</h2>
<p>I changed how it was clearing the frame to black from this:</p>
<pre class="prettyprint"><code>ctx.fillStyle = "black"
ctx.fillRect(0, 0, PIXEL_WIDTH*pixel_size, PIXEL_HEIGHT*pixel_size)
</code></pre>
<p>to this:</p>
<pre class="prettyprint"><code>ctx.clearRect(0, 0, PIXEL_WIDTH*pixel_size, PIXEL_HEIGHT*pixel_size)
</code></pre>
<p>as I read someplace that it was faster. This also required the canvas background colour to be black, which it was already.</p>
<h2 id="performance-info">Performance Info</h2>
<p>I wanted to have some info dumped on frame rate and how much time we were using to render the frames, so I added this code, which should be fairly self-explanatory:</p>
<pre class="prettyprint"><code>var PERF_INFO_FRAMES = 100
// clear perf info after displaying it
function resetPerfInfo(perfInfo) {
perfInfo.lastCalcUpdateTime = Date.now()
perfInfo.frameCounter = 0
perfInfo.elapsedTimeInFunction = 0
}
// update after every frame
function updatePerfInfo(perfInfo, funcStartTime) {
perfInfo.elapsedTimeInFunction += Date.now() - funcStartTime
perfInfo.frameCounter++
// after every PERF_INFO_FRAMES frames, dump performance info
if (perfInfo.frameCounter == PERF_INFO_FRAMES) {
var timeSinceLast = Date.now() - perfInfo.lastCalcUpdateTime
var frameRate = Math.round(1000*10*PERF_INFO_FRAMES/timeSinceLast)/10
var runtimePercentage = perfInfo.elapsedTimeInFunction / (Date.now() - perfInfo.lastCalcUpdateTime)
console.log({
frameRate: frameRate,
timeBudgetUsed: Math.round(runtimePercentage*1000)/10 + "%"
})
resetPerfInfo(perfInfo)
}
}
</code></pre>
<p>And called it at the start and end of the drawFrame:</p>
<pre class="prettyprint"><code>// set up data structure
var perfInfo = {}
resetPerfInfo(perfInfo)
function drawFrame(): void {
var funcStartTime = Date.now()
ā¦
updatePerfInfo(perfInfo, funcStartTime)
}
</code></pre>
<p>This gives us nice messages in the console like this that tell us what frame rate we are getting and how much of our ātime budgetā (the amount of time between each frame) we are using up:</p>
<pre class="prettyprint"><code>{frameRate: 60, timeBudgetUsed: "5.2%"}
{frameRate: 60, timeBudgetUsed: "5.1%"}
{frameRate: 60, timeBudgetUsed: "5.7%"}
{frameRate: 60, timeBudgetUsed: "4.9%"}
</code></pre>
<p>5% is quite high considering we are only animating one cube! This includes a mixed bag of computing intersections, calculating perspective, and filling in all those little squares in the canvas. Maybe later we will analyse that in more depth to see where the time is going. For now, onwards!</p>
<h2 id="more-cubes">More Cubes!</h2>
<p>I decided I was bored with the single blue cube demo so I added some more cubes! I had to at last encapsulate the cube vertices and edges into a Model class. I rebased the cube vertices to make 0 the centre of the cube rather than it being offset by 100 into the world.</p>
<pre class="prettyprint"><code>class Model {
constructor(public vertices: Point[], public edges: Edge[]) {}
}
type Edge = number[]
var cubeModel = new Model(
[
new Point(50, 50, 50),
new Point(50, 50, -50),
new Point(50, -50, 50),
new Point(-50, 50, 50),
new Point(50, -50, -50),
new Point(-50, 50, -50),
new Point(-50, -50, 50),
new Point(-50, -50, -50),
],
[
[0, 1],
[0, 2],
[0, 3],
[1, 4],
[1, 5],
[2, 4],
[2, 6],
[3, 5],
[3, 6],
[4, 7],
[5, 7],
[6, 7],
]
)
</code></pre>
<p>Then each cube that exists in the world is an āInstanceā of this Model, containing a reference to the model and a location of the object:</p>
<pre class="prettyprint"><code>class Instance {
constructor(public model: Model, public location: Point) {}
}
</code></pre>
<p>Then creating an array that contains all the many many cubes there now are:</p>
<pre class="prettyprint"><code>var objects: Instance[] = [
new Instance(cubeModel, new Point(0, 0, 400)),
new Instance(cubeModel, new Point(150, 0, 500)),
...
new Instance(cubeModel, new Point(-150, +300, 500)),
new Instance(cubeModel, new Point(-300, +300, 500)),
]
</code></pre>
<p>And rewriting drawFrame to draw the edges of the objects based on this array:</p>
<pre class="prettyprint"><code> // draw edges
ctx.fillStyle = "yellow"
for (var i = 0; i < objects.length; i++) {
var object = objects[i]
for (var j = 0; j < object.model.edges.length; j++) {
var p1 = object.model.vertices[object.model.edges[j][0]]
var p2 = object.model.vertices[object.model.edges[j][1]]
var loc = object.location
var newP1 = new Point(p1.x + loc.x + transform.x, p1.y + loc.y + transform.y, p1.z + loc.z + transform.z)
var newP2 = new Point(p2.x + loc.x + transform.x, p2.y + loc.y + transform.y, p2.z + loc.z + transform.z)
var clampedLine = clampLineToView(newP1, newP2)
if (clampedLine)
drawLine3d(ctx, clampedLine[0], clampedLine[1])
}
}
</code></pre>
<p>Andā¦.</p>
<p><img src="/images/3fs/day-3-demo.gif" class="nofloat" alt="" /></p>
<p>Nice!</p>
<h2 id="conclusion">Conclusion</h2>
<p>Pretty happy with all that. TypeScript I will keep I think, as it seems to provide a level of certainty about my JavaScript that I really appreciate. There were a few times I used the āRename symbolā option in VSCode and it worked perfectly, which is very cool.</p>
<ul>
<li><a href="https://github.com/danlucraft/3d-from-scratch/blob/master/src/day3.ts">Day 3 Source code</a></li>
<li><a href="/3d-from-scratch/demos/day3.html">Demo</a></li>
</ul>
<p>Day 4 I have some technical screen size issues to sort out. Not glamorous but Iāve been lax about things so want to get things fixed before moving on.</p>
tag:danlucraft.com,2016-12-04:/blog/blog/2016/12/3d-from-scratch-day-1/3D from Scratch - Day 12016-12-04T00:00:00Z2016-12-04T00:00:00Z<p><em>First day of seeing if I can figure out retro 3d graphics from scratch.</em> (To catch up on this series, go <a href="/blog/2016/12/3d-from-scratch-intro/">here</a>.)</p>
<p>My task for today: <strong>Ā make a wireframe cube that I can move around with the cursor keys. In 3D.</strong></p>
<p>This is going to be a test to see whether this is a remotely plausible project. Because if I canāt figure this out, Iāve got no hope for the rest of itā¦</p>
<h2 id="cube">CUBE!</h2>
<p>Preliminary setup. The HTML file, with text if Canvas isnāt supported in the userās browser:</p>
<pre class="prettyprint"><code><canvas>Too bad.</canvas>
</code></pre>
<p>And the size our screen is going to be (for now):</p>
<pre class="prettyprint"><code>// Our retro "screen" resolution
var PIXEL_WIDTH = 160
var PIXEL_HEIGHT = 120
</code></pre>
<h3 id="step-1-make-a-screen-of-pixels-using-canvas">Step 1: Make a screen of pixels using Canvas</h3>
<p>First job is figure out how to use Canvas in such a way that it seems as though itās a simple screen of (huge) pixels. This is harder than you might think, for two reasons:</p>
<ol>
<li>Every Canvas drawing function is anti-aliased, and bugger if I can figure out how to turn that off. I donāt think itās possible.</li>
<li>Even if I could turn it off, the pixels on a modern screen are tiiiiiny. Thereās no setting in canvas called āset pixel size = 10ā or anything like that.</li>
</ol>
<p>Now I had a few options here, and Iāve gone ahead and chosen the worst. But also the fastest to get up and running. Iāll revisit it later. </p>
<p>That is: Iāll use the canvas <code>fillRect</code> function to draw little squares where the pixels should be. Onwards!</p>
<pre class="prettyprint"><code>// Actual space we can use in the browser window
var WIN_WIDTH = window.innerWidth
var WIN_HEIGHT = window.innerHeight
// Calculate how big we can make the virtual pixels
// (In whole numbers, can't have our virtual pixel be 2.5
// real pixels, that would look terrible)
var ratio_width = WIN_WIDTH / PIXEL_WIDTH
var ratio_height = WIN_HEIGHT / PIXEL_HEIGHT
var pixel_size = Math.floor(Math.min(ratio_width, ratio_height))
// Resize the canvas
var canvas = document.getElementById("canvas")
canvas.width = PIXEL_WIDTH * pixel_size
canvas.height = PIXEL_HEIGHT * pixel_size
// Get the context, which is where you do all the actual drawing
var ctx = canvas.getContext("2d")
// Make it a black screen
ctx.fillStyle = "black"
ctx.fillRect(0, 0, PIXEL_WIDTH*pixel_size, '' PIXEL_HEIGHT*pixel_size)
// function to set a pixel (to the colour set with fillStyle)
function setPixel(ctx, x, y) {
if (x > 0 && x < PIXEL_WIDTH && y > 0 && y < PIXEL_HEIGHT)
ctx.fillRect(x*pixel_size, y*pixel_size, pixel_size, pixel_size)
}
</code></pre>
<p>That looks good. And a little demo to check it works right:</p>
<pre class="prettyprint"><code>ctx.fillStyle = "white"
for (var x = 0; x < PIXEL_WIDTH; x++) {
setPixel(ctx, x, Math.floor(30*Math.sin(x/10)) + 55)
}
</code></pre>
<p><img src="/images/3fs/day-1-sine.png" class="nofloat" alt="" /></p>
<p>Suitably retro. OK, we have our screen.</p>
<h3 id="step-2-draw-the-points-of-the-cube">Step 2: Draw the points of the cube</h3>
<p>OK, letās get straight in there and draw the corners of the cube as single pixels, in 3D.</p>
<p>Mental visualisation. Iām here, floating in space, looking straight ahead. Thereās a cube hovering in front of me. How do I turn all that into a 2D screen?</p>
<p>After some thought, Iāve decided that this mental visualisation has to include the screen as well, as a flat rectangle hovering directly in front of me, between me and the cube. You can then find the location of any point on the cube on the screen, by drawing a line from the my eye to the point on the cube, and marking where exactly it intersects the screen.</p>
<p>This makes the picture on the screen the projection of the cube. I recall projection being a thing from Maths. </p>
<p>Terrible diagram of this (the first of many):</p>
<p><img src="/images/3fs/day-1-3d-projection.jpg" class="nofloat" alt="" /></p>
<p>Iām not a fan of trigonometry, but I think if you threw enough of it at this, you could figure out the locations of the points on the screen in pixels.</p>
<p>But Iām a bit at a loss as how to code this straight away, so letās simplify by tossing out the <em>x</em>-axis and just considering one point to start with. </p>
<p>To make things as easy as possible, Iām going to assume that the camera is at <em>(0, 0, 0)</em>, that it is lookingā¦ upā¦ the <em>z</em>-axis, and that the screen is <em>a</em>ā¦ unitsā¦ up the <em>z</em>-axis, and that the cube is <em>b</em> units up the <em>z</em>-axis, and has ā¦ <em>2c</em> units to a side. (Can you tell Iām making this up as I go along?)</p>
<p>This means that the <em>x</em> and <em>y</em> axes of the screen are aligned with the <em>x</em> and <em>y</em> axes of the space itās floating in, again to simplify things. That the centre point of the screen is _x = 0, y = 0, z = a.</p>
<p>That gives me this diagram:</p>
<p><img src="/images/3fs/day-1-2d-projection.jpg" class="nofloat" alt="" /></p>
<p>Now to draw the point on the screen, I need to know the <em>y</em> pixel coordinate, which is marked as <em>yā</em>. (Weāre forgetting about <em>x</em> coordinate for a minute.)</p>
<p>The <em>y</em> coordinate of the pixel is something like <em>c</em>, but a bit less because of the perspective.</p>
<p>If I redraw that highlighting the triangle formed by the camera location, the point in 3D space, and the midpoint of the cube line, it becomes easy to see how to derive <em>yā</em>:</p>
<p><img src="/images/3fs/day-1-2d-projection-triangle.jpg" class="nofloat" alt="" /></p>
<p>Because itās a right-angled triangle, the value of <em>yā</em> is proportional to <em>c</em> in the same ratio as the distance that the screen is along the base of the triangle. In other words, <em>yā = c(a/b)</em>. And thatās our screen coordinate!</p>
<p>And this works exactly the same in both the <em>x</em>-axis and the <em>y</em>-axis! (You can imagine the diagram with <em>x</em>-axis in place of the <em>y</em>-axis and nothing changes.) That means we can calculate the pixel coordinates (of that single point) now:</p>
<pre class="prettyprint"><code>// cube corner, x and y are 'c' and z is 'b' in the diagram above
var p = {x:50, y:50, z:200}
// screen distance from camera is 'a' in the diagram above
var screen_dist = 100
var screen_coordinates = {
x: Math.round(p.x*screen_dist / p.z),
y: Math.round(p.y*screen_dist / p.z)
}
</code></pre>
<p>And letās draw it like this:</p>
<pre class="prettyprint"><code>ctx.fillStyle = "white"
setPixel(ctx, screen_coordinates.x, screen_coordinates.y)
</code></pre>
<p>Fingers crossedā¦</p>
<p><img src="/images/3fs/day-1-single-3d-point.png" class="nofloat" alt="" /></p>
<p>BOOM! A point! In 3D!</p>
<p>I mean I guess it looks like itās in about the right placeā¦ Lets draw the rest of the cube to see. First Iāll wrap up the point drawing code into a function, then draw the rest of the points.</p>
<pre class="prettyprint"><code>function drawPoint3d(ctx, p) {
var x = Math.round(p.x * (screen_dist / p.z))
var y = Math.round(p.y * (screen_dist / p.z))
setPixel(ctx, x, y)
}
var cube = [
{ x: 50, y: 50, z: 250},
{ x: 50, y: 50, z: 150},
{ x: 50, y: -50, z: 250},
{ x: -50, y: 50, z: 250},
{ x: 50, y: -50, z: 150},
{ x: -50, y: 50, z: 150},
{ x: -50, y: -50, z: 250},
{ x: -50, y: -50, z: 150}
]
ctx.fillStyle = "white"
for (var i = 0; i < cube.length; i++) {
drawPoint3d(ctx, cube[i])
}
</code></pre>
<p>And the result:</p>
<p><img src="/images/3fs/day-1-two-3d-points.png" class="nofloat" alt="" /></p>
<p>OK well that looks even more amazingly 3D than the last one!</p>
<p>Although itās obviously centered the cube at (0, 0) on the screenā¦ so letās make sure to translate that screen half way in both axes so that the centre of the screen is at x=0, y=0.</p>
<pre class="prettyprint"><code>function drawPoint3d(ctx, p) {
var x = Math.round(p.x * (screen_dist / p.z))
var y = Math.round(p.y * (screen_dist / p.z))
setPixel(ctx, x + PIXEL_WIDTH/2, y + PIXEL_HEIGHT/2)
}
</code></pre>
<p>And the result is very definitely a 3D cube!</p>
<p><img src="/images/3fs/day-1-cube-points.png" class="nofloat" alt="" /></p>
<p>And no trigonometry required at all. š</p>
<h3 id="step-3-move-the-cube-with-cursor-keys">Step 3: Move the cube with cursor keys</h3>
<p>OK I want to be able to move this baby around, really feel the 3D.</p>
<p>Shouldnāt be too hard, just need to hook into some JS key events and change the cube coordinates if the cursor keys are pressed.</p>
<p>First letās maintain the state of the cursor keys using JavaScript document events:</p>
<pre class="prettyprint"><code>var keyState = {
up: false,
down: false,
left: false,
right: false,
}
document.addEventListener('keydown', function(e) {
if (e.keyIdentifier == "Up") keyState.up = true
if (e.keyIdentifier == "Down") keyState.down = true
if (e.keyIdentifier == "Left") keyState.left = true
if (e.keyIdentifier == "Right") keyState.right = true
})
document.addEventListener('keyup', function(e) {
if (e.keyIdentifier == "Up") keyState.up = false
if (e.keyIdentifier == "Down") keyState.down = false
if (e.keyIdentifier == "Left") keyState.left = false
if (e.keyIdentifier == "Right") keyState.right = false
})
</code></pre>
<p>Now, if this is going to move about then Iām stepping into animation territory, which means I should switch to doing all my drawing inside a <code>window.requestAnimationFrame</code> call. (This allows the browser to call your function that draws a frame whenever it decides that it is time for a new frame to be drawn.)</p>
<p>Itās also going to have to keep track of where the cube is. I decided not to change the values of the coordinates in the cube points every time it moves, but just to keep track of the change in the points in a separate variable:</p>
<pre class="prettyprint"><code>var transform = {x: 0, y: 0, z: 0}
</code></pre>
<p>Now Iāll have a <code>drawFrame</code> function that <code>requestAnimationFrame</code> can call. It needs to clear the screen before it renders the points each frame, and update the transform if it detects that the keys are pressed.</p>
<p>Iāll only have it move in the <em>z</em> and <em>x</em> axes (as there are only four cursor keys).</p>
<pre class="prettyprint"><code>function drawFrame() {
// clear frame
ctx.fillStyle = "black"
ctx.fillRect(0, 0, PIXEL_WIDTH*pixel_size, PIXEL_HEIGHT*pixel_size)
// draw points
ctx.fillStyle = "white"
for (var i = 0; i < cube.length; i++) {
var p = cube[i]
// move point based on transform
var newP = {x: p.x + transform.x, y: p.y + transform.y, z: p.z + transform.z}
drawPoint3d(ctx, newP)
}
// update cube location
if (keyState.down) transform.z -= 10
if (keyState.up) transform.z += 10
if (keyState.left) transform.x -= 10
if (keyState.right) transform.x += 10
window.requestAnimationFrame(drawFrame)
}
// start the whole thing off:
window.requestAnimationFrame(drawFrame)
</code></pre>
<p>And that should do it!</p>
<p><img src="/images/3fs/day-1-cube-points-moving.gif" class="nofloat" alt="" /></p>
<h3 id="step-4-write-a-function-to-draw-lines">Step 4: Write a function to draw lines</h3>
<p>This is just a set of points floating around. To make it a real cube it needs to be wireframe, and that meansā¦ I have to figure out how to draw lines. To be honest Iāve been putting this off a little bit, because I have no idea how to do it, but itās clearly time now.</p>
<p>I spent quite a bit of time figuring this out, way longer than on the 3D point drawing. Iām not going to tell you all my errant thought processes here, so Iāll just show you a few lowlights.</p>
<p>The goal is to turn a platonic āperfectā line between two points into a set of illuminated pixels that approximate that line in a āniceā way (see the illustration below). The points at the start and end of the line are always at the exact centre of two pixels.</p>
<p>Now if you draw a few of these it becomes clear pretty quickly that sometimes it can be done more nicely than others. For instance line II in this diagram is a little unbalanced, and will appear a little curved on the screen, but there is just no way to do it better.</p>
<p><img src="/images/3fs/day-1-line-examples.jpg" class="nofloat" alt="" /></p>
<p><strong>Red Herring Number 1.</strong> First thing I did was get properly side-tracked into trying to create a recursive algorithm. The first line in the diagram above passes through the exact midpoint of a pixel in the middle of the line. Therefore you can decompose the problem into two around that midpoint, and recursively call your line drawing algorithm with those two halves. This seemed to me to be very promising.</p>
<p>The problem is thereās no way to do the same for line II (or none that I can see) because the line midpoint falls on the boundary between two pixels, so the sub-problems donāt obey the constraint of starting and ending at the centre of two pixels. And there are more cases like this. So this turned out to go nowhere.</p>
<p><strong>Solution</strong> Eventually I noticed that (for a line that runs with a steep slope downwards, like Line I and Line II in the diagram), for each row of pixels there is only one active. This led me to think about how you would pick which of the row to activate. The answer is to look at the horizontal line that passes through the midpoint of the row of pixels, and ask: in which pixel does the perfect line intersect this midpoint horizontal line? Hereās what that looks like:</p>
<p><img src="/images/3fs/day-1-line-choosing-pixels.jpg" class="nofloat" alt="" /></p>
<p>You can see that the intersections are in the correct pixels for this line.</p>
<p>Thatās pretty easy to code up (remember weāre assuming that the line slopes down and to the right severely). We step along the perfect line, increasing <em>y</em> by one each time and increasing <em>x</em> by the proportional amount. Itās the <code>Math.round</code> call thatās doing the work of selecting the pixel in the row:</p>
<pre class="prettyprint"><code>function drawLine(ctx, x1, y1, x2, y2) {
var x = x1
var y = y1
var slope = (x2 - x1) / (y2 - y1)
while (y <= y2) {
setPixel(ctx, Math.round(x), y)
y++
x += slope;
}
}
</code></pre>
<p>And a demo:</p>
<pre class="prettyprint"><code>// inside drawFrame
ctx.fillStyle = "yellow"
drawLine(ctx, 10, 10, 10, 50)
drawLine(ctx, 10, 10, 20, 50)
drawLine(ctx, 10, 10, 30, 50)
drawLine(ctx, 10, 10, 40, 50)
drawLine(ctx, 10, 10, 50, 50)
</code></pre>
<p><img src="/images/3fs/day-1-line-demo.png" class="nofloat" alt="" /></p>
<p>So that looks right. Now we need to consider the cases where the line <em>doesnāt</em> slope down and to the right like that.</p>
<p>First of all, thereās no reason that we have to consider lines that run from right to left. We can just swap the ends, and then for the rest of the function we are guaranteed they run from left to right:</p>
<pre class="prettyprint"><code>function drawLine(ctx, x1, y1, x2, y2) {
// ensure line from left to right
if (x2 < x1) {
var xt = x1
var yt = y1
x1 = x2
y1 = y2
x2 = xt
y2 = yt
}
...
</code></pre>
<p>Once weāve done that, there are four cases to consider. If we calculate the slope of the line as <em>s</em>, which is change in <em>x</em> over change in <em>y</em>:</p>
<pre class="prettyprint"><code>var s = (x2 - x1) / (y2 - y1)
</code></pre>
<p>Then the cases are:</p>
<p><img src="/images/3fs/day-1-line-cases.jpg" class="nofloat" alt="" /></p>
<p>For the two more horizontal cases, the algorithm steps along <em>x</em> one a time (instead of <em>y</em>) and looks to see which pixel in the <em>column</em> (instead of row) of pixels should be activated:</p>
<p><img src="/images/3fs/day-1-line-choosing-pixels-horiz.jpg" class="nofloat" alt="" /></p>
<p>Now we can code up those cases, very similar to the previous ones. The differences in each case are:</p>
<ul>
<li>whether it is <em>y</em> or <em>x</em> that is incremented at each step</li>
<li>if <em>y</em>, whether it is incremented or decremented (line goes down or up)</li>
<li>
<p>if we are scanning across columns (<em>x</em> is being incremented), then <em>y</em> needs to change by <em>1/s</em>, rather than s. This is because we expressed <em>s</em> as āchange in x per yā but now we need āchange in y per xā. </p>
<pre class="prettyprint"><code>if (s > 0 && s <= 1) {
while (y <= y2) {
setPixel(ctx, Math.round(x), y)
y++
x += s
}
} else if (s < 0 && s >= -1) {
while (y >= y2) {
setPixel(ctx, Math.round(x), y)
y--
x -= s
}
} else if (s < -1) {
while (x <= x2) {
setPixel(ctx, x, Math.round(y))
x++
y += 1/s
}
} else if (s > 1) {
while (x <= x2) {
setPixel(ctx, x, Math.round(y))
x++
y += 1/s
}
} }
</code></pre>
</li>
</ul>
<p>And try a demo with different colours for each of the four cases:</p>
<pre class="prettyprint"><code> ctx.fillStyle = "yellow"
drawLine(ctx, 10, 60, 10, 100)
drawLine(ctx, 10, 60, 20, 100)
drawLine(ctx, 10, 60, 30, 100)
drawLine(ctx, 10, 60, 40, 100)
drawLine(ctx, 10, 60, 50, 100)
ctx.fillStyle = "red"
drawLine(ctx, 10, 60, 10, 20)
drawLine(ctx, 10, 60, 20, 20)
drawLine(ctx, 10, 60, 30, 20)
drawLine(ctx, 10, 60, 40, 20)
drawLine(ctx, 10, 60, 50, 20)
ctx.fillStyle = "green"
drawLine(ctx, 10, 60, 50, 30)
drawLine(ctx, 10, 60, 50, 40)
drawLine(ctx, 10, 60, 50, 50)
drawLine(ctx, 10, 60, 50, 60)
ctx.fillStyle = "purple"
drawLine(ctx, 10, 60, 50, 70)
drawLine(ctx, 10, 60, 50, 80)
drawLine(ctx, 10, 60, 50, 90)
</code></pre>
<p><img src="/images/3fs/day-1-line-examples-missing.png" class="nofloat" alt="" /></p>
<p>Which looks pretty goodā¦ Except weāre missing the vertical lines.</p>
<p>This puzzled me a bit. In both upwards and downwards vertical lines the slope <em>s</em> is zero. The difference is that <em>s</em> is either <em>+0</em>, or <em>-0</em>. Of course you canāt distinguish those with an inequality condition, so we can just check whether the second <em>y</em> coordinate is bigger or lesser than the first. Adding that to the code:</p>
<pre class="prettyprint"><code> if ((s > 0 && s <= 1)) || (s == 0 && y2 > y1)) {
...
} else if ((s < 0 && s >= -1)) || (s == 0 && y2 < y1)) {
...
} else if (s < -1) {
...
} else if (s > 1) {
...
}
</code></pre>
<p>And bingo!</p>
<p><img src="/images/3fs/day-1-line-demo-all-cases.png" class="nofloat" alt="" /></p>
<h3 id="step-5-draw-the-wireframe-cube">Step 5: Draw the wireframe cube</h3>
<p>The line drawing seems to be working. Letās hook it up to the cube and win!</p>
<p>We need a description of which edges we want, which Iāve chosen to do in terms of which corners to go from and to. Here the numbers are indexes into the <code>cube</code> array of points from before:</p>
<pre class="prettyprint"><code>var edges = [
[0, 1],
[0, 2],
[0, 3],
[1, 4],
[1, 5],
[2, 4],
[2, 6],
[3, 5],
[3, 6],
[4, 7],
[5, 7],
[6, 7],
]
</code></pre>
<p>And hereās a function that copies the code from <code>drawPoint3d</code> that turns the 3D points into screen coordinates, and then just draws the line between them:</p>
<pre class="prettyprint"><code>function drawLine3d(ctx, p1, p2) {
var x1 = Math.round(p1.x * (screen_dist / p1.z))
var y1 = Math.round(p1.y * (screen_dist / p1.z))
var x2 = Math.round(p2.x * (screen_dist / p2.z))
var y2 = Math.round(p2.y * (screen_dist / p2.z))
drawLine(ctx, x1 + PIXEL_WIDTH/2, y1 + PIXEL_HEIGHT/2, x2 + PIXEL_WIDTH/2, y2 + PIXEL_HEIGHT/2)
}
</code></pre>
<p>And adding code to <code>drawFrame</code> to actually draw them from point to point, suitably transformed as before:</p>
<pre class="prettyprint"><code>for (var j = 0; j < edges.length; j++) {
var p1 = cube[edges[j][0]]
var p2 = cube[edges[j][1]]
ctx.fillStyle = "blue"
var newP1 = {x: p1.x + transform.x, y: p1.y + transform.y, z: p1.z + transform.z}
var newP2 = {x: p2.x + transform.x, y: p2.y + transform.y, z: p2.z + transform.z}
drawLine3d(ctx, newP1, newP2)
}
</code></pre>
<p>And run it:</p>
<p><img src="/images/3fs/day-1-final.gif" class="nofloat" alt="" /></p>
<p>And done!</p>
<h3 id="conclusion">Conclusion</h3>
<p>Pleased with the days work! Was not nearly as hard as I expected, so maybe I can do this šŖ</p>
<ul>
<li><a href="https://github.com/danlucraft/3d-from-scratch/blob/master/src/day1.js">Source code</a></li>
<li><a href="/3d-from-scratch/demos/day1.html">Demo</a></li>
</ul>
<p>On to <a href="/blog/2016/12/3d-from-scratch-day-2/">Day Two</a>ā¦</p>
tag:danlucraft.com,2016-12-03:/blog/blog/2016/12/3d-from-scratch-intro/3D from Scratch - Introduction2016-12-03T00:00:00Z2016-12-03T00:00:00Z<p><img src="/images/3fs/intro-goal.png" alt="This is where I want to end up" /></p>
<h2 id="new-project">New Project!</h2>
<p>Iām going to figure out enough about how 3D graphics and game programming work
to write a simple retro Elite-style game from scratch. But Iām <em>not</em> going look
at any graphics or game programming references or tutorials. The rule is Iāve
got to figure it all out myself.</p>
<p>To be clear: I have no idea how 3D graphics work. I have virtually no idea how
2D graphics work. I <em>am</em> pretty good with maths.</p>
<p>Iāll do it in JavaScript because I want to finish this century and because my
JavaScript knowledge is still a little jQuery-era and I want to brush up.</p>
<p>I <em>can</em> look at any JavaScript documentation I want, including the Canvas API.
But for the graphics programming Iāll treat HTML5 canvas entirely as a dumb
screen of pixels (step one is to figure out how to do this). This means no
OpenGL/WebGL either: all the 3D and rendering will be implemented in pure
JavaScript.</p>
<p>Also Iāll allow myself to look up generic Maths definitions and theorems,
otherwise it will take all year.</p>
<p>What will be in these posts will be all my reasoning as I work this stuff out,
including diagrams and full code (in a kind of a literate style). And Iāll
check in each dayās code in the repo.</p>
<p>It might not be pretty, but itās going to be a lot of fun.</p>
<h2 id="thoughts-on-javascript-as-the-implementation-language">Thoughts on JavaScript as the implementation language</h2>
<p>Again, Iām choosing this language because I donāt have much free time and I
want to make rapid progress.</p>
<p>Also, if it works I can eventually figure out how to deploy it anywhere. There
are many HTML/JS wrapper frameworks that I forget the names of that can deploy
to all platforms.</p>
<p>However Iām not entirely sure that JavaScript is fast enough to do this.
(Again, this is 3D graphics <em>without</em> OpenGL.) I wouldnāt even consider it
except that this is going to be very retro graphics style with something like a
320x200 resolution and wireframe or flat-shaded models.</p>
<p>When you compare to the hardware that Bell and Braben had in the early 80ās
when making Elite, it certainly <em>seems</em> as though the modern browser should be
able to compete.</p>
<p>And Iāve heard of people getting amazing performance out of the modern runtimes
(like emulating x86 CPUs with a fair speed!) so surely itās possible. And
learning how to optimize JavaScript is an interesting project in its own right.</p>
<p>A bigger worry is GC pause times for a realtime application. I know the V8 team
have done a bunch of work making the runtime prioritize live stuff. But what
about Safari? I donāt want to have jerky graphics. If necessary, learning how
to maintain object pools to keep GC minimal will also be a very interesting
project, and something Iāve wanted to try forever.</p>
<p>And finally I reserve the right to bail out into any other language at any time
if it turns out not to be possible or just too much work to be reasonable.</p>
<h2 id="where-to-start">Where to start</h2>
<p>First things first, how do we even do retro pixel graphics in HTML Canvas? And
then something very simple to test the watersā¦</p>
<h2 id="series-toc">Ā Series TOC</h2>
<ol>
<li><a href="/blog/2016/12/3d-from-scratch-day-1/">Day 1 - Screen and a Cube</a></li>
<li><a href="/blog/2016/12/3d-from-scratch-day-2/">Day 2 - Proper clipping</a></li>
<li><a href="/blog/2016/12/3d-from-scratch-day-3/">Day 3 - TypeScript, Refactoring, more Cubes</a></li>
</ol>
tag:danlucraft.com,2013-12-20:/blog/blog/2013/12/ann-simplex-for-ruby/Simplex for Ruby2013-12-20T00:00:00Z2013-12-20T00:00:00Z<p><em>Iāve released a <a href="https://github.com/danlucraft/simplex">pure-Ruby implementation of the Simplex algorithm</a>
for solving linear problems. It may be useful to you if you can only run Ruby, or if you want to learn about
the Simplex algorithm from a simple implementation.</em></p>
<p>I really really didnāt want to write my own LP solver implementation. If someone else told
me they had done this, I would smirk. Itās a notoriously hard algorithm to implement correctly. </p>
<p><img src="/images/2013/12/fsf-ship.png" alt="ship design example" />
My use case is allocating power through circuits to weapons and shields and things in imaginary
space ships (see right) created by users
in my web game (codenamed Fantasy Star Fleets). The optimal power allocation (given whichever
power cores and couplings have been blown up by enemy action at the present time) is a linear program.</p>
<p>The game runs on Heroku, which is a terrific time-saver. Have you tried compiling the āproā
LP solvers packages for Heroku? Have you tried compiling them on Heroku <em>for Ruby 2.0</em>?</p>
<p>I spent most of a day trying to make that work with various different solvers. Then I gave up and
spent an hour writing my own.</p>
<p>It works for me because the little space ships are little, so the problems are small. Plus they
are all of a very standard simple form, so there is no chance of degeneracy or hard things in general.</p>
<p>To solve the maximization in standard form (which is the only kind it can do atm):</p>
<pre class="prettyprint"><code>max x + y
2x + y <= 4
x + 2y <= 3
x, y >= 0
</code></pre>
<p>Do this:</p>
<pre class="prettyprint"><code>> simplex = Simplex.new(
[1, 1], # coefficients of objective function
[ # matrix of inequality coefficients on the lhs ...
[ 2, 1],
[ 1, 2],
],
[4, 3] # .. and the rhs of the inequalities
)
> simplex.solution
=> [(5/3), (2/3)]
</code></pre>
<p>Although it may not be of much practical use outside the restricted Heroku environment, Iāve tried to make
it clean and easy to learn from. You can run the algorithm step by step and inspect the tableau as you
go along:</p>
<pre class="prettyprint"><code>> simplex = Simplex.new([1, 1], [[2, 1], [1, 2]], [4, 3])
> puts simplex.formatted_tableau
-1.000 -1.000 0.000 0.000
----------------------------------------------
*2.000 1.000 1.000 0.000 | 4.000
1.000 2.000 0.000 1.000 | 3.000
> simplex.can_improve?
=> true
> simplex.pivot
=> [0, 3]
> puts simplex.formatted_tableau
0.000 -0.500 0.500 0.000
----------------------------------------------
1.000 0.500 0.500 0.000 | 2.000
0.000 *1.500 -0.500 1.000 | 1.000
</code></pre>
<p>In the project description on Github and Rubygems I call this a ā<strong>naive</strong>ā solver, and that it certainly is. For example,
it assumes your problem has feasible origin (because in my use case this is always true). Iād like to improve it
so that it doesnāt make this assumption, but I might not find the time.</p>