Question

In some cases, the method "TFGBSPNode.PerformSplit" trapped into an "dead-loop" causes "stack overflow" exception. I have traced the source code and found that the method "TFGBSPNode.FindSplitPlane" always gets the same value...

unit unTest;    
interface    
uses
  Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,
  Dialogs, GLScene, GLVectorFileObjects, GLCoordinates, GLCrossPlatform,
  BaseClasses, GLWin32Viewer;    
type
  TForm1 = class(TForm)
    GLSceneViewer1: TGLSceneViewer;
    GLScene1: TGLScene;
    GLCamera1: TGLCamera;
    GLFreeForm1: TGLFreeForm;
    GLLightSource1: TGLLightSource;
    GLFreeForm2: TGLFreeForm;
    procedure FormCreate(Sender: TObject);
  end;
var
  Form1: TForm1;    
implementation
uses GLMeshCSG, GLMesh;
{$R *.dfm}

procedure TForm1.FormCreate(Sender: TObject);
var
  MO: TMeshObject;
begin
  GLFreeForm1.LoadFromFile('MO.glsm');
  MO := TMeshObject.CreateOwned(GLFreeForm2.MeshObjects);    
  CSG_Operation(GLFreeForm1.MeshObjects[0], GLFreeForm1.MeshObjects[1],
                CSG_Subtraction, MO, '', '');    
  GLFreeForm2.StructureChanged;
end;
end.
//the exception would be raised here
procedure TFGBSPNode.PerformSplit(const splitPlane : THmgPlane;
                                  const maxTrianglesPerLeaf : Integer = MaxInt);
var
   fgPos, fgNeg : TFGBSPNode;
   fgPosIndices, fgNegIndices : TIntegerList;
   indices : TIntegerList;

   procedure SplitTriangleMid(strayID, strayNext, strayPrev : Integer;
                              eNext, ePrev : Single);
   var
      iOpp : Integer;
      invSum : Single;
   begin
      invSum:=1/(Abs(eNext)+Abs(ePrev));
      iOpp:=AddLerp(strayNext, strayPrev, Abs(eNext)*invSum, Abs(ePrev)*invSum);
      if eNext>0 then begin
         fgPosIndices.Add(strayID, strayNext, iOpp);
         fgNegIndices.Add(iOpp, strayPrev, strayID);
      end else begin
         fgNegIndices.Add(strayID, strayNext, iOpp);
         fgPosIndices.Add(iOpp, strayPrev, strayID);
      end;
   end;

   procedure SplitTriangle(strayID, strayNext, strayPrev : Integer;
                           eStray, eNext, ePrev : Single);
   var
      iNext, iPrev : Integer;
      invSum : Single;
   begin
      invSum:=1/(Abs(eNext)+Abs(eStray));
      iNext:=AddLerp(strayNext, strayID, Abs(eNext)*invSum, Abs(eStray)*invSum);
      invSum:=1/(Abs(ePrev)+Abs(eStray));
      iPrev:=AddLerp(strayPrev, strayID, Abs(ePrev)*invSum, Abs(eStray)*invSum);
      if eStray>0 then begin
         fgPos.VertexIndices.Add(strayID, iNext, iPrev);
         fgNeg.VertexIndices.Add(strayNext, strayPrev, iPrev);
         fgNeg.VertexIndices.Add(iPrev, iNext, strayNext);
      end else if eStray<0 then begin
         fgNeg.VertexIndices.Add(strayID, iNext, iPrev);
         fgPos.VertexIndices.Add(strayNext, strayPrev, iPrev);
         fgPos.VertexIndices.Add(iPrev, iNext, strayNext);
      end;
   end;

var
   i, i1, i2, i3, se1, se2, se3 : Integer;
   e1, e2, e3 : Single;
   vertices : TAffineVectorList;
   subSplitPlane : THmgPlane;
