Face * SABSP_Tree::SelectGoodSplitter(list<Face *> faceList)
{
Face * Splitter;
list<Face *>::iterator Faceit, Face_it;
int Minimum = (int) faceList.size()*100;
for(Faceit = faceList.begin(); Faceit != faceList.end(); Faceit++)
{
//do not take an already taken splitter
if((*Faceit)->usedAsSplitter == true)
continue;
int FrontFaces = 0, BackFaces= 0 , IntersectFaces = 0;
for(Face_it = faceList.begin(); Face_it != faceList.end(); Face_it++)
{
if(Face_it == Faceit)
continue;
Vertex vertices[3];
vertices[0] = (_p3DSLoader->vertices[(*Face_it)->index[0]]);
vertices[1] = (_p3DSLoader->vertices[(*Face_it)->index[1]]);
vertices[2] = (_p3DSLoader->vertices[(*Face_it)->index[2]]);
Plane3D P(_p3DSLoader->vertices[(*Faceit)->index[0]],(*Faceit)->faceNormal);
CLASSIFY Classed[3];
for(int j = 0 ; j < 3 ; j++)
Classed[j] = ClassifyVertexToPlane(vertices[j],P);
int Cfront = 0, Cback = 0;
for(int j = 0 ; j < 3 ; j++)
{
if(Classed[j] == FRONT)
Cfront++;
else
if (Classed[j] == BACK)
Cback++;
}
if(Cback == 0)
FrontFaces++;
else
if(Cfront == 0)
BackFaces++;
else
IntersectFaces++;
}
int Test = abs(BackFaces - BackFaces) + IntersectFaces * 6;
if(Test < Minimum)
{
Minimum = Test;
Splitter = *Faceit;
}
}
Splitter->usedAsSplitter = true;
return Splitter;
}
Author
i m working on a game engine where the maps are based on PVS (Solid Area BSP Tree with portals) kindal ike quacke engines. the problem is that demo works like a charm cuz map is like quacke (made up of rooms) now when i try to use more complex room structure my create bsp function just crashes and it seems it is not finding any splitter (it doesnt find any splitter face and just sets its value to NULL as initialized then when the program tries to access it it crashes).
the select gd splitter algorithm is very simple and follows this concept:
For Each face get the nb of faces behind it and the nb of faces
in front of it. the splitter would have the minimum difference between the sizes
of its front list and its back list.
and my implentation is:
plz note this is the basic implementation and it is not yet optimized :P.
any help appreciated cuz i m countin on the pvs for my collision handeling
the weird thing is that it is workin in some maps but other more complex maps it would crash even if the objects r just extruded from walls.
Hi there...
this row seems fishy:
int Test = abs(BackFaces - BackFaces) + IntersectFaces * 6;
should be:
int Test = abs(BackFaces - FrontFaces) + IntersectFaces * 6;
i guess?
Otherwise this is a rather complex matter to debug by reading code... I suggest you try to eliminate as many error sources as possible and see if it still crashes. For example by selecting the first available polygon as a splitter.
It could also be worth while trying to build a simple scene that crash your engine and try to debug it.
Regards,
hObbE
this row seems fishy:
int Test = abs(BackFaces - BackFaces) + IntersectFaces * 6;
should be:
int Test = abs(BackFaces - FrontFaces) + IntersectFaces * 6;
i guess?
Otherwise this is a rather complex matter to debug by reading code... I suggest you try to eliminate as many error sources as possible and see if it still crashes. For example by selecting the first available polygon as a splitter.
It could also be worth while trying to build a simple scene that crash your engine and try to debug it.
Regards,
hObbE
Author
i already tried that if u dt find any splitter just assign the 1st face u find that has never been used as splitter and set it to be the splitter.
the pvs will just run and give me some memory error (which means are faces have been used as splitters yet the loop is still called and the recursivity is never returned) :S this is very sucky and i m trying to c maybe pvs algorithm demands some special looking areas to be rendered or someth. :(
btw 10x ofr that BackFaces thing i fixed it :P
the pvs will just run and give me some memory error (which means are faces have been used as splitters yet the loop is still called and the recursivity is never returned) :S this is very sucky and i m trying to c maybe pvs algorithm demands some special looking areas to be rendered or someth. :(
btw 10x ofr that BackFaces thing i fixed it :P
I think whats happening is once you've run out of splitting planes, it will just keep doing 'continue;' in the for loop. So no splitting plane will be set, the pointer points to garbage or nothing. I think you need to have something to return NULL if all splitting planes are used, then you can check if it has returned NULL and do whatever you want to happen when there are nor more planes.
Author
the problem with the pvs:
i am choosing the splitter and then i am trying to split the faces into front and back faces.
the splitting of faces is where the problem is occuring. when you try to classify the face relatively to the splitter you classify the 3 vertices belonging to the face and then make conclusions about the position of the face relative to the splitter. if the 3 vertices belong to the plane of the splitter then the face is parrallel, all to the front then the face is to the front, all to the back then the face is to the back, front and back then the face must be split. the classification of the vertices is the dotproduct between the normal of the splitter and the vector from any vertex of the splitter to the vertex we are considering. I am using an epsilon value to avoid comparison with 0. if the dotproduct is greater than the epsilon(0.0005f) then it is on the front, if it is less than -epsi then it is on the back else it intersect. after i classify the face if it is parrellel to the splitter i must add it to the front or the back list depending on whether the normal of the face is the same as the one of the splitter or if it is opposite to the one of the splitter. this is basically a dotproduct test.
the error is: i classify the vertices and i get that all 3 belong to the plane of the splitter; which is not accurate since the face is actually in front of the splitter but the dotproduct value is less than epsilon. so i figured that the next step which means classifying the normal of the face with the normal of the splitter will solve it but this also does not work for a good reason: the normals of the face and splitter are perpendicular to each other and the dotproduct that it gives me can be a very very small negative value which will add the face to the back list (i will include a picture of the case i am talking about). the problem is not as much from the second test as it is from the first test which is failing to appropriately classify the faces. this is occuring when the 2 faces are perpendicular (or nearly) and one of the faces is very very small look for the picture for details it will clarrify everything.
Picture:
http://www.2and2.net/Uploads/Images/bspprob001.PNG
i am choosing the splitter and then i am trying to split the faces into front and back faces.
the splitting of faces is where the problem is occuring. when you try to classify the face relatively to the splitter you classify the 3 vertices belonging to the face and then make conclusions about the position of the face relative to the splitter. if the 3 vertices belong to the plane of the splitter then the face is parrallel, all to the front then the face is to the front, all to the back then the face is to the back, front and back then the face must be split. the classification of the vertices is the dotproduct between the normal of the splitter and the vector from any vertex of the splitter to the vertex we are considering. I am using an epsilon value to avoid comparison with 0. if the dotproduct is greater than the epsilon(0.0005f) then it is on the front, if it is less than -epsi then it is on the back else it intersect. after i classify the face if it is parrellel to the splitter i must add it to the front or the back list depending on whether the normal of the face is the same as the one of the splitter or if it is opposite to the one of the splitter. this is basically a dotproduct test.
the error is: i classify the vertices and i get that all 3 belong to the plane of the splitter; which is not accurate since the face is actually in front of the splitter but the dotproduct value is less than epsilon. so i figured that the next step which means classifying the normal of the face with the normal of the splitter will solve it but this also does not work for a good reason: the normals of the face and splitter are perpendicular to each other and the dotproduct that it gives me can be a very very small negative value which will add the face to the back list (i will include a picture of the case i am talking about). the problem is not as much from the second test as it is from the first test which is failing to appropriately classify the faces. this is occuring when the 2 faces are perpendicular (or nearly) and one of the faces is very very small look for the picture for details it will clarrify everything.
Picture:
http://www.2and2.net/Uploads/Images/bspprob001.PNG
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
