Here's the email I sent in search of someone who could make a more efficent vis alorithim:
Topic:
Need help on a visibility algorithim.
- Code: Select all
I was wondering if you could help on an algorithim problem? An opensource 3D game called nexuiz uses a(n) (also opensource) map compiler called q3map2 to compile it's maps into a BSP tree and compute visibilty and lighting. Currently the visibility stage uses an algorithim called "PassageFlow" to compute the visibility tables. The thing is, for any slightly complex map the time to compute visibility seems to rises exponentially. The original maps that this program was used for were fairly simple so this was not a problem and was not fixed. As this program is used for larger and more complex maps the problems increase greatly (2.5 day vis times are not terribly uncommon for large maps, even with large blocksizes set). Could you perhaps help to find or develop a more efficent algorithim?
The program's source is available through svn (along with the map editor) at http://emptyset.endoftheinternet.org/svn/radiant15/trunk/tools/quake3/q3map2/
and the visibility computing algorithims are in these two files:
http://emptyset.endoftheinternet.org/svn/radiant15/trunk/tools/quake3/q3map2/vis.c
http://emptyset.endoftheinternet.org/svn/radiant15/trunk/tools/quake3/q3map2/visflow.c
(On linux or other unix-like systems the command (svn checkout http://emptyset.endoftheinternet.org/svn/radiant15/trunk/ NetRadiant) can be used to retrieve the whole package, it uses the ./configure; make; system to build)
The devs of nexuiz usually are avaiable at http://alientrap.org/forum/ and there is a development forum in there (Divverent is currently the main developer). Everything is opensource and under the GPL.
I hope there is a better algorithim other than n^n for this problem :P
Please join the emailing campaign (see if you can get media, code, etc devs for nexuiz, you can use my mails ofcourse if you want or make your own).
Also, for what it's worth, I've made bumpmaps for some of my celing textures.