在某些情况下，陷入“死循环”的方法“TFGBSPNode.PerformSplit”会导致“堆栈溢出”异常。我跟踪了源代码，发现方法“TFGBSPNode.FindSplitPlane”总是得到相同的值......
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;
闲置的数据会将“PerformSplit”陷入无限循环。它看起来像一个斜坡。
(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)
我已经上传了一个[demo]：https ://sourceforge.net/apps/phpbb/glscene/download/file.php?id=387&sid=730698aae61c17e76802714334745f04来重现这个问题。在演示中，文件“MO.glsm”由两个从 TGLExtrusionSolid 对象翻译而来的 MeshObject 组成。
提前感谢您的任何建议。
谢谢大家。问题解决了。答案如下： VectorGeometry.pass 中的函数“CalcPlaneNormal”返回一个不正确的法线，bcoz Vertexs 的值和上面一样很大。例如，法线将是“CalcPlaneNormal”计算的“13119570882.098259961”，而这里会发生舍入问题......所以我将大坐标值转换为小坐标值。异常消失了。