Okay, so normal texture painters. You project a brush tip shape onto a mesh. You clip that projected shape to one or more polygons for each of disconnected face groups you hit.
Then you project each of those polygons into texture space. Then for all the texels in your polygons, inverse-project back through the transformations you did to find what pixels of the brush tip shape you should paint.