search

akuukka / quickhull

C++ implementation of the 3D QuickHull algorithm
266 stars 52 forks source link

Not getting all the triangles in a hull. #1

Closed shekarmantha closed 8 years ago

shekarmantha commented 8 years ago

I am using this library and I think I found a problem. Not sure where to post this question so I am posting it here.

If I have a set of four points:

(-3.000000 -0.250000 -0.800000) (-3.000000 0.250000 -0.800000) (-3.125000 0.250000 -0.750000) (-3.125000 -0.250000 -0.750000)

I am able to create a hull but the hull only has two triangles:

`-3.000000 -0.250000 -0.800000 -3.437502 0.250000 -0.624999 -3.000000 0.250000 -0.800000 -3.437502 0.250000 -0.624999 -3.000000 -0.250000 -0.800000 -3.437502 -0.250000 -0.624999'

I would have thought there would be four triangles since the 4 input points above form a tetrahedron. Am I missing something?

akuukka commented 8 years ago

Thanks! I will investigate this.

shekarmantha commented 8 years ago

Thank you. I really appreciate your work. If I can help, please tell me. I can code and test as well.

On Jun 22, 2016, at 8:40 PM, Antti Kuukka notifications@github.com wrote:

Thanks! I will investigate this.

— You are receiving this because you authored the thread. Reply to this email directly, view it on GitHub https://github.com/akuukka/quickhull/issues/1#issuecomment-227941875, or mute the thread https://github.com/notifications/unsubscribe/AQZFz7saXV2zh_Zc8h3IBOxV6vfuxJO5ks5qOgA-gaJpZM4I8WZf.

akuukka commented 8 years ago

The points you have given all lie on the same plane so the "tetrahedron" they form is infinitely thin.

shekarmantha commented 8 years ago

Yes, but is that what is preventing them from forming a tetrahedron? OK, I will look into why this is happening in my code. I am trying to compute a hull based no the intersection of a hexahedron and a tetrahedron and that data is coming from an external source.

Thanks

On Jun 22, 2016, at 8:48 PM, Antti Kuukka notifications@github.com wrote:

The points you have given all lie on the same plane so the "tetrahedron" they form is infinitely thin.

— You are receiving this because you authored the thread. Reply to this email directly, view it on GitHub https://github.com/akuukka/quickhull/issues/1#issuecomment-227942628, or mute the thread https://github.com/notifications/unsubscribe/AQZFzybV91Ef5Hftu32KOGuU3wn3d64Dks5qOgH2gaJpZM4I8WZf.

akuukka commented 8 years ago

Well, if QuickHull is given a point cloud where all points lie on the same plane, it will return a set of triangles that covers all the points but doesn't form a triangle mesh with volume.

Now that I think of it again, perhaps we should return an infinitely thin mesh in these degenerate cases... only a few lines of could would have to be changed.

shekarmantha commented 8 years ago

Yes. That would be useful. Since even if it is a thin mesh, it is still a mesh. And if you would like to put a tolerance around how thin a mesh you support, it could be something that can be configured.

On Jun 22, 2016, at 9:10 PM, Antti Kuukka notifications@github.com wrote:

Well, if QuickHull is given a point cloud where all points lie on the same plane, it will return a set of triangles that covers all the points but doesn't form a triangle mesh with volume.

Now that I think of it again, perhaps we should return an infinitely thin mesh in these degenerate cases... only a few lines of could would have to be changed.

— You are receiving this because you authored the thread. Reply to this email directly, view it on GitHub https://github.com/akuukka/quickhull/issues/1#issuecomment-227945087, or mute the thread https://github.com/notifications/unsubscribe/AQZFzx7Bvv_dI8bUTBdw1QmlVxt-oZS8ks5qOgdCgaJpZM4I8WZf.

akuukka commented 8 years ago

Agreed, I will update the code this week. Output will be a tetrahedron even if the point cloud forms just a line in 3D space.

shekarmantha commented 8 years ago

Cool. Thanjs On Jun 22, 2016 9:21 PM, "Antti Kuukka" notifications@github.com wrote:

Agreed, I will update the code this week. Output will be a tetrahedron even if the point cloud forms just a line in 3D space.

— You are receiving this because you authored the thread. Reply to this email directly, view it on GitHub https://github.com/akuukka/quickhull/issues/1#issuecomment-227946207, or mute the thread https://github.com/notifications/unsubscribe/AQZFz85f0MSOqW9miuBsODi5a-oE4bHbks5qOgnHgaJpZM4I8WZf .

akuukka commented 8 years ago

Fixed the problem. The output is now always a proper triangle mesh, even if it has no volume.

shekarmantha commented 8 years ago

Thank you.

On Jun 23, 2016, at 7:22 AM, Antti Kuukka notifications@github.com wrote:

Closed #1 https://github.com/akuukka/quickhull/issues/1.

— You are receiving this because you authored the thread. Reply to this email directly, view it on GitHub https://github.com/akuukka/quickhull/issues/1#event-701953629, or mute the thread https://github.com/notifications/unsubscribe/AQZFz2zA2M4foehtRrx2BOljKxDC-pygks5qOpakgaJpZM4I8WZf.