Triangulation of simple polygon fails


Procedural::Shape s = Procedural::Shape().addPoint(0, 0).addPoint(0, 5).addPoint(3, 4).addPoint(5, -4).close();
Procedural::Triangulator().setShapeToTriangulate(&s).realizeMesh("square");


Am I forgetting something perhaps? This does not seem to work even though I would expect it to.

Shapes have an "outside", and default is on the right.
That information is used by the triangulator to determine which triangles to remove at the end of the triangulation.
In your case, you defined your points clockwise, so the outside is on the left.

You have to use :
setOutSide(SIDE_LEFT)

If your shape is user provided and you don't have a clue if it's clockwise or anticlockwise, you may use findRealOutside.

Worked like a charm! Thank you! I have another issue you might be able to help me with though. With the following code


Procedural::Shape outerShape = Procedural::Shape().addPoint(0, 0).addPoint(0, 5).addPoint(3, 4).addPoint(5, -4).close();
outerShape.setOutSide(outerShape.findRealOutSide());
Procedural::Shape innerShape = Procedural::Shape().addPoint(1, 1).addPoint(2, 2).addPoint(2, 1).close();
innerShape.setOutSide(outerShape.findRealOutSide()).switchSide();
ms.addShape(outerShape);
ms.addShape(innerShape);
Procedural::Triangulator().setMultiShapeToTriangulate(&ms).realizeMesh("square");


I construct a 2D mesh. However, my data concerns 3 dimensional data. For now I simply did not use any of the depth information, first I wanted the triangulation to be done. Upon doing the triangulation I would like to add depth information, a Z coordinate for each point, and subsequently construct a mesh. Is this possible?

Do you mean you want to extrude your 2D shape to a 3D mesh? (if so, use the Extruder)

Or create a curved 2D surface?

If I understand extrusion correct (from the example), what I look for is a curved 2D surface Could that be done?

Alright, so I dug into the code a little bit, and I suppose I could obtain the result I like by running the triangulation obtain the result in a TriangleBuffer of my own, modify the vertices in this TriangleBuffer correctly and somehow create a new mesh out of the modified TriangleBuffer?

Alright, so I dug into the code a little bit, and I suppose I could obtain the result I like by running the triangulation obtain the result in a TriangleBuffer of my own, modify the vertices in this TriangleBuffer correctly and somehow create a new mesh out of the modified TriangleBuffer?
Yes, that's what I was about to suggest.

Wanted you to know, that did the trick! Solved my troubles yesterday
Of course I don't want to withhold my solution from you. Thanks for your support!


Procedural::Shape outerShape = getShape();
Procedural::MultiShape ms;
Procedural::TriangleBuffer triangleBuffer;
Procedural::Triangulator triangulator;

if (innerPolygons_.size() > 0)
{
// use a multishape to construct an entity
ms.addShape(outerShape);

for (unsigned int i = 0; i < innerPolygons_.size(); ++i)
{
// for inner shapes, we make sure we first set the correct origin,
// namely the origin (first point) of the outer shape
Procedural::Shape innerShape = innerPolygons_->createShape((*this)[0]);
// an inner shape, a hole, needs to be regarded inside out
ms.addShape(innerShape.switchSide());
}

triangulator.setMultiShapeToTriangulate(&ms);
}
else
triangulator.setShapeToTriangulate(&outerShape);

// perform triangulation and store the result in our buffer
triangulator.addToTriangleBuffer(triangleBuffer);
// fetch the reference to the vertices
std::vector<Procedural::TriangleBuffer::Vertex>& vertices = triangleBuffer.getVertices();

// we need to add the proper height depth information (z coordinate) to
// the obtained triangulation result
unsigned int vertexIndex = 0;
for (unsigned int i = 0; i < points(); ++i, ++vertexIndex)
vertices[vertexIndex].mPosition.z = (*this).z;
for (unsigned int i = 0; i < innerPolygons_.size(); ++i)
for (unsigned int j = 0; j < innerPolygons_->points(); ++j, ++vertexIndex)
vertices[vertexIndex].mPosition.z = innerPolygons_->getPoint(j).z;

entity_ = ogreSceneManager_.createEntity(triangleBuffer.transformToMesh(guid_));


Found another issue I have trouble finding a proper explanation for. Consider the following code:

Procedural::Shape s;

s.addPoint(0,0);
s.addPoint(11.6406,-1.40625);
s.addPoint(55.5625,-7.28125);
s.addPoint(57.0469,-9.25);
s.addPoint(58.125,-11.5);
s.addPoint(58.4531,-14.0938);
...
...
...
s.addPoint(-33.125,8.71875);
s.addPoint(-30.3594,7.34375);
s.addPoint(-27.2969,5.9375);
s.addPoint(-24.3906,4.90625);
s.addPoint(-20.5,3.84375);
s.addPoint(-12.9219,2.1875);
s.close();
s.setOutSide(Procedural::SIDE_LEFT);

Procedural::Triangulator triangulator;
triangulator.setShapeToTriangulate(&s);

Ogre::Entity* testEntity = ogreSceneManager_->createEntity(triangulator.realizeMesh());


I can construct a mesh out of the shape. However, I cannot seem to triangulate it. My application simply freezes upon calling triangulator.realizeMesh();. What could be the reason for this?

