Segment Query (raycasting) API requests

Discuss new features and future development.
ShiftZ
Posts: 114
Joined: Sat Mar 07, 2009 7:23 am
Contact:

Re: Segment Query (raycasting) API requests

Post 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.
ShiftZ
Posts: 114
Joined: Sat Mar 07, 2009 7:23 am
Contact:

Re: Segment Query (raycasting) API requests

Post 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
User avatar
slembcke
Site Admin
Posts: 4166
Joined: Tue Aug 14, 2007 7:13 pm
Contact:

Re: Segment Query (raycasting) API requests

Post 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. ;)
Can't sleep... Chipmunks will eat me...
Check out our latest projects! -> http://howlingmoonsoftware.com/wordpress/
dieterweb
Posts: 176
Joined: Fri Feb 27, 2009 7:12 am
Location: Germany
Contact:

Re: Segment Query (raycasting) API requests

Post 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
Visit our game Blog: [url]http://zombiesmash.gamedrs.com[/url] or follow us on twitter: [url]http://twitter.com/zombiesmash[/url]
User avatar
slembcke
Site Admin
Posts: 4166
Joined: Tue Aug 14, 2007 7:13 pm
Contact:

Re: Segment Query (raycasting) API requests

Post 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.
Can't sleep... Chipmunks will eat me...
Check out our latest projects! -> http://howlingmoonsoftware.com/wordpress/
ShiftZ
Posts: 114
Joined: Sat Mar 07, 2009 7:23 am
Contact:

Re: Segment Query (raycasting) API requests

Post 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
User avatar
slembcke
Site Admin
Posts: 4166
Joined: Tue Aug 14, 2007 7:13 pm
Contact:

Re: Segment Query (raycasting) API requests

Post 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.
Can't sleep... Chipmunks will eat me...
Check out our latest projects! -> http://howlingmoonsoftware.com/wordpress/
Post Reply

Who is online

Users browsing this forum: No registered users and 8 guests