Hey there . Haven't been able to get an answer that has put me on the right track yet . I want to create a skybox for my game that has something big and exciting in the distance , like the ring world in halo or the background in the UDK4 tech demo

I know the majority of stuff in the foreground is simple 3d geometry , where as the further stuff is painted. What I'm looking for is a good work flow to get something like this up and running. Obviously mine won't look this good . By the way I'm using unity :)

Google is your friend... you are about number 1'000'000'000 in the line of people searching for such a tool (me included )

This is your best starting point I guess:

http://answers.unity3d.com/questions/53898/program-to-create-skybox.html

What I have used before is this tool:

http://alexcpeterson.com/spacescape

Its awesome if you need space skyboxes. You get lots of control and can build up your space scene with layers. The really awesome thing is: it will spit out 6 Images at the end you can use in your Unity space scene without further preparation (just the left and right image is the other way round).

Sadly I have not found a good tool that will allow you to paint your 6 sides and then will calculate the perspectivic distortion of the spherical to cube projection. There might be PS Plugins and Filters that do it, but to this day I am still searching for it.

Kinda offtopic: I don't think what you see in the UDK4 Techdemo in the distance is just a skybox, I think its a mixture of Skybox and 3D Models / Billboards. I have not really stared long enough at the techdemo (was not blown away enough) to really make a final call, but I guess, depending on how vast this level is and how clear the view on the skyscrapers, using 3D Models might become essential as the player might else see quite clearly that its just a flat part of the skybox.

As long as you are not delivering your game to a really lowpowered device, scramming everything into the skybox is not always the best option.

I use a space skybox at the moment, but I use some additional geometry for atmospheric scattering and distant objects. Originally chosen because of my inability to get a good tool for generating the skybox out of painted images, I must say now, both the parallax effect is quite cool in vast open levels (you can see that not everything is one flat skybox), you get the option for an "animated skybox" (clouds and so on), and the performance cost is negligible in my case (some draw calls and double digit unlit polygons more, and as long as this additional "skybox layer" remains static, it can be combined with other static objects, rendering everything in a single draw call).

EDIT:

I had some more ideas in the evening.

First I made some pics of my current setup in Unity (very heavy WIP):

[attachment=22998:Background_Layers.png]

This is the setup I currently use. It is consisting of a skybox, a Atmospheric layer (orange), two "far mountains" layers (red brownish), and two fog layers (one before each mountain layer). These layers are simple chopped off spheres created in blender. UV Mapping is straight forward thanks to the geometry, there is almost no stretching.

All these layers and the skybox (and the moon and clouds which are geometry too) are rendered by a special "background cam" which is rendered before the actual game cam... this way both cams can have different viewranges (very high for background cam, as amount of visible geometry is highly controllable)

The Fog layers are additionally rotated, to make it look like slow moving fog.

And this is how it looks ingame:

[attachment=22999:Ingame_shot_2.png]

A shot from a higher vantage point:

[attachment=23000:Ingame_shot_3.png]

If you compare the shots you can see how the parallax effect helps making the background more believable.

Which brings me to the additional ideas I had.

1) With my setup I could change to a single Skybox solution in no time. There is a cheap asset store solution (I guess with time I could write my own solution) to capture a 360° spherical image from a specially placed camera and convert it to a cubemap. This way I could take a shot of all my background layers, use that as a skybox and switch off all the geometry.

You will find similar solutions for most 3D Packages (like blender), where you could build your background from a simple skybox and geometry layers, and then convert that to a single cubemap.

2) You could create a high-poly sphere, turn the polygons inside out and paint that in a 3D Package like blender. Then convert that to a cubemap. This way you get a nice painted spherical background.

In these times of "Next-Gen" hysteria, I feel like I gotta tell you; UE4 demo backdrops are actual geo. Drop $20 and download the sample projects to check out how they did it. I know they're geo in many current gen games (selling point in consumer-aimed dev vids). 360/PS3/PC games might have billboards, but it's still usually geo and not paintovers. UDK/UE3 demos still had geo as background detail; simple as heck (often textured cubes or the same rock 2939347849843 times; its why they like distant cities so much) but still geo.

But Skybox is valid, too, as long as it will mesh with your scene well. :)

In Half-Life 2 and its Source engine, they have some geometry in front of the skybox (like BagelHero says), specifically so the camera can create the proper angle of the objects when you shift your viewing angle (helping simulate depth), since even several miles are near-ish enough to need viewing angles. But they scale down the geometry by 1/16th, if I remember correctly. Here's the developer wiki link explaining it.

I know the majority of stuff in the foreground is simple 3d geometry , where as the further stuff is painted. What I'm looking for is a good work flow to get something like this up and running.

