View Issue Details [ Jump to Notes ] [ Print ]
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 
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);
}
TagsComputeNormal, concave vertices, normal of polygon, vtkPolygon
ProjectTBD
Typeincorrect functionality
Attached Files? file icon a.vtk [^] (672 bytes) 2013-09-12 17:28
cxx file icon test.cxx [^] (2,056 bytes) 2013-09-12 17:29
cxx file icon TestComputeNormal.cxx [^] (2,567 bytes) 2014-10-09 16:59
? file icon polygon.vtk [^] (6,608 bytes) 2015-07-20 17:02
txt file icon CMakeLists.txt [^] (346 bytes) 2015-07-20 17:05 [Show Content]

 Relationships

  Notes
(0030912)
Jean-Christophe Fillion-Robin (manager)
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 (administrator)
2013-07-22 18:35

 If the bug is still present in 6.0.0, please reopen this report.
(0031567)
Ronald Römer (reporter)
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 (manager)
2014-10-08 08:34

 Looking into issue
(0033620)
Will Schroeder (manager)
2014-10-09 16:58
edited on: 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 (developer)
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 (administrator)
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.

 Issue History
Date Modified Username Field Change
2011-03-18 17:56 Ronald Römer New Issue
2011-03-18 19:05 Ronald Römer Tag Attached: ComputeNormal
2011-03-18 19:05 Ronald Römer Tag Attached: concave vertices
2011-03-18 19:05 Ronald Römer Tag Attached: normal
2011-03-18 19:05 Ronald Römer Tag Attached: vtkPolygon
2011-03-18 19:05 Ronald Römer Tag Detached: normal
2011-03-18 19:05 Ronald Römer Tag Attached: normal of polygon
2013-06-05 15:40 Jean-Christophe Fillion-Robin Note Added: 0030912
2013-07-22 18:35 Dave DeMarle Note Added: 0031198
2013-07-22 18:35 Dave DeMarle Status backlog => expired
2013-07-22 18:35 Dave DeMarle Assigned To => Dave DeMarle
2013-09-12 17:28 Ronald Römer File Added: a.vtk
2013-09-12 17:29 Ronald Römer File Added: test.cxx
2013-09-12 17:38 Ronald Römer Note Added: 0031567
2013-09-12 17:40 Ronald Römer Note Edited: 0031567
2013-12-11 15:59 Ronald Römer Status expired => backlog
2013-12-11 15:59 Ronald Römer Resolution open => reopened
2014-09-30 10:56 Dave DeMarle Project => TBD
2014-09-30 10:56 Dave DeMarle Type => incorrect functionality
2014-09-30 10:56 Dave DeMarle Assigned To Dave DeMarle =>
2014-10-02 09:42 Will Schroeder Assigned To => Will Schroeder
2014-10-08 08:34 Will Schroeder Note Added: 0033617
2014-10-08 08:34 Will Schroeder Status backlog => active development
2014-10-09 16:58 Will Schroeder Note Added: 0033620
2014-10-09 16:58 Will Schroeder Status active development => closed
2014-10-09 16:58 Will Schroeder Resolution reopened => fixed
2014-10-09 16:58 Will Schroeder Note Edited: 0033620
2014-10-09 16:59 Will Schroeder File Added: TestComputeNormal.cxx
2015-07-20 17:01 David Gobbi Note Added: 0034811
2015-07-20 17:01 David Gobbi Status closed => backlog
2015-07-20 17:01 David Gobbi Resolution fixed => reopened
2015-07-20 17:02 David Gobbi File Added: polygon.vtk
2015-07-20 17:05 David Gobbi File Added: CMakeLists.txt
2016-08-12 09:55 Kitware Robot Note Added: 0037226
2016-08-12 09:55 Kitware Robot Status backlog => closed
2016-08-12 09:55 Kitware Robot Resolution reopened => moved

Copyright © 2000 - 2018 MantisBT Team