PDA

View Full Version : BSP vs Portal systems



LostInTheWoods
12-03-2002, 06:18 AM
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?

Humus
12-03-2002, 06:39 AM
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.

AdrianD
12-03-2002, 07:01 AM
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.)

LostInTheWoods
12-03-2002, 07:01 AM
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.

Coriolis
12-03-2002, 09:04 AM
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.

LostInTheWoods
12-03-2002, 10:43 AM
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.

JD
12-03-2002, 05:34 PM
^^^^ 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.

JD
12-03-2002, 05:41 PM
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.

jwatte
12-03-2002, 06:01 PM
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.

pkaler
12-03-2002, 09:05 PM
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.

tfpsly
12-04-2002, 12:43 AM
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).]

MickeyMouse
12-04-2002, 01:20 AM
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?

LostInTheWoods
12-04-2002, 03:46 AM
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.

knackered
12-04-2002, 03:56 AM
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).

ehart
12-04-2002, 04:21 AM
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

LostInTheWoods
12-04-2002, 05:47 AM
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 1024*1024 or a 2048*2048. 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??

knackered
12-04-2002, 06:06 AM
2048*2048*4 = 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).]

LostInTheWoods
12-04-2002, 06:30 AM
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.

knackered
12-04-2002, 07:16 AM
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? http://www.opengl.org/discussion_boards/ubb/wink.gif

LostInTheWoods
12-04-2002, 08:20 AM
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.

zeckensack
12-04-2002, 08:42 AM
Originally posted by LostInTheWoods:
Dot3 only works on NVidia cards[/B]
Who told you that? http://www.delphi3d.net/hardware/extsupport.php?extension=GL_ARB_texture_env_dot3

LostInTheWoods
12-04-2002, 09:05 AM
Maybe i got dot3 and register combiners mixed up. Sorry new to the bump mapping ideas.

jwatte
12-04-2002, 08:04 PM
Mickey,

Portals cull out most things that you're not going to see, except for possibly walls in rooms that you only render partly. Most importantly, they cull out meshes that don't intersect the restricted viewing frustums, so you don't have to spend time working on meshes that won't be displayed. They're sloppier than BSP trees in many implementations, but not THAT much worse.

Another nice thing with portals is that they naturally render from near to far, which means that modern hierarchic Z acceleration will make the card take only maybe a thousand clock cycles to (not) render an entire mesh that's behind a wall, even if that mesh would fill large parts of the screen and had a 50 instruction fragment program on it.

Lost,

Putting all textures in a single texture sheet is popular on consoles with very limited texture memory, and expensive texture paging. However, your artists will hate you, because they're used to smacking down two triangles, and then tile a brick wall texture over that with a repeat of four or five. In texture sheets, you can't use tiling.

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

tfpsly
12-04-2002, 11:52 PM
Originally posted by jwatte:
Another nice thing with portals is that they naturally render from near to far, which means that modern hierarchic Z acceleration will make the card take only maybe a thousand clock cycles to (not) render an entire mesh that's behind a wall, even if that mesh would fill large parts of the screen and had a 50 instruction fragment program on it.
You can have the same result using a BSP, even more accurately. In a portal system, you can have some walls behind others in the same leaf, which mean some overdrawing depending on where is the camera. In a BSP, you'll always have perfect order.

MickeyMouse
12-05-2002, 12:25 AM
jwatte,

So your proposal is to send all PVS-determined faces to rendering API, setting for each "room" proper frustum in hardware. I don't think it can be as fast as BSP in general.

Some time ago when I was implementing and testing BSP+portals working together, I got quite a big speedup (>50%) when I made individual BSP for each sector (cluster in quake). I could spend much less time on organizing buffers for faces, copying verts coordinates, texture coordinates etc.

However good BSPs are not easy to build. In order to make recursive culling fast, leafs should contain reasonably many faces, so you will be still culling groups of faces, not each one, one by one.

BTW in my incoming engine I'm planning to use a bit modified "loose" BSPs that don't need cutting faces, resulting in as few polys as it's possible. Before it made some of my wired maps having even 3-5 times as many polys as before building BSP.

[This message has been edited by MickeyMouse (edited 12-05-2002).]

Devulon
12-05-2002, 02:34 AM
Originally posted by LostInTheWoods:
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.

Axial Aligned BSP is actually a really good idea. I believe quake 1 and 2 use some form of it. That could be worded better. There is a flag for the splitting planes that stores which axis the plane is aligned too as well as if it is aligned. That way if it is aligned the check is simple scalar math. If its misaligned then bust out the DP instructions. Its a simple check and for a game like quake there are enough axial aligned walls and stuff to make it worth the simple "bitwise and".

Devulon

MickeyMouse
12-05-2002, 03:01 AM
Originally posted by Devulon:
I believe quake 1 and 2 use some form of it.


Al quakes use arbitrary angle planes for splitting, but axis aligned ones are prefered. In that case, you were right, additional bit indicating axis-alignment is set.

LostInTheWoods
12-05-2002, 03:44 AM
Ive seen some wire frame models of a couple quake 3 maps. They dont seem to be using 2 polys per wall, with a repeated texture. They seem to be breaking them down like I would, to many polys per wall. Or am i mistaken?? I think it would work out alot better that way anyways, since textures might have a hard time lining up with eachother at the points where walls meet. Or being squished to fit.

EDIT: Also, wouldnt creating 2 LARGE polys for one wall, make it near impossible to create light maps? I mean think of all the lighting changes that could happen on one wall. You would have to create a seperate map image for EACH wall. That would start getting insane. Or am i mistaken about this too?

[This message has been edited by LostInTheWoods (edited 12-05-2002).]

LostInTheWoods
12-05-2002, 05:34 AM
DEAR GOD, IM AS DUMB AS A BOX OF ROCKS. I assumed (Makes an ass out of u and me, but mostly me) that light maps are just a multitexture overlay over the original polys in a scene. BUT if is simply create another poly square that holds just the light map, and apply it with some blending to the scene, I can simply use 2 polys for an entire wall, then a couple more polys laid on top to give the effect of lighting.

Sound right???

Coriolis
12-05-2002, 08:14 AM
If your lightmap polygons do not have the exact same vertices as your texture polygons you will have some tricky depth buffer issues to handle. If you don't use any polygon offset you will have z-fighting between the lightmap and the texture.

LostInTheWoods
12-05-2002, 09:24 AM
Isnt there a way to draw both polys on one plane, but have them blend? Like if i set the light map to a translucent value?? Or does this have to be done another way?

Coriolis
12-05-2002, 09:29 AM
You can draw them on the same plane and use a multiplicative blend. However, they are not guaranteed to have the same depth values at each pixel unless the use the same vertices.

jwatte
12-05-2002, 12:37 PM
I realize that BSP will give you "perfect" Z ordering. However, I maintain that modeling appropriate levels of detail in BSPs these days is a waste of CPU resources and space. Portals are fast enough, and have no weird interactions with complexity of geometry. If you have other things to spend your CPU and memory on, I'd suggest just using portals, or possibly portals plus a very coarse BSP that's NOT tied to your actual geometry.

As far as lightmaps go, you don't have to use the same UV for lightmaps as for regular textures. Thus, you have two sets of texture coordinates; one for textures (which tile) and one for light maps (which don't). They still are drawn as a single poly using the same verts -- that's what multitexturing is all about.