Thursday, 28 July 2016

An Abstract Algorithm To Augment Alpha'd Atlases

Texture atlases are routinely used to improve rendering performance (fewer texture swaps) and reduce memory footprint (especially on power-of-two-texture hardware).

In the specific case where textures are irregular sprites with an alpha channel (for 2D games and UI elements), there is an opportunity to save additional memory by eliminating most of the redundant blank space around the edges of the images.

Normally this is done by hand, if it is done at all: manually placing images within a larger texture and then defining irregular polygonal areas for each sprite. This can become burdensome if the number of images is very large or images change frequently.

The algorithm described here achieves significant savings (around 25% of total texture space on a sample commercial mobile app) without any user input and without excessive processing.

Outline

  • For each image you want to add to the atlas:
    • Find the initial bounding rectangle within the original image. This is how much room the image would take up if committed to the atlas unchanged.
    • Find the left and right extents of every horizontal line of the image.
    • For every possible horizontal slice you could take out of the image (ie, every possible y_top and y_bottom that you could cut across in order to extract a slice)
      • Estimate the savings that would result if that slice were extracted and the empty space at either end cropped.
        • Because atlasing images requires that a pixel gap be left to prevent bleeding, reduce each estimate by the number of duplicate pixels needed.
    • Then, while savings remain to be made:
      • Find the best remaining slice (the one that saves the most memory if extracted on its own)
      • Examine every combination of two contiguous slices (ie, <y_top to y_middle> and <y_middle to y_bottom>) that would together cover that 'best slice', and find the most memory-saving combination (if there is one).
      • Take whichever is the most memory-saving individual slice of that 'best pair'
      • Mark that vertical span of the image as 'done'.
      • Repeat until no further savings can be made.
Once you have your slices, add them to a master list and feed them (rather than the original images) into a standard texture-atlasing algorithm. It's then straightforward to auto-generate geometry that stitches the image back together from its parts. The example below uses wireframe to illustrate how a rectangular image (of a shopping basket) is automatically broken up into smaller, individually atlased sections and then reassembled at render-time. The yellow area is background and not part of the atlased image.


In practice, the overhead of transforming the extra geometry is (especially on hi-res mobile platforms) more than compensated for by fill-rate savings.

Other Considerations

  • Slices of an image should ideally all be kept together on the same atlas, which does require extra computation (since atlasing algorithms usually sort input images by height, which tends to mix all your image slices up together and then spread them across however many atlases you end up using)
  • As well as the 'duplicate pixel' cost of splitting an image, you must also factor in the memory consumed by the extra geometry (which will depend on your implementation).
  • If you wish, you can further decrease estimated savings by a 'transformation tax', to represent the performance penalty of transforming additional vertices versus savings in fill rate.

Thursday, 3 March 2016

Self-Existence

Two options are under consideration for self-existence: a being/God, and the energy level of the universe. It is not claimed that the latter is fully understood, but that it is the more worthy avenue of investigation.

Knowns to account for:

  • Conservation of Energy
  • The singularity (the beginning of time)
Note: Conservation of Energy (CoE) is an observed truth in this universe, not a logical necessity of all universes. It's easy to simulate worlds that violate CoE. Also note that 'violating CoE' does not logically mandate heading off to infinite or zero energy, merely that it can fluctuate.

Candidate 1: A Being

  1. Assumed to be capable of choice.
  2. Assumed to be pure actuality, with no potential. (How is this compatible with 1?)
If there is choice involved, it ought to be justifiable. Why should time and space begin at a singularity, and why should conservation of energy be so strictly observed, to the point where the environment we inhabit is fully dictated - and greatly restricted - by extrapolation from both? By way of illustration, the amount of stuff in the observable universe, if arranged more agreeably, abandoning the superfluous causal chain from singularity and CoE and imposing a straightforward 'Minecraft' style system of downward gravity and impenetrable bedrock, would yield a habitable environment (conservatively) two thousand billion billion billion times the surface area of Earth. CoE also mandates hunger, thirst, limited resources. It pits life against itself and creates the food chain - the most abominable feature imaginable in any universe.

