CODEWITHSUNDEEP
algorithmsearchgeometrypoint
user3427995
user3427995

Reputation: 21

There is a point on a triangulated surface, how can i find triangle which contains the point?

We have a 3d triangulated surface and there is a point on it. How can i find the triangle which contains the point. We can find with testing all triangles but it is slow way. I must make the algorithm faster.

Is there any searching algorithm or is there any technique about reducing searching area?

Upvotes: 2

Views: 106

Answers (3)

mvw
mvw

Reputation: 5105

What you need is a spatial data structure, they allow those typical queries of computational geometry. Your point is a query point for the set of triangles.

You might for example calculate a minimal bounding box for each triangle and store those into a R-tree (keep a map of which mbb is for what triangle or put those triangles as leave nodes in the R-tree) and then fast lookups of the best bounding box should give you maybe not the final result, but I think it would deliver a much reduced search area (a list of matching mbbs which result in a list of triangle candidates), where you then quickly search the exact triangle (because bounding boxes and triangles differ a bit).

Upvotes: 2

thumbmunkeys
thumbmunkeys

Reputation: 20764

Use a ´bounding sphere collision detection´ algorithm to test all triangles.

This algorithm is fast, but has false positives. On all triangles that fulfill the bounding sphere test, use your algorithm to do the final collision test.

Upvotes: 0

Codor
Codor

Reputation: 17605

You could speed up the comparison by using the bounding box of each triangle to test if the point is not contained.

Upvotes: 0

Related Questions