Posts Tagged ‘SVG’

Brute-force convex hull construction

I’ve been experimenting a bit with convex hull constructions and below I’ll explain how to do a brute-force construction of a hull.

It’s worth noting up-front that the brute-force method is slow, O(n3) worst case complexity. So why bother? I think there are a few compelling reasons:

  • The brute-force method expresses the fundamental solution, which gives you the basic building blocks and understanding to approach more complex solutions
  • It’s faster to implement
  • It’s still a viable solution when n is small, and n is usually small.

What is a convex hull?

You can find a formal definition on Wikipedia. Informally, and specific to computational geometry, the convex hull is a convex polygon in which all points are either vertices of said polygon or enclosed within the polygon.

Brute-force construction

  • Iterate over every pair of points (p,q)
  • If all the other points are to the right (or left, depending on implementation) of the line formed by (p,q), the segment (p,q) is part of our result set (i.e. it’s part of the convex hull)

Here’s the top-level code that handles the iteration and construction of resulting line segments:

/**
* Compute convex hull
*/
var computeConvexHull = function() {
console.log(
"--- ");

for(var i=0; i<points.length; i++) {
for(var j=0; j<points.length; j++) {
if(i === j) {
continue;
}

var ptI = points[i];
var ptJ = points[j];

// Do all other points lie within the half-plane to the right
var allPointsOnTheRight = true;
for(var k=0; k<points.length; k++) {
if(k === i || k === j) {
continue;
}

var d = whichSideOfLine(ptI, ptJ, points[k]);
if(d < 0) {
allPointsOnTheRight =
false;
break;
}
}

if(allPointsOnTheRight) {
console.log(
"segment " + i + " to " + j);
var pointAScreen = cartToScreen(ptI, getDocumentWidth(), getDocumentHeight());
var pointBScreen = cartToScreen(ptJ, getDocumentWidth(), getDocumentHeight());
drawLineSegment(pointAScreen, pointBScreen);
}

}
}
};

The “secret sauce” is the whichSideOfLine() method:

/**
* Determine which side of a line a given point is on
*/
var whichSideOfLine = function(lineEndptA, lineEndptB, ptSubject) {
return (ptSubject.x - lineEndptA.x) * (lineEndptB.y - lineEndptA.y) - (ptSubject.y - lineEndptA.y) * (lineEndptB.x - lineEndptA.x);
};

This is a bit of linear algebra derived from the general equation for a line.

The result represents the side of a line a point is one, based on the sign of the result. We can check if the point is on the left or on the right, it doesn’t matter as long as there is consistency and the same check is done for all points.

How it looks

I made a few diagrams to show the first few steps in the algorithm, as segments constituting the convex hull are found. The shaded area represents our success case, where all other points are to the right of the line formed by the points under consideration. Not shown are the failure cases (i.e. one or more points are on the left of the line formed by the points under consideration).

convex hull construction, brute force, step 1

convex hull construction, brute force, step 1

convex hull construction, brute force, step 1

Code and Demo

You can play around with constructing a hull below by double-clicking to add vertices.

You can find the code on GitHub.

A look at Adobe Edge Animate

I recently played around a bit with Adobe Edge Animate, as I was searching for an SVG animation tool, and jotted down a few notes on my impression of the editor.

Adobe Edge Animate CC 2014
  • The timeline and visual preview are excellent, it’s refreshing to have something like this available for web animations. I did notice a tendency for the preview to tear and flicker when animating but, overall, it’s a minor annoyance.
  • The output is not cross-platform, the generated code is heavily webkit-based and depends on vendor-prefixed styles (-webkit-filter) for certain effects. It’s cool to see the effect and have them in the editor, but it really doesn’t achieve a “write once, run anywhere” development process.
  • This is not an SVG animation tool. I expected transitions and transformation on SVG elements (groups, paths, etc.), instead what’s generated is CSS3 transitions/transformations on a <div> element (the SVG document is simply put as the background-image of the <div>). This severely limits what can be done. Much richer and expressive animations could be achieved by allowing manipulating the points and control points on individual SVG elements.

It’s disappointing that despite being an incredibly visual medium, most web design tasks are still done by writing linear blocks of code. Animation is a task well suited for a WYSIWYG editor and Edge Animate is ultimately a step in the right direction, but it’s basis on CSS3 transition and transform puts some hard limits on what can be achieved and I can’t see myself using it for anything substantial.

Rtf2Html 1.3

I recently made a small update to Rtf2Html (the converter I wrote for converting RTF text to HTML markup):

  • Support for conversion to SVG markup
  • Updated preview form to use GeckoFX 29 and XULRunner 29.0.1 (the major version numbers have to match)

Download it here.
Note that this version requires the .NET Framework v4.0 or later.

Rtf2Html SVG support

While you can put the generated SVG text on a page, that wasn’t really my motivation here; what I wanted was a way to import syntax-highlighted text (in my case, typically code) into a vector graphics application (Inkscape, Illustrator, etc.) to be placed as part of a diagram.

