torsdag 31 januari 2013

Magnetically suspended sliding doors

Don't you think all sliding doors should be magnetically suspended above the ground?
And just have some rails to "guide" them? :).

At least I do!

söndag 27 januari 2013

Words...

Politicians are glorified parking attendants, they just waffle their way out of bullshit...
   Ramsay 2009, still true


onsdag 23 januari 2013

Space sim physics

Every couple of years a decent space fighter game/sim is released. But while games such as freelancer are overall well designed and fun to play for the action and story line, they have completely unrealistic physics. From a dogfighting perspective they're boring - Just full pull and fire when u see your target... Try that online in a decent fighter jet sim and you're pretty much dead against any decent opponent, those fights are based on faints, traps and gaining the energy advantage over your opponent.

There are some niche games that do attempt more physically accurate simulations (such as Starshatter), but as it turns out space combat with realistic traditional physics is, to me, even less interesting.

Space of course has no obvious potential wells/differences/axes, unless you count fighting close to planets/other gravity/mass concentrations. Space (usually) has no high enough concentrations of mass (think "air") that you may surf on. - So any form of dogfighting discussion with energy maneuvering  becomes pretty lame, long range guided weapons become death rays, impossible to evade without sufficient standoff/turn-and-run energy - meaning more boring fights.

Assume you're making a space sim which has something like bases/stations and capital ships/something man-made larger than a fighter. Let's also assume these structures have the ability to generate reasonably strong magnetic- or another type of field.... See where this is going? - There's your continously varying potential that your fighters may "fly/surf on". I'm not going to do all the math here but I bet a few well placed superconductors on your fighters would make for an interesting situation... All of a sudden it becomes important to maneuver through "dense space" to maximize turn rates ;).

Potential energy around planets/Earth is pretty boring after all, being (pretty much) spherically symmetric. All of a sudden, in a space game as mentioned before, you'd have capital ships battling with their own weapons as well as giving their fighters the best "sea" in between as possible. You'd need displays and sensors that give you a good idea of the potentials ahead and where to "sail/drift/surf" to maximize your performance and defeat your opponents.

Kids' killer app of 2013/2014?

Another wierd idea. A smart phone app where you have the classic virtual pet, but with a twist!

This virtual pet hooks into the GPS, wifi and other available sensors of the device. In combination with communication to a (few) centralized server(s) your pet can run away, you'll need to find it by using a/the map application and GPS - your pet can also run to other pets' screens and "play", or ...make more pets? :P

Aw the possibilities are endless...
Will sell for $5. Extra DLCs available for clothing, toys, pet food.
Special offer for a twin pet, only $3.99!

If anyone feels like financing such a project I'll code it :P.

On resource managment, c++, java, .net

Going into Java vs Native is a hopeless battle. Their respective crowds remain the same.
Let's just believe that there exists optimal tools for tasks with well defined boundaries. 

For any hobby project my choice was usually Java (now it is Scala). At work, it's C++ or C.

I love working on the JVM because of how easy it is to set up server-client architectures, run multiple threads across platforms, guarantee cross thread visibility and for each error getting standardized stack traces with thread and code line references - out of the box.

But when it comes to what most people consider the flagship (or devil) of Java, the Garbage Collector, I don't like him. He might be fast, efficient, but he is only capable of a small range of tasks.

If you pile up junk on a big heap he will do his job fine.
If want to help out with your neighbors trash, the GC gets confused - Because the GC goes "lalalala, I only see your pile of trash". When he's at it (that is, collecting your garbage) you can tell him to also help your neighbor, but you can't order him to actually observe your neighbors heap of junk on his own.

Suppose instead your neighbor is a set of file resources, network resources, video card resources, exernal device resources, etc, the list can be made arbitrarily long. Automatic management and collection can't be handled by the GC, because he doesn't really know when things are no longer needed.

Enter C++ and RAII, and the wonders of smart pointers - you may reference count anything you like, and it works beautifully. You may argue all you want that java's try-with-resources or C#'s using pattern exist, but in reality they are nowhere near the capability of hooking into deterministic stack push/pop behaviour.

Dear Oracle: Would you please introduce a ref counting Generic class (RefCnted<T>, or RefCnted ifc that you implement) which does not imply automatic garbage collection, but instead behaves like a normal C++ smart pointer/stack object? JVM languages would be much richer with such capability. JVM byte-code is stack based afaik, pease let us use that power :).

Friendship compatibility test

When bored, there's always xkcd...
Favorites (not in any particular order):

http://xkcd.com/378/
http://xkcd.com/297/
http://xkcd.com/849/
http://xkcd.com/464/
http://xkcd.com/833/
http://xkcd.com/341/
http://xkcd.com/350/
http://xkcd.com/327/
http://xkcd.com/371/
http://xkcd.com/138/
http://xkcd.com/458/
http://xkcd.com/290/


