The yellow circle represents the player in this 2d level, with the little yellow line representing the player's look vector.

Each convex polygon (blue lines) is a sector, the magenta lines are adjoins between the sectors.

The gray lines represent the portal culling frustum, which starts at the player. The angle between the gray lines begins with the player's field of view (FOV), which is 60 degrees in this example.

The bright green lines are the segments of portals that have been clipped by the portal culling frustum.

Sectors that are highlighted have been determined visible by the algorithm, given the current player position, look vector, and field of view.



The program is not done, i still need to do some poly-poly clipping on the view areas

So instead of the map we get this?

Curious. XD Should prove fun to mill around with. And give you ideas where it's best to hide yourself on a map. =D

[QUOTE=Pedro T Hutt]Curious. XD Should prove fun to mill around with. And give you ideas where it's best to hide yourself on a map. =D[/QUOTE]

I don't think you understand the true purpose of this :p

It's a program that tells the rendering engine what to render. Ideally you only want what is visible to the player rendered, while everything else is left alone.

Impressive. That's always a good choice for optimizing your rendering.

It has other applications as well; for not just graphics but also gameplay. This algorithm could be run on any object in the game world; you could determine exactly which objects or sectors are visible to an AI character, for example. Simulating mirrors is also possible (as most of you have already seen, used in sith2's water reflections).


EDIT:
once i write the poly-poly clipping code so the project looks a little cleaner, ill upload a copy and let everybody play with it i imagine at least a few people would be interested

I thought though that in most games, not only the sectors that you could see are rendered, but the sectors that are visible from those sectors as well. Isnt it a 2 step process?

[QUOTE=Cool Matty]I don't think you understand the true purpose of this :p

It's a program that tells the rendering engine what to render. Ideally you only want what is visible to the player rendered, while everything else is left alone.[/QUOTE]

Well, you didn't tell us much about it for starters, or at least, not in plain english. =D. But while an interesting idea, couldn't that prove a bit troublesome should you suddenly decide to turn around as then the game has to render all that stuff you weren't looking at? But in theory it is a good idea to safe resources.

I could understand starting with a 2D implementation back in the old days, but if you're going to do 3D rendering with an API like OpenGL or DirectX, is it really necessary? Why not just acquire the frustum planes in the usual way and use those to detect visible adjoins/sectors, and then recursively render the visible sectors?

its more for the experience. both bsp (and its derivatives like quadtree) *and* cell and portal are still widely used, sometimes a combination of both in more sophisticated engines.

there are multiple advantages with using cell and portal. the biggest is efficiency; geometry that is not potentially in view is not even considered for rendering. the disadvantage, especially with a lot of fanmade JK levels, is the number of visible portals at any given time can go through the roof, and actually cause a drop in framerate. but if levels are designed with the algorithm in mind, some staggering increases in performance can be achieved.


another really cool thing with cell and portal is you know literally every unit of space that is visible. you can take an x,y,z coordinate and know if it is in view or not, given any camera transformation in a 3d world. objects can essentially be sorted by which sector they are in, so while going through the cell and portal process, each cell that is rendered can have any objects within it tested with the current portal culling frustum. the result is less number of objects being drawn when they really arent visible.

there is still a large cost for rendering things that cant actually be seen. this is called 'overdraw' and it is the goal of visibility determination algorithms like bsp and cell&portal to reduce this overdraw factor as much as possible.

someone said you could do a frustum test with all the sectors or all the portals, and just render those. that would work, sure. but if you have a thousand sectors or a thousand portals, you still have to loop through those every frame and test each one. and there is still a large overdraw cost as objects and sectors behind what is visible are still technically rendered.

there is also a problem with geometry sorting. it is actually faster to render things that are nearest to the camera first, as the z-buffer will block actually rasterizing geometry that is behind something already drawn on the screen. however, certain special effects such as translucency or really any type of blending requires that it be drawn last, on top of anything already visible (this problem is evident in JK when using translucent surfaces on a 3do). going through all the sectors as a big list doesnt give geometry in a sorted set in any way, but with cell and portal you get the geometry back sorted breadth-first by nature of the algorithm. Specifying whether an object or sector is drawn before or after another cell is as easy as putting the rendering code before or after the recursing function call.

Very interesting, thanks!

Not if you detect which sector the player is in first, and then recursively scan connected sectors. You then make sure the player is in the same sector each frame, and if he isn't, then you check the connected sectors. This would prevent you from having to loop through all of the sectors every frame, unless, of course, the player was teleported. Of course, you could even stop looping through all sectors in this scenario if you used an octree/portal hybrid.

That's certainly a plausible solution, except there can still be instances of a pretty large amount of overdraw. For example, if you are in an outside area looking at a few buildings with windows/doorways that lead into a more intricuite inside.

With a dynamic portal frustum, only the cell inside the building that the window is connected to would be drawn. With a connected-cell frustum test like you describe, the entire contents of the building(s) would be rendered. In a case like that, you will probably have a bigger performance penalty than just drawing the extra sectors, since you are still traversing through the JKL graph and culling portals for geometry that no way in hell would be visible; which could be in the hundreds or possibly thousands depending on which way the camera was oriented towards the geometry. For example, facing the opening of a tunnel network that extends somewhat consistantly in one direction would be a high amount of overdraw.


The C&P also requires that the camera's sector be known at start of the algorithm. A far more optimal way than recalculating this for the camera/every object per frame is to keep track of the current sector, and change the sector ID when an adjoin is crossed (JK does this for things, and it is why you can not CreateThingAtPos() without specifying a sector. TeleportThing works by inheriting the destination thing's sector).

