|  | Today I sat down and, in typical fashion, designed the layout for this site instead of what I was actually supposed to be doing. I even did it with an unholy mix of <table> cells and CSS to be a really rebellious little dirtbag. Since I can't say no to a cute xeyes imitation and this page (somehow) looks pretty clean it will replace Idiot Hut until I put together something a bit less sucky, hopefully using those CSS grid thingys. |

| # K-means clustering video encoder progress |
--- | --- | ---
| Original demo by Onslaught, click here to see this production's page on Pouet. | We all know that one bad apple is enough to spoil a bunch so it's fitting that Bad Apple has managed to spread its contagious beat everywhere it might just fit as well as a few places it doesn't have any right to. The ~170 kB of a 5¼" Commodore 64 floppy disk is one of those places thanks to the work of demoscener Algorithm on his Bad Apple port to the system. In the comment section of the demo's Pouet page he writes that the primary form of compression used was vector quantization. The original video's frames, downscaled to the C64's resolution, were divided into 16x16 pixel blocks that were then each mapped to their most visually similar counterpart out of a smaller library of only 256 blocks. |
| Since replacing graphics with ones that look "close enough" is an inherently lossy process, he took a genetic approach to iteratively adjust the library until total introduced error was sufficently minimized. He then coupled this with a few forms of lossless compression like inter-frame delta encoding and LZ packing. The end result of these measures was that each frame of the final video only took up about 70 bytes and 2200 frames total were packed on to the disk. |
| Inspired by his efforts, I've decided to develop a successor to my previous two video encoders for the TI83+. |
| The first was very rudimentary and would only directly downscale and quantize each frame in a given input sequence; the program was so crudely assembled that the extraction of frames from an input video called for the use of a separate, external utility. The resolution of its output would be so low that it would fall below that of the calculator itself, each pixel big enough to be represented by one of four dither patterns. While such drastic measures naturally yielded high compression ratios, they were so lossy that only the most general of details could survive them. |
| The second encoder sacrificed color depth for increased visual detail while introducing a slightly more sophisticated form of compression. Matching the resolution of the calculator's display came with the limitation of also matching the number of bits per pixel it supports: one. This did, however, have the useful side effect of improving the efficacy of run-length-encoding (RLE) based compression, assuming a heterogeneous distribution of white and black pixels, by allowing a typical frame to be represented by fewer (value/# of repetitions) pairs, or "tokens". The program's GUI provides brightness and contrast settings to help any hapless user in better achieving this condition. This particular implementation of RLE additionally allows a token, called a "nodraw" token by source code comments, to designate its pixels as unchanged from their counterparts in the previous frame. When selecting token types, the encoder has a preference for those yielding longer stretches of pixels. |
| First attempt | Second attempt |
| To improve the color depth of full resolution (96x64) frames from the device's native 1 BPP to 2 BPP we may leverage the slow response time of its LCD. If we constantly toggle a display element on and off at a fixed frequency it will never appear fully set or reset but, to the viewer, exist in an intermediate "gray" state. To have some control over which shades of gray different pixels appear to display we can keep them set, once put into that state, for varying numbers of calls to, or "ticks" of, a clock-triggered interrupt service routine (ISR) before they are reset again, more ticks corresponding to darker shades. The maximum number of ticks a pixel may be set for a given frame may be thought of as the drawing proccedure's "grayscale flicker period". This page and this other one on WikiTI have more information regarding the TI83+ I/O ports that control which timers are enabled and at which frequency they operate, respectively. |
| Illustration of how ISR ticks may be used to alter the duration for which a pixel stays set in a single period | Unfortunately this technique tends to highlight another major limitation of the hardware. There is no way, short of the user manually adjusting an artificial delay appended to the start of the ISR, to synchronize our writes to the LCD's video memory with its own screen refresh cycle; no signal or interrupt alerts us to this event. This memory will routinely be displayed before we are done writing to it, resulting in screen tearing and inconsistent pixel set/reset timings. A method of hybrid spatial and temporal dithering outlined by Runner112 of Omnimaga makes these anomalies less noticeable by only setting some pixels of a particular gray level at a time instead of all of them at once, distributing error. |
| Given a flicker period of four ticks, a repeating four-pixel pattern (represented by a small "pattern mask") can be cycled through its four possible translations on the screen to simultaneously guarantee that every pixel is set/reset for the correct amount of time every period and always maintain a relatively homogenious distribution of set and reset pixels across the screen on any given tick. If a color depth of 2 BPP is targeted then each frame may be represented using two bitplanes. Their bitwise XOR yeilds a bit mask , or "application mask", of every pixel to which the pattern mask should be applied as pixels assigned 0x11 or 0x00 will be completely filled in or blank, respectively, throughout the entire flicker period. A bitwise AND of the application mask with either of the original bitplanes will produce masks for applying light and dark variants of the pattern mask, specific to pixels assigned 0x01 and 0x10, respectively. To make the most effective use of the Z80 ISA, register pairs to use for these boolean operations may be freed up with techniques such as employing self-modifying code to store the states of loop counters within the machine code that references them. |
| Animated demonstration of the concept, note the horizontally shifting vertical lines caused by a suboptimal spatial distribution of set/reset bits | Detail of the translations of the 75% and 25% darkness patterns |
| To extract frames from as many input video formats as possible, libavcodec will be employed to identify a given file's container format and video codec as well as perform the appropriate demuxing and decoding. In order to decode the correct incoming packets (only video, not sound, will be supported) from the demuxer, they must be filtered by stream index, the desired one of which may be easily found through the API call av_find_best_stream(). |
| Illustration of how audio/video frames are encoded into packets identified by stream index and muxed into a container (credit igalia.com) |
| Libswscale will be used for converting decoded frames into a grayscale pixel format since the one they are in, as returned by the decoder, is decided by the video's codec. The library additionally handles the scaling of frames to the calculator's resolution before they are split into tiles. In an unsuccessful attempt to change the pixel format of decoded frames from their default format of YUV, typical of MPEG4 videos, into BGR32 the three channels of the former were, inadvertently, directly mapped into those of the latter. While the input luma (Y) formed a coherent image in the target channel B, U and V formed in G and R two distinctly shaded, low-resolution images resembling Y. This mildly noteworthy artifact is presumably attributable to chroma subsampling in the input U and V channels. |
| The decoded test frame's B, G, and R channels, from left to right. Note the normal appearance of B |
| Libswscale supports grayscale frames with a minimum of eight bits per pixel (AV_PIX_FMT_GRAY8) while our program is to operate on frames with two bits per pixel. One way of recovering information that would be lost in direct quantinization is simply first adding random noise to the input pixels' intensity values. Whether their corresponding output intensities are shifted up or down a level, or not at all, will be influenced by both the noise function itself as well as the input intensities' distances from the nearest values mapped to lighter and darker output levels. This can be expressed in the below formula, where c is input pixel intensity, c' is output intensity, r is "spread" that defines the domain of the injected noise as [-r/2,r/2), n is the width of M divided by two, and M is an array of evenly distributed, by size, random fractions between 0 and 1 known as a Beyer matrix. Since the definition of M allows for matrices larger than 2x2 to be recursively defined in terms of M of lower n, the current version of the dithering code allows the user to specify their desired matrix dimensions. |
| (credit Wikipedia) |
| The use of floating-point math in applying the Bayer matrix may be eliminated, in much of the same vein as in Bresenham's line algorithm, by multiplying both terms inside the quantinization function by 4n2. The only adjustment required for this to work is to alter the input domain of quantize() to 255*4n2. The results of the right term within quantize() may additionally be precalculated and cached for each element of M. The below formula assumes an r of 64 (for 8 bpp to 2 bpp conversions). |
| (credit Wikipedia) |
| Another common information recovery technique is to compensate for the quantinization error introduced by one pixel's color reduction by adding varying fractions of it onto its surrounding neighbors. The program is planned to support Floyd-Steinburg dithering which employs the error diffusion scheme illustrated below. |
| (credit Wikipedia) |
| Any potential real-time application of this technique, such as streaming video, that wishes to speed up the process by employing parallel processing will have to contend with the fact that most output pixels will be dependent on the results of processing other output pixels. One way of remedying this is allowing threads of execution to use flags/semaphores to inform other threads that their results are ready, as was done in this article. |
| Original frame, ordered-dithered frame, and error-diffusion-dithered frame from left to right, respectively |
| The primary form of compression that this program is to employ is vector quantinization through Lloyd's algorithm. Both input and output videos are understood as a sequence of "samples", which may be interchangably thought of as a string of N pixels or a point in N-dimensional space. The library of samples used for constructing frames during playback will be called the "dictionary"; output videos' data should mainly be a list of indices, themselves possibly compressed through huffman coding, into the relatively small dictionary. The dictionary is initialized as a random selection from the "observation library", or the full list of samples observed across the duration of the input video. | Animated example of Lloyd's algorithm (credit Wikipedia) |
| Each sample in the observation library is mapped to its closest counterpart, by distance, in the dictionary. The average position of the samples mapped to a given dictionary entry will then replace that entry for the next iteration of the algorithm. The previous two steps are repeated until the mapping becomes fairly stable, though not necessarily at the global minimum of S, the sum of distances between every observation library sample and its corresponding dictionary sample. While this algorithm has much faster alternatives, it will be adequate for the intents and purposes of this program as the preprocessing it performs does not take place at video runtime. |

