Friday, June 22, 2012

Searching point clouds - Hashes vs Trees

About a year ago I was sitting in the lawn outside of the Google buildings in Mountain View, discussing the project I was working on at the time. I had the fun job of displaying very large (60GB +) NetCDF data sets in NASA WorldWind. We were approaching it from the classic game developer perspective and considering building an octree or hyper-octree (this data had temporal slices) index over the dataset to quickly locate subsections we wanted to display at the proper detail. As an aside we began to consider what the limits of the disk to screen transmission are. A 1920x1200 screen with RGB data will have about 6.6 MB of data uncompressed, with compression this will come down a bit. At 60 FPS this requires about 3 Gbit/s disk bandwidth, compare this to what is available via SATA 3. SATA 2 will definitely be too slow adding the times required to search the index, perform seeks and read the pre-computed chunk. It might look better with highly redundant data and good compression.

The idea here comes down to searching using 2 different methods - Hash Search vs Binary Search. Octree based rendering is essentially a binary search in 3 dimensions. The other way to render would be to hash the camera position and orientations or view frustrums, create indexes and blocks of the point cloud being rendered to load chunks as the camera is moved around and data block required is located on the disk using the index + hash. The gamers keep harping on about polygon counts without looking at how the facade of the very large word-count of the internet can be quickly acessed via hashing the query, similarly the first surface of a large object count scene can be quickly accessed via hashing the camera.

All this brings me to the point of the conversation. In the last few days a bit of a drama played out in the hard-core gamer community regarding a leak from Euclideon, who make engines not websites. Hash based searching will work quite well for static data and unlike trees will not require rebalancing for dynamic data. Finding a nice unique hash for frustrums can get quite tricky and storing and compressing the results in a nice data format will also be a challenge. Building a game engine from scratch without all the blocks the graphics world has put in place is a Radical Rewrite. May be it will work, then again we live in a universe where there are 4 dimensions and no one asks how to compute the volume of a hyper-sphere. Knowing e=mc^2 does not let you build an atom bomb or a nuclear reactor, even figure out how to avoid Fukushima. Engineering simply is not the same as Mathematics.

Saturday, June 16, 2012

Power of appearances - Peacocks and Pandas

Somebody once told me the only survival adaptations pandas have evolved is their cuteness. They eat hard to digest, scarce low nutrient food, move and breed slowly and are distinct and highly visible to predators. They have only survived because people find them cute.

Studying the appearance and optic manipulation performed to achieve the colours opens up a huge arena in the study of wave propagation. Peacocks achieve their iridiscent plumage through structural colouration. The quality of the colouration reveals a lot regarding the refinement of the genetic processes which create it.
Beauty is said to be in the eye of the beholder, it more like beauty is in the sensor and the heuristics attached to the sensor. With proper training you will find X-rays of ribcages and hyaenas beautiful (of course after you have spent a few years studying the subject for say a PhD). Beauty is often associated with a halo effect and positive attributes are lumped onto those who pass our physical beauty filter.

Rampant use of cosmetics has messed up our facial feature filters somewhat, soon we will be judging people by their bone structure (this happens a bit already among athletes), heat distribution or UV images. All the better for cyborg like optical implants or AR Goggles. I will keep performing full wave EM simulations in head and keep seeing things in Gigahertz range. With the anthropic principle in effect and metallic content of the known universe increasing due to fusion and the cosmic background being in this range, it might come in handy one day.

Saturday, June 9, 2012

Go back to PvE - fighting each other vs conquering the universe

In Hobart I used to hang out often at the Dr.Coffee. One Sunday I was sitting around drinking coffee and sketching, I met somebody preparing a lesson for a church gathering. We started talking about what each of us did and eventually I started describing, 3D modelling and game design. How a game has to have balance, PvE (player versus environment) and PvP (player versus player), how often at low levels the player is made struggle against the environment and some choose to keep doing it or on a game like Guild Wars with low level cap they choose to play PvP after having attained a certain level. Keeping on playing against the mind less monsters in the environment is considered grinding or farming, and generally looked down upon, unless you are a gold farmer who exchanges game gold for real world gold.

At the end of this conversation the believer in God left me a few words - "While you design and play games do not forget who designed you and which game you are living in.". This theme has been a common refrain since the advent of gaming. The overlap between virtual worlds and the real world is growing and is captured in a lot of cyber punk such as REAMDE. Currencies are changing hands by being sacrificed to gods in game world only to be converted to fiat in real world. Religions pose a similar dogma in real world, proposing to convert our material wealth, faith or in certain cases lives to real wealth for our players in some world beyond this one. The central premise being this is sort of a game world and we should indulge in PvP against players of the opposing team(religion, colour, nation, whatever label seems appropriate) to earn points, which will be converted to rewards in the world in which this simulation is running. The grand illusion of material world ideas have been around for a while, not as long as the 14billion year long illusion, but if you believe in such weirdness, time itself is an illusion anyway.

We seem to have reached a level cap for the time being in our evolutionary progression and become so heavily embroiled in PvP i.e. taking it out on each other that we have no time to engage in conquering our environment and making our society stronger. Widening our play ground, instead of squabbling over the invididual grains of sand in the sand pit. There is a favourite refrain among elite PvP players - "Go back to PvE". The politicians, financial magnets and all those playing to beat other humans in the game of life are PvP players looking down on those attempting to conquer the environment, be it in exploring new frontiers in medicine, space or fabrication.

If this does happen to be a game, why not figure out the mechanics first and become masters of the environment before going around shouting from roof tops about religion and judgement day, and why we should serve the games master i.e. a deity if we want to finish with a good score. We should just get along and keep playing the game of life, all eschatology aside. Our indulgence in gaming world seems to have helped in expanding the boundaries of real world through the likes of Elon Musk, we just need more people to stop playing against each other.