Jump to content
  • Advertisement
Dingybarker

BSP tree question

Recommended Posts

Posted (edited)

I'm thinking about making a first person shooter 3D game engine that uses separate BSP trees to represent one map.
The map is made of smaller pieces that are sectors so each sector is a separate BSP tree.
I want to be able to make 3D shapes that can occupy the same space that do not merge and can do non-euclidean geometry.
Map sectors won't merge if they are separate BSP trees.
I think I can bring the separate BSP trees together with portal rendering and the game engine keeps track of what sector the player is in.

Is it possible to use separate BSP trees in one map?

Edited by Dingybarker
Spelling

Share this post


Link to post
Share on other sites
Advertisement

There's nothing stopping you from using multiple BSP trees in the same map. As long as there's no overlapping it should be relatively straight forward. Again, these are just way to partition a space to make it easier to manage in memory and processing. 

Share this post


Link to post
Share on other sites
6 hours ago, Dingybarker said:

I want to be able to make 3D shapes that can occupy the same space that do not merge and can do non-euclidean geometry.

Reminds me about this project, maybe it's helpful: https://github.com/HackerPoet/NonEuclidean 

Maybe it's an alternative to use user clip planes instead BSP trees. I assume they are available in any rendering API, and if enough it should be much easier to implement.

6 hours ago, Dingybarker said:

Is it possible to use separate BSP trees in one map?

Yes. Likely what you want is to clip BSP trees with portals. That's possible, and i think you could still use a single BSP tree as well (e.g. The mirrors in Quake 3 or the first Prey game).

Goos luck with the project, sounds very interesting! :D

 

 

Share this post


Link to post
Share on other sites
On 6/10/2019 at 1:56 AM, JoeJ said:

Reminds me about this project, maybe it's helpful: https://github.com/HackerPoet/NonEuclidean 

Maybe it's an alternative to use user clip planes instead BSP trees. I assume they are available in any rendering API, and if enough it should be much easier to implement.

Yes. Likely what you want is to clip BSP trees with portals. That's possible, and i think you could still use a single BSP tree as well (e.g. The mirrors in Quake 3 or the first Prey game).

Goos luck with the project, sounds very interesting! :D

 

 

Thanks.

On 6/9/2019 at 11:56 PM, namar0x0309 said:

There's nothing stopping you from using multiple BSP trees in the same map. As long as there's no overlapping it should be relatively straight forward. Again, these are just way to partition a space to make it easier to manage in memory and processing. 

I'm actually trying to make a game engine that allows overlapping sectors and I thought maybe separate BSP trees would allow the space inside each sector to be separate.

Will the sectors that overlap and share the same space conflict with one another or will they stay separate because they are separate BSP trees?

Share this post


Link to post
Share on other sites
Posted (edited)
49 minutes ago, Dingybarker said:

Will the sectors that overlap and share the same space conflict with one another or will they stay separate because they are separate BSP trees?

I'ver never done such intersting things so i can't help much, but because BSP partitions space with planes, anything that keep the relations between those planes intact should work, e.g. translation, rotation, nonuniform sacle, mirroring - any kind of linear transformation and combination of this. What won't work would be curvy distortions like bend or curl because separating planes would start to intersect.

Thinking of it, you're likely right with making each sector its own BSP. The BSPs stay seperate because they are static, and the protals only create the illusion they would be connected. If the player goes through a portel he gets teleported from one place to another but he does not realize the trick. Overlaps would be no problem here. That's how i would do it, but my imagination is limited to things like this:

This was a nice project. (Physics work by having two instances of a body that goes through the portal. A Joint connects them to make tham act like a single body, and in the contact callback contacts behind the portal plane get rejected to virtually cut the objects. Rendering worked with render to texture which looked a bit glitchy when i tried the demo. Quake did better with its portals.)

I'm unsure if this can do 'Noneuclidean Space' like you want, but making a room inside larger than the house is from the outside should work using scale for example.

I'm also unsure if you really need BSP for that. It seems all the magic happens at the portals and the transformation they do?

 

 

 

Edited by JoeJ

Share this post


Link to post
Share on other sites
Posted (edited)
3 hours ago, JoeJ said:

I'ver never done such intersting things so i can't help much, but because BSP partitions space with planes, anything that keep the relations between those planes intact should work, e.g. translation, rotation, nonuniform sacle, mirroring - any kind of linear transformation and combination of this. What won't work would be curvy distortions like bend or curl because separating planes would start to intersect.

Thinking of it, you're likely right with making each sector its own BSP. The BSPs stay seperate because they are static, and the protals only create the illusion they would be connected. If the player goes through a portel he gets teleported from one place to another but he does not realize the trick. Overlaps would be no problem here. That's how i would do it, but my imagination is limited to things like this:

