Archived

This topic is now archived and is closed to further replies.

Cedric

Genetic algroithms applied to scene rendering

Recommended Posts

I skimmed over the NVidia notes yesterday, and that idea sprung to mind. The problem of knowing what part of a scene can be culled and how to optimize the rendering calls seems perfect for genetic programming. The problem space is very large (there are many possibilities and combinations to consider), the same problem has to be tackled for every new scene, it is very easy to compare the program''s output with what it should be, and the optimization function is very clear (speed of rendering). Is there any literature on this topic? Cédric

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
Could you put the link to this NV culling paper. The problem space is so large that the main problem will be to have a fast convergence towards a good solution and you need to model this the right way, otherwise it could stick to local optimums.

Share this post


Link to post
Share on other sites
Sure, the optimization function is clear. Then all you need to do is cull everything. Very fast frame-rate!

What you mean is, culling without losing any visual data - which is a highly discontinuous, nonlinear function. There won''t be local maxima, the algorithm just won''t converge.

Other problem is what is the genotype/phenotype of your genetic algorithm? What operations can it perform and what data is it given? If you don''t give the algorithm enough specific data it won''t be able to solve the problem and if you give it too much you might as well implement the culling algorithm directly.

Tom

Share this post


Link to post
Share on other sites
quote:
Original post by ParadigmShift
What you mean is, culling without losing any visual data - which is a highly discontinuous, nonlinear function. There won''t be local maxima, the algorithm just won''t converge.
The function could drop quickly (but continuously) proportionally to the number of pixels that are wrong, thus ensuring a certain convergence towards solutions that are visually adequate.
quote:
Other problem is what is the genotype/phenotype of your genetic algorithm? What operations can it perform and what data is it given? If you don''t give the algorithm enough specific data it won''t be able to solve the problem and if you give it too much you might as well implement the culling algorithm directly.
I was thinking about genetic programming. I admit that I don''t know that much about the down-to-earth details of this kind of optimization, but from what little I have read, it seems that there are general culling concepts to apply to any scene, but it is possible to optimize further by considering specific cases.

Maybe...

Gah, now I feel stupid for posting about something that I don''t really know.

Watch out; tomorrow, I''ll unveil my special compression algorithm: save half the space by storing only the 1''s!

Share this post


Link to post
Share on other sites
I would imagine the biggest thing would be in determining an efficient manner for storing the information your GP requires. (effectivly two GP''s, one for initialization, another for executing) This is no trivial problem, I dont think this is a great plan. (Would be impressive if you managed to do it, I think you would be very popular very quickly).

You could implement a BSP tree style solution, start the algorithm off by seeding the population with that solution and see if it could improve on it. This might work better.

I look forward to recieving your compression algorithm. Is it similar to the one that only stores zeros? (zeros take less space than 1''s you know.)

Share this post


Link to post
Share on other sites
Couldn''t you write a GA that would balance a scenes ABT depending on the geometry to give good culling? That would be an easier and more practical use of GAs for graphics optimisations

Share this post


Link to post
Share on other sites
Hmm, would the use of a histogram (output analysis) and the adaptive modifying of a parameter depending on that histogram (''selection'') classify as a primitive form of GA ?

quote:

Couldn''t you write a GA that would balance a scenes ABT depending on the geometry to give good culling?


Interesting idea. The problem being, that a perfect output solution to compare to doesn''t exist. Even finding a parameter to classify the quality of the output (in order to guide the direction of the next iteration cycle) would be rather difficult.

Share this post


Link to post
Share on other sites
quote:
Original post by Yann L
Even finding a parameter to classify the quality of the output (in order to guide the direction of the next iteration cycle) would be rather difficult.



Surely not? Pick (either via code or level designer) 10 or so points in the level to benchmark from. Then at each render several frames looking in different directions and avarage the fps for all the frames over all the sample points. That should give you a good indication of how well the new ABT has been created.

Or if you want a more complete test, get some sort of recorded demo of a person playing though a level. Then play that back with the test ABT and see what the avarage framerate is like.


Edit: Although by simplifying the whole ABTs performance down to a single fps value your GA isn't going to be very directed, unless you use some variation on my idea of sample points. The sample points could nudge the GA in the direction of areas in the tree to mutate the most.


[edited by - OrangyTang on October 14, 2003 9:41:07 AM]

Share this post


Link to post
Share on other sites
You could probably do that. But as you mentioned, you''d need to define a complete path through your level/scene, in order to give the GA a good feedback. That''s not always possible, and most of all, that is going to take a lot of time to evaluate the quality factor. On ABTs with thousands of nodes, you''d probably need to render millions of frames to provide an acceptable feedback to the GA.

