1

I first came across that algorithm as the "Random minimum cut" algorithm. And recently a colleague was trying to pack a big quantity of small textures into one image file. Then it clicked - why not use Karger for this packing problem?

I don't know a good way to map this problem to a graph defined in order to minimize the wasted space between images.

Here I define the minimum cut as "the atlas with less blank filler pixels". So I need to generate a graph that represents a "distance" between images as an edge. Any suggestion on what type of distance to use?

Here is the first idea I had:

Given an image A(w, h) where w is width and h is height, if B(w', h') exists for w = w' or h = h' create an edge between A and B. (The same rule with a certain tolerance could be used, like + or - 1%).

I would be very surprised if I am the first one to think about this. So if anybody knows about anything similar that has been done, please do say so.

Improve this question
2
  • 1
    i think, your question was answered here gamedev.stackexchange.com/questions/2829/…
    – c69
    Aug 18, 2013 at 16:12
  • 1
    I know this problem has been solved in other ways. But for pure curiosity and the potential for awesomeness I wanted to see if a randomized approach would work. Krager's has the neat advantage to give the wrong answer only 1/Nth of the time. Which is quite good. There might be other solutions that are better ... and I am aware of that. Here it is more about the journey than the destination.
    – le-doude
    Aug 19, 2013 at 9:48

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Browse other questions tagged or ask your own question.