Segment Query (raycasting) API requests

Discuss new features and future development.

Re: Segment Query (raycasting) API requests

Postby ShiftZ » Fri Oct 23, 2009 6:25 am

Yes, i've found that bug and fixed. But problem decribed above still present. Try demo modification, if it will work for ?
ShiftZ
 
Posts: 114
Joined: Sat Mar 07, 2009 7:23 am

Re: Segment Query (raycasting) API requests

Postby slembcke » Fri Oct 23, 2009 9:33 am

Hmm. I remember that coming up and thought I added the change to trunk. Apparently I didn't. :|
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 » Fri Oct 23, 2009 4:46 pm

Hi again, recenly i had some research about that raytracing issue and found and odd thing, either a terrbile bug or something ive missed.

static inline void
hashHandle(cpSpaceHash *hash, cpHandle *hand, cpBB bb)
{
// Find the dimensions in cell coordinates.
cpFloat dim = hash->celldim;
int l = bb.l/dim;
int r = bb.r/dim;
int b = bb.b/dim;
int t = bb.t/dim;


Here is cell index definition.
And strange thing, both (int)0.99f and (int)-0.99f gives us zero.
So, shape that should be located in cell (0,-1) actually hashed as cell (0, 0). When we begin ray traversing from cell (0, -1) we see nothing. Is it correct?

You have hash grid like that: 2 1 0 0 -1 -2 and traversing 2 1 0 -1 -2

int l = (int)cpffloor(bb.l/dim);
fixes problem. Ive found 4 instances in code where it should be fixed.
Last edited by ShiftZ on Fri Oct 23, 2009 7:52 pm, edited 2 times in total.
ShiftZ
 
Posts: 114
Joined: Sat Mar 07, 2009 7:23 am

Re: Segment Query (raycasting) API requests

Postby ShiftZ » Fri Oct 23, 2009 7:41 pm

Also, you do not checking last cell while traverse.

while(next_h < 1.0f || next_v < 1.0f)

this prevent performing quering when next_h and next_v is out of range. But they should be out of range in last cell. And if first is last , then we miss quering totally.

Adding

int index = hash_func(cell_x, cell_y, n);
query(hash, hash->table[index], obj, func, data);

after while block fixes this problem.
Last edited by ShiftZ on Fri Oct 23, 2009 7:53 pm, edited 1 time in total.
ShiftZ
 
Posts: 114
Joined: Sat Mar 07, 2009 7:23 am

Re: Segment Query (raycasting) API requests

Postby ShiftZ » Fri Oct 23, 2009 7:49 pm

With these two fixes it works fine.
ShiftZ
 
Posts: 114
Joined: Sat Mar 07, 2009 7:23 am

Re: Segment Query (raycasting) API requests

Postby slembcke » Sat Oct 24, 2009 3:47 pm

Very good catch. I actually did know that from working on some procedural noise code once. I guess I never put the two together though. :oops:

I commited those changes and am still able to get it to miss raycasts:
http://files.slembcke.net/temp/screensh ... 154204.png

I know there were some bugs that caused it to miss raycasts that happened along the x and y axis before, but haven't had the time to figure out why.

Thank you very much for your help so far. I know that this is a feature that other people really want, but I just haven't had the time with contracting work and trying to develop our own games lately to finish it properly.
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 » Sun Oct 25, 2009 9:37 am

Implemented bullets with raycasting, and it works fine for me, no misses.
I can share a file to you.
ShiftZ
 
Posts: 114
Joined: Sat Mar 07, 2009 7:23 am

Re: Segment Query (raycasting) API requests

Postby slembcke » Fri Oct 30, 2009 4:57 pm

Fixed the missed raycasts that I was talking about. It was only an issue when the start point was on a grid point and the direction was very close to horizontal or vertical but biased in the positive direction of the minor direction axis... If that made any sense. Ultimately it just came down to replacing a ceil(value) with a floor(value + 1). I think the raycasting code is functionally complete and hopefully mostly bug free!

The next item to do is implement an early exit when you only want the first object hit along a long ray. Right now it finds all hits and returns only the earliest one.
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 slembcke » Fri Oct 30, 2009 6:24 pm

slembcke wrote:The next item to do is implement an early exit when you only want the first object hit along a long ray. Right now it finds all hits and returns only the earliest one.


Turs out that this was pretty easy too. When traversing the grid, it stores the current "t" value along the segment query. I just modified it a bit so that the callbacks it uses return the collision value and it won't traverse to the next cell if the cell is beyond the collision.

I have done absolutely no performance testing of the raycasting stuff, though I think it's pretty algorithmically sound at this point. The only bummer is that spatial hashes aren't exactly raycasting's best friend. You can't do true infinite ray queries, and very long queries may have to traverse a lot of cells, possibly wasting a lot of time only to find nothing. On the other hand, very short queries, like bullet trajectories should be very fast.

I'm quite happy with the way the API turned out as well and don't expect to be making further changes:
Code: Select all
typedef void (*cpSpaceSegmentQueryFunc)(cpShape *shape, cpFloat t, cpVect n, void *data);
int cpSpaceShapeSegmentQuery(cpSpace *space, cpVect start, cpVect end, cpLayers layers, cpLayers group, cpSpaceSegmentQueryFunc func, void *data);

int cpSpaceShapeSegmentQueryFirst(cpSpace *space, cpVect start, cpVect end, cpLayers layers, cpLayers group, cpSegmentQueryInfo *out);

int cpShapeSegmentQuery(cpShape *shape, cpVect a, cpVect b, cpLayers layers, cpLayers group, cpSegmentQueryInfo *info);

cpVect cpSegmentQueryHitPoint(cpVect start, cpVect end, cpSegmentQueryInfo info);
cpFloat cpSegmentQueryHitDist(cpVect start, cpVect end, cpSegmentQueryInfo info);


That gets you a callback based query iterator, an efficient short-circuit-first-hit-only query, the ability to raycast individual shapes, and some helper functions for determining hit points and distances.
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 slembcke » Fri Oct 30, 2009 10:24 pm

Hah. I had thought I simplified the terminating condition for the grid traversal, but I ended up just re-adding the bug that ShiftZ pointed out. :oops: It's actually fixed and simplified now. Whoops.
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

PreviousNext

Return to Features/Development

Who is online

Users browsing this forum: No registered users and 2 guests