Entering the world of high-DPI displays

With a Retina iPad and my recent purchase of a Yoga 2 laptop with a “Quad HD” display (3200×1800) I’ve been dragged into the world of high-DPI (more precisely PPI) displays. For years, DPI was “standard” at either 96dpi (Windows) or 72dpi (Mac OS), with a logical/software pixel being equivalent to a hardware pixel on the display device. A higher resolution monitor meant the content on your display got a bit smaller but you gained a couple more thousand pixels to work with, but the recent and massive increases in pixel densities seems to be the end of the 1:1 mapping between software and hardware pixel references. Below are a few notes on my experiences dealing with high-DPI displays and content so far.

  • Windows 8.1 support is terrible. Both application support and operating system support for high-DPI displays is abysmal. See the post Living a High-DPI desktop lifestyle can be painful by Scott Hanselman which reflects many of the issues I’ve encountered with my Yoga 2 as well. There’s a large list of issues: for non-DPI aware applications Windows scale text but not icons and layout, applications lie about being DPI-aware and are rendered too small, and some applications simply crash (TourtiseSVN’s diff… no clue why, too many pixels?!). It’s easy to wag a finger at application developers, but legacy support is clearly something the operating system needs to handle. In addition, despite Windows 8.1 touting automatic, per-monitor, DPI detection, it’s all based off of the DPI of a “primary monitor” and content on the other monitors is scaled to match. So dragging a window for an application from the Yoga 2 display across to a HD/96dpi monitor results in the window being scaled down (and visibly blurry). Worse, all applications undergo the same treatment – so if you’re thinking you can just use non-DPI aware applications on an external display until support comes around, guess again.
    ArsTechnica did a piece mentioning this issue in particular, and Windows 8.1’s high-DPI support is general.
  • Web support is only half-way there. The best thing done to support high-DPI displays was defining the CSS2 reference pixel to be independent of hardware pixels. Beyond that you have media queries and higher resolution background images, but there’s still no good way to specify alternate foreground images, though the <picture> element may gain support soon. In general, outside of CSS things gets messy, as is the case with a high-DPI <canvas>.
    One problem with the web that I don’t see a proposed solution for is handling low-resolution image assets for which you can’t get a higher resolution version. This is a problem I face with this blog. There’s a lot of images (old screenshots, low-resolution photos, etc.) for which I can’t get a 2x, 4x, etc., higher resolution version and there’s no way to prevent upscaling the images or specify how the upscaling is done. The typical 2x-bilinear-filtered upscaling, done by most browsers, is not always desirable. In addition, as display vendors pack more pixels in, what happens when the “high-resolution” version needed is 4x or 8x?
  • SVG/Vector-based images aren’t always the answer. There’s a lot of benefits to vector-based formats, but they’re not the holy grail many think they are. For vector-based images, rendering costs grow as you add details with polygons and paths. It’s why video games still rely heavily on texture mapping, even as graphics hardware has progressed to handle rendering millions of polygons per frame – the additional geometry and computation for fine details is enormous.

No SMIL+SVG in Internet Explorer

After noticing the SMIL animation in my previous post on SVG animations not working in Internet Explorer 10, I did a bit of digging to see what level of support was offered by IE10 and IE9 (previous versions do not support SVG). Simply put, Internet Explorer does not support SMIL animation of SVG. An entry from IEBlog regarding the an IE9 platform preview explains why:

… support for SMIL animation of SVG in the web development community is far from strong. The leader of the SVG standardization effort wrote that not supporting SMIL in its current state is probably best “since the SVG WG intends to coordinate with the CSS WG to make some changes to animation and to extend filters.” There’s already work started to reconcile CSS3 animations and SVG.

I’m not shedding any tears. That said, I’m not that enthusiastic about CSS3 animations for SVG either, as CSS3 animations bring with them the same loss of flexibility as SMIL. The current, flexible, cross-browser solution for SVG animation is Javascript, and I can’t see why that’s not a worthwhile solution for the foreseeable future as well.

SVG Animations

I decided to play around a bit with animating SVG content. There are actually multiple ways to animate SVG: CSS (transition, transform, @keyframes), Javascript, or Synchronized Multimedia Integration Language (SMIL). Where possible, I tend to prefer Javascript, as you have far more flexibility compared to markup languages; however, out of curiosity, I did try my hand at SMIL as well.

Method 1: Javascript

Here’s the SVG markup for the object being animated.

<svg version="1.1" x="0px" y="0px" width="74px" height="74px" viewBox="-1.751 -1.751 74 74" enable-background="new -1.751 -1.751 74 74" xml:space="preserve">
    <
g id="circularMarker" transform="rotate(0 35.163 35.521)">                
        <
path fill="#27AAE1" d="M46.336,7.908c2.174,0.678,4.236,1.538,6.199,2.54V3.69c-1.417-0.607-2.875-1.146-4.377-1.616
            C37.794-1.161,27.147-0.491,17.793,3.242v6.663C26.41,5.825,36.518,4.843,46.336,7.908z"/>
        <