This was a nice project. (Physics work by having two instances of a body that goes through the portal. A Joint connects them to make tham act like a single body, and in the contact callback contacts behind the portal plane get rejected to virtually cut the objects. Rendering worked with render to texture which looked a bit glitchy when i tried the demo. Quake did better with its portals.)

I'm unsure if this can do 'Noneuclidean Space' like you want, but making a room inside larger than the house is from the outside should work using scale for example.

I'm also unsure if you really need BSP for that. It seems all the magic happens at the portals and the transformation they do?

 

 

 

A 2.5D game named Marathon could do non-euclidean geometry with its 2D map and it used portals instead of BSP trees.
The game only rendered the area where the player was and that allowed it to do non-euclidean things.

I want to make something like Marathon, but the map is 3D.

Maybe I can make it with one BSP tree or no BSP tree at all.

Edited by Dingybarker

Share this post


Link to post
Share on other sites
Posted (edited)
4 hours ago, Dingybarker said:

Thanks.

I'm actually trying to make a game engine that allows overlapping sectors and I thought maybe separate BSP trees would allow the space inside each sector to be separate.

Will the sectors that overlap and share the same space conflict with one another or will they stay separate because they are separate BSP trees?

I agree that the BSP trees should keep things pretty divided in terms of data/physics etc. but when it comes to rendering, everything will be converging to the camere (unless you have multiple viewports for each BSP and do the merging later on in the rendering pipeline; fragment shader?)

At worst you'll get some interesting rendering artifacts. Maybe you'll break through into some new level design paradigms :)

When the camera decides what to render, I'm expecting the overlapping areas to glitch or artifact on the screen, because you'll be querying multiple BPS trees which will return different information for the same spatial location. 

That said, you can probably fix that by setting a z-order to whatever BSP wants to take priority. 

Edited by namar0x0309
typo and more thoughts

Share this post


Link to post
Share on other sites
10 hours ago, Dingybarker said:

A 2.5D game named Marathon could do non-euclidean geometry with its 2D map and it used portals instead of BSP trees.
The game only rendered the area where the player was and that allowed it to do non-euclidean things.

I remember playing this game on Mac at work, but not the euclidean stuff. Tried to download, but like many older games the exe does not start up and there is no error message at all. I already consider to go back to Win7 because of this :(

 

But i thought about the question BSP yes or no. 

You can use the BSP to determinate portal visibility. (The main reason why this kept useful for some time even after GPUs became popular) This works by rendering the world front to back (BSP can do this without runtime sorting), and clipping the whole level geometry by the current open area on screen. While this allows to render the world without any overdraw, the polygon splitting is quite some work, so most games tried to precompute visibilty per sector using a PVS.

Calculating PVS is not easy: http://www.cs.utah.edu/~jsnider/SeniorProj/BSP/default.htm

Personally i made a software rasterizer without PVS or portals, it clipped the polygons per span against open screen and the resulting visibility was used to terminate processing the BSP further if occluded. So i lack experience with portals.

While visibility determination was the main motivation to use BSPs in games, it also has some other useful properties: I gives you information about solid space or not, so the volume. Polygon meshes alone don't have this property. This can be used to do boolean operations on meshes like unions or subtractions.

But in practice all of this works only with low poly geometry. For detailed models it becomes quickly unpractical, not only because of performance but mainly because of floating point precision issues. It's hard and tedious to make this work, and this also applies to writing a BSP compiler that processes your levels.

To learn how it works this was a good resource: http://www.jagregory.com/abrash-black-book/

 

If all this sounds complicated you hear why i suggest user clip planes as an alternative. :)

This would be much simpler: For a rectangular portal you set up a frustum with planes from the edges to the camera and then you can transform and render whatever different world visible through the portal without glitches. ZBuffer should still work as usual if the transform is right, and splitting objects (if necessary) would also work using an extra plane at the portal.

But you would need to make sure your minimum GPU requirements support the number if user clip planes you need. I guess that's no problem but don't know.

Also this would be compatible with any amount of details and complex geometry.

Visibility determination could be done using GPU occlusion queries, or a software based system with poly/span clipping of a simplified version of the scene. But there is a chance you don't need this at all if your levels are not too large and detailed.

It depends on your interests - if you are willing to learn all this poly clipping / BSP / visibility determination stuff or if you want to focus more on the game from the start.

 

Using engines like UE or Unity should work as well i guess? (e.g. Antichamber was made with UE3 AFAIK) But i have no experience with those.

 

 

 

 

Share this post


Link to post
Share on other sites

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!