Thank you for the detailed and thoughtful response! I've been looking for something exactly like this, this gives me a fantastic head start. To apply gravity, I assume you also add a downward velocity to the Verlet integration?
I just add to the new position each frame (though I cap the velocity). This has the same result as manipulating the velocity but allows me to decouple velocity components and gravity components, though admittedly I didnt make use of this.
