Michael Fogleman

ProjectsArtworkAboutResumeMore

Projects tagged "go"

Hopefully something here will catch your eye.

Table of Contents


Rush Hour June 2018

191 Go C++ Game AI

I solved the Rush Hour puzzle game and created a database of every interesting starting position.

Rush Hour is a 6x6 sliding block puzzle invented by Nob Yoshigahara in the 1970s. It was first sold in the United States in 1996.

I played a clone of this game on my first iPhone several years ago. Recently, I stumbled on the physical incarnation of it and instantly bought it on Amazon for my kids to play. We've been having fun with it, but naturally I was most interested in writing some code to solve the puzzles.

I did more than write a simple puzzle solver. I ended up computing every possible puzzle and built a complete database of every "interesting" starting position. It was quite challenging (and exciting!) so I wrote a whole article about it. Check it out!


Domain Coloring March 2018

33 Go 2D Graphics

Visualize complex functions by coloring each point in the complex plane.

This was a quick experiment inspired by 3Blue1Brown's video called How to solve 2D equations using color. The colorings are based on the magnitude and/or phase of the complex numbers transformed by a function. The coloring algorithm can be as simple or as complicated as you can imagine, providing plenty of room for creativity.


Contour Maps February 2018

130 Go Vector Maps

Generate vector-based contour maps using AWS terrain tiles.

This code generates topographic maps (using contour lines) based on elevation data. It can automatically fetch and cache terrain tiles from AWS. It can render a region defined by a lat/lng bounding box or by a shapefile (such as for a given country or state). I used this code to draw topographic maps on my AxiDraw pen plotter.

The example below shows the topography of the Grand Canyon and its surroundings with contour lines separated by 50 meters in elevation.


3D Packing June 2017

210 Go 3D Optimization

Tightly pack 3D meshes into as small of a volume as possible.

Formlabs recently announced the Fuse 1, a 3D printer that works via Selective Laser Sintering. This technique uses a nylon powder which conveniently supports the structures as they are printed. No scaffolding or supports are needed, so we can print as many objects as we can pack into the volume.

This begs the question - how many 3DBenchy boats can the Fuse 1 print in a single batch? As soon as the printer was announced, I immediately gravitated toward this algorithmic challenge.

With naive bin packing, 82 boats can be packed into the printer volume. But with some more advanced packing algorithms, 113 boats can fit - a 37.8% improvement!

Read the article here.


Ribbon Diagrams February 2017

148 Go 3D Science

Parse PDB files and render ribbon diagrams of proteins.

Ribbon diagrams are 3D schematic representations of protein structure.

You've probably happened upon these before. I always thought they looked very complex and never figured I'd know how to create such a diagram myself. After creating FauxGL, however, I was in search of interesting 3D visualizations and decided to research these interesting diagrams.

Roughly, proteins are chains of amino acids that are pieced together while reading genetic code. As a protein is formed, these chains will fold in various ways, forming helixes, strands, and coils. A ribbon diagram depicts the 3D structure of the protein as well as these common secondary structures.

The Protein Data Bank is an online database of over 130,000 PDB files. These files encode all of the information needed to produce a ribbon diagram. With this software, you can simply type rcsb XXXX where XXXX is the alphanumeric PDB code and a PNG will be generated in a few seconds.


FauxGL January 2017

434 Go 3D Graphics

3D software rendering in pure Go. No OpenGL, no C extensions, no nothin'.

It's like OpenGL, but it's not. It's FauxGL.

It doesn't use your graphics card, only your CPU. So it's slow and unsuitable for realtime rendering. But it's still pretty fast. It works the same way OpenGL works - rasterization.

I mostly wrote this for fun and for learning, but I've already found it useful in other projects.

Features

  • STL, OBJ, PLY, 3DS file formats
  • triangle rasterization
  • vertex and fragment "shaders"
  • view volume clipping, face culling
  • alpha blending
  • textures
  • depth biasing
  • wireframe rendering
  • built-in shapes (plane, sphere, cube, cylinder, cone)
  • anti-aliasing (via supersampling)
  • parallel processing

