Hello all,
Current features in BoT, with possible modifications:
1. A struct bot_edge exists with attributes as the destination vertex,
use_count - no. of faces using it (0/1/2), next edge.
*Suggestion*: To add the faces using it. This will aid the face adjacencies
to be set more easily. If at any time we require the adjacent faces of any
particular triangle, without the face information in the bot_edge structure
we will have to search the entire face list. If we do include that
information, we can get the adjacent faces through that. Basically a shift
from O(n) to O(1).
2. Edges with use_count = 0 (dangling edges) are removed.
3. > Unused vertices and duplicate vertices are removed.
In the function rt_bot_condense in bot.c, for vertex merging, bin
sorting has been used as the better alternative. But if all the points have
the same x-coordinate (points are put into different bins based on the
x-coordinate), then that would be the worst case when it would take O(n^2)
time.
*Suggestion*: Instead if we use a balanced binary search tree (AVL
tree), for a point if we need to search if there is an equivalent vertex,
that would only take O(log n) time. So, overall this would be over in
O(n*logn) time, even in the worst case. This can be implemented.
> Two equivalent faces are fused.
Essentially, removal of isolated, duplicate vertices, and dangling edges,
operations to produce more efficient usage of edges, and a few mesh
optimization operations are already implemented in BoT.
The geometric errors that need attention now are: gaps, overlaps, T-joints,
self-intersection, degenerate faces, sliver patches/skewed elements. And
they will be handled according to their orientation, mode, and the
circumstances in which the error is present.
Reference: Generating topological information from a bucket of facets (Rock
and Wozny, 1992)
http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.492.4919&rep=rep1&type=pdf
------------------------------------------------------------------------------
Transform Data into Opportunity.
Accelerate data analysis in your applications with
Intel Data Analytics Acceleration Library.
Click to learn more.
http://pubads.g.doubleclick.net/gampad/clk?id=278785231&iu=/4140
_______________________________________________
BRL-CAD Developer mailing list
brlcad-devel@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/brlcad-devel
