<p>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.</p>

<p>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.)</p>

<p>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.</p>

<p>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.</p>

CC BY-SA 3.0
2017-07-04T14:42:26.767Z
2017-07-04T14:42:26.767Z
Dan Hulme
<h3>Idea A:</h3>
<p>Draw an invisible mesh that will occlude the points we don't want.</p>
<ol>
<li>Create a mesh from the point cloud.</li>
<li>Render that mesh to a depth buffer but not to the color buffer.</li>
<li>Render the point cloud using a depth test &quot;closer or equal&quot;.</li>
</ol>
<p>This approach should give the expected result, but the problem with it is the first part, which is not trivial at all.</p>
<h3>Idea B:</h3>
<p>Approximate the mesh with fat particles, that are big enough to hide points in the background.</p>
<ol>
<li>Pick a size that is roughly the typical distance between two points.</li>
<li>Use that size as a particle diameter.</li>
<li>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.</li>
<li>Render the point cloud using points this time, and using a depth test &quot;closer or equal&quot;.</li>
</ol>
<p>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.</p>
<h3>Idea C:</h3>
<p>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.</p>

CC BY-SA 3.0
2017-08-02T17:11:06.080Z
@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?
angel_30
CC BY-SA 3.0
2017-08-04T12:14:51.710Z
@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.
Julien Guertault
CC BY-SA 4.0
2019-12-06T13:39:10.627Z
@JulienGuertault In Idea A, say #1 is done, how do you render the mesh into depth buffer?
June Wang
CC BY-SA 4.0
2019-12-12T21:54:51.820Z
@JuneWang You can render a mesh with depth writing enabled but without writing to the color buffer. See for example something called **"Z pre-pass"** or **"depth pre-pass"**.
Julien Guertault
CC BY-SA 3.0
2017-06-27T08:55:30.997Z
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.
joojaa
CC BY-SA 3.0
2017-06-27T14:33:04.553Z
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?
angel_30
CC BY-SA 3.0
2017-06-28T07:32:23.457Z
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.
Julien Guertault
CC BY-SA 3.0
2017-06-27T02:46:40.427Z
2017-06-27T02:46:40.427Z
2020-06-18T08:32:12.800Z
Julien Guertault
<p>Let's assume we have a 3D model consisted of <code>XYZ</code>-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?</p>

<p>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>

<p>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.</p>

<p>Here is a test point cloud model to work with: <a href="https://www.dropbox.com/s/dfhyy9xa5i9o2fz/testPLY.ply?dl=0" rel="nofollow noreferrer">https://www.dropbox.com/s/dfhyy9xa5i9o2fz/testPLY.ply?dl=0</a></p>

<p><a href="https://i.sstatic.net/eoovAm.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/eoovAm.png" alt="enter image description here"></a></p>

CC BY-SA 3.0
2017-06-22T16:03:43.193Z
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.
Dan Hulme
CC BY-SA 3.0
2017-06-22T16:08:11.617Z
@DanHulme OK. Let's assume we have the camera projection. Usually given by the 3D graphics API. Remember, we have points. Not meshes which makes the problem simpler.
angel_30
CC BY-SA 3.0
2017-06-22T16:12:34.783Z
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)
Dan Hulme
CC BY-SA 3.0
2017-06-22T16:18:19.620Z
@DanHulme Right. Probably we need some mathematical algorithms playing around with the XYZ coordinates and understand if a point is behind others. Or some other approach.
angel_30
CC BY-SA 3.0
2017-06-22T23:17:17.703Z
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.
Felipe Lira
CC BY-SA 3.0
2017-06-23T08:21:33.280Z
@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.
Dan Hulme
CC BY-SA 3.0
2017-06-23T10:08:34.623Z
@FelipeLira That's interesting. I didn't know it can be as complicated. Is there any reference/source code to that?
angel_30
CC BY-SA 3.0
2017-06-23T10:11:01.427Z
@DanHulme Well, you are right in general. But even with my simple mathematical assumption, the middle of donut is empty, no points there. So we should see whatever behind. It is like sending a beam to every single pixel visible from my projection. Then if two points are in the same line, we have to remove whatever behind.
angel_30
CC BY-SA 3.0
2017-06-23T10:16:04.993Z
@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.
Dan Hulme
CC BY-SA 3.0
2017-06-23T10:40:41.423Z
@DanHulme Yes the size of points in a point cloud matter to know if anything is visible in the behind or not. We can start from the simplest approach and assumptions independent. I've updated the question with a test model.
angel_30
CC BY-SA 3.0
2017-06-23T13:58:47.280Z
I think you're a bit optimistic if you think people will go download your file and run tests on it before they can answer your question usefully. You're most likely to get good answers when all the relevant information is in the question.
Dan Hulme
CC BY-SA 3.0
2017-06-23T15:06:20.720Z
The test file is to show what I mean of point cloud and the format for those who are not familiar. Yes, most important for me is the description of the approach.
angel_30
CC BY-SA 3.0
2017-06-23T17:32:31.623Z
A point (in the mathematical sense generally used in computer graphics) has zero size, as mentioned in previous comments. If you want an approach that will work with points that *do* have a size, we'd need to know what size the points are and how their size works. For example, does a point have some defined size in 3D space, or does it have a fixed 2D size independent of distance from the camera (maybe 4 pixels per point)? Using a non-standard definition of "point" is fine, but we can't answer without knowing what that new definition is.
trichoplax is on Codidact now
CC BY-SA 3.0
2017-06-23T21:36:32.440Z
@trichoplax yes In point clouds, points have a size. So let's assume they have a size, say 5 pixel radius just for modeling purpose. Updated the question.
angel_30
CC BY-SA 3.0
2017-06-23T22:27:29.640Z
I see. So just to be explicit, points further away don't look any smaller, still 5 pixels?
trichoplax is on Codidact now
CC BY-SA 3.0
2017-06-23T22:29:10.057Z
It might be worth changing the example picture if you are interesting in points occluded by other points, rather than by polygonal faces. A picture showing points might make for less confusion.
trichoplax is on Codidact now
CC BY-SA 3.0
2017-06-23T23:23:41.737Z
@trichoplax Sure. I updated the figure. It should be clear what I mean.
angel_30
CC BY-SA 3.0
2017-06-25T09:27:15.360Z
There is no simple answer for this question simply because it depends on your interpretation of things and as such has many answers and none at the same time. Since you are not describing your qualitative border constraints. So the question might as well be how to create a mesh fom a pointcloud.
joojaa
<3d><computational-geometry><geometry><mesh><normal-mapping>
Extract visible vertices from a 3D geometry model
angel_30
# Extract visible vertices from a 3D geometry model

