LoD calculation time, fps wise.

Hello,

I made a Lod and using it for a while now at small games, Atm i am building a bigger game and walked into processing issues.

I made a blend with 500 trees and 3000 flowers, if i run this without Lod i am at a steady 60 fps, as soon as i use the Lod it goes down to 40 fps. I solved it by delaying the LoD by 30 ticks and it runs at 60 fps again.

But is this normal? i know 3500 objects are a lot to go trough but i thought that the Lod should be able to handle it.

This is my Lod, what do you think? did i build it the wrong way or are the amount of objects just the bottleneck?


#
# LoD by cotax
#


# Place a property on the object that needs LoD, call it lod_mesh and put the origional mesh name in it.
# Now duplicate it as much as you like. 
# Make a low poly mesh, call that mesh: origionalname_far (so put _far behind the origional mesh name).


# You can use the property on the low poly instead of the high one, easier to work with ;).
# (only 1 mesh type needs a property, either the high one or low one depending on what you place in the main scene)


# Use the update_lod_list(cont) to update the list when needed


def lod(cont):
    
    own = cont.owner


    if not 'lod_list' in own:
        update_lod_list(cont)
            
    for obj in own['lod_list']:
        
        distance    = own.getDistanceTo(obj)
        mesh_name   = obj['lod_mesh']
        
        # get LOD distances
        min, max  = set_distances(mesh_name)
  
        if distance <= min:
            visible(obj, True)           
            change_mesh(obj, mesh_name)
        elif distance > min and distance <= max:
            visible(obj, True)
            change_mesh(obj, mesh_name + '_far')
        else:
            visible(obj, False)  




def update_lod_list(cont):
    
    own = cont.owner   
    own['lod_list'] = [obj for obj in own.scene.objects if 'lod_mesh' in obj]
          
             
def set_distances(mesh_name):
    
    if mesh_name == 'tree_green_leaves':
        min     = 75.0 # high mesh
        max     = 125.0 # low mesh 
    elif mesh_name == 'flower_red' or 'flower_blue':
        min     = 20.0 # high mesh
        max     = 40.0 # low mesh   
    else:
        min = 10.0
        max = 20.0
            
    return min, max




def visible(obj, state):
    
    if state == True:
        if obj.visible == False:
            obj.restoreDynamics()
            obj.visible = True
            
    elif state == False:
        if obj.visible == True:
            obj.suspendDynamics()
            obj.visible = False
        


def change_mesh(obj, mesh_name):
    
    mesh = obj.meshes[0].name


    if mesh != mesh_name:
        obj.replaceMesh(mesh_name)


    if state == True:
        if obj.visible == False:
            obj.restoreDynamics()
            obj.visible = True
            
    elif state == False:
        if obj.visible == True:
            obj.suspendDynamics()
            obj.visible = False

Don’t compare to Boolean types in Python. It’s the same as omitting it (x == True returns either True or False)


if state:
    if not obj.visible :
        obj.restoreDynamics()
        obj.visible = True

elif not state:
    if obj.visible:
        obj.suspendDynamics()
        obj.visible = False

One of the reasons we use LOD is to avoid performing processing operations on lots of objects at once. In your demo you are continually changing the mesh of objects. This is horribly inefficient. You only want to change the mesh when an object changes its lod status.

Also, in set_distances, just use a dict to map object name to distances rather than a long if loop.
Avoid calling functions inside high-iteration loops. They’re more expensive than just running the code directly.

You should not be running this every frame either. It’s a trade off between runtime performance of the renderer, and the scripting engine. I suspect it’s quite often going to be logic causing the bottleneck.

In your demo you are continually changing the mesh of objects

No it does not?, i check the mesh name, if the mesh name is the same as the new mesh it just returns and not changing anything.

  if mesh != mesh_name:
        obj.replaceMesh(mesh_name)

or is this wrong already?

i found out that ‘is not’ is not the same as !=.
due to if you use ‘is not’ it indeed keeps changing meshes but with != it doesn’t.