I would have attached it, but .txt is apparently not an acceptable attachment file extension. Anyway, below you find all the polygon coordinates:

0,0
11.6406,-1.40625
55.5625,-7.28125
57.0469,-9.25
58.125,-11.5
58.4531,-14.0938
46.9063,-92.0313
30.7656,-194.5
30.1719,-196.094
29.5781,-197.625
29.2344,-198.813
27.9688,-200.469
26.5781,-201.781
24.75,-202.938
23.0938,-204
21.625,-204.875
19.75,-205.875
18.1563,-206.75
14.4063,-205.625
14.2344,-205.469
9.85938,-201.938
9.0625,-201.281
8.625,-200.625
8.01563,-199
8.09375,-194.594
11.9063,-175.313
13.6406,-161.375
14.7031,-150.219
14.5156,-141.813
14.7969,-139.813
10.9688,-114.031
7.51563,-97.7813
4.07813,-81.8125
-2,-64.3438
-6.9375,-51.2813
-15.25,-36.0938
-23.0313,-23.125
-33.25,-9.625
-39.2969,-2.125
-48.1875,7.8125
-62.1406,20.9375
-80.3906,36.1875
-92.5313,46.0938
-101.344,53.6563
-113.828,65.6563
-120.953,72.875
-127.422,80.0938
-132.688,85.9063
-138.719,93.4375
-143.297,99.2188
-147.953,105.656
-151.719,111.156
-157.75,120.188
-163.016,129.438
-172.203,147.156
-175.75,154.688
-179.453,162.938
-181.844,168.375
-183.813,173.188
-187.094,184.063
-189.547,191.969
-191.875,199.063
-195.281,213.438
-197.609,222.5
-200.125,232.219
-202.516,241.781
-205.109,253.125
-209.672,274
-214.406,294.969
-216.75,304.875
-220.672,311.344
-220.844,312.281
-220.266,312.094
-220.063,311.969
-219.75,311.719
-219.484,311.531
-219.297,311.313
-219.141,311.031
-218.969,310.719
-218.813,310.438
-218.609,310
-218.391,309.656
-218.125,309.344
-217.813,308.969
-217.188,308.219
-216.891,307.938
-216.578,307.719
-215.453,307.031
-214.125,306.438
-212.375,305.75
-211.438,305.344
-210.547,304.469
-209.641,303.094
-209.016,301.781
-207.422,298.906
-209.219,294.094
-203,265.875
-197.109,241.094
-187.813,209.156
-177.734,173.375
-177.156,172.875
-176.203,172.313
-175.406,172.719
-174.781,173.656
-173.875,174.75
-168.313,180.469
-165.078,184.5
-161.141,191
-158.391,195.531
-151.328,211.313
-146.391,218.781
-144.359,223.219
-143.781,225.25
-143.422,227.25
-143.844,229.281
-144.547,232.125
-154.75,246.344
-170.203,272.25
-181.953,290.063
-196.672,308.906
-200.188,315.156
-201.844,316.813
-203.203,317.75
-204.453,318.156
-207.172,318.5
-209.656,318.5
-216.969,318.281
-221.391,318.125
-221.469,318.719
-217,318.813
-211.672,318.938
-203.188,319.281
-193.406,319.688
-180.688,320.125
-174.641,320.406
-174.563,320.438
-174.109,318.906
-172.875,315.375
-171.75,312.75
-170.563,310.25
-169.609,308.344
-168,306.094
-160.422,294.469
-152.953,283.563
-152.844,283.344
-145.297,272.188
-136.359,258.656
-134.859,256.219
-133.719,254.063
-133.203,252.906
-132.844,251.469
-132.609,250.313
-132.344,247.844
-132.438,242.594
-132.953,239.813
-134.797,234.594
-137.156,229.156
-139,225.656
-144.531,216.469
-148.109,210.719
-153.297,201.281
-156.563,195.344
-158.406,191.813
-160.625,187.063
-164.266,178.281
-166.625,171.656
-168.234,166.438
-169.156,162.156
-169.484,160.031
-169.609,158.313
-169.641,156.625
-169.438,155.469
-168.797,152.906
-167.375,148.813
-165.813,144.875
-163.984,140.719
-161.766,136.219
-159.266,131.469
-155.781,125.313
-153.141,120.844
-148.75,114.375
-146.188,110.406
-144.266,107.75
-142.141,104.625
-140.297,102.25
-137.516,98.5313
-134.328,94.4688
-130.75,90.3438
-127.516,86.5313
-120.516,79.0313
-112,70.75
-106.625,65.8125
-102.672,62.25
-91.0938,52.5313
-77.9219,41.8438
-62.2031,29.4375
-50.1094,20.4688
-41.9531,14.625
-40.5625,13.625
-36.875,11.0313
-33.125,8.71875
-30.3594,7.34375
-27.2969,5.9375
-24.3906,4.90625
-20.5,3.84375
-12.9219,2.1875
0,0


I reproduced your bug locally, but I don't know why the triangulator fails on that shape.
Added an item to my TODO list

Thanks for your response! I really appreciate your effort. If you do find the problem and are able to solve it, I am very much interested in a patch and some details on what caused the problem of course. Also, I might have a little contribution to your library in the future myself. I wanted to set the vertex colour of the vertices that are in a TriangleBuffer, I got that to work with a little work around. However, I thought I might simply propose a patch that makes this possible in a proper manner.