modifying csg.c to use more than 128 polygons

Hello Everyone,

I downloaded “csg.c” in the GLUT distrubution. It shows how to display Constructive Solid Geometry in realtime with some help of the stencil buffer. This has been really helpful because it shows how render CSG and it works very well.

I modified the code to use my model instead of the simple red box. I still am using the cone to intersect with my model. I have found that my model does not draw properly when my model exceeds 128 polygons. I am thinking there is a limit on the number of polygons drawn to the stencil buffer.

Can anyone provide suggestions on some things to try? My model is very large and I would like to see the cone subtracted out of my model.

Thanks,

Tim

How old are you and where are you from? Is english your first language?
If you’re an english speaking adult, what in gods name are you doing asking such a dumb question?

I guess I am stupid. Are you going to answer the question and become a hero?

Tim

No there is no limit how many polygons you can draw into the stencil buffer. the stencilbuffer is just a 2d-buffer like the framebuffer: you can draw as many polygons into it as you want…

about your application limit: i don’t know how the meshes are drawn in this particular piece of code.
(vertex arrays? indexed primitives ? imidiate mode ?)
but a limit of 128 tris would make sense, if the indicies of the triangles where stored as singend bytes (-> range -127…+128). check this.
if this is not the problem: check the buffersizes.
if this is not the problem: just take any other opengl-meshrendering-example and learn how to do it yourself.
(it always helps to understand how something works…)

btw.: stencil is not really a good way for dooing csg. it is good for small examples like the one you have, but if you plan to create huge scenes, containing many meshes i suggest you to do it offline on the triangle level before rendering.
(but this task is very hard to accomplish)

and finally: this question shows, that you are new in openGL programming.
please ask such questions in the beginner forum (after reading the specs and tutorials from this site)

Perhaps one of the stencil wrap extensions would help in this case.

Adrian,
Thanks for the post. I thought this was a pretty advanced question and I still do. I checked the comments that you had and I did not find anything that jumped out at me.

Can you explain why using stencil planes is not the way to go if I am using many polygons. I would really like to use the graphics hardware to cut through my model since (like you said) it is very difficult to do the tmesh math. I am getting the cut out through my model when I draw more than 128 polygons but it looks like all of my polgons are drawn using the back of the polygon instead of the front. Maybe the glStencilFunc cannot process more than 128 polygons in a single pass???

What are your thoughts on using the tesselation functions in opengl to cut through my model?

BTW: Why did the original guy who answered this question respond like he did. Is he really a member of the advanced forum group. I found his response rather un-professional.

Tim

Knackered’s post may have been a little blunt, but I also wondered whether or not English was your native language when I first read your post. Do you really mean to say that it breaks as soon as you render more than 128 polygons PERIOD, or are you trying to say that it breaks when you render 128 polygons that all overlap on the screen (i.e. you have an overdraw factor of 128)?

The former scenario can only point to a silly mistake on your behalf. The stencil test is a per-fragment operation, and it does not know or care how many polygons are being rendered. The latter scenario, however, is less unlikely. The stencil buffer is typically an 8-bit buffer, and massive overdraw like that could cause the values to overflow. Read CatAtWork’s post again if this is the case.

– Tom


Can you explain why using stencil planes is not the way to go if I am using many polygons. I would really like to use the graphics hardware to cut through my model since (like you said) it is very difficult to do the tmesh math.

it depends on your application which way is the better one. when you plan to do some animated special-effects with a limited number of intersecting objects, then the stencil-method could be a good way for doing it.
but when you want to create huge scenes(quake-like) using this method, you end up drawing a lot of invisible geometry, which consumes a lot of fillrate.
when you start thinking about shadows, things gets even whorser:
with stencil-shadows:
1.you don’t have a stencil-buffer anymore.(ok, it can be simulated using the alphabuffer but this is really hard stuff…but if you want do it, i can give you a paper about it)
2.you don’t have any information about the acutal geometry, except the basic primitives you used to define the csg-operations, so you can’t create a shadowvolume of this geometry…(except you try doing the same csg-operations with the shadowvolumes of the basic primitives. which creates even more fillrate-issues)
with shadowmaps, you have to render the scene from lights point of view…and you must do all the csg-opearations again.

