How to determine the visibility of a single vertex, given a viewpoint?

Question

I have a 3D triangle mesh, and I want to know, given a viewpoint (defined by a model, view and projection matrix), if a certain vertex is visible or not.

My approach was to render the mesh using standard software rasterization (I can't use OpenGL/DX), i.e. project all the triangle vertices to screen-space, then loop through each triangle's bounding-box and rasterize/shade the pixels inside the triangle (using barycentric coordinates). I'm also using a z-Buffer here, and the rendering works fine.

To find out if a certain vertex point is visible, my naive idea was then to just project that vertex from 3D to 2D using the same matrices, and comparing the z-value I get for that pixel to the value in the z-Buffer.

However, this approach does not work, I get vertices flagged as visible that should be invisible and vice versa.

I believe this is because of the following: When I render the triangles, I loop over the bounding-box of the triangle and set the color and depth value by interpolating a value between the 3 triangle vertices, using barycentric coordinates. Thus, the depth value written to the z-buffer for a given point (x, y) on screen is a linear combination of the z-value of the 3 vertices that make up the triangle. In contrast to that, when I project the single vertex later, I render the exact point, independent from any triangles, and thus get a different z-value for the same (x, y) location on screen.

Is my assumption on why it is not working correct, and how would I correctly determine the visibility of a vertex in the mesh?

Update: Let me clarify what's going on with this picture:

Let's say v0 = (1.1, 1.1), v1 = (6.7, 2.1), v2 = (3.7, 6.7) after projection to screen-space. When rendering/rasterizing the triangle, I have a loop

for x = 1 to 7 // from floor(min(v0.x, v1.x, v2.x)) to ceil(max(v0.x, v1.x, v2.x))
    for y = 1 to 7 // same for y
        current_pixel_center = (x+0.5, y+0.5); // we want calculations to use the center of pixels
        alpha = ..., beta = ..., gamma = ...; // calculate the barycentric weights for current_pixel_center
        if all 3 bary. weights > 0 // means the pixel is inside the triangle
            z_value_of_curr_pixel = alpha * v0.z + beta * v1.z + gamma * v2.z;
            // Do the z-test and then draw the pixel at position (x, y), and set the z-buffer at (x, y) to the new value 'z_value_of_curr_pixel'

So the pixel at position (1, 1) in my drawing gets some color and z-value based on the barycentric weights calculated for this point, it is close to v0 so probably something like alpha = 0.95, beta = 0.02, gamma = 0.03.

Now, in contrast to that, I am later interested in knowing if the single vertex v0 is visible (I don't have any information about triangles at that point). So I project the vertex v0 which will land at (1.1, 1.1) in screen space and end up with a z-value as well. However this z-value will be different than the one that is in the z-buffer for this pixel, because the z-value in the z-buffer has been calculated using the barycentric weights of the triangle for the middle point of the triangle. So I can't determine if the vertex v0 is visible or not.

To rephrase: The z-value in the z-buffer is from the red dot in the image (produced when rendering the triangle), and it is different from the z-value of the projection of the vertex v0 which is exactly at position v0.

Answer 1

The assumption you've made is that depth is linear in screen space. This is true for orthographic projection. If you're using a perspective projection this assumption no longer holds true for 3 dimensions.

For classic perspective projection you must interpolate the reciprocal of depth in screen space in order to account for the division by the w component that occurs due to the nature of perspective projection. So you need to interpolate 1/depth in screen space. If you need depth at a particular location it can be inverted after interpolation occurs.

Assuming you understand these details then the implementation you described of a depth buffer should work just fine.

Answer 2

Rasterization will never give you precise results because of subpixel inaccuracies like the one you described. You can of course improve accuracy by increasing resolution. You can also bias the result to make either false positives or false negatives more likely.

To get a more accurate answer you can use ray tracing techniques. This will also be slower unless the polygon count is low. You want to cast a ray from the camera to the point and do ray-triangle intersection tests on all triangles. You can reduce the number of triangles to test by using spatial subdivision on the triangles (e.g. a k-d tree).