Geometric Algebra Pitfalls

After studying more than I expected to during the holidays, I believe I have finally got my wits together and can now give some clear hints to anyone else who wishes to travel this path.  I highly suggest "Linear and Geometric Algebra" by Alan Macdonald.  Read the previews and details online before considering to purchase this book.  I like it, doesn't mean you will too.

First, and most importantly, write out your multi vectors explicitly.  For example, vector (2, 3, 4) should be written as 2e₁ + 3e₂ + 4e₃.  Recall the multiplication of the e's (or basis as that is what they form) is not associative.

Consider (1e₁ + 2e₂)(3e₁ + 4e₂).

Intuitively, from the good ol' days, we would do: (1e₁3e₁ + 1e14e2 + 2e₂3e₁ + 2e₂4e₂).

Regrouping the scalers together: (3e₁e₁ + 4e₁e₂ + 6e₂e₁ + 8e₂e₂)

Since e₁e₁ = 1: (3 + 4e₁e₂ + 6e₂e1 + 8)

Switching the place of two adjacent e's flips the sign, ie. e₁e₂ = -e₂e₁: (3 + 4e₁e₂ - 6e₁e₂ + 8)

Final grouping: (11 - 2e1e2)

Notice that, save for the special rules surrounding the es, it is very much as was learned before from the days of multiplying two expressions consisting of x and y, such as (2x+y)(4z+8w).

If a problem in geometric algebra seems difficult, my first reaction has been to ensure that everything uses e explicitly.

Second, when reading articles and books, always be sure to know which dimension the given results apply in.  I have yet to find an article that does not give examples or definitions at a lower dimension before jumping to the dimensionless forms thanks to the desire to give out something practical without having to face a wall of mathematics.

Third, the inner (also known as the dot) and outer products are filters on the geometric product.  If the result does not match the product, it is zero, and we move on.

