← Back to branch summary

~siretart/ubuntu/utopic/blender/libav10

« back to all changes in this revision

Viewing changes to extern/carve/lib/intersect_group.cpp

  • Committer: Package Import Robot
  • Author(s): Matteo F. Vescovi
  • Date: 2012-07-23 08:54:18 UTC
  • mfrom: (14.2.16 sid)
  • mto: (14.2.19 sid)
  • mto: This revision was merged to the branch mainline in revision 42.
  • Revision ID: package-import@ubuntu.com-20120723085418-9foz30v6afaf5ffs
Tags: 2.63a-2
http://bugs.debian.org/658075
* debian/: Cycles support added (Closes: #658075)
  For now, this top feature has been enabled only
  on [any-amd64 any-i386] architectures because
  of OpenImageIO failing on all others
* debian/: scripts installation path changed
  from /usr/lib to /usr/share:
  + debian/patches/: patchset re-worked for path changing
  + debian/control: "Breaks" field added on yafaray-exporter

Show diffs side-by-side

added added

removed removed

Lines of Context:
extern/carve/lib/intersect_group.cpp
 
1
// Begin License:
 
2
// Copyright (C) 2006-2011 Tobias Sargeant (tobias.sargeant@gmail.com).
 
3
// All rights reserved.
 
4
//
 
5
// This file is part of the Carve CSG Library (http://carve-csg.com/)
 
6
//
 
7
// This file may be used under the terms of the GNU General Public
 
8
// License version 2.0 as published by the Free Software Foundation
 
9
// and appearing in the file LICENSE.GPL2 included in the packaging of
 
10
// this file.
 
11
//
 
12
// This file is provided "AS IS" with NO WARRANTY OF ANY KIND,
 
13
// INCLUDING THE WARRANTIES OF DESIGN, MERCHANTABILITY AND FITNESS FOR
 
14
// A PARTICULAR PURPOSE.
 
15
// End:
 
16
 
 
17
 
 
18
#if defined(HAVE_CONFIG_H)
 
19
#  include <carve_config.h>
 
20
#endif
 
21
 
 
22
#include <carve/csg.hpp>
 
23
#include <carve/timing.hpp>
 
24
 
 
25
#include "csg_detail.hpp"
 
26
#include "intersect_common.hpp"
 
27
 
 
28
void carve::csg::CSG::makeEdgeMap(const carve::csg::FaceLoopList &loops,
 
29
                                  size_t edge_count,
 
30
                                  detail::LoopEdges &edge_map) {
 
31
#if defined(UNORDERED_COLLECTIONS_SUPPORT_RESIZE)
 
32
  edge_map.resize(edge_count);
 
33
#endif
 
34
 
 
35
  for (carve::csg::FaceLoop *i = loops.head; i; i = i->next) {
 
36
    edge_map.addFaceLoop(i);
 
37
    i->group = NULL;
 
38
  }
 
39
}
 
40
 
 
41
#include <carve/polyline.hpp>
 
42
 
 
43
#if defined(CARVE_DEBUG_WRITE_PLY_DATA)
 
44
void writePLY(const std::string &out_file, const carve::mesh::MeshSet<3> *poly, bool ascii);
 
45
void writePLY(const std::string &out_file, const carve::line::PolylineSet *lines, bool ascii);
 
46
#endif
 
47
 
 
48
void carve::csg::CSG::findSharedEdges(const detail::LoopEdges &edge_map_a,
 
49
                                      const detail::LoopEdges &edge_map_b,
 
50
                                      V2Set &shared_edges) {
 
51
  for (detail::LoopEdges::const_iterator
 
52
         i = edge_map_a.begin(), e = edge_map_a.end();
 
53
       i != e;
 
54
       ++i) {
 
55
    detail::LoopEdges::const_iterator j = edge_map_b.find((*i).first);
 
56
    if (j != edge_map_b.end()) {
 
57
      shared_edges.insert((*i).first);
 
58
    }
 
59
  }
 
60
 
 
61
#if defined(CARVE_DEBUG)
 
62
  detail::VVSMap edge_graph;
 
63
 
 
64
  for (V2Set::const_iterator i = shared_edges.begin(); i != shared_edges.end(); ++i) {
 
65
    edge_graph[(*i).first].insert((*i).second);
 
66
    edge_graph[(*i).second].insert((*i).first);
 
67
  }
 
68
 
 
69
  std::cerr << "*** testing consistency of edge graph" << std::endl;
 
70
  for (detail::VVSMap::const_iterator i = edge_graph.begin(); i != edge_graph.end(); ++i) {
 
71
    if ((*i).second.size() > 2) {
 
72
      std::cerr << "branch at: " << (*i).first << std::endl;
 
73
    }
 
74
    if ((*i).second.size() == 1) {
 
75
      std::cerr << "endpoint at: " << (*i).first << std::endl;
 
76
      std::cerr << "coordinate: " << (*i).first->v << std::endl;
 
77
    }
 
78
  }
 
79
 
 
80
  {
 
81
    carve::line::PolylineSet intersection_graph;
 
82
    intersection_graph.vertices.resize(edge_graph.size());
 
83
    std::map<const carve::mesh::MeshSet<3>::vertex_t *, size_t> vmap;
 
84
 
 
85
    size_t j = 0;
 
86
    for (detail::VVSMap::const_iterator i = edge_graph.begin(); i != edge_graph.end(); ++i) {
 
87
      intersection_graph.vertices[j].v = (*i).first->v;
 
88
      vmap[(*i).first] = j++;
 
89
    }
 
90
 
 
91
    while (edge_graph.size()) {
 
92
      detail::VVSMap::iterator prior_i = edge_graph.begin();
 
93
      carve::mesh::MeshSet<3>::vertex_t *prior = (*prior_i).first;
 
94
      std::vector<size_t> connected;
 
95
      connected.push_back(vmap[prior]);
 
96
      while (prior_i != edge_graph.end() && (*prior_i).second.size()) {
 
97
        carve::mesh::MeshSet<3>::vertex_t *next = *(*prior_i).second.begin();
 
98
        detail::VVSMap::iterator next_i = edge_graph.find(next);
 
99
        CARVE_ASSERT(next_i != edge_graph.end());
 
100
        connected.push_back(vmap[next]);
 
101
        (*prior_i).second.erase(next);
 
102
        (*next_i).second.erase(prior);
 
103
        if (!(*prior_i).second.size()) { edge_graph.erase(prior_i); prior_i = edge_graph.end(); }
 
104
        if (!(*next_i).second.size()) { edge_graph.erase(next_i); next_i = edge_graph.end(); }
 
105
        prior_i = next_i;
 
106
        prior = next;
 
107
      }
 
108
      bool closed = connected.front() == connected.back();
 
109
      for (size_t k = 0; k < connected.size(); ++k) {
 
110
        std::cerr << " " << connected[k];
 
111
      }
 
112
      std::cerr << std::endl;
 
113
      intersection_graph.addPolyline(closed, connected.begin(), connected.end());
 
114
    }
 
115
 
 
116
#if defined(CARVE_DEBUG_WRITE_PLY_DATA)
 
117
    std::string out("/tmp/intersection.ply");
 
118
    ::writePLY(out, &intersection_graph, true);
 
119
#endif
 
120
  }
 
121
 
 
122
  std::cerr << "*** edge graph consistency test done" << std::endl;
 
123
#endif
 
124
}
 
125
 
 
126
 
 
127
 
 
128
#if defined(CARVE_DEBUG_WRITE_PLY_DATA)
 
129
static carve::mesh::MeshSet<3> *groupToPolyhedron(const carve::csg::FaceLoopGroup &grp) {
 
130
  const carve::csg::FaceLoopList &fl = grp.face_loops;
 
131
  std::vector<carve::mesh::MeshSet<3>::face_t *> faces;
 
132
  faces.reserve(fl.size());
 
133
  for (carve::csg::FaceLoop *f = fl.head; f; f = f->next) {
 
134
    faces.push_back(f->orig_face->create(f->vertices.begin(), f->vertices.end(), false));
 
135
  }
 
136
  carve::mesh::MeshSet<3> *poly = new carve::mesh::MeshSet<3>(faces);
 
137
 
 
138
  poly->canonicalize();
 
139
  return poly;
 
140
}
 
141
#endif
 
142
 
 
143
 
 
144
 
 
145
void carve::csg::CSG::groupFaceLoops(carve::mesh::MeshSet<3> *src,
 
146
                                     carve::csg::FaceLoopList &face_loops,
 
147
                                     const carve::csg::detail::LoopEdges &loop_edges,
 
148
                                     const carve::csg::V2Set &no_cross,
 
149
                                     carve::csg::FLGroupList &out_loops) {
 
150
  // Find all the groups of face loops that are connected by edges
 
151
  // that are not part of no_cross.
 
152
  // this could potentially be done with a disjoint set data-structure.
 
153
#if defined(CARVE_DEBUG_WRITE_PLY_DATA)
 
154
  static int call_num = 0;
 
155
  call_num++;
 
156
#endif
 
157
 
 
158
  static carve::TimingName GROUP_FACE_LOOPS("groupFaceLoops()");
 
159
 
 
160
  carve::TimingBlock block(GROUP_FACE_LOOPS);
 
161
 
 
162
  int tag_num = 0;
 
163
  while (face_loops.size()) {
 
164
    out_loops.push_back(FaceLoopGroup(src));
 
165
    carve::csg::FaceLoopGroup &group = (out_loops.back());
 
166
    carve::csg::FaceLoopList &curr = (group.face_loops);
 
167
    carve::csg::V2Set &perim = (group.perimeter);
 
168
 
 
169
    carve::csg::FaceLoop *expand = face_loops.head;
 
170
 
 
171
    expand->group = &group;
 
172
    face_loops.remove(expand);
 
173
    curr.append(expand);
 
174
 
 
175
    while (expand) {
 
176
      std::vector<carve::mesh::MeshSet<3>::vertex_t *> &loop = (expand->vertices);
 
177
      carve::mesh::MeshSet<3>::vertex_t *v1, *v2;
 
178
 
 
179
      v1 = loop.back();
 
180
      for (size_t i = 0; i < loop.size(); ++i) {
 
181
        v2 = loop[i];
 
182
 
 
183
        carve::csg::V2Set::const_iterator nc = no_cross.find(std::make_pair(v1, v2));
 
184
        if (nc == no_cross.end()) {
 
185
          carve::csg::detail::LoopEdges::const_iterator j;
 
186
 
 
187
          j = loop_edges.find(std::make_pair(v1, v2));
 
188
          if (j != loop_edges.end()) {
 
189
            for (std::list<carve::csg::FaceLoop *>::const_iterator
 
190
                   k = (*j).second.begin(), ke = (*j).second.end();
 
191
                 k != ke; ++k) {
 
192
              if ((*k)->group != NULL ||
 
193
                  (*k)->orig_face->mesh != expand->orig_face->mesh) continue;
 
194
              face_loops.remove((*k));
 
195
              curr.append((*k));
 
196
              (*k)->group = &group;
 
197
            }
 
198
          }
 
199
 
 
200
          j = loop_edges.find(std::make_pair(v2, v1));
 
201
          if (j != loop_edges.end()) {
 
202
            for (std::list<carve::csg::FaceLoop *>::const_iterator
 
203
                   k = (*j).second.begin(), ke = (*j).second.end();
 
204
                 k != ke; ++k) {
 
205
              if ((*k)->group != NULL ||
 
206
                  (*k)->orig_face->mesh != expand->orig_face->mesh) continue;
 
207
              face_loops.remove((*k));
 
208
              curr.append((*k));
 
209
              (*k)->group = &group;
 
210
            }
 
211
          }
 
212
        } else {
 
213
          perim.insert(std::make_pair(v1, v2));
 
214
        }
 
215
        v1 = v2;
 
216
      }
 
217
      expand = expand->next;
 
218
    }
 
219
    tag_num++;
 
220
 
 
221
#if defined(CARVE_DEBUG_WRITE_PLY_DATA)
 
222
    {
 
223
      carve::mesh::MeshSet<3> *poly = groupToPolyhedron(group);
 
224
      char buf[128];
 
225
      sprintf(buf, "/tmp/group-%d-%p.ply", call_num, &curr);
 
226
      std::string out(buf);
 
227
      ::writePLY(out, poly, false);
 
228
      delete poly;
 
229
    }
 
230
#endif
 
231
  }
 
232
}