Sign in to follow this  
multifractal

Improving Quadtree (LOD) System

Recommended Posts

multifractal    306

Hello,

A while ago I threw together a LOD system based on quads being loaded in and out depending on the distance from them and the camera. The quads are created as needed rather than at start up. Recently as I have been using it more I have noticed it becomes very slow at times. I was wondering if I am doing something entirely wrong or if there was anything I can do to improve on it. 

Here is the code that examines the list of quads and makes more if needed:

for(int i = 0; i<Quad.list.size(); i++){
	    	Quad q = Quad.list.get(i);
	    	Vector3f center = Quad.getCenter(q);
	    	float width = q.width;
	    	float distance = center.distance(cam.getLocation());
	    	float view = (float) (2 * width);
	    	// if children = true the quad has children being displayed on screen
	    	//q.childs is the arraylist holding the quad's children 
	    if(view >= distance && !q.children && q.width >= (max_size)){
	    	if(q.childs != null){
	    		if(q.parent != null && q.parent.childs.get(0).receiving){
	    			
	    		Quad.list.remove(q.parent);
	    		}
	    		int size = verts.length;
	    		q.children = true;
	    		q.receiving = false;
	    		q.childs.get(0).receiving = true;
	    		q.childs.get(1).receiving = true;
	    		q.childs.get(2).receiving = true;
	    		q.childs.get(3).receiving = true;
	    		Quad.list.addAll(q.childs);
	    		int length = indices.length;
	    		int[] indices2 = new int[length+4608];
	    		System.arraycopy(indices, 0, indices2,0,length);
	    		indices = null;
	    		verts = null;
	    		verts = (Quad.getVertices());
	    		VertexBuffer vb = mesh.getBuffer(Type.Position);
	    		vb.updateData(BufferUtils.createFloatBuffer(verts));
	    		int n = length;
	    		for(int u = size; u<verts.length; u+=4){
	    			indices2[n++] = u;
	    			indices2[n++] = u+1;
	    			indices2[n++] = u+2;
	    			indices2[n++] = u+2;
	    			indices2[n++] = u+3;
	    			indices2[n++] = u;
	    		}
	    		indices = indices2;
	    		indices2 = null;	
	    		VertexBuffer ib = mesh.getBuffer(Type.Index);
	    		ib.updateData(BufferUtils.createIntBuffer(indices));	
	    	
	    	}else{
	    		if(q.parent != null && q.parent.childs.get(0).receiving){
		    		Quad.list.remove(q.parent);
		    		}
	    	int size = verts.length;
	    	Quad.split(q,q.index1,q.index2);
			verts = (Quad.getVertices());
	    	int length = indices.length;
    		int[] indices2 = new int[(verts.length/4)*6];
    		System.arraycopy(indices, 0, indices2,0,length);
    		indices = null;
    		VertexBuffer vb = mesh.getBuffer(Type.Position);
    		vb.updateData(BufferUtils.createFloatBuffer(verts));
    		int n = length;
    		for(int u = size; u<verts.length; u+=4){
    			indices2[n++] = u;
    			indices2[n++] = u+1;
    			indices2[n++] = u+2;
    			indices2[n++] = u+2;
    			indices2[n++] = u+3;
    			indices2[n++] = u;
    		}
    		indices = indices2;
    		indices2 = null;	
    		VertexBuffer ib = mesh.getBuffer(Type.Index);
    		ib.updateData(BufferUtils.createIntBuffer(indices));
    
	    }
	    }
	    else if(view < distance && q.children){
	    	q.childs.get(0).receiving = false;
	    	q.childs.get(1).receiving = false;
	    	q.childs.get(2).receiving = false;
	    	q.childs.get(3).receiving = false;
	    	Quad.list.removeAll(q.childs);
	    	q.receiving = true;
	    	q.children = false;
	    	  	if(q.parent != null && q.parent.childs.get(0).receiving && q.parent.childs.get(1).receiving && q.parent.childs.get(2).receiving && q.parent.childs.get(3).receiving){
		    		Quad.list.add(q.parent);
		    		}
	    	VertexBuffer vb = mesh.getBuffer(Type.Position);
	    	verts = (Quad.getVertices());
	    	vb.updateData(BufferUtils.createFloatBuffer(verts));
	    	int newSize = (verts.length/4)*6;
	    	int[] indices2 = new int[newSize];
	    	System.arraycopy(indices, 0, indices2, 0, newSize);
	    	indices = null;
	        indices = indices2;
	    	VertexBuffer vi =(mesh.getBuffer(Type.Index));
	    	vi.updateData(BufferUtils.createIntBuffer(indices));

	    }
	    } 

The way in which I gather the vertices from the quads is shown as follows:

public static Vector3f[] getVertices(){
		ArrayList<Vector3f> returning = new ArrayList<Vector3f>();
	
		for(int i = 0; i<list.size(); i++){
			Quad q = list.get(i);
			if(q.receiving){
				returning.addAll(q.leaves);
			}
		}
		Vector3f[] r = new Vector3f[returning.size()];
		returning.toArray(r);
		returning.clear();
		returning = null;
		return r;
	}

 If a quad is "reveiving" then it's vertices are being drawn on screen. I think if any problems exist then this is the block of code in which they do. 

Any help is appreciated, thanks. 

Edited by multifractal

Share this post


Link to post
Share on other sites
swiftcoder    18426

I don't know for sure that [tt]getVertices()[/tt] is the root of all your problems, but it is indeed a terrible function. Here's a few things I find painful about it:

 

- You allocate a new ArrayList, then incrementally fill it with vertices. This is bad, as the incremental fill will have to reallocate and copy the underlying storage, potentially as many as [tt]list.size()[/tt] times.

 

- Then you allocate a big vertex array, and copy the ArrayList into it. This is not quite as bad as the previous stage, but you are still allocating and copying a potentially huge chunk of memory.

 

- Then you [tt]clear()[/tt] the ArrayList, which has to loop over the entire list and set each element to null. Which might be useful if you were going to reuse the list, but...

 

- You explicitly null the ArrayList. This makes the previous call to [tt]clear/[tt] completely redundant, as the whole lot will get garbage collected anyway. But both are completely unnecessary, because [tt]returning[/tt] is a local variable that is never visible to an outside scope, so the reference will be gone when the function returns, anyway.

Share this post


Link to post
Share on other sites
multifractal    306

Hmm well short of doing something messy like this: 

public static Vector3f[] getVertices(){
	int size = list.size();
	int n = 0;
for(int i = 0; i<size; i++){
	if(list.get(i).receiving){
		n++;
	}
}
n*= 1024;
Vector3f[] r = new Vector3f[n];
int s = 0;
		for(int i = 0; i<size; i++){
			Quad q = list.get(i);
			int l = q.leaves.length;
			if(q.receiving){
			for(int ii = 0; ii<l; ii++){
				r[s] = q.leaves[ii];
				s++;
			}}else{continue;}
		}
		return r;
	}

I can't think of any other ways to accomplish it...

Edited by multifractal

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this