MantisBT - VTK
View Issue Details
IDProjectCategoryView StatusDate SubmittedLast Update
0011988VTK(No Category)public2011-03-18 17:562016-08-12 09:55
ReporterRonald Römer 
Assigned ToWill Schroeder 
PrioritynormalSeverityminorReproducibilityalways
StatusclosedResolutionmoved 
PlatformOSOS Version
Product Version 
Target VersionFixed in Version 
ProjectTBD
Typeincorrect functionality
Summary0011988: vtkPolygon::ComputeNormal returns wrong directed normal if polygon has more concave than convex vertices
DescriptionHello,

the methods in vtkPolygon that are purposed for computing the normal of a polygon does not work, if the polygon has more concave than convex vertices. The normal there is an average from all cross-products, that cause a wrong sign of the normal. In Graphics Gems III there is an interesting method from Nevell, that should replace the actual versions of ComputeNormal. A lite version, without optimation for triangles, I provide below:

void ComputeNormal(vtkPoints *pts, vtkIdList *poly, double *n) {
  n[0] = 0; n[1] = 0; n[2] = 0;
  double pt0[3], pt1[3];

  pts->GetPoint(poly->GetId(0), pt0);
  
  unsigned int nbr = poly->GetNumberOfIds();

  for(unsigned int i = 0; i < nbr; i++) {
    pts->GetPoint(poly->GetId((i+1)%nbr), pt1);
  
    n[0] += (pt0[1]-pt1[1])*(pt0[2]+pt1[2]);
    n[1] += (pt0[2]-pt1[2])*(pt0[0]+pt1[0]);
    n[2] += (pt0[0]-pt1[0])*(pt0[1]+pt1[1]);
    
    pt0[0] = pt1[0];
    pt0[1] = pt1[1];
    pt0[2] = pt1[2];
    
  }
  
  vtkMath::Normalize(n);
}
Steps To Reproduce
Additional Information
TagsComputeNormal, concave vertices, normal of polygon, vtkPolygon
Relationships
Attached Files? a.vtk (672) 2013-09-12 17:28
https://www.vtk.org/Bug/file/9521/a.vtk
cxx test.cxx (2,056) 2013-09-12 17:29
https://www.vtk.org/Bug/file/9522/test.cxx
cxx TestComputeNormal.cxx (2,567) 2014-10-09 16:59
https://www.vtk.org/Bug/file/9750/TestComputeNormal.cxx
? polygon.vtk (6,608) 2015-07-20 17:02
https://www.vtk.org/Bug/file/9854/polygon.vtk
txt CMakeLists.txt (346) 2015-07-20 17:05
https://www.vtk.org/Bug/file/9855/CMakeLists.txt
Issue History
Date ModifiedUsernameFieldChange
2011-03-18 17:56Ronald RömerNew Issue
2011-03-18 19:05Ronald RömerTag Attached: ComputeNormal
2011-03-18 19:05Ronald RömerTag Attached: concave vertices
2011-03-18 19:05Ronald RömerTag Attached: normal
2011-03-18 19:05Ronald RömerTag Attached: vtkPolygon
2011-03-18 19:05Ronald RömerTag Detached: normal
2011-03-18 19:05Ronald RömerTag Attached: normal of polygon
2013-06-05 15:40Jean-Christophe Fillion-RobinNote Added: 0030912
2013-07-22 18:35Dave DeMarleNote Added: 0031198
2013-07-22 18:35Dave DeMarleStatusbacklog => expired
2013-07-22 18:35Dave DeMarleAssigned To => Dave DeMarle
2013-09-12 17:28Ronald RömerFile Added: a.vtk
2013-09-12 17:29Ronald RömerFile Added: test.cxx
2013-09-12 17:38Ronald RömerNote Added: 0031567
2013-09-12 17:40Ronald RömerNote Edited: 0031567bug_revision_view_page.php?bugnote_id=31567#r653
2013-12-11 15:59Ronald RömerStatusexpired => backlog
2013-12-11 15:59Ronald RömerResolutionopen => reopened
2014-09-30 10:56Dave DeMarleProject => TBD
2014-09-30 10:56Dave DeMarleType => incorrect functionality
2014-09-30 10:56Dave DeMarleAssigned ToDave DeMarle =>
2014-10-02 09:42Will SchroederAssigned To => Will Schroeder
2014-10-08 08:34Will SchroederNote Added: 0033617
2014-10-08 08:34Will SchroederStatusbacklog => active development
2014-10-09 16:58Will SchroederNote Added: 0033620
2014-10-09 16:58Will SchroederStatusactive development => closed
2014-10-09 16:58Will SchroederResolutionreopened => fixed
2014-10-09 16:58Will SchroederNote Edited: 0033620bug_revision_view_page.php?bugnote_id=33620#r878
2014-10-09 16:59Will SchroederFile Added: TestComputeNormal.cxx
2015-07-20 17:01David GobbiNote Added: 0034811
2015-07-20 17:01David GobbiStatusclosed => backlog
2015-07-20 17:01David GobbiResolutionfixed => reopened
2015-07-20 17:02David GobbiFile Added: polygon.vtk
2015-07-20 17:05David GobbiFile Added: CMakeLists.txt
2016-08-12 09:55Kitware RobotNote Added: 0037226
2016-08-12 09:55Kitware RobotStatusbacklog => closed
2016-08-12 09:55Kitware RobotResolutionreopened => moved

Notes
(0030912)
Jean-Christophe Fillion-Robin   
2013-06-05 15:40   
Does the problem still occur with VTK 5.10 ? VTK 6 ?

Would be great if you could submit a patch using Gerrit. For more details see http://www.vtk.org/Wiki/VTK/Git/Develop [^]

Thanks
Jc
(0031198)
Dave DeMarle   
2013-07-22 18:35   
If the bug is still present in 6.0.0, please reopen this report.
(0031567)
Ronald Römer   
2013-09-12 17:38   
(edited on: 2013-09-12 17:40)
I figured out, that the current ComputeNormal-function also returns a wrong result when the polygon has more convex than concave vertices. Look at my attachments... The Error is much bigger, than my version of ComputeNormal (I'm not the inventor!). Here is the output of the compiled test.cxx:

-0.252643, -0.00068456, 0.967559
0.248688, -1.59333e-06, -0.968584
-0.00107443
2.61958e-06
(0033617)
Will Schroeder   
2014-10-08 08:34   
Looking into issue
(0033620)
Will Schroeder   
2014-10-09 16:58   
The example polygon loop provided is non-planar. Newells method, etc. and other methods assume that the polygon points lie in a plane. Also by selecting points that are very close together the numerics can be jiggered enough to cause strange behavior.

This is easy to see by computing distance to plane (see attached file TestComputeNormal.cxx).
(0034811)
David Gobbi   
2015-07-20 17:01   
I believe that the algorithm that vtkpolygon uses to compute the normal is, in fact, coded incorrectly. See the attached data set "polygon.vtk", which is planar but which causes TestComputeNormal.cxx to fail.
(0037226)
Kitware Robot   
2016-08-12 09:55   
Resolving issue as `moved`.

This issue tracker is no longer used. Further discussion of this issue may take place in the current VTK Issues page linked in the banner at the top of this page.