Getting a list of objects in the frustrum

Ive touched on this before but I cant find the thread. After seeing some of Smoking Mirror’s work I wanted to reask the question. Is there a way to get a list of objects within the frustrum maybe using sphere or box inside frustrum.

I beleive that when I asked this before I was told that the program would still have to go through every object in the scene, check to see if each object is within the frustrum, and then return a list of the objects within the view frustrum. Is this accurate? Or Can you make the program just get the objects that are within the frustrum, without running through all objects in the scene.

Thanks in advance

We did some work on this with my project and I do believe it would have to check every object in the scene. We tried grouping the objects to narrow the scope of the search. This is what we ended up with;


from bge import logic

#Library names and its load state will be stored in this dictionary:
LibData = {}

#Positions of spawner, spawner object, whether spawned or not, instance of the spawned object.
SpawnData = {}

#Run once
def init():

    #Prepare the dictionary
    SpawnData['Position'] = []
    SpawnData['Spawner'] = []
    SpawnData['Spawned'] = []
    SpawnData['Instance'] = []
    
    #Get current scene
    scene = logic.getCurrentScene()
    
    #Loop through all objects
    for obj in scene.objects:
    
        #Check if object has a 'Spawn' property
        if obj.get('Spawn'):
            #Write the necessary data
            SpawnData['Position'].append(obj.worldPosition) #You can use this position array to build a KDTree
            SpawnData['Spawner'].append(obj)
            SpawnData['Spawned'].append(False)
            SpawnData['Instance'].append(None)
            
            #Check if object has a 'Library' property
            libname = obj.get('Lib')
            
            #Check if this library was not added to LibData before
            if libname and not libname in LibData:
                ld = {}
                ld['loaded'] = False
                ld['users'] = 0
                ld['path'] = logic.expandPath("//%s.blend" % libname)
                
                #Add it
                LibData[libname] = ld
    
    print("Total spawners found: %i" % len(SpawnData['Position']))
    print("Total libraries found: %i" % len(LibData))


batch_start = 0 #The position of index currently being processed
batch_count = 1500 #Number of objects to process during a single batch session
#(0 - 1500, 1501 - 3000, 3001 - 4500, 4501 - 6000, 6001 - 7500, 7501 - 9000, 9001 - 1000.. cycles continues) 
#This is so that the logic is not completely frozen during frustum checks

# Always sensor - frequency of 1
def tick():

    #Get scene and camera
    scene = logic.getCurrentScene()
    cam = scene.active_camera
    
    remove_count = 0 #Number of objects removed this session
    remove_max = 50 #Max removal per session
    #Removal is the most logic heavy command, so 50 per session is good enough
    
    #Bringing in the global variables
    global batch_start
    global batch_count
    
    #Set a marker for end index
    batch_end = batch_start + batch_count
    
    #Enable this to see what happens:
    #print("%i <--> %i" % (batch_start, batch_end))
    
    #Lets loop through batch start and batch end indexes of all positions
    for i, pos in enumerate(SpawnData['Position'][batch_start:batch_end]):
    
        #The actual spawner index is batch_start + i, not just i
        index = batch_start + i
        
        #Check is position falls inside frustum
        if cam.pointInsideFrustum(pos):
        
            #If yes, check if this object was spawned or not
            if not SpawnData['Spawned'][index]:
            
                #Library codes are commented for time being, until BGE lib bugs are solved
                """libname = SpawnData['Spawner'][index].get('Lib')
                if not LibData[libname]['loaded']:
                    print('Load library: %s' % libname)
                    logic.LibLoad(LibData[libname]['path'], 'Scene')
                    LibData[libname]['users'] = 1
                    LibData[libname]['loaded'] = True
                else:
                    LibData[libname]['users'] += 1"""
                
                #Instantiate the new object
                SpawnData['Instance'][index] = scene.addObject(SpawnData['Spawner'][index].get('Spawn'), SpawnData['Spawner'][index])
                
                #Set the index to True for quick next quick check
                SpawnData['Spawned'][index] = True
            else:
            
                #If its in frustum, set the visibilty to True
                SpawnData['Instance'][index].visible = True
        else:
        
            #If not in frustum
            if SpawnData['Spawned'][index]:
            
                #Set the visiblity to False, to speed up rasterizer
                SpawnData['Instance'][index].visible = False
                
                #Logic is less laggy if you don't actually end the object, just hide it. Try commenting this whole part.
                if remove_count < remove_max:
                    remove_count += 1
                    SpawnData['Instance'][index].endObject()
                    SpawnData['Spawned'][index] = False
                    
                    #Library codes commented out
                    """libname = SpawnData['Spawner'][index].get('Lib')
                    if LibData[libname]['loaded']:
                        LibData[libname]['users'] -= 1
                        if LibData[libname]['users'] == 0:
                            print('Unload library: %s' % libname)
                            logic.LibFree(LibData[libname]['path'])
                            LibData[libname]['loaded'] = False"""
            
    #Set starting marker for next session
    batch_start += batch_count
    if batch_start > len(SpawnData['Position']):
        #If batch reached its end, set it back to 0
        batch_start = 0

