Axis Aligned Spatial Division : Divide space into random rectangles?

Question

I need a method to divide 3d space into random axis aligned box shapes. For now I am currently dividing the 2d space for testing purposes. The most immediate approach I came up with was to define a rectangle of size (1, 1) and then recursively split all existing rectangles to two uneven rectangles alternating between axis X and Y.

The problem here is obvious. This approach results in long stretching lines (marked in red)

What I would like is something more organic looking (I included an example)

See, no long straight lines from top to bottom or left to right.

The only constraint is that I may wish to limit the minimal size of the rectangle without affecting the granularity of the sizes. i.e. if the smallest rect is 1 square centimeters than the seconds smallest room should not be 2 square units.

So ideally the algorithm should meet all three following constraints:

1. Rectangles are not infinitesimally small.
2. Rect sizes aren't discrete multiplication of the smallest rect size. i.e. if the smallest rect is 3 square unit than larger rects are not constrained to be 6, 9, 12 and so forth square units and instead could be 3.2 or 4.7 for that matter).
3. The algorithm runs in polynomial time (needs to compute fast).

Answer 1

The approach you outline is simple and useful, but suffers from terrible artifacts as shown. Avoid it. You need a parallel growth algorithm; for a single-threaded model, a round-robin approach follows:

1. Randomly place various points in your map space. Normalise their distribution (avoids ugly clustering) using Gaussian distribution or by applying an iterative relaxation algorithm to move randomly placed points away from one another, as per Lloyd relaxation for Voronoi Diagrams. These points represent the centroids of your rooms-to-be.
2. (Parallel / Repeat round-robin for all rooms) From each point, grow 4 vertices outward (a rectangular room), moving from the centre point per global iteration (you can grow different rooms at different rates in each axis rather than the same for all, and see how this turns out -- possibly for a more organic / varied result). At some point, some of your rectangles will begin to press against each other. At that point, limit growth in that axis, ensure the two rooms' adjacent edges are exactly touching, and move on.
3. Repeat step 2, growing every room incrementally, till all growth is restricted by adjacent rooms or the bounds of the map.
4. This will still leave some empty spaces. The problem now becomes one of locating and making rooms out of non-occupied spaces. In fact, if your underlying space is a (integer-indexed) grid (and every growth iteration snaps to that grid), then this is much easier to deal with, since you can maintain lists of occupied and unoccupied grid cells: Once you've placed and grown all your rooms, search through the unoccupied list for discrete spaces consisting of groups of adjacent cells. As many unused spaces will have non-rectangular shapes, you'll need to pick a cell at random from within that non-rectangular space, and grow it to its maximal size just as you did with rooms in step 2. Repeat within said non-rectangular space, till it is completely filled.
5. Repeat step 4 till your map is 100% occupied.

Answer 2

As you can see, I managed to rid the world of these artifacts. The idea is very similar.

1. Divide the 2d space into a non-uniform grid. If two lines are too close, remove one.
2. Pick a rectangle in random, check if it's been modified across axis-y (in height) and if it's direct neighbor was modified across axis-y. I both were not modified, have them renegotiate the segment between them (one will donate some space to the other).
3. Do the same as in step 2 only this time on the other axis.
4. Repeat the process until you modified as many as possible.

Non-uniform grid (1):

Negotiating on axis x (2):

Negotiating on axis y (3):

Result (4) :