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

Post those lines of code you feel like sharing or find what you require for your project here; or simply use them as tutorials.
CodeGen
Posts: 13
Joined: Tue Apr 21, 2009 5:12 pm

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

Post by CodeGen »

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. )
Last edited by CodeGen on Sat Jul 11, 2009 5:40 am, edited 1 time in total.
shadowslair
Posts: 758
Joined: Mon Mar 31, 2008 3:32 pm
Location: Bulgaria

Post by shadowslair »

All I can say is: "Lol! Interesting! So much work!" :o
"Although we walk on the ground and step in the mud... our dreams and endeavors reach the immense skies..."
bitplane
Admin
Posts: 3204
Joined: Mon Mar 28, 2005 3:45 am
Location: England
Contact:

Post by bitplane »

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?
Submit bugs/patches to the tracker!
Need help right now? Visit the chat room
FuzzYspo0N
Posts: 914
Joined: Fri Aug 03, 2007 12:43 pm
Location: South Africa
Contact:

Post by FuzzYspo0N »

yea cool! interesting implementation
netpipe
Posts: 669
Joined: Fri Jun 06, 2008 12:50 pm
Location: Edmonton, Alberta, Canada
Contact:

super sweet

Post by netpipe »

aweee yeah, this is exactly what i wanted... Thanks a bajillion.
d3jake
Posts: 198
Joined: Sat Mar 22, 2008 7:49 pm
Location: United States of America

Post by d3jake »

Also very nice! It's awesome that we have something like this without having to lease the engine that RF uses....
The Open Descent Foundation is always looking for programmers! http://www.odf-online.org
"I'll find out if what I deleted was vital here shortly..." -d3jake
netpipe
Posts: 669
Joined: Fri Jun 06, 2008 12:50 pm
Location: Edmonton, Alberta, Canada
Contact:

mmm

Post by netpipe »

http://www.xup.in/dl,79082444/GeoModWithIrrlicht.7z i started this linux CB port but am stuck.
CodeGen
Posts: 13
Joined: Tue Apr 21, 2009 5:12 pm

Post by CodeGen »

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" ) :

Image

( 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 ) :

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

But i think that would be better :
Image
Yoran
Site Admin
Posts: 96
Joined: Fri Oct 07, 2005 8:55 am
Location: The Netherlands
Contact:

Post by Yoran »

Hey Codegen i wondered where you went :)
Really great work, hope it can be incorporated
Bill777
Posts: 1
Joined: Sat Jul 11, 2009 9:01 pm

Post by Bill777 »

What system requirements for a drawing?
CodeGen
Posts: 13
Joined: Tue Apr 21, 2009 5:12 pm

Post by CodeGen »

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
Posts: 26
Joined: Mon Jan 04, 2010 8:02 pm

Post by wowdevver24 »

can download be re-uploaded plz, really wanted to check this out
Remember all information is contextual and if I do not understand the context I cannot gras the information
netpipe
Posts: 669
Joined: Fri Jun 06, 2008 12:50 pm
Location: Edmonton, Alberta, Canada
Contact:

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

Post by netpipe »

Live long and phosphor!
-- https://github.com/netpipe/Luna Game Engine Status 95%
REDDemon
Developer
Posts: 1044
Joined: Tue Aug 31, 2010 8:06 pm
Location: Genova (Italy)

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

Post by REDDemon »

few screenshots? nice anyway ;)
Junior Irrlicht Developer.
Real value in social networks is not about "increasing" number of followers, but about getting in touch with Amazing people.
- by Me
CodeGen
Posts: 13
Joined: Tue Apr 21, 2009 5:12 pm

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

Post by CodeGen »

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.
Post Reply