Hi, I wanna have a large Doom/Descent-like level in my 3D-game.
Does anybody have an idea how render selection could be done?
It's important to tell the graphics card only to render the nearby walls, floors, ceilings - but how to do that?

In my special case the level won't have more than one floor.

One idea are trigger points: "When you're in room no. 5: render level sections 3, 4 and 5"

that's surely difficult and requires a lot of hard-coding

The other idea: Subdividing the level in, let's say, 15X15 meter squares. And then telling the graphics card: "render the 20 squares in front of you"

Does anybody know how modern level design works? What methods do UT, Half Life and so on use?

bsp trees or whatever?

Marcello

Yeah, items, walls, ceilings and so on.

Doom uses a totally different rendering system than UT or Half Life. Are you wanting this HW accellerated or are you going to have it as a raytracer? There have been some good raytracers written here that run on fairly slow hardware, there was a contest IIRC or something, AYBABTU and 23yrold3yrold made some good ones.

You want to use a bsp tree system... google it up and enjoy.

Marcello

raycaster
And there's one on my website IIRC.

[EDIT]
It's not much like Doom though. Only works with square blocks.

bsp trees? Hm, never heard of it.
I'll google for it
I know RayTracing as a method for creating shadows in rendering programs...

But how does it help with render selection? Is it a kind of ray collision detection for checking if a polygon is visible ore not?

DOOM uses a 2d BSP tree to split the level (technically, the universe) into sectors and subsectors.

It works out which sector the player's in by walking the BSP tree down the side of each node the player's in.

Then it goes for adjacent sectors until there aren't any more visible ones any more.

Doom is unusual compared to modern games, because it renders front-to-back rather than back-to-front (for floors and walls anyway - THINGS are rendered back-to-front)

The advantage of this approach is it minimises overdrawing and hence memory writes / texture reads, which means that on a slow fillrate GPU (Actually DOOM uses software rendering) it's faster

Mark

Surely not most recent one.

Rendering front-to-back is the way to go on modern hardware.

Most common techniques that I can think of are:
** Determining visibility - algorithms that remove regions that can't be seen from current camera position

• PVS (Potentially Visible Sets) - something close to what was already said, when camera is in certain region you know which regions can be visible. Quite simple approach, but writing good algorithm for splitting levels and determining visibility can can cause some problems.

• Portals - again, level is split into regions, which are connected through portals (usually 3d convex polygons). You can:

- render invisible portal polygon and check if it's visible, then render region behind it if it is and continue this process (unfortunately, this requires occlusion query GPU ability)
- calculate portal polygon bounding box and use scissor test to clip what's rendered behind (portals of next region may be all outside portal bounding box, which stops further rendering in this direction)

** Frustum culling - algorithms that remove things outside camera field of view

• BSP - every node has bounding box, when node is outside frustum, it's not rendered

• Oct-Tree - method similar to BSP, but uses certain scheme - at every tree level node (cubical region) is divided into 8 smaller cubes (of course only when node is complex enough)

You don't actually want to use the techniques DOOM uses in your game! Instead, I'd recommend you let OpenGL and your graphics card do most of the hard work, and just use frustum culling + perhaps octrees to limit the amount of the scene you render.

(edit: beaten by KK)

edit: KK -- your BSP definition looks wrong. The way I've always seen BSP defined is as a method splitting the world in two parts at each node -- 'in front' of the triangle to which the node corresponds, and 'in back' of the triangle. Triangles which are neither in front or in back will be split into two triangles. This allows fast depth sorting.

OMG!!!11 That is teh fu|\||\|y!!!!111

Duke Nukem 3D uses a far better technique than Doom involving sectors.
Each sector is a closed loop made from a series of walls. Each wall can either be a link to another sector(red in the editor) or a solid wall(white).

1. Add players current sector to render list.
2. Render first sector in list.
3. For each visible red wall add linked sector to render list.
4. Repeat from step 2 until list empty.

Of course the actual render loop works totally differently because of raytracing but I assume you'll be using hardware instead.

Decent uses a similar method but with the addition of an extra dimension making a sector a closed solid instead of a closed loop. Decent 1 and probably 2 adds an extra restriction by forcing the sectors to be cuboids(6 square faces). Of course a cunning level designer will combine cuboids to make better shapes. I have previously used the decent method to achieve zero overdraw, but it can be a little fiddly to edit maps.

EDIT: Yes I know it is called PVS but that name has become associated with Unreal's particular form of PVS.

I've actually assumed that it's known how BSP trees are built and pointed out that they can be used for frustum culling. They are of course useful for other things like collision and raycasting (for shooting or generating lightmaps), but depth-sorting became probably less useful than frustum culling. Also I usually use Quake 2 (in general all Quakes) BSP trees, which are defined a bit differently:
- every node is defined as a plane, but doesn't contain any actual geometry (it holds other data, like bounding boxes and additional info for collision detection)
- every leaf is in fact convex part of space (may be infinite and not closed from all sides), leaves have list of polygons associated with them (as well as other info), but no splitting is done
- when rendering a map, some polygons may appear more than once in rendered leaves, but simple last_frame variable for every polygon solves the problem