Again, let's return to (1e1 + 2e2)(3e1 + 4e2).
The result with the geometric product was: (11 - 2e1e2).
Let us consider the dot product of (1e1 + 2e2) and (3e1 + 4e2).  The grade of 1e1 is 1 (to obtain the grade, count the number of unique e's after the scalar).  When multiplying two elements together, the dot product says the grade of the result must equal the grade of the second element minus the grade of the first.  So when we take the inner product 1e1 with 3e1 where the grade(3e1) - grade(1e1) = 1 - 1 = 0, therefore the result must be a scalar, which it is (3).

The outer product filter is the sum of the grades.

The filter applies only to the two elements being multiplied together at a time, not to the whole multivectors.  After the product is done, the results are added as usual.

Finally, just keep on finding more sources.  I found it easier to work with the topic once I had a dozen articles each tackling the topic slightly differently.  If my mental model of how the geometric algebra was accurate, then each paper I would read would not conflict with the mental model.

Edits:

1. Since my initial hints were leading people astray.  They exemplified my lack of understanding, which should be resolved.
2. Reorganization for clarity.

C++11 for Math Vector Types

Something about code has been ringing true since I heard of the idea at school: each line of code has a maintenance cost.  Code is rarely never changing.

Come in C++11 and the common issue of dealing with the vector types.  These include position (we have the CGPoint in iOS, skVector3 in SpriteKit, and so forth), size (CGSize), colour (4 either floats or bytes), etc.

What changes between these?  The number of elements, the type of the elements.

What remains constant?  The operations.  Dot product can be used for luminance as it can be used for getting the angle between two vectors.  Even it can be treated as an innate part of matrix multiplication which we use for general transforms in space, such as from RGB to YUV.

In C++11 we can define something very nice, a template with two parameters, a type and a size.  A colour will typically be 3 or 4 components with either a uint8_t or a float as a type.  A position can be 2-4 components and is typically a float but can also be a double.

For the constructor, we can use variadic templates to ensure that 0-N components can be initialized at once.  For example, in a RGBA colour we could initialize just the first 3 components.

Pushing this idea further, we can make a lot of code much simpler.  Consider parsing a range of memory containing an image.  We usually have a stride for the x and y which determines how many bytes until the next x pixel and next y pixel.  X is typically 4 for 32-bit colour and Y is the width of the image times 4.

Imagine we were to store the strides in a vector, then we could dot the stride with the desired pixel position to get the byte offset.  We then have replaced what may appear to be a bunch of semi-random operations all over the code with dot products.

Yes, the example is contrived, and would need some tweaking to be just as efficient - however the point is that all the varied structures described above can be represented using a single structure with a common set of operations.

Consider, my vector for a colour is now defined as: typedef Vector<uint8_t, 4> Colour;

For small hobbyist projects, this is an essential trick to have a rich set of types with relatively little effort.

Update March 1st, 2015 -- Sample code:

#pragma once//

#include <assert.h>

#include <cmath>

#include <initializer_list>

#include <stdlib.h>

template<class T, int N>

class LVector

{

private:

typedef LVector<T, N> _type;

T _d[N];

// Utility so constructor can take N elements

LVector(T*, int) {}

template<typename ... Args>

LVector(T *idx, T v, Args... args)

: LVector(idx+1, args...)

{

assert(idx <= _d);

idx[0] = v;

}

// Utility so swizzle can take N elements

template<int M>

void _swizzle(LVector<T, M> &ref, const int i)

{ assert(i == M); /* Ensure that we have given all params. */ }

template<int M, typename ... Args>

void _swizzle(LVector<T, M> &ref, const int i, const int idx, Args... args)

{

ref._d[i] = (*this)[idx];

_swizzle(ref, i+1, args...);

}

public:

LVector() = default;

LVector(const LVector<T, N>&) = default;

template<typename ... Args>

LVector(T v, Args... args)

: LVector(_d+1, args...)

{

static_assert(N > 0, "Too many elements for size of vector");

_d[0] = v;

}

_type operator+(const _type &a) const

{

_type r;

for (int i=0; i<N; i++)

r._d[i] = _d[i] + a._d[i];

return r;

}

// Swizzle is a common operation to extract vectors.

template<int M, typename ... Args>

LVector<T, M> swizzle(Args... args)

{

LVector<T, M> v;

_swizzle(v, args...);

return v;

}

// Cast to bool (enables operators to work)

operator bool() const

{

for (int i=0; i<N; i++)

{ if (_d[i] != 0) return false; }

return false;

}

// Comparators (we return masks as they may be multiplied + avoid type issues)

_type operator >(const T& a) const

{

_type r;

for (int i=0; i<N; i++)

{ r._d[i] = (_d[i] > a) ? 1 : 0; }

return r;

}

_type operator >=(const T& a) const

{

_type r;

for (int i=0; i<N; i++)

{ r._d[i] = (_d[i] >= a) ? 1 : 0; }

return r;

}

_type operator >(const _type &a) const

{

_type r;

for (int i=0; i<N; i++)

{ r._d[i] = (_d[i] > a._d[i]) ? 1 : 0; }

return r;

}

_type operator <(const T& a) const

{

_type r;

for (int i=0; i<N; i++)

{ r._d[i] = (_d[i] < a) ? 1 : 0; }

return r;

}

_type operator <(const _type &a) const

{

_type r;

for (int i=0; i<N; i++)

{ r._d[i] = (_d[i] < a._d[i]) ? 1 : 0; }

return r;

}

_type operator ==(const _type &a) const

{

_type r;

for (int i=0; i<N; i++)

{ r._d[i] = (_d[i] == a._d[i]) ? 1 : 0; }

return r;

}

// Easy indexing

T &operator[](int i) { return _d[i]; }

T  operator[](int i) const { return _d[i]; }

// C++11 utilities

static int size() { return N; }

T* begin() { return _d; }

T* end() { return _d+N; }

};

// Useful derived types

typedef LVector<uint8_t, 4> LColour;

typedef LVector<float, 2> LVector2;

typedef LVector<float, 3> LVector3;

typedef LVector<int, 3> LIVector3;

// Common offsets

enum

{

kX = 0,

kY = 1,

kZ = 2,

kW = 3,

kR = 0,

kG = 1,

kB = 2,

kA = 3

};

// Useful derived operations

template<class T, int N>

T abs(const LVector<T, N> &v)

{

T s;

for (int i=0; i<N; i++)

s[i] = abs(v[i]);

return s;

}

template<class T, int N>

T dot(const LVector<T, N> &l, const LVector<T, N> &r)

{

T s;

for (int i=0; i<N; i++)

s += l[i] * r[i];

return s;

}

template<class T, int N>

T max(const LVector<T, N> &l)

{

T s = l[0];

for (int i=1; i<N; i++)

{

if (s < l[i])

s = l[i];

}

return s;

}

Social Assumptions Regarding Blogs

Often times the obvious just hits me.  Years later.  The obvious, this time, is the social encoding found within blogs.  There is a codified set of assumptions based upon how people will consume content which determine what content creators can do.

Yes.  Painfully obvious, isn't it.  Also, nefarious.

My latest project on this platform has been a short story.  Each post continues on the previous.  I find the exercise to be quite entertaining as it forces me to consider different types of scenarios and also my mind gets bored by the mundane and usual so I've allowed myself to come up with the atypical.  The latest, for example, is a spiral escalator.

Blogger enforces that newer posts appear first.  Is there a problem with that?  Inherently no.  Most blogs follow the right template.  New stuff is awesome, old stuff just gets stuck behind.  For example, product reviews thrive on the new.  Events thrive on the new.  Even documenting technology or how to do something can thrive on the new.

Of course, you could argue that if something isn't new and worthwhile, it will be linked to a million times voer and Google will provide an link to it.  Sure.

Now, the core of the issue - everything is independent.  There is no prescribed reading order.  People just are supposed to jump in at any given point in time and be able to pick up on the information.  What if I want to describe something complex in a linear format over severall posts?  Then I'd have to fight the digital system (as others have) to ensure that posts appear in te desired order, and that the front page would always be the first post.

Or, I could stop being lazy and could include small summaries of the story with each post.  It's all about the person reading the material - after all it's not as though they are starved for content/entertainment.  Even though I'd like whoever (if anyone) who reads that blog to read it in order, I should make it convenient to read from whenever.

That is if I cared about readers.  To me it's a nice platform to simply write.

Discouraging how I've turned around and through a royal meh and passively accepted my fate as a person writing using this service.  (probably since it's free and I don't feel like moving it anywhere else.

Review of the Lego Big Ben (350 piece) model

Armed with a 20% off coupon, I ended up buying this small set of bricks.  The Whitehouse was the first set I got in the series, and I thoroughly enjoyed building it.  The series itself tends to do clever things with the bricks in sets that aren't too big or expensive (ie. the Parisian Cafe which I'd love to have).

