some mid-edge projections\u00a0are lost as the scanline moves forward<\/li>\n<\/ol>\n
in other words, it sucks.<\/p>\n
which\u00a0edges?<\/p><\/blockquote>\n
the first step is to determine which edges to process.\u00a0<\/span>we need to process an edge only if it is <\/span>potentially<\/em> visible from the light source.\u00a0this is achieved by computing the dot product of the edge’s normal vector & the vector going from the light source towards one of the edge’s vertices.\u00a0if the result is negative, the vectors are pointing in opposite directions meaning the edge is “facing” the light source & needs to be processed.<\/span><\/p>\n
this is the code you need:<\/p>\n
function normalize( point )\r\n{\r\n\tvar length = Math.sqrt( point.x * point.x + point.y * point.y );\r\n\tpoint.x \/= length;\r\n\tpoint.y \/= length;\r\n\treturn point;\r\n}\r\n\r\nfunction normal( p0, p1 )\r\n{\r\n\treturn new Point( -( p0.y - p1.y ), ( p0.x - p1.x ) );\r\n}\r\n\r\nfunction dotProduct( p0, p1 )\r\n{\r\n\treturn ( p0.x * p1.x + p0.y * p1.y );\r\n}\r\n\r\n\/\/ p0 \/ p1 are the two edge's ends\r\n\/\/ light is the light source\r\n\/\/ dir is a temporary vector from one end of the edge\r\n\/\/ to the light source\r\n\r\nvar dir = new Point();\r\ndir.x = p0.x - light.x;\r\ndir.y = p0.y - light.y;\r\n\r\nvar norm = normalize( normal( p0, p1 ) );\r\n\r\n\/\/edge is visible\r\nif( dotProduct( norm, dir ) < 0 )\r\n{\r\n\t\/\/visible edge code here\r\n}<\/pre>\n
statistically, this removes 50% of the\u00a0computations. note that I said as few assumptions as possible concerning the edges<\/em> but this is a strong one ; I assume that edges are opaque on both sides. by using a more sophisticated edge data structure, we could specify which side is visible or have one-sided walls ( like a stainless mirror ).<\/p>\n
a nice (& necessary) addition is the visibility range<\/em> ; beyond a given distance from the light source, we don’t have to compute anything.
\nby adding a simple distance check to the previous test, we can decimate the potentially visible edges’ list further.<\/span><\/p>\n
function squareDistance( a,b )\r\n{\r\n\treturn ( a.x - b.x ) * ( a.x - b.x ) + ( a.y - b.y ) * ( a.y - b.y );\r\n}\r\n[...]\r\n\/\/the light's range\r\nvar range = 200;\r\n\r\n\/\/using square distances saves some square roots computations\r\nvar square_range = range * range;\r\nif(\tsquareDistance( p0, light ) > square_range\r\n&&\tsquareDistance( p1, light ) > square_range )\r\n{\r\n\t\/\/ both ends of this edge are too far, no need to process\r\n\tcontinue;\r\n}<\/pre>\n
overmore, if we consider the edges as walls &\u00a0we know that we can have closed shapes, an interesting test can be performed before actually processing anything to determine whether or not a polygon\u00a0contains<\/em>\u00a0the light source & eventually stop the computation there. in my previous article, I’ve shown a method that does this.<\/p>\n
here’s a live demo:<\/p>\n
<\/div>\npotential visibility fullscreen<\/a>
\nmove around to see the potentially visible edges (blue) click & drag<\/strong> to use the visibility range, when the shape turns grey, it means that the shape\u00a0contains the light so nothing is computed.<\/p>\n
when clicked, the pink edges are out of range\u00a0&\u00a0don’t need to be processed which leaves us only with the blue edges. I’ve displayed the\u00a0decimation<\/em> ratio that indicates how\u00a0much of the original edges\u00a0are valid and need to be processed.<\/p>\n
closing the visibility polygon<\/p><\/blockquote>\n
the visibility range is a nice addition yet it induces\u00a0a greater problem ; how to close the Visibility Polygon.<\/p>\n
the\u00a0simple solution is to\u00a0enclose all\u00a0the polygons inside a bounding polygon (usually a quadrilateral) &\u00a0use\u00a0infinite rays\u00a0; this way we are certain that the rays\u00a0will\u00a0hit something… some time.<\/p>\n
in the next example, I’ve added a series of 4 (yellow), 8 (red) & 60(blue) edges forming a circle around the light.
\nI also perform the tests described above so when running, only the visible edges within the light range are being processed. this should run much faster than the naive approach (roughly twice).<\/p>\n
here’s the result:<\/p>\n
<\/div>\neducated approach fullscreen<\/a><\/p>\n
before starting the animation, you should see the outlines of the visible polygons.<\/p>\n
even though it works, this is not a very elegant solution ; we have to create extra geometry or we’ll lose the benefit of a visibility range. in the case of AI, the agents would have an infinite line of sight, in the case of graphics, the light would flood offscreen which is not the expected result. overmore, this approach doesn’t solve the mid-edge projection issue & the precision of the boundaries depends on the number of edges added (the edge count is discrete as opposed to continuous arcs).<\/p>\n
I had the intuition that the problem\u00a0could boil\u00a0down to determining when a ray would switch<\/em>\u00a0between distances\u00a0from the light source. indeed if we convert all cartesian coordinates to polar coordinates, we get the 2 values we need to solve the algorithm:<\/p>\n
\n
the angles at which we should project rays<\/li>\n
the distances from each point to the light source<\/li>\n<\/ul>\n
as it’s not a trivial concept to understand, here’s a demo of polarization<\/p>\n
<\/div>\n
polar fullscreen<\/a>
\nmove your mouse around, you’ll see the arcs described by the edges’ start and end angles projected on the visibility range around the mouse.<\/p>\n
the important bit here is what happens at the bottom where all the angles are represented as vertical lines and all the edges as segments.
\nbefore going further, computing the edge’s projection against the visibility circle allows for a nifty trick ; instead of computing the visible polygon, what if we compute the invisible polygon?<\/p>\n
instead of casting light, why not casting shadows?<\/p>\n
here’s how the code would go:<\/p>\n
ctx.fillStyle = \"rgba(0,0,0,.15);\/\/15% opacity\r\nctx.beginPath();\r\nvar dir = new Point();\r\nfor( var i =0; i < points.length; i++ )\r\n{\r\n var p0 = points[ i ];\r\n var p1 = points[ ( i+1 ) % points.length ];\r\n\r\n \/\/same old visibility test to spare computations\r\n dir.x = p0.x - light.x;\r\n dir.y = p0.y - light.y;\r\n var norm = normalize( normal( p0, p1 ) );\r\n\r\n \/\/edge is visible\r\n if( dotProduct( norm, dir ) <= 0 )\r\n {\r\n edge = new Edge( p0, p1, light );\r\n\r\n \/\/this is the projection of the edge's ends on the visibility range\r\n\r\n var pp0 = new Point( light.x + Math.cos( edge.start ) * range,\r\n light.y + Math.sin( edge.start ) * range );\r\n\r\n var pp1 = new Point( light.x + Math.cos( edge.end ) * range,\r\n light.y + Math.sin( edge.end ) * range );\r\n\r\n ctx.moveTo( edge.p0.x, edge.p0.y);\r\n ctx.lineTo( edge.p1.x, edge.p1.y);\r\n ctx.lineTo( pp1.x, pp1.y );\r\n ctx.lineTo( pp0.x, pp0.y );\r\n }\r\n}\r\nctx.fill();\r\n<\/pre>\n
& this would be the result (click maintain & drag):<\/p>\n
<\/div>\n
shadow casting fullscreen<\/a><\/p>\n
note: you’ll need a big range<\/em> for it to work as it is supposed to overflow the screen.
\nif the light source is too close from the edge, it will fail. as the edge’s end are projected on a huge circle, the closer you get to a wall, the closer the arc’s chord will be to the back of the wall. it’s still a fast and easy solution for graphics rendering of shadows.<\/p>\n
back to the polar view, we saw it’s possible to consider the edges’ projections as angle-distance rather than X Y coordinates (polar coordinates vs cartesian coordinates).<\/p>\n
to solve the problem in the polar space, we have to change the approach a bit. the scanline would move from left to right & the light would cast a ray from the top towards the bottom. the picture below sums up the cases we need to solve.
\n $\"polarized\"$ <\/p>\n
we’re after the thick blue line.<\/p>\n
the code remains the same as before but instead of systematically picking the closest intersection, we’ll have to perform some extra tests depending on the nature of the point being processed & for this we need…<\/p>\n
a less stupid data structure<\/p><\/blockquote>\n
a less stupid Point<\/p>\n
var EdgePoint = function( x, y, angle, distance, light )\r\n{\r\n\r\n\tthis.x = x||0;\r\n\tthis.y = y||0;\r\n\tthis.angle = angle||0;\r\n\tthis.distance = distance||0;\r\n\r\n\tthis.A = -Math.cos( this.angle );\r\n\tthis.B = Math.sin( this.angle );\r\n\tthis.C = light.x * ( light.y + this.B ) - light.y * ( light.x - this.A );\r\n\r\n\tthis.edge = null;\r\n\tthis.isChained = false;\r\n\tthis.isArc = false;\r\n\r\n};\r\n<\/pre>\n
now the point is aware of the edge it belongs to, stores its angle and knows if it belongs to a chain or if it is the end of an edge. in addition, it computes the values (ABC) required to perform the projection test & can be flagged as an arc (see render method below).<\/p>\n
a less stupid edge<\/p>\n
var Edge = function()\r\n{\r\n\r\n\tthis.p0 = null;\r\n\tthis.p1 = null;\r\n\tthis.a0 = 0;\r\n\tthis.a1 = 0;\r\n\r\n\tthis.init = function( p0, a0, d0, p1, a1, d1, light )\r\n\t{\r\n\r\n\t\ta0 = ( a0 + PI2 );\r\n\t\ta1 = ( a1 + PI2 );\r\n\r\n\t\tthis.p0 = new EdgePoint( p0.x, p0.y, a0, d0, light );\r\n\t\tthis.a0 = a0;\r\n\t\tthis.p1 = new EdgePoint( p1.x, p1.y, a1, d1, light );\r\n\t\tthis.a1 = a1;\r\n\r\n\t\tthis.D = this.p0.x - this.p1.x;\r\n\t\tthis.E = this.p1.y - this.p0.y;\r\n\t\tthis.F = this.p0.x * this.p1.y - this.p0.y * this.p1.x;\r\n\r\n\t\tthis.p0.edge = this;\r\n\t\tthis.p1.edge = this;\r\n\r\n\t};\r\n\r\n};\r\n<\/pre>\n
it stores the two points, the two angles & precomutes the projection value D,E,F.<\/p>\n
another thing we have to determine is whether or not a point is occluded<\/em> ; indeed if a point is completely hidden behind an edge, it cannot belong to the solution.
\nduring the projection loop, I’ve added an occluded<\/em> boolean that is set to false for each point & switches to true if the point’s projection is closer to the light source than the point itself (those are the red crosses the picture above).<\/p>\n
with this less stupid data structure, we can refine the tests after finding the closest point:<\/p>\n
if( !occluded )\r\n{\r\n\t\/\/if the point doesn't belong to a chain\r\n\tif( !p.isChained )\r\n\t{\r\n\t\t\/\/ and was not projected on any other segment\r\n\t\tif( closest == null )\r\n\t\t{\r\n\t\t\t\/\/ it belongs to the visibility range\r\n\t\t\t\/\/we have to create this point\r\n\t\t\tclosest = polarToCartesian( p.angle, range, light );\r\n\t\t\tclosest.angle = A;\r\n\t\t\t\/\/and flag it as an arc\r\n\t\t\tclosest.isArc = true;\r\n\t\t}\r\n\t\tif( p == p.edge.p0 )\/\/ if p is the start point of the edge\r\n\t\t{\r\n\t\t\tsolution.push( closest, p );\r\n\t\t}\r\n\t\telse \/\/ other wise p is the end point\r\n\t\t{\r\n\t\t\tsolution.push( p, closest );\r\n\t\t}\r\n\t}\r\n\telse\r\n\t{\r\n\t\t\/\/the point belongs to a chain, add it\r\n\t\tsolution.push( p );\r\n\t}\r\n}<\/pre>\n
when a point belongs to the visibility range, we need to create a point using the polarToCartesian()<\/em> method. no black magic here either:<\/p>\n
function polarToCartesian( angle, distance, origin )\r\n{\r\n\tvar out = new Point();\r\n\tout.x = origin.x + Math.cos( angle ) * distance;\r\n\tout.y = origin.y + Math.sin( angle ) * distance;\r\n\treturn out;\r\n}<\/pre>\n
which gives us this glorious demo:<\/p>\n
<\/div>\n
behold YE glorious fullscreen<\/a> – here’s the source code<\/a>
\nthe source code is not the cleanest you can dream of but at least it is standalone.<\/p>\n
another thing is that to properly close the the visibility polygon, we need to draw arcs. that’s where the EdgePoint.isArc<\/strong><\/em> comes to the rescue.
\nthe arcs are always drawn between 2 points of the solution so the rendering method only needs to know when 2 consecutive<\/em> points of the solution have their .isArc<\/strong> flag set to true & draw a sector (a.k.a. pie slice<\/em>) otherwise draw a triangle.<\/p>\n
var solution = compute( points, light, range );\r\ncontext.beginPath();\r\nfor( i = 0; i < solution.length; i++ )\r\n{\r\n\tcontext.moveTo( light.x, light.y );\r\n\r\n\tp = solution[ i ];\r\n\tn = solution[ ( i+1 ) % solution.length ];\r\n\tif( p.isArc && n.isArc )\r\n\t{\r\n\t\tcontext.arc( light.x, light.y, range, p.angle, n.angle, false );\r\n\t}\r\n\telse\r\n\t{\r\n\t\tcontext.lineTo( p.x, p.y );\r\n\t\tcontext.lineTo( n.x, n.y );\r\n\t}\r\n\tcontext.lineTo( light.x, light.y );\r\n\r\n}\r\ncontext.closePath();\r\ncontext.fill();<\/pre>\n
this takes advantage of the way the Canvas API works : beginPath() opens a buffer of mixed instructions until the closePath() or a draw method is called. as our solution is guaranteed to be convex & to have a CW winding, we can iterate on the solution’s points linearly.<\/p>\n
it’s pretty similar to having created the circular frame around the light with the notable difference that it doesn’t create extra geometry. unfortunately there are still some cases where it breaks ; the arcs are not drawn properly so the safest is still to use a bounding polygon.<\/p>\n
penumbra<\/p><\/blockquote>\n
I tried to implement a penumbra<\/em> (soft shadows) as described in this article<\/a> but failed miserably.
\nthe plan was simple, as we know when we render an arc, we should be able to draw an area that simulates the light fading away. to do this – as the shading is not linear – we need a texture like the one below:
\n $\"\"$
\n(in photoshop, it’s a transparent “angle gradient” with a very small (<2%) opaque black span at both ends) so whenever we hit an arc, we translate the canvas at the location of the point before the arc point, rotate the canvas to orient it along this edge. then we set the texture as fill pattern & draw an arc of 45\u00b0 (= PI \/ 4). the code:<\/p>\n
var pid = 0,\r\n\tnid = 0,\r\n\tprevious = null,\r\n\tnext = null,\r\n\tdist = 0;\r\n\r\nfor( i = 0; i < solution.length; i++ )\r\n{\r\n\tp = solution[ i ];\r\n\tn = solution[ ( i+1 ) % solution.length ];\r\n\r\n\tif( p.isArc && n.isArc )\r\n\t{\r\n\t\r\n\t\t\/\/left shadow\r\n\t\tpid = ( i-1 ) < 0 ? solution.length - 1 : ( i - 1 );\r\n\t\tprevious = solution[ pid ];\r\n\t\r\n\t\tdist = range - previous.distance;\r\n\t\r\n\t\tcontext.save();\r\n\t\r\n\t\t\tcontext.translate( previous.x, previous.y );\r\n\t\t\tcontext.rotate( p.angle - PI \/ 4 );\r\n\t\r\n\t\t\tcontext.beginPath();\r\n\t\t\tcontext.moveTo( 0,0 );\r\n\t\t\tcontext.arc( 0,0, dist, 0, PI \/ 4, false );\r\n\t\t\tcontext.lineTo( 0,0 );\r\n\t\t\tcontext.closePath();\r\n\t\t\tcontext.fill();\r\n\t\r\n\t\tcontext.restore();\r\n\t\r\n\t\t\/\/right shadow\r\n\t\tnid = ( i+2 ) % solution.length;\r\n\t\tnext = solution[ nid ];\r\n\t\r\n\t\tdist = range - next.distance;\r\n\t\r\n\t\tcontext.save();\r\n\t\r\n\t\t\tcontext.translate( next.x, next.y );\r\n\t\t\tcontext.rotate( n.angle - PI \/ 4 );\r\n\t\r\n\t\t\tcontext.beginPath();\r\n\t\t\tcontext.moveTo( 0,0 );\r\n\t\t\tcontext.arc( 0,0, dist, PI \/ 4, PI \/ 2, false );\r\n\t\t\tcontext.lineTo( 0,0 );\r\n\t\t\tcontext.closePath();\r\n\t\t\tcontext.fill();\r\n\t\r\n\t\tcontext.restore();\r\n\t\r\n\t}\r\n}<\/pre>\n
& here’s the result:<\/p>\n
<\/div>\n
fullscreen<\/a> – source<\/a> – texture<\/a><\/p>\n
there are flaws here too ; the self-projections are not taken into account ; it would mean we know which side fades in which direction. as we use a texture, it can’t be faded away along the edge’s axis like a radial gradient would so the length of the soft shadow depends on the texture itself.<\/p>\n
holes<\/p><\/blockquote>\n
this basically relies on the way edges are built & oriented ; the same algorithm works with “compound” objects.
\nhere’s a compound object for instance ; the eyes and the nose have a different orientation then the rest.<\/p>\n
<\/div>\n
fullscreen<\/a> – source<\/a>
\n20 light sources are computed on click (might take some time…), sometimes the light lies within a “hole” & doesn’t spread around or is being blocked by the shape containing the “hole”.
\nI used 2 color palettes: canary<\/a> & Hibiki<\/a> note that the shapes are not being drawn at all ; it’s only made of light.<\/p>\n
extending<\/p><\/blockquote>\n
along the way, I thought of a couple of extensions<\/em> that could be done to improve the thing further<\/p>\n
\n
various light shapes: I used only point lights but why not using a direction & an angle span to create a spot light? or a line that would emit light along its normals?<\/li>\n
translucency: if the ends of the edge know how much light they let through, they can affect the visibility range thus creating a cheap “translucency”<\/li>\n
caustics: as for translucency, caustics would bounce some of the light it recieives either outwards <\/em>(reflection) or inwards<\/em>(refraction)<\/li>\n
curves: I’m only using line\/line intersections here but with a more clever data format & the appropriate intersection methods, it is possible to use curves (for instance using Kevin Lindsey’s intersection routines<\/a>)<\/li>\n
handling the primitives such as circles or regular polygons separately ; there are “shortcuts” to perform the projections on those shapes<\/li>\n<\/ul>\n
… the hidebehind?<\/p><\/blockquote>\n
I like all kinds of insects, chimeras, monsters\u00a0(dragons seems trendy those days) &\u00a0I often envision the algorithms as creatures with an autonomous life<\/em>. I first read about the\u00a0hidebehind\u00a0<\/em>in the\u00a0Book of Imaginary Beings<\/em>\u00a0by\u00a0Jorge Luis Borges.\u00a0<\/em>here’s a description of this creature ( wikipedia source\u00a0<\/a><\/em>)<\/p>\n
\n
[…] As its name suggests, the hidebehind is noted for its ability to conceal itself.\u00a0When an observer attempts to look directly at it, the creature hides again behind an object or the observer and therefore can’t be directly seen\u00a0[…]<\/h4>\n<\/blockquote>\n
the hidebehind<\/em> was a good match for what I was after: a creature that can’t be seen.<\/p>\n