Transcript - CSUN ScholarWorks - California State University

Evaluation of HTML5 Graphics for
Data Structure Visualization
Gevik Sarkissian
Master’s Thesis
California State University, Northridge
May 9, 2014
Abstract
Graphics have become a major part of the digital world,
including the web. The latest era of the web is HTML5 and it provides
many new features for web developers and users. Some of theses
features are new ways to render, interact with, and animate graphics
inside a web browser – CSS3, Canvas, SVG, and WebGL. This paper is a
study on these graphics technologies, and the ability to use them to
visualize data structures in a browser as an alternative to using plugins
like Flash. The four technologies were compared in an effort to
understand each one, and from this comparison a determination was
made on which is the best choice for visualizing data structures. The
technology of choice was used to build a tool that allows for native webbased data structure visualization. The criteria for success of the tool are
its usability, performance, and feature set. The tool successfully
demonstrates that the modern web’s native graphics technologies are a
viable alternative to traditional Flash-based data structure visualization
tools.
Outline
 Rationale
 Background
 Research
 Decision
 Implementation
 Demonstration
 Findings
Rationale
 As HTML5 has matured and the web standards have changed,
the need for using external plugins in a browser like Flash,
Java, Silverlight and QuickTime has declined.
 Data structures and algorithms are essential concepts for
computer science students and learning about them visually is
the most effective way.
 Existing tools to visualize data structures are dominantly Flashbased or Java-based and could greatly be improved.
 Many native desktop applications are moving into the web
and/or mobile apps.
The Web
 Web 1.0 – The Brochure Web
 Web 2.0 – User-generated content
 Web 2.5 – Web applications and video streaming
 HTTP has not changed as much as the front end of the
web has.
Internet Traffic Distribution
HTML5
 Is the latest iteration of the front end of the web.
 Provides new features for developers and users – video
and audio streaming, semantic tags, geolocation, local
storage as an alternative to cookies, and form
enhancements.
 Also introduces new graphics technologies like Canvas
and WebGL while improving existing ones like SVG and
CSS.
Graphics
 Two main graphics types: raster (JPG, BMP, GIF, PNG) and
vector (SVG, EPS).
 Raster graphics are a matrix of pixels with color and alpha
values and lose quality when enlarged.
 Vector graphics contain instructions on how the graphic
should render and can resize without losing quality.
 Raster graphics are ideal for real images while vector
graphics are ideal for logos and simple graphics.
Research
 The four graphics technologies that were considered are
SVG, Canvas, CSS3, and WebGL.
 Comparisons were made in the areas of performance,
support, and ease of development.
 One of these four was chosen to implement the binary
search tree visualization tool.
Canvas
 Canvas is a HTML5 element that provides a JavaScript API
for developers to render and animate graphics.
 The <canvas> element is rendered to the page but its
context property is used to render graphics onto it.
 Currently supports two contexts: “2d” and “webgl”.
 Often used by Google Doodles or for web games.
Canvas Example
SVG
 Scalable Vector Graphics is a popular vector graphic
format for use on the web and in apps.
 Each SVG is represented by XML and is converted to a
DOM element when the browser parses it.
 While SVG existed pre-HTML5, HTML5 allows for better
integration of SVGs with a browser.
 When the browser parses an SVG, it turns it into a
Document Object Model (DOM) element in the page.
SVG Example
Raster vs. Vector
Raster vs. Vector
Raster vs. Vector
Raster vs. Vector
CSS3
 CSS3 expands on the capabilities of CSS2 by providing
new ways to style and animate HTML elements.
 Using CSS3 we can render basic shapes using properties
like border-radius, border-style, width, and height.
 CSS3 also provides transforms to allow for advanced
rendering and animation of HTML elements, such as
skewing, rotating, and translating.
WebGL
 WebGL is a hardware-accelerated 3-dimensional graphics
technology.
 Can be thought of as OpenGL in a browser.
 Not a good candidate for the relatively simple task of
visualizing data structures, but is worth mentioning.
Browser Support
Performance (Render Time)
Performance (Memory Usage)
Decision
 While Canvas does perform better than SVGs at higher
sprite counts, this sprite count will not be reached in a
data structure visualization tool.
 Since SVGs are DOM elements, implementing drag and
drop functionality in the tool will be easier than with
Canvas.
 Nodes in a binary search tree require references to other
nodes, lines, and properties like position, color, and
dimensions. This is easier to associate to SVGs than
pixels.
Existing Tools
 http://www.cs.jhu.edu/~goodrich/dsa/trees/btree.html
 http://www.qmatica.com/DataStructures/Trees/BST.html
 http://www.ibr.cs.tubs.de/courses/ss98/audii/applets/BST/BST-Example.html
 http://www.cosc.canterbury.ac.nz/mukundan/dsal/TwoT
hreeTree.html
 http://www.cs.usfca.edu/~galles/visualization/Algorithms
.html
Architecture
Libraries Used
Name
Version
License
Source
jQuery
2.1
MIT
http://jquery.com/
Buckets
2
Apache
https://github.com/mauriciosantos/buckets
Raphael
2.1
MIT
http://raphaeljs.com/
HTML5 Shiv
3.7
MIT/GPLv2
https://code.google.com/p/html5shiv/
jQuery SVG
1.4.5
MIT
http://keith-wood.name/svg.html
Underscore
1.6
MIT
http://underscorejs.org/
SCSS (PHP)
0.0.9
MIT/GPLv3
http://leafo.net/scssphp/
CSS Reset
2
Public Domain http://meyerweb.com/eric/tools/css/reset/
Demonstration
Advantages
 When compared to existing Java/Flash based tools, this
tool is superior for a number of reasons.
 The tool runs on any modern web browser and does not
have dependencies on operating system, Java version,
and does not prompt security warnings.
 The tool is highly interactive and is more intuitive than
existing tools.
 This is also an improvement over Dr. David Galles’
excellent tool because it features drag and drop, file
upload, and pruning.
Future work
 UI improvements can be made regarding the
repositioning of nodes to eliminate overlaps.
 The tool does not react well to a resized browser since it
depends on initial conditions to position nodes correctly.
 More data structures and algorithms to choose from.
 Ability to save tree to a text file.
Results
 Canvas performs better than SVG at high sprite counts.
 SVGs are easier to work with in terms of interactivity.
 There is no reason to use Java or Flash to visualize data
structures.
 There is now a user-friendly, effective tool available for
students wanting to learn the operations of a binary
search tree.