Hi, ive been working on my portal/sector based engine for a while now but I do not know how to go about finding the sector that a given point is in. I do have a few ideas but they are too slow for my perposes as this would be called several times per frame. One way I have thought of is organising the sectors into a BSP tree, but I have know idea about how to choose the splitting planes for such a tree. Any suggestions for both the BSP or alternatives would be greatly appreciated.

i assume that all objects originate either from an editor-placed spawnpoint, or from another object, which is originating at an editor-placed spawnpoint.

the thing with this being that you can use a slow method of calculating the sector a spawnpoint is in, in the editor, by testing against every polygon in the nearby sectors.

after this, you know which sector an object starts in, and so
when you move a significant distance, you can determine VERY QUICKLY which sector the entity is now in.

1. do a facing test against all of the portals in the last known location.

2. if one fails (we''re on the outside of the sector, through this plane), move to that sector and repeat.

3. if you find a node with no failures, that''s your sector!

known flaws in this technique:
1. you cant use it to determine the initial location of an object, because there may well be several sectors (that are not connected together by a portal) which satisfy the plane-side conditions. therefore, you must do a slow thing to determine the initial sector.

2. in order to prevent ''lost'' objects, the current sector must be determined frequently, preferably every time the object moves a considerable distance, but this should not be a problem, since it is most likely cheaper than your collision detector

Thank you for your reply Qatal, but unfortunatly I am not working with convex sectors so I don''t think that this approach would work.

I''d also thought of doing something similar with the collision detection code but how do you deal with a teleporting character or something that goes through walls (such as a "wall walk" type of camera used by level designers)?

The only reliable way I can think of is some form of spacial data structure, such as a BSP tree. An Octree would be easier to implement but lacks accuracy.

I did come across one engine that built a BSP tree by forceing the splitting planes to be along the plane of portals placed in the editor, it then merged the leaves in the tree to form the sectors. Maybe I may HAVE to go with this approach, unfortunatly it seems to be more a BSP engine then portal/sector....

Dunno, I need to keep thinking... Thanks anyway

are you meaning that you also need to be able to find out if a point is *in* a sector, as well as which one it is in.

my method does not require convex sectors btw, my engine doesnt use convex sectors, adn it works fine.

is this being used as your collision detector as well? that could be tricky.

for the bad case where you cant track movement through portals, you can find it by a brute-force method:

simply test aganst ALL the significant polys in a sector, rather than just the portals.

i didnt suggest this because i thought it wouldnt be needed...

The point to sector code is used for rendering and will also be used for collision detection (I havent written it yet ). Elimination of redundent sectors is the first step for both processes. This is why the code MUST be fast and why I need to know if it is *in* a sector.

I think the BSP approach to sorting the sectors would be perfect if only I could figure out a way to build it...

As for the convex/concave sectors thing, what happens if you have a setup like so:

+-------------+
|......x......|
|.............|
|...+----+....|
|...|....|....|
|...+****+....|
|.............|
+-------------+


The x is the current point is question and the *** are a portal that links to a staircase, mirror or some other affect. The portal is back facing and the algo would try another sector. This is also possible with other shaped concave rooms. Or am I missing something?!?

Any more suggestions Qatal?!? I'm scraping the bottom of the barrel...


[edited by - Digitalblur on January 7, 2004 11:11:33 PM]

DAM ASCII art...

Lets try that again... Think of a square room with a box in the middle, one side of this box is a portal to a staircase, mirror, etc. And the point in question is on the other side of this box, the portal would fail your test...

Does that description make sense?!? I hope so...

Dam i''m slow... I don''t know why i didn''t see this before: All I have todo is build a leafy BSP tree as I would normally but include the portals as candidates for the splitting planes. Then I can use the leafs that contain the portals to tag each leaf within the tree with the sector it belongs to

All Im required to store are the splitting planes & possibly the set of planes that describe the convex hull at the leafs of the tree.

To figure out the sector a point is in, I walk the tree untill I get to a leaf. The leaf has a convex hull and a sector id, if the point is outside the convex hull then the point is not inside the level, otherwise I can use the sector id.

Provided I use only the external polygons of a sector to build the tree it wont be very large and will be REALLY quick to find the sector a point lies in