The accurate and efficient tracing of streamlines is fundamental to any streamline-based simulation method. For grids with irregular cell geometries, such as corner-point grids with faults or Voronoi-diagram (pebi) grids, most efforts to trace streamlines have been focused on subdividing irregular cells into sets of simpler subcells, typically hexahedra or simplices. Then one proceeds by reconstructing the velocity field on, and tracing through, the sets by a more basic algorithm. One such basic algorithm applies to incompressible flow on simplices. In that case there is a cell-wise constant velocity that is consistent with given face fluxes, as long as those face fluxes sum to zero for the cell. We give an efficient and simple formulation of this algorithm using barycentric coordinates. Another approach to irregular cell tracing is computing the streamline directly on the complex cell geometry. We give a new method based on generalized barycentric coordinates for direct tracing on arbitrary convex polygons, which generalizes the corner velocity interpolation method of Hægland et al (2007). The method generalizes to convex polytopes in 3D, with a restriction on the polytope topology near corners that is shown to be satisfied by several popular grid types.