That's pretty much what I said. :/




Good point, I suppose it could be solved occlusion tests, but I see what you're getting at. In any case, it's not my algorithm, so I shouldn't be so quick to jump down your throat. It looks cool, and I anticipate the final product.

I actually considered doing hardware occlusion queries to cull portals. Basically you would render whatever current cell, then render its portals using occlusion queries. If a portal had any fragments that passed the z buffer, you know it is at least partially in view and you can continue the test from there. The only real problem is, you'd have to know the results from 1 batch of portals before being able to do another ply, and I can almost gaurantee there is some kind of performance cost for each batch of occlusion queries (if it is processed on the graphics hardware, there is communication across the bus, which is a bottleneck, and a few portals per test is a very trivial amount of data to process). one cool thing about hardware occlusion queries is it would actually eliminate the need for disabling a sector's adjoins in the case of opening doors. If the cell's objects were rendered alongside the cell itself, the portal culling would automatically take into account the possibility of an object completely blocking a line of sight through a portal; for free. In general, though, it wouldn't be worth it.

I definitely understand where you're coming from, though. All the math and such involved seems like (and can prove to be) a good deal of overhead, but I think in the end it is probably worth it. I'm considering some ideas for speeding up the culling process by reducing the number of portals. Frankly, in the average JK level, there are way more portals than there really need to be. Note: I'm talking about PORTALS not necessarily adjoins. Sector adjoins are critical to maintain convex polyhedra. However, 'cell clusters' could be formed by 'merging' multiple adjacent cells into one group (with the group usually having a concave shape, but this is ok). The optimization comes into play by eating portals that almost always depend on the visibility of another portal.

Consider the following theoretical example:
Take your basic starting sector in JED. Now cleave and delete a square shape from the center of the sector. You've now created 6 portals, when really no matter which way the camera is oriented in the sector, you're pretty much going to get all the cells flagged as visible, yet you are still casting a culling frustum through all 6 portals or whatever. Clustering these cells together would remove a lot of CPU computation and although creating overdraw, the graphics hardware can handle it. The CPU remains free during this saved time to perform pathfinding or script execution or process particles. Even if you were in a hallway connected to this room, chances are almost all of the sectors would still be tested positive for visibility. Now the portal between the hallway and this cluster of cells should be preserved.

I can think of 2 problems straight off the bat, though:
a) the process of actually clustering cells. how do you know which portals
are redundant?
b) concave polyhedra can result in false positives for portals leading out from the cell cluster, resulting in overdraw since none of the geometry actually in that cell cluster can reject portals. however, even eating just 1 portal for every other 1 portal would result in potentially half as many portal culls; and the resulting overdraw would probably be pretty minimal to where it might be worthwhile. exact visibility portal culling requires that the current portal to test be clipped to the current culling frustum (which is not a traditional 6-plane frustum, but has N+2 number of planes, where N is the number of edges of the previously clipped portal polygon) and poly-to-poly clipping is a fairly expensive operation to perform many times per frame (the operation is roughly O(N*M) where N is the number of edges in the clipper polygon, and M is the number of points in the clippee polygon).

UPDATED:



The yellow circle represents the player in this 2d level, with the little yellow line representing the player's look vector.

Each convex polygon (blue lines) is a sector, the magenta lines are adjoins between the sectors.

The gray lines represent the portal culling frustum, which starts at the player. The angle between the gray lines begins with the player's field of view (FOV), which is 60 degrees in this example. *Update* the visible area is now highlighted

The bright green lines are the segments of portals that have been clipped by the portal culling frustum.

Sectors that are highlighted have been determined visible by the algorithm, given the current player position, look vector, and field of view.