4 ms·

> The really neat thing about a BSP tree, which Fuchs, Kedem, and Naylor stress several times, is that it only has to be constructed once. This is somewhat surp

> The really neat thing about a BSP tree, which Fuchs, Kedem, and Naylor stress several times, is that it only has to be constructed once. This is somewhat surprising, but the same BSP tree can be used to render a scene no matter where the camera viewpoint is. The BSP tree remains valid as long as the polygons in the scene don’t move. This is why the BSP tree is so useful for real-time rendering—all the hard work that goes into constructing the tree can be done beforehand rather than during rendering. I can't visualize why it's true

bombcar 4y ago
https://developer.valvesoftware.com/wiki/BSP https://developer.valvesoftware.com/wiki/BSP may help - the key is you have divided it into convex spaces.
deleted 4y ago
[deleted]
whatshisface 4y ago
Here's my explanation of BSP trees, written as much for my own benefit as anybody else's (maybe it will help you): To start off with, we have a basic geometric fact: if you have a surface that divides space into separate regions (this can be a closed surface like a sphere, or an infinite surface like a plane), a line of sight can't cross between the two partitions of space without passing through the surface. If the surface is convex, a line of sight can only cross it once. (That's one definition of convexity.) Now, suppose that you have a lot of objects, and none of them are on both sides of the boundary. You can ensure that condition by splitting any object that crosses the boundary in two. No matter where the line of sight begins, and no matter what direction it moves in, the boundary then offers a definite, albeit partial ordering of events: objects on the same side of the boundary may intersect, then the line will intersect the boundary, then the objects on the other side may intersect. If you find an intersection with an opaque object on the same side of the boundary, you never need to check any objects on the other side, because the order of events above. That is a big benefit when about half of the objects in front of you are on your side of the boundary: if you are right in front of the boundary, or if there's nothing on the other side of it, it doesn't help a lot. Checking all of the objects on one side of the boundary is the same kind of problem as checking all the objects, and that means you can speed those up too by having sub-boundaries for the sub-problems. That gives you the recursion and makes it a tree. If the reasoning based on boundaries continues until there is only one object in a sub-problem, you don't need to sort lists based on distance - meaning that the whole ordering problem can be solved just with partition trees. Choosing a good tree is a difficult problem because, unlike the fact that the ordering problem can always be solved, the amount that an individual boundary division helps depends on where you and the objects are in relation to it. Planes are generally used instead of other things like spheres because splitting a polygon along the edge of a sphere doesn't result in another polygon, while splitting it along a plane does.
kazinator 4y ago
Because the input to the BSP traversal is the view position. Every node in the tree is associated with an infinite plane that divides space in half. Stuff on one side of the plane is in the left subtree; stuff on the other side of the plane is in the other subtree. The viewer is on one side of the plane or the other (or maybe on it, oops). We know that stuff on the other side of the plane cannot occlude the view of stuff on the viewer's side of the plane. So for instance if we're doing back-to-front rendering, we would draw the material from the other side of the plane first, then stuff from this side. (Subject to the content being rotated into the correct view and clipped to the view frustum.) There is no polygon in the tree that intersects/straddles these dividing planes, which is the point. When the BSP is constructed, whenever these planes cut through some input polygon, it is cut into two pieces that get assigned to different subtrees. There are then situations in which those pieces will not get drawn at the same time though they belong to the same logical surface. The planes which subdivide space in half are independent of each other; they go every which way. So if we have nodes like a b c d e f g it is possibly the case that plane b cuts through the polygon sets f and g, and maybe some of them even straddle plane b. None of that is relevant to them because the b subset is on the opposite side of common ancestor a, the b plane subdivision is concerned only separating d from e. Binary space partitioning is not actually a mathematical partition (exhaustive division into non-overlapping parts) of the space. The set of poygons gets partititoned, of course; not the space itself.
amelius 4y ago
But in reality the polygons in a scene do move ...
- danparsonson 4y ago
  Not the walls, at least not in Doom.

bombcar 4y ago

https://developer.valvesoftware.com/wiki/BSP https://developer.valvesoftware.com/wiki/BSP may help - the key is you have divided it into convex spaces.

deleted 4y ago

[deleted]

whatshisface 4y ago

Here's my explanation of BSP trees, written as much for my own benefit as anybody else's (maybe it will help you): To start off with, we have a basic geometric fact: if you have a surface that divides space into separate regions (this can be a closed surface like a sphere, or an infinite surface like a plane), a line of sight can't cross between the two partitions of space without passing through the surface. If the surface is convex, a line of sight can only cross it once. (That's one definition of convexity.) Now, suppose that you have a lot of objects, and none of them are on both sides of the boundary. You can ensure that condition by splitting any object that crosses the boundary in two. No matter where the line of sight begins, and no matter what direction it moves in, the boundary then offers a definite, albeit partial ordering of events: objects on the same side of the boundary may intersect, then the line will intersect the boundary, then the objects on the other side may intersect. If you find an intersection with an opaque object on the same side of the boundary, you never need to check any objects on the other side, because the order of events above. That is a big benefit when about half of the objects in front of you are on your side of the boundary: if you are right in front of the boundary, or if there's nothing on the other side of it, it doesn't help a lot. Checking all of the objects on one side of the boundary is the same kind of problem as checking all the objects, and that means you can speed those up too by having sub-boundaries for the sub-problems. That gives you the recursion and makes it a tree. If the reasoning based on boundaries continues until there is only one object in a sub-problem, you don't need to sort lists based on distance - meaning that the whole ordering problem can be solved just with partition trees. Choosing a good tree is a difficult problem because, unlike the fact that the ordering problem can always be solved, the amount that an individual boundary division helps depends on where you and the objects are in relation to it. Planes are generally used instead of other things like spheres because splitting a polygon along the edge of a sphere doesn't result in another polygon, while splitting it along a plane does.

kazinator 4y ago

Because the input to the BSP traversal is the view position. Every node in the tree is associated with an infinite plane that divides space in half. Stuff on one side of the plane is in the left subtree; stuff on the other side of the plane is in the other subtree. The viewer is on one side of the plane or the other (or maybe on it, oops). We know that stuff on the other side of the plane cannot occlude the view of stuff on the viewer's side of the plane. So for instance if we're doing back-to-front rendering, we would draw the material from the other side of the plane first, then stuff from this side. (Subject to the content being rotated into the correct view and clipped to the view frustum.) There is no polygon in the tree that intersects/straddles these dividing planes, which is the point. When the BSP is constructed, whenever these planes cut through some input polygon, it is cut into two pieces that get assigned to different subtrees. There are then situations in which those pieces will not get drawn at the same time though they belong to the same logical surface. The planes which subdivide space in half are independent of each other; they go every which way. So if we have nodes like a b c d e f g it is possibly the case that plane b cuts through the polygon sets f and g, and maybe some of them even straddle plane b. None of that is relevant to them because the b subset is on the opposite side of common ancestor a, the b plane subdivision is concerned only separating d from e. Binary space partitioning is not actually a mathematical partition (exhaustive division into non-overlapping parts) of the space. The set of poygons gets partititoned, of course; not the space itself.

amelius 4y ago

But in reality the polygons in a scene do move ...

danparsonson 4y ago
Not the walls, at least not in Doom.