begin
   Assert((PositiveSubNodeIndex=0) and (NegativeSubNodeIndex=0));
   ConvertToList;
   // prepare sub nodes
   FPositiveSubNodeIndex:=Owner.Count;
   fgPos:=TFGBSPNode.CreateOwned(Owner);
   fgPosIndices:=fgPos.VertexIndices;
   FNegativeSubNodeIndex:=Owner.Count;
   fgNeg:=TFGBSPNode.CreateOwned(Owner);
   fgNegIndices:=fgNeg.VertexIndices;
   // initiate split
   Self.FSplitPlane:=splitPlane;
   indices:=TIntegerList.Create;
   vertices:=Owner.Owner.Vertices;
   i:=0; while i<VertexIndices.Count do begin
      // evaluate all points
      i1:=VertexIndices[i];
      e1:=PlaneEvaluatePoint(splitPlane, vertices.List^[i1]);
      i2:=VertexIndices[i+1];
      e2:=PlaneEvaluatePoint(splitPlane, vertices.List^[i2]);
      i3:=VertexIndices[i+2];
      e3:=PlaneEvaluatePoint(splitPlane, vertices.List^[i3]);
      if Abs(e1)<cOwnTriangleEpsilon then begin
         e1:=0;
         se1:=0;
      end else se1:=Sign(e1);
      if Abs(e2)<cOwnTriangleEpsilon then begin
         e2:=0;
         se2:=0;
      end else se2:=Sign(e2);
      if Abs(e3)<cOwnTriangleEpsilon then begin
         e3:=0;
         se3:=0;
      end else se3:=Sign(e3);
      // case disjunction
      case se1 of
         -1 : case se2 of
            -1 : case se3 of
               -1, 0 : fgNegIndices.Add(i1, i2, i3);
               +1 : SplitTriangle(i3, i1, i2, e3, e1, e2);
            end;
            0 : case se3 of
               -1, 0 : fgNegIndices.Add(i1, i2, i3);
               +1 : SplitTriangleMid(i2, i3, i1, e3, e1);
            end;
            +1 : case se3 of
               -1 : SplitTriangle(i2, i3, i1, e2, e3, e1);
               0  : SplitTriangleMid(i3, i1, i2, e1, e2);
               +1 : SplitTriangle(i1, i2, i3, e1, e2, e3);
            end;
         end;
         0 : case se2 of
            -1 : case se3 of
               -1, 0 : fgNegIndices.Add(i1, i2, i3);
               +1 : SplitTriangleMid(i1, i2, i3, e2, e3);
            end;
            0 : case se3 of
               -1 : fgNegIndices.Add(i1, i2, i3);
               0  : indices.Add(i1, i2, i3);
               +1 : fgPosIndices.Add(i1, i2, i3);
            end;
            +1 : case se3 of
               -1 : SplitTriangleMid(i1, i2, i3, e2, e3);
               0, +1 : fgPosIndices.Add(i1, i2, i3);
            end;
         end;
         +1 : case se2 of
            -1 : case se3 of
               -1 : SplitTriangle(i1, i2, i3, e1, e2, e3);
               0  : SplitTriangleMid(i3, i1, i2, e1, e2);
               +1 : SplitTriangle(i2, i3, i1, e2, e3, e1);
            end;
            0 : case se3 of
               -1 : SplitTriangleMid(i2, i3, i1, e3, e1);
               0, +1 : fgPosIndices.Add(i1, i2, i3);
            end;
            +1 : case se3 of
               -1 : SplitTriangle(i3, i1, i2, e3, e1, e2);
               0, +1 : fgPosIndices.Add(i1, i2, i3);
            end;
         end;
      end;
      Inc(i, 3);
   end;
   VertexIndices:=indices;
   indices.Free;
   if fgPos.TriangleCount=0 then begin
      FPositiveSubNodeIndex:=0;
      FNegativeSubNodeIndex:=FNegativeSubNodeIndex-1;
      FreeAndNil(fgPos);
   end;
   if fgNeg.TriangleCount=0 then begin
      FNegativeSubNodeIndex:=0;
      FreeAndNil(fgNeg);
   end;
   if Assigned(fgPos) and (fgPos.TriangleCount>maxTrianglesPerLeaf) then begin
      subSplitPlane:=fgPos.FindSplitPlane;//in some case, "FindSplitPlane" always get the same value
      fgPos.PerformSplit(subSplitPlane, maxTrianglesPerLeaf);
   end;
   if Assigned(fgNeg) and (fgNeg.TriangleCount>maxTrianglesPerLeaf) then begin
      subSplitPlane:=fgNeg.FindSplitPlane;//in some case, "FindSplitPlane" always get the same value
      fgNeg.PerformSplit(subSplitPlane, maxTrianglesPerLeaf);
   end;
