Blender V2.61 - r43446

subd_mesh.cpp

Go to the documentation of this file.
00001 /*
00002  * Original code in the public domain -- castanyo@yahoo.es
00003  * 
00004  * Modifications copyright (c) 2011, Blender Foundation.
00005  * All rights reserved.
00006  * 
00007  * Redistribution and use in source and binary forms, with or without
00008  * modification, are permitted provided that the following conditions are
00009  * met:
00010  * * Redistributions of source code must retain the above copyright
00011  *   notice, this list of conditions and the following disclaimer.
00012  * * Redistributions in binary form must reproduce the above copyright
00013  *   notice, this list of conditions and the following disclaimer in the
00014  *   documentation and/or other materials provided with the distribution.
00015  * 
00016  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
00017  * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
00018  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
00019  * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
00020  * HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
00021  * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
00022  * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
00023  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
00024  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
00025  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
00026  * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
00027  */
00028 
00029 #include <stdio.h>
00030 
00031 #include "subd_build.h"
00032 #include "subd_edge.h"
00033 #include "subd_face.h"
00034 #include "subd_mesh.h"
00035 #include "subd_patch.h"
00036 #include "subd_split.h"
00037 #include "subd_vert.h"
00038 
00039 #include "util_debug.h"
00040 #include "util_foreach.h"
00041 
00042 CCL_NAMESPACE_BEGIN
00043 
00044 SubdMesh::SubdMesh()
00045 {
00046 }
00047 
00048 SubdMesh::~SubdMesh()
00049 {
00050     pair<Key, SubdEdge*> em;
00051 
00052     foreach(SubdVert *vertex, verts)
00053         delete vertex;
00054     foreach(em, edge_map)
00055         delete em.second;
00056     foreach(SubdFace *face, faces)
00057         delete face;
00058 
00059     verts.clear();
00060     edges.clear();
00061     edge_map.clear();
00062     faces.clear();
00063 }
00064 
00065 SubdVert *SubdMesh::add_vert(const float3& co)
00066 {
00067     SubdVert *v = new SubdVert(verts.size());
00068     v->co = co;
00069     verts.push_back(v);
00070 
00071     return v;
00072 }
00073 
00074 SubdFace *SubdMesh::add_face(int v0, int v1, int v2)
00075 {
00076     int index[3] = {v0, v1, v2};
00077     return add_face(index, 3);
00078 }
00079 
00080 SubdFace *SubdMesh::add_face(int v0, int v1, int v2, int v3)
00081 {
00082     int index[4] = {v0, v1, v2, v3};
00083     return add_face(index, 4);
00084 }
00085 
00086 SubdFace *SubdMesh::add_face(int *index, int num)
00087 {
00088     /* test non-manifold cases */
00089     if(!can_add_face(index, num)) {
00090         /* we could try to add face in opposite winding instead .. */
00091         fprintf(stderr, "Warning: non manifold mesh, invalid face '%lu'.\n", (unsigned long)faces.size());
00092         return NULL;
00093     }
00094     
00095     SubdFace *f = new SubdFace(faces.size());
00096     
00097     SubdEdge *first_edge = NULL;
00098     SubdEdge *last = NULL;
00099     SubdEdge *current = NULL;
00100 
00101     /* add edges */
00102     for(int i = 0; i < num-1; i++) {
00103         current = add_edge(index[i], index[i+1]);
00104         assert(current != NULL);
00105         
00106         current->face = f;
00107         
00108         if(last != NULL) {
00109             last->next = current;
00110             current->prev = last;
00111         }
00112         else
00113             first_edge = current;
00114         
00115         last = current;
00116     }
00117 
00118     current = add_edge(index[num-1], index[0]);
00119     assert(current != NULL);
00120     
00121     current->face = f;
00122 
00123     last->next = current;
00124     current->prev = last;
00125 
00126     current->next = first_edge;
00127     first_edge->prev = current;
00128 
00129     f->edge = first_edge;
00130     faces.push_back(f);
00131 
00132     return f;
00133 }
00134 
00135 bool SubdMesh::can_add_face(int *index, int num)
00136 {
00137     /* manifold check */
00138     for(int i = 0; i < num-1; i++)
00139         if(!can_add_edge(index[i], index[i+1]))
00140             return false;
00141 
00142     return can_add_edge(index[num-1], index[0]);
00143 }
00144 
00145 bool SubdMesh::can_add_edge(int i, int j)
00146 {
00147     /* check for degenerate edge */
00148     if(i == j)
00149         return false;
00150 
00151     /* make sure edge has not been added yet. */
00152     return find_edge(i, j) == NULL;
00153 }
00154 
00155 SubdEdge *SubdMesh::add_edge(int i, int j)
00156 {
00157     SubdEdge *edge;
00158 
00159     /* find pair */
00160     SubdEdge *pair = find_edge(j, i);
00161 
00162     if(pair != NULL) {
00163         /* create edge with same id */
00164         edge = new SubdEdge(pair->id + 1);
00165         
00166         /* link edge pairs */
00167         edge->pair = pair;
00168         pair->pair = edge;
00169         
00170         /* not sure this is necessary? */
00171         pair->vert->edge = pair;
00172     }
00173     else {
00174         /* create edge */
00175         edge = new SubdEdge(2*edges.size());
00176         
00177         /* add only unpaired edges */
00178         edges.push_back(edge);
00179     }
00180     
00181     /* assign vertex and put into map */
00182     edge->vert = verts[i];
00183     edge_map[Key(i, j)] = edge;
00184     
00185     /* face and next are set by add_face */
00186     
00187     return edge;
00188 }
00189 
00190 SubdEdge *SubdMesh::find_edge(int i, int j)
00191 {
00192     map<Key, SubdEdge*>::const_iterator it = edge_map.find(Key(i, j));
00193 
00194     return (it == edge_map.end())? NULL: it->second;
00195 }
00196 
00197 bool SubdMesh::link_boundary()
00198 {
00199     /* link boundary edges once the mesh has been created */
00200     int num = 0;
00201     
00202     /* create boundary edges */
00203     int num_edges = edges.size();
00204 
00205     for(int e = 0; e < num_edges; e++) {
00206         SubdEdge *edge = edges[e];
00207 
00208         if(edge->pair == NULL) {
00209             SubdEdge *pair = new SubdEdge(edge->id + 1);
00210 
00211             int i = edge->from()->id;
00212             int j = edge->to()->id;
00213 
00214             assert(edge_map.find(Key(j, i)) == edge_map.end());
00215 
00216             pair->vert = verts[j];
00217             edge_map[Key(j, i)] = pair;
00218             
00219             edge->pair = pair;
00220             pair->pair = edge;
00221             
00222             num++;
00223         }
00224     }
00225 
00226     /* link boundary edges */
00227     for(int e = 0; e < num_edges; e++) {
00228         SubdEdge *edge = edges[e];
00229 
00230         if(edge->pair->face == NULL)
00231             link_boundary_edge(edge->pair);
00232     }
00233     
00234     /* detect boundary intersections */
00235     int boundaryIntersections = 0;
00236     int num_verts = verts.size();
00237 
00238     for(int v = 0; v < num_verts; v++) {
00239         SubdVert *vertex = verts[v];
00240 
00241         int boundarySubdEdges = 0;
00242         for(SubdVert::EdgeIterator it(vertex->edges()); !it.isDone(); it.advance())
00243             if(it.current()->is_boundary())
00244                 boundarySubdEdges++;
00245 
00246         if(boundarySubdEdges > 2) {
00247             assert((boundarySubdEdges & 1) == 0);
00248             boundaryIntersections++;
00249         }
00250     }
00251 
00252     if(boundaryIntersections != 0) {
00253         fprintf(stderr, "Invalid mesh, boundary intersections found!\n");
00254         return false;
00255     }
00256 
00257     return true;
00258 }
00259 
00260 void SubdMesh::link_boundary_edge(SubdEdge *edge)
00261 {
00262     /* link this boundary edge. */
00263 
00264     /* make sure next pointer has not been set. */
00265     assert(edge->face == NULL);
00266     assert(edge->next == NULL);
00267         
00268     SubdEdge *next = edge;
00269 
00270     while(next->pair->face != NULL) {
00271         /* get pair prev */
00272         SubdEdge *e = next->pair->next;
00273 
00274         while(e->next != next->pair)
00275             e = e->next;
00276 
00277         next = e;
00278     }
00279 
00280     edge->next = next->pair;
00281     next->pair->prev = edge;
00282     
00283     /* adjust vertex edge, so that it's the boundary edge. (required for is_boundary()) */
00284     if(edge->vert->edge != edge)
00285         edge->vert->edge = edge;
00286 }
00287 
00288 void SubdMesh::tesselate(DiagSplit *split, bool linear, Mesh *mesh, int shader, bool smooth)
00289 {
00290     SubdBuilder *builder = SubdBuilder::create(linear);
00291     int num_faces = faces.size();
00292                 
00293     for(int f = 0; f < num_faces; f++) {
00294         SubdFace *face = faces[f];
00295         Patch *patch = builder->run(face);
00296 
00297         if(patch->is_triangle())
00298             split->split_triangle(mesh, patch, shader, smooth);
00299         else
00300             split->split_quad(mesh, patch, shader, smooth);
00301 
00302         delete patch;
00303     }
00304 
00305     delete builder;
00306 }
00307 
00308 CCL_NAMESPACE_END
00309