in set_distances, just use a dict to map object name to distances rather than a long if loop.
Avoid calling functions inside high-iteration loops

I was planning to do that, but for testing purpose(3 objects) this was easier/faster to setup.
i didn’t thought calling a function in a loop would be ‘heavy’ i will change that tonight.

You should not be running this every frame either. It’s a trade off between runtime performance of the renderer, and the scripting engine

Thanks, that is good to know, due to it was strange to see that it runs at 60 without lod and 40 with haha.
with a delay of 30 it works good, if needed i can delay it more, but its good to have someone to tell me its ok due to i wasn’t sure.

I will change it tonight.

Btw are there more options that i can add into the lod?
now it changes at range:

  • mesh
  • visibility
  • dynamics

#edit


 if distance <= min:
            visible(obj, True)           
            change_mesh(obj, mesh_name)
        elif distance > min and distance <= max:
            visible(obj, True)
            change_mesh(obj, mesh_name + '_far')
        else:
            visible(obj, False)  

so you actually prefer to build it in here instead of calling functions? because if i got tons of different lod levels i need to copy/paste it a lot, thats the main reason why i use functions here (saves alot of writing).

I misread your initial code, sorry.

3500 objects isn’t a lot for Python, either. However, you can still significantly improve the program.

Firstly, you should cache set_distances into a dictionary by mesh name. It’s probably faster.

As the program has to deal with more objects, it will become increasingly slower to run. Is there any reason you’re not using the built in LOD? You can use spatial representation data structures like QuadTrees to avoid testing trees that are farther away than a fixed distance. You can also do frustum tests to avoid rendering objects directly behind the player at any distance > 2m for example.

i’ve changed the distances to a dict type and store it in the object, and load it once on start.
this indeed increases the speeds and runs smoother.


#
# LoD by cotax
#


# Place a property on the object that needs LoD, call it lod_mesh and put the origional mesh name in it.
# Now duplicate it as much as you like. 
# Make a low poly mesh, call that mesh: origionalname_far (so put _far behind the origional mesh name).


# You can use the property on the low poly instead of the high one, easier to work with ;).
# (only 1 mesh type needs a property, either the high one or low one depending on what you place in the main scene)


# Use the update_lod_list(cont) to update the list when needed


def lod(cont):
    
    own = cont.owner


    if not 'lod_list' in own:
        update_lod_list(cont)
        get_distances(cont)
                
    for obj in own['lod_list']:
        
        distance    = own.getDistanceTo(obj)
        mesh_name   = obj['lod_mesh']
            
        # get LOD distances
        min, max  = own['lod_distances'][mesh_name][0], own['lod_distances'][mesh_name][1]
        
        if distance <= min:
            visible(obj, True)           
            change_mesh(obj, mesh_name)
        elif distance > min and distance <= max:
            visible(obj, True)
            change_mesh(obj, mesh_name + '_far')
        else:
            visible(obj, False)  




def update_lod_list(cont):
    
    own = cont.owner   
    own['lod_list'] = [obj for obj in own.scene.objects if 'lod_mesh' in obj]
          
             
def get_distances(cont):
       
    own = cont.owner
    
    own['lod_distances'] = { # mesh name - min - max
                    'tree_green_leaves':    [75,125], 
                    'flower_red':           [20,50],
                    'flower_blue':          [20,40]
                    }




def visible(obj, state):
    
    if state:
        if not obj.visible:
            obj.restoreDynamics()
            obj.visible = True
            
    elif not state:
        if obj.visible:
            obj.suspendDynamics()
            obj.visible = False
        


def change_mesh(obj, mesh_name):
    
    mesh = obj.meshes[0].name


    if mesh != mesh_name:
        obj.replaceMesh(mesh_name)

Is there any reason you’re not using the built in LOD

You can not tweak it, as i see no visibility toggle, mesh spawn distance are set, this way i can adjust it during runtime and make a setting for every object.