Yes, it is a small model.  Very thin, very small.  And for that size, it has a lot of bricks.  Why?  it's the small detail and that there is very little, if any, empty space within the 3-brick-thick walls.

Most of the model uses bricks that I could find on my spaceships of yore - much of the detail comes from clever brick building.  And that is why I must write a blog post about this model.  I enjoyed following the instructions and building it since it achieved so much detail with so few bricks.  Even though I could tell from the box that they couldn't have built it in many other ways, the person who translated the model into lego did a great job.

It is the latest landmark to exist on my desk.  :)

The Ire of Perpetual Change in Software

Software is becoming a special beast.  It is ever changing its face.

Just look at the applications that are "cloud" driven.  This is more of accepting the reality that application development has to follow the changes of the landscape (operating system, etc.) and that feature-wise many of these software are more than complete.

Consider Office.  You have styles, bibliography building, rudimentary grammar correction, layout, indexing, cross-referencing and whatnot.  Same features available in LaTeX if you can stomach the scripting.  I would argue that since 2000 the software has been sufficiently feature-complete for my needs and have been relearning to find the same features in reorganized menus since.

Windows is endemic of the problem.  Click advanced properties on a file and you get something reminiscent of Windows 2000.

Arguably, OS X has had no intention of preserving the old.  Yes, there is a new way to launch applications.  There is an updated look.  Updated usability.  A moving target for every piece of software.

If utensils were made by software companies, then each two years we would have a new way to eat.  A new easier way to hold them.  A new easier set of foods.  Something much more fashionable.  All the time.

I have no issue with progress, but do we have to slow down the machine.  Have fewer software developers.  More stability.

May be we don't need to change the user interface of our digital utensils every year.  Maybe once a decade.  Or less.

Yet again, new sells.  And in software that can be expensive.  Is it worth the cost?

32 to 64 bit for the rest of us

Today I shall discuss the issues that arise when migrating 32 bit code to 64 bit.  Without falling into the typical jargon.