Heh, right! Thanks -- Your previous post makes a lot more sense now

A closed solid with 6 square faces is called a cube. You probably mean 6 rectangular faces. I'm pretty sure though at least descent 2 allows for more complex shapes. There are lots of tunnels in there that have a hexagon or octagon cross-section, and I don't see you building these out of cuboids.

I think you guys are scaring him.

Yeah, start with something simple. Understand completely BSP technique and how it's used in 3D shooters and everything will start making sense. Google will help you, just don't search for "BSP", it's better to search like this.

Thanks for advice, boys!
Seems I got a lot to learn now...

Ummm, no.. it's all done with cuboids, ever edit one of those levels? It sucks to make those wierd shaped rooms.

Just out of curiosity, how do you know if the wall you are rendering is visible, or hidden behind another wall?

In Doom, a wall was always vertical and there was nothing beneath floors. IIRC, Doom used a primitive z-buffer-like technique (it didn't use an actual z-buffer, but it stored the vertical strips' positions as it drew front to back) and the floor/ceiling is drawn from the bottom/top of the wall to the bottom/top of the buffer. There was some overdraw but, given the engine, would have been more expensive to fix than just let it happen.

In Duke3D-like games, each see-through "wall" was a portal.. set the clipping area to the wall (which was convex), and draw the area behind it. If another see thorugh wall is in view there, set the clipping area to that (while paying atttention to previous clipping areas) and repeat. Recurse for each wall, and the wall has everything drawn behind it, optionally draw the translucent/transparent texture, then when all the walls are done do the sprites. So, like:

Not quite true. Floors and ceilings are done across lines of constant z (i.e. horizontally) as a post processing effect, with a pixel finding algorithm a lot like a flood fill.

Doom also uses a BSP to draw its world from front to back. That substantially simplifies the processing on the vaguely z-buffer related structure they keep. Note that contrary to popular belief (and one widely read PCGPE article) ray casting is not done in Doom in any real sense.

Duke Nukem actually uses a slightly weird form of portals. They are calculated per vertical slice. For each slice the engine shoots out a ray, Wolfenstein style and figures out which wall of the current sector is hit. If it is a portal, any 'above' and 'below' drawing is done (as sectors may have different heights, we're talking about steps etc) and then the ray heads into the sector connected by the portal. In each portal you can cache which wall was hit by the last ray and test each new ray against it first. Usually you are correct if you are casting rays e.g. from left to right from the point of the observer.

There are no true 3d levels in Duke Nukem 3d, just a wide array of hacks.

Descent also uses portals, but in a true 3d world. It only uses 8 sided sectors as a memory saving device (most information about polygons is implicit) but the same algorithm would work for any connected set of convex sectors. The algorithm is to start with the current sector, set the current clip set to be the view frustum without a near clip plane and draw all solid walls with correct clipping. Then for each portal, clip that polygon to the current clip set, push the current clip set to a stack, use the clipped poly's edges to engineer a new clip set and recurse into that sector. If there is a mask texture (e.g. an opening door) then draw that after the recursion returns.

The major disadvantage of that technique is that you often end up entering the same sector to fill a continuous region of screen area from two different view portals. Imagine standing in a 100% transparent glass cube and looking at a room outside. If each wall of the cube is a different portal then with Descent style drawing you'd end up slicing the outside room down lines deliminating the edges of the glass cube.

Descent avoids this by being tunnel set. That problem rarely happens.

Portals are still quite popular but are used in a different way now. All 3d cards from the last few years have supported an extension that allows the user to query if a given polygon would be visible were it drawn. Most can tell you how many pixels would be visible but that is a slightly newer variation on the same extension. Obviously you just use the z-buffer for polygon sorting now and don't bother with convex sectors but still delimit the borders between sectors by invisible polygons and only draw on if one would be visible. Don't recurse into sectors that have already been drawn.

I've read information that most of the N64 period Nintendo games use a variation on this as the memory footprint for such a scheme is substantially smaller than e.g. a BSP tree.

I have practical experience of implementing all of these if you have any questions.

I'm just curious as I haven't heard of this before.
Do you know how this would be achieved when using the OpenGL API? Is it an extension which you need to set up yourself (like with shaders for example) or just a standard gl call? How many cards would support this function?

The correct 'modern' way to achieve this in OpenGL is the ARB occlusion query extension. This replaces the nVidial occlusion query extension. Both of those make a count of total pixels that would be drawn.

An older extension that just returns a boolean on whether any pixel would be visible is the HP occlusion test extension.

It is a standard part of OpenGL 2.0, see page 204 of the specification (page 218 of the PDF).

A search of the OpenGL site reveals that this extension doesn't seem to have existed in 1999. Nevertheless, it is supported in hardware by the Voodoo 3 and is definitely supported by the OpenGL implementation on my old Radeon 7500.

And is not supported by GeForce 2/4MX or earlier.

You're right! How weird given that the query extension (as opposed to test) is an nVidia effort. Looks like you're stuck in the world of doing at least some of your own geometry if you want to use portals on those cards!