optimization of huge and complex scenes is mostly about draw-only-what-you-see:
clipping, backface/occlusion culling, Possible Visibility lists & stuff.
with your method you are doing the opposite: you draw a lot more primitives than you finally see on the screen. with todays hardware it is a lot faster to draw a large mesh with a lot of triangles, than to draw a lot of meshes with a small number of tris.


I am getting the cut out through my model when I draw more than 128 polygons but it looks like all of my polgons are drawn using the back of the polygon instead of the front. Maybe the glStencilFunc cannot process more than 128 polygons in a single pass???

the stencilbuffer has a bitdepth (usually 8 bit, but i have also seen a kyroII-board with 4 bit stencil)
when you are using stencil to mask out 2 objects, you are using at least 2 different stencil-states to represent them.
so when you are using more than 2 objects, the number of needed flags grows and you get at some point an overflow problem.
in this case - like catatwork said - would the stencil wrap extension help.
but i actually don’t think that that’s your problem. this would be true when you would draw more then 2 objects in the scene.
it sounds for me like every polygon would get its own stencil-value (which sounds strange…)
i don’t know exactly how your example works, but i have some ideas:

  • when you are using some additive methods in the stencil (increasing or decreasing the value in the test) then your problem could be that the stencil is initialized with 128 instead of 0. i think, when you set the number to 0, then you could draw 255-polygon meshes. if this works, then i think you should show some codepieces of your drawing-code.


What are your thoughts on using the tesselation functions in opengl to cut through my model?

my honest thougts: there are no tesselation functions in opengl !
what you are talking about is the GLUT, which is a utility library, but not part of opengl.
i am not using it.
why ? i do this stuff myself.
again, why ? because this way i can optimize it for the particular application, where i am needing it.
ie.: with the tesselation-routines from glut, i can’t get the siluetteinformations for shadowvolumes. and i can’t do proper collisiondetection on this object - except i am performing the boolean operations by myself during the collisondetection.
there are some other useful glut-functions, which are nice to use when you start coding (ie.gluPerspective). but once you implemented your own versions, it’s easier to use them.


BTW: Why did the original guy who answered this question respond like he did. Is he really a member of the advanced forum group. I found his response rather un-professional.
Tim

this is a public forum. and like in every public area, sometimes there are guys around who think that this is “their private” area. And because they are forced (by an invisible, psychological force) to read all posts, they sometimes get upset when they read what they dont like. then they start “protecting their property against intruders”…
i think its a kind of instinct(kind of “protect your hunting-grounds-instinct”). not really explainable. just emotions.
there is only one way to deal with it(it is actually a very easy way, which seems not to be an option for this ppl…but anyway):
don’t read what you don’t like. just ignore it. :wink:

I think in that sample, they set the stencil clear value to 127 or 128 to make sure overflow and underflow is unlikely to occur.

Like CatAtWork said, stencil wrap (EXT_stencil_wrap) will help. EXT_stencil_two_side should improve the algorithm’s performance.

PS: this does qualify as a beginners question.

OK… I am starting to think this is a beginners question. I thought I was a out of the beginners level but the more I read your responses the more “beginner” I feel. But, I would like to finish my problem using this discussion thread because I already have smart people helping me.

Some of you think (like V-Man) that my stencil reference is initialize to 128. I do not see where the author of csg.c example has implemented 128. The default is 0, right? I see that the GL_STENCIL_BITS is 0. This leads me to believe that it is infact initialized to 0, not 128. What are your thoughts???

I read what I could find on “stencil wrap extensions”. Is this an extra library that I have to download? Some of the #defines are not in any of my include files such as GL_STENCIL_TEST_TWO_SIDE_EXT. I am using Visual C++ 6.0 and I have added the glut libraries. Can someone point me to these extensions or even help explain what they are? I read that they do things like the DirectX libraries.

