[Algorithms] Navigation meshes: The Followup From: Diogo de Andrade - 2005-10-18 16:50:06 ```Hey all! I've been working on and off in the automatic generation of the navigation meshes, and although my algorithm combined with some of the ideas you all pitched in works more or less alright, and although it still produces very ugly meshes, they are quite functional, although they still generated quite ugly "serrated" edges near "wall" objects. Thinking about this, I came to the conclusion that this is a consequence of the algorithm as I'm formulating it: recursive subdivision until a certain area/side lenght is reached: if I put this value very low, I get a very nice fitting navigation mesh, although it takes forever to generate and has too many triangles (although this last could be solved with some mesh simplification code). So, I started thinking on new approaches to the problem... The solution proposed by Patrick Smith in Gamasutra (http://www.gamasutra.com/features/20020405/smith_01.htm) is a nice formulation and has the advantage of also enabling us to create portals more or less automatically... It has the problem of having to encode the movement rules of the game in question in the navigation mesh generation, but I'm sure some solution to this can be found (lots of parameters, corresponding to step size, max height for a "step", ignorable objects (below a certain volume threshould), considerations about crouched/walking movement). Another solution I considered is one that I'm not at all confortable, but it seems "correct": Boolean operations on triangle meshes; this solution would subtract the "wall triangles" from the "floor triangles", considering some very nice epsilon-calculations... This solution in theory is perfect, in practice I doubt I can make it work (we all know the problems visible in most complicated Boolean operations in 3d programs), specially with border cases (that would be quite frequent in the wall/floor scenario). Besides I don't even know where to begin: the last time I read something about CSG was in the time Doom 1 was king and it involved some sort of BSP, but I can't recall the details. So, what are you thoughts about the Boolean approach? Is it worth the effort of experimenting with (I don't have lots of time pressure here; the artists are doing the nav meshes by hand for our projects)? If yes, where can I get some info on CSG (only interested in subtraction, really), what would be a good place to start, etc? Thanks in advance! Diogo de Andrade Creative & Technical Director Spellcaster Studios diogo.andrade@... http://www.spellcasterstudios.com ```
 [Algorithms] Navigation meshes: The Followup From: Diogo de Andrade - 2005-10-18 16:50:06 ```Hey all! I've been working on and off in the automatic generation of the navigation meshes, and although my algorithm combined with some of the ideas you all pitched in works more or less alright, and although it still produces very ugly meshes, they are quite functional, although they still generated quite ugly "serrated" edges near "wall" objects. Thinking about this, I came to the conclusion that this is a consequence of the algorithm as I'm formulating it: recursive subdivision until a certain area/side lenght is reached: if I put this value very low, I get a very nice fitting navigation mesh, although it takes forever to generate and has too many triangles (although this last could be solved with some mesh simplification code). So, I started thinking on new approaches to the problem... The solution proposed by Patrick Smith in Gamasutra (http://www.gamasutra.com/features/20020405/smith_01.htm) is a nice formulation and has the advantage of also enabling us to create portals more or less automatically... It has the problem of having to encode the movement rules of the game in question in the navigation mesh generation, but I'm sure some solution to this can be found (lots of parameters, corresponding to step size, max height for a "step", ignorable objects (below a certain volume threshould), considerations about crouched/walking movement). Another solution I considered is one that I'm not at all confortable, but it seems "correct": Boolean operations on triangle meshes; this solution would subtract the "wall triangles" from the "floor triangles", considering some very nice epsilon-calculations... This solution in theory is perfect, in practice I doubt I can make it work (we all know the problems visible in most complicated Boolean operations in 3d programs), specially with border cases (that would be quite frequent in the wall/floor scenario). Besides I don't even know where to begin: the last time I read something about CSG was in the time Doom 1 was king and it involved some sort of BSP, but I can't recall the details. So, what are you thoughts about the Boolean approach? Is it worth the effort of experimenting with (I don't have lots of time pressure here; the artists are doing the nav meshes by hand for our projects)? If yes, where can I get some info on CSG (only interested in subtraction, really), what would be a good place to start, etc? Thanks in advance! Diogo de Andrade Creative & Technical Director Spellcaster Studios diogo.andrade@... http://www.spellcasterstudios.com ```