You might find this thread interesting: http://mathoverflow.net/questions/35946/how-expensive-is-knowledge-knots-links-3-and-4-manifold-algorithms-closed

I believe it's expected there should be a polynomial time algorithm to go from a triangulation to a surgery diagram or Heegaard splitting -- in particular see the Thurston and Costantino reference in the above thread.  I've been hoping to eventually flesh that out and implement it in Regina but I haven't had the time yet.  

For triangulating 3-manifolds given by Heegaard splittings, this was done by Schleimer. See his webpage: http://www.warwick.ac.uk/~masgar/Maths/twister.html there is C-code available, as well. I believe he does something quite comparable to what you describe, using layered triangulations.