Partitioning 3d Space

Hi guys,

I'm looking for some advice, ideas, what have you. I need to solve this problem fairly quickly so here I am :-)

Basically I need to procedurally generate a number of cities at runtime. Theres some specific requirements, namely I need to have a large central building, with smaller buildings in nearby space around it. Theres going to be billboards on the side of some of these buildings, and I need to try to minimize buildings obscuring another buildings billboards.

I don't know if in my head, I'm making this out to be harder than it really is.

-I've tried adapting some code that arranges rectangular regions.( basically a spin on the black pawn lightmap packing algorithm ) It sort of works but looks kind of wrong too since all the buildings shift over to a side. I'm looking for something better.

Does anyone know or can think of a better way to do this? I keep thinking there must be some magic algorithm using a tree( like a quadtree ) to partition everything up, but I can't for the life of me figure out how to do it right now. Especially because of the main building which should be centered between the others.

-I've thought of using some kind of brute force method, that just randomly places buildings, and if theres any penetrations, it moves the involved buildings as needed.

-I've also considered using a kind of grid system, but I'm thinking that will make the buildings look too even and uniform.

Anyways, if anybodys got ideas, shoot. I'd love to hear em. :-)


BTW, took a gamble and put the thread here in general discussion. Its not blitz specific, and I figured general discussion has a good amount of traffic in it. So yea. :P

Space partitioning is (thankfully) pretty much irrelevant on modern hardware. The 8800 is bandwidth and fillrate limited long before the vertex pipeline gets maxed out, so in most cases you are better of chucking the whole geometry at the card.

Er, thanks for the reply but I didn't mean it in the rendering optimizations sense.

I meant partitioning like how I can procedurally place the buildings within a small area, without overlapping and without looking too "fake".

Orca, I think your problem is a bit unclear. If you are trying to make it exactly like a city, then you would rely simply on the side of the building that faces the street. If you want more space, then you could use green-spaces or parks in various locations, and buildings would direct their ads towards that. If your problem is something else, then I think you need to be more specific.

Yeah its a bit hard to explain.

I need to setup a number of buildings. In this case, just think a bunch of tall cubes.

I need to have one larger more prominent one in the center, with cubes of various sizes/heights surrounding this central one. Cant be touching, but need to be fairly close since they should all mostly be in view of the camera.

I've been a little picky regarding how it looks. I don't want it to look like its based around a grid/cell map/array.
Want something more random...

Though I'm running out of time and ideas so I may have to settle for a grid based approach.

Hello.

Why not just create a huge number of templates and randomly choose from them?

Goodbye.

So basically your looking for a function that will place the tallest building in the center, and as you move away from the building in any direction the buildings get smaller (with a certain amount of random height thrown in so it doesnt look so uniform)? And all these buildings have to face one way?

Before I answer my own question is that what your looking for?

Make some height map tiles that can follow tiling rules to accomodate buildings with billboards. Then populate the city with random buildings allowed on a height map tile. Should allow you to make sprawling cities in a procedural and semi-random fashion.

I'd make it array based with a few rules to brake up the array from time to time so it's looks a little more random.

Plus, something that helps cities look a lot better is uneven terrain elevations. You could use the terrain system to make a ground base with roads on it with slightly uneven tarrain, then make sure all your buildings have a foundation level that can be submerged into the ground a little. Roads in cities are rearly completely flat, unless your in Dallas, TX.

Thanks alot guys :)

@Craig
Thats basically the system I decided to go with. Hope it wont look too crap, but times running out so gotta do somethin...