PDA

View Full Version : Binary Space partitioning



fobru
02-19-2003, 04:37 AM
Hallo,

Has anybody experience with BSP??
Can you help me with some code??

Any help is good!!

Thanks in advance

Eric
02-19-2003, 04:46 AM
Jan2000 already gave you interesting links in your previous topic:
http://www.opengl.org/discussion_boards/ubb/Forum3/HTML/008798.html

Have you read it all and digested it already???

Regards,

Eric

M/\dm/\n
02-19-2003, 04:46 AM
That should be posted on super GURUs board even ogl.org doesn't have. http://www.opengl.org/discussion_boards/ubb/biggrin.gif
But anyways, I tried Enabling/Disabling depth_test on GF2GTS and got no FPS increase (although there was different story on TNT2), AFAIK BSP trees are made upon this idea, you can simply disable depth_test and render everything from back to front.
Although I may be wrong, as this is subject for me tu study & I can't find time for it.

antipop
02-19-2003, 05:02 AM
Originally posted by fobru:
Hallo,

Has anybody experience with BSP??
Can you help me with some code??

Any help is good!!

Thanks in advance

I've used Binary Space Partitioning for raytracing, however, that's probaly a bit outside the scope.

But, since the view frustum is a convex hull, it should be fairly easy to use a BSP tree to determine which leaves in the tree which are potentially visible.

What do you want to do with your BSP-tree?

fobru
02-19-2003, 05:22 AM
The final step is to make "Constructive Solid Geometry" (CSG)
Like making a hole in a cube (subtracting one object from another).
In a previous question one of the answers was that BSP is a first step to get there!
So I want to start with that.

Thanks to everybody who wants to help

antipop
02-19-2003, 05:27 AM
Originally posted by fobru:
... BSP is a first step to get there!
So I want to start with that.[/B]

Aha, I see the clue. In the process of constructing a BSP-tree, some of the triangles are split. However, after the tree is finished no triangles intersect, and thus, finding CSG-intersections, differences etc. should be a matter of rejecting triangles.

I think there is a FAQ on BSP-trees somewhere, at least, it was one some years ago.

To build such a BSP-tree do the following: Given a set of triangles, find a suitable splitting plane (one of the triangles for example). Then make two new sets P and N. For each triangle: if the triangle is completely inside the positive part of the half-space defined by the splitting plane, put the triangle in P. Otherwise, if the triangle is completely inside the negative half-space, put it in N. If the triangle intersects the clipping plane, split the triangle (into three I guess) into parts which are either completely positive or completely negative.

Do this recursively on P and N until P and N only contains one triangle.

This is just from the top of my head --- I guess I have forgotten something.

[This message has been edited by antipop (edited 02-19-2003).]

zeraiam
02-20-2003, 12:13 PM
you might find this interesting:

http://www.opengl.org/developers/code/bspfaq/index.html

regards