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 3388 - (download) (annotate)
Tue Nov 10 03:17:51 2015 UTC (3 years, 10 months ago) by lamonts
File size: 4958 byte(s)
Adding support for disabling spatial optimization
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 sphereSearchOpt(@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)
{
	@STRANDTY@ ** strands = wrld->inState;
	if (!curr) return; 

	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)))) {

		sphereSearchOpt(wrld,curr->left,qPos,qStrandId,qList, radius, i, dim,neighborCount);
		sphereSearchOpt(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)){
		sphereSearchOpt(wrld,curr->right,qPos,qStrandId, qList,radius, i, dim,neighborCount);
	}else {
		sphereSearchOpt(wrld,curr->left, qPos,qStrandId, qList,radius, i, dim,neighborCount);
	} 
}
void sphereSearch(@PREFIX@World_t * wrld,  
				  Diderot_vec@SPATIAL_DIMENSION@_t qPos,
				  uint32_t qStrandId, 
				  QueryList_t * qList,
				  Diderot_real_t radius,  
				  uint32_t dim,
				  uint32_t * neighborCount)
{
	@STRANDTY@ ** strands = wrld->inState;
	for(int i = 0; i < wrld->numStrands; i++){
		@STRANDTY@ * curr = strands[i]; 
		bool shouldInclude = (qStrandId != curr->strandId) && 
						 (wrld->status[curr->strandId] == DIDEROT_ACTIVE || 
						  wrld->status[curr->strandId] == DIDEROT_STABLE); 
   		if (shouldInclude && Diderot_KDTree_isWithinRadius(qPos,curr,radius,dim)){
   			Diderot_QueryList_Add(strands[curr->strandId],qList); 	
			*neighborCount +=1; 
   	 	}
   }
}


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); 
	if(!wrld->disableSOpt)
	{
		sphereSearchOpt(wrld,tree->root,qPos,qStrandId,qList,radius,0,tree->dim,&neighborCount); 
	}else {
		sphereSearch(wrld,qPos,qStrandId,qList,radius,@SPATIAL_DIMENSION@,&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