You can use spatial representation data structures like QuadTrees to avoid testing trees that are farther away than a fixed distance. You can also do frustum tests to avoid rendering objects directly behind the player at any distance > 2m for example.

No idea what that all is, but i am using it in a 3d perspective and the cam can be moved away from the player, is that setting tweakable during runtime?

for static object use a kdtree (they are in mathutils) they are much faster than checking distance using python each frame

instead of building using vertex use objects world position,

store a list that is the same index as the kdtree so you can look up the list very very fast.

you can use multiple radius lists to check what objects are in range withkdtree -

moving objects / rebalancing the tree can be slow however so it’s best to use on static items only**

the stuff about context and bpy just hack out and use object.worldPosition

I use KDTree for physics LOD and for Lamp LOD and will be using it for streaming terrain*https://blenderartists.org/forum/showthread.php?405261-Proof-of-physics-LOD-s-utility

KDTrees aren’t the best data structure for this particular task - large searches, where the ability to cull far regions of N trees hierarchically can be performed using Octrees (or quadtrees in this case), or other spacial data structures.

I will look up kdtree and quadtrees havent worked with both so that’s new to me, and out of topic in this case.

Thank you for the information, it already runs smoother without the if statement and using a dict.
I tried a few things out, one of them making 1 script instead of calling functions for visibility etc. but that does not work so well.( i don’t like to repeat code at every statement).

I run the 3500 object at 55 fps now when running it every tick. so that’s an increase of 15 fps i like it :). (i gonna run it at 30/60)

Thanks again.

A simple quadtree:


def mean(x, y):
    return (x + y) / 2




class AABB:
    
    def __init__(self, p_min, p_max):
        self.p_min = p_min
        self.p_max = p_max
        
        x_min, y_min = p_min
        x_max, y_max = p_max
        cx = mean(x_min, x_max)
        cy = mean(y_min, y_max)
        
        self.center = cx, cy
        self.width = x_max - cx
        self.height = y_max - cy
    
    def intersects(self, aabb):
        cx, cy = self.center
        ox, oy = aabb.center
        
        dx = abs(cx - ox)
        dy = abs(cy - oy)
        
        return dx < (self.width + aabb.width) and dy < (self.height + aabb.height)
    
    def contains(self, point):
        x, y = point
        x_min, y_min = self.p_min
        x_max, y_max = self.p_max
        
        if x < x_min or x > x_max:
            return False
        
        if y < y_min or y > y_max:
            return False
        
        return True




class Circle:
    
    def __init__(self, origin, radius):
        self.origin = origin
        self.radius = radius
        self.radius_sq = radius ** 2
        
        x, y = origin
        p_min = x - radius, y - radius
        p_max = x + radius, y + radius
        self.aabb = AABB(p_min, p_max)
    
    def contains(self, point):        
        px, py = point
        x, y = self.origin
        
        dx = px - x
        dy = py - y
        dist_sq = dx ** 2 + dy ** 2
        return dist_sq <= self.radius_sq
    
    


