← Back to branch summary

~ubuntu-branches/ubuntu/utopic/slic3r/utopic

« back to all changes in this revision

Viewing changes to xs/src/poly2tri/sweep/sweep_context.cc

  • Committer: Package Import Robot
  • Author(s): Chow Loong Jin
  • Date: 2014-06-17 01:27:26 UTC
  • Revision ID: package-import@ubuntu.com-20140617012726-2wrs4zdo251nr4vg
Tags: upstream-1.1.4+dfsg
Import upstream version 1.1.4+dfsg

Show diffs side-by-side

added added

removed removed

Lines of Context:
xs/src/poly2tri/sweep/sweep_context.cc
 
1
/*
 
2
 * Poly2Tri Copyright (c) 2009-2010, Poly2Tri Contributors
 
3
 * http://code.google.com/p/poly2tri/
 
4
 *
 
5
 * All rights reserved.
 
6
 *
 
7
 * Redistribution and use in source and binary forms, with or without modification,
 
8
 * are permitted provided that the following conditions are met:
 
9
 *
 
10
 * * Redistributions of source code must retain the above copyright notice,
 
11
 *   this list of conditions and the following disclaimer.
 
12
 * * Redistributions in binary form must reproduce the above copyright notice,
 
13
 *   this list of conditions and the following disclaimer in the documentation
 
14
 *   and/or other materials provided with the distribution.
 
15
 * * Neither the name of Poly2Tri nor the names of its contributors may be
 
16
 *   used to endorse or promote products derived from this software without specific
 
17
 *   prior written permission.
 
18
 *
 
19
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
 
20
 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
 
21
 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
 
22
 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR
 
23
 * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
 
24
 * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
 
25
 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
 
26
 * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
 
27
 * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
 
28
 * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
 
29
 * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 
30
 */
 
31
#include "sweep_context.h"
 
32
#include <algorithm>
 
33
#include "advancing_front.h"
 
