From da376e0237517543aa21740ee2363234ee1c20ae Mon Sep 17 00:00:00 2001 From: Ton Roosendaal Date: Wed, 27 Apr 2011 11:58:34 +0000 Subject: Cycles render engine, initial commit. This is the engine itself, blender modifications and build instructions will follow later. Cycles uses code from some great open source projects, many thanks them: * BVH building and traversal code from NVidia's "Understanding the Efficiency of Ray Traversal on GPUs": http://code.google.com/p/understanding-the-efficiency-of-ray-traversal-on-gpus/ * Open Shading Language for a large part of the shading system: http://code.google.com/p/openshadinglanguage/ * Blender for procedural textures and a few other nodes. * Approximate Catmull Clark subdivision from NVidia Mesh tools: http://code.google.com/p/nvidia-mesh-tools/ * Sobol direction vectors from: http://web.maths.unsw.edu.au/~fkuo/sobol/ * Film response functions from: http://www.cs.columbia.edu/CAVE/software/softlib/dorf.php --- intern/cycles/subd/subd_mesh.cpp | 309 +++++++++++++++++++++++++++++++++++++++ 1 file changed, 309 insertions(+) create mode 100644 intern/cycles/subd/subd_mesh.cpp (limited to 'intern/cycles/subd/subd_mesh.cpp') diff --git a/intern/cycles/subd/subd_mesh.cpp b/intern/cycles/subd/subd_mesh.cpp new file mode 100644 index 00000000000..8ed4854b786 --- /dev/null +++ b/intern/cycles/subd/subd_mesh.cpp @@ -0,0 +1,309 @@ +/* + * Original code in the public domain -- castanyo@yahoo.es + * + * Modifications copyright (c) 2011, Blender Foundation. + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions are + * met: + * * Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * * Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS + * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT + * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR + * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT + * HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, + * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT + * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, + * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY + * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT + * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE + * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ + +#include + +#include "subd_build.h" +#include "subd_edge.h" +#include "subd_face.h" +#include "subd_mesh.h" +#include "subd_patch.h" +#include "subd_split.h" +#include "subd_vert.h" + +#include "util_debug.h" +#include "util_foreach.h" + +CCL_NAMESPACE_BEGIN + +SubdMesh::SubdMesh() +{ +} + +SubdMesh::~SubdMesh() +{ + pair em; + + foreach(SubdVert *vertex, verts) + delete vertex; + foreach(em, edge_map) + delete em.second; + foreach(SubdFace *face, faces) + delete face; + + verts.clear(); + edges.clear(); + edge_map.clear(); + faces.clear(); +} + +SubdVert *SubdMesh::add_vert(const float3& co) +{ + SubdVert *v = new SubdVert(verts.size()); + v->co = co; + verts.push_back(v); + + return v; +} + +SubdFace *SubdMesh::add_face(int v0, int v1, int v2) +{ + int index[3] = {v0, v1, v2}; + return add_face(index, 3); +} + +SubdFace *SubdMesh::add_face(int v0, int v1, int v2, int v3) +{ + int index[4] = {v0, v1, v2, v3}; + return add_face(index, 4); +} + +SubdFace *SubdMesh::add_face(int *index, int num) +{ + /* test non-manifold cases */ + if(!can_add_face(index, num)) { + /* we could try to add face in opposite winding instead .. */ + fprintf(stderr, "Warning: non manifold mesh, invalid face '%lu'.\n", faces.size()); + return NULL; + } + + SubdFace *f = new SubdFace(faces.size()); + + SubdEdge *first_edge = NULL; + SubdEdge *last = NULL; + SubdEdge *current = NULL; + + /* add edges */ + for(int i = 0; i < num-1; i++) { + current = add_edge(index[i], index[i+1]); + assert(current != NULL); + + current->face = f; + + if(last != NULL) { + last->next = current; + current->prev = last; + } + else + first_edge = current; + + last = current; + } + + current = add_edge(index[num-1], index[0]); + assert(current != NULL); + + current->face = f; + + last->next = current; + current->prev = last; + + current->next = first_edge; + first_edge->prev = current; + + f->edge = first_edge; + faces.push_back(f); + + return f; +} + +bool SubdMesh::can_add_face(int *index, int num) +{ + /* manifold check */ + for(int i = 0; i < num-1; i++) + if(!can_add_edge(index[i], index[i+1])) + return false; + + return can_add_edge(index[num-1], index[0]); +} + +bool SubdMesh::can_add_edge(int i, int j) +{ + /* check for degenerate edge */ + if(i == j) + return false; + + /* make sure edge has not been added yet. */ + return find_edge(i, j) == NULL; +} + +SubdEdge *SubdMesh::add_edge(int i, int j) +{ + SubdEdge *edge; + + /* find pair */ + SubdEdge *pair = find_edge(j, i); + + if(pair != NULL) { + /* create edge with same id */ + edge = new SubdEdge(pair->id + 1); + + /* link edge pairs */ + edge->pair = pair; + pair->pair = edge; + + /* not sure this is necessary? */ + pair->vert->edge = pair; + } + else { + /* create edge */ + edge = new SubdEdge(2*edges.size()); + + /* add only unpaired edges */ + edges.push_back(edge); + } + + /* assign vertex and put into map */ + edge->vert = verts[i]; + edge_map[Key(i, j)] = edge; + + /* face and next are set by add_face */ + + return edge; +} + +SubdEdge *SubdMesh::find_edge(int i, int j) +{ + map::const_iterator it = edge_map.find(Key(i, j)); + + return (it == edge_map.end())? NULL: it->second; +} + +bool SubdMesh::link_boundary() +{ + /* link boundary edges once the mesh has been created */ + int num = 0; + + /* create boundary edges */ + int num_edges = edges.size(); + + for(int e = 0; e < num_edges; e++) { + SubdEdge *edge = edges[e]; + + if(edge->pair == NULL) { + SubdEdge *pair = new SubdEdge(edge->id + 1); + + int i = edge->from()->id; + int j = edge->to()->id; + + assert(edge_map.find(Key(j, i)) == edge_map.end()); + + pair->vert = verts[j]; + edge_map[Key(j, i)] = pair; + + edge->pair = pair; + pair->pair = edge; + + num++; + } + } + + /* link boundary edges */ + for(int e = 0; e < num_edges; e++) { + SubdEdge *edge = edges[e]; + + if(edge->pair->face == NULL) + link_boundary_edge(edge->pair); + } + + /* detect boundary intersections */ + int boundaryIntersections = 0; + int num_verts = verts.size(); + + for(int v = 0; v < num_verts; v++) { + SubdVert *vertex = verts[v]; + + int boundarySubdEdges = 0; + for(SubdVert::EdgeIterator it(vertex->edges()); !it.isDone(); it.advance()) + if(it.current()->is_boundary()) + boundarySubdEdges++; + + if(boundarySubdEdges > 2) { + assert((boundarySubdEdges & 1) == 0); + boundaryIntersections++; + } + } + + if(boundaryIntersections != 0) { + fprintf(stderr, "Invalid mesh, boundary intersections found!\n"); + return false; + } + + return true; +} + +void SubdMesh::link_boundary_edge(SubdEdge *edge) +{ + /* link this boundary edge. */ + + /* make sure next pointer has not been set. */ + assert(edge->face == NULL); + assert(edge->next == NULL); + + SubdEdge *next = edge; + + while(next->pair->face != NULL) { + /* get pair prev */ + SubdEdge *e = next->pair->next; + + while(e->next != next->pair) + e = e->next; + + next = e; + } + + edge->next = next->pair; + next->pair->prev = edge; + + /* adjust vertex edge, so that it's the boundary edge. (required for is_boundary()) */ + if(edge->vert->edge != edge) + edge->vert->edge = edge; +} + +void SubdMesh::tesselate(DiagSplit *split, bool linear, Mesh *mesh, int shader, bool smooth) +{ + SubdBuilder *builder = SubdBuilder::create(linear); + int num_faces = faces.size(); + + for(int f = 0; f < num_faces; f++) { + SubdFace *face = faces[f]; + Patch *patch = builder->run(face); + + if(patch->is_triangle()) + split->split_triangle(mesh, patch, shader, smooth); + else + split->split_quad(mesh, patch, shader, smooth); + + delete patch; + } + + delete builder; +} + +CCL_NAMESPACE_END + -- cgit v1.2.3