2D packing, maybe greedy?
category: general [glöplog]
Does anyone know if there's an approach to fill a 2D region with as few quads as possible, maximising total area coverage, minimising number of used quads, minimising empty space?
I have weak hardware and it's good at drawing quads with its API. I wanted to do a scrolling hills effect, maybe using quads to colour in the stuff below a basic Sin wave. The less quads, the less draw calls, but more quads is nicer looks hills.
It's good at triangles too. But raymarching is a no go, it suxx at doing pixel by pixel.
I have weak hardware and it's good at drawing quads with its API. I wanted to do a scrolling hills effect, maybe using quads to colour in the stuff below a basic Sin wave. The less quads, the less draw calls, but more quads is nicer looks hills.
It's good at triangles too. But raymarching is a no go, it suxx at doing pixel by pixel.
Quote:
fill a 2D region with as few quads as possible
Mainly depends on how this "2d region" is defined.
I guess it's not an arbitrary polygon but something much simpler?
They said "below sin wave" ;P but yeah they probably want more generic algo.
So which one is it and where the empty space comes from?
Usually you have max error min # quads problem, where you define max approximation error and want to find min number of quads that suffice.
I guess you also want quads to be convex?
What I would do is first approximate the region boundary with a polygon, triangulate and merge greedily into convex quads if possible (or leave triangle if not). Optimal # quads is difficult. Search engines or AI chatbots are your friends here.
Quote:
maximising total area coverage, minimising number of used quads, minimising empty space?
So which one is it and where the empty space comes from?
Usually you have max error min # quads problem, where you define max approximation error and want to find min number of quads that suffice.
I guess you also want quads to be convex?
What I would do is first approximate the region boundary with a polygon, triangulate and merge greedily into convex quads if possible (or leave triangle if not). Optimal # quads is difficult. Search engines or AI chatbots are your friends here.
Are the quads orthogonal? Is the shape you want to fill an orthogonal polygon
I've gone for this for now. I think the problem is a little out my depth and expertise to do any better. it's not exactly what I was originally asking in my post, but it does the job on the hardware and runs flawlessly, so I'd rather move on to a different thing now. Thanks for the responses anyway! <3
Largest Interior Rectangle algorithm: LIR repo in python
I did my own impl variant of LIR in Rust.
I wonder if the LIR algorithm can be appied over and over, will yield fewer rectangles.
I did my own impl variant of LIR in Rust.
I wonder if the LIR algorithm can be appied over and over, will yield fewer rectangles.
- Find LIR.
- Find LIR on the remaining.
- Repeat over.
You don't need all the complexity of LIR for just covering the area under a curve, since it will be convex. The only relevant question is where you start each rectangle (the height is going to be the min() of the function value from that point to the next). For that, just start with N equidistant points and then run gradient descent until it converges. For difficult functions (e.g. something with discontinuities), you have no guarantee that this will be optimal, but for something that's smooth as sine, I would be surprised if you don't get something that's pretty good.
