CODEWITHSUNDEEP
c++geometrymeshnormals
ocular
ocular

Reputation: 11

Normal of point via its location on STL mesh model

Can someone tell me the best way to estimate the normal at a point on CAD STL geometry?

This is not exactly a question on code, but rather about efficiency and approach.

I have used an approach in which I compare the point whose normal needs to be estimated with all the triangles in the mesh and check to see if it lies inside the triangle using the barycentric coordinates test. (If the value of each barycentric coordinate lies between 0 and 1, the point lies inside.) This post explains it

https://math.stackexchange.com/questions/4322/check-whether-a-point-is-within-a-3d-triangle

Then I compute the normal of that triangle to get the point normal.

The problem with my approach is that, if I have some 1000 points, and if the mesh has say, 500 triangles, that would mean doing some 500X1000 checks. This takes a lot of time.

Is there an efficient data structure or approach I could use, to pinpoint the right triangle? Or a library that could get the work done?

Upvotes: 1

Views: 518

Answers (1)

user1196549
user1196549

Reputation:

A relatively easy solution is by using a grid: decompose the space in a 3D array of voxels, and for every voxel keep a list of the triangles that interfere with it.

By interfere, I mean that there is a nonempty intersection between the voxel and the bounding box of the triangle. (When you know the bounding box, it is straight forward to tell what voxels it covers.)

When you want to test a point, find the voxel it belongs to and compare to the list of triangles. You will achieve a speedup equal to N/M, where M is the average number of triangles per voxel.

The voxel size should be chosen carefully. Too small will result in a too big data structure; too large will make the method ineffective. If possible, adjust to "a few" triangles per voxel. (Use the average triangle size - square root of double area - as a starting value.)

For better efficiency, you can compute the exact intersections between the triangles and the voxels, using a 3D polygon clipping algorithm (rather than a mere bounding box test), but this is more complex to implement.

Upvotes: 1

Related Questions