Tom,
How could massive overdraw to the stencil bit planes could cause overflow? I thought the polygons are masked out depending on the depth of the 256 stencil levels. Could it be that the polygon cannot decide which stencil bit to draw in because there are so many polygons in that stencil plane?

Thanks for all of your help,
Tim

GL_STENCIL_BITS is 0

This means that you have no stencil buffer at all.

Originally posted by tec:
[b]Tom,
How could massive overdraw to the stencil bit planes could cause overflow? I thought the polygons are masked out depending on the depth of the 256 stencil levels. Could it be that the polygon cannot decide which stencil bit to draw in because there are so many polygons in that stencil plane?

Thanks for all of your help,
Tim[/b]
What Tom means is that your Stencil buffer is only 8 bits (hence the 256 “Levels”). If you initialise your Stencil buffer to zero, then set your stencil op to increment, and then draw 256 polygons, each overlapping, then the portions that overlap in all 256 polygons will “overflow”. Ie. with poly 255 your buffer will be 255, and with 256 it will go back to zero. The same can happen with decrementing too.

In your case people seem to be leaning towards your code having initialised the buffer to 127 which will give you 128 stencil increments before overflow.

What I don’t understand with this whole thread is you appeared to state that if you draw more than 128 tris/polys then you have this problem (and you don’t state that it occurs when you have 128 polys that all overlap - unless I have missed it).

You also stated that it appears that all your poly’s end up being rendered using the “back of the polygon instead of the front”. Perhaps if you can post a (link to a) screen shot of what this looks like it might help.

To me it sounds like a simple winding order - you wouldn’t be using a lightwave model (or a Quake/Doom/id model) would you? If so the poly/tri winding is the reverse of default GL. So you either need to reverse the winding, set glCullFace(GL_FRONT) or use glFrontFace(GL_CW).

Originally posted by rgpc:
Ie. with poly 255 your buffer will be 255, and with 256 it will go back to zero. The same can happen with decrementing too.
[/QB]
Wrapping will only happen if you use GL_INCR_WRAP or GL_DECR_WRAP else if the demo is using GL_INCR or GL_DECR, then this will clamp values during overflow and underflow.

I don’t know what method is used in csg.c, so this may not be the issue.

Ah yes. Der. :rolleyes:

So in tec’s case the 128th write (and subsequent writes) will not change the stencil buffer (rather than “Wrapping” as V-man correctly pointed out)

But I still think the problem might be something else…

Thanks everyone for your latest responses,

jwatte: I was mistaken when I said
GL_STENCIL_BITS = 0. It is infact 8.

rgpc: Not all of my polygons appear to be drawn as backface. I depends on the orientation of my model. All polygons draw correctly when I switch back to drawing my target without subtracting out the cylinder. Remember, I am using csg.c which allows my to render my target as “A or B” and “B - A”. “A or B” renders both models correctly because no stencil planes are used. “B - A” has problems.

V-man: The csg.c does not use wrapping. I would really like to learn more about wrapping put I cannot find any documentation of this technique. Could someone point me in the right direction?

Below I have copied the “inside” function used to “cut out” model “a” from “b”. It apears to me that the stecil function is always resetting the reference back to zero. Is this what is wrong? I would just define the reference once during initialization and then do the increments or decrements as I draw more polygons. Maybe csg.c has a bug?

