ActionScript 3.0 :: Fastest Method Of Determining If A Triangle Is Encompassed By Smaller Grid Squares?

I've got my 3D sphere to triangle collision detection working now, but I need an efficient method of adding the triangles to the broadphase grid.

This is easy enough if the triangles are smaller than the grid nodes, however - especially given the polycounts I'm working with - it's going to be fairly frequent that a triangle is significantly larger than the grid nodes.

Here's an example.See the yellow polygon? Just adding it the grid nodes by it's vertices results in it NOT being added to 4 grid nodes that it does reside in.

My first thought is repeatedly casting rays along one of the edges from the normal of the edge until you find the intersection point with one of the other edges, of course checking for intersections with the grid edges until you reach the destination intersection with one of the other edges of the triangle. This would work, but is not particularly fast.

Although these triangles aren't being added/removed in real time, only when building the level, when constructing a level with say 100,000 polygons total, I obviously want it to be processed as quickly as possible.