Also the question remains, how to control the direction of the genetic evolution. The behaviour of an ABT and it''s impact on rendering performance is very unpredictable, almost chaotic, as you change the creation parameters.

Share this post


Link to post
Share on other sites
heh, all GA methods are slow so to get a good result, no real surprise there

Yann, didn''t you mention you used a set of weights to control the equation & selection of splitting planes in your ABT? Couldn''t you do this on a smaller scale and use the GA to control them instead of the whole tree generation?

Then you could train a good set of generic weights, and run the GA on each level to try and see if it can tweek them in a specific case.

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
What about a neural network for this job, could be more adapted than GA ? I''m not sure about the outputs that it should produce..It looks like one would need need an extra large hidden layer and tons of inputs.

Share this post


Link to post
Share on other sites
I''m not an expert in 3D rendering techniques, but I am fairly experienced with GA''s so I''ll put in my .02 here.

If I understand correctly, efficient culling basically boils down to being able to split your scene up into groupings of triangles that you will use so you can cull entire groups at once instead of testing each individual triangle. This is then extended to support a hierarchy of triangle groupings (ie. quadtrees, octrees, etc) [not really sure what an ABT is, but I''m guessing its some kind of alternative to quadtrees].

You could definately use a GA to find an efficient "non-regular" grouping of triangles that produces efficient culling. The way I would do it is first create the geometry for your scene. Then create a playable version of the game that either uses per-triangle culling and will only run on very beefy computers, or use lower-quality geometry to create this playable version. Have a bunch of people play-test this version, and have code that will log the camera position and orientation for every frame. Once you have enough of these logs you can create a weighted map of your scene that determines what camera locations occur most often and least often. You can then design a GA that will generate a hierarchical grouping of the scenes geometry and use this weighted map of camera locations to choose say 100+ viewpoints to use to render frames from and recording how efficient this specific triangle grouping is (this will be your fitness function).

Yes, this will take a very long time to run. You will probably need to set it up on a top of the line PC and let it churn away for a month or so. If you develop it in a distributed manner (which this specific GA lends itself to very naturally) you can use the idle time of all the computers in your company to do the computations. I would expect a properly designed GA to be able to generate a triangle grouping that is drastically better than any generic approach such as quadtrees or octrees.

Share this post


Link to post
Share on other sites
One approach is to start out with every triangle in the level that will be drawn together ( same materials, etc. ).

Then, find local clusters of these somehow, and create a bounding box for these.

I suppose the GA could contain rules about when to split a cluster, or how to decide on which triangles joined a cluster.

This seems like quite a lot of overkill, though. A per-material AABB tree or ABT with a notion of node size hueristics could probably do 99% of the optimal solution in terms of fps.

Remember the goal is not >95% culling efficiency, but >95% potential frame rate.

Culling efficiency limits frame rate at the low end, but then has very little effect at the high end. That''s how you know you''re doing it right.

Share this post


Link to post
Share on other sites
Of course you could always develop your fitness function so that it rewards framerate instead of culling efficiency. That would alleviate your concerns about that. But now I am curious as to how much improvement a GA generated "triangle tree" (not sure what the appropriate term is) will have versus an optimized traditional method. Sounds like a good masters project.

Share this post


Link to post
Share on other sites
quote:
Original post by Anonymous Poster
What about a neural network for this job, could be more adapted than GA ? I'm not sure about the outputs that it should produce..It looks like one would need need an extra large hidden layer and tons of inputs.


I used a NN to create ABTs for quite some time. Eventually, I replaced it by more conventional heuristics. The NN gave very good results, but was just too resource hungry - very slow convergence rate, and it used tons of memory. The new heuristics are much, much faster and give only slightly worse results.

As for the GA, it would probably be possible with a rules set as SimmerD mentioned. It could be combined with a classical approach, but shifting weights as the creation of the tree advances. But I won't even dare to imagine the time needed for even a moderately complex scene...

Edit: unless you have a massive parallel architecture, such as a cluster. Although synchronisation could be an issue.


[edited by - Yann L on October 17, 2003 9:48:44 PM]

Share this post


Link to post
Share on other sites
I used a NN to create ABTs for quite some time. !!
If you dont mind, could you tell us what inputs & outputs you had?
Thanks!

[edited by - aboeing on October 18, 2003 1:13:49 AM]

Share this post


Link to post
Share on other sites