If the bible is to believed, God can cause CoE to be violated. So we are left with an unanswerable question: why choose to violate it in those specific, trivial ways, when so many better options for existence are available to someone with that power?

Candidate 2: Energy

  1. Assumed to be incapable of choice.
  2. Assumed to be pure actuality, with no potential.
Obviously, we get conservation of energy for free, as it's merely a restatement of the premise.
In this scenario, existence is inevitably all and only states in which energy is conserved.

Does our existence require energy to 'choose'?


No. All possible states that conserve energy exist. This also tallies with the implications of Quantum Mechanics.

Is energy obliged to change?

No. The set of all states in which energy is conserved is static and unchanging. This multidimensional 'sculpture' of states is characteristic of energy that is being neither created nor destroyed. To put it another way, it is the only shape that energy that is neither created nor destroyed can have.

What about the singularity?


This is where things get really interesting. The existence of the singularity is mandatory, as it belongs to the set of states where energy is conserved.

More than that, the conundrum of causality evaporates. Rather than imagining history as a hierarchy of effects, descending a ladder resting on mysterious darkness beyond, we can imagine instead taking a journey to the North Pole. There is nothing to stop us continuing to walk in a straight line when we get there, but all directions from the north pole necessarily lead south.

So it is with the singularity. It's just part of the set of existence, one of many allowed and thus mandatory states, surrounded on all sides by other states. To 'go back in time' is to approach it in our imagination from the vantage point of this 'slice' of existence. There is no end to be found there, no inexplicable nothingness 'beyond'. All 'directions' are available for us to travel - it is simply that if we do so we are obliged to depart the singularity state. It should not be visualised as an extremity, but as the centre. It is not the 'causal seed' of the states around it, it simply must be there and 'where it is' based on CoE.

Summary


  • God doesn't explain the singularity or strict conservation of energy.
  • Observed 'choices' are inexplicable and lead to unnecessary suffering, inequality and poverty, and a universe in which life is only just barely not impossible.
  • Does not provide a basis for the 'causal ladder' view of history anyway, begging the question of why the rest of the ladder is even there.

  • We can see and test that the existence of energy is non-contingent: no event can create or destroy it.
  • We can see and test that all states conserving energy exist and interlock (see slit experiments)
  • The seeming tendency of energy to change is an illusion created by the way we are observing it. Conceived as a whole, the overall 'form' of energy is static and eternal.
  • Eliminates the 'causal ladder' conundrum. The singularity is surrounded on all 'sides' by other states. It is the state of lowest entropy; the centre of existence, not an extremity.

Wednesday, 4 February 2015

Open Letter to Krish Kandiah (Christian Today)

In your article responding to Stephen Fry's televised comments, you confessed your initial anger at his description of god as capricious, mean-minded and stupid. That's understandable, but what may surprise you is the anger the rest of your article kindled in me as an atheist.

You didn't set out to insult anyone, of course, and I am sure even now you do not think you did. But in a way that's precisely what's so aggravating. Allow me to explain:

1. You leverage compassion to forestall your readers taking criticism seriously.


Your words:

"But then I caught myself. Perhaps Fry has lost someone close to him with bone cancer and he needs my sympathy and care for his grief rather than my offence?"

This has been a bad habit of many Christian apologists I've encountered: faced with unpalatable criticism you begin by attributing it to an irrational motive. You play down the need to mount a robust intellectual defence, and get to give yourselves a little pat on the back for being so understanding and sympathetic.

Obviously there are times when it's right to make allowances for the emotional state of others. This is not one of those times. It is disrespectful to imply that Fry's judgement is clouded simply because you don't like what he has to say.

2. You paint likable atheists as closet Christians by twisting their words and misrepresenting atheism.


"Atheism has no response to the outrage you feel...For Dawkins, atheism's answer to the problem of suffering is basically 'Tough luck. Bad things happen. Deal with it.'" 

