Cycles: svn merge -r41225:41232 ^/trunk/blender
[blender.git] / intern / cycles / subd / subd_mesh.cpp
1 /*
2  * Original code in the public domain -- castanyo@yahoo.es
3  * 
4  * Modifications copyright (c) 2011, Blender Foundation.
5  * All rights reserved.
6  * 
7  * Redistribution and use in source and binary forms, with or without
8  * modification, are permitted provided that the following conditions are
9  * met:
10  * * Redistributions of source code must retain the above copyright
11  *   notice, this list of conditions and the following disclaimer.
12  * * Redistributions in binary form must reproduce the above copyright
13  *   notice, this list of conditions and the following disclaimer in the
14  *   documentation and/or other materials provided with the distribution.
15  * 
16  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
17  * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
18  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
19  * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
20  * HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
21  * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
22  * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
23  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
24  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
25  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
26  * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
27  */
28
29 #include <stdio.h>
30
31 #include "subd_build.h"
32 #include "subd_edge.h"
33 #include "subd_face.h"
34 #include "subd_mesh.h"
35 #include "subd_patch.h"
36 #include "subd_split.h"
37 #include "subd_vert.h"
38
39 #include "util_debug.h"
40 #include "util_foreach.h"
41
42 CCL_NAMESPACE_BEGIN
43
44 SubdMesh::SubdMesh()
45 {
46 }
47
48 SubdMesh::~SubdMesh()
49 {
50         pair<Key, SubdEdge*> em;
51
52         foreach(SubdVert *vertex, verts)
53                 delete vertex;
54         foreach(em, edge_map)
55                 delete em.second;
56         foreach(SubdFace *face, faces)
57                 delete face;
58
59         verts.clear();
60         edges.clear();
61         edge_map.clear();
62         faces.clear();
63 }
64
65 SubdVert *SubdMesh::add_vert(const float3& co)
66 {
67         SubdVert *v = new SubdVert(verts.size());
68         v->co = co;
69         verts.push_back(v);
70
71         return v;
72 }
73
74 SubdFace *SubdMesh::add_face(int v0, int v1, int v2)
75 {
76         int index[3] = {v0, v1, v2};
77         return add_face(index, 3);
78 }
79
80 SubdFace *SubdMesh::add_face(int v0, int v1, int v2, int v3)
81 {
82         int index[4] = {v0, v1, v2, v3};
83         return add_face(index, 4);
84 }
85
86 SubdFace *SubdMesh::add_face(int *index, int num)
87 {
88         /* test non-manifold cases */
89         if(!can_add_face(index, num)) {
90                 /* we could try to add face in opposite winding instead .. */
91                 fprintf(stderr, "Warning: non manifold mesh, invalid face '%lu'.\n", faces.size());
92                 return NULL;
93         }
94         
95         SubdFace *f = new SubdFace(faces.size());
96         
97         SubdEdge *first_edge = NULL;
98         SubdEdge *last = NULL;
99         SubdEdge *current = NULL;
100
101         /* add edges */
102         for(int i = 0; i < num-1; i++) {
103                 current = add_edge(index[i], index[i+1]);
104                 assert(current != NULL);
105                 
106                 current->face = f;
107                 
108                 if(last != NULL) {
109                         last->next = current;
110                         current->prev = last;
111                 }
112                 else
113                         first_edge = current;
114                 
115                 last = current;
116         }
117
118         current = add_edge(index[num-1], index[0]);
119         assert(current != NULL);
120         
121         current->face = f;
122
123         last->next = current;
124         current->prev = last;
125
126         current->next = first_edge;
127         first_edge->prev = current;
128
129         f->edge = first_edge;
130         faces.push_back(f);
131
132         return f;
133 }
134
135 bool SubdMesh::can_add_face(int *index, int num)
136 {
137         /* manifold check */
138         for(int i = 0; i < num-1; i++)
139                 if(!can_add_edge(index[i], index[i+1]))
140                         return false;
141
142         return can_add_edge(index[num-1], index[0]);
143 }
144
145 bool SubdMesh::can_add_edge(int i, int j)
146 {
147         /* check for degenerate edge */
148         if(i == j)
149                 return false;
150
151         /* make sure edge has not been added yet. */
152         return find_edge(i, j) == NULL;
153 }
154
155 SubdEdge *SubdMesh::add_edge(int i, int j)
156 {
157         SubdEdge *edge;
158
159         /* find pair */
160         SubdEdge *pair = find_edge(j, i);
161
162         if(pair != NULL) {
163                 /* create edge with same id */
164                 edge = new SubdEdge(pair->id + 1);
165                 
166                 /* link edge pairs */
167                 edge->pair = pair;
168                 pair->pair = edge;
169                 
170                 /* not sure this is necessary? */
171                 pair->vert->edge = pair;
172         }
173         else {
174                 /* create edge */
175                 edge = new SubdEdge(2*edges.size());
176                 
177                 /* add only unpaired edges */
178                 edges.push_back(edge);
179         }
180         
181         /* assign vertex and put into map */
182         edge->vert = verts[i];
183         edge_map[Key(i, j)] = edge;
184         
185         /* face and next are set by add_face */
186         
187         return edge;
188 }
189
190 SubdEdge *SubdMesh::find_edge(int i, int j)
191 {
192         map<Key, SubdEdge*>::const_iterator it = edge_map.find(Key(i, j));
193
194         return (it == edge_map.end())? NULL: it->second;
195 }
196
197 bool SubdMesh::link_boundary()
198 {
199         /* link boundary edges once the mesh has been created */
200         int num = 0;
201         
202         /* create boundary edges */
203         int num_edges = edges.size();
204
205         for(int e = 0; e < num_edges; e++) {
206                 SubdEdge *edge = edges[e];
207
208                 if(edge->pair == NULL) {
209                         SubdEdge *pair = new SubdEdge(edge->id + 1);
210
211                         int i = edge->from()->id;
212                         int j = edge->to()->id;
213
214                         assert(edge_map.find(Key(j, i)) == edge_map.end());
215
216                         pair->vert = verts[j];
217                         edge_map[Key(j, i)] = pair;
218                         
219                         edge->pair = pair;
220                         pair->pair = edge;
221                         
222                         num++;
223                 }
224         }
225
226         /* link boundary edges */
227         for(int e = 0; e < num_edges; e++) {
228                 SubdEdge *edge = edges[e];
229
230                 if(edge->pair->face == NULL)
231                         link_boundary_edge(edge->pair);
232         }
233         
234         /* detect boundary intersections */
235         int boundaryIntersections = 0;
236         int num_verts = verts.size();
237
238         for(int v = 0; v < num_verts; v++) {
239                 SubdVert *vertex = verts[v];
240
241                 int boundarySubdEdges = 0;
242                 for(SubdVert::EdgeIterator it(vertex->edges()); !it.isDone(); it.advance())
243                         if(it.current()->is_boundary())
244                                 boundarySubdEdges++;
245
246                 if(boundarySubdEdges > 2) {
247                         assert((boundarySubdEdges & 1) == 0);
248                         boundaryIntersections++;
249                 }
250         }
251
252         if(boundaryIntersections != 0) {
253                 fprintf(stderr, "Invalid mesh, boundary intersections found!\n");
254                 return false;
255         }
256
257         return true;
258 }
259
260 void SubdMesh::link_boundary_edge(SubdEdge *edge)
261 {
262         /* link this boundary edge. */
263
264         /* make sure next pointer has not been set. */
265         assert(edge->face == NULL);
266         assert(edge->next == NULL);
267                 
268         SubdEdge *next = edge;
269
270         while(next->pair->face != NULL) {
271                 /* get pair prev */
272                 SubdEdge *e = next->pair->next;
273
274                 while(e->next != next->pair)
275                         e = e->next;
276
277                 next = e;
278         }
279
280         edge->next = next->pair;
281         next->pair->prev = edge;
282         
283         /* adjust vertex edge, so that it's the boundary edge. (required for is_boundary()) */
284         if(edge->vert->edge != edge)
285                 edge->vert->edge = edge;
286 }
287
288 void SubdMesh::tesselate(DiagSplit *split, bool linear, Mesh *mesh, int shader, bool smooth)
289 {
290         SubdBuilder *builder = SubdBuilder::create(linear);
291         int num_faces = faces.size();
292                         
293         for(int f = 0; f < num_faces; f++) {
294                 SubdFace *face = faces[f];
295                 Patch *patch = builder->run(face);
296
297                 if(patch->is_triangle())
298                         split->split_triangle(mesh, patch, shader, smooth);
299                 else
300                         split->split_quad(mesh, patch, shader, smooth);
301
302                 delete patch;
303         }
304
305         delete builder;
306 }
307
308 CCL_NAMESPACE_END
309