(Asked by: username_0 on 2017-06-22)

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](https://i.sstatic.net/eoovAm.png)](https://i.sstatic.net/eoovAm.png)

**Tags:** 3d, computational-geometry, geometry, mesh, normal-mapping

> **Comments:**
> **username_1**: 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.  
> **username_0**: @username_1 OK. Let's assume we have the camera projection. Usually given by the 3D graphics API. Remember, we have points. Not meshes which makes the problem simpler.  
> **username_1**: 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)  
> **username_0**: @username_1 Right. Probably we need some mathematical algorithms playing around with the XYZ coordinates and understand if a point is behind others. Or some other approach.  
> **username_2**: 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.  
> **username_1**: @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.  
> **username_0**: @username_2 That's interesting. I didn't know it can be as complicated. Is there any reference/source code to that?  
> **username_0**: @username_1 Well, you are right in general. But even with my simple mathematical assumption, the middle of donut is empty, no points there. So we should see whatever behind. It is like sending a beam to every single pixel visible from my projection. Then if two points are in the same line, we have to remove whatever behind.  
> **username_1**: @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.  
> **username_0**: @username_1 Yes the size of points in a point cloud matter to know if anything is visible in the behind or not. We can start from the simplest approach and assumptions independent. I've updated the question with a test model.  
> **username_1**: I think you're a bit optimistic if you think people will go download your file and run tests on it before they can answer your question usefully. You're most likely to get good answers when all the relevant information is in the question.  
> **username_0**: The test file is to show what I mean of point cloud and the format for those who are not familiar. Yes, most important for me is the description of the approach.  
> **username_3**: A point (in the mathematical sense generally used in computer graphics) has zero size, as mentioned in previous comments. If you want an approach that will work with points that *do* have a size, we'd need to know what size the points are and how their size works. For example, does a point have some defined size in 3D space, or does it have a fixed 2D size independent of distance from the camera (maybe 4 pixels per point)? Using a non-standard definition of "point" is fine, but we can't answer without knowing what that new definition is.  
> **username_0**: @username_3 yes In point clouds, points have a size. So let's assume they have a size, say 5 pixel radius just for modeling purpose. Updated the question.  
> **username_3**: I see. So just to be explicit, points further away don't look any smaller, still 5 pixels?  
> **username_3**: It might be worth changing the example picture if you are interesting in points occluded by other points, rather than by polygonal faces. A picture showing points might make for less confusion.  
> **username_0**: @username_3 Sure. I updated the figure. It should be clear what I mean.  
> **username_4**: There is no simple answer for this question simply because it depends on your interpretation of things and as such has many answers and none at the same time. Since you are not describing your qualitative border constraints. So the question might as well be how to create a mesh fom a pointcloud.  

---

## 2 answers

### Answer by username_5 on 2017-06-27. Score: 4 | Accepted answer

### 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.

> **Comments:**
> **username_4**: 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.  
> **username_0**: 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?  
> **username_5**: 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.  
> **username_0**: @username_5 Hi username_5. 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?  
> **username_5**: @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.  
> **username_6**: @username_5 In Idea A, say #1 is done, how do you render the mesh into depth buffer?  
> **username_5**: @username_6 You can render a mesh with depth writing enabled but without writing to the color buffer. See for example something called **"Z pre-pass"** or **"depth pre-pass"**.  

---

### Answer by username_1 on 2017-07-04. Score: 3

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.


---

