[vtkusers] vtkIntersectionPolyDataFilter::TriangleTriangleIntersection corrupts the stack?
Cory Quammen
cquammen at cs.unc.edu
Fri Oct 5 15:48:54 EDT 2012
James,
I've posted a patch on the gerrit review system here:
http://review.source.kitware.com/#/c/7763/
If you wouldn't mind, could you register on gerrit and give the patch a review?
Additional instructions for VTK development that may be useful are posted here:
http://www.vtk.org/Wiki/VTK/Git
Thanks,
Cory
On Fri, Oct 5, 2012 at 11:41 AM, James Johnston <JamesJ at motionview3d.com> wrote:
>> -----Original Message-----
>> From: Cory Quammen [mailto:cquammen at cs.unc.edu]
>> Sent: Thursday, October 04, 2012 20:19
>> To: James Johnston
>> Cc: vtkusers at vtk.org
>> Subject: Re: [vtkusers]
>> vtkIntersectionPolyDataFilter::TriangleTriangleIntersection corrupts the
> stack?
>>
>> Hi James,
>>
>> I'm the author of this code. If you are interested in understanding the
> algorithm
>> more, please see Section 11.5.4 on pages 539-542 in
>>
>> Schnieder and Eberly, Geometric Tools for Computer Graphics, Morgan
>> Kaufman
>>
>> I plotted your triangles in ParaView and they do not appear to intersect,
> but
>> rather share a vertex. Perhaps the line of intersection between the two
> planes
>> in which the triangles lie lines up with one of the edges. The three
> edge/plane
>> intersection tests could then all pass, causing overflow in the t1 and t2
>> variables.
>
> Thanks for the response. Apparently so. They do indeed share a vertex and
> I'm sure you noticed that the triangles are also nearly coplanar (or
> coplanar I guess, depending on your precision).
>
>>
>> I think the right thing to do would be to increase the size of t1 and
>> t2 to 3 to avoid the stack overflow. Further down in the code, index1 and
> index2
>> are checked to see if they are equal to 2. If not, the triangle/triangle
>> intersection would report that the triangles don't intersec, which seems
>> reasonable to me.
>>
>> A more robust function would return a poly data that would contain a line
>> segment for triangles that overlap nicely, a single vertex if the
> triangles share a
>> vertex, or several triangles if the triangles overlap and are co-planar.
>> Unfortunately, I don't have the time to write that.
>
> Indeed, that would be most ideal. Unfortunately, I don't have time to write
> that for now at this point, either. The main thing I'm focusing on finding
> is the common case of triangles which intersect and don't share
> edges/vertices and are not coplanar. But it seems my data would make the
> algorithm exhibit undefined behavior (stack corruption).
>
> As you indicated in your paper (which I skimmed through), there is a good
> bit more future work to be done in this area for handling special cases like
> coplanar triangles.
>
> For now, I would want the function to not crash and return *relatively* sane
> results. I say relatively since you already described the ideal. For the
> time being, I would think a patch to at least fix the crash would be
> sufficient.
>
>>
>> Thoughts?
>>
>> Cory
>>
>>
>>
>> On Tue, Oct 2, 2012 at 12:24 PM, James Johnston
>> <JamesJ at motionview3d.com> wrote:
>> > Hi,
>> >
>> > I'm trying to find triangle-triangle intersection and I think
>> > vtkIntersectionPolyDataFilter::TriangleTriangleIntersection will work
>> > for me. Unfortunately, I *think* this function contains a bug. I
>> > just don't know the algorithms in that function well enough to say
>> > what the exact problem is or what the fix should be - I'm just trying to
> use the
>> function.
>> > I assume there aren't any bugs in my code - but if there are,
>> > hopefully someone can point them out!
>> >
>> > Trivial code that causes crash:
>> >
>> > int coplanar;
>> > double isectpt1[3], isectpt2[3];
>> > double thisCellTri[9] = {-30.121610641479492,
>> > 29.366317749023438, -27.164772033691406, -29.923696517944336,
>> > 29.366317749023438, -27.334911346435547, -30.055425643920898,
>> > 28.556877136230469, -27.227336883544922};
>> > double otherCellTri[9] = {-29.923696517944336,
>> > 29.366317749023438, -27.334911346435547, -29.858596801757812,
>> > 29.366317749023438, -27.390081405639648, -29.813289642333984,
>> > 27.682807922363281, -27.436887741088867};
>> >
>> > vtkIntersectionPolyDataFilter::TriangleTriangleIntersection(&thisCellT
>> > ri[0], &thisCellTri[3], &thisCellTri[6], &otherCellTri[0],
>> > &otherCellTri[3], &otherCellTri[6],
>> > coplanar, isectpt1, isectpt2);
>> >
>> > This causes TriangleTriangleIntersection to corrupt the stack. The
>> > offending section of code inside TriangleTriangleIntersection is as
> follows:
>> >
>> > int index1 = 0, index2 = 0;
>> > double t1[2], t2[2];
>> > for (int i = 0; i < 3; i++)
>> > {
>> > double t, x[3];
>> > int id1 = i, id2 = (i+1) % 3;
>> >
>> > // Find t coordinate on line of intersection between two planes.
>> > if (vtkPlane::IntersectWithLine( pts1[id1], pts1[id2], n2, p2, t, x
> ))
>> > {
>> > t1[index1++] = vtkMath::Dot(x, v) - vtkMath::Dot(p, v);
>> > }
>> >
>> > if (vtkPlane::IntersectWithLine( pts2[id1], pts2[id2], n1, p1, t, x
> ))
>> > {
>> > t2[index2++] = vtkMath::Dot(x, v) - vtkMath::Dot(p, v);
>> > }
>> > }
>> >
>> > I've verified that the first " vtkPlane::IntersectWithLine( pts1[id1],
>> > pts1[id2], n2, p2, t, x )" condition is evaluating to true all three
> times.
>> > This causes the loop to attempt to write to t1[2], which is
>> > out-of-bounds and therefore corrupts the stack (detected by MSVC debug
>> > build). I don't want to just change the declaration of t1 and t2 to
>> > hold 3 elements instead of 2, because the rest of the code doesn't
>> > seem to reference a third element. It would fix the stack corruption
>> > but probably just mask the real issue.
>> >
>> > This is tested on VTK 5.10.0. However, I assume the latest version on
>> > master branch contains the same issue, because Git history shows that
>> > nobody has made any meaningful changes to
>> > vtkIntersectionPolyDataFilter.cxx. (Just a few changes for VTK6 and
>> > to fix an implicit double-to-int compiler warning).
>> >
>> > Ideas?
>> >
>> > Best regards,
>> >
>> > James Johnston
>
> _______________________________________________
> Powered by www.kitware.com
>
> Visit other Kitware open-source projects at http://www.kitware.com/opensource/opensource.html
>
> Please keep messages on-topic and check the VTK FAQ at: http://www.vtk.org/Wiki/VTK_FAQ
>
> Follow this link to subscribe/unsubscribe:
> http://www.vtk.org/mailman/listinfo/vtkusers
--
Cory Quammen
Research Associate
Department of Computer Science
The University of North Carolina at Chapel Hill
More information about the vtkusers
mailing list