1. Tylko raz. Co klatkę to marnowanie czasu. Jeśli obiekty są nieruchome, nowe nie przybywają, nie są usuwane, nie zmieniają rozmiaru (słowem - są statyczne), to podziel raz, na początku i potem korzystaj z tego drzewa. Jeśli są dynamiczne, to musisz dopisać funkcję wstawiania i usuwania obiektów z istniejącego drzewa, najlepiej z automatycznym rozbijaniem i łączeniem węzłów - nieproste, ale da się zrobić. Z resztą na początek tego nie musisz robić.
2. Proponuję zatrzymać rekurencyjne dzielenie, kiedy spełniony jest co najmniej jeden z tych warunków:
a) Rekurencja osiągnęła pewną głębokość (np. 6 czy 8 poziomów).
b) Liczba obiektów w bieżącym węźle (tym co byśmy go ewentualnie dalej podzielili) jest już mała, np. 16.
3. Co chcesz :) Najlepiej wskaźniki do tych obiektów albo jakieś inne odniesienia do nich.
4. Musisz opisać kształt pola widzenia kamery frustumem, czyli taką bryłą co ma taki kształt, jak pole widzenia takiej kamery :) A potem testować kolizję, czyli sprawdzać specjalną magiczną funkcją matematyczną, czy frustum przecina się z prostopadłościanem opisującym dany węzeł drzewa. Jeśli tak, to wchodzimy do tego węzła, rysujemy zgromadzone w nim obiekty i testujemy frustum dalej rekurencyjnie z jego podwęzłami. Jeśli nie, to cały ten węzeł razem z podwęzłami ignorujemy. Zobacz mój artykuł:
http://www.warsztat.gd/articles.php?x=view&id=279