Attempt to implement real-time CSG (GeoMod of Red Faction 1)
Posted: Fri Jul 10, 2009 8:30 pm
A very basic demo showing real-time CSG. The algorithm used in the demo is BSP tree merging by Bruce Naylor ( that algo is nearly 20 years old ).
I thought that would be useful to community because i couldn't find it on the Web (when i search for "GeoMod implementation with source code"
nothing shows up on Google). So, i did some research ( played RF, found many GeoMod bugs, read papers ) and i selected, of course, Irrlicht engine for graphics ( easy to use, high speed of development with it, etc. ). And this project had remained untouched for a month when i felt i was not going to finish it. My stupid studies keep me busy.
The demo is not about graphics, it's an attempt to implement something
similar to RF's GeoMod and test Irrlicht.
The download link:
http://www.mediafire.com/?sharekey=4f0f ... f6e8ebb871
Controls:
WASD, Whitespace - movement,
shoot with mouse, select "weapons" with mouse wheel.
Notes:
Remember, the demo is very glitchy ( esp. physics ).
After a few "CSG blasts" ugly holes between polygons may appear due to finite numerical precision. We need to use adjacency data structures to avoid that. (However, we may run into problems with texture coordinates - a real-life cube has 8 vertices, but a properly textured one has >= 12 vertices ... ) i did an earlier demo where i used a greater value for game length unit and such holes were almost unnoticeable.
We can also use an adjacency data structure to calculate vertex normals for correct lightning and detect isolated ( floating in space without any support ) chunks of solid material.
A simple Bullet collision shape based on a nodey BSP tree is implemented. It's very slow, using a dynamic BV tree would be a better choice.
Future improvements ( it's up to you to implement ) :
Use incremental linear programming to achieve a faster and more robust tree merging ( the paper is freely available ).
And I think we can use LP for quickly detecting isolated pieces of solid stuff - we should search for solid cells which don't intersect ( test LP feasibility ). It would be easy since each region is bounded by planes.
Then we can see how solid cells are connected and drop those which are hanging "loosely in the air". We can check if the volume of a solid cell
is infinite ( in LP, that means infinite number of solutions ) or if it exceeds a certain threshold and that cell and all other cells connected to it should remain fixed ( shouldn't fall down ).
Remember which branches of the tree have changed and generate mesh
only from modified parts of the tree ( keep indices in tree nodes ... ).
... Progressive BSP trees for LOD, some pertubations to mesh generation and materials to improve visuals ( because models look so low poly ) ...
Clever dynamic vertex and index buffers management is necessary.
I was a bit upset after looking at the source of Irrlicht... Later i will post some of my ideas which i hope will help you to improve your marvelous engine.
Any good, bad, or ugly feedback will be appreciated.
If you think I have left out something or you have some better ideas or you have problems with download or whatever, please feel free to e-mail me at usercodegen@ymail.com. ( And sorry for my english. )
I thought that would be useful to community because i couldn't find it on the Web (when i search for "GeoMod implementation with source code"
nothing shows up on Google). So, i did some research ( played RF, found many GeoMod bugs, read papers ) and i selected, of course, Irrlicht engine for graphics ( easy to use, high speed of development with it, etc. ). And this project had remained untouched for a month when i felt i was not going to finish it. My stupid studies keep me busy.
The demo is not about graphics, it's an attempt to implement something
similar to RF's GeoMod and test Irrlicht.
The download link:
http://www.mediafire.com/?sharekey=4f0f ... f6e8ebb871
Controls:
WASD, Whitespace - movement,
shoot with mouse, select "weapons" with mouse wheel.
Notes:
Remember, the demo is very glitchy ( esp. physics ).
After a few "CSG blasts" ugly holes between polygons may appear due to finite numerical precision. We need to use adjacency data structures to avoid that. (However, we may run into problems with texture coordinates - a real-life cube has 8 vertices, but a properly textured one has >= 12 vertices ... ) i did an earlier demo where i used a greater value for game length unit and such holes were almost unnoticeable.
We can also use an adjacency data structure to calculate vertex normals for correct lightning and detect isolated ( floating in space without any support ) chunks of solid material.
A simple Bullet collision shape based on a nodey BSP tree is implemented. It's very slow, using a dynamic BV tree would be a better choice.
Future improvements ( it's up to you to implement ) :
Use incremental linear programming to achieve a faster and more robust tree merging ( the paper is freely available ).
And I think we can use LP for quickly detecting isolated pieces of solid stuff - we should search for solid cells which don't intersect ( test LP feasibility ). It would be easy since each region is bounded by planes.
Then we can see how solid cells are connected and drop those which are hanging "loosely in the air". We can check if the volume of a solid cell
is infinite ( in LP, that means infinite number of solutions ) or if it exceeds a certain threshold and that cell and all other cells connected to it should remain fixed ( shouldn't fall down ).
Remember which branches of the tree have changed and generate mesh
only from modified parts of the tree ( keep indices in tree nodes ... ).
... Progressive BSP trees for LOD, some pertubations to mesh generation and materials to improve visuals ( because models look so low poly ) ...
Clever dynamic vertex and index buffers management is necessary.
I was a bit upset after looking at the source of Irrlicht... Later i will post some of my ideas which i hope will help you to improve your marvelous engine.
Any good, bad, or ugly feedback will be appreciated.
If you think I have left out something or you have some better ideas or you have problems with download or whatever, please feel free to e-mail me at usercodegen@ymail.com. ( And sorry for my english. )