Sign in to follow this  
CadeF

Problems using portals to split a scene into cells

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 this post


Link to post
Share on other sites
Quote:
Original post by CadeF
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.

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

Share this post


Link to post
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 this post


Link to post
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 this post


Link to post
Share on other sites
Quote:
Original post by CadeF...


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.

Hope that can help you.

Share this post


Link to post
Share on other sites
Quote:
Original post by CadeF...


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 this post


Link to post
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 this post


Link to post
Share on other sites
Quote:
Original post by Sunray
...

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. :)



1. The raycasting from portal is done just at the beginning. Later, the raycast is done from actual resolved polys, so concave rooms are ok.
The idea, is to let the portal 'mark' many vis polys, then let the invisible polys find marked ones, thus marking the whole room.
Having already something marked, means that testing should be done only for unmarked vs already marked.
But the GPU approach should rule over that one, imho.
GPU+'brute force' are my favourite words lately... :)

2. BSPs for high-poly, are terrible thing to do, just because of the non-locality of the splitting plane. It can be done stable, but with a lot of efford, that finally will approach Exact computations.. :)

Share this post


Link to post
Share on other sites
Quote:
Original post by CadeF
So, a precomputed-visibility-system is preferrable?


PVS is not easier to code, compared to GPU portalizator for example.
The GPU approaches for computing both, would be same as speed actually.

PVS vs portals - it depends of the types of scenes you'd like to handle. And the size of PVS tends to grow, if kept the whole in memory at once.
Portals are better for culling objects, and can handle occluders nicely, where PVS can't do that well (or so fast, since the cells-graph is not here any more).

Share this post


Link to post
Share on other sites
Well then, for portals, I would like to take the GPU aproach, as I've got that same "brute-force" approach working before for octrees. It's just that, I'm not sure how to handle calculating convex cells. Heck, I'm not sure about most of it. Got any good examples of code, DirectX preferrably?

Share this post


Link to post
Share on other sites
I have thought of one way of locating cells based on a portal system derived from a mesh.

1) compute all the adjacency info for the mesh. You would need to fill a winged edge data structure or a half edge data structure.

2) for each portal, find the connected verts - these should happen at kinks ( doors or windows ).

3) Traverse the data structure for all polys on one side of the portal building a list of polys that are connected to polys connected to the portal. Use this new list as a sector or cell.

for rooms with multiple portals a similar approach is used, although the other portals have to be marked as adjacent to their connected polys and form part of the temporary mesh - to be removed after the cell has been processed.


Alternatively you label rooms as rooms and doors as doors - this works well for architecture, although for caves or space age structures it can be laborious and difficult.

Share this post


Link to post
Share on other sites
What I do is I group polys into their areas and then make the portal between areas by hand. When I was doing bsp csg I was thinking of auto generating the portal by csg'ing two areas. The advantage of these areas is that in an editor I can hide each one to speed up rendering of the scene.

Share this post


Link to post
Share on other sites
Quote:
Original post by _code_fly
I have thought of one way of locating cells based on a portal system derived from a mesh.


That is one possible approach, that I didn't mentioned, because:

- it requires the mesh to be connected (vertices and faces)
- if not, it requires to connect all adjacent verts, and make CSG on penetrating faces
- flying geometry that don't touch nothing, will not be processed with that method
- there can be geometry, that penetrates rooms, and can't be cut by a portal, so it will connect both rooms and will fool the algorithm into thinking that they are one. That can be fixed, by tracking very carefully 'front' faces.

If implemented stable (csg!), this algorithm is maybe the fastest one though.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this