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