Hi !
Featured games (85)
games approved by the League of Dukes
Games in Showcase (616)
Games in Android Showcase (173)
games submitted by our members
Games in WIP (659)
games currently in development
News: Read the Java Gaming Resources, or peek at the official Java tutorials
    Home     Help   Search   Login   Register   
Pages: [1]
  ignore  |  Print  
  How BSP and other optimizations work ?  (Read 728 times)
0 Members and 1 Guest are viewing this topic.
Offline Pavelcz

Junior Newbie

« Posted 2013-03-30 08:49:05 »

Hello everyone,

I'd like to ask a few questions about BSP trees, or generally about any methods that split the scene into more parts Wink I've studied these methods in theory,but never used. Now I have my own OpenGL engine written in Java and I'd like to use these optimalizations.

1. WHEN is the world split into more areas ? Does this happen when you export your map out of your editor ? Or does the engine load the map and does the splitting ?

2. Is it ok to test an object placed in more BSP logical parts of the scene in every one of them ? Or is there a different approach ?

3. Are there any good tutorials HOW EDITORS work ? I still wonder what's the difference between 3DMax and GTK Radiant. I can import my models to GTK, but game maps seem to be made of much less polygons ...  Is the engine support related ? Is it connected with BSP ?

Thank you for your replies.  Smiley

Offline relminator
« Reply #1 - Posted 2013-03-30 10:17:33 »

1. Depends.  For Octrees(fixed node), it's usually a set number of polygons per node.  For KD Trees(balanced octrees), the same as octrees but the number of node depends on the number of polys on a scene.  For BSP trees (a non-axis alingned KD tree), well, same as a KD tree but with addition of a thing called PVS (Polygon Visibility Set).

2. Collisions(assuming this is what you mean) is also dependent upon the spatial partitioning you use.  For octrees, I just do a sphere to cube intersection for each node and if the sphere intersects a node, collide with all the polys inside the intersected node using the "plane equation".

3. I cannot help you there since I cannot make 3d models if my life depended on it.  But basically just import (obj is the easiest) read the model and construct your octree, kd tree or bsp tree.  You can save your tree on a file or calculate on the fly.

Tute (trees and quadtrees):

Binary and source for an octree:

PS. Are you sure BSP trees are what you need?  Octrees and KD trees beat the crap out of BSPs in scenes that don't have lots of walls. ie. Outside scenes.  BSP trees work best in dungeon type scenes.

Offline delt0r

JGO Knight

Medals: 33
Exp: 18 years

Computers can do that?

« Reply #2 - Posted 2013-03-30 10:55:35 »

BSPs got popular because Doom then quake used them. Back when doom was doing it, it was because you can do the painters algo pretty easy and add some tricks to that to improve things even more. Remember that Opengl was something only million dollar machines had at the time..Well at least a few 100k.

The painters algo is simply drawing things far away first. BSP allow you to easily traverse in a depth order from where ever the viewer is quickly.

They are perhaps not really a good match for modern hardware, but then again it depends.

I wrote one way back when i was still young. There are a few tricks to make sure the BSP is balanced. Also you need to "cut" large flat surfaces a lot when there are lots of little surfaces. So there are lots degenerate cases that you must consider. BSP take in triangle, for each triangle the space is cut into 2, the side "above" the triangle and the side below the triangle. As you can imagine, there are some triangles that are both above and below. These need to be cut.

So yea. Can't see why one would use BSP these days. Perhaps there are some cases where you can "compile" the map and then make some of the drawing code faster. But i can't see it being easier or better than some of the other spacial tree structures theses days.

I have no special talents. I am only passionately curious.--Albert Einstein
Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline Roquen
« Reply #3 - Posted 2013-03-30 13:41:31 »

For highly occluded scenes: cell & portals = win.
Offline delt0r

JGO Knight

Medals: 33
Exp: 18 years

Computers can do that?

« Reply #4 - Posted 2013-03-30 15:15:27 »

I would still think something like a quad/oct tree would work better. It can partition the space at wall/room boundaries.

I have no special talents. I am only passionately curious.--Albert Einstein
Offline relminator
« Reply #5 - Posted 2013-03-30 15:26:24 »

I would still think something like a quad/oct tree would work better. It can partition the space at wall/room boundaries.

Plus, you can sort the nodes from near to far so that rendering is near first.  That way, fillrate would astronomically be lower.
Offline Roquen
« Reply #6 - Posted 2013-03-31 07:10:41 »

There's no mutual exclusion here.  Spatial partitioning is great at spatial queries, so "tell me all geometry within the frustum" should be a fast operation.  What most are very pretty poor at is the hard part of generating a near minimal potentially visible set: "tell me the (close to) minimal set of visible geometry".  Cell & portal's trivially handle that problem.  So the cells store the spatial partitioned data (as individual sets) and portals are the connection graph.
Pages: [1]
  ignore  |  Print  
You cannot reply to this message, because it is very, very old.

Coldstream24 (16 views)
2015-09-03 00:41:28

Andrew_3ds (26 views)
2015-09-01 19:08:10

afikri (17 views)
2015-08-31 09:30:22

afikri (25 views)
2015-08-31 09:30:07

afikri (13 views)
2015-08-31 09:27:24

afikri (16 views)
2015-08-31 09:26:40

Roquen (30 views)
2015-08-29 11:30:54

GamerC4 (36 views)
2015-08-22 20:38:50

GamerC4 (33 views)
2015-08-22 20:37:18

GamerC4 (40 views)
2015-08-22 20:37:01
HotSpot Options
by Roquen
2015-08-29 11:33:11

Rendering resources
by Roquen
2015-08-17 12:42:29

Rendering resources
by Roquen
2015-08-17 09:36:56

Rendering resources
by Roquen
2015-08-13 07:40:51

Networking Resources
by Roquen
2015-08-13 07:40:43

List of Learning Resources
by gouessej
2015-07-09 11:29:36

How Do I Expand My Game?
by bashfrog
2015-06-14 11:34:43

List of Learning Resources
by PocketCrafter7
2015-05-31 05:37:30 is not responsible for the content posted by its members, including references to external websites, and other references that may or may not have a relation with our primarily gaming and game production oriented community. inquiries and complaints can be sent via email to the info‑account of the company managing the website of java‑
Powered by MySQL Powered by PHP Powered by SMF 1.1.18 | SMF © 2013, Simple Machines | Managed by Enhanced Four Valid XHTML 1.0! Valid CSS!