I think the fastest possible distance check is vector based, which I'm sure someone could post an example off - should be 2 or 3 times faster than the old square root method. If nobody comes forth I'll post up and example later.
I think though that your taking a long way around optimisation in that method, because it relies on a distance calculation to remove detail that is probably taking less processor time than the mesh render itself (well, maybe not).
What I would do is make an indexed grid, if your scene is mostly on 1 level, then it would probably work out pretty nice.
Like your already using a grid, so if you imagine a list of objects at each grid location that you can actually see. Change grid location, change the visibility on the meshes. So firstly you'd check the current grid and hide everything at that location, then check the new grid position and show everything at that location. It's a bit rough and ready, but this technique is blindingly fast, you'd use a 2D array representing the grid, but storing the start object number.
It's getting complex to explain this, maybe psuedo code...
Dim cull_grid(64,64)
Dim cull_index(32000)
ind=0
for y=0 to 63
for x=0 to 63
cull_grid(x,y)=ind - Store the start of the list for current grid pos
for o=0 to 10000
if object_visible_from_grid then cull_index(ind)=o : inc ind,1 - Store the object number in the array
next o
cull_index(ind)=-1 : inc ind,1 - Store a -1 to signify the end of the list for the grid pos
next x
next y
Then you can get the cameras grid location and show the objects that are visible from there by simply...
- Hide the current level objects first
ind=cull_grid(x,y)
while cull_index(ind)>-1 and ind<10000
hide object cull_index(ind)
inc ind,1
wend
- Then update the grid X Y position
- Show the current grid objects
ind=cull_grid(x,y)
while cull_index(ind)>-1 and ind<10000
show object cull_index(ind)
inc ind,1
wend
Of course, the tricky part is working out if an object is visible from the grid location. You could use a range and angle check to get it up and running I suppose, but the benefits would come from only showing the visible objects. It could all be precalculated though, so you'd load in a level, with this BSP style grid index included - the workings out could be done in an editor.
At a push, I'd make a screen comparison check, like show all objects, render, then hide the object in question and render again, but compare it with the last render, if there's a change then the object is visible - that's one really slow solution but still an option. Rendering from different areas in the grid would make it nice and accurate.