class QuadTree:
    
    min_points = 4
    
    @classmethod
    def from_data(cls, data_):
        data = list(data_)
        
        xs = [m[0][0] for m in data]
        ys = [m[0][1] for m in data]
        
        min_x = min(xs)
        max_x = max(xs)
        
        min_y = min(ys)
        max_y = max(ys)
        
        p_min = min_x, min_y
        p_max = max_x, max_y
        
        self = cls(p_min, p_max)
        for point, point_data in data:
            self.insert_pair(point, point_data)
            
        return self
    
    def __init__(self, p_min, p_max):
        self.aabb = AABB(p_min, p_max)
        
        self.ne = None
        self.se = None
        self.sw = None
        self.nw = None
        
        self._pairs = []
    
    def _subdivide(self):
        x_min, y_min = self.aabb.p_min
        x_max, y_max = self.aabb.p_max
        x_mid, y_mid = self.aabb.center
        
        self.ne = QuadTree((x_mid, y_mid), (x_max, y_max))
        self.se = QuadTree((x_mid, y_min), (x_max, y_mid))
        self.sw = QuadTree((x_min, y_min), (x_mid, y_mid))
        self.nw = QuadTree((x_min, y_mid), (x_mid, y_max))
    
    @property
    def pairs(self):
        yield from self._pairs
        if self.ne is not None:
            yield from self.ne.pairs
            yield from self.nw.pairs
            yield from self.se.pairs
            yield from self.sw.pairs    
    
    def insert_pair(self, point, data):
        if not self.aabb.contains(point):
            return False
        
        if len(self._pairs) < self.min_points:
            self._pairs.append((point, data))
            return True
        
        if self.ne is None:
            self._subdivide()
        
        if self.se.insert_pair(point, data):
            return True
            
        if self.ne.insert_pair(point, data):
            return True
            
        if self.sw.insert_pair(point, data):
            return True
        
        if self.nw.insert_pair(point, data):
            return True
        
        return False


    def get_pairs_in_aabb(self, aabb):
        if not aabb.intersects(self.aabb):
            return
        
        for point, data in self._pairs:
            if aabb.contains(point):
                yield point, data
        
        if self.ne is None:
            return
        
        yield from self.ne.get_pairs_in_aabb(aabb)
        yield from self.nw.get_pairs_in_aabb(aabb)
        yield from self.se.get_pairs_in_aabb(aabb)
        yield from self.sw.get_pairs_in_aabb(aabb)
        
    def get_pairs_in_circle(self, circle):
        contains_point = circle.contains
        for point, data in self.get_pairs_in_aabb(circle.aabb):
            if contains_point(point):
                yield point, data

Note that it stores N points before subdividing, so to find the points at any depth, you have to take all the points in “_pairs” and then do the same for each child tree until there are no more left. (in this code, the “pairs” property does this for you)


data = [(tree.worldPosition.xy, tree) for tree in trees]
tree = QuadTree.from_data(data)
           
# Now do some query (e.g LOD by range from pos (5, 5) within a distance of 2
x = y = 5
radius = 2


circle = Circle((x, y), radius)
points_and_trees_in_circle = list(tree.get_pairs_in_circle(circle)) # Build list, as return from get_pairs_in... is a generator

but the mathutils kdtree is compiled native code right?

we should run side by side and see what is faster*

maybe mathutils needs a mathutils.quadTree or mathutils.octTree?

Absolutely, the QuadTree is slower in this case, because it’s pure-python. Writing it in C would be far faster, and better for non-trivial queries like circles! But, it’s quite probably that KDTrees would be faster according to implementation details here… write it in C and test it!

I think maybe there is an implementation that is open source we can paste in no?

I don’t know anything about setting up python bindings though*

It’s a trivial structure, wouldn’t take long to write in C or Cython

def visible(obj, state):
if state:
if not obj.visible:
obj.restoreDynamics()
obj.visible = True

elif not state:
    if obj.visible:
        obj.suspendDynamics()             obj.visible = False

Warning!
Do not use obj.suspendDynamics() or obj.restoreDynamics()

I found out that it messed up the physics of the object thus needed more calculation time.
I found this out while showing the physics visualization.

upbge has suspendPhysics() which actually turns off collision, unlike
suspendDynamics()

should be in next release,

some things…
a function called get_something() , should return ever something.

remember -> obj.getDistanceTo(other)

the functiuon is written so:


def getDistanceTo(self, other):
    dist = calc_dist(self,other)
    return dist

instead set_something() meanly return nothing

the names are from, the “end user perspective”, so,
scene = logic.getCurrentScene() # get , so return something otherwise the local variable “scene” will be None

little trick-> avoid punctations inside loops


    getDistanceTo = own.getDistanceTo
    for obj in own['lod_list']:
        distance    = getDistanceTo(obj)
        mesh_name   = obj['lod_mesh']

