Jump to content

  • Log In with Google      Sign In   
  • Create Account

Improving Quadtree (LOD) System


Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

  • You cannot reply to this topic
2 replies to this topic

#1 multifractal   Members   -  Reputation: 229

Like
0Likes
Like

Posted 10 July 2013 - 01:38 PM

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, 10 July 2013 - 01:39 PM.


Sponsor:

#2 swiftcoder   Senior Moderators   -  Reputation: 10367

Like
0Likes
Like

Posted 11 July 2013 - 05:01 AM

I don't know for sure that getVertices() 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 list.size() 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 clear() 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 clear/[tt] completely redundant, as the whole lot will get garbage collected anyway. But both are completely unnecessary, because [tt]returning is a local variable that is never visible to an outside scope, so the reference will be gone when the function returns, anyway.


Tristam MacDonald - Software Engineer @Amazon - [swiftcoding]


#3 multifractal   Members   -  Reputation: 229

Like
0Likes
Like

Posted 13 July 2013 - 02:43 AM

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, 13 July 2013 - 07:30 PM.





Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.



PARTNERS