Menu

#436 Finding face adjacencies efficiently

Incomplete
open
None
5
2016-03-24
2016-03-24
No

This is patch to find the adjacent faces of a given face efficiently. There is a function to set, for each vertex, the faces containing it (rt_bot_set_vert_faces). Then the function rt_bot_find_adj_faces finds the adjacent faces given the structure pointer set using the previous function. The efficiency of this method can be seen in terms of complexity. In the brute force method, for each face we'd have to look through all the faces (for the edges) -> O(3n) for each face (where n is the number of faces). In the efficient method, for each face we look through only the faces containing the vertex. This would be O(3k^2) for each face, where k is the average number of faces that contain a vertex. In most cases it is the situation that n>>k. Thus this method is efficient and helpful.

1 Attachments

Discussion


Log in to post a comment.

MongoDB Logo MongoDB