flipcode - Room Finding

Room Finding
Question submitted by (26 July 1999)

i've been wondering about how i could find the room a point is in rather quickly and easily. by a room i mean an area surrounded by a convex shell of planes. either a 3d or 2d explanation would be good, should be about the same math.

here's an example problem to better view the situation. hope you're using a fixed width font.




+--------+          +-------+                the '+' == verts
|         \         |        \               the '-' and '|' == walls
|   1      +--------+         \              the rooms are numbered and
could be connected by
|          |   2    |   3      \                portals.
+----------+--------+           \            the 'x' == the point
                    |     x      \
                    +-------------+

now how would i find the room 'x' is in w/o knowing it first and be able to calculate it every frame? that layout could just as easily be 3d.

the use i'm planning on using this for it a portal type 3d engine and/or a gui(to find the mouse pointer in a n-gon window).

either a reference or an idea should be suffiecent. as long as it can get me to the point of finding where the point is.


	Here's a quick solution: Build an octree that simply stores which convex area(s) intersect each octree node (if any.) As you build your octree, continue to subdivide if more than one convex area intersects the given octree node. By doing this, you will get an octree traversal that is very fast and results in the convex area containing the input location. You can limit your octree depth, but by doing this you may have multiple convex areas that intersect the leaf node causing you to perform a limited search through a small set of convex areas. Response provided by Paul Nettle

This article was originally an entry in flipCode's Fountain of Knowledge, an open Question and Answer column that no longer exists.