| # Spinnin' Donuts |
--- | --- | ---
| While I'm on a Yabasic kick I think now would be an opportune time to dust off another one of my rendering toys made using the language (and all the limitations that come with it): a gouraud-shaded torus spinning on the screen at a frame rate above a PowerPoint slideshow. Besides employing common-sense optimizations like generating the mesh once and continually applying a precalculated transformation to it every frame, I had to wrangle with a few of Yabasic's unique quirks like its slow execution of subroutine calls and rendering primitives that live up to the name "primitive". Below is a dramatic visual comparison of how the program ran before and after tweaking: |
| Optimized code | Unoptimized code |
| The change that was the least clever yet most impactful on performance was replacing all frequent subroutine calls (the biggest offender was the one for finding dot products) with copies of the subroutine itself. My vague, uneducated guess is that this slowdown pertains to the memory operations involved in pushing and popping the Yabasic equivalent of stack frames. For this very reason I had to rewrite the function for sorting the donut's polygons, itself a necessity due to Yabasic's lack of a Z-buffer, to execute iteratively instead of recursively. To properly sort the faces they, being made up of four vertices each, had to be distilled into single points with single distances from the viewer. This was possible because the overall mesh is built by revolving a circle of vertices about a coplanar axis, producing trapezoids when connected into faces. The centers of these trapezoids are suitable for use in distance sorting and can be easily found from the intersection of the trapezoids' diagonals. Backface culling was also implemented. |
| Three frames of the torus animation being constructed: yellow lines represent the faces' normal vectors while the blue ones span across their diagonal lengths | Determining lighting intensity at a vertex subjected to a given light source was only a matter of finding the dot product between that vertex's normal and the spatial difference between it and the light source. To furnish the former of these two vectors we simply calculate the average of the normal vectors of the vertex's four surrounding faces. The contributions of every light source are then summed and clipped into the RGB888 format. |
| Credit for the Win 32 port of the Playstation 2's particular dialect of the Yabasic Interpreter goes to James Shaw and Pieter-Bas IJdens (the original was written by Marc-Oliver Ihm). A copy of it may be downloaded from this server using the following link, the GPL license that this program was distributed under may be downloaded with this link. This link may be used to download the speed-optimized variant of the torus spinner while this one links to the slower, more readable one. One interesting observation is that when running the programs with ps2yabasic.exe in my curent environment, subroutine calls are much, much less prohibitively expensive and, ironically, donut-slow actually runs a great deal faster than donut-fast. |