void inside(void(*a)(void), void(b)(void), GLenum face, GLenum test)
{
/
draw A into depth buffer, but not into color buffer */
glEnable(GL_DEPTH_TEST);
glColorMask(GL_FALSE, GL_FALSE, GL_FALSE, GL_FALSE);
glCullFace(face);
a();

/* use stencil buffer to find the parts of A that are inside of B
 * by first incrementing the stencil buffer wherever B's front faces
 * are...
 */
glDepthMask(GL_FALSE);
glEnable(GL_STENCIL_TEST);
glStencilFunc(GL_ALWAYS, 0, 0); // ref and mask do not matter because the polys are always passed

//glStencilOp(failstencil, zfail, zpass); zbuffer fail/pass
//the first param says what happens to the stencil buffer value if the stencil test fails. The two other values are not used
//if the stencil passes than zfail or zpass will be used.
glStencilOp(GL_KEEP, GL_KEEP, GL_INCR);
glCullFace(GL_BACK);
b();

/* ...then decrement the stencil buffer wherever B's back faces are */
glStencilOp(GL_KEEP, GL_KEEP, GL_DECR);
glCullFace(GL_FRONT);
b();

/* now draw the part of A that is inside of B */
glDepthMask(GL_TRUE);
glColorMask(GL_TRUE, GL_TRUE, GL_TRUE, GL_TRUE);
glStencilFunc(test, 0, 1); // ref is 0, test is either equal or not equal, 1 is the mask
glDisable(GL_DEPTH_TEST);
glCullFace(face);
a();

/* reset stencil test */
glDisable(GL_STENCIL_TEST);

}

Please feel free to download the csg.c and view the entire example at: http://www.opengl.org/resources/code/basics/more_samples/index.html

Thanks again,
Tim

Here is a new thought.

What if I only perform the stencil bits on the polygons that are within my intersecting cylinder. This will reduce the number of polygons under 256. I can calculate if my model’s vertices are within the interecting cylinder. If any vertex is inside the cylinder then I will add the polygon to the stencil planes. If all polygons are outside the cylinder volume, then I will draw the polygon normally.

I looked on the internet to find a software library that will break apart my model without using stencil planes. I tried to do the cutting math myself but it is too complex for me. Does anyone know of a Windows library that will take a large model and cut (boolean operation) into it with another shape (cylinder)? csg.c uses the stencil planes.

Thanks,
Tim

What is the object that you are trying to draw (ie. what is it a model of?). I suspect, though I haven’t played with the code to test it, that your object may, in some way be concave (ie. if you draw a line through the model in some directions, you will strike more than two polygons [or surfaces]).

Looking at the code you posted, I suspect that this might be the cause, because the final Stencil Op relies on a stencil buffer value of 0 and the Mask is 1. Try setting the Mask to 255 and see if that helps (I can’t say because I spend very little time using the Stencil buffer, and I haven’t tried this for myself).

So your last bit of the inside function will be:

    /* now draw the part of A that is inside of B */
    glDepthMask(GL_TRUE);
    glColorMask(GL_TRUE, GL_TRUE, GL_TRUE, GL_TRUE);
    glStencilFunc(test, 0, 255);
    glDisable(GL_DEPTH_TEST);
    glCullFace(face);
    a();

    /* reset stencil test */
    glDisable(GL_STENCIL_TEST);

Although as I think about it, if you are subtracting the cone from your model, it shouldn’t make a difference…

Post a screenshot…

All,
Please see my images at:
http://www.knology.net/~tec/bad_stencil.jpg

My model is an aircraft nose in gray. The two images are rendered with the same perspective view. The image on the left is my model or’ed with a yellow cylinder. Therefore, everything is rendered, correctly. 

The one on the right is my model minus the cylinder. Notice that the right model is showing holes in the side of the nose. The cylinder does not intersect my model so the cylinder will not cut into my model. I just wanted to show you the problem with the depth zbuffer (or is it a stencil buffer problem).

Thanks for looking at this,

Tim

After much stuffing around with the code I think the problem may “simply” be that this technique doesn’t work with “3+ Manifold” objects (ie. Object where drawing a line through the object will result in hitting 3 or more faces).

One way to show this is by using the “Sphere” and “Cylinder” sub-routines in your code as A and B. As you have pointed out, if you use this, it works. However, if you change “Sphere” and add a second sphere (glutSphere (0.5, 16, 16)) just before the first, it does not work (and you get a z-order problem like what you are currently experiencing).

In tec’s case the model being used is essentially a cone within a cone, which seems to be confusing the stencil buffer/z-buffer.

I think you’d be better off looking at nVidia’s “Cull Fragment Complex” which is included in their SDK.