Region Quadtrees in C++

quadtree

(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++”

Experimental Tool for Removing Unwanted Artefacts in Textures

texture

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”

Poisson Disk Sampling Example Code

poissonI decided to put the Poisson disk sampling code here for download since the site that hosted it is down. The code accompanies the tutorial on Dev.Mag: Poisson Disk Sampling.

Download

poisson_disk_java.zip (184 KB)
poisson_disk_python.zip (912 KB)
poisson_disk_ruby.zip (59 KB)

15 Steps to Implement a Neural Net

neuron

(Original image by Hljod.HuskonaCC BY-SA 2.0).

I used to hate neural nets. Mostly, I realise now, because I struggled to implement them correctly. Texts explaining the working of neural nets focus heavily on the mathematical mechanics, and this is good for theoretical understanding and correct usage. However, this approach is terrible for the poor implementer, neglecting many of the details that concern him or her.

This tutorial is an implementation guide. It is not an explanation of how or why neural nets work, or when they should or should not be used. This tutorial will tell you step by step how to implement a very basic neural network. It comes with a simple example problem, and I include several results that you can compare with those that you find.

Continue reading “15 Steps to Implement a Neural Net”

How to Turn XSI Mod Tool into a Level Editor for your XNA Games: Example Updated for XNA 3.0.

xsixna_small_header1The example for the tutorial How to Turn XSI Mod Tool into a Level Editor for your XNA Games: Updated for XNA 3.0 have also been updated to work with XNA 3.0. The XSI plug-in has also been tested in the new Mod Tool (7.5).

Download

XSIModToolLevelEditor3.zip (5.2 MB).

Update: Reference for Functional Equations

1052727062_0ec2c67ea4_smallIn this new  version of Reference for Functional Equations I added several more z-transform pairs. I also started to add binomial transform pairs. The definition for the binomial is not consistent among different authors. I arbitrarily chose one, and later I changed it. I will probably change it again. Several typos were fixed. I am working on a system to include proofs so that the tables can be checked more easily.

Cellular Automata for Simulation in Games

header

A cellular automata system is one of the best demonstrations of emergence. If you do not know what cellular automata (CA) is, then you should go download Conway’s Game of Life immediately:

Conway’s Game of Life

Essentially, CA is a collection of state machines, updated in discrete time intervals. The next state of one of these depends on the current state as well as the states of neighbours. Usually, the state machines correspond to cells in a grid, and the neighbours of a cell are the cells connected to that cell. For a more detailed explanation, see the Wikipedia article.

Even simple update rules can lead to interesting behaviour: patterns that cannot be predicted from the rules except by running them. With suitable rules, CA can simulate many systems:

  • Natural phenomena: weather, fire, plant growth, migration patterns, spread of disease.
  • Socio-economic phenomena: urbanisation, segregation, construction and property development, traffic, spread of news.

Continue reading “Cellular Automata for Simulation in Games”

How to Turn XSI Mod Tool into a Level Editor for your XNA Games: Updated for XNA 3.0.

header

Last year I wrote a tutorial explaining how to use XSI Mod Tool as a level editor, specifically for XNA. Below is the same tutorial, updated for XNA 3.0. There are only a few minor changes:

  • You need not copy compiled assets from the batch file as before.
  • A section is included that describes how to use the content pipeline classes for easy reading of XML files (useful for level files, etc.).

I also corrected quite a few typos.
Continue reading “How to Turn XSI Mod Tool into a Level Editor for your XNA Games: Updated for XNA 3.0.”

A Reference for Functional Equations

1052727062_0ec2c67ea4_smallI have not posted in a while; one reason is that I got sucked into some interesting mathematics; the work-in-progress Reference for Functional Equations is the result. If you are interested in such things – have a look.

A simple texture algorithm – faster code and more results

header

Faster Code

A while back I wrote about a simple texture algorithm that I have been exploring. The Python implementation was very slow – so much, that I decided to implement it in C++ to see what performance gain I would get. Surprisingly, the C++ version is about 100 faster, if not more. I expected a decent increase, but what once took several hours can now be done in a minute!

Continue reading “A simple texture algorithm – faster code and more results”