Looking at the relevant InsideFrustum methods on the camera object, it seems like you would have to go through each and every object in the scene, at the very least; for complete reliability you would probably have to go through each and every vertex in the mesh.

from both of your responses it seems my fear was correct, I have to loop through the all the scene objects, and then see if they are in frustrum. Hmmmm…I know a radar is slow, but do you think it would be faster to use a radar sensor that’s roughly the size of the frustrum and get those objects rather than loop through all the objects?

would a collision check be faster?

I think the underlying mechanic is still the same, radar checks would have to run nearly every frame to maintain reliability. The number of scene objects makes a huge difference as well.

Don’t worry about it until you implement it and find out it’s too slow. It doesn’t matter too much which method is slower if either one is far more than fast enough for your purposes.

I would do an angle check between the camera’s vector and a vector from the camera to the object. But as SolarLune says, see if it’s a problem first.

Normally you would have other processes running in your game too where you have to go through all objects in the scene. That’s why I would think it’s best to have a ‘scene manager’ to collect relevant data of each object just once on every logic tic. Then separate processes, such as the process you’re describing, can use this data.

As a side-note, I wonder if collision wouldn’t be faster? Suppose you have a whole bunch of (invisible) tubes stretching from the Camera so that at a reasonable distance the gaps between those tubes wouldn’t be less then a Blender Unit or so…

Edit: or rather a bunch of planes…
Edit: didn’t realize the inside of a cube collides too, so just a cube will suffice

I’ve done some tests. Attached are three test files to compare. With a Collision Sensor Logic usage will decrease, but it will have a cost on Physics. With a Radar Sensor the Physics cost is to high. So I think it’s worth considering to get the hitObjectList of a Collision Box (with Collision Bounds Type Box) and go from there instead of iterating through all objects in the scene.

Attachments

Frustum_collision_test.blend (85.6 KB)Frustum_radar_test.blend (84.8 KB)Frustum_iteration_test.blend (84.1 KB)

If you’re talking about optimizations, then you should consider what you really need to iterate through. Do you need to iterate through everything, or just certain objects? Why not add those things to a separate list that you loop through? Do you need to loop through them all every frame? Or could you do it every other frame?

Raco’s original idea about having a scene manager collect the data is a good one - store the data somewhere where everything can use it so that any object can benefit from it.

But yeah, don’t worry about optimizations unless you can see it’s bogging down your framerate considerably.

I like the sound of a scene manager. I wish that was something built in to blender already. It’s be great if I could get scene.particles or scene.bullets or scene.agents by setting an object type in the game physics panel.

I’d also like to get scene.objects_in_frustum from the frustum culling process.

The only problem with a scene manager is that it runs at the beginning of the frame and by the end of the frame several of the objects in your scene could have been ended, which will give you a problem when you try to use them in a calculation. You’ll have to use if not ob.invalid every time you used something from the list.

I think point inside frustum is probably the quickest operation, though get_screen_position is not slow either, and that will tell you if the object is on screen or not, if the number returned is more than 1.0 or less than 0.0. If you want more precision there is soon to be a function for get own world size which would be helpful for getting the bounding box to do cube inside frustum.

You’d have to test it to find out which one is quicker. Anyway, to make sure it’s as quick as possible you can check if the object is one of the kinds you want to check on or is just junk:

