CSG Operations Again

Graphics and GPU Programming Programming

Started by Gammastrahler May 26, 2003 01:59 PM

4 comments, last by Gammastrahler 20 years, 10 months ago

Gammastrahler

150

Author

May 26, 2003 01:59 PM

Hi, and first thanks to many people who helped me getting my CSG stuff to work

though there are still problems. i have included an image that visualizes the problem (culling is enabled so don´t be confused). the red circle marks splits that must not occur, since the second object don´t pass through the back side of the big main cube.

you see the problem: the splits on the backface of the big cube are invalid since the long lower object do not pass through the back of it! it was hard to debug my code..... i just came to the point where i suffered to keep track of debugging it because of the deep recursions of the trees. maybe i should post some code here right now:

            
void CBSPTree::CSG_Union(BSPNode* pNode, CBSPTree &destTree, CBSPTree &resultTree)
{
    if (pNode->_isLeaf)
    {
        std::vector<CPolygon>::iterator pPoly = pNode >_polyList.begin();

	for ( ; pPoly != pNode->_polyList.end(); ++pPoly)
	{
	    destTree.Store_Front_Faces_For_Union(*pPoly, destTree.root(), resultTree);
	}

	return;
    }

    CSG_Union(pNode->_frontNode, destTree, resultTree);    
    CSG_Union(pNode->_backNode, destTree, resultTree);
}

void CBSPTree::Store_Front_Faces_For_Union(const CPolygon &poly, BSPNode* pNode, CBSPTree &resultTree)
{
    if (pNode->_isLeaf)
    {
	if (ClassifyPolygon(poly, pNode->_terminalNode->_splitter) == PLANE_TRI_FRONT)
	{
	    CPolygon tempPoly = poly;
	    tempPoly._splitPlane = false;
	    pNode->_polyList.push_back(poly);
	    resultTree.add_poly(tempPoly, resultTree.root());
	}
	return;
    }

    int result = ClassifyPolygon(poly, pNode->_splitter);

    if (result == PLANE_TRI_FRONT)
    {
	Store_Front_Faces_For_Union(poly, pNode->_frontNode, resultTree);
    }
    else if (result == PLANE_TRI_BACK)
    {
	Store_Front_Faces_For_Union(poly, pNode->_backNode, resultTree);
    }
    else if (result == PLANE_TRI_PLANAR)
    {
	float side = poly._plane._normal.Dot(pNode->_splitter._normal);

	if (side >= 0.0f)
	    Store_Front_Faces_For_Union(poly, pNode->_frontNode, resultTree);
	else
	    Store_Front_Faces_For_Union(poly, pNode->_backNode, resultTree);

	}
	else if (result == PLANE_TRI_SPANNING)
	{
	    CPolygon outPoly[2];

	    SplitPolygon(poly, pNode->_splitter, outPoly);
	
	    Store_Front_Faces_For_Union(outPoly[0], pNode->_frontNode, resultTree);
	    Store_Front_Faces_For_Union(outPoly[1], pNode->_backNode, resultTree);
	}
}

// and here is the usage example code for the two objects:


void SetupScene()
{
    bsp_a.InsertMesh(my_big_cube_mesh);    // the big cube

    bsp_a.Compile();

    bsp_b.InsertMesh(my_obj_b);    // the one which goes inside the big cube

    bsp_b.Compile();

    bsp_b.CSG_Union(bsp_b.root(), bsp_a, result_bsp);
    bsp_a.CSG_Union(bsp_a.root(), bsp_b, result_bsp);

    result_bsp.Compile();

i hope someone finds the error! i would be very happy for any help.... thanks Gammastrahler [edited by - Gammastrahler on May 26, 2003 3:09:36 PM]

Basiror

241

May 27, 2003 05:46 AM

your problem is you didn t check if the polygon you clip against he brush sides are infront or behind the side or spanning

if it is behind you need to clip it against the rest of the brush sides ....

http://www.8ung.at/basiror/theironcross.html

Gammastrahler

150

Author

May 27, 2003 06:06 AM

but i actually do it....

look at my source code, i test the polygon to clip against the brush sides for front, back, spanning and planar, and i go into the proper subtrees.

Gammastrahler

150

Author

May 27, 2003 06:21 AM

I have found an interesting article about CSG.

Here is the link:
from the article:

"Once you've implemented CSG, there's just one more thing you might want to know about: unnecessary splits. That's right, the CSG algorithm can cause a lot of polygons to be split for no reason."

maybe my code isn´t wrong....

[edited by - Gammastrahler on May 27, 2003 7:22:18 AM]