Determining whether a point will be drawn.

Before asking a question, I ask you to excuse me
about using POOR English.
I learned English, but I’m not good at English.

I learned that computer determines whether a point will
be drawn or not.(By using z buffer)
But, I want to know a information about it.

I’m making a simulator, and to make it, I should
know whether a point is located inside
3d-objects(with arbitrary shapes) , or not.
To know it, I decided to use OpenGL. I thought that
if I draw a object and a point, then I can know the information
about position relationship between a objects, and a point.

But, after I succeed to draw it, I realize that there is no
function that give the information that I want to know.

Is there a algorithm, or method to know it?

Thanks for any advice.

I assume that you represent your 3D objects in some kind of piecewise linear fashion, e.g. a triangle or quad mesh. If for this mesh your normals are consistent (they all point outwards) you could run a plane-distance test for all the triangles/quads in your mesh.

You know that for your point to be inside the object, the distance to all the planes has to have the same sign (positive or negative depending on convention). This test would not require opengl and would be quite slow if your 3D objects are detailed.

A way of doing it in hardware might be to render into two separate depth buffers. The first is for the closest triangles that are facing you, the second for the closest back facing triangles. Once you have these two textures (depth buffers), you just have to render your point and figure out which pixel/pixels it maps to and check that it is inside the interval spanned by your two textures.

Please let me know if this is unclear!

A very simple and effective approach, is to use the extension http://www.opengl.org/registry/specs/ARB/occlusion_query.txt if it’s available to you.

This is only true for convex 3D models, not concave ones…

N.

Nicolai: Will the occlusion_query not just let you know whether the point gets rendered or not? I.e. if the point is behind the 3D object the answer is false, otherwise true. This does not answer the question of whether it is inside or not?

Nico: Well, the only requirement I can think of is that the primitives of the 3D object do not intersect. In this case there is a clear distinction between inside and outside. Is this what you meant?

For really fast lookup one can also generate a signed distance field of the 3D object (google: level sets), but this is quite involved.

Not really…

For convex 3D objects the distances to all primitives have the same sign:


_____________
|           |
|           |
|    x      |
|           |
|___________|


For concave 3D objects this is not the case:


_____________
|        _  |
|       | |_|
|    x  | __
|       |_| |
|___________|


N.

Nico: You are right, thanks for the illustration.

I will stick with recommending the signed distance field approach which works without exceptions for water-tight meshes.

I also realized that the approach of using two depth buffers doesn’t work either because of the concavity issues that Nico pointed out.

Thanks for your advice.

I think that I should think more about it.
I also should care about “Inner empty spaces”
like a core-shell.
(or more complex concave inner empty spaces).

If you have a good idea,

Please tell me by replying , or by sending E-mail to me.