Dimajix Developer Blog

I reworked the complete frustum culling code - it is not so easy to deduce an efficient and flexible algorithm for frustum-box intersections. I also fixed some bugs in the scene-graph implementation, and now both work as they should.

The scene graph is implemented as two independent structes: One is the tree itself describing the relation between the objects containing all graphics, audio and behaviour nodes. The second structure is a loose octree that is used for view frustum culling. The separation of both structures requires a little bit overhead, but it enables a scene designer to concentrate on the scene itself without spending any thought about manually optimising the layout of the scene graph in order to speed up culling.

You can download the demo from the website of Project Magnum or directly following this link to the executable. The source package is available on the project's homepage.

...when I tried to get active in the demo scene. Still before the advent of Windows 95 back in the times of MS-DOS, I made some little Intros each of them smaller than 4096 in size. I was missing the source code of one of the two intro for some time, but when I searched through my old floppy-discs today I finally found an archieve containing both demos bundeled with their source code. Surprisingly they both still work with Windows 2000 (and I hope they will also do with Windows XP). And I have to admit I still like Points of No Return.

You can download both intros: Planetside and Points of No Return.

Kaya

A small update to the entry More Fun with Maple. I just implemented another approximation algorithm to the well-known traveling salesman problem. This time it employs a genetic algorithm approach and it produces better solutions in less time compared to simulated annealing.

What I also really like about genetic programming is that there are many different possibities to implement the mutation and crossing procedures - of course the choice will have a high impact on the optimality of the solution and the running time. Currently I use a rather simple mutation scheme that simply reverses part of a given path. The crossing function that should mix two tours and produce a new one is also very simplistic: It selects one city at random and follows one of the two parent solutions in one direction and uses the other parent for the continuation into the opposite direction from that city.

I guess there is still some room for optimisations, especially the crossing function needs some rework that hoprefully constructs better solutions.

You can dowonload the Maple worksheet here.

MS Linux is, as a true Microsoft product, even more overdue than Longhorn: MS Linux, Shipping in November 2003. From the website:

"...With Microsoft Linux Enterprise Edition, you can create scalable multi-tier applications using our new Graphical User Interface command-Line Technology (GUILT). Extend your productivity with optimized support for Internet Active-XWindows Technology and built-in Internet Xplorer web browser..."

Kaya

While searching some information about other approximation algorithms for the traveling salesman problem, I found a page containing a Java applet for evolving walking styles using some genetic selection and mutation algorithm. It is really very amazing to see a human skeleton model learning to walk!

GA-Walk!

After I was stuck with designing an algorithm for automatic layout of random graphs, I shifted over to some other interesting problems at work. On the basis of the excellent book "Lectures on Monte Carlo Methods" by Neal Madras I have implemented two simualted annealing algorithms.

The first algorithm is an application to the backpack problem which is given as follows: There are a number of items, each having a specific weight and value. You are a burgler with a backpack which can only carry a limited amount of weight - of course you want to theft as much valuable items as you can, but not all items fit into your bag. A very simple but quite powerful algorithm is as follows:

1. Calculate the ratio "value per weight" for each item.
2. Sort all items according to this ratio.
3. Beginning with the items with the highest ratio, try to put each item into your bag in the order of that sorted list.

Although this is a very simple and straight-forward solution, it gives very good results (though these do not have to be optimal).

After that I tried to implement an approach using simulated annealing, which works as follows:

1. Empty your bag.
2. Select an item at random.
3. If the item is in your bag, remove with probability exp(-beta ratio log(iteration)).
If the item is not in your bag, and there is still enough room, put it into your bag.
4. goto 3.

The value beta*log(iteration) represents the inverse temperature at each iteration and is raised logarithmically. Of course simulated annealing is a very general approach, which does not exploit the special structure of a given problem, so you cannot expect very good solutions to a given problem. But when running long enough (about 1000 iterations) I was able to get near the solution given by the simple algorithm in the case of 100 items (each with a uniformly distributed weight and value) and a bag pack which can carry at most a weight of 20.

Another interesting problem is the traveling salesman problem: Given a number of cities with their location, find a tour which visits each city and has minimal length among all such tours. This problem is known to be NP-hard (just like the first one), so probably no efficient algorithm for the opimal solution does exist. The simulated annealing approach looks very similar, here we start at a trivial tour that simply visits all cities in the order of appearance and exchanged two cities on the tour with a probability depending on the win/loss of tour length.

You can download the Maple worksheets here: Backpack.mw and Traveling Salesman.

Kaya