path fill="#27AAE1" d="M62.423,46.338c-0.679,2.173-1.537,4.236-2.538,6.199h6.757c0.605-1.417,1.147-2.877,1.615-4.382
            c3.235-10.364,2.564-21.006-1.167-30.362h-6.664C64.505,26.41,65.489,36.52,62.423,46.338z"/>
        <
path fill="#27AAE1" d="M23.992,62.42c-2.171-0.678-4.236-1.536-6.199-2.538v6.759c1.418,0.604,2.877,1.146,4.381,1.616
            c10.364,3.233,21.009,2.564,30.362-1.17v-6.664C43.921,64.505,33.81,65.488,23.992,62.42z"/>
        <
path fill="#27AAE1" d="M7.909,23.994c0.678-2.174,1.538-4.237,2.538-6.2H3.691c-0.606,1.416-1.147,2.878-1.617,4.38
            c-3.234,10.364-2.564,21.012,1.168,30.365h6.664C5.825,43.921,4.843,33.813,7.909,23.994z"/>
        <
circle fill="#00AEEF" cx="35.163" cy="35.521" r="11.331"/>
    </
g>
</
svg>    

To animate, the transform attribute on the #circularMarker group element is updated every frame to do a simple rotation at a rate of 0.275 deg/ms. You can see the result in the iframe below.

Here’s the Javascript code that makes it happen:

<script src="jquery-1.8.2.min.js" type="text/javascript"></script>
<
script type="text/javascript">

// setup window.requestAnimationFrame
(function ()
{
var requestAnimationFrame = window.requestAnimationFrame || window.mozRequestAnimationFrame ||
                                 window.webkitRequestAnimationFrame || window.msRequestAnimationFrame;
window.requestAnimationFrame = requestAnimationFrame;
})();


// set initial frame time (in milliseconds)
var ft1 = new Date().getTime();

// set initial angle (in degrees)
var angleDeg = 0;

// function to rotate circle
function rotateCircularMarker()
{
var ft = new Date().getTime();
var ftDelta = ft - ft1;
ft1 = ft;

// rotate at a rate of 0.275 deg/ms
angleDeg += ftDelta * 0.275;

if (angleDeg >= 360) {
// full circle!, reset angleDeg
angleDeg = 0;
}

// transform the #circularMarker group
// Note: the rotation is about the center of the circle element (35.163, 35.521)
$('#circularMarker').attr('transform', 'rotate(' + angleDeg + ' 35.163 35.521)');

// call requestAnimationFrame to continue animating
requestAnimationFrame(rotateCircularMarker);
}

$(document).ready(
function ()
{

rotateCircularMarker();

});
            
</script>

Note that window.requestAnimationFrame is used, so a modern browser is required. For older browsers it is possible to use window.setInterval as a fallback.

Method 2: SMIL

With SMIL, the SVG code remains the same, with the exception of an animateTransform tag within the #circularMarker group element.

<animateTransform attributeName="transform" attributeType="XML" type="rotate" from="0 35.163 35.521" to="360 35.163 35.521" begin="0s" dur="1.336996s" repeatCount="indefinite"/>

The attributes of animateTransform describe the animation, mainly type, from, to, begin, dur, and repeatCount.

Obviously SMIL yields less code and removes all Javascript dependencies, but it does come at the cost of losing flexibility (as you can only perform transformations and timing operations supported by SMIL attributes) and having to learn yet another markup language.

poly2path

I’m working on a little SVG project using Raphaël. Unfortunately, Illustrator exports polygons in its SVG output which is not supported by Raphaël (only paths are supported). So I wrote an app to convert the SVG polygon string to an SVG path string.

Please upgrade your Flash Player This is the content that would be shown if the user does not have Flash Player 9.0.115 or higher installed.

the conversion…

poly2path conversion

Note that you only input the points data from the polygon (from the points attribute), not the entire polygon element. The result is the path string for the d attribute of the path element.

The conversion is very simple and based upon the fact that a polygon is a path starting with an absolute moveto, linetos to each of the points, and a closepath (this bug report [yes, a bug report!] was pretty helpful).

I actually wanted to render the output, but I was disappointed to discover that Adobe Air doesn’t currently support SVG.

The main reason for not including it was runtime size concerns (adding it would have increased the runtime size by 15 to 20 percent). Initially, the main pain-points regarding AIR were the size of the runtime, integration with the operating system and native APIs, support for the <canvas> tag and new CSS properties, and JavaScript performance. These priorities, coupled with a trend toward reduced interest in SVG graphics, led to SVG support not being included in the current version of Adobe AIR.

Firelight

I stumbled across an interesting project on reddit yesterday, it’s called Firelight and it’s basically a system that utilizes Javascript + SVG + XAML. It’s still in its infancy and I’m pretty iffy on XAML in general, but it’s a pretty cool idea nonetheless.