end;

function TFGBSPNode.FindSplitPlane(triangleSplitCost : Single = 1;
                                   triangleImbalanceCost : Single = 0.5) : THmgPlane;
var
   i, k, n : Integer;
   ns, np, nn : Integer;
   evalPlane : THmgPlane;
   bestEval, eval : Single;
   vertices : TAffineVectorList;
begin
   Result:=NullHmgVector;
   bestEval:=1e30;
   n:=VertexIndices.Count;
   vertices:=Owner.Owner.Vertices;
   if n>0 then for k:=0 to n div 4 do begin
      case Mode of
         fgmmTriangles, fgmmFlatTriangles : begin
            i:=Random((n div 3)-1)*3;
            evalPlane:=PlaneMake(vertices[VertexIndices[i]],
                                 vertices[VertexIndices[i+1]],
                                 vertices[VertexIndices[i+2]]);
         end;
         fgmmTriangleStrip : begin
            i:=Random(n-2);
            evalPlane:=PlaneMake(vertices[VertexIndices[i]],
                                 vertices[VertexIndices[i+1]],
                                 vertices[VertexIndices[i+2]]);
         end;
      else
         // fgmmTriangleFan
         i:=Random(n-2);
         evalPlane:=PlaneMake(vertices[VertexIndices[0]],
                              vertices[VertexIndices[i]],
                              vertices[VertexIndices[i+1]]);
      end;
      EvaluateSplitPlane(evalPlane, ns, np, nn);
      eval:=ns*triangleSplitCost+Abs(np-nn)*0.5*triangleImbalanceCost;
      if eval<bestEval then begin
         bestEval:=eval;
         Result:=evalPlane;
      end;
   end;
end;

The fallowing Data would trap "PerformSplit" into a infinite recusion. It looks like a incline.

(7009.6484375, 17768.642578, -3770.213623) (3504.8242188, 17524.121094, -3770.213623) (7009.6484375, 17768.642578, -2970.2131348)

(7009.6484375, 17768.642578, -2970.2131348) (3504.8242188, 17524.121094, -3770.213623) (3504.8242188, 17524.121094, -2970.2131348)

I have uploaded a [demo]:https://sourceforge.net/apps/phpbb/glscene/download/file.php?id=387&sid=730698aae61c17e76802714334745f04 to reproduce the problem. In the demo , the file "MO.glsm" is made up of two MeshObjects translated from TGLExtrusionSolid Object.

Thanks in advance for any suggestion.

Thanks all. The problem was solved. The Answer as follow: The function "CalcPlaneNormal" in VectorGeometry.pas returns an incorrect Normal, bcoz Vertexs value is very large as above. E.g, the normal would be "13119570882.098259961" calculated by "CalcPlaneNormal", and the rounding issue would happen here... so I translated the big coordinate value to a small coordinate value. And the exception has gone.

No correct solution

OTHER TIPS

I don't think this is going to be simple to remedy. I don't have GLScene installed to run your test program but looking at the code above it seems that PerformSplit is a recursive algorithm that I can only guess is failing to effectively handle whatever geometry is in your mesh object. I would probably submit this as a bug report here (or here) to whomever is maintaining GLScene.

Licensed under: CC-BY-SA with attribution
Not affiliated with StackOverflow
scroll top