Home My Page Projects Code Snippets Project Openings diderot
Summary Activity Tracker Tasks SCM

SCM Repository

[diderot] View of /branches/lamont/src/compiler/c-target/fragments/kdtree.in
ViewVC logotype

View of /branches/lamont/src/compiler/c-target/fragments/kdtree.in

Parent Directory Parent Directory | Revision Log Revision Log


Revision 3282 - (download) (annotate)
Tue Oct 13 19:46:34 2015 UTC (4 years, 3 months ago) by lamonts
File size: 4114 byte(s)
Fixed bug with dead strands appearing in query lists
typedef Diderot_real_t Diderot_vec1_t;

void  Diderot_KDTree_Swap(@STRANDTY@ ** x, @STRANDTY@ ** y) {
	@STRANDTY@ * tmp = x[0]; 
	x[0] = y[0]; 
	y[0] = tmp; 
}
Diderot_real_t Diderot_KDTree_GetPos3D(Diderot_vec3_t pos, uint32_t idx){
	Diderot_union3_t u; 
    u.v = pos; 
    return u.r[idx]; 
}
Diderot_real_t Diderot_KDTree_GetPos2D(Diderot_vec2_t pos, uint32_t idx){
	Diderot_union2_t u; 
    	u.v = pos;
	return u.r[idx];  
}
Diderot_real_t Diderot_KDTree_GetPos1D(Diderot_real_t pos, uint32_t idx){
	return pos;  
}
Diderot_real_t Diderot_KDTree_GetPosValue(@STRANDTY@ * strand, uint32_t idx) { 

	return Diderot_KDTree_GetPos@SPATIAL_DIMENSION@D(strand->pos,idx); 

}
Diderot_real_t Diderot_Query_GetPosValue(Diderot_vec@SPATIAL_DIMENSION@_t qPos, uint32_t idx) { 

	return Diderot_KDTree_GetPos@SPATIAL_DIMENSION@D(qPos,idx); 

}
bool Diderot_KDTree_isWithinRadius(Diderot_vec@SPATIAL_DIMENSION@_t qPos,@STRANDTY@ * neighbor, Diderot_real_t radius, uint32_t dim) { 

	return isWithinRadius@SPATIAL_DIMENSION@D(qPos, neighbor->pos, radius); 
}

void sphereSearch(@PREFIX@World_t * wrld,  
				  KDNode_t * curr,
				  Diderot_vec@SPATIAL_DIMENSION@_t qPos,
				  uint32_t qStrandId, 
				  QueryList_t * qList,
				  Diderot_real_t radius, 
				  uint32_t i,  
				  uint32_t dim,
				  uint32_t * neighborCount)
{
	
	if (!curr) return;

	@STRANDTY@ ** strands = wrld->inState;
	bool shouldInclude = (qStrandId != curr->strandId) && 
						 (wrld->status[curr->strandId] == DIDEROT_ACTIVE || 
						  wrld->status[curr->strandId] == DIDEROT_STABLE); 

	if(shouldInclude && Diderot_KDTree_isWithinRadius(qPos,strands[curr->strandId],radius,dim)) {
	
		Diderot_QueryList_Add(strands[curr->strandId],qList); 	
		*neighborCount +=1; 

	}

	int oldI = i;

	if (++i >= dim) i = 0;

	if ( Diderot_Query_GetPosValue(strands[curr->strandId]->pos,oldI) >= (Diderot_Query_GetPosValue(qPos,oldI) - radius)  &&
		(Diderot_Query_GetPosValue(strands[curr->strandId]->pos,oldI) <= (Diderot_Query_GetPosValue(qPos,oldI) + radius))) {
		sphereSearch(wrld,curr->left,qPos,qStrandId,qList, radius, i, dim,neighborCount);
		sphereSearch(wrld,curr->right,qPos,qStrandId, qList,radius, i, dim,neighborCount);

	}else if(Diderot_Query_GetPosValue(strands[curr->strandId]->pos,oldI) <= (Diderot_Query_GetPosValue(qPos,oldI) - radius)){
		sphereSearch(wrld,curr->right,qPos,qStrandId, qList,radius, i, dim,neighborCount);
	}else {
		sphereSearch(wrld,curr->left, qPos,qStrandId, qList,radius, i, dim,neighborCount);
	}

}


STATIC_INLINE Diderot_DynSeq_t * spherical_query(
                                 @PREFIX@World_t * wrld,  
                                 Diderot_vec@SPATIAL_DIMENSION@_t qPos,
                                 @STRANDTY@ * qStrand,
                                 QueryListPool_t * queryPool, 
                                 Diderot_real_t radius)
{

	uint32_t neighborCount=0; 
	@STRANDTY@ ** strands = wrld->inState;
	KDTree_t * tree = wrld->spatialTree;
 	uint32_t qStrandId = qStrand->strandId;
	QueryList_t * qList = Diderot_Grab_QueryList(queryPool); 
	sphereSearch(wrld,tree->root,qPos,qStrandId,qList,radius,0,tree->dim,&neighborCount); 
	Diderot_DynSeq_t * seq = Diderot_DynSeqAlloc(sizeof(@STRANDTY@ *), neighborCount);
    seq->data = qList->pool;
	return seq; 
}
@STRANDTY@ ** Diderot_KDTree_Seq_FindMedian(@STRANDTY@ ** start, @STRANDTY@ ** end, uint32_t idx, uint32_t dim){

	if(end <= start) return NULL;
	if(end == start + 1) return start;
	@STRANDTY@ **curr, **store, **mid =  start + (end-start)/2;
	Diderot_real_t pivot;

	while(true) {
		
		pivot = Diderot_KDTree_GetPosValue(mid[0],idx);

		Diderot_KDTree_Swap(mid,(end -1));

		for (store = curr = start; curr < end; curr++) {
			if (Diderot_KDTree_GetPosValue(curr[0],idx) < pivot) {
				if (curr != store)
					Diderot_KDTree_Swap(curr, store);
				store++;
			}
		}
		Diderot_KDTree_Swap(store, (end - 1));

		/* median has duplicate values */
		if (Diderot_KDTree_GetPosValue(store[0],idx)  == Diderot_KDTree_GetPosValue(mid[0],idx))
			return mid;

		if (store > mid)	end = store;
		else		start = store;


	}
	return NULL;
}


root@smlnj-gforge.cs.uchicago.edu
ViewVC Help
Powered by ViewVC 1.0.0