I haven't worked with TBB for a while so it's quite possible this question is easily answered. I have a simple triangulated polygon that i would like to tesselate, and would like to do the work making efficient use of the processor cores. I'm not worried about distributing this across CPUs.
At this point i think a simple parallel-for over the faces to generate new points/faces followed by a point merge/sort, removal of duplicates, and update of the triangle indices into the resulting points list is reasonable. Does this seem reasonable to the TBB gurus out there?
The question is not actually TBB specific, so you better seek for algorithmic gurus :)
To me, it sounds reasonable for the initial implementation. You can start with that and analyze what are its obstacles/bottlenecks. And if you later find ways for improvement, there will bethe baseline to compare with.