BSP vs Portal systems

I am attempting to figure out which is better, for rendering speed. If i understand these correctly they work like this. In a portal system, you create chunks of a map, say each room is a chunk. Now if the room is visable you render the entire chunk in one blast, (One array) This is very very fast for that chunk, and the more chunks you drop the better. Now in a BSP system. You always start at your key node (the first node). You run though the nodes finding front or back to you, and dropping the pieces that are otherwise. This cuts out alot of data quickly, but at the 2 costs. First cost is the amount of distance checks it will take to find if your on the front or back of all those polys. The second cost is that each wall would have to be rendered in its own mini chunk. This seems alot slower to me.

What do you guys think? Or am I way off base here?

Sounds pretty much right. BSP trees aren’t well suited for todays hardware really IMO. You get a lot of per-polygon work on the CPU. It’s also hard to sort for material etc with a BSP. A portal system is preferred.

on the other side, BSPs are great for fast collision detection.
i am using a combination of both:
first i am creating a BSP-tree, then i create based on it sectors and determine the portals to the neigburing sectors.
when rendering, i am using BSP’s to compute the current sector, and them i draw all sectors as one meshes. (every sector get clipped against their portals ofcourse)
The BSP is also used to compute collisions inside my applications. (btw.: gamasutra has a very good feature about collisions with a bsp tree.)

I do see one benefit from a BSP style set up though. But it wouldnt be a real BSP, more like a modified BSP system. And that benifit is collision detection. You could easily cut out BLOCKS of walls to check against. One thing i would change though is make 3 bsp trees. One for each major axis. This way we could build a bsp tree that is highly optimized each time around.

I’m not sure what you mean by a separate BSP for each major axis, but it doesn’t sound right. To get a good axial BSP you have to switch axes frequently.

Ok, yeah i get that now. I was hoping to make it even faster, but i have found the error in that thought. Doh… I will use the best of both worlds. I am going to use my portal system for the rendering code, and the BSP for the collision detection. BUT, im giong to build a BSP for each zone (portal) im in. This way i can cut even MORE checks out.

^^^^ sounds like a good idea. Usually you want to cull out as much geometry as possible when doing collision system on cpu. As far as rendering goes it depends. If your tree traversing times are slower than rendering times then it’s better to render more to cut down on tree traversing ie. using portals that can be tailored to handle larger sectors. Bsp might create too many splits and micro brushes when used in high poly scenes so be careful. That’s why many non essential parts are marked as detail to prevent cutting level geometry. You can also use octrees in your sector.

Something else. Make sure your collision bsp tree is balanced to minimize traversals. Usually for bsp rendering the tree is not balanced to prevent many splits. This is like a beam tree that has long chain of nodes on right side but none on left side for example.

You probably want to add a “split” polygon to both sides of the BSP tree to avoid splits, in a collision system.

Note that the key to portal systems is restricting the viewing frustum used for culling/clipping each time you traverse through a portal into a new sector; you clip your viewing frustum to the intersection between current viewing frustum and the portal. Typically, you’ll actually use the screen-space bounding rect of the portal, and use glScissor for clipping graphics, but still restrict the four planes you use for gross view frustum culling in software.

Yeah, BSPs aren’t too good for graphics hardware. The downside of portals is that they require someone to work out the chunks by hand to be optimal. Neither BSPs or portals work to well for outdoor scenes.

I like the idea of octrees. Loose octrees in particular. Check out this thread: http://tulrich.com/geekstuff/partitioning.html

And Thatcher Ulrich’s article in Game Programming Gems. The main beneift being able to handle dynamic objects quite elegantly.

Originally posted by LostInTheWoods:
First cost is the amount of distance checks it will take to find if your on the front or back of all those polys. The second cost is that each wall would have to be rendered in its own mini chunk.

  • Portals: Now if the room is visable you render the entire chunk in one blast, (One array)
  • BSP: each wall would have to be rendered in its own mini chunk

Are you crazy =) ?
Try to implement a surface (like Q3 shaders) renderer on top of this and you’ll get 1 or 2 fps =)
You’d better, in both cases, sort visible faces according to their shader (using an htable) and then display all the faces using the same shader at the same time.
As a conclusion: BSP or Portals, does not make any change on rendering speed.

On the other hand, you’ll have much more precomputations to do while building the BSP (Note: you don’t need to split any triangle). It will be hard to automatically place portals in a level (done by graphics usually).

And a BSP helps so much for collision: you just don’t need to compute any collision against faces, just check that the volume of your entity is fully inside the BSP, which is quite easy (see the first function in http://tfpsly.planet-d.net/MesProgs/Physic.C )

  • BSP: First cost is the amount of distance checks it will take to find …
    Just one dot product and one substraction per plane. Cost is nearly 0, pinnuts.

EDIT: FIXED URL

[This message has been edited by tfpsly (edited 12-04-2002).]

Hmmm I still think BSP can speedup rendering a lot. tfpsly is right it would be much faster to sort all faces by shaders. Then passing them to OpenGL with less state changes will result in better overall speed.

Anyway in most engines I’ve seen (not older than 2-3 years however) all data to be displayed is first buffered per frame, then whole arrays/elements sorted by textures/shaders are used to feed rendering API. So in that case any ready-to-just-pass-to-OpenGL-array is a myth.

BSPs are very fast. When something is not visible (especially expensive bumped meshes with shadow volumes), why would one want to display it?

Ok, i get the whole sort by shader and use BSP to render. But i am not currently doing shader work. What I am doing, is creating ONE texture map for the entire map im in. (Expecialy since many textures repeat ALOT). I can then throw the entire room in one chuck to the graphics card with with texture call. Actualy a couple, cause im also using textures for lighting and such.

Must be a small map, or a big map with very low quality textures then…
Do yourself a benchmark - split your one big array up into several smaller ones, and time your entire render loop. I think you’ll find that gldrawelement calls aren’t as expensive as you think - neither are texture changes (so long as you’ve got plenty of video/agp memory left over after your framebuffer/vertexarray allocations).

Originally posted by tfpsly:

Are you crazy =) ?
Try to implement a surface (like Q3 shaders) renderer on top of this and you’ll get 1 or 2 fps =)