tisdag 22 januari 2013

A new years OpenCL GPU ray tracer

Something that has been bugging me for too long, so I had to start working on it.

Let's face it: Ray tracing is awesome :). Back in the day when I did my msc thesis my supervisor showed it to me: it was the first time I had really looked into it - I also saw OpenCL and GPU programming for the first time. I wrote a (judging with the knowledge I have today) crappy ray tracer for physics simulations for my thesis and passed.

But this christmas I wanted to redo it with what I've learned since then, and I wanted to do it for CG. Many articles I've read seem to point to one of the issues being: That it IS possible to use ray tracing as the primary rendering method for a somewhat simple but still interactive 3D game, but the cost of rebuilding the search trees/acceleration structures every frame is too high.

The overall cost of rendering a scene by rasterization is about O(n), where n is the number of objects/triangles/you name it. In ray tracing, supposedly, you should be able to achieve < O(n), but this is all broken because when scenes are animated/interactive, objects move and their acceleration structures must be rebuilt, supposedly every frame...If that rebuildling cost could be moved to <= O(n) while also keeping the tracing itself to < O(n), then ray tracing could possibly challange rasterization sometime in the future.

Given that this is a pretty heavily researched subject and that dozens/hundreds of smarter people than me are working on it daily (while I'm doing it when there's some extra spare time) it would be unwise to claim that the ideas I present here are new and revolutionary ;).

Insert question:
Why on earth would you want to rebuild the entire world's acceleration structure each frame?
Ok.......it's conceptually simple to code an implementation with just triangles and kd tree partitioning, or some general bvh method, whatever....what is to say that there is a universal super solution to everything - why should raw triangles in an acceleration structure be the key? (Just to make it clear I'll believe in voxel solution when I see a good one with shadows/reflections etc working decent in a dynamic game environment)

