[phpBB Debug] PHP Warning: in file [ROOT]/includes/bbcode.php on line 488: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file [ROOT]/includes/bbcode.php on line 488: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file [ROOT]/includes/bbcode.php on line 488: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file [ROOT]/includes/bbcode.php on line 488: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file [ROOT]/includes/bbcode.php on line 488: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file [ROOT]/includes/bbcode.php on line 488: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file [ROOT]/includes/bbcode.php on line 488: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file [ROOT]/includes/bbcode.php on line 488: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file [ROOT]/includes/bbcode.php on line 488: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file [ROOT]/includes/bbcode.php on line 488: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file [ROOT]/includes/bbcode.php on line 488: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file [ROOT]/includes/bbcode.php on line 488: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file [ROOT]/includes/bbcode.php on line 488: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file [ROOT]/includes/bbcode.php on line 488: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file [ROOT]/includes/bbcode.php on line 488: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file [ROOT]/includes/bbcode.php on line 488: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file [ROOT]/includes/bbcode.php on line 488: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file [ROOT]/includes/bbcode.php on line 488: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file [ROOT]/includes/bbcode.php on line 488: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file [ROOT]/includes/bbcode.php on line 488: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file [ROOT]/includes/bbcode.php on line 488: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file [ROOT]/includes/bbcode.php on line 488: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file [ROOT]/includes/bbcode.php on line 488: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file [ROOT]/includes/bbcode.php on line 488: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file [ROOT]/includes/bbcode.php on line 488: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file [ROOT]/includes/bbcode.php on line 488: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file [ROOT]/includes/bbcode.php on line 112: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file [ROOT]/includes/bbcode.php on line 112: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file [ROOT]/includes/bbcode.php on line 112: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file [ROOT]/includes/bbcode.php on line 112: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file [ROOT]/includes/functions.php on line 4762: Cannot modify header information - headers already sent by (output started at [ROOT]/includes/functions.php:3897)
[phpBB Debug] PHP Warning: in file [ROOT]/includes/functions.php on line 4764: Cannot modify header information - headers already sent by (output started at [ROOT]/includes/functions.php:3897)
[phpBB Debug] PHP Warning: in file [ROOT]/includes/functions.php on line 4765: Cannot modify header information - headers already sent by (output started at [ROOT]/includes/functions.php:3897)
[phpBB Debug] PHP Warning: in file [ROOT]/includes/functions.php on line 4766: Cannot modify header information - headers already sent by (output started at [ROOT]/includes/functions.php:3897)
Chipmunk Physics • View topic - Segment Query (raycasting) API requests

Segment Query (raycasting) API requests

Discuss new features and future development.

Segment Query (raycasting) API requests

Postby slembcke » Thu May 21, 2009 4:16 am

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 OneSadCookie » Thu May 21, 2009 6:17 am

OneSadCookie
 
Posts: 2
Joined: Thu May 21, 2009 6:05 am

Re: Segment Query (raycasting) API requests

Postby slembcke » Thu May 21, 2009 12:47 pm

Well, one problem with traversing a spatial hash is that you don't really get anything in order. With a nice spatial structure like a BSP, you always know that you are traversing the splitting planes in order and can terminate whenever you want. With a spatial hash, a grid cell near the end of traversal could be hashed to the same hash cell as a grid cell near the beginning of the traversal, and within each grid cell you objects certainly won't be in order either. So you basically have to run the entire traversal before deciding which is closest. Though I'm sure there are some heuristics that could be used to cut it down based on grid cell distance estimates or something. I'm somewhat worried that this will make the performance be lackluster.

So to implement what you are suggesting would require finding all intersections, sorting them by distance, then passing them to the callback. Not really so bad implementation-wise, but it's not like it would turn out to be an optimization that allows one to terminate the search early. The only useful early termination would be the trivial "Did I hit anything at all?" case. As far as sidestepping memory issues from the callback passing you a malloc()ed struct, I guess passing the values back as params does get around ever needing to malloc() anything internally even. That I guess is worth something.
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 OneSadCookie » Thu May 21, 2009 2:55 pm

OneSadCookie
 
Posts: 2
Joined: Thu May 21, 2009 6:05 am

Re: Segment Query (raycasting) API requests

Postby slembcke » Thu May 21, 2009 3:34 pm

Hmm. I suppose in order to traverse the grid, I will need to be tracking the alpha value anyway, so that part won't really be so hard. I don't really like the ambiguity of keeping a "small number" of allocations on the stack, so I would need to toss a bunch of memory management code into it.

I think I'm going to approach the implementation in a couple of passes. First just iterate all of the objects in the hash and check each individually. This would be a good simple base implementation to test against. Next move onto a normal AABB query that the spatial hash currently supports. That should at least make the performance usable. Then implement a grid traversal query in the spatial hash. As a bonus, that could also be used for hashing line segment shapes. Probably a decent bonus for long diagonal line segments. Once all that is working... Then finally move onto in order traversal of the ray collisions.

I guess I'm not too concerned initially about having in order traversal. If you want all of the collisions and want them sorted, it's not hard to put them in an array and sort them yourself. If you want just the first collision there can be an API call to wrap that. Without in order traversal, finding the first won't be super efficient, but will work without changes once it does get implemented giving you a free speed boost.
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 majicDave » Thu May 21, 2009 6:04 pm

All sounds pretty good to me.

I can see situations where the exit point may also be useful to know, if that info isn't too difficult to add. Maybe just alphaNear and alphaFar or something?
majicDave
 
Posts: 6
Joined: Thu May 21, 2009 5:44 pm

Re: Segment Query (raycasting) API requests

Postby slembcke » Thu May 21, 2009 11:10 pm

I can't really see the exit point being usefull 99% of the time. Circles are the only case where calculating the exit point would be a trivial addition. If you want both, just query the reverse segment against each individual shape returned by the space.
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 May 22, 2009 2:53 am

Can someone give me e short explanation for what the segment query is useful? Line to Line collisions, bullets?

Thanks,
Thomas
Visit our game Blog: or follow us on twitter:
dieterweb
 
Posts: 176
Joined: Fri Feb 27, 2009 7:12 am
Location: Germany

Re: Segment Query (raycasting) API requests

Postby slembcke » Fri May 22, 2009 9:14 am

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 » Mon May 25, 2009 4:18 am

Thank you for this detailed answer. No need for this in my current project, but I will keep this in mind.

Are all of your current cvs changes for this feature?

Thomas
Visit our game Blog: or follow us on twitter:
dieterweb
 
Posts: 176
Joined: Fri Feb 27, 2009 7:12 am
Location: Germany

Next

Return to Features/Development

Who is online

Users browsing this forum: No registered users and 1 guest