add BLI_strcpy_rlen, replace strcat, which was used in misleading way.
[blender.git] / intern / cycles / subd / subd_ring.cpp
1 /*
2  * Copyright 2006, NVIDIA Corporation Ignacio Castano <icastano@nvidia.com>
3  * 
4  * Modifications copyright (c) 2011, Blender Foundation.
5  * All rights reserved.
6  *
7  * Permission is hereby granted, free of charge, to any person obtaining a copy
8  * of this software and associated documentation files (the "Software"), to deal
9  * in the Software without restriction, including without limitation the rights
10  * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
11  * copies of the Software, and to permit persons to whom the Software is
12  * furnished to do so, subject to the following conditions:
13  * 
14  * The above copyright notice and this permission notice shall be included in
15  * all copies or substantial portions of the Software.
16  * 
17  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
18  * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
19  * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
20  * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
21  * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
22  * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
23  * THE SOFTWARE.
24  */
25
26 #include "subd_face.h"
27 #include "subd_ring.h"
28 #include "subd_stencil.h"
29 #include "subd_vert.h"
30
31 #include "util_algorithm.h"
32 #include "util_debug.h"
33 #include "util_math.h"
34
35 CCL_NAMESPACE_BEGIN
36
37 /* Utility for sorting verts by index */
38
39 class vertex_compare
40 {
41 public:
42         const vector<int>& index;
43         vertex_compare(const vector<int>& index_) : index(index_) {}
44         bool operator()(int a, int b) const { return index[a] < index[b]; }
45 };
46
47 /* Subd Face Ring */
48
49 SubdFaceRing::SubdFaceRing(SubdFace *face, SubdEdge *firstEdge)
50 {
51         m_face = face;
52         m_firstEdge = firstEdge;
53         m_num_edges = face->num_edges();
54
55         assert(m_num_edges == 3 || m_num_edges == 4);
56
57         initVerts();
58 }
59
60 int SubdFaceRing::num_verts()
61 {
62         return m_verts.size();
63 }
64
65 SubdVert *SubdFaceRing::vertexAt(int i)
66 {
67         return m_verts[i];
68 }
69
70 int SubdFaceRing::vert_index(SubdVert *vertex)
71 {
72         int count = this->num_verts();
73
74         for(int i = 0; i < count; i++)
75                 if(m_verts[i] == vertex)
76                         return i;
77         
78         assert(0);
79         return 0;
80 }
81
82 void SubdFaceRing::evaluate_stencils(float3 *P, StencilMask *mask, int num)
83 {
84         /* first we sort verts by id. this way verts will always be added
85          * in the same order to ensure the exact same float ops happen for control
86          * points of other patches, so we get water-tight patches */
87         int num_verts = m_verts.size();
88
89         vector<int> vmap(num_verts);
90         vector<int> vertid(num_verts);
91
92         for(int v = 0; v < num_verts; v++) {
93                 vmap[v] = v;
94                 vertid[v] = m_verts[v]->id;
95         }
96
97         sort(vmap.begin(), vmap.end(), vertex_compare(vertid));
98
99         /* then evaluate the stencils */
100         for(int j = 0; j < num; j++) {
101                 float3 p = make_float3(0.0f, 0.0f, 0.0f);
102
103                 for(int i = 0; i < num_verts; i++) {
104                         int idx = vmap[i];
105                         p += m_verts[idx]->co * mask[j][idx];
106                 }
107
108                 P[j] = p;
109         }
110 }
111
112 bool SubdFaceRing::is_triangle()
113 {
114         return m_num_edges == 3;
115 }
116
117 bool SubdFaceRing::is_quad()
118 {
119         return m_num_edges == 4;
120 }
121
122 int SubdFaceRing::num_edges()
123 {
124         return m_num_edges;
125 }
126
127 bool SubdFaceRing::is_regular(SubdFace *face)
128 {
129         if(!is_quad(face))
130                 return false;
131
132         for(SubdFace::EdgeIterator it(face->edges()); !it.isDone(); it.advance()) {
133                 SubdEdge *edge = it.current();
134
135                 /* regular faces don't have boundary edges */
136                 if(edge->is_boundary())
137                         return false;
138
139                 /* regular faces only have ordinary verts */
140                 if(edge->vert->valence() != 4)
141                         return false;
142
143                 /* regular faces are only adjacent to quads */
144                 for(SubdVert::EdgeIterator eit(edge); !eit.isDone(); eit.advance())
145                         if(eit.current()->face == NULL || eit.current()->face->num_edges() != 4)
146                                 return false;
147         }
148
149         return true;
150 }
151
152 bool SubdFaceRing::is_triangle(SubdFace *face)
153 {
154         return face->num_edges() == 3;
155 }
156 bool SubdFaceRing::is_quad(SubdFace *face)
157 {
158         return face->num_edges() == 4;
159 }
160
161 bool SubdFaceRing::is_boundary(SubdFace *face)
162 {
163         /* note that face->is_boundary() returns a different result. That function
164          * returns true when any of the *edges* are on the boundary. however, this
165          * function returns true if any of the face *verts* are on the boundary.  */
166
167         for(SubdFace::EdgeIterator it(face->edges()); !it.isDone(); it.advance()) {
168                 SubdEdge *edge = it.current();
169
170                 if(edge->vert->is_boundary())
171                         return true;
172         }
173
174         return false;
175 }
176
177 void SubdFaceRing::initVerts()
178 {
179         m_verts.reserve(16);
180
181         /* add face verts */
182         for(SubdFace::EdgeIterator it(m_firstEdge); !it.isDone(); it.advance()) {
183                 SubdEdge *edge = it.current();
184                 m_verts.push_back(edge->from());
185         }
186         
187         // @@ Add support for non manifold surfaces!
188         // The fix: 
189         // - not all colocals should point to the same edge.
190         // - multiple colocals could belong to different boundaries, make sure they point to the right one.
191
192         // @@ When the face neighborhood wraps that could result in overlapping stencils. 
193
194         // Add surronding verts.
195         for(SubdFace::EdgeIterator it(m_firstEdge); !it.isDone(); it.advance()) {
196                 SubdEdge *firstEdge = it.current();
197         
198                 int i = 0;
199
200                 /* traverse edges around vertex */
201                 for(SubdVert::ReverseEdgeIterator eit(firstEdge); !eit.isDone(); eit.advance(), i++) {
202                         SubdEdge *edge = eit.current();
203
204                         assert(edge->from()->co == firstEdge->from()->co);
205
206                         add_vert(edge->to());
207
208                         if(edge->face != NULL)
209                                 add_vert(edge->next->to());
210                 }
211
212                 assert(i == firstEdge->from()->valence());
213         }
214 }
215
216
217 void SubdFaceRing::add_vert(SubdVert *vertex)
218 {
219         /* avoid having duplicate verts */
220         if(!has_vert(vertex))
221                 m_verts.push_back(vertex);
222 }
223
224 bool SubdFaceRing::has_vert(SubdVert *vertex)
225 {
226         int num_verts = m_verts.size();
227
228         for(int i = 0; i < num_verts; i++)
229                 if(m_verts[i]->co == vertex->co)
230                         return true;
231
232         return false;
233 }
234
235 CCL_NAMESPACE_END
236