2
$\begingroup$

Let's assume we have a 3D model consisted of XYZ-formatted vertices (such as point cloud model). My problem is given the position and normal of camera or camera projection (i.e. where I am looking at the points- usually given by my API), how can I extract the visible points and remove the non-visible points?

For instance here points corresponding to the black point cloud box and the back surface of the red box are removed. In point clouds, points have a size. So let's assume they have a size, say 5 pixel radius just for modeling purpose.

P.S. It doesn't have to be perfect. Just any approach to somehow remove the non-visible points so to decrease the total points with not much impact on the visible points will work.

Here is a test point cloud model to work with: https://www.dropbox.com/s/dfhyy9xa5i9o2fz/testPLY.ply?dl=0

enter image description here

Improve this question
$\endgroup$
18
  • 1
    $\begingroup$ Note that which faces are hidden depends on the whole camera projection, not just the position and normal. Say you look at one face of a cube, but deform the cube into a frustum where the near face is slightly smaller than the far face. The other four faces might be visible in an orthographic projection but not in a perspective projection. $\endgroup$
    – Dan Hulme
    Commented Jun 22, 2017 at 16:03
  • 1
    $\begingroup$ I don't think it does make the problem simpler. If you don't know the connectivity of the points, you don't know where the faces are, so you can't test for occlusion at all. I think mesh reconstruction needs to be the first step of your algorithm, unless an approximation is good enough (e.g. if a point is within a half-degree of another from the camera's pov, one occludes the other) $\endgroup$
    – Dan Hulme
    Commented Jun 22, 2017 at 16:12
  • 1
    $\begingroup$ Seems like you might want to do a sort of software render. You can create a buffer and initialize it with max z value. For each vertex apply MVP to find the x, y coord in the buffer. perform depth testing and if passes store new z and vertexID. If you have a buffer the size of your screen then you have perfect precision, if you create a buffer less than your screen size you improve performance at accurracy expense. You can probably clusterize and compute with a compute shader. $\endgroup$
    – Felipe Lira
    Commented Jun 22, 2017 at 23:17
  • 2
    $\begingroup$ @TinaJ A mathematical point can't occlude another because they have zero size. Only the surface can occlude. To take your diagram, what if the orange object were a doughnut? How would we know we can see through the middle of it? You need more information about the nature of this point cloud to decide what surfaces the points represent. You probably have that if you know what the real-world objects are, but you haven't told us anything about that. $\endgroup$
    – Dan Hulme
    Commented Jun 23, 2017 at 8:21
  • 1
    $\begingroup$ @TinaJ The point is, how big does the gap between points have to be before you think it's a doughnut hole? We can't know that (or even if there is a value that makes sense for that) without knowing something about what the points represent in the real world. $\endgroup$
    – Dan Hulme
    Commented Jun 23, 2017 at 10:16

2 Answers 2

Reset to default
4
$\begingroup$

Idea A:

Draw an invisible mesh that will occlude the points we don't want.

  1. Create a mesh from the point cloud.
  2. Render that mesh to a depth buffer but not to the color buffer.
  3. Render the point cloud using a depth test "closer or equal".

This approach should give the expected result, but the problem with it is the first part, which is not trivial at all.

Idea B:

Approximate the mesh with fat particles, that are big enough to hide points in the background.

  1. Pick a size that is roughly the typical distance between two points.
  2. Use that size as a particle diameter.
  3. Render the point clouds using such large particles, to a depth buffer but not to the color buffer. Maybe offset that point cloud a little, so it's a bit farther from the camera.
  4. Render the point cloud using points this time, and using a depth test "closer or equal".

This method should be a lot simpler to implement than A, because there is no need to triangulate anymore. The result will not be perfect though: some points that should be visible might disappear, and some that shouldn't be visible will remain visible. Tweaking the particle diameter and offset will yield different results.

Idea C:

As a very cheap trick, just render the point cloud with a fog function. The farther points are from the camera, the less visible they are. This method won't hide any point, but still help reading the volume.

Improve this answer
$\endgroup$
7
  • 1
    $\begingroup$ Part 1 is the sticky point, it is in fact the problem. This makes the question subjective as the mesh creation in fact has same definition problem as the question in general. We can not give qualitative advice because we dont know what the data is supposed to mean. Only the original author can nknow what the broder constraints should be. And in this case it seems OP does not so we can not really help. It affects the choice of disk size in method 2 too. $\endgroup$
    – joojaa
    Commented Jun 27, 2017 at 8:55
  • $\begingroup$ Thanks. It is a good description. But we don't know if they work unless we test them. Are you aware of any implementation, source code, or anything? $\endgroup$
    – angel_30
    Commented Jun 27, 2017 at 14:33
  • $\begingroup$ At that point you'd have to start experimenting. C should be trivial to implement, B is simple but a little more involved, and as said, the triangulation for A is really problematic. Not only it is an open problem, but I'd expect existing solutions to be tedious to implement. I would recommend finding a library that does a half decent job at it. $\endgroup$
    – Julien Guertault
    Commented Jun 28, 2017 at 7:32
  • $\begingroup$ @JulienGuertault Hi Julien. On A.2, what do you mean of "render the mesh busing a depth buffer but not color buffer"? Is that a known technique? Any references? $\endgroup$
    – angel_30
    Commented Aug 2, 2017 at 17:11
  • 1
    $\begingroup$ @TinaJ Before rendering the mesh, you just disable writing to the color buffer. The depth will be written but the image will be left untouched. It's pretty standard, although the details will depend on the API or software you are using. $\endgroup$
    – Julien Guertault
    Commented Aug 4, 2017 at 12:14
3
$\begingroup$

Conceptually simplest would be to treat it as a ray-casting problem, representing each point as a small sphere. It should work like the shadow rays in a conventional raytracer: iterate over all of your points, and for each one, trace a ray to the camera. If the ray intersects the sphere representing another point, then remove it.

If the number of points is small enough, you can do this directly, but if that's not fast enough, you should put the points into an acceleration structure such as a kd-tree. (If you need this kind of optimization, it might be best to start from an existing ray-tracer such as PBRT instead of writing it from scratch.)

If the points represent surface detections (from something like a laser scanner), you might also have the surface normal at each point, depending on the scanner technology. In this case, you might get better results by using small discs instead of spheres. That'll be more robust on faces seen at a glancing angle.

Finally, if you also need to remove points that are outside the camera's view (e.g. behind the camera), you can do this at the same time by comparing the direction of each ray with the camera's view bounds.

Improve this answer
$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.