00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024 #include "loopsubdiv.h"
00025 #include "context.h"
00026 #include "paramset.h"
00027 #include "dynload.h"
00028
00029 #include <boost/pool/object_pool.hpp>
00030
00031 using namespace lux;
00032
00033
00034 LoopSubdiv::LoopSubdiv(const Transform &o2w, bool ro,
00035 int nfaces, int nvertices,
00036 const int *vertexIndices,
00037 const Point *P,
00038 const float *uv,
00039 int nl,
00040 const boost::shared_ptr<Texture<float> > dismap,
00041 float dmscale, float dmoffset,
00042 bool dmnormalsmooth, bool dmsharpboundary)
00043 : Shape(o2w, ro), displacementMap(dismap), displacementMapScale(dmscale),
00044 displacementMapOffset(dmoffset), displacementMapNormalSmooth(dmnormalsmooth),
00045 displacementMapSharpBoundary(dmsharpboundary) {
00046 nLevels = nl;
00047 hasUV = (uv != NULL);
00048
00049
00050 int i;
00051 SDVertex *verts = new SDVertex[nvertices];
00052 for (i = 0; i < nvertices; ++i) {
00053 if (hasUV)
00054 verts[i] = SDVertex(P[i], uv[2 * i], uv[2 * i + 1]);
00055 else
00056 verts[i] = SDVertex(P[i]);
00057
00058 vertices.push_back(&verts[i]);
00059 }
00060
00061 SDFace *fs = new SDFace[nfaces];
00062 for (i = 0; i < nfaces; ++i)
00063 faces.push_back(&fs[i]);
00064
00065 const int *vp = vertexIndices;
00066 for (i = 0; i < nfaces; ++i) {
00067 SDFace *f = faces[i];
00068 for (int j = 0; j < 3; ++j) {
00069 SDVertex *v = vertices[vp[j]];
00070 f->v[j] = v;
00071 v->startFace = f;
00072 }
00073 vp += 3;
00074 }
00075
00076
00077 set<SDEdge> edges;
00078 for (i = 0; i < nfaces; ++i) {
00079 SDFace *f = faces[i];
00080 for (int edgeNum = 0; edgeNum < 3; ++edgeNum) {
00081
00082 int v0 = edgeNum, v1 = NEXT(edgeNum);
00083 SDEdge e(f->v[v0], f->v[v1]);
00084 if (edges.find(e) == edges.end()) {
00085
00086 e.f[0] = f;
00087 e.f0edgeNum = edgeNum;
00088 edges.insert(e);
00089 }
00090 else {
00091
00092 e = *edges.find(e);
00093 e.f[0]->f[e.f0edgeNum] = f;
00094 f->f[edgeNum] = e.f[0];
00095
00096
00097
00098
00099 int otherv0 = e.f[0]->vnum(f->v[v0]);
00100 int otherv1 = e.f[0]->vnum(f->v[v1]);
00101 if (PREV(otherv0) != otherv1) {
00102 luxError(LUX_CONSISTENCY, LUX_ERROR, "Inconsistent vertex winding in mesh, aborting subdivision.");
00103
00104 nLevels = 0;
00105 return;
00106 };
00107 edges.erase(e);
00108 }
00109 }
00110 }
00111
00112
00113 for (i = 0; i < nvertices; ++i) {
00114 SDVertex *v = vertices[i];
00115 SDFace *f = v->startFace;
00116 do {
00117 f = f->nextFace(v);
00118 } while (f && f != v->startFace);
00119 v->boundary = (f == NULL);
00120 if (!v->boundary && v->valence() == 6)
00121 v->regular = true;
00122 else if (v->boundary && v->valence() == 4)
00123 v->regular = true;
00124 else
00125 v->regular = false;
00126 }
00127 }
00128
00129 LoopSubdiv::~LoopSubdiv() {
00130 delete[] vertices[0];
00131 delete[] faces[0];
00132 }
00133
00134 BBox LoopSubdiv::ObjectBound() const {
00135
00136 BBox b;
00137 for (u_int i = 0; i < vertices.size(); i++)
00138 b = Union(b, vertices[i]->P);
00139 return b;
00140 }
00141
00142 BBox LoopSubdiv::WorldBound() const {
00143
00144 BBox b;
00145 for (u_int i = 0; i < vertices.size(); i++)
00146 b = Union(b, ObjectToWorld(vertices[i]->P));
00147 return b;
00148 }
00149
00150 bool LoopSubdiv::CanIntersect() const {
00151 return false;
00152 }
00153
00154 boost::shared_ptr<LoopSubdiv::SubdivResult> LoopSubdiv::Refine() const {
00155
00156
00157 if (nLevels < 1) {
00158 return boost::shared_ptr<LoopSubdiv::SubdivResult>((LoopSubdiv::SubdivResult*)NULL);
00159 }
00160
00161 std::stringstream ss;
00162 ss << "Applying " << nLevels << " levels of loop subdivision to " << faces.size() << " triangles";
00163 luxError(LUX_NOERROR, LUX_INFO, ss.str().c_str());
00164
00165 vector<SDFace *> f = faces;
00166 vector<SDVertex *> v = vertices;
00167 boost::object_pool<SDVertex> vertexArena;
00168 boost::object_pool<SDFace> faceArena;
00169
00170 for (int i = 0; i < nLevels; ++i) {
00171
00172 vector<SDFace *> newFaces;
00173 vector<SDVertex *> newVertices;
00174
00175
00176 for (u_int j = 0; j < v.size(); ++j) {
00177 v[j]->child = vertexArena.malloc();
00178 v[j]->child->regular = v[j]->regular;
00179 v[j]->child->boundary = v[j]->boundary;
00180 newVertices.push_back(v[j]->child);
00181 }
00182 for (u_int j = 0; j < f.size(); ++j)
00183 for (int k = 0; k < 4; ++k) {
00184 f[j]->children[k] = faceArena.malloc();
00185 newFaces.push_back(f[j]->children[k]);
00186 }
00187
00188
00189
00190 for (u_int j = 0; j < v.size(); ++j) {
00191 if (!v[j]->boundary) {
00192
00193 if (v[j]->regular)
00194 weightOneRing(v[j]->child, v[j], 1.f/16.f);
00195 else
00196 weightOneRing(v[j]->child, v[j], beta(v[j]->valence()));
00197 } else {
00198
00199 weightBoundary(v[j]->child, v[j], 1.f/8.f);
00200 }
00201 }
00202
00203
00204 map<SDEdge, SDVertex *> edgeVerts;
00205 for (u_int j = 0; j < f.size(); ++j) {
00206 SDFace *face = f[j];
00207 for (int k = 0; k < 3; ++k) {
00208
00209 SDEdge edge(face->v[k], face->v[NEXT(k)]);
00210 SDVertex *vert = edgeVerts[edge];
00211 if (!vert) {
00212
00213 vert = vertexArena.malloc();
00214 newVertices.push_back(vert);
00215 vert->regular = true;
00216 vert->boundary = (face->f[k] == NULL);
00217 vert->startFace = face->children[3];
00218
00219 if (vert->boundary) {
00220 vert->P = 0.5f * edge.v[0]->P;
00221 vert->P += 0.5f * edge.v[1]->P;
00222
00223 vert->u = 0.5f * (edge.v[0]->u + edge.v[1]->u);
00224 vert->v = 0.5f * (edge.v[0]->v + edge.v[1]->v);
00225 } else {
00226 vert->P = 3.f/8.f * edge.v[0]->P;
00227 vert->P += 3.f/8.f * edge.v[1]->P;
00228 SDVertex *ov1 = face->otherVert(edge.v[0], edge.v[1]);
00229 vert->P += 1.f/8.f * ov1->P;
00230 SDVertex *ov2 = face->f[k]->otherVert(edge.v[0], edge.v[1]);
00231 vert->P += 1.f/8.f * ov2->P;
00232
00233 vert->u = 3.f/8.f * edge.v[0]->u;
00234 vert->u += 3.f/8.f * edge.v[1]->u;
00235 vert->u += 1.f/8.f * ov1->u;
00236 vert->u += 1.f/8.f * ov2->u;
00237
00238 vert->v = 3.f/8.f * edge.v[0]->v;
00239 vert->v += 3.f/8.f * edge.v[1]->v;
00240 vert->v += 1.f/8.f * ov1->v;
00241 vert->v += 1.f/8.f * ov2->v;
00242 }
00243 edgeVerts[edge] = vert;
00244 }
00245 }
00246 }
00247
00248
00249
00250 for (u_int j = 0; j < v.size(); ++j) {
00251 SDVertex *vert = v[j];
00252 int vertNum = vert->startFace->vnum(vert);
00253 vert->child->startFace =
00254 vert->startFace->children[vertNum];
00255 }
00256
00257
00258 for (u_int j = 0; j < f.size(); ++j) {
00259 SDFace *face = f[j];
00260 for (int k = 0; k < 3; ++k) {
00261
00262 face->children[3]->f[k] = face->children[NEXT(k)];
00263 face->children[k]->f[NEXT(k)] = face->children[3];
00264
00265 SDFace *f2 = face->f[k];
00266 face->children[k]->f[k] =
00267 f2 ? f2->children[f2->vnum(face->v[k])] : NULL;
00268 f2 = face->f[PREV(k)];
00269 face->children[k]->f[PREV(k)] =
00270 f2 ? f2->children[f2->vnum(face->v[k])] : NULL;
00271 }
00272 }
00273
00274
00275 for (u_int j = 0; j < f.size(); ++j) {
00276 SDFace *face = f[j];
00277 for (int k = 0; k < 3; ++k) {
00278
00279 face->children[k]->v[k] = face->v[k]->child;
00280
00281 SDVertex *vert =
00282 edgeVerts[SDEdge(face->v[k], face->v[NEXT(k)])];
00283 face->children[k]->v[NEXT(k)] = vert;
00284 face->children[NEXT(k)]->v[k] = vert;
00285 face->children[3]->v[k] = vert;
00286 }
00287 }
00288
00289
00290 f = newFaces;
00291 v = newVertices;
00292 }
00293
00294
00295 SDVertex *Vlimit = new SDVertex[v.size()];
00296 for (u_int i = 0; i < v.size(); ++i) {
00297 if (v[i]->boundary)
00298 weightBoundary(&Vlimit[i], v[i], 1.f/5.f);
00299 else
00300 weightOneRing(&Vlimit[i], v[i], gamma(v[i]->valence()));
00301 }
00302 for (u_int i = 0; i < v.size(); ++i) {
00303 v[i]->P = Vlimit[i].P;
00304 v[i]->u = Vlimit[i].u;
00305 v[i]->v = Vlimit[i].v;
00306 }
00307 delete[] Vlimit;
00308
00309
00310 u_int ntris = u_int(f.size());
00311 u_int nverts = u_int(v.size());
00312 int *verts = new int[3*ntris];
00313 int *vp = verts;
00314 map<SDVertex *, int> usedVerts;
00315 for (u_int i = 0; i < nverts; ++i)
00316 usedVerts[v[i]] = i;
00317 for (u_int i = 0; i < ntris; ++i) {
00318 for (int j = 0; j < 3; ++j) {
00319 *vp = usedVerts[f[i]->v[j]];
00320 ++vp;
00321 }
00322 }
00323
00324
00325 Normal* Ns = new Normal[ nverts ];
00326 GenerateNormals(v, Ns);
00327
00328
00329 float *UVlimit = NULL;
00330 if (hasUV) {
00331 UVlimit = new float[2 * nverts];
00332 for (u_int i = 0; i < nverts; ++i) {
00333 UVlimit[2 * i] = v[i]->u;
00334 UVlimit[2 * i + 1] = v[i]->v;
00335 }
00336 }
00337
00338 ss.str("");
00339 ss << "Subdivision complete, got " << ntris << " triangles";
00340 luxError(LUX_NOERROR, LUX_INFO, ss.str().c_str());
00341
00342 if (displacementMap.get() != NULL) {
00343
00344
00345 ApplyDisplacementMap(v, Ns, UVlimit);
00346
00347 if (displacementMapNormalSmooth) {
00348
00349 GenerateNormals(v, Ns);
00350 }
00351 }
00352
00353
00354 Point *Plimit = new Point[nverts];
00355 for (u_int i = 0; i < nverts; ++i)
00356 Plimit[i] = v[i]->P;
00357
00358 if( !displacementMapNormalSmooth ) {
00359 delete[] Ns;
00360 Ns = NULL;
00361 }
00362
00363 return boost::shared_ptr<SubdivResult>(new SubdivResult(ntris, nverts, verts, Plimit, Ns, UVlimit));
00364 }
00365
00366 void LoopSubdiv::Refine(vector<boost::shared_ptr<Shape> > &refined) const {
00367 if(refinedShape) {
00368 refined.push_back(refinedShape);
00369 return;
00370 }
00371
00372 ParamSet paramSet;
00373
00374 {
00375 boost::shared_ptr<SubdivResult> res = Refine();
00376
00377 paramSet.AddInt("indices", res->indices, 3 * res->ntris);
00378 paramSet.AddPoint("P", res->P, res->nverts);
00379 paramSet.AddNormal("N", res->N, res->nverts);
00380 if (res->uv)
00381 paramSet.AddFloat("uv", res->uv, 2 * res->nverts);
00382 }
00383
00384 this->refinedShape = MakeShape("trianglemesh", ObjectToWorld,
00385 reverseOrientation, paramSet);
00386 refined.push_back(this->refinedShape);
00387 }
00388
00389 void LoopSubdiv::GenerateNormals(const vector<SDVertex *> v, Normal *Ns) {
00390
00391 int ringSize = 16;
00392 Point *Pring = new Point[ringSize];
00393 for (u_int i = 0; i < v.size(); ++i) {
00394 SDVertex *vert = v[i];
00395 Vector S(0,0,0), T(0,0,0);
00396 int valence = vert->valence();
00397 if (valence > ringSize) {
00398 ringSize = valence;
00399 delete[] Pring;
00400 Pring = new Point[ringSize];
00401 }
00402 vert->oneRing(Pring);
00403
00404 if (!vert->boundary) {
00405
00406 for (int k = 0; k < valence; ++k) {
00407 S += cosf(2.f*M_PI*k/valence) * Vector(Pring[k]);
00408 T += sinf(2.f*M_PI*k/valence) * Vector(Pring[k]);
00409 }
00410 } else {
00411
00412 S = Pring[valence-1] - Pring[0];
00413 if (valence == 2)
00414 T = Vector(Pring[0] + Pring[1] - 2 * vert->P);
00415 else if (valence == 3)
00416 T = Pring[1] - vert->P;
00417 else if (valence == 4)
00418 T = Vector(-1*Pring[0] + 2*Pring[1] + 2*Pring[2] +
00419 -1*Pring[3] + -2*vert->P);
00420 else {
00421 float theta = M_PI / float(valence-1);
00422 T = Vector(sinf(theta) * (Pring[0] + Pring[valence-1]));
00423 for (int k = 1; k < valence-1; ++k) {
00424 float wt = (2*cosf(theta) - 2) * sinf((k) * theta);
00425 T += Vector(wt * Pring[k]);
00426 }
00427 T = -T;
00428 }
00429 }
00430 Ns[i] = Normal(Cross(T, S));
00431 }
00432 }
00433
00434 void LoopSubdiv::ApplyDisplacementMap(
00435 const vector<SDVertex *> verts,
00436 const Normal *norms,
00437 const float *uvs) const {
00438
00439 std::stringstream ss;
00440 ss << "Applying displacement map to " << verts.size() << " vertices";
00441 luxError(LUX_NOERROR, LUX_INFO, ss.str().c_str());
00442
00443 for (u_int i = 0; i < verts.size(); i++) {
00444 Point pp = ObjectToWorld(verts[i]->P);
00445 Normal nn = Normalize(norms[i]);
00446 Vector dpdu, dpdv;
00447 CoordinateSystem(Vector(nn), &dpdu, &dpdv);
00448
00449 float u, v;
00450 if (uvs != NULL) {
00451 u = uvs[2 * i];
00452 v = uvs[2 * i + 1];
00453 } else {
00454 u = pp.x;
00455 v = pp.y;
00456 }
00457
00458 DifferentialGeometry dg = DifferentialGeometry(
00459 pp,
00460 nn,
00461 dpdu, dpdv,
00462 Normal(0, 0, 0), Normal(0, 0, 0),
00463 u, v, this);
00464
00465 Vector displacement(nn);
00466 displacement *= - (
00467 displacementMap.get()->Evaluate(NULL, dg) * displacementMapScale +
00468 displacementMapOffset);
00469
00470 verts[i]->P += displacement;
00471 }
00472 }
00473
00474 void LoopSubdiv::weightOneRing(SDVertex *destVert, SDVertex *vert, float beta) const {
00475
00476 int valence = vert->valence();
00477 SDVertex **Vring = (SDVertex **)alloca(valence * sizeof(SDVertex *));
00478 vert->oneRing(Vring);
00479
00480 Point P = (1 - valence * beta) * vert->P;
00481 float u = (1 - valence * beta) * vert->u;
00482 float v = (1 - valence * beta) * vert->v;
00483
00484 for (int i = 0; i < valence; ++i) {
00485 P += beta * Vring[i]->P;
00486 u += beta * Vring[i]->u;
00487 v += beta * Vring[i]->v;
00488 }
00489
00490 destVert->P = P;
00491 destVert->u = u;
00492 destVert->v = v;
00493 }
00494
00495 void SDVertex::oneRing(SDVertex **V) {
00496 if (!boundary) {
00497
00498 SDFace *face = startFace;
00499 do {
00500 *V = face->nextVert(this);
00501 V++;
00502 face = face->nextFace(this);
00503 } while (face != startFace);
00504 } else {
00505
00506 SDFace *face = startFace, *f2;
00507 while ((f2 = face->nextFace(this)) != NULL)
00508 face = f2;
00509 *V = face->nextVert(this);
00510 V++;
00511 do {
00512 *V = face->prevVert(this);
00513 V++;
00514 face = face->prevFace(this);
00515 } while (face != NULL);
00516 }
00517 }
00518
00519 void SDVertex::oneRing(Point *P) {
00520 if (!boundary) {
00521
00522 SDFace *face = startFace;
00523 do {
00524 *P++ = face->nextVert(this)->P;
00525 face = face->nextFace(this);
00526 } while (face != startFace);
00527 } else {
00528
00529 SDFace *face = startFace, *f2;
00530 while ((f2 = face->nextFace(this)) != NULL)
00531 face = f2;
00532 *P++ = face->nextVert(this)->P;
00533 do {
00534 *P++ = face->prevVert(this)->P;
00535 face = face->prevFace(this);
00536 } while (face != NULL);
00537 }
00538 }
00539
00540 void LoopSubdiv::weightBoundary(SDVertex *destVert, SDVertex *vert,
00541 float beta) const {
00542
00543 int valence = vert->valence();
00544 SDVertex **Vring = (SDVertex **)alloca(valence * sizeof(SDVertex *));
00545 vert->oneRing(Vring);
00546
00547 if(!displacementMapSharpBoundary) {
00548 Point P = (1 - 2 * beta) * vert->P;
00549 P += beta * Vring[0]->P;
00550 P += beta * Vring[valence - 1]->P;
00551 destVert->P = P;
00552 } else
00553 destVert->P = vert->P;
00554
00555 float u = (1 - 2 * beta) * vert->u;
00556 float v = (1 - 2 * beta) * vert->v;
00557 u += beta * Vring[0]->u;
00558 v += beta * Vring[0]->v;
00559 u += beta * Vring[valence - 1]->u;
00560 v += beta * Vring[valence - 1]->v;
00561
00562 destVert->u = u;
00563 destVert->v = v;
00564 }
00565
00566 Shape *LoopSubdiv::CreateShape(
00567 const Transform &o2w,
00568 bool reverseOrientation,
00569 const ParamSet ¶ms)
00570 {
00571 map<string, boost::shared_ptr<Texture<float> > > *floatTextures = Context::getActiveFloatTextures();
00572 int nlevels = params.FindOneInt("nlevels", 3);
00573 int nps, nIndices, nuvi;
00574 const int *vi = params.FindInt("indices", &nIndices);
00575 const Point *P = params.FindPoint("P", &nps);
00576 if (!vi || !P) return NULL;
00577
00578 const float *uvs = params.FindFloat("uv", &nuvi);
00579
00580
00581 string displacementMapName = params.FindOneString("displacementmap", "");
00582 float displacementMapScale = params.FindOneFloat("dmscale", 0.1f);
00583 float displacementMapOffset = params.FindOneFloat("dmoffset", 0.0f);
00584 bool displacementMapNormalSmooth = params.FindOneBool("dmnormalsmooth", true);
00585 bool displacementMapSharpBoundary = params.FindOneBool("dmsharpboundary", false);
00586
00587 boost::shared_ptr<Texture<float> > displacementMap;
00588 if (displacementMapName != "") {
00589 displacementMap = (*floatTextures)[displacementMapName];
00590
00591 if (displacementMap.get() == NULL) {
00592 std::stringstream ss;
00593 ss << "Unknown float texture '" << displacementMapName << "' in a LoopSubdiv shape.";
00594 luxError(LUX_SYNTAX, LUX_WARNING, ss.str().c_str());
00595 }
00596 }
00597
00598
00599 string scheme = params.FindOneString("scheme", "loop");
00600
00601 return new LoopSubdiv(o2w, reverseOrientation, nIndices/3, nps,
00602 vi, P, uvs, nlevels, displacementMap,
00603 displacementMapScale, displacementMapOffset,
00604 displacementMapNormalSmooth, displacementMapSharpBoundary);
00605 }
00606
00607
00608