# Check if point in space is completely enclosed by faces

This topic is 2146 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

Hi,

I want to check if a certain point or box in space (3D) is completely surrounded by faces (e.g. rectangles), so that this point or box is not visible from any location with a certain minimum distance.

Do you know of such an algorithm?

To make it clearer:

Imagine a minecraft style game. There may be caves in the underground, but when you're outside the cave, and the cave does not have any entrance, anything in the cave cannot be seen, from no direction. I want to detect if something is inside such a "cave", so it doesn't need to be rendered (unless you drill a hole and enter the cave).

Thanks,

c++good

##### Share on other sites
Set up each box you want to render with 6 booleans for each side. Flag those when there is a box next to them. Create a list for all the boxes you want to render using these booleans. You only need to update the booleans when a box next to it changes.

##### Share on other sites

Set up each box you want to render with 6 booleans for each side. Flag those when there is a box next to them. Create a list for all the boxes you want to render using these booleans. You only need to update the booleans when a box next to it changes.

This would just eliminate the boxes that have a direct neighbor. I want to detect also if the box is occluded by more distant faces; in my "cave" example, I want to eliminate drawing the inner walls of the cave, too.

Also, minecraft was just an example to illustrate. I need a solution also for occluders and occludees that are not only equally sized cubes. The occludee is a bounding box for an arbitrary shape; the occluders are rectangles of arbitrary size and orientation, but typically these rectangles have adjacent edges and form a closed inner surface, like the inner wall of a house made of bricks of varying size. I want to check if these rectangles surround the inner box without any holes.

Edited by cdoubleplusgood

##### Share on other sites

I want to check if a certain point or box in space (3D) is completely surrounded by faces (e.g. rectangles), so that this point or box is not visible from any location with a certain minimum distance.

All I can think is this: Place a camera at the certain point, render the scene from its point of view (for instance into a cubemap) and see if anything was rendered farther away than the minimum distance. If you want to check the visibility of a box, it sounds even harder (test a bunch of points in the box and hope for the best?). Hopefully you only need to do this offline.

##### Share on other sites

You need to look into Potentially Visible Sets.

L. Spiro

##### Share on other sites

Place a camera at the certain point, render the scene from its point of view (for instance into a cubemap) and see if anything was rendered farther away than the minimum distance. If you want to check the visibility of a box, it sounds even harder (test a bunch of points in the box and hope for the best?). Hopefully you only need to do this offline.

Yes, it's offline, and only for more distant parts of the scene. It's kind of heuristic, but maybe a good starting point.

Thanks.

##### Share on other sites

Can't you just use a ray cast and count intersections? Odd = in, even = out? Maybe I don't understand the question, but see here:

http://en.wikipedia.org/wiki/Point_in_polygon#Ray_casting_algorithm

Should work fine for 3D as well, assuming your mesh is water tight.

##### Share on other sites

Can't you just use a ray cast and count intersections? Odd = in, even = out? Maybe I don't understand the question, but see here:

http://en.wikipedia.org/wiki/Point_in_polygon#Ray_casting_algorithm

Should work fine for 3D as well, assuming your mesh is water tight.

It's a cave. Of course it's not water tight. I think you misunderstood the question.

EDIT: I reread the question and now I am not sure either. I thought he was trying to save the work of drawing most of the contents of a cave that is kind of twisted, so from a distance only the entrance can be seen.

Edited by Álvaro

##### Share on other sites

You need to look into Potentially Visible Sets.

L. Spiro

Great, that gave me the right keywords.

##### Share on other sites

I reread the question and now I am not sure either. I thought he was trying to save the work of drawing most of the contents of a cave that is kind of twisted, so from a distance only the entrance can be seen.

Not exactly. I want to skip drawing the interior of a "cave" (or room) that doesn't have an entrance at all (until the player creates an entrance).

• 19
• 22
• 23
• 16
• 11
×

## Important Information

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!