Genetic algroithms applied to scene rendering
Author
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
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.
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
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
Author
quote:Original post by ParadigmShiftThe 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.
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.
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!
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.)
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.)
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 
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 ?
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.
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.
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]
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.
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.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