George is a city planner.  He likes to plan out cities and determine who will live where.

There's also the home builder Alan.  He likes building homes for people within cities.

Both have to work together when building new cities.  Alan needs space for his houses.  George needs to know how large Alan's houses will be.

Alan knows there are various types of houses.  Small, medium, and large.  They are 10 square feet, 15 square feet, and 20 square feet in usable floor space respectively.  Then there are the variants, such as a bungalow which takes the same amount of space as a small home and a mansion which takes the same amount of space as a large home.

Sometimes, some of Alan's clients ask him to change a small home for a bungalow, etc.  when this happens, he doesn't have to notify George since the amount of space needed is the same.

For years, the two have happily built houses forming complete cities without a hitch.  Actually, they just copy the same city all over the place.

However, one day, Prime Minister Slim looked at what was being built.  Bungalows, typically lived in by families, should be larger he ascertained.  He saw families squished into their miniature bungalows.  So, he put out a decree, all Bungalows shall be 15 feet, not 10.

For George, this entails he must alter how he plans the layout of his cities.  For Alan, he has a problem.  The interchangeable use of small houses and bungalows means he must inform George of which homes are larger than the initial plan.

And herein lies the problem with going from 32 bit to 64 bit.  The person making the software has made a lot of assumptions that held true for years but are no longer the case.

SpriteKit and Normal Maps

Since iOS 8 SpriteKit now has some rudimentary lighting capabilities which has been a feature that I wanted for quite a while in a 2D engine.  Below you'll find my thoughts and details related to performance and aesthetics.

First, there are many potential pitfalls that may destroy the frame rate of your application on devices that do not have an A7, or later, chip.  The issues I discuss below tend to only crop up on low end devices.  We will look at batching, the fragment shader, and potential optimizations.

Batching, as I have discovered, can be broken by having various sprites at various angles when a light shines upon them.  As far as I can tell, the issue is that the implementation uses a single uniform to describe the angle of rotation when converting normals from view space to world space.

The fragment shader is hefty.  On older devices, multiple lights can take a significant portion of the time used to render a frame.  My intuition tells me that these devices are having trouble with the branching and looping found within the shader.

As an optimization, one option is to have lights affect as few objects as possible through the light mask.  Another option, which is a bit more extreme, would be to have a custom fragment program that is fine tuned for the number of lights present in the scene.  If you need to go further, then you may find yourself outgrowing SpriteKit and using Unity or a custom engine which tessellates around the image to minimize the number of times the fragment shader is run.  And if you go that far, you might want to consider moving to a deferred pipe where lights are much less expensive, even if the frame rate would be passable at best on the low end devices.

If you are using batching (a folder with a .atlas extension), have a separate atlas for the colour and normal maps.  If you don't, I've noticed SpriteKit generates its own rather than use the provided ones.

Second, aesthetics plays a pivotal role in whether this capability should be used.  My comments are divided between the shadows and the lights.

Shadows are not as expensive as I would expect them to be.  Shadows can be enabled through a mask to ensure only the most important objects are affected.  If you have a series of images that share edges, like a series of blocks piled upon one another, then be careful if there is anti-aliasing in the image since the shadow extends the alpha portion of the image which may lead to weird lines that are undesired (a break in what should be a continuous flat shadow).  Also, be sure to test on device as the algorithm seems to be slightly different. (It might be using the bounding box rather than the silhouette)

In terms of looks, I found that having a few lights led to some interesting results with little effort.  Unfortunately, I believe much more could be done.  What if the light is behind a sprite illuminating but its edges?  At the moment it feels like it's slightly above the sprites thus illuminating them directly.  A light is like a 3D object in this 2D world, limiting it to two axis reduces the number of possible effects.

In the end, SpriteKit introduces a very rudimentary concept of lighting.  It is not sophisticated, but sufficient to add a little extra detail to an application.  On the down side, it is too easy to hit the limits of what the implementation can do and be forced to change technology.

Edited on February 27th, 2015:  edited the text for legibility.  It seems to have been written when I was exhausted, hence barely comprehensible.  Certain details I did not have offhand (how shadows behave on device versus on the Mac), and will fill that in later when I get the chance.  Doesn't deviate from the fact that testing on device is always a good idea.

I have written a quick set of thoughts when SpriteKit first came out.