add BLI_strcpy_rlen, replace strcat, which was used in misleading way.
[blender.git] / intern / cycles / subd / subd_build.cpp
1 /*
2  * Copyright 2006, NVIDIA Corporation Ignacio Castano <icastano@nvidia.com>
3  *
4  * Modifications copyright (c) 2011, Blender Foundation. All rights reserved.
5  * 
6  * Permission is hereby granted, free of charge, to any person obtaining a copy
7  * of this software and associated documentation files (the "Software"), to deal
8  * in the Software without restriction, including without limitation the rights
9  * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
10  * copies of the Software, and to permit persons to whom the Software is
11  * furnished to do so, subject to the following conditions:
12  * 
13  * The above copyright notice and this permission notice shall be included in
14  * all copies or substantial portions of the Software.
15  * 
16  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
17  * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
18  * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
19  * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
20  * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
21  * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
22  * THE SOFTWARE.
23  */
24
25 #include "subd_build.h"
26 #include "subd_edge.h"
27 #include "subd_face.h"
28 #include "subd_ring.h"
29 #include "subd_mesh.h"
30 #include "subd_patch.h"
31 #include "subd_stencil.h"
32 #include "subd_vert.h"
33
34 #include "util_algorithm.h"
35 #include "util_debug.h"
36 #include "util_math.h"
37 #include "util_string.h"
38
39 CCL_NAMESPACE_BEGIN
40
41 /* Subd Builder */
42
43 SubdBuilder *SubdBuilder::create(bool linear)
44 {
45         if(linear)
46                 return new SubdLinearBuilder();
47         else
48                 return new SubdAccBuilder();
49 }
50
51 /* Gregory ACC Stencil */
52
53 class GregoryAccStencil {
54 public:
55         SubdFaceRing *ring;
56         StencilMask stencil[20];
57
58         GregoryAccStencil(SubdFaceRing *ring_)
59         {
60                 ring = ring_;
61
62                 for(int i = 0; i < 20; i++)
63                         stencil[i].resize(ring->num_verts());
64         }
65
66         StencilMask& get(int i)
67         {
68                 assert(i < 20);
69                 return stencil[i];
70         }
71
72         float& get(int i, SubdVert *vert)
73         {
74                 assert(i < 20);
75                 return stencil[i][ring->vert_index(vert)];
76         }
77 };
78
79 static float pseudoValence(SubdVert *vert)
80 {
81         float valence = (float)vert->valence();
82
83         if(vert->is_boundary()) {
84                 /* we treat boundary verts as being half a closed mesh. corners are
85                  * special case. n = 4 for corners and n = 2*(n-1) for boundaries. */
86                 if(valence == 2) return 4;
87                 return (valence - 1)*2;
88         }
89
90         return valence;
91 }
92
93 /* Subd ACC Builder */
94
95 SubdAccBuilder::SubdAccBuilder()
96 {
97 }
98
99 SubdAccBuilder::~SubdAccBuilder()
100 {
101 }
102
103 Patch *SubdAccBuilder::run(SubdFace *face)
104 {
105         SubdFaceRing ring(face, face->edge);
106         GregoryAccStencil stencil(&ring);
107         float3 position[20];
108
109         computeCornerStencil(&ring, &stencil);
110         computeEdgeStencil(&ring, &stencil);
111         computeInteriorStencil(&ring, &stencil);
112
113         ring.evaluate_stencils(position, stencil.stencil, 20);
114
115         if(face->num_edges() == 3) {
116                 GregoryTrianglePatch *patch = new GregoryTrianglePatch();
117                 memcpy(patch->hull, position, sizeof(float3)*20);
118                 return patch;
119         }
120         else if(face->num_edges() == 4) {
121                 GregoryQuadPatch *patch = new GregoryQuadPatch();
122                 memcpy(patch->hull, position, sizeof(float3)*20);
123                 return patch;
124         }
125
126         assert(0); /* n-gons should have been split already */
127         return NULL;
128 }
129
130 /* Gregory Patch */
131
132 void SubdAccBuilder::computeCornerStencil(SubdFaceRing *ring, GregoryAccStencil *stencil)
133 {
134         const int cornerIndices[7] = {8, 11, 19, 16,   6, 9, 12};
135         int primitiveOffset = ring->is_quad()? 0: 4;
136
137         SubdEdge *firstEdge = ring->firstEdge();
138
139         /* compute corner control points */
140         int v = 0;
141
142         for(SubdFace::EdgeIterator it(firstEdge); !it.isDone(); it.advance(), v++) {
143                 SubdVert *vert = it.current()->from();
144                 int valence = vert->valence();
145                 int cid = cornerIndices[primitiveOffset+v];
146
147                 if(vert->is_boundary()) {
148                         /* compute vertex limit position */
149                         SubdEdge *edge0 = vert->edge;
150                         SubdEdge *edge1 = vert->edge->prev;
151
152                         assert(edge0->face == NULL);
153                         assert(edge0->to() != vert);
154                         assert(edge1->face == NULL);
155                         assert(edge1->from() != vert);
156
157                         stencil->get(cid, vert) = 2.0f/3.0f;
158                         stencil->get(cid, edge0->to()) = 1.0f/6.0f;
159                         stencil->get(cid, edge1->from()) = 1.0f/6.0f;
160
161                         assert(stencil->get(cid).is_normalized());
162                 }
163                 else {
164                         stencil->get(cid, vert) = 3.0f*valence*valence;
165
166                         for(SubdVert::EdgeIterator eit(vert->edge); !eit.isDone(); eit.advance()) {
167                                 SubdEdge *edge = eit.current();
168                                 assert(vert->co == edge->from()->co);
169
170                                 stencil->get(cid, edge->to()) = 12.0f;
171
172                                 if(SubdFaceRing::is_triangle(edge->face)) {
173                                         /* distribute weight to all verts */
174                                         stencil->get(cid, vert) += 1.0f;
175                                         stencil->get(cid, edge->to()) += 1.0f;
176                                         stencil->get(cid, edge->next->to()) += 1.0f;
177                                 }
178                                 else
179                                         stencil->get(cid, edge->next->to()) = 3.0f;
180                         }
181
182                         /* normalize stencil. */
183                         stencil->get(cid).normalize();
184                 }
185         }
186 }
187
188 void SubdAccBuilder::computeEdgeStencil(SubdFaceRing *ring, GregoryAccStencil *stencil)
189 {
190         const int cornerIndices[7] = {8, 11, 19, 16,    6,  9, 12};
191         const int edge1Indices[7] = {9, 13, 18, 14,    7, 10, 13};
192         const int edge2Indices[7] = {12, 10, 15, 17,    14,  8, 11};
193         int primitiveOffset = ring->is_quad()? 0: 4;
194
195         float tangentScales[14] = {
196                 0.0f, 0.0f, 0.0f, 0.667791f, 1.0f,
197                 1.11268f, 1.1284f, 1.10289f, 1.06062f,
198                 1.01262f, 0.963949f, 0.916926f, 0.872541f, 0.831134f
199         };
200
201         SubdEdge *firstEdge = ring->firstEdge();
202
203         /* compute corner / edge control points */
204         int v = 0;
205
206         for(SubdFace::EdgeIterator it(firstEdge); !it.isDone(); it.advance(), v++) {
207                 SubdVert *vert = it.current()->from();
208                 int valence = vert->valence();
209                 int cid = cornerIndices[primitiveOffset+v];
210
211                 int i1 = 0, i2 = 0, j = 0;
212
213                 for(SubdVert::EdgeIterator eit(vert->edge); !eit.isDone(); eit.advance(), j++) {
214                         SubdEdge *edge = eit.current();
215
216                         /* find index of "our" edge for edge control points */
217                         if(edge == it.current())
218                                 i1 = j;
219                         if(edge == it.current()->prev->pair)
220                                 i2 = j;
221                 }
222
223                 if(vert->is_boundary()) {
224                         int num_verts = ring->num_verts();
225                         StencilMask     r0(num_verts);
226                         StencilMask     r1(num_verts);
227
228                         computeBoundaryTangentStencils(ring, vert, r0, r1);
229
230                         int k = valence - 1;
231                         float omega = M_PI_F / k;
232
233                         int eid1 = edge1Indices[primitiveOffset + v];
234                         int eid2 = edge2Indices[primitiveOffset + v];
235
236                         if(it.current()->is_boundary()) {
237                                 assert(it.current()->from() == vert);
238
239                                 stencil->get(eid1, vert) = 2.0f / 3.0f;
240                                 stencil->get(eid1, it.current()->to()) = 1.0f / 3.0f;
241
242                                 assert(stencil->get(eid1).is_normalized());
243
244                                 if(valence == 2) {
245                                         for(int i = 0; i < num_verts; i++)
246                                                 stencil->get(eid1)[i] += r0[i] * 0.0001f;
247                                 }
248                         }
249                         else {
250                                 stencil->get(eid1) = stencil->get(cid);
251
252                                 /* compute index of it.current() around vert */
253                                 int idx = 0;
254
255                                 for(SubdVert::EdgeIterator eit(vert->edges()); !eit.isDone(); eit.advance(), idx++)
256                                         if(eit.current() == it.current())
257                                                 break;
258
259                                 assert(idx != valence);
260
261                                 float c = cosf(idx * omega);
262                                 float s = sinf(idx * omega);
263
264                                 for(int i = 0; i < num_verts; i++)
265                                         stencil->get(eid1)[i] += (r0[i] * s + r1[i] * c) / 3.0f;
266                         }
267
268                         if(it.current()->prev->is_boundary()) {
269                                 assert(it.current()->prev->pair->from() == vert);
270
271                                 stencil->get(eid2, vert) = 2.0f / 3.0f;
272                                 stencil->get(eid2, it.current()->prev->pair->to()) = 1.0f / 3.0f;
273
274                                 assert(stencil->get(eid2).is_normalized());
275
276                                 if(valence == 2) {
277                                         for(int i = 0; i < num_verts; i++)
278                                                 stencil->get(eid2)[i] += r0[i] * 0.0001f;
279                                 }
280                         }
281                         else {
282                                 stencil->get(eid2) = stencil->get(cid);
283
284                                 /* compute index of it.current() around vert */
285                                 int idx = 0;
286
287                                 for(SubdVert::EdgeIterator eit(vert->edges()); !eit.isDone(); eit.advance(), idx++)
288                                         if(eit.current() == it.current()->prev->pair)
289                                                 break;
290
291                                 assert(idx != valence);
292
293                                 float c = cosf(idx * omega);
294                                 float s = sinf(idx * omega);
295
296                                 for(int i = 0; i < num_verts; i++)
297                                         stencil->get(eid2)[i] += (r0[i] * s + r1[i] * c) / 3;
298                         }
299                 }
300                 else {
301                         float costerm = cosf(M_PI_F / valence);
302                         float sqrtterm = sqrtf(4.0f + costerm*costerm);
303
304                         /* float tangentScale = 1.0f; */
305                         float tangentScale = tangentScales[min(valence, 13U)];
306
307                         float alpha = (1.0f +  costerm / sqrtterm) / (3.0f * valence) * tangentScale;
308                         float beta  = 1.0f / (3.0f * valence * sqrtterm) * tangentScale;
309
310
311                         int eid1 = edge1Indices[primitiveOffset + v];
312                         int eid2 = edge2Indices[primitiveOffset + v];
313
314                         stencil->get(eid1) = stencil->get(cid);
315                         stencil->get(eid2) = stencil->get(cid);
316
317                         j = 0;
318                         for(SubdVert::EdgeIterator eit(vert->edges()); !eit.isDone(); eit.advance(), j++) {
319                                 SubdEdge *edge = eit.current();
320                                 assert(vert->co == edge->from()->co);
321
322                                 float costerm1_a = cosf(M_PI_F * 2 * (j-i1) / valence);
323                                 float costerm1_b = cosf(M_PI_F * (2 * (j-i1)-1) / valence); /* -1 instead of +1 b/c of edge->next->to() */
324
325                                 float costerm2_a = cosf(M_PI_F * 2 * (j-i2) / valence);
326                                 float costerm2_b = cosf(M_PI_F * (2 * (j-i2)-1) / valence); /* -1 instead of +1 b/c of edge->next->to() */
327
328
329                                 stencil->get(eid1, edge->to()) += alpha * costerm1_a;
330                                 stencil->get(eid2, edge->to()) += alpha * costerm2_a;
331
332                                 if(SubdFaceRing::is_triangle(edge->face)) {
333                                         /* @@ this probably does not provide watertight results!! (1/3 + 1/3 + 1/3 != 1) */
334
335                                         /* distribute weight to all verts */
336                                         stencil->get(eid1, vert) += beta * costerm1_b / 3.0f;
337                                         stencil->get(eid1, edge->to()) += beta * costerm1_b / 3.0f;
338                                         stencil->get(eid1, edge->next->to()) += beta * costerm1_b / 3.0f;
339
340                                         stencil->get(eid2, vert) += beta * costerm2_b / 3.0f;
341                                         stencil->get(eid2, edge->to()) += beta * costerm2_b / 3.0f;
342                                         stencil->get(eid2, edge->next->to()) += beta * costerm2_b / 3.0f;
343                                 }
344                                 else {
345                                         stencil->get(eid1, edge->next->to()) += beta * costerm1_b;
346                                         stencil->get(eid2, edge->next->to()) += beta * costerm2_b;
347                                 }
348                         }
349                 }
350         }
351 }
352
353 void SubdAccBuilder::computeInteriorStencil(SubdFaceRing *ring, GregoryAccStencil *stencil)
354 {
355         static int corner1Indices[7] = {8, 11, 19, 16,    6, 9, 12};
356         static int corner2Indices[7] = {11, 19, 16, 8,    9, 12, 6};
357         static int edge1Indices[7] = {9, 13, 18, 14,    7, 10, 13};
358         static int edge2Indices[7] = {10, 15, 17, 12,    8, 11, 14};
359         static int interior1Indices[7] = {1, 3, 6, 4,    1, 3, 5};
360         static int interior2Indices[7] = {2, 7, 5, 0,    2, 4, 0};
361
362         int primitiveOffset = ring->is_quad()? 0: 4;
363
364         SubdFace * face = ring->face();
365         SubdEdge *firstEdge = ring->firstEdge();
366
367         /* interior control points */
368         int v = 0;
369         for(SubdFace::EdgeIterator it(firstEdge); !it.isDone(); it.advance(), v++) {
370                 SubdEdge *edge = it.current();
371
372                 if(edge->is_boundary()) {
373                         float valence1 = pseudoValence(edge->from());
374                         float valence2 = pseudoValence(edge->to());
375
376                         float weights1[4];
377                         float weights2[4];
378
379                         if(ring->is_quad()) {
380                                 weights1[0] = 3 * valence1;
381                                 weights1[1] = 6;
382                                 weights1[2] = 3;
383                                 weights1[3] = 6;
384
385                                 weights2[0] = 6;
386                                 weights2[1] = 3 * valence2;
387                                 weights2[2] = 6;
388                                 weights2[3] = 3;
389                         }
390                         else {
391                                 assert(ring->is_triangle());
392                                 weights1[0] = 3 * valence1 + 1;
393                                 weights1[1] = 7;
394                                 weights1[2] = 7;
395
396                                 weights2[0] = 7;
397                                 weights2[1] = 3 * valence2 + 1;
398                                 weights2[2] = 7;
399                         }
400
401                         int idx1 = interior1Indices[primitiveOffset+v];
402                         int idx2 = interior2Indices[primitiveOffset+v];
403
404                         int i = 0;
405                         for(SubdFace::EdgeIterator it_sub(face->edges(edge)); !it_sub.isDone(); it_sub.advance(), i++) {
406                                 SubdVert *vert = it_sub.current()->from();
407                                 stencil->get(idx1, vert) += weights1[i];
408                                 stencil->get(idx2, vert) += weights2[i];
409                         }
410
411                         stencil->get(idx1).normalize();
412                         stencil->get(idx2).normalize();
413                 }
414                 else {
415                         SubdVert *e0 = edge->from();
416                         float costerm0 = cosf(M_2PI_F / pseudoValence(e0));
417
418                         SubdVert *f0 = edge->to();
419                         float costerm1 = cosf(M_2PI_F / pseudoValence(f0));
420
421                         /*  p0 +------+ q0
422                          *       |        |
423                          *  f0 +======+ e0 <=== current edge
424                          *       |        |
425                          *  p1 +------+ q1
426                          */
427
428                         SubdVert *q0 = edge->next->to();
429                         SubdVert *p0 = edge->prev->from();
430
431                         SubdVert *p1 = edge->pair->next->to();
432                         SubdVert *q1 = edge->pair->prev->from();
433
434
435                         StencilMask     x(ring->num_verts());
436                         StencilMask     y(ring->num_verts());
437
438                         for(int i = 0; i < ring->num_verts(); i++) {
439                                 x[i] =
440                                         (costerm1 * stencil->get(corner1Indices[primitiveOffset+v])[i] -
441                                         (2*costerm0 + costerm1) * stencil->get(edge1Indices[primitiveOffset+v])[i] +
442                                         2*costerm0 * stencil->get(edge2Indices[primitiveOffset+v])[i]) / 3.0f;
443                         }
444
445                         /* y = (2*( midedgeA1 - midedgeB1) + 4*(centroidA - centroidB))/18.0f; */
446                         y[ring->vert_index(p0)] = 1;
447                         y[ring->vert_index(p1)] = -1;
448
449                         /* add centroidA */
450                         if(ring->is_triangle()) {
451                                 y[ring->vert_index(p0)] += 4.0f / 3.0f;
452                                 y[ring->vert_index(e0)] += 4.0f / 3.0f;
453                                 y[ring->vert_index(f0)] += 4.0f / 3.0f;
454                         }
455                         else {
456                                 y[ring->vert_index(p0)] += 1;
457                                 y[ring->vert_index(q0)] += 1;
458                                 y[ring->vert_index(e0)] += 1;
459                                 y[ring->vert_index(f0)] += 1;
460                         }
461
462                         /* sub centroidB */
463                         if(SubdFaceRing::is_triangle(edge->pair->face)) {
464                                 y[ring->vert_index(p1)] -= 4.0f / 3.0f;
465                                 y[ring->vert_index(e0)] -= 4.0f / 3.0f;
466                                 y[ring->vert_index(f0)] -= 4.0f / 3.0f;
467
468                         }
469                         else {
470                                 y[ring->vert_index(p1)] -= 1;
471                                 y[ring->vert_index(q1)] -= 1;
472                                 y[ring->vert_index(e0)] -= 1;
473                                 y[ring->vert_index(f0)] -= 1;
474                         }
475
476                         y /= 18.0f;
477
478                         if(ring->is_triangle()) {
479                                 x *= 3.0f / 4.0f;
480                                 y *= 3.0f / 4.0f;
481                         }
482
483                         /* this change makes the triangle boundaries smoother, but distorts the quads next to them */
484 #if 0
485                         if(ring->is_triangle() || SubdFaceRing::is_triangle(edge->pair->face)) {
486                                 y *= 4.0f / 3.0f;
487                         }
488 #endif
489
490                         stencil->get(interior1Indices[primitiveOffset+v]) = stencil->get(edge1Indices[primitiveOffset+v]);
491                         stencil->get(interior1Indices[primitiveOffset+v]) += x;
492                         stencil->get(interior1Indices[primitiveOffset+v]) += y;
493
494                         for(int i = 0; i < ring->num_verts(); i++) {
495                                 x[i] =
496                                         (costerm0 * stencil->get(corner2Indices[primitiveOffset+v])[i] -
497                                         (2*costerm1 + costerm0) * stencil->get(edge2Indices[primitiveOffset+v])[i] + 
498                                         2*costerm1 * stencil->get(edge1Indices[primitiveOffset+v])[i]) / 3.0f;
499                         }
500
501                         /* y = (2*( midedgeA2 - midedgeB2) + 4*(centroidA - centroidB))/18.0f; */
502                         y = 0.0f;
503
504                         /* (2*( midedgeA2 - midedgeB2) */
505                         y[ring->vert_index(q0)] = 1;
506                         y[ring->vert_index(q1)] = -1;
507
508                         /* add centroidA */
509                         if(ring->is_triangle()) {
510                                 y[ring->vert_index(p0)] += 4.0f / 3.0f;
511                                 y[ring->vert_index(e0)] += 4.0f / 3.0f;
512                                 y[ring->vert_index(f0)] += 4.0f / 3.0f;
513                         }
514                         else {
515                                 y[ring->vert_index(p0)] += 1;
516                                 y[ring->vert_index(q0)] += 1;
517                                 y[ring->vert_index(e0)] += 1;
518                                 y[ring->vert_index(f0)] += 1;
519                         }
520
521                         /* sub centroidB */
522                         if(SubdFaceRing::is_triangle(edge->pair->face)) {
523                                 y[ring->vert_index(p1)] -= 4.0f / 3.0f;
524                                 y[ring->vert_index(e0)] -= 4.0f / 3.0f;
525                                 y[ring->vert_index(f0)] -= 4.0f / 3.0f;
526
527                         }
528                         else {
529                                 y[ring->vert_index(p1)] -= 1;
530                                 y[ring->vert_index(q1)] -= 1;
531                                 y[ring->vert_index(e0)] -= 1;
532                                 y[ring->vert_index(f0)] -= 1;
533                         }
534
535                         y /= 18.0f;
536
537                         if(ring->is_triangle()) {
538                                 x *= 3.0f / 4.0f;
539                                 y *= 3.0f / 4.0f;
540                         }
541
542                         /* this change makes the triangle boundaries smoother, but distorts the quads next to them. */
543 #if 0
544                         if(ring->is_triangle() || SubdFaceRing::is_triangle(edge->pair->face))
545                                 y *= 4.0f / 3.0f;
546 #endif
547
548                         stencil->get(interior2Indices[primitiveOffset+v]) = stencil->get(edge2Indices[primitiveOffset+v]);
549                         stencil->get(interior2Indices[primitiveOffset+v]) += x;
550                         stencil->get(interior2Indices[primitiveOffset+v]) += y;
551                 }
552         }
553 }
554
555 void SubdAccBuilder::computeBoundaryTangentStencils(SubdFaceRing *ring, SubdVert *vert, StencilMask & r0, StencilMask & r1)
556 {
557         assert(vert->is_boundary());
558         assert(r0.size() == ring->num_verts());
559         assert(r1.size() == ring->num_verts());
560
561         SubdEdge *edge0 = vert->edge;
562         assert(edge0->face == NULL);
563         assert(edge0->to() != vert);
564
565         SubdEdge *edgek = vert->edge->prev;
566         assert(edgek->face == NULL);
567         assert(edgek->from() != vert);
568
569         int valence = vert->valence();
570
571         int k = valence - 1;
572         float omega = M_PI_F / k;
573         float s = sinf(omega);
574         float c = cosf(omega);
575
576         float factor = 1.0f / (3 * k + c);
577
578         float gamma = -4 * s * factor;
579         r0[ring->vert_index(vert)] = gamma;
580         /* r1[ring->vert_index(vert)] = 0; */
581
582         float salpha0 = -((1 + 2 * c) * sqrtf(1 + c)) * factor / sqrtf(1 - c);
583         float calpha0 = 1.0f / 2.0f;
584
585         r0[ring->vert_index(edge0->to())] = salpha0;
586         r1[ring->vert_index(edge0->to())] = calpha0;
587
588         float salphak = salpha0;
589         float calphak = -1.0f / 2.0f;
590
591         r0[ring->vert_index(edgek->from())] = salphak;
592         r1[ring->vert_index(edgek->from())] = calphak;
593
594         int j = 0;
595         for(SubdVert::EdgeIterator it(vert->edges()); !it.isDone(); it.advance(), j++) {
596                 SubdEdge *edge = it.current();
597
598                 if(j == k) break;
599
600                 SubdVert *p = edge->to();
601                 SubdVert *q = edge->pair->prev->from();
602
603                 float alphaj = 4 * sinf(j * omega) * factor;
604                 float betaj = (sinf(j * omega) + sinf((j + 1) * omega)) * factor;
605
606                 if(j != 0)
607                         r0[ring->vert_index(p)] += alphaj;
608
609                 if(edge->pair->prev->prev->prev == edge->pair) {
610                         r0[ring->vert_index(vert)] += betaj / 3.0f;
611                         r0[ring->vert_index(edge->pair->from())] += betaj / 3.0f;
612                         r0[ring->vert_index(q)] += betaj / 3.0f;
613                 }
614                 else
615                         r0[ring->vert_index(q)] += betaj;
616         }
617
618         if(valence == 2) {
619                 /* r0 perpendicular to r1 */
620                 r0[ring->vert_index(vert)] = -4.0f / 3.0f;
621                 r0[ring->vert_index(edgek->from())] = 1.0f / 2.0f;
622                 r0[ring->vert_index(edge0->to())] = 1.0f / 2.0f;
623                 r0[ring->vert_index(edge0->next->to())] = 1.0f / 3.0f;
624         }
625 }
626
627 /* Subd Linear Builder */
628
629 SubdLinearBuilder::SubdLinearBuilder()
630 {
631 }
632
633 SubdLinearBuilder::~SubdLinearBuilder()
634 {
635 }
636
637 Patch *SubdLinearBuilder::run(SubdFace *face)
638 {
639         Patch *patch;
640         float3 *hull;
641
642         if(face->num_edges() == 3) {
643                 LinearTrianglePatch *lpatch = new LinearTrianglePatch();
644                 hull = lpatch->hull;
645                 patch = lpatch;
646         }
647         else if(face->num_edges() == 4) {
648                 LinearQuadPatch *lpatch = new LinearQuadPatch();
649                 hull = lpatch->hull;
650                 patch = lpatch;
651         }
652         else {
653                 assert(0); /* n-gons should have been split already */
654                 return NULL;
655         }
656
657         int i = 0;
658
659         for(SubdFace::EdgeIterator it(face->edge); !it.isDone(); it.advance())
660                 hull[i++] = it.current()->from()->co;
661
662         if(face->num_edges() == 4)
663                 swap(hull[2], hull[3]);
664
665         return patch;
666 }
667
668 CCL_NAMESPACE_END
669