Day 25: Four-Dimensional Adventure

The last day of the Advent of Code (in 2018 at least): Day 25. Not a day that I can really condone since real advent calendars end on the 24th, but since I got this far I might as well get my last gold stars.

The puzzle is to find the number of constellations made out of a number four dimensional points. A point belongs to a constellation if the Manhattan distance between two points are less or equal to three. Finding the Manhattan distance between the higher dimensional points is not particularly difficult, and neither was finding the constellations. Instead…

Visualising

…visualising these constellations would be a way to waste innumerable hours, especially because I decided to write some rendering code myself based on the scratchapixel tutorials. The rendering is described briefly in the rendering section below.

3D

The first visualisation shows all the points plotted in 3 dimensions with the constellations coloured according to number of points (blue: a few, red: many). This visualisation ignores the 4th dimension, except for calculating the Manhattan distance. The camera performs one revolution around the centre in 60 seconds.

4D

The second visualisation represents the fourth dimension as time, which is spanned out over the 60 seconds of the rotation around the centre. Only points which are within a distance of three points on either side of the current time are shown. Points around the current time at full brightness and points towards the start and end of the visible range are dim.

Rendering

The rendering is done using a simple wire-frame renderer implemented based on various articles in scratchapixel:

• https://www.scratchapixel.com/lessons/3d-basic-rendering/get-started
• https://www.scratchapixel.com/lessons/3d-basic-rendering/rendering-3d-scene-overview/perspective-projection
• https://www.scratchapixel.com/lessons/3d-basic-rendering/computing-pixel-coordinates-of-3d-point
• https://www.scratchapixel.com/lessons/3d-basic-rendering/computing-pixel-coordinates-of-3d-point/mathematics-computing-2d-coordinates-of-3d-points

In the videos above the 2D position for each point is calculated and then lines are drawn between points (between the projected 2D points) where the Manhattan distance of the 4D points are within 3 units of each other. This means that lines between points do not necessarily cross each other correctly and there is no visible indicator (e.g. size) that one line is closer than another. The points are finally drawn on top of everything else (again, same size and generally with complete disregard for distance to the camera). Since the camera rotates around the centre of the scene there is a perception of depth.

The videos are rendered in glorious 4K (because, why not… though I skimped on the HDR, sorry) and encoded using ffmpeg H.265. To avoid unsightly temporary PNG files hanging around, all the frames are piped from the rendering program to ffmpeg.