The intended implication is that, since two prominent atheists have such different views, at least one of them can't be comfortable in his atheism. This is deeply and, so far as I can tell, deliberately misleading.

Firstly, Dawkins is describing how things are, not how it should make us feel or what we should do about it. Atheism is not scornful of sympathy or empathy. Its answer to suffering is not as you describe. Rather it says: "Terrible, unfair things do happen, and if we want them to stop it's up to us. There is no grand, secret plan to magically keep us safe, no rapture waiting to bail us out of our debts, no comfort to be found in the death of a child other than the knowledge that, thanks to our efforts, it will happen less often tomorrow. We must care for each other because there is nobody to do it for us."

Secondly, Fry isn't outraged. He was speaking to the hypothetical circumstance in which he is presented with a god. In that case alone he would consider the existence of undeserved misery evil and monstrous, rather than merely an unpleasant reality. His moral outrage was not directed at the existence of bone cancer or parasites, but at the idea of a god who creates or permits them to exist. It is dishonest of you to conflate the two in an attempt to appropriate a popular public figure and outspoken atheist for the Christian cause.

3. You imply that atheists are just Christians who haven't thought things through properly.


I refer here to CS Lewis, and the quotation you provided. Lewis presents an interesting and subtle logical argument, which can be illustrated thus:

Imagine there's a fatal disease that's known to afflict half the population. There is a blood test available, which is 90% accurate if you have the disease (it will only give a false negative 10% of the time). But there's a catch: the test is thought to be only 1% accurate if you don't have the disease (it gives a false positive 99% of the time).

This means that, of every 11 people who get the 'good news' of a negative result, ten of them will actually have the disease and only one will not. A negative result is, perversely, a strong indication that you have the disease!

Lewis proposes an analogous scenario: he argues that in the absence of a god to define his morality he would be overwhelmingly likely to accept the world, warts and all, as fair and just. On the other hand, if there is a god, Lewis's sense of injustice could be a misfire: a failure to understand god's plan. On balance, then, the most likely explanation for his outrage is that there is a god.

Lewis was a smart guy, and his logic is sound. But his conclusion is only correct if it is indeed true that, lacking divine inspiration, we would surely fail to perceive nature's lack of justice. What Lewis could not anticipate was the discovery, a decade or so after his death, of the means by which our sense of morality would inevitably evolve, even unguided.

I'm speaking of stable strategies in game theory: the inexorable tendency for groups to converge on particular cooperative behaviours. The existence of these 'moral attractors' - objective truths about successful cooperation that closely match our actual morals, such as the Golden Rule - invalidates Lewis's assumption that a godless humanity would tend to see an indifferent universe as right and fair. On the contrary: it is inevitable that successful societies would sooner or later recognise the absence of natural justice, reversing Lewis's conclusion.

4. You invoke original sin, which is an insult to anyone's intelligence.


"At the heart of the Fry's argument is the idea that the world that exists is as God intended it to be. He assumes that God deliberately created a universe with appalling undeserved suffering. But a central doctrine of the Christian faith is that God created a good and perfect world and after the fall of humanity nothing is fully as it should be. To blame God for natural disasters and childhood cancer is like blaming the landlord after tenants have trashed their house."

The concept of original sin is ludicrous. It's an example of what you get when you apply Sherlock Holmes's famous maxim to the wrong impossibilities.

Firstly, what's the mechanism by which our actions brought these specific maladies into being? Walk me through it. Explain how our disobedience caused the continents to start rubbing against one another, while god stood by and wrung his hands. No? Well, perhaps you can describe the domino effect we set in motion that spawned the malaria parasite. Really? Nothing? Then what exactly do you mean when you claim we caused these things, that we brought them on ourselves? If I kick a hole in the wall of my flat, I wake up the next day with a sore foot in a flat with a hole in the wall. I don't wake up with AIDS. That would not be a consequence of my actions; it would be a punishment for them.

But OK, let's suppose for a moment there was an Adam, and he was naughty and had to be punished. Who made up the rule that his offspring should also suffer? What kind of landlord would insist my children and grandchildren also hobble around on sore feet? With AIDS? Again, that decision was entirely down to your god.

