How to add detailed engravings onto a curved surface in Blender for 3D-printing? In Blender I have a curved surface, only quads. Now I want to "engrave" the surface. See picture as example, but only with curved surface of object instead of flat.


Good example of how it should look printed


How to cut this out off the object?

What did not work: 


boolean in various combinations. Tried making curves with triangle profile, putting them on a lattice for deforming them to shape and shrinkwrapping the lattice onto my object. Then booleaned curve with object and tried to delete all excessive faces.
Lots of ugly triangles. 
Making only the outline of my desired engraving and knife projecting it. Then, having the outlines, extruding them into the object and tried scaling them. While this somehow seems to work a little better, I still have very ugly tris for subsurf and complex shapes do not really scale or offset well.
Trying to sculpt with Dyntopo enabled. Maybe there would be a way with a certain sculpt tool, but Dyntopo makes ugly geometry, too...


What do? Do I have to remodel the whole object and manually building all the complex engraving? Thanks for your time in advance.

Edit: I want to 3D-print this, so bumpmaps are not an option here.
Also please note that the engraving has to be CUT OUT of the object, not a curve put on. If by any means I could export my object into another freeware program or use another program altogether to more easily get the desired results, please let me know.
You could try and model it with Bezier Curve objects combined with a Shrink Wrap modifier.
Just model use a any bezier curve object, define any desired section and use it as bevel object.

Apply a Shrink Wrap modifier to the curve, but the important part is to activate the option Apply this and all preceding deformation modifiers on splines’ points rather than on filled curve/surface.

This will make it so the bezier control points are wrapped to the surface, rather than the final beveled geometry, so that the curve can be beveled live, but its thickness and shape is kept.

Then adjust and model as desired, you can use curve radius to make certain parts thicker or thinner.