It is currently Wed Aug 12, 2020 3:29 am


All times are UTC




Post new topic Reply to topic  [ 6 posts ] 
Author Message
 Post subject: PolyVox and Distance Transforms
PostPosted: Tue Oct 05, 2010 12:35 am 

Joined: Sat Sep 18, 2010 9:45 pm
Posts: 189
Hi, do you have any recommendation for Distance Transforms (for Distance Fields computation of volume)? I'm looking into implementing Distance Transforms but I'm very noob at this. I will get it sorted out eventually. Just thinking maybe you have some advice. Perhaps in the form of some library?

A little bit on what my plan is: I have already a set of OpenCL functions which implements pathfinding that is based on Potential Fields (computed from gradients of distance fields of "obstacles" and summed with other contributing fields). This part I had done before getting into PolyVox. Now I'm trying to get PolyVox to work with that. My plan is to extract some sort of information from the Volume, similar to the SurfaceExtractors. I'm sorry I can't say exactly what I'm going to extract because like I said, I don't even know how to generate distance transforms. Well, that's the plan, extract the information from the Volume, then compute the distance transform from that using what I'm going to implement with OpenCL. After that, I can pass this data to my A.I functions.


Top
Offline Profile  
Reply with quote  
 Post subject: Re: PolyVox and Distance Transforms
PostPosted: Tue Oct 05, 2010 4:53 am 

Joined: Sat Sep 18, 2010 9:45 pm
Posts: 189
I would like to add maybe computing distance transforms in order to do path-finding may not even work. I'm not sure what I want yet. I'm also thinking of using NavMesh and run the mesh that is generated from PolyVox through that. I'm not sure whether that will work.


Top
Offline Profile  
Reply with quote  
 Post subject: Re: PolyVox and Distance Transforms
PostPosted: Tue Oct 05, 2010 6:56 pm 
Developer
User avatar

Joined: Sun May 04, 2008 6:35 pm
Posts: 1827
Hi,

If you want to compute a distance transform then you should look into 'distance propagation' methods. These are fast but maybe not that accurate. You can improve on this with the slower 'vector propagation' techniques. I don't think I have an actual library for you though and I haven't implemented it into PolyVox.

How3ever, the problem with distance fields is that the whole thing can become invalid if one voxel changes in the volume. And I think a 256^3 one takes a couple of seconds to compute. You can probably improve on this if you only want it to be locally accurate - I'm not sure though.

As for other ideas, I think Recast Navigation uses some voxel based internal format. Maybe you can hook into that but again I doubt if it's real time.

Otherwise maybe subsample the volume to a lower resolution and just use something conventional like A*?

Sorry I can't be more helpful, I don't have much experience with AI...


Top
Offline Profile  
Reply with quote  
 Post subject: Re: PolyVox and Distance Transforms
PostPosted: Tue Oct 05, 2010 11:10 pm 

Joined: Sat Sep 18, 2010 9:45 pm
Posts: 189
Maybe I will do that, downsample and use A*.

Today I thought maybe I could compute the distance function from the noise function. I simply say that above certain value returned from my noise function implies that it is impassable (due to larger value of gradient on the Y), and the distance value would be threshhold - current_value. Wait, the problem is with dynamic content... Hmm. Maybe I'm going scale down my vision and just limit the type of AI that I have in mind to certain precomputed areas. Then for everywhere else I can think those places as wilderness and have random dumb mob AIs. Doing everything I wanted is going to be hard.

Thanks.


Top
Offline Profile  
Reply with quote  
 Post subject: Re: PolyVox and Distance Transforms
PostPosted: Wed Oct 06, 2010 5:46 pm 
Developer
User avatar

Joined: Sun May 04, 2008 6:35 pm
Posts: 1827
beyzend wrote:
Wait, the problem is with dynamic content...

Yeah, this is basically the biggest problem. You need to rely on as few data stuctures as you can, and those that you do rely on need to be updated in realtime (or spread out over a few frames).

Maybe you could instead attach 'feelers' to each character in the form of raycasts in several directions? Raycasts at least are fast through volume data. This can stop AI walking into walls but doesn't give them much sense of direction.

Yep, tricky problem :-)


Top
Offline Profile  
Reply with quote  
 Post subject: Re: PolyVox and Distance Transforms
PostPosted: Thu Oct 07, 2010 12:49 am 

Joined: Sat Sep 18, 2010 9:45 pm
Posts: 189
Well I'm going to try A* for global pathfinding and RVO2 for local avoidance. The reason I looked into distance map in the first place is because I wanted to try something new, I wanted to try Potential Field based methods. I don't actually need it. A* should work.


Top
Offline Profile  
Reply with quote  
Display posts from previous:  Sort by  
Post new topic Reply to topic  [ 6 posts ] 

All times are UTC


Who is online

Users browsing this forum: No registered users and 4 guests


You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot post attachments in this forum

Search for:
Jump to:  
cron
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group
Theme created StylerBB.net