To generate an original set of six textures for use with a skybox, you first need to set up a 90º field-of-view camera. This is the only type of camera that can be used to render an environment into a skybox, as this specific FOV value enables the camera to face each one of the six skybox directions (up, down, left, right, front and back) without having to move at all, only rotating in place.
Imagine the camera as in the center of a cube, the skybox cube. When the field-of-view has that particular value, the frustum edges are aligned with the diagonals of the cube:

You can do this in Blender, 3ds Max and other packages — the FOV value is a very common property of virtual cameras.
So after creating a camera, you set its FOV value to 90 degrees and place it at some height where you want the environment to be seen\captured from, like some height way above the horizon level in case of that futuristic city in that video, which is being seen from above (the level seems to take place in a floor of a tall building).
Then You can start creating the environment that will be rendered onto the skybox textures. This means modeling, texturing, setting up lights and special effects etc. Here you can use all of the tricks that you can come up with to produce the visuals you want.
You really need to model the environment from scratch since you can't use "terrain" software like Terragen or Bryce to create unique environments like cityscapes, outer space, the Halo ring etc.
Once the environment is finished then you can render the camera view into power-of-two textures, and rotate the camera 90 degrees in particular ways so as to render an image for each face of the cube. Remember that the camera does not move, only rotate.
Depending on how you orient the camera for the top and bottom views you will have to rotate the resulting images in an image editing program so that the edges match later, when applying the textures back to the skybox cube.

Once the textures are generated, you may want to edit them with adjustments (brightness, contrast, levels, curves, saturation etc.) to enliven them. You would apply the same adjustments to all of them of course.
Since each face of the cube proposes a different view direction, manually painting on the textures is not recommended unless you have experience and can follow the perspective conveyed by each texture, or else the effect will be broken.
In this case you may want to just add your modifications to the original 3D environment and render the textures again so you don't have to paint directly on the textures.
You can also use the same modeling package that you used to create the environment to make the skybox. It's nothing more than a unit cube (a cube with a side length of 1.0), to which you apply the respective textures on each face. Then you flip the cube mesh and export it to your engine. The benefit of making the cube manually in a 3D package is that you can address any issues with UV mapping and texturing.
The cube size can be small. There's no need to scale the cube to be extremely large if you can change its rendering order to be the first thing to be rendered and to not write to the depth buffer (Unity has ShaderLab instructions for this, with the "background" queue order and the "ZWrite" property).
It will only appear in spots not covered by anything else, staying in the background. Make sure that it also does not receive fog.

Note that the skybox was rendered with that 90º FOV camera, but in your game you can use a camera with any FOV value that you want. The effect is not broken. The 90º requirement is only for creating the skybox images.

With distant background meshes (called "3D skybox" by Valve according to that link posted by Servant) you have a new layer of complexity added to your background art.
Background meshes are extremely optimised models with low resolution textures, as these elements will be far away from the camera and don't need that many resources.
These meshes need the same lighting and fog\hazing conditions as those of the level and of the environment portrayed on skybox or the illusion will be broken, and the scale needs to be accurate. It's easy to tell how large an object is based on the parallax that it has when the camera is moving, so make sure that the background meshes are as large as they need to be.
They add richness and depth to your scene, and can look good when combined with a skybox (an example would be a Halo ring as a background mesh and a space themed skybox, with stars and planets).
http://www.interlopers.net/tutorials/1839

Sadly I have not found a good tool that will allow you to paint your 6 sides and then will calculate the perspectivic distortion of the spherical to cube projection. There might be PS Plugins and Filters that do it, but to this day I am still searching for it.

Take a look at SkyPaint ( US$ 80 ): http://www.skypaint.com/
It is an old program but it's still recommended by the CryEngine documentation as seen here: http://docs.cryengine.com/display/SDKDOC3/SkyPaint+Tutorial

Sadly I have not found a good tool that will allow you to paint your 6 sides and then will calculate the perspectivic distortion of the spherical to cube projection. There might be PS Plugins and Filters that do it, but to this day I am still searching for it.

Take a look at SkyPaint ( US$ 80 ): http://www.skypaint.com/
It is an old program but it still recommended by the CryEngine documentation as seen here: http://docs.cryengine.com/display/SDKDOC3/SkyPaint+Tutorial

Yes, good find. I remember now stumbling over this thing some time ago, but somehow I dismissed it (looks very dated and 80$).

But now that I read the cry engine documentation, it still seems to fit the bill (And if it really works as "advertised", worth the 80$ without doubt).

If its compatible with PS CS 5, I might pick it up at some point.