hi, I am writing a 3D world engine, for first person games is BSP still used? What do games like Halo use? Is it using raycasting? I write operating systems for a living so be patient if this is too lame of a question. 3D programming is more interesting to me. thanks, Mike

The "traditional" form of BSP (like in Doom 1) isn't used in modern games. Quake uses a PVS (Potentially Visible Set) system, where they do some offline processing (raytracing) to determine which parts of the world are visible from where. Then they use a BSP tree to quickly determine what the current PVS is. I'm probably explaining this horribly, but Abrash's article on Quakes visible surface determination method should explain it better than me.

Then there's portals. Doom 3 uses portals, I believe. Portals are very simple to understand and implement. Basically, you break up the level into little areas connected by doors or corridors (this works well for a game like Doom 3 as you can imagine), then place a "portal" at the door. When the door is open and visible to the user, you render what's behind it. Otherwise, you don't. Jacco Bikker's portal engine column has some good info on there. I believe Quake 2 uses a hybrid system of Portals + PVS where the PVS is determined like in Quake 1, then additional data is culled off using portals at doors and in corridors and such.

There's also occlusion mapping. You basically render plain geometry to a low resolution surface and it sends back information saying whether or not an object is entirely occluded. If it is, you don't render it for your full rendering. If it isn't, you do render the object. This article can serve as a handy introduction to that method. Also look for some of Yann L's posts on the issue, it seems to be his preferred method for what he's doing.

You can also subdivide your levels into little cubic cells and put them into a structure called an Octree. This method is probably easier to implement than any of them, but it only provides frustum culling (no occlusion culling whatsoever), so it might not be optimal in many cases (tight indoor levels with lots of intricate geometry, for example).

Many games will use hybrids of these methods + terrain LOD and some other stuff to cut down on data. It would be nice if the answer to the visibility question was simple and straightforward, but they all have their pros and cons. It's just a matter of figure out which technique gives you the most optimal data set with the least overhead. For example, in a lot of cases, something like portals would be overkill when simple octrees would work fine enough. Investigate them all, look at the tradeoffs, look at what works best for the game you're making and the data you're rendering. Good luck!

Quote:Original post by zed_padawan
What do games like Halo use? Is it using raycasting?

Hehe, raycast Halo would be awesome. Raycasting refers to the technique used to render games like Wolfenstein 3D, it hasn't been used in a commercial game for years. Halo uses a Quake style BSP (like Johnny Watson is talking about) for collision detection and portals for visibility, which is pretty common among FPS engines (Unreal, Doom 3, etc.)

Id recommend you to use portals, as theyre likely to overtake bsps, afaik

For a starting point:

Quote:Original post by Johnny Watson
Jacco Bikker's portal engine column has some good info on there

I'd start with brute-force frustum culling first. Most likely you will have other problems and bottlenecks before this really gets too slow. This will leave you with some time to get more familiar with graphics programming, so that you are able to judge for yourself which partitioning structure(s) and culling method(s) would be best for you.

Anyhow, for "standard" indoor scenes I'd go with an ABT or octree and portals atm. In an outdoor setting occlusion culling would be preferred over portals, selecting "good" portals sounds like a pretty hard thing to do without any "doors". Check some of the links from here for info about ABTs and occlusion culling.

Thanks for everyones input. Looks like I got some reading and coding experiments to do. The links are great!

Quote:Original post by DirectXFreak
Wait, so that's all you have to do to for portal rendering!? I've read articles on portals and they seemed much more complicated than that. What am I missing?

Portal engines are only complicated if you want absolutely zero overdraw.

In the perfect case, you begin with a working frustum matching that of the camera frustum. Clipping all geometry in the area where the camera is to this frustum, and rendering. Then for each portal from that area that survived clipping, you repeat the process using that clipped frustum. The renderer ends up being a huge experiment in efficient geometry clipping to the point where 90% or more of the code is dedicated to it. Ie, a complicated mess.

In the most dirty case, you begin as before with a working frustum matching that of the camera frustum. But instead of clipping all the geometry in the area you just render all geometry in the area. You *only* clip *portals* to the frustum. For any portal that survives clipping, you repeat the process rendering the entire area the portal points to. And so on....

Now, in the most dirty case you can even garantee that the working frustum is always convex just by being a little sloppy when clipping the frustum to the portals.