Page 4 of 4

Re: Segment Query (raycasting) API requests

Posted: Tue Nov 17, 2009 2:16 am
by ShiftZ
Again im having trouble with raycasting. Sometime i have misses.

Code: Select all

static inline cpFloat
segmentQuery(cpSpaceHash *hash, cpSpaceHashBin *bin, void *obj, cpSpaceHashSegmentQueryFunc func, void *data)
{
	for(; bin; bin = bin->next){
		cpHandle *hand = bin->handle;
		void *other = hand->obj;
		
		// Skip over certain conditions
		if(
			// Have we already tried this pair in this query?
			hand->stamp == hash->stamp
			// Has other been removed since the last rehash?
			|| !other
			) continue;
		
		// Stamp that the handle was checked already against this object.
		hand->stamp = hash->stamp;
		
		return func(obj, other, data);
	}
	
	return 1.0f;
}
Ok, here we pass some checks about stamp and existance, and.... returning with single object check. But hey, what about others? I had misses when i have two or more shapes in cell and when hash collision. That makes no sens.

Re: Segment Query (raycasting) API requests

Posted: Tue Nov 17, 2009 2:35 am
by ShiftZ

Code: Select all

static inline cpFloat
segmentQuery(cpSpaceHash *hash, cpSpaceHashBin *bin, void *obj, cpSpaceHashSegmentQueryFunc func, void *data)
{
	cpFloat t = 1.0f;
	for(; bin; bin = bin->next){
		cpHandle *hand = bin->handle;
		void *other = hand->obj;
		
		// Skip over certain conditions
		if(
			// Have we already tried this pair in this query?
			hand->stamp == hash->stamp
			// Has other been removed since the last rehash?
			|| !other
			) continue;
		
		// Stamp that the handle was checked already against this object.
		hand->stamp = hash->stamp;

		cpFloat ft = func(obj, other, data);
		if (ft < t) t = ft;
	}
	
	return t;
}
That's better

Re: Segment Query (raycasting) API requests

Posted: Tue Nov 17, 2009 10:08 am
by slembcke
Yet another good catch. I guess I got a bit overzealous with my early exit optimizations.

I also noticed yet another bug that I added recently. I had replaced the (int)floor(f) with an inlined int_floor() function for performance issues. It was rounding integral numbers down, so rays that started exactly on a grid cell boundary would cause the ray to be traced from an offset cell. -_- Fixed that too.

There is still one minor known issue with integral ray start coordinates. Regardless of the direction of the ray, it will always start in the cell to the upper right. It will still hit all the correct cells, but will have the cost of visiting the extra cell. I'm going to leave it for now as it seems like a very minor performance issue. I did a stress test on the query demo shooting random rays towards of about screen length and was able to get almost 2 million raycasts per second on my 2.4Ghz Core2. Not going to worry about 1 extra cell traversal just yet. ;)

Re: Segment Query (raycasting) API requests

Posted: Fri Dec 04, 2009 6:16 am
by dieterweb
Look like there is a bug in the docu:

cpSegmentQueryInfo info;
if(cpSpaceSegmentQueryFirst(space, a, b, -1, 0, &info)){

You have to set info->shape = NULL, otherwise the function will return the random memory location as the shape, if nothing was hit.

Thomas

Re: Segment Query (raycasting) API requests

Posted: Fri Dec 04, 2009 9:30 am
by slembcke
Hmm. I guess I always wrapped it in an if like that or initialized the struct as cpSegmentQueryInfo info = {};. That is a bug though. I'll add it to the list.

edit: Fixed. I'll make a note in the documentation too that it doesn't need to be initialized.

Re: Segment Query (raycasting) API requests

Posted: Wed May 19, 2010 6:38 am
by ShiftZ
Does cpSpaceSegmentQuery always interate shapes in order they appear on the way of ray? i get reverse order some times or maybe arbitrary, is it possible?

i get t = 0.934297 and then suddenly t = 0.205411

Re: Segment Query (raycasting) API requests

Posted: Wed May 19, 2010 8:31 am
by slembcke
If you need them in order you will have to sort them yourself. It iterates them in the order that it finds them in the spatial hashes. It first checks the static shapes, then checks the active shapes. The order objects are found in each spatial hash is mostly in order, but depends on the sizes of bounding boxes and the order the objects were inserted.