A generator (as I will use the term here) is an object that can “generate” other objects on demand. They work like random generators, except that they need not generate numbers or do so randomly: you ask it for the next value, and it gives it to you.
The naive generator is simply a class that supports this method:
Generators work a bit like iterators, but they are slightly different:
- Iterators work on both finite and infinite sequences, while generators are always (supposed to be) infinite.
- Iterators are typically used in loops to process elements in sequence on the spot. Generators are generally use over some time span (similar to how random numbers are often used in simulations).
- Iterators are usually restarted on each use; generators are rarely restarted.
Continue reading “Generators”
A while back I developed a mild obsession with pentagons (mathematical ones, not symbolistic!) It started when I discovered some beautiful (simple and to me, unknown) theorems of quadrangles, such as Varignon’s theorem. I already came across Miquel’s pentagon theorem, and wondered what other gems I could find.
Here is what I found: Pentagons (2.4 MB PDF).
My search was on the surface a bit disappointing: pentagons as such are not widely studied. I guess it is because some more general theorems (that apply to general polygons) contain the theory, and the specifics as applied to pentagons are not so interesting.
Nevertheless, I did discover a few theorems, and the journey took me into some very interesting corners of geometry; a very rewarding experience. I started to collect these into a document, which is shared below. It’s not comprehensive or complete; there are a few gaps.
(At some stage I may return to look at this again. In particular, there are many theorems of the type “if there is n, there is n+1”, which seems to me to hint at a very general theorem which can be used to prove a bunch of specifics.)
Also, when I started, I did not realise how many of the theorems will generalise to general polygons, so the collection looks a bit silly in retrospect (kind of like listing all the properties of the number 8 that equally apply to even numbers).
Even so, what’s done is done, and can perhaps satisfy someone else’s curiosity.
Continue reading “Pentagons”
A while back I needed to implement fast minimum and maximum filters for images. I devised (what I thought was) a clever approximation scheme where the execution time is not dependent on the window size of the filter. But the method had some issues, and I looked at some other algorithms. In retrospect, the method I used seems foolish. At the time, I did not realise the obvious: a 1D filter could be applied to first the rows, and then the columns of an image, which makes the slow algorithm faster, or allows you to use one of the many published fast 1D algorithms.
I wanted to write down my gained knowledge, and started to work on a blog post. But soon it became quite long, so I decided to put it into a PDF document instead. You can download it below.
Continue reading “2D Minimum and Maximum Filters: Algorithms and Implementation Issues”
This is a substantial update of this reference document. The most important addition is the chain and substitution rules for arithmetic difference calculus (ADC). Other additions include: more properties of the discrete power function, more properties of ADC operators, definitions of analog functions, and ranges of convergence of (some) z-transforms. I also corrected some errors that were discovered since the last version.
Grab it here.
I have updated the Reference for Functional Equations. I have added several entries to the tables, updated the graphs, added some new graphs, added some explanations and additional notes on notation, corrected a few typos, and re-organised the document slightly. Get the new version here.
(Original Image by Valerie Everett)
It is sometime necessary to move an object in a physics simulation to a specific point. On the one hand, it can be difficult to analyse the exact force you have to apply; on the other hand it might not look so good if you animate the object’s position directly.
A compromise that works well in many situations is to use a spring-damper system to move the object.
The trick is simple: we apply two forces—the one is proportional to the displacement; the other is proportional to the velocity. Tweaked correctly, they combine to give realistic movement to the desired point.
Continue reading “A Simple Trick for Moving Objects in a Physics Simulation”
(Original image by GoAwayStupidAI).
Below are four C++ implementations of the region quadtree (the kind used for image compression, for example). The different implementations were made in an attempt to optimise construction of quadtrees. (For a tutorial on implementing region quadtrees, see Issue 26 [6.39 MB zip] of Dev.Mag).
- NaiveQuadtree is the straightforward implementation.
- AreaSumTableQuadtree uses a summed area table to perform fast calculations of the mean and variance of regions in the data grid.
- AugmentedAreaSumTableQuadtree is the same, except that the area sum table has an extra row and column of zeros to prevents if-then logic that slows it down and makes it tricky to understand.
- SimpleQuadtree is the same as AugmentedAreaSumTableQuadtree , except that no distinction is made (at a class level) between different node types.
Continue reading “Region Quadtrees in C++”
When implementing image algorithms, I am prone to make these mistakes:
- swapping x and y;
- working on the wrong channel;
- making off-by-one errors, especially in window algorithms;
- making division-by-zero errors;
- handling borders incorrectly; and
- handling non-power-of-two sized images incorrectly.
Since these types of errors are prevalent in many image-processing algorithms, it would be useful to develop, once and for all, general tests that will catch these errors quickly for any algorithm.
This post is about such tests.
Continue reading “Catching Common Image Processing Programming Errors with Generic Unit Tests”
*Fast = not toooo slow…
For the image restoration tool I had to implement min and max filters (also erosion and dilation—in this case with a square structuring element). Implementing these efficiently is not so easy. The naive approach is to simply check all the pixels in the window, and select the maximum or minimum value. This algorithm’s run time is quadratic in the window width, which can be a bit slow for the bigger windows that I am interested in. There are some very efficient algorithms available, but they are quite complicated to implement properly (some require esoteric data structures, for example monotonic wedges (PDF)), and many are not suitable for floating point images.
So I came up with this approximation scheme. It uses some expensive floating point operations, but its run time is constant in the window width.
Continue reading “Simple, Fast* Approximate Minimum / Maximum Filters”
Many textures used for 3D art start from photographs. Ideally, such textures should be uniformly lit so that the texture does not interfere with the lighting applied by the 3D software. Often, lighting artefacts must be removed by hand. This can be tedious and time consuming.
The tool provided here aims to automate this process. It is still in an experimental phase, so it is very crude. Below you can see some of the before and after pictures.
Continue reading “Experimental Tool for Removing Unwanted Artefacts in Textures”