We do indeed have the ability to write to the file system. I believe the tests are run with the working directory being polyvox/build and indeed they should be cleared before each build. There's a lot of space on the disc on the test machine so a few megabytes will be absolutely fine.

_________________
Matt Williams
Linux/CMake guy

Sounds good, I'll add the FilePager into the tests then. I also just fixed the build on Linux and added the required bindings files so hopefully it runs OK again tonight.

i was just thinking about polyvox, large volume and threading this week, now i come here, and you are already throwing the party

I don't think it's possible to write one perfect large volume that fits all threading wishes.

There are two things i think should be benchmarked.

1. make largevolume threadsafe by locking threads trying to access largevolume blocks that another thread is already accessing (i think this is the basic method to allow multithreaded access to an array of any dimension?)

2. The most regular use case would be one volume that the user edits and then extracts a mesh from. preferably both simultaneously, without editing stuff that the mesh extractor is playing with.
This should maybe be done in a higher level class, instead of using a thread safe largevolume.
Currently it feels like a hazzle to do all this stuff. One class that has the number of extraction threads it should use and wrapper accessors to the underlying volume for the main thread.
internally all kinds of magic could happen.

I'm not actually looking at threading quite yet (I'm refactoring the compression and paging first) but I'll get to it eventually. I'm mostly concerned about allowing multiple concurrent reads as this is a common use case for people wanting to split surface extraction over a number of threads. Concurrent writing will probably come later and require more locking.

I think the main problem with concurrent reads occurs when:

1. First thread points a VolumeSampler at a voxel.
2. Second thread access a different voxel, which pages its block into memory.
3. This pushes past the maximum number of blocks and an old block is paged out of memory.
4. The first thread happened to be using that block and now has a null pointer.

I think the situation can be improved without even adding any threading code to PolyVox. The LargeVolume could have a 'pinRegion()' method which would make sure that any blocks in that region don't get paged to disk, even if the memory usage gets high. So the user would have to:

1. Call pinRegion() on part of the volume.
2. Start a number of surface extraction threads on different parts of that region.
3. Wait for the threads to finish.
4. Unpin the region.

I haven't given this enough thought yet, but I'm keeping it in mind as I refactor some existing code.

I also agree that a thread-safe wrapper could be a useful construct, it could probably have the same interface as a volume but insert locks as needed.

This is pretty much the solution I was thinking of to avoid things being paged away while they're being read. This is essentially a mutex since paging away a block is basically a write operation.

I imagine that we'll provide some implementation of the above workflow, perhaps within the surface extractors inside PolyVox which should be possible with the C++11 threading tools. Perhaps something that returns a std::vector<std::future<SurfaceMesh>> or similar.

_________________
Matt Williams
Linux/CMake guy

so you'd only deliver safe access, and still require the user to behave in terms of modifying?

i mean, a user that is writing to a block while the surfaceextractor is reading it could create amusing results in the final mesh.

creating different locking mechanisms for the region/block could solve this:
read lock: any number of threads can do a read lock on a block, it'll just do what pinRegion does (and increase/decrease a counter so once it hits zero, there's no lock on it anymore)
write locks:
if there are read locks on the block and no write locks: create a new memory region for the user to write to.

• overwrite: random allocated memory (maybe with voxel constructor initialized?)
• modify write: a copy of the block

only one write lock is allowed to exist on one block


of course this could end up with a lot of deadlock situations (if the user wants to lock multiple blocks at the same time)
therefor, if at any time it's not possible to lock the whole region, the already taken block locks are undone and the user is somehow notified that the lock failed (TryLock).

as long as there are only read locks happening, everyone is happy.
if a write lock happens before a read lock, the read lock needs to wait.
if a write lock happens after a read lock, the write lock gets a copy.

It would be nice to have thread safe write access as well, but I think the thread safe read access is both more important and easier to implement. So we can start with that first.

As you say, the writing is likely to involve more locking and something such as a TryLock could be useful. At a higher level, it might be useful for an application to maintain a queue of 'volume modification tasks' in a similar way to it might have a queue of surface extraction tasks. Perhaps this allows some batching of the volume modifications to reduce the number of locks?

Overall I need to do some reading on threading and also some experiments. I recently switched Cubiquity over to the LargeVolume so it's getting some testing now, and there's a background surface extractor thread which worked with the SimpleVolume. It's currently disabled, but once the pluggable compression/paging stuff is tidied up I'll turn on the background surface extraction and see what happens...

Forgive my naivety as a newcomer, but I'm pretty familiar with threading. Is there a forum thread or documentation that outlines the wishlist of threading? I just want to understand the terminology people are using before I try to lend any potential threading solutions.

It sounds like the situation is that you generally use the surface extractor at a different 'resolution' than the voxel chunk size might be set up with(for paging in the data?), and this is where the threading complexities arise. Is there a reason that has to be the case? As it sounds like if those regions were one in the same, it could simplify things.

Is this primarily meant to address the concurrency issue of the surface extractor building a new render mesh for something potentially in parallel with game logic modifying the voxel data? Is there any reason why a simpleish deferred modification scheme cannot be employed on the application side? For example, if an explosion goes off, it can query the region of voxels is affects to see if they are in-use by a surface extractor. If any are in a currently marked in-use region, the effects of the explosion are queued and deferred, to be tried again after a simple dependency resolution(when all overlapping extractors are finished, via extractor callbacks or whatever. This in-use marking can probably be done with a simple lockless data structure that holds a list of voxel bounding boxes or something, and actual thread locking could potentially be avoided altogether. In my experience, using thread locking primitives in the game loop is to be avoided and only used as a last resort. Deferring operations, double buffering, or performing it when possible at a stage of the frame that the threads are finished(sync/join points) would be evaluated and locks only used as a last resort.

Is there more to the situation than that with regards to threading considerations?

There is some information here about the situation as I currently understand it: http://www.volumesoffun.com/polyvox/doc ... ading.html



PolyVox does indeed allow the size of the extracted mesh to be different than the block size of the volume ('block' is the PolyVox name for 'chunk'). But actually it is more general that this - PolyVox does not require the volume to be composed of blocks at all (the RawVolume is just one large piece of data) and also supports algorithms beyond surface extraction (blurring the volume is an example of where handling block edges would be tricky if PolyVox did no already handle it).

Generally we try to see the use of blocks as an implementation detail of the LargeVolume.



I think there are two (possibly distinct) scenarios.

1. The data is not being modified, and the user wishes to run multiple surface extraction at the same time. In this case the biggest issue is that reading a block (chunk) may cause a different block to get paged out of memory, even if one of the other surface extractors is using it. We can probably deal with this by 'pinning' blocks which are currently in use so they don't get paged out of memory.

2. The data is also being modified at the same time. This is more complex, and perhaps a double buffering scheme as you propose could be useful.



I think something like this is possible though I have little experience in the area. I think it will be more efficient to do some of this at the application level rather than the PolyVox level, but we might want to expose a bit more information from PolyVox (the fact that the volume is built from blocks, which ones are loaded, etc) to make this easier for the user to implement.

I see that that the article covers RawVolume and LargeVolume but not SimpleVolume. I guess in this context, the advice there is identical to RawVolume since no paging is performed in SimpleVolume?

In the work I'm currently doing to implement Dual Contouring, I'm considering using threading within the surface extractor to speed up the processing. A lot of the work in there is almost trivially parallelisable and could easily be distributed across a thread pool. I expect I'll investigate using C++11's std::async (or other threading tools) as I believe that they are available in VS2012 and above. It will be an experiment anyway.

_________________
Matt Williams
Linux/CMake guy