Attempt to implement real-time CSG (GeoMod of Red Faction 1)

CodeGen · Post by **CodeGen** » 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. )

shadowslair · Post by **shadowslair** » Fri Jul 10, 2009 9:22 pm

All I can say is: "Lol! Interesting! So much work!"

bitplane · Post by **bitplane** » Fri Jul 10, 2009 10:30 pm

This is really cool, I hope you or someone else develops it further!
I guess for the full effect we'd also need some kind of scene editor that can organise the CSG, including setting materials for the inside of the mesh?

FuzzYspo0N · Post by **FuzzYspo0N** » Fri Jul 10, 2009 10:44 pm

yea cool! interesting implementation

netpipe · Post by **netpipe** » Fri Jul 10, 2009 11:39 pm

aweee yeah, this is exactly what i wanted... Thanks a bajillion.

d3jake · Post by **d3jake** » Sat Jul 11, 2009 12:32 am

Also very nice! It's awesome that we have something like this without having to lease the engine that RF uses....

netpipe · Post by **netpipe** » Sat Jul 11, 2009 1:05 am

http://www.xup.in/dl,79082444/GeoModWithIrrlicht.7z i started this linux CB port but am stuck.

CodeGen · Post by **CodeGen** » Sat Jul 11, 2009 6:08 am

And we need to improve surface clipping routines.
Suppose we carve a cube from a slab.
This is how they did in RF ( note the "wrapping" ) :

( These convex polys are then triangulated. Look at http://john.slagel.com/Geomods.html )

And this is what does my stupid implementation ( note how many polys it creates ) :

( i simply filtered surface polys through a tree ( RemoveFacesInsideNode(), RemoveFacesOusideNode() ). )

But i think that would be better :

Yoran · Post by **Yoran** » Sat Jul 11, 2009 9:07 am

Hey Codegen i wondered where you went

Really great work, hope it can be incorporated

Bill777 · Post by **Bill777** » Sat Jul 11, 2009 9:09 pm

What system requirements for a drawing?

CodeGen · Post by **CodeGen** » Sat Jul 11, 2009 9:45 pm

The demo was compiled under Windows, uses DirectX render API, doesn't use any shaders, but is very CPU-intensive ( it doesn't use hardware buffers for rendering, just raw mesh buffers placed in system memory ). And it crashes if it fails to create a sound device.
System requirements are pretty low but the faster CPU the better.

Bitplane, this technique works only with solid & non-solid materials, it doesn't take into account the material of the inside of the mesh.

I think that using pointerless structures ( half-edges and BSP nodes ) is the way to go. Knowing mesh adjacency would enable us to apply large decals to the mesh's surface, reduce polygon count ( merging coplanar adjacent faces), morph the mesh and so on.
After repeated operations trees may grow large ( in RF1, shoot many times at the same spot with a rocket and quite noticeable delays will occur ) -> we should use several BSP trees with their own dynamic mesh buffers and organize them in an octree or something like that.
And in a real world application we should precompile ( precache ) trees from geomod meshes ( it would be easy to store them, fast to operate on them, fast to transform them, as they would be pointerless, can be stored in linear arrays ) for better run-time performance.
Combining voxels with this method seems to be promising...

I'd like to see how people improve it to a point where it can become usable and how they use it in games. ( I currently have no time to do that. ) Or we can make a tutorial for beginners with a GeoModdableSceneNode...

wowdevver24 · Post by **wowdevver24** » Sun Jan 17, 2010 2:01 am

can download be re-uploaded plz, really wanted to check this out

netpipe · Post by **netpipe** » Sun Feb 26, 2012 8:19 am

ah here yar my port attempt -- http://www.xup.in/dl,52841989/GeoModWithIrrlicht.7z/

http://www.xup.in/dl,97032263/GeoModWit ... t-orig.7z/

REDDemon · Post by **REDDemon** » Thu Mar 01, 2012 9:08 am

few screenshots? nice anyway

CodeGen · Post by **CodeGen** » Tue Mar 06, 2012 10:41 pm

Hi!

Stan Melax has recently opened the source of his impressive demo:
http://www.melax.com/csg.html

more details and link to the source code are here:
http://altdevblogaday.com/2011/09/02/destruction/

so we can expect to see real-time booleans in video games soon.
it will probably work on low res meshes and hardware tessellation will be used to add visual detail.

i have to say, this source code that i wrote is crap, and i feel ashamed for it.
in my current version each internal tree node now occupies 8 bytes instead of 64, nodes, planes and polygons are stored in a separate arrays,
but the code is still too branchy, and i'm not totally satisfied with it.

Irrlicht Engine

Attempt to implement real-time CSG (GeoMod of Red Faction 1)

Attempt to implement real-time CSG (GeoMod of Red Faction 1)

super sweet

mmm

Re: Attempt to implement real-time CSG (GeoMod of Red Factio

Re: Attempt to implement real-time CSG (GeoMod of Red Factio

Re: Attempt to implement real-time CSG (GeoMod of Red Factio