Actually, a lot more plays into this. State changes are indeed expensive. The problem with attemping to create a minimal or near minimal set of state changes is that the overhead of sorting and batching stuff together can become prohibitive. The nice thing about a portal-style system is that reasonably large batches of triangles with the same shader tend to all reside in a single portal, and as a result can be pre-sorted and put into a display-list or vertex array to be downloaded to the HW.

So here are the general tradeoffs:

Portal:

  • Less runtime work to create HW friendly render calls
  • More state changes

BSP:

  • A lot of time creating draw lists
  • Minimal or near minimal state changes

In general, I have seen portals faster with todays HW, as a full BSP technique can lead starvation and CPU limits. Modified BSP type rendering that reduces the traversal overhead can be more competitive.

-Evan

Ok, Question: It was mentioned that i must have crappy texture maps cause im only using one texture for the map. Why? If i simply take ALL the textures that have to be loaded ANYWAYS for each surface, and save it in ONE texture file, and simply load that one. How am I any farther behind?

This way, i simply load one LARGE texture instead of many smaller ones. So I could very easily load a 10241024 or a 20482048. Then simply use that texture as my map texture. But most of my maps will be smaller anyhow.

My other idea was to simply create a Texture PER zone (Portal) but that dosnt work out well sinse i will have textures that repeat in multiple rooms. Thus creating duplicats.

I dont see how loading 30 smaller textures is any better than loading one large one?? Or am i mistaken??

204820484 = 16mb of 32bit texture for your entire game level.
That’s not all that much really, for any kind of varied detail. That’s a lot of repetition. Why link your texture detail to the maximum size a texture can be created on the users hardware? (remember, geforce2 and below max out at 1024^2).
Also, I’m not sure of the ins and outs of this, but from my experience large textures (2048^2) tend to be slow to handle in the pipeline…if you’ve got a single small texture that you repeat many times, I believe you would get better performance if you had a small texture object rather than texcoording a small area of an extremely large texture.

BTW, by using texture coordinates to index a small texture in a large texture object means you won’t be able to take advantage of texture tiling, and will therefore have to tesselate your geometry all the more in order tile the texture…

[This message has been edited by knackered (edited 12-04-2002).]

What is so wrong about more tesselation in a map? If im using the portal system im cutting out HUGE blocks of polys anyhow. This means i can make more believable per vertex lighting (More verts = better light calculations), and I can texture map things alot better. Say I have a brick wall, and half way down i want a crack texture to enhance the wall. I can do this without texturing the REST of the wall. Just that spot with a little detail texture on top.

I still believe that sending ONE huge block of polys to the card at once to render at once is better than sending a bunch of walls a little at a time. I could be wrong. So tell me if this is a good idea.

NEW IDEA: Build my Zones (Portals) in array blocks. Each block will be an individual array, with its own texture assigned to it. This way i sort my geometry by texture, but not by wall. So if i only use 5 textues in a room I have 5 arrays sent to the GPU to render. This way im still sending large chunks at one time, but im also not splitting them up to far. This is similar to the shader technique mentioned above. Also I could cut out that ONE huge texture and break it down piece by piece.

Originally posted by LostInTheWoods:
What is so wrong about more tesselation in a map? If im using the portal system im cutting out HUGE blocks of polys anyhow. This means i can make more believable per vertex lighting (More verts = better light calculations)

Vertex lighting? Naaahhhhh, it’s all perpixel these days man =)

I still believe that sending ONE huge block of polys to the card at once to render at once is better than sending a bunch of walls a little at a time. I could be wrong. So tell me if this is a good idea.

Don’t believe, benchmark!

NEW IDEA: Build my Zones (Portals) in array blocks. Each block will be an individual array, with its own texture assigned to it. This way i sort my geometry by texture, but not by wall. So if i only use 5 textues in a room I have 5 arrays sent to the GPU to render. This way im still sending large chunks at one time, but im also not splitting them up to far. This is similar to the shader technique mentioned above. Also I could cut out that ONE huge texture and break it down piece by piece.

Now you’ve got the idea!
But only 5 textures per room?

All per pixel? So no one ever uses actual lights any more? My lighting will consist of this, what do you think? First light maps. Obviosly. Second shadow maps based on rendering the scene from the lights point of views and combining the images w/ the depth buffer etc;. Third a purely ambient light for Gamma type settings (Whole scene). Forth the bump mappings. Right now im looking at using the Emboss bump, because Dot3 only works on NVidia cards, and i want to have a full range of cards. I may just jump between the 2 on run time, but havent decided yet.

I guess your right, there realy is no use for normal lights anymore? They simply just eat up clock ticks.