Question submitted by (26 July 1999)
|Return to The Archives|
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
here's an example problem to better view the situation. hope you're using a fixed width font.
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.