mesh_name = obj[‘lod_mesh’] # why not get all infos once? [dist0:mesh0],[dist1:mesh1],[dist2,mesh2] is more performant

mot sure if work
changes are , the lod info are written inside the object to lod
removed the physic settings (assuming are object static)


def lod(cont):
    
    own = cont.owner
    
    if not 'lod_list' in own:
        own['lod_list'] = [obj for obj in own.scene.objects if 'lod_mesh' in obj]
        for obj in own['lod_list']:
            mehs_name = obj['lod_mesh']
            d = { # mesh name - min - max
                            'tree_green_leaves':    [75,125], 
                            'flower_red':           [20,50],
                            'flower_blue':          [20,40]
                            }
            min,max = d[mesh_name]
            obj["lods"] = [mehs_name, min, max] 
    
    
    gdt = own.getDistanceTo
    for obj in own['lod_list']:
        distance    = gdt(obj)
        mesh_name, min, max  = obj['lods']
        
        if distance > max:
            obj.visible = False
        elif distance > min:
            obj.visible = True
            change_mesh(obj, mesh_name + '_far')
        else:
            obj.visible = True
            change_mesh(obj, mesh_name) 


def change_mesh(obj, mesh_name):
    if obj.meshes[0].name != mesh_name
        obj.replaceMesh(mesh_name)
        
        


another little trick, make comparison with the same type ,
since in this case “distance” is a float , also min max should be coerced to float


obj["lods"] = [mesh_name, float(min), float(max)]

so the comparison is float > float (fast)
rather than float > int (slow)

Hey MarcoIT,

some things…
a function called get_something() , should return ever something.

Indeed, in fact it does return me the list with objects, no return used but its placed into the owner.
better name is set rather then get.

mot sure if work
changes are , the lod info are written inside the object to lod
removed the physic settings (assuming are object static)

i removed the typos, and gave it a spin, it works. But i don’t see a performance increase. Also the mesh dict cant be at first frame only due to my list based level generator, I remove all objects and load the next level (same scene) this causes the error that the key lods not exist. so i need to keep that part outside the object.

so this:


for obj in own['lod_list']:
            mesh_name = obj['lod_mesh']
            d = { # mesh name - min - max
                    'tree_green_leaves':    [30,60], 
                    'flower_red':           [20,50],
                    'flower_blue':          [20,40],
                    'platform_stone':       [40,75],
                    'platform_grass':       [40,75],
                    'platform_sand':        [40,75],
                    'platform_tree':        [40,75]
                    }
            min,max = d[mesh_name]
            obj["lods"] = [mesh_name, min, max] 

does work for first time loading level, but any level past that does not have the lods key, but i can make it the same as what i did with getting the lod objects in first place (the update_lod_list function).
that is why i had it that way, when the level is loaded i send a message to update it. I can let the loop react on the same message.

so the comparison is float > float (fast)
rather than float > int (slow)

Ok i didn’t thought it would be faster or slower, i will keep this in mind, thanks for the tip.

gdt = own.getDistanceTo for obj in own[‘lod_list’]: distance = gdt(obj)

It is better to do it like this? dont you call the function twice now(before and in the loop)?

obj.visible = False

Also you are using this, doesn’t it mean it set it to True or False even if it is already True or False?
so this is more performance eating?

(if some things don’t make sense, sorry its to late and i wanted to test it out)

gdt = own.getDistanceTo

is to confuse the reader. I strongly suggest to avoid such obfuscation code.

What does it do:

it creates a variable called “gdt” with the function “getDistanceTo” of object own.

Why do I see this as problematic?

  • what does “gdt” mean?
  • why to store a function of an object in a variable?
  • can quickly be confused by reading it as call [which is getDistanceTo() - with parenthesis]

The function is used later:


distance    = gdt(obj)

now look at this code:


distance = own.getDistanceTo(obj)

which one is better to understand? Your choice ;).

Inventing cryptic abbreviations is not a sign of professionalism - Iispl.