Given that god decided to execute Adam and Eve as punishment, despite having created them incapable of knowing right from wrong (and despite the fact their first impulse upon learning the difference, according to the bible, was to try and correct their mistakes), surely it would have been more humane to simply kill them and start over. Maybe plant the tree in a corner this time; hide it behind some trellis. Or on, you know, the moon. He could have done that easily, as often as necessary. But no: he decided that what ought to happen is that billions of people would suffer for a mistake Adam and Eve couldn't even know they were making. I can just feel the love, can't you?

In fact, there is really no way in which the alleged fall of humanity is comparable to tenants trashing a rented property. Here's a true analogy:

A man opens a day-care centre. Then he digs a pit in the middle of the floor and lines it with broken glass and used syringes. He covers it with a colourful activity mat and adds a cuddly toy that dares anyone who wanders past to hop on and play. Then he warns the kids once not to play on the mat, and leaves them to their own devices. Later, when the first toddler falls in, he shrugs and says "He was warned. He brought it on himself." Then he pushes all the other kids into the pit and sprays them with anthrax.

That's the story of Genesis.

If there's one genuine truth this 'central doctrine' of Christianity reveals, it is the scale of the problem the obvious indifference of the universe presents to your narrative of a loving god. You must be truly desperate to clutch at such a straw.

Final thoughts.


By comparison, the atheist perspective appears almost shockingly sane and straightforward. Life takes the form it does - the only form that could plausibly evolve unsupervised - because it did evolve unsupervised. We have these morals because they demonstrably work better than those morals. We detect no pattern of justice overlaying the vagaries of nature because there is none to detect. The world is exactly as it appears, and it is endlessly amazing.

See how simple it is? No need to bypass critical thought by indoctrinating children. No agonising over whether humans without penises are worthy to occupy this or that ceremonial position, or which arrangements of protons, neutrons and electrons god has randomly declared unclean. No tormenting ourselves with imaginary guilt. Just an acceptance of responsibility for each other and the future.

Saturday, 17 January 2015


Why You Should Vote.

1. Because otherwise, political parties only have the votes of extremists to chase.

Look at what happened when UKIP gained traction: most of the major parties promptly fell over themselves trying to appear as UKIP as possible. UKIP showed there was a part of the population whose vote is up for grabs if you pander to their extreme views.

The major parties wouldn't have chased those votes if they thought they had a large, moderate core vote they might alienate in the process. But they don't. Consequently, Nigel gets his leery, beery mug splashed across national media as a 'man of the people', when nothing could be further from the truth.

2. Because there's no such thing as a wasted vote.

All votes matter, because it's not just about this election. It's about the next one, and the one after that. As a moderate voter, you're in it for the long haul.

Your vote may not change the outcome this time. But it will be part of the numbers all the parties look at when considering future policy. So vote Conservative, or Labour, or Green, even if they can't win, because by doing so you're announcing to the party that does win: "I have a vote for you to chase."

Even if you really can't choose a 'least bad' option, even if you vote entirely at random, it makes a difference. Why? Well, compare these results:

Con: 4000
Lab: 2000
Green: 600
Lib: 500

with these:

Con: 8000
Lab: 6000
Green: 4600
Lib: 4500

The difference is 16,000 moderate voters voting at random. Looks like a closer race, doesn't it? I'd expect the Conservative and Labour parties to be much more interested in courting the Green and Liberal vote next time around - which means policies that are more attractive to moderate voters like you.

Moderates voting at random is even better if there's an extremist party like the BNP or UKIP involved, because you'll help keep those extremists out of government. Compare:

UKIP: 4500
Con: 4000
Lab: 2000
Green: 600
Lib: 500

with:

Con: 8000
Lab: 6000
Green: 4600
Lib: 4500
UKIP: 4500

Same story as above: 16,000 moderates voting at random but not for UKIP.

That's the great thing about being the silent majority (as non-voters have been in recent elections): you don't have to vote tactically to affect the outcome.

You just have to vote.