You need to split intersected triangles. Take a look at any open-source Ray-Tracing algorithms which use KD-Trees for how to do this, or search for academic papers on Google Scholar.
Take a look at the Surface Area Heuristic for a good way to choose splitting planes, it is generally used in Ray Tracing but it may be applicable in your situation.