# Problems using portals to split a scene into cells

This topic is 4631 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

Hi everyone, Lets say I have a scene with the following portals And already implemented in my code is the ability to split a polygon based on a plane and test if a polygon is on the front, back, or coplanar to a plane. How would I go about using the portals to split my scene into cells? I've tried treating the portals as planes and splitting, but it is incorrect as polygons on one side of the plane are sent to the new cell while polygons on the other side of the plane are left in the old cell. From what I understand, portals & cells are like this: I just want to know how to use the portals to split the scene into cells. Note, that my portals are an exact fit of the area they are in. Thanks :) Edit: I don't want to clip the frustum to the portal if possible. Instead, I will just render the whole cell. I can't clip the frustum for exact portal rendering as the scene is fairly high poly, so it gets slow to clip each polygon. [Edited by - CadeF on November 12, 2005 9:34:49 PM]

##### Share on other sites
Quote:
 Original post by CadeFHow would I go about using the portals to split my scene into cells?I've tried treating the portals as planes and splitting, but it is incorrect as polygons on one side of the plane are sent to the new cell while polygons on the other side of the plane are left in the old cell.

That's usually how it's done. What's not working out for you?

##### Share on other sites
My "cells" do not consist of joint polygons.

In the colorful diagram,
Lets say I used the top-left portal in Portals-1 to split my scene. Scince the area on the top-right is also behind that portal, it takes both the top-left and the top-right box as it's cell. The middle-right portal does not cut this portal, as the middle-right portal is on it's front face and so splits it's front half.

##### Share on other sites
I had a feeling that's what you meant. In that case, only split the polygons that are touching the portal. You said portals fit the area they're in, so you can easily calculate which polygons they touch. Alternatively, you assign each portal a list of polygons it's supposed to clip in the map editor. This might be a bit more contrived however if gives you some flexibility once more complex geometry needs to be split.

##### Share on other sites
Got any working examples? Thanks.

##### Share on other sites
Quote:

I've still got to see an elegant solution to that problem, but here are some of the methods I know of:

-BSP the scene, computing convex cells and how they connect each to another - then flood that graph of cells, to find all the cells between a group of portals, and assign all their polys to the room these portals are enclosing.
pros: can be fast.
cons: all sorts of precision problems, that BSPs have. Not trivial to implement. Not very well suited for high-poly environments.

-Raycasting scheme: find visible pairs of polys, starting with the portal - cast a ray from its center, to the centers of polygons in front of it - it the ray didn't intersect anything, the poly is visible from that portal, and belongs to its room. Continue that, shooting not only from portals, but from visible polys too. Rely heavily on ray-collision tests.
pros: fairly easy to implement.
cons: can be slow, scales bad with poly count, and depend heavily on heuristics used to choose the pairs for the ray test.

-'Flooding poly soup' scheme: start from a cell (in front of portal), and place there a cube. Test if something intersects that cube. If not, this is the front of our floodfill - continue by creating 6 new cubes at the sides of the first one, and go that way, until they hit some poly. By doing this, we fill the space with cubes, approximating the inner space of the rooms by set of connected cubes. Cubes must be small enough, to be able to pass through windows/doors. Then find the closest cube for each poly (this can be done in O(1)) and get its portal number - done! Rely heavily on proximity tests.
pros: intuitive, easy to code.
cons: depens heavily on cubes' size - too big size can cause errors, too small can be slow and memory intensive.

-GPU rendering: place the camera behind a portal, and render the whole world with z-test/write on. Render each poly with different unique color. Extract back-buffer, and read each rendered color - that will show you each visible poly, from that portal. Render portals with black, so they'll block visibility.
Since that will not resolve all polys (rooms are concave?), next thing is to find unmarked polys, and render the world as if they are portals, so if they see a marked poly, they will now what room they are in (visible pair resolving).
Rendering from a portal/poly is done, by placing camera a bit behind, so we get a FOV of ~120 degrees, near plane is the portal/plane in question and back-buffer is rather render target, with big resolution. Maybe several frames will be needed, camera moved left/right, up/bottom, to get better visible polys' extraction.
pros: easy to implement, fast.
cons: sometimes it is hard to find visible pairs, especially in very low-poly labyrinth-like environments.

##### Share on other sites
Thanks :)

...
*thinks*
...

Ah bugger, going back to precomputed-visibility-systems ;)

##### Share on other sites
Quote:

On the other hand, some people that I know of, use much simpler systems in real production.
They mark their room geometry, and that's all. They even don't have portals (since they can be easily extracted at intersection point of the rooms).
And artists don't complain, since it is quite easy.

##### Share on other sites
Quote:
 Original post by Zemedelec-Raycasting scheme: find visible pairs of polys, starting with the portal - cast a ray from its center, to the centers of polygons in front of it - it the ray didn't intersect anything, the poly is visible from that portal, and belongs to its room. Continue that, shooting not only from portals, but from visible polys too. Rely heavily on ray-collision tests. pros: fairly easy to implement. cons: can be slow, scales bad with poly count, and depend heavily on heuristics used to choose the pairs for the ray test.

How could this work? Not all polygons are visible from the portal. Maybe you're assuming convex rooms? To me a room could be concave and very complex.

I've implemented the BSP floodfilling approach. It works well for low-poly scenes. I had some problems with complex scenes and after some period of time the whole problem made me wanna cry. :)

##### Share on other sites
So, a precomputed-visibility-system is preferrable?

1. 1
Rutin
24
2. 2
3. 3
4. 4
JoeJ
18
5. 5

• 14
• 19
• 11
• 11
• 9
• ### Forum Statistics

• Total Topics
631762
• Total Posts
3002180
×