Primitive September 2016

9,739 Go Objective-C 2D Vector Graphics Optimization

Recreate your photos with vector-based geometric primitives.

You provide an image as input. The app tries to find the most optimal shape that can be drawn to maximize the similarity between the target image and the drawn image. It repeats this process, adding one shape at a time. Using this process, the program can recreate a photo with surprisingly few shapes.

This project was originally inspired by the popular and excellent work of Roger Johansson - Genetic Programming: Evolution of Mona Lisa. Since seeing that article when it was quite new, I've tinkered with this problem here and there over the years. But only now am I satisfied with my results.

The core is written in Go and is open source. A native macOS app is also available in the App Store, providing a nice UI on top of the engine as well as some additional features like "drawing mode." To date, this has been my most successful paid app.


Mesh Simplification May 2016

148 Go 3D Meshing

Simple command line tool for simplifying meshes in STL format.

This is a straight-forward implementation of Surface Simplification Using Quadric Error Metrics, SIGGRAPH 97, written in Go. Some problematic meshes don't simplify very well, but overall it works nicely. Watch the animation - the mesh is repeatedly simplified, starting with 86632 triangles and ending with just 64 triangles. The bunny remains recognizable for an impressive duration.


Point Maps April 2016

102 Go Cassandra Maps

Custom tile server for rendering millions of points on a map efficiently.

I wrote this as a learning exercise for dealing with huge amounts of data on a map.

The points are stored in Cassandra, where they are clustered by their tile coordinates at a predefined map zoom level. When a tile is requested, the tile server can then quickly fetch the correct points. The points are then rendered onto the tile in a way that looks nice but is very performant. The tile server also caches the tiles on disk.


Go Graphics February 2016

1,588 Go 2D Graphics

Cairo-inspired 2D graphics library written in pure Go.

Go has an excellent set of image packages, but what do you do when you want to render 2D graphics? The golang freetype library implements nice anti-aliased rendering of paths, but is primarily for drawing text. So I built gg on top of it to provide a nice, general purpose 2D graphics API inspired by Cairo.

Features

  • Anti-aliased rendering
  • Fill and stroke paths
  • Draw images and text
  • Built-in word wrapping
  • Line caps, joins, dashes
  • Gradients and patterns
  • Transformation matrix
  • Push and pop context state
  • Clipping regions

Traveling Pixel January 2016

32 Go Graphics Optimization

Applying the traveling salesman problem to pixel art.

This code uses simulated annealing to find the shortest path to visit all black pixels in an image. Then it generates an animated GIF showing the order of traversal.


Line Art January 2016

2,317 Go 3D Vector

Rendering engine that produces 2D vector graphics (think SVGs) depicting 3D scenes.

Unlike OpenGL, where the output of the rendering pipeline is a rastered image, the output of ln is a set of 2D vector paths. It supports texturing, CSG, and more! I created this so I could plot 3D drawings with my pen plotter, which naturally requires vector input.


NES Emulator March 2015

3,857 Go Emulator OpenGL

Supports USB joysticks and has an awesome game selection screen.

I never had an NES as a kid, but I did have a Commodore 64. I played lots of games on it, including Mario ripoffs. Some of my friends had a Nintendo, so I did have some exposure and was always fond of SMB3. Writing an emulator sounded fun and now I can play old Mario classics whenever I want. And yes, it can generate animated GIFs!


Path Tracer January 2015

1,680 Go 3D Graphics

CPU-only, unidirectional path tracing engine written in Go.

This was the first thing that I wrote using Go and I've been loving it ever since! The inspiration for this project came from Evan Wallace's WebGL Path Tracing.

  • Supports OBJ and STL file formats
  • Supports textures, bump maps and normal maps
  • Supports raymarching of signed distance fields
  • Supports volume rendering from image slices
  • Supports various material properties
  • Supports configurable depth of field
  • Supports iterative rendering
  • Supports adaptive sampling and firefly reduction
  • Uses k-d trees to accelerate ray intersection tests
  • Uses all CPU cores in parallel
  • 100% pure Go with no dependencies besides the standard library