Ok. But anyway, let's propose a first method of solving the heavy acceleration structure rebuilds: Let's just have 2 acceleration structures which will be traversed in parrallel - One for dynamic objects and one for static (in all likelyhood, at least the first generation of ray traced games will have most of their scene's shapes static - like the majority of todays rasterized games!).

Another possible solution (which I've been experimenting with) is a simple variant of multi level acceleration structures: Top level structures enclosing instanced sub spaces/acceleration structures with their own rotated/translated/skewed/lalala coordinate systems.

Example: You have a top down game with for example a game like Diablo's POV. Imagine a coarse top level acceleration structure/grid which holds only references to models placed in it, and that each ray hitting a model then subsequently traverses the particular space/acceleration structure belonging to that model, with the transformations for this particular model instance. The second level structure may be of any kind (kd, grid, bvh etc), the ray initially only needs to know (e.g. in 1st pass for breadth first) that that particular sub space has to be traversed. One could add (e.g. for parts of models beloning to one bone in an animation skeleton) or remove  levels as needed. Models could have pregenerated acceleration structures.

Also, I stumbled across some DAC(Divide and conquer) ideas for ray tracing, where acceleration structurs are built on demand, which would fit nicely into this, as you could generate coarse top level structures often and the lower level ones on demand (dynamic model complexity also comes to mind here)..

Anyway, all talk, here's my experiment in action:
http://www.youtube.com/watch?v=dSTfNg-uCqk

16 Stanford bunnies at 100 fps @ 1080p with shadows. OK that is actually a static scene with a single moving light source, but you'll have to trust me or just implement it yourself - that code uses a single bunny instanced 16 times in a coarse grid. The rays which intersect any models are transformed to that particular second level acceleration structure's coordiante system and continue from there.

The whole scene has about ~250k triangles, but is rather simple because most rays hit nothing at all.

An alternative to java serialization

Googling gives you an abundance of suggestions. However you will probably either run into frameworks that require you to make some sort of manual message description files (e.g. protobuffers, which kick ass btw when you don't mind the extra work).

Whether you go the GSON/Jackson JSON route, JBOSS serialization, protobuffers or some xml serialization tool, at least I was never satisfied.

Many tools have issues with generics or just simply issues with a message class declaring a member of typ A and then actually sending that member when it's of type B (which inherits from A).

Buf if you're like me you want to do lots of experiments and not worry about formalities and writing cross communication message description files. Where are the tools for this!? (If you know of any fulfulling my requirements let me know, and I can throw away my own hacks at this ^^)

Here are my requirements:

1. You just want to write your Java classes and be done with it - you know there is enough metadata in Java to serialize the stuff to decent messages - Even when class members are arrays, generics, etc - Java Serialization can do it, you can too!

2. Do not allow cross message referencing, as this puts requirements on nodes remembering previous messages for some time span. Allow references between objects within a single message, but - again - not cross messages.

3. Send no more information with each message than what is absolutely necessary to deserialize it, but DO assume that both end points know the class - If someone wants to send a message of a type only known to one end point, force the user to send the class first.

4. Allow mid point nodes/servers/routers to pass the messages along in any order along any paths, without any repacking/parsing/deserializing! - do not require any guarantees when it comes to ordering or packet loss.

5. Do not enforce a stupid object stream architecture. Let us have a pure Object<->byte[] so that we can use any transport layer.

6. This really is covered by #2, but to make absolutely clear. Maintain ZERO node states between messages. No hidden type or object caches. It's fine between objects that are all within a single message, but NEVER cross messages.

----------------------------------

I wrote such a tool which has about the same serialization times performance as Java's serialization, and about the same message sizes (it's only when you add an extra zip compression layer that the mathematically less information with java serialization becomes apparent - it maintains node states after all, see my previous post).

Though this tool was written in Scala, it can of course be used from java as well. It's a hack, just a quick setup, but it works well enough for me. (https://www.gigurra.se/svn/GEAR/YodaUtils/scala/yodautils/scala/serialization/BinSerializer.scala public/public)

On serialization and message passing

You've been doing network IO using this seemingly awesome tool, allowing you to write virtually any object to any data stream, and read it back perfectly without implementing any form of serialization logic.

Sounds like magic, you just put "implements serializable" on your class and woop-dee-doodle-doo everything just works...or does it?

What could possibly go wrong?

Java serialization certainly has advantages. It's there from the beginning - Virtually all standard java classes support it. It has a well known API and many external libraries have support for it. It just might be the tool for you, but it might also be completely wrong.

Let's examine what it does. Marking your own class as Serializable allows you to write/read instances of your class to/from an object stream (this can be disk io, network io, memory buffer io etc). This conversion of objects to an actual underlying byte stream is done at runtime using Java reflection  - essentially just using class metadata to write class/member identifiers and member data in a consistent way as bytes (It can also do some other fancy things).
Example: You create an object stream around a byte output stream and write objects A and B to it. Object B has references to Object A. When you read back the contents from the stream you get objects A and B back, and behold, B's reference to A still holds! Even cooler still, if you write the same object twice, it will only write an object id the second time(an int or long, I can't remember which) instead of the whole object!

aHA! So can I use this as a way to pass messages over sockets between VMs/programs/game instances?
Sure, let's say every object is a message, that would work - up to the point where you start getting strange out-of-memory or stream corruption errors. You wonder what is going on...

Remember the example above: B may hold references to A...therefor the stream on both sides must guarantee that the GC does not collect A until the stream is closed or reset. So...On both sides the stream pretty much holds references to all the objects it has ever sent.

"Hey hey I can live with this, I can work around this - why don't I just reset the stream every N number of bytes/messages?". That sort of solves the issue above, except it's rather inefficient. The reason is that the first time you send an object type or object across an object stream it carries an obscene amount of metadata - Not uncommon is to see the first message of type X taking being up to 5-10 times larger than subsequent sent instances of type X.

What more is wrong with this? - B can no longer reference A, because the remote endpoint no longer has any knowledge of A after the reset. So for generality you just lost the ability for subsequent messages to reference previous messages, not always, but if a reset should occur..

"Wait wait, I'll just hook in a resend request for A, or something similar".
Right, now, what if B arrives before A in the object stream? B arrives with a reference to object with id that has not yet arrived...Here it get's even more interesting. You will probably end up with a stream corruption exception and need to reset the stream again...

So in short to be able to use the many cool features of Java serialization it requires you to guarantee that objects/messages in the stream will arrive in the same order that they were sent and that you don't reset the stream, except that not resetting the stream will eventually give you out of memory crashes/errors.

All these problems are non-issues when you just want to write/read binary files. it-just-works (Let's ignore data class versions and changes for now ;)), but for low latency unreliable networking (Hint: UDP) it's pretty much a no-go, given that to get it to work over UDP you would either have to live with a reset after every message and the extra high bandwdith requierments due to resends of metadata each message, or implement TCP on top of your UDP...either way...not very useful.

All these issues become even worse when you start dealing with a network environment where each message has to go through several nodes with their own node states/remembered objects, and where remembrance of types/objects may be linked to multiple machines/other nodes. Which ones should be reset when? Heck you can't even add any extra pipe/layer in between because it might reorder messages, chose different routing paths...anything.......you're just simply plain screwed.

There are 3rd party variants such as JBOSS serialization where you can separate the reset of object cache vs type cache (allowing you to reset object cache after each message, solving the OOM issue), but you still have the ordering requirement and the requirement that all class information must come through.

What if you want your host to serve multiple clients at the same time. One thread per client, at least!
What about an asynchronous (NIO) approach? - With serialization :)....which is totally locked down on using blocking reads....You've got some work to do!

My point being:
Strongly consider using other methods than java serialization for message passing, unless you are absolutely sure of its guarantees and requirements. It's terribly easy to shoot oneself in the foot.



I started a blog, Hooray!

bbl...(food..)