Isosurfaces are fundamental geometrical objects for the analysis and visualization of volumetric scalar fields. Recent work has
generalized them to bivariate volumetric fields with fiber surfaces, the pre-image of polygons in range space. However, the existing algorithm
for their computation is approximate, and is limited to closed polygons. Moreover, its runtime performance does not allow instantaneous updates
of the fiber surfaces upon user edits of the polygons. Overall, these limitations prevent a reliable and interactive exploration of the space of fiber
surfaces. This paper introduces the first algorithm for the exact computation of fiber surfaces in tetrahedral meshes. It assumes no restriction on the
topology of the input polygon, handles degenerate cases and better captures sharp features induced by polygon bends. The algorithm also allows
visualization of individual fibers on the output surface, better illustrating their relationship with data features in range space. To enable truly interactive
exploration sessions, we further improve the runtime performance of this algorithm. In particular, we show that it is trivially parallelizable and that
it scales nearly linearly with the number of cores. Further, we study acceleration data-structures both in geometrical domain and range space and
we show how to generalize interval trees used in isosurface extraction to fiber surface extraction. Experiments demonstrate the superiority of our
algorithm over previous work, both in terms of accuracy and running time, with up to two orders of magnitude speedups. This improvement enables
interactive edits of range polygons with instantaneous updates of the fiber surface for exploration purpose.