What are Octrees, bsps, etc. ?

OpenGL OpenGL: Advanced Coding
1

Hello,

I don’t know what octree, bsp. I have the impression it is some way to organize geometrical data.

Can someone explain this to me or indicate some useful books or links?

Thanks.

2

Hi,

Octrees and BSPs are used in game engines for gaining performance. Both systems are based in “divide and conquer” and are designed for different engines. They divide all your geometry info in a few smaller structures. Depending of where you are in the world, you only process small data structures pointing your geometry info instead of processing all geometry info (the most part is unused in big worlds because you are far, etc).

Try to search in the net (you’ll be able to find a lot of information, it’s plenty).

See you,

3

www.gamedev.net www.flipcode.com
check them out. I think you will find somthing there…
and if you want a good book so “Real-Time Rendering” may be your answer…

4

BSPs (based on nodes or on leaves), Portals and so on, are preprocessed space partitioning algorithm.
“BSP” aims at building a binary tree by subdivising the space by planes liying on polygons. So, you can easily get polygons sorted (thus, no problem of transparent polygon) with specific graph traversal. But the performance strictly depends on the database complexity.
“Portal” divides the space in rooms and portals (used for indoor databases like doom…), so there will have no overdraw (only visible rooms will be rendered) .

Here you can found some links: http://reality.sgi.com/bspfaq/index.shtml http://www.exaflop.org/site/frames.cgi?HREF=http://www.exaflop.org/docs/naifgfx/naifbsp.html http://www.cs.virginia.edu/~luebke/publications/portals.html http://www.rz.tu-ilmenau.de/~juhu/Papers/IWK/node26.html http://www.flipcode.com/harmless/issue02.htm
http://crystal.linuxgames.com/docs/portal.html http://graphics.lcs.mit.edu/~seth/ http://www.cise.ufl.edu/~areddish/cap6836/
http://www.geocities.com/SiliconValley/Park/9784/tut.html#culling http://www.geocities.com/SiliconValley/Lakes/6588/BSPpaper.html http://www.netmagic.net/~achalfin/Graphics/portal.htm http://members.home.com/droyer/tutorials/Engine05.html

If you want more links, write to me

5

Thanks for all the helpful replies!

6

Was doom really a portal engine? I’m sure duke was it, but doom was a 2d bsp I think.

7

Yep Michael, I think you are right: Doom was a 2D BSP…

Regards.

Eric

8

Oups !..Micheal, you are absolutely right, Doom was a 2D BSP…

Sorry…

9

I would like to say Michael and not Micheal …