real-time constructive solid geometry

I am newbie. I need to build a small application to demonstrate real-time constructive solid geometry between two models. So, I want to subtract one basic model from another (boolean difference). Let's say I want to subtract a cylinder from a box to create a box with a cylindrical hole in it. The cylinder is moved by me in the game. IS this possible in lite-C enviroment?

In order to be more explicit concerning boolean subtraction see
http://en.wikipedia.org/wiki/Constructive_solid_geometry

Thank you guys.

Another similar question asked in other thread and people argue around.

I think it is possible via shaders. I meat you can fake it using shaders .So instead of building real boolean difference you can use a shader to fake it.

I am not a shader expert so i cant go further.

this can be done but is relatively complicated.

Also, doing this with primitives is different from models - heres how to do it with primitives, including rendering in GS:

first, you need a sort class to store data:
as you read on wikepedia, CSG can be represented by various primitives connected to each other via boolean arithmetic (+ or -).

so, in lite-c we don't have classes, but we can use variables instead.
so, for your example, we would store data for a cube and a cylinder and "link" them together (in C++ you could just make a shape class that has another Shape variable inside), lite-c you'll have to play around :\

when rendering, you have 2 choices - represent your geometry as polygons via dynamically created data, or render s-curves or dots/lines with d3d_draw.

for the first, we can use a recursive subdivision routine that will base its starting values on the intersection points between the two shapes. Check our ray-line intersection equations for this. So, you will create a list of vertices by analyzing each point on the parent shape. if the said point is intersecting with the child shape, you replace the intersection volume location with the equation for the child shape and continue. The result will be a highly tesselated model that will render via draw_begin and sending the vertices as a vertex buffer to d3d. you could also render each vertex as a point for an easier way of showing the mesh without too much directX knowledge.

if you need more specifics, contact me - I know my explanation is a bit confusing - I don't have enough room or time right now to explain in even more detail.

ps, intersecting 2 models can be done in the same way but using ray-polygon intersection and testing every polygon against the sample point (its slow but this is the easiest way to implement).

-Mike-

Mike, thanks for the fast reply. I just started to learn 3d game studio for 3 days so i must confess I am not able to do this at the time. I thought is much simpler to do this. I will try to follow step by step other newbie tutorial.

Will be great if they could implement such features.

Thank you very much once again.

Me again...With the models will be much simpler? Can you suggest some steps? Thank you very much.

I am so confused foxfire.
I didt mean geometry modification via complex vertex shaders. I mean if there is way not to really do it but make it appear like that using a view-dependent method. i have no exact idea how should it be. but i think its possible.
let me give you a deeper plan:
we have two objects (models) one to be subtracted(B) and one as knife(B)
firs we render (A) to stencil buffer then using stencil buffer we render (B) on screen with flip normals, so til now we have rendered B with fliped normals only on pixels were A and B are overlaping (interrelate). Then we render Last B once again using stencil buffer but instead of screen we use stencil buffer as render target. finally we render A using stencil buffer on screen. after all we have a rendered total screen. A and B are:
1-B is not rendered but in interrelate areas it is rendered whit fliped normals
2-A is rendered but in interrelate areas it is not rendered

it may have some problems specially with texture and UVs.
I think it may work but i dont know how to implement it. i hope you understand my approach.

Dr_Black, I want geometry modification of the "subtracted" object (model). As a matter of fact I want to be able to see, what is the shape the "subtracted" object.

yeah, I'm talking about just CSG as an algorithm and how to basically build a procedural model to render - it doesn't need any shaders or anything - this is done on the CPU. You can render it by just making a vertex buffer based on the 3d points and their neighbors.

anyway - I can help you in person, just add me on msn =]

-Mike-

oh, and DR-Black, that is a clever idea for real-time CSG. but i think he wants to actually do single calculations and store the result. Either way I know how to do it. Dr-Black, feel free to add me on msn too - we can colaborate (the 3 of us) to figure out a working implementation in GS. -Mike-

one question, do you need it for presentation?

Or do you need this stuff for real?

If you need it for a presentation, you maybe could work with ent_morph and ent_create?

greetings

Mike

Foxfire,Thank for that,I will be glad to do that.But i dont like msn i use yahoo instead.

we can colaborate (the 3 of us) to figure out a working implementation in GS.Its good idea to do that. I am waiting for you Foxfire and CItrok

I found that my approach may not work when knife(B) is completely inside base(A). in this case wrong results may appear.Some other cases that wrong results appear :
1- when we handle concave-shaped models (as both knife and base)
2- when the camera (eye) is inside either base or knife (which cause the stencil buffer to completely filed)

It has some shadowing and collission detection knot. So for now it is not practical unless we work on it to figure it out.

I think this approach is better:
As always we have to objects(models) on to be subtracted(A) we call this "base" and one to be knife(B) we do following :
1-Render A (base) using a depth map generator shader (simple camera-space Z > pixel brightness) and store result in a buffer for example "bdm" (stand for base depth map)
2-Render B same way and store result to a buffer named "kdm" (stands for knife depth map)
3- Do this :

for each bpx as pixel in bdm //for each pixel in base depth map
for each kpx as pixel in knm //for each pixel in knife depth map
if bpx == kpx //if the depth is equal
fill same pixel in stencil buffer
end
end
end

Now stencil buffer contains area where surfaces of A and B are overlaping

4-Render B with flipped normals using stencil buffer on screen
5-Invert stencil buffer
6-Render A using stencil buffer on screen
7-end

It seems it works better when base is a flat surface and knife is convex-shaped for example it can used for bullet hole ,so on. Any idea?

For collission : Every time C (third object) collides with A(base) and NOT collides whit B(knife) it (C) collides the way we want

For shadownig : I have no idea.

i think i might have a helpful resource. look up Red Faction's Geo-Mod Technology, Red Faction is the game i started my hobby as a Game Artist.

Is there any shader guy who can implement this?

I dont think 3DGS support realtime primitive instancing/creation.
You still can do it using C++ I guess, using directX interface, but it's beyond my knowledge...

There's another option, with Pixel Shader 3.0 Geometry Shader, but I dont know if 3DGS support that too...