ABT and polygon soup

This is one problem that I''ve come across. I''ve not implemented a LOD system yet and so haven''t had chance to play around with solutions to this problem. I think that one solution to it would be that for objects with LOD you insert the entire object and just use the objects bounding box as the item in the ABT. I think that there has to be a very close interaction between the ABT and the scenegraph defining the heirarchy of objects in order to geet an effective system.

I don''t think that you need to account for every LOD level while selecting the splitting plane, however there does seem to be a need to hold extra information with the geometry data i.e. which object it belongs to if you want to do LOD. This will cause a rebuild of some of the leafs of the tree when LOD changes so this suggests that a highler level primitive is required in the tree. Looking over Yann''s posts it seems that he uses polygons in the construction of the tree, but this doesn''t seem to accomodate LOD and since LOD wasn''t a topic in the discussion he probably simplified the design so that the concepts were understood.

As to the actual position of the plane, there is a thread that explains the 4 weighted functions that should be taken into consideration, and you simply evaluate the plane at a given position and find which gives the best ''score'' from the sum of the weighted functions.

The four functions are IIRC:

1) vol 1 approx. equal to vol 2
2) num faces 1 approx equal to numfaces 2
3) cuts the longest axis of the current AABB
4) num of split faces is minimised

Then the sum of these is the score: score = w1* 1) + w2 * 2) + w3 * 3) + w4 * 4)
Of course the weights depend entirely upon the bottlenecks in your engine.

I''m rambling on a bit here, so I''ll stop there.

Yes, I am well aware of those four functions. However, I am interested in how can I effectively choose split plane. Should I pick random value, check func results and move left-right until Iam satisfied?

I was considering this method :
For each plane in {XY, XZ, YZ}
Create distribution graph

Distribution graph shold look like this :
+----------------------+
|sssssssssssssss/-----/|
|sssssssss/----/sssssss|
|sss/-----sssssssssssss|
|--/sssssssssssssssssss|
+----------------------+

Graph starts in lower left corner and finishes in upper right corner.
Now width should represent one axis:
for XY plane, splitting plane will be parallel to y axis so width represents y axis of AABB (not entire size, it''s scaled)
for XZ...
for YZ...
Height represents number of triangles where bottom is 0 and top is number of triangles in this AABB.

From this graph is easy to :
1) find half of triangles (or to make num_faces1 ~ num_faces2)
2) calculate volume of child AABB

+----------------------+
|sssssssssssssss/-----/|
|sssssssss/----/sssssss|
|sss/-----sssssssssssss|
|--/sssssssssssssssssss|
+-----------|----------+
|
i.e. let''s split here

To calculate number of splitted triangles, simlpy check how many triangles did your selected plane split.

After you build graphs for all three planes, it is relatively easy to minimize f(pos).

What do you think about this idea? It''s rather slow, but it''is calculated offline so it shouldn''t pose a problem.

Depends on how good you want the results to be. If you''re lucky, the samples for your distribtion graph can appear at very satisfying positions, OR they can appear at verybad places.
For example, say that for one plane, you split no polys at all when the split happens at X-0.0001. Around that position, both "left and right" by a margin of 0.01, you split a few thousand polys. If you step by 1 unit from X in both directions for your distribution-graph and you start from X, you will never find X-0.0001. To find the location, you will need 1/0.0001 more samples, and that''s just too much
Now this doesn''t mean that skipping the optimal position is deadly in all cases, or that any other method than sampling is ultimately better. The problem is that you have to decide and perhaps profile a few ideas to find the most appropriate method for you.
Sampling is quick and easy but a sorted walking (you could build a tree for this, needed for every split though) can find places in the soup with nice "holes" where you can split.

One way I was thinking about doing this is by using a genetic algorithm to solve the problem. This may not always give the optimal solution since it can get stuck at local maxima. However by increasing the number of generations I think that we will get satisfactory results in a relatively short time period.

The only other method is to take a weighted sample of planes. I say weighted since the optimal solution is more likely to be toward the centre of the axis so it would be best to take more dense samples around that area.

Of course for both the above methods you would need to do these calculations on all three axis, and take the best one.

James

I noticed that volume and number of faces (on sides) are linear functions, therefore predictable. Number of split faces isn''t but I could, after I find splitting plane reading distribution graph, use those splitted trangles for search for minimal splitting.

Yes, that distribution graph may present a problem. However, maybe I should analyze slope of distribution graph. Find the middle then look left-right for flattest part. That part should likely contain les polygons so I''ll split them less.

We could also take whole objects into consideration at first few levels of ABT so that we don''t break them.

There must be method better than best-guess approximation...

The father of ABTs (Yann L) used neural nets "at first" to find the best split. He swapped it for a sampling-method I think, which could build the crazy big worlds a little quicker. If you want a better method than sampling, the only way I can think of right now is to look for where there are little polygons: before they start and after they end. Traverse all polygons, or even bounding hulls, to find places that are little spanned by polygons. You''ll get perfect coordinates with this method and find small gaps that could be easily missed by sampling.

I personally think that a genetic algorithm is the most suited for this problem. The way I propose to do this is:
create 3 simulations one for each plane XY, XZ, YZ

Run genetic algorithm with fitness function the weighted function I described above.

For creating offspring, all you would do is take the average value of the two parent''s planes. This is simply the average of two values since the planes are all parallel to each other.

The mutation step can simply be an addition of a random amount up to half the size of the bounding box. It may be beneficial in finetuning the system to add an additional mutator that mutates by fine amounts at a much higher rate this should help in getting the case where moving the plane 0.001 units in a direction gives a more optimal solution

jamessharpe:
I''ve noticed that you keep recalling apllication of genetic algorithms. Although I have no practical experience in writing them, I do understand their capabilities. Do you have any sort of stable system working around them(considering this topic or similar)?

No, I haven''t actually got any code which uses genetic algorithms, my experience with them is limited to a session with my supervisor at uni discussing them(his field of research is AI). Basically the purpose of a genetic algorithm is to allow us to solve a problem which has no mathematical way of solving/or we don''t know how to solve it, but we do need to be able to rank the results in order i.e. this result is better than this one. I believe that the neural networks that Yann talked about using are probably based upon a genetic algorithm

A basic implementation is thus:

class GeneticAlgorithm
{
public:
      void Simulate(int popSize, int numGenerations);
      int GetFitness(Individual * i);
      void GeneratePopulation(int popSize);
protected:
      std::vector<Individual> population;
      Individual bestSoFar;
};

class Individual
{
public:
     void Mutate();
     void Crossover(Individual * i);
};

Then the main loop looks something like this:

GeneratePopulation()
EvaluateFitnessFunction(population)

Loop for n generations
      Select individuals to reproduce
      Crossover pairs at random
      Apply Mutation on new population
      EvaluateFitnessFunction(newpopulation)
 

Of course the only downside to this algorithm is that due to the random nature you may get better results some times, also the crossover and mutation functions are obviously important as is the percentage chance of mutation. After my exams have finished next week I''ll probably try out this system(a generic template for genetic algorithms would be an interesting exercise in coding in c++!)

I''ll take a look at that.