如何将Portal压入BSP树中？

小小C

最近一直在看<Binary Space Partioning Trees and Polygon Removal in Real Time 3D Rendering>,全英文看得很痛苦。里面讲到Partioning engine，将一个Portal压入BSP树中，我怎么看都不明白，望达人指教。

小小C

Placing the portals
As we mentioned before, one of the big problems in a portal engine is the placement of
the portals. It is a very time consuming process to manually place the portals, not to
mention the skill required of the map designer. As with many other things, that time
could be better used in other places. So a good algorithm for automatic portal placement
is needed. A colleague of mine, Andreas Brinck, has come up with a good solution to this
problem. To use his solution a BSP-tree will have to be used.
The general idea is that each portal in the tree must be coinciding with a plane defined by
a dividing polygon in the tree. Out of each of these planes a portal polygon is created,
that portal polygon is initially a four-sided polygon that exceeds the bounding box19 of
the node it is located in. Then each portal polygon is pushed down the sub trees of the
node it is in. When a portal polygon passes through a node in one of its sub trees the
plane defined by the dividing polygon in that node clips it, it is also clipped by the
polygons in that node if the node is a leaf. If a polygon is clipped, the two resulting parts
are sent down from the top of the tree. When a portal polygon is not in need of any
clipping, it is sent down to the sub trees of the node currently visiting. This means that if
it is on the positive side of the plane it will be sent down the right sub tree, and if it is on
the negative side it will be sent down the left sub tree. But if it is coinciding with the
plane defined by the dividing polygon in the current node it will be sent down both sub
trees.
In order to be able to define the algorithm that places all the portals in the tree we need
to define how to clip a polygon, for this we need to assume there is a function called
INTERSECTION-POINT that returns a intersection point between a plane and a line
between two 3D points.

小小C

A portal engine has a very flexible structure that provides some nice features. When we
started designing our system we considered doing it as a portal engine, but there are some
problems with portal engines, especially all the clipping that occurs when you are drawing
the scene. So we decided to do a more static solution to avoid expensive calculations
during run-time. The idea is somewhat similar to a portal engine but instead of calculating
what needs to be drawn during run-time it is done in the pre-rendering of the map. For
each leaf in the BSP-tree a Potentially Visible Set (PVS21) is created. This PVS is the set of
leaves that is visible from the first leaf; it is not only of use during the drawing phase. It
can also be used when radiosity22 is calculated and networking is optimised for example.
The PVS is calculated during the pre-rendering of the map. In each leaf a set of visible
leaves is stored. When a scene should be drawn, first the leaf where the camera is in is
drawn, and then each leaf in the PVS is drawn. This requires that you have some kind of
algorithm that takes care of overdraw. As we have mentioned before, graphic cards of
today has hardware accelerated Z-buffers, which is enough.