We present a new algorithm to compute a geodesic path over a triangulated surface. Based on Sethian's Fast Marching Method and Polthier's Straightest Geodesics theory, we are able to generate an iterative process to obtain a good discrete geodesic approximation. It can handle both convex and non-convex surfaces. It is dened a new class of curves, called geodesic B´ezier curves, that are suitable for modeling on manifold triangulations. As a natural generalization of B´ezier curves, the new curves are as smooth as possible. We discuss the construction of C0 and C1 piecewise B´ezier splines. We also describe how to perform editing operations, such as trimming, using these curves. Special care is taken to achieve interactive rates for modeling tasks. After giving an appropriated denition of convex sets on triangulations, we use it to study the convergence of the geodesic algorithm, as well as the convex hull property of geodesic B´ezier curves. We prove some results concerning convex sets.