Segment Query (raycasting) API requests

Discuss new features and future development.

Re: Segment Query (raycasting) API requests

Postby ShiftZ » Tue Nov 17, 2009 2:16 am

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

Re: Segment Query (raycasting) API requests

Postby ShiftZ » Tue Nov 17, 2009 2:35 am

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

Re: Segment Query (raycasting) API requests

Postby slembcke » Tue Nov 17, 2009 10:08 am

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

Re: Segment Query (raycasting) API requests

Postby dieterweb » Fri Dec 04, 2009 6:16 am

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: http://zombiesmash.gamedrs.com or follow us on twitter: http://twitter.com/zombiesmash
dieterweb
 
Posts: 176
Joined: Fri Feb 27, 2009 7:12 am
Location: Germany

Re: Segment Query (raycasting) API requests

Postby slembcke » Fri Dec 04, 2009 9:30 am

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

Re: Segment Query (raycasting) API requests

Postby ShiftZ » Wed May 19, 2010 6:38 am

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

Re: Segment Query (raycasting) API requests

Postby slembcke » Wed May 19, 2010 8:31 am

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

Previous

Return to Features/Development

Who is online

Users browsing this forum: No registered users and 4 guests