Jump to content
  • Advertisement

Archived

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

Cedric

Genetic algroithms applied to scene rendering

This topic is 5390 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

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
Advertisement
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

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!