34
 
 
35
namespace p2t {
 
36
 
 
37
SweepContext::SweepContext(const std::vector<Point*>& polyline) : points_(polyline),
 
38
  front_(0),
 
39
  head_(0),
 
40
  tail_(0),
 
41
  af_head_(0),
 
42
  af_middle_(0),
 
43
  af_tail_(0)
 
44
{
 
45
  InitEdges(points_);
 
46
}
 
47
 
 
48
void SweepContext::AddHole(const std::vector<Point*>& polyline)
 
49
{
 
50
  InitEdges(polyline);
 
51
  for(unsigned int i = 0; i < polyline.size(); i++) {
 
52
    points_.push_back(polyline[i]);
 
53
  }
 
54
}
 
55
 
 
56
void SweepContext::AddPoint(Point* point) {
 
57
  points_.push_back(point);
 
58
}
 
59
 
 
60
std::vector<Triangle*> &SweepContext::GetTriangles()
 
61
{
 
62
  return triangles_;
 
63
}
 
64
 
 
65
std::list<Triangle*> &SweepContext::GetMap()
 
66
{
 
67
  return map_;
 
68
}
 
69
 
 
70
void SweepContext::InitTriangulation()
 
71
{
 
72
  double xmax(points_[0]->x), xmin(points_[0]->x);
 
73
  double ymax(points_[0]->y), ymin(points_[0]->y);
 
74
 
 
75
  // Calculate bounds.
 
76
  for (unsigned int i = 0; i < points_.size(); i++) {
 
77
    Point& p = *points_[i];
 
78
    if (p.x > xmax)
 
79
      xmax = p.x;
 
80
    if (p.x < xmin)
 
81
      xmin = p.x;
 
82
    if (p.y > ymax)
 
83
      ymax = p.y;
 
84
    if (p.y < ymin)
 
85
      ymin = p.y;
 
86
  }
 
87
 
 
88
  double dx = kAlpha * (xmax - xmin);
 
89
  double dy = kAlpha * (ymax - ymin);
 
90
  head_ = new Point(xmax + dx, ymin - dy);
 
91
  tail_ = new Point(xmin - dx, ymin - dy);
 
92
 
 
93
  // Sort points along y-axis
 
94
  std::sort(points_.begin(), points_.end(), cmp);
 
95
 
 
96
}
 
97
 
 
98
void SweepContext::InitEdges(const std::vector<Point*>& polyline)
 
99
{
 
100
  size_t num_points = polyline.size();
 
101
  for (size_t i = 0; i < num_points; i++) {
 
102
    size_t j = i < num_points - 1 ? i + 1 : 0;
 
103
    edge_list.push_back(new Edge(*polyline[i], *polyline[j]));
 
104
  }
 
105
}
 
106
 
 
107
Point* SweepContext::GetPoint(size_t index)
 
108
{
 
109
  return points_[index];
 
110
}
 
111
 
 
112
void SweepContext::AddToMap(Triangle* triangle)
 
113
{
 
114
  map_.push_back(triangle);
 
115
}
 
116
 
 
117
Node& SweepContext::LocateNode(const Point& point)
 
118
{
 
119
  // TODO implement search tree
 
120
  return *front_->LocateNode(point.x);
 
121
}
 
122
 
 
123
void SweepContext::CreateAdvancingFront(const std::vector<Node*>& nodes)
 
124
{
 
125
 
 
126
  (void) nodes;
 
127
  // Initial triangle
 
128
  Triangle* triangle = new Triangle(*points_[0], *tail_, *head_);
 
129
 
 
130
  map_.push_back(triangle);
 
131
 
 
132
  af_head_ = new Node(*triangle->GetPoint(1), *triangle);
 
133
  af_middle_ = new Node(*triangle->GetPoint(0), *triangle);
 
134
  af_tail_ = new Node(*triangle->GetPoint(2));
 
135
  front_ = new AdvancingFront(*af_head_, *af_tail_);
 
136
 
 
137
  // TODO: More intuitive if head is middles next and not previous?
 
138
  //       so swap head and tail
 
139
  af_head_->next = af_middle_;
 
140
  af_middle_->next = af_tail_;
 
141
  af_middle_->prev = af_head_;
 
142
  af_tail_->prev = af_middle_;
 
143
}
 
144
 
 
145
void SweepContext::RemoveNode(Node* node)
 
146
{
 
147
  delete node;
 
148
}
 
149
 
 
150
void SweepContext::MapTriangleToNodes(Triangle& t)
 
151
{
 
152
  for (int i = 0; i < 3; i++) {
 
153
    if (!t.GetNeighbor(i)) {
 
154
      Node* n = front_->LocatePoint(t.PointCW(*t.GetPoint(i)));
 
155
      if (n)
 
156
        n->triangle = &t;
 
157
    }
 
158
  }
 
159
}
 
160
 
 
161
void SweepContext::RemoveFromMap(Triangle* triangle)
 
162
{
 
163
  map_.remove(triangle);
 
164
}
 
165
 
 
166
void SweepContext::MeshClean(Triangle& triangle)
 
167
{
 
168
  std::vector<Triangle *> triangles;
 
169
  triangles.push_back(&triangle);
 
170
 
 
171
  while(!triangles.empty()){
 
172
        Triangle *t = triangles.back();
 
173
        triangles.pop_back();
 
174
 
 
175
    if (t != NULL && !t->IsInterior()) {
 
176
      t->IsInterior(true);
 
177
      triangles_.push_back(t);
 
178
      for (int i = 0; i < 3; i++) {
 
179
        if (!t->constrained_edge[i])
 
180
          triangles.push_back(t->GetNeighbor(i));
 
181
      }
 
182
    }
 
183
  }
 
184
}
 
185
 
 
186
SweepContext::~SweepContext()
 
187
{
 
188
 
 
189
    // Clean up memory
 
190
 
 
191
    delete head_;
 
192
    delete tail_;
 
193
    delete front_;
 
194
    delete af_head_;
 
195
    delete af_middle_;
 
196
    delete af_tail_;
 
197
 
 
198
    typedef std::list<Triangle*> type_list;
 
199
 
 
200
    for(type_list::iterator iter = map_.begin(); iter != map_.end(); ++iter) {
 
201
        Triangle* ptr = *iter;
 
202
        delete ptr;
 
203
    }
 
204
 
 
205
     for(unsigned int i = 0; i < edge_list.size(); i++) {
 
206
        delete edge_list[i];
 
207
    }
 
208
 
 
209
}
 
210
 
 
211
}