#165881 - DiscoStew - Sun Jan 11, 2009 6:48 am
Ok, I'm getting to the point where I understand how BSPs work, and will be in the process of actually testing them out. However, I found out a few things about them that disappoint me. The main thing is that they are best for indoor environments, whereas my game idea involves both indoor and outdoor environments, with terrain much like a height-map, but with holes for allowing tunnels and such to be made.
With BSPs working a specific way, would it be possible to include terrain as described into it? I was thinking of converting this terrain into actual polygons that get processed in with the other polygons to be compiled into a BSP structure, but what do you all think?
_________________
DS - It's all about DiscoStew
#165898 - DensitY - Mon Jan 12, 2009 1:27 am
it'll be quicker (rendering speed) if you treat the entire terrain as a polygon mesh but not actually subdividing each hill into a convex space as it'll create an insane amount of bsp nodes that'll just add to walking time for no reason. I'd treat the terrain as a 'detail' mesh in that case, and have the entire terrain section sit within 1 bsp leaf node and if performance becomes a problem, use antiportals to speed up performance.
#165921 - sajiimori - Tue Jan 13, 2009 2:27 am
BSP is good for collision, but not good for rendering (except maybe if you're using a software renderer where overdraw is a performance killer).
If you're using it for collision, I'd suggest compiling all the buildings in a level into one big BSP tree. As for terrain, you could either treat it as a separate 'layer' of collision (and do your collision tests against both layers simultaneously), or compile the terrain directly into the BSP tree.
Treating terrain as a separate layer is easy: just test versus BSP, then versus terrain, and report back whichever collision happened earlier.
Compiling the terrain directly as BSP can potentially result in an inefficient tree, but you can improve the situation a lot by simply forcing extra vertical split planes into the tree at particular places, perhaps on a grid. Then the mess from one region of terrain won't spill over into neighboring regions; the vertical planes effectively insulate each region.
With appropriate subdivisions, a monolithic BSP tree containing both buildings and terrain could actually end up more efficient than having disjoint layers, since only one kind of test is required at runtime.
#165933 - a128 - Tue Jan 13, 2009 6:37 pm
could this thread move into C/C++?
BSP is not related to the DS hardware.
#165934 - Maxxie - Tue Jan 13, 2009 6:44 pm
Not C/C++ either.
But meh. Let it, seems like he wants to know an advise for a DS project (good faith is a good thing)
_________________
Trying to bring more detail into understanding the wireless hardware
#165935 - DiscoStew - Tue Jan 13, 2009 7:24 pm
If I may ask, why is it not good for rendering? I can sort of see it from the perspective of doing it on the DS because of it dealing with individual polygons for each plane split, and that would take quite of bit of non-sequential accesses to RAM, reducing it's efficiency.
But, what if I were to configure the compiling of the BSP trees so that when it gets to a point of having separated sections into convex shapes (even with other details in the inside, like crates), it will just render the entire static area as a single display list with crates and all, and let the hardware handle Z-buffering and crop out polygons either pointing away from the camera or outside the frustum, all the while continuing the trip down the trees for additional collision testing? I think of it like a BSP tree inside another BSP tree.
Also, I believe I read that with using portals in these situations for these convex areas with openings, and testing them against the viewing frustum, it would test if an adjacent room is even partially visible, and clip the frustum to match the portal, draw that area, and do another portal test with that room's adjacent rooms, excluding the one the test came from. With clipping the frustum, even if you tried to display an additional room, only those part even partially in the frustum will be the only ones actually loaded into memory for display.
The terrain for this, as you said sajiimori, could then be separate, and then if any portal is pointing outside, do box tests for terrain sections in front of the camera to an extent, and draw those as necessary.
Now, this is all what I believe can work according to what I read. Implementing it is a completely different story, and would take me a bit of time to even attempt it. :P
_________________
DS - It's all about DiscoStew
#165937 - Maxxie - Tue Jan 13, 2009 7:54 pm
| DiscoStew wrote: |
| If I may ask, why is it not good for rendering? I can sort of see it from the perspective of doing it on the DS because of it dealing with individual polygons for each plane split, and that would take quite of bit of non-sequential accesses to RAM, reducing it's efficiency. |
This is due to the premise that the graphic hardware can do it better then the software.
If you render via BSP you render sorted by the pane distance and direction to the viewer. Deciding which side of a pane to render first in this recursive process does take some calculation power. If the hardware can decide on the fly what is infront of something else you better let it do that job and save cpu time. A frustum is usually implemented in an earliest possible stage in the hardware too, so that you usually do not have a performance impact if you only do a pretty bad decission which part of the scene to feed to the hardware.
On the other hand, using a BSP you get a lot new poligons, where panes divide poligons into parts. On the DS you might run into the hard-limit of poligons depending on the scene geometry and quality of the software creating the BSP from the scene.
_________________
Trying to bring more detail into understanding the wireless hardware
#165940 - Kaiser - Tue Jan 13, 2009 8:53 pm
You may want to divide your terrain up into small sectors or chunks and use a test-case scenario to see if they're within the player's view frustrum or not, if not, then don't render that sector/portion on the terrain.
You can also do some LOD method where distant polygons on the terrain would become simplfied while those closer to the player retain its detail.
#165941 - DiscoStew - Tue Jan 13, 2009 9:21 pm
Maxxie:
Yes, the hardware is better for rendering, but I also took that into consideration with the idea I had after what you quoted. My idea was to create a BSP compiler that splits based on walls first so as to find enclosed areas and have initial collision detection data to work with, compile all polygons used in an enclosed area (including walls and non-wall objects) into a single display list to be rendered at that node, and then further split that room based on the static non-wall objects for the remaining collision data. So, if the camera is in a room, then the room is rendered in one go, and the hardware deals with it from there. As I said for adjacent rooms, portals would be used, with the frustum clipped to match the visible portion of the portal, and that next room is rendered, but even less to render because of the clipped frustum.
Kaiser:
Splitting up sections, and (box)testing them was what I was thinking. But, the LOD method didn't seem to cross my mind. Thanks.
_________________
DS - It's all about DiscoStew
#165942 - DensitY - Tue Jan 13, 2009 9:25 pm
he could effectly do that by having the terrain (or terrain chunks) one leaf in the bsp tree. Since each node should be frustum culled before walking to its children nodes (or rendering it if it's a leaf node). he'd need to insert inviiable objects to mark those boundaries if its just one large terrain he wants to divide up, which might be a pain :/ LOD the terrain is a good idea.
As for BSP + rendering. On PC hardware it is alot faster nowadays just to render the entire map (if you try with a quake 3 map for example) then to-do a BSP walk, mark all of the visible surfaces in each leaf and rendering each surface. However it can be still useful if its mixed with portals.
if each node knows which portal-area it is in, you can simply do a walk of the bsp tree to find which node your in hence which portal area your in, after that you can check for all connecting portals, and see if they are open/visable. then simply render all surfaces within those portals (you can use the first bsp walk for colision as well, why not huh). that'll allow the hardware todo most of the scene sorting that BSP trees normally do for old school bsp software renderers.
EDIT: DS posted while I was writing this seems like he is on my wave length.
#165945 - sajiimori - Tue Jan 13, 2009 10:38 pm
Yes, BSP is "less bad" for rendering if you don't split the world as much, just because the negative effects of BSP aren't given as much of a chance to hurt your performance.
(But why accept the negative effects at all?)
If you insist on putting graphical geometry in the BSP tree, you don't actually have to have a nested tree or anything -- just have a flag in the node struct to say "there is graphical geometry on this node, so if you're rendering, stop here and upload the display list, but if you're colliding, ignore this flag and keep descending".
#165947 - TwentySeven - Tue Jan 13, 2009 11:25 pm
Keep in mind using a bsp for rendering in the quake series was done two ways.
In q1 and q2, the wall polys and convex collision brushes were clipped to the bsp tree, somewhat increasing the scene surface count due to splits, BUT, it mean you could produce a no-overdraw walk. Ideal for a software rasterizer.
In q3, the wall surfaces were no longer clipped by the geometry, instead leaf nodes of the tree contained surface references. This meant when the scene graph was being built, a single surface may have been attempted to be added to the scene multiple times (and rejected). But you ended up with many many more triangles stored per leaf node.
The DS is more suited for this latter style of rendering.
Its honestly a pretty good fit, except that trying to get good hidden surface removal using a q3 style bsp tree is a lost cause. Not to mention brush-based csg editing (even by pros who dont use csg) produces fairly rubbishly optimized triangle geometry.. if you can have your artists produce geometry in 3dsmax or maya, do so.
Personally I'd use a KD tree with a hard axis aligned portal/antiportal scheme for surface rendering on the DS. Accurate hidden surface removal with minimal geometry splitting is your goal.
A big rant on how to properly do KD trees with square axis aligned portals for hidden surf removal is for another day...
#165967 - sajiimori - Wed Jan 14, 2009 7:01 pm
One slightly awkward thing is that poly soup (e.g. Maya and Max geometry) is best for rendering, whereas CSG (e.g. from a Quake editor) is nicer for collision. I guess that's okay -- it's usually good to separate visual geometry from collision anyway.
My 2 cents about level geometry partitioning on the DS: do it by hand. The hard poly limit on the DS means the artist needs to know without a doubt what will be displayed at runtime, without trying to predict what some automatic partitioning algorithm is going to come up with.
Sometimes low tech is the way to go.
#165975 - TwentySeven - Wed Jan 14, 2009 11:26 pm
re: collision, agreed. 1:1 geometry/visual collision is a luxury the PC gets due to its abundance of cpu.
The consoles have been using seperately produced collision meshes since the first 3d titles. Ramps instead of stairs, for example.
#165976 - elhobbs - Thu Jan 15, 2009 1:20 am
quake uses multiple trees. one for rendering and collision for point size objects as well as two other trees used for colliding players/monsters and another for large monsters. so once the correct tree is selected all collision code is done by tracing lines through the tree since they have the offsets(or bounding boxes for the entity) built into the tree. the rendering tree is built to minimize splits. the collision only trees are built to subdivide space evenly.
#165977 - TwentySeven - Thu Jan 15, 2009 1:40 am
Precalculated expanded minkowski sums of brushes in the bsp wernt used in quake 3, allowing you to have any size collision object. (Just one tree...)
I have no idea if they did that in quake 1, been too long since I looked but it wouldn't surprise me.
I know they did do this for the .aas navigation format for AI (at least in doom 3), but not for the actual engine collision system.
#165978 - DensitY - Thu Jan 15, 2009 1:47 am
| elhobbs wrote: |
| quake uses multiple trees. one for rendering and collision for point size objects as well as two other trees used for colliding players/monsters and another for large monsters. so once the correct tree is selected all collision code is done by tracing lines through the tree since they have the offsets(or bounding boxes for the entity) built into the tree. the rendering tree is built to minimize splits. the collision only trees are built to subdivide space evenly. |
Quake used 1 bsp tree. just each leaf node stored a reference to a list of render faces or collision brushes. you did however had todo seperate walks of the tree for tracing line rays or AABB Boxes through it.
#165979 - sajiimori - Thu Jan 15, 2009 2:10 am
DensitY, you're mistaken; elhobbs is correct.
I disagree that PC games use visual geometry for collision due to an abundance of CPU time. A more sensible analysis would be that older games more frequently used the same geometry for both because they were so low-poly that using a lower-poly mesh for collision would cause a a noticeable mismatch between the visuals and the collision -- when polys are large, every poly matters.
For instance, Quake 2 introduced 'detail' objects that weren't part of the collision geometry. Later games continued down that path, and now it's generally considered needlessly wasteful to use the same high-poly models for collison as are used for rendering.
#165980 - DensitY - Thu Jan 15, 2009 2:55 am
| sajiimori wrote: |
DensitY, you're mistaken; elhobbs is correct.
|
he's correct if its quake 1 since that has both nodes and clipnodes, I was thinking quake 3 when I posted which does only have 1 tree. but anyhow we're going off topic :p
#165981 - TwentySeven - Thu Jan 15, 2009 3:18 am
| Quote: |
| For instance, Quake 2 introduced 'detail' objects that weren't part of the collision geometry. |
Well, no, specifying a brush as detail in q2 (and q3) meant that it wasn't used in the vis calculations or for sealing the map. It still had full collision detection.
#165982 - elhobbs - Thu Jan 15, 2009 3:25 am
I do not think that the detail objects were part of the bsp tree either. I think they were linked to leaves (or nodes?) and tested for collision separately.
#165983 - TwentySeven - Thu Jan 15, 2009 3:31 am
Thats not the same as having no collision ;)
*For reference, Im currently maintaining a fork of q3map2, the q3 compiler tool chain.
#165995 - sajiimori - Thu Jan 15, 2009 7:38 pm
Oh yeah, I was thinking only of BSP, and forgot about the separate collision data. ^_^
Anyway, I hope the point still stands that nobody really uses high-poly visual geometry for collision.
(And the notion that PC game developers don't have to optimize for CPU is absurd.)
#166003 - TwentySeven - Thu Jan 15, 2009 11:48 pm
Eh, good thing noone said that saji :)
The point I was making was quake/unreal/halflife/doom3 engine titles typically have the world collision geometry almost identical to the world render geometry*. All of the geometry produced from brush source data is 1:1. Of COURSE, some imported meshes were manually clipped (trees, cars, statues etc)
The mapper isn't required to hand construct a seperate collision mesh for the entire level like was required for alot of console engines during the ps2/xbox 1 era.
To summarize:
Pc fps engines = Very little hand built collision info. Some manual optimization.
ALOT of Console game engines = Entirely hand build collision info.
I'm not arguing that you cannot use automatically constructed collision info on the DS, I was just providing the information for point of contrast because the DS falls well within the power band of those old console engines.
#166011 - sajiimori - Fri Jan 16, 2009 7:29 pm
Our disagreement is not in the facts (i.e. which engines used which techniques on which platforms), but in our interpretation of those facts.