| # Yabasic BSP renderer progress |
--- | --- | ---
| The demo in action: sloped ceilings/floors and working boundaries between subsectors with different floor/ceiling heights | In 2000 Sony attempted to circumvent import duties on game consoles shipped to the UK by arguing that the PlayStation 2 was, in fact, a home computer. This argument was predicated on the fact that it came bundled with a BASIC interpreter not too dissimilar to those that came with the PCs of yesteryear. After a five-year long legal dispute it was decided that this definition of a personal computer, much like Thatcherism, was a relic best left in the past. No rebate was paid to Sony to cover the 6.60 Pound duty... that had steadily dropped into irrelevancy while this was all going on. |
| To prove Yabasic's suitability as an IDE and rectify this miscarriage of justice we must answer one essential question: "can it build Doom?" Yabasic, like many dialects of BASIC that came before it, supplies its users with some very helpful rendering functions to draw graphic primitives such as rectangles, circles, and, crucially, triangles. The catch is that rasterising triangles is ALL we can do directly. For proper 3d rendering we have to perform the relevant rotation/projection transformations, occlusion culling, and frustum clipping manually ourselves. Thankfully for us Doom's rendering engine was built with specific limitations to simplify as much of this as possible. For one, each map is made up of two-dimensional lines segments (segDefs) grouped into convex shapes (subsectors) that are "extruded" vertically to form the world's walls. Since the base of every subsector is convex we don't have to worry about the order in which we draw its walls since they'll never visually overlap, saving us from having to do constant, expensive sorting operations. |
| Doom's most famous optimization assigns different partitions (in front of and behind different 2d "splitting" planes) of the world to nodes in a binary tree (hence "Binary Space Partitioning"). The tree's leaves represent individual subsectors so we may perform binary searches of it at runtime to quickly determine the subsector containing the player for initiating rendering. Once we're done rendering the player's subsector we typically find that the entire screen has not been filled in; segDefs may at most be partially drawn if they connect two subsectors for mutual visibility between them. | the inevitable result of trying to render a concave subsector (credit: Bisqwit) |
| The best candidate for the next subsector to draw is the other child of the current one's parent node (or its children if it itself is a spliting node) as we know for sure that it (or they) will be visible through the partially drawn segDef. We repeat this process on successive parent nodes' children until drawing of the entire horizonal span of the screen is completed. The progress of this process can be represented as single number (X-pixels drawn vs total X-span) as the walls in Doom are always perfectly vertical. This fact also makes clipping partially occluded walls and culling away entirely occluded ones as simple as comparing/shifting horizonal screen coordinates. |
| Illustration of the organization of subsectors in a BSP tree (credit: Wikipedia) |
| Applying rotational transformations is also just that little bit cheaper because the player only ever rotates on one axis (left to right) in the game's original release and sourceports highly faithful to it. Additionally, near-plane frustum clipping can be implemented by just truncating away the parts of walls that fall below the near-plane after translation and rotation. |
| The first map of Doom split up into its constituent sub sectors (Credit: doomwiki) | In the program's current state, the rendering of subsectors and the interfaces between them is fully functional and complete with varying floor/ceiling heights, not only between subsectors but within them as well. The debugging graphics visible in the above clip demonstrate that the code to find the player's world partition is also fully complete, it has just not yet been integrated into the rendering process. At the moment the player is simply always assumed to be in subsector zero and the world is always drawn from that perspective. |