for ob in scene.objects:
    if ob.get("enemy"): 
        do_further_checks()

In that case most objects will be skipped after a quick ob.get check. it’s unlikely to slow you down too much unless you have thousands of objects (which I sometimes do have :frowning: ).

Absolutely.

I’ve seen many people waste copious amounts of time on things that just didn’t matter in their overall performance profile.

I would advise everyone to focus on their actual needs, and the performance requirements those needs actually imply.

in the end, your game will only scale as well as you plan, so I disagree, some features are resource intensive so the only way to make room is to run everything smart.

All good points. Y’Know this may can be solved just by using activity-culling, Im getting ahead of myself because im not even at that point yet, so Ill take what you guys have said into consideration, It just seems sometimes so hard to go back and repair/fix code, rather than to do it right the first time. Im doing a major scaleback on my own project and sometimes it seems hard to find what im looking for(and the related stuff) and chop it out. Sometimes I think I could build the whole thing over faster.

If you’re talking about optimizations, then you should consider what you really need to iterate through. Do you need to iterate through everything, or just certain objects?

I was thinking about this, and dont I still have to iterate through everything, even to narrow it down. Say I want all objects with property"enemy". Dont I still have to iterate through all objects, and then return all objects with “enemy”. Or if I want an object within range, dont I have to iterate through all objects, then check their distance and cull that way. I see Advantages of creating list, but dont I still have to iterate through all objects, to get a condition or property to populate the list with. Unless I use a collision object, I dont see a way around still iterating all objects to cull out the ones I want. Once again though Ill worry about this when I get there. im getting ahead of myself again

on frame 0

delay(once)------------------generate enemyList
in item named Enemy List


import bge
cont=bge.logic.getCurrentOwner()
own=cont.owner
scene=bge.logic.getCurrentScene()
for item in scene.objects:
    if 'Enemy' in item:
        own['EnemyList']+=[item]

adding enemy

trigger-----------python


import bge
cont=bge.logic.getCurrentScene()
own=cont.owner
scene=bge.logic.getCurrentScene
EnemyList=scene.objects['EnemyList']
AddedEnemy=scene.addObject('Enemy',own,0)
EnemyList['EnemyList']+=[AddedEnemy]

in item reading list


if 'EnemyList' not in own:
    EnemyList=scene.objects['EnemyList']
else:
    for item in EnemyList['EnemyList']:
        futurism check

so you only iterate to find the list the first time.

No one argued against planning.

some features are resource intensive so the only way to make room is to run everything smart.

What do you mean by “smart”? Do you mean optimized as much as possible?

Either way: In all my time as a programmer, I have yet to see the kind of “narrow margin” feature you imply, where optimizing everything in the program would provide the necessary gains to make that one demanding feature “fit” into existing performance constraints.

Usually, there are a few bottlenecks that significantly impact performance, and those are the pieces that make for reasonable optimization targets; everything else is negligible, in terms of overall performance impact.

Optimizing everything is like trying to plan for everything: At best, you end up with a mediocre solution for the problems that you actually do encounter, but it’s more common that you’ll just fail to produce anything, because all those optimizations carry a system complexity cost that you can’t afford - Your code becomes a mess, and you hit a dead end (sound familiar?).

You need to understand what you’re doing well enough to make a targeted solution (for your actual problems), which can be expressed in very clear terms, and which can thereby avoid the kind of complexity that overly optimized systems typically suffer from.

if best practice should be your common practice, then there is no confusion.

I overthink, I agree, but then again I have not hit any walls yet, besides my GPU :smiley:

Optimizing everything is not best practice.

Also, whether or not you “overthink” the solution is largely irrelevant when you don’t understand the nature of the problem, or the fundamentals of good programming style, or how to effectively manage complexity.

I appreciate your work, and your suggestions, however I think that if there is a problem point it out, if there is a solution propose it,

else:

rethink your statement.

I learn by doing, and it’s worked out rather well so far, (my logic is about 2 ms for my game including weapons, AI, physical walking rig, and compound assembly system)

in my own project-

there are some sensors I can push into states so they are not so spammy, and there are some python scripts I can trigger on changed values, but other then that I am running about 100% lean.

I have even used X*.decimals instead of x/

anything you can add I will consider however…