Page 3 of 4

Re: Segment Query (raycasting) API requests

Posted: Fri Oct 23, 2009 6:25 am
by ShiftZ
Yes, i've found that bug and fixed. But problem decribed above still present. Try demo modification, if it will work for ?

Re: Segment Query (raycasting) API requests

Posted: Fri Oct 23, 2009 9:33 am
by slembcke
Hmm. I remember that coming up and thought I added the change to trunk. Apparently I didn't. :|

Re: Segment Query (raycasting) API requests

Posted: Fri Oct 23, 2009 4:46 pm
by ShiftZ
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.

Re: Segment Query (raycasting) API requests

Posted: Fri Oct 23, 2009 7:41 pm
by ShiftZ
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.

Re: Segment Query (raycasting) API requests

Posted: Fri Oct 23, 2009 7:49 pm
by ShiftZ
With these two fixes it works fine.

Re: Segment Query (raycasting) API requests

Posted: Sat Oct 24, 2009 3:47 pm
by slembcke
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.

Re: Segment Query (raycasting) API requests

Posted: Sun Oct 25, 2009 9:37 am
by ShiftZ
Implemented bullets with raycasting, and it works fine for me, no misses.
I can share a file to you.

Re: Segment Query (raycasting) API requests

Posted: Fri Oct 30, 2009 4:57 pm
by slembcke
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.

Re: Segment Query (raycasting) API requests

Posted: Fri Oct 30, 2009 6:24 pm
by slembcke
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.

Re: Segment Query (raycasting) API requests

Posted: Fri Oct 30, 2009 10:24 pm
by slembcke
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.