Segment Query (raycasting) API requests

[ShiftZ]

Yes, i've found that bug and fixed. But problem decribed above still present. Try demo modification, if it will work for ?

[slembcke]

Hmm. I remember that coming up and thought I added the change to trunk. Apparently I didn't.

[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.

[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.

[ShiftZ]

With these two fixes it works fine.

[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.

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.

[ShiftZ]

Implemented bullets with raycasting, and it works fine for me, no misses.
I can share a file to you.

[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.

[slembcke]

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.

[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. It's actually fixed and simplified now. Whoops.