From fd25e883e2807a151f673b87c152a59701a0df80 Mon Sep 17 00:00:00 2001 From: Brecht Van Lommel Date: Sun, 24 Oct 2021 14:19:19 +0200 Subject: Cycles: remove prefix from source code file names Remove prefix of filenames that is the same as the folder name. This used to help when #includes were using individual files, but now they are always relative to the cycles root directory and so the prefixes are redundant. For patches and branches, git merge and rebase should be able to detect the renames and move over code to the right file. --- intern/cycles/subd/CMakeLists.txt | 18 +- intern/cycles/subd/dice.cpp | 283 ++++++++++++ intern/cycles/subd/dice.h | 103 +++++ intern/cycles/subd/patch.cpp | 121 ++++++ intern/cycles/subd/patch.h | 63 +++ intern/cycles/subd/patch_table.cpp | 295 +++++++++++++ intern/cycles/subd/patch_table.h | 64 +++ intern/cycles/subd/split.cpp | 748 ++++++++++++++++++++++++++++++++ intern/cycles/subd/split.h | 75 ++++ intern/cycles/subd/subd_dice.cpp | 283 ------------ intern/cycles/subd/subd_dice.h | 103 ----- intern/cycles/subd/subd_patch.cpp | 121 ------ intern/cycles/subd/subd_patch.h | 63 --- intern/cycles/subd/subd_patch_table.cpp | 295 ------------- intern/cycles/subd/subd_patch_table.h | 64 --- intern/cycles/subd/subd_split.cpp | 748 -------------------------------- intern/cycles/subd/subd_split.h | 75 ---- intern/cycles/subd/subd_subpatch.h | 219 ---------- intern/cycles/subd/subpatch.h | 219 ++++++++++ 19 files changed, 1980 insertions(+), 1980 deletions(-) create mode 100644 intern/cycles/subd/dice.cpp create mode 100644 intern/cycles/subd/dice.h create mode 100644 intern/cycles/subd/patch.cpp create mode 100644 intern/cycles/subd/patch.h create mode 100644 intern/cycles/subd/patch_table.cpp create mode 100644 intern/cycles/subd/patch_table.h create mode 100644 intern/cycles/subd/split.cpp create mode 100644 intern/cycles/subd/split.h delete mode 100644 intern/cycles/subd/subd_dice.cpp delete mode 100644 intern/cycles/subd/subd_dice.h delete mode 100644 intern/cycles/subd/subd_patch.cpp delete mode 100644 intern/cycles/subd/subd_patch.h delete mode 100644 intern/cycles/subd/subd_patch_table.cpp delete mode 100644 intern/cycles/subd/subd_patch_table.h delete mode 100644 intern/cycles/subd/subd_split.cpp delete mode 100644 intern/cycles/subd/subd_split.h delete mode 100644 intern/cycles/subd/subd_subpatch.h create mode 100644 intern/cycles/subd/subpatch.h (limited to 'intern/cycles/subd') diff --git a/intern/cycles/subd/CMakeLists.txt b/intern/cycles/subd/CMakeLists.txt index c697ddb9891..4bf5503dc4b 100644 --- a/intern/cycles/subd/CMakeLists.txt +++ b/intern/cycles/subd/CMakeLists.txt @@ -21,18 +21,18 @@ set(INC_SYS ) set(SRC - subd_dice.cpp - subd_patch.cpp - subd_split.cpp - subd_patch_table.cpp + dice.cpp + patch.cpp + split.cpp + patch_table.cpp ) set(SRC_HEADERS - subd_dice.h - subd_patch.h - subd_patch_table.h - subd_split.h - subd_subpatch.h + dice.h + patch.h + patch_table.h + split.h + subpatch.h ) set(LIB diff --git a/intern/cycles/subd/dice.cpp b/intern/cycles/subd/dice.cpp new file mode 100644 index 00000000000..461fa0bcd9c --- /dev/null +++ b/intern/cycles/subd/dice.cpp @@ -0,0 +1,283 @@ +/* + * Copyright 2011-2013 Blender Foundation + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +#include "scene/camera.h" +#include "scene/mesh.h" + +#include "subd/dice.h" +#include "subd/patch.h" + +CCL_NAMESPACE_BEGIN + +/* EdgeDice Base */ + +EdgeDice::EdgeDice(const SubdParams ¶ms_) : params(params_) +{ + mesh_P = NULL; + mesh_N = NULL; + vert_offset = 0; + + params.mesh->attributes.add(ATTR_STD_VERTEX_NORMAL); + + if (params.ptex) { + params.mesh->attributes.add(ATTR_STD_PTEX_UV); + params.mesh->attributes.add(ATTR_STD_PTEX_FACE_ID); + } +} + +void EdgeDice::reserve(int num_verts, int num_triangles) +{ + Mesh *mesh = params.mesh; + + vert_offset = mesh->get_verts().size(); + tri_offset = mesh->num_triangles(); + + mesh->resize_mesh(mesh->get_verts().size() + num_verts, mesh->num_triangles()); + mesh->reserve_mesh(mesh->get_verts().size() + num_verts, mesh->num_triangles() + num_triangles); + + Attribute *attr_vN = mesh->attributes.add(ATTR_STD_VERTEX_NORMAL); + + mesh_P = mesh->verts.data() + vert_offset; + mesh_N = attr_vN->data_float3() + vert_offset; + + params.mesh->num_subd_verts += num_verts; +} + +void EdgeDice::set_vert(Patch *patch, int index, float2 uv) +{ + float3 P, N; + + patch->eval(&P, NULL, NULL, &N, uv.x, uv.y); + + assert(index < params.mesh->verts.size()); + + mesh_P[index] = P; + mesh_N[index] = N; + params.mesh->vert_patch_uv[index + vert_offset] = make_float2(uv.x, uv.y); +} + +void EdgeDice::add_triangle(Patch *patch, int v0, int v1, int v2) +{ + Mesh *mesh = params.mesh; + + mesh->add_triangle(v0 + vert_offset, v1 + vert_offset, v2 + vert_offset, patch->shader, true); + params.mesh->triangle_patch[params.mesh->num_triangles() - 1] = patch->patch_index; + + tri_offset++; +} + +void EdgeDice::stitch_triangles(Subpatch &sub, int edge) +{ + int Mu = max(sub.edge_u0.T, sub.edge_u1.T); + int Mv = max(sub.edge_v0.T, sub.edge_v1.T); + Mu = max(Mu, 2); + Mv = max(Mv, 2); + + int outer_T = sub.edges[edge].T; + int inner_T = ((edge % 2) == 0) ? Mv - 2 : Mu - 2; + + if (inner_T < 0 || outer_T < 0) + return; // XXX avoid crashes for Mu or Mv == 1, missing polygons + + /* stitch together two arrays of verts with triangles. at each step, + * we compare using the next verts on both sides, to find the split + * direction with the smallest diagonal, and use that in order to keep + * the triangle shape reasonable. */ + for (size_t i = 0, j = 0; i < inner_T || j < outer_T;) { + int v0, v1, v2; + + v0 = sub.get_vert_along_grid_edge(edge, i); + v1 = sub.get_vert_along_edge(edge, j); + + if (j == outer_T) { + v2 = sub.get_vert_along_grid_edge(edge, ++i); + } + else if (i == inner_T) { + v2 = sub.get_vert_along_edge(edge, ++j); + } + else { + /* length of diagonals */ + float len1 = len_squared(mesh_P[sub.get_vert_along_grid_edge(edge, i)] - + mesh_P[sub.get_vert_along_edge(edge, j + 1)]); + float len2 = len_squared(mesh_P[sub.get_vert_along_edge(edge, j)] - + mesh_P[sub.get_vert_along_grid_edge(edge, i + 1)]); + + /* use smallest diagonal */ + if (len1 < len2) + v2 = sub.get_vert_along_edge(edge, ++j); + else + v2 = sub.get_vert_along_grid_edge(edge, ++i); + } + + add_triangle(sub.patch, v1, v0, v2); + } +} + +/* QuadDice */ + +QuadDice::QuadDice(const SubdParams ¶ms_) : EdgeDice(params_) +{ +} + +float2 QuadDice::map_uv(Subpatch &sub, float u, float v) +{ + /* map UV from subpatch to patch parametric coordinates */ + float2 d0 = interp(sub.c00, sub.c01, v); + float2 d1 = interp(sub.c10, sub.c11, v); + return interp(d0, d1, u); +} + +float3 QuadDice::eval_projected(Subpatch &sub, float u, float v) +{ + float2 uv = map_uv(sub, u, v); + float3 P; + + sub.patch->eval(&P, NULL, NULL, NULL, uv.x, uv.y); + if (params.camera) + P = transform_perspective(¶ms.camera->worldtoraster, P); + + return P; +} + +void QuadDice::set_vert(Subpatch &sub, int index, float u, float v) +{ + EdgeDice::set_vert(sub.patch, index, map_uv(sub, u, v)); +} + +void QuadDice::set_side(Subpatch &sub, int edge) +{ + int t = sub.edges[edge].T; + + /* set verts on the edge of the patch */ + for (int i = 0; i < t; i++) { + float f = i / (float)t; + + float u, v; + switch (edge) { + case 0: + u = 0; + v = f; + break; + case 1: + u = f; + v = 1; + break; + case 2: + u = 1; + v = 1.0f - f; + break; + case 3: + default: + u = 1.0f - f; + v = 0; + break; + } + + set_vert(sub, sub.get_vert_along_edge(edge, i), u, v); + } +} + +float QuadDice::quad_area(const float3 &a, const float3 &b, const float3 &c, const float3 &d) +{ + return triangle_area(a, b, d) + triangle_area(a, d, c); +} + +float QuadDice::scale_factor(Subpatch &sub, int Mu, int Mv) +{ + /* estimate area as 4x largest of 4 quads */ + float3 P[3][3]; + + for (int i = 0; i < 3; i++) + for (int j = 0; j < 3; j++) + P[i][j] = eval_projected(sub, i * 0.5f, j * 0.5f); + + float A1 = quad_area(P[0][0], P[1][0], P[0][1], P[1][1]); + float A2 = quad_area(P[1][0], P[2][0], P[1][1], P[2][1]); + float A3 = quad_area(P[0][1], P[1][1], P[0][2], P[1][2]); + float A4 = quad_area(P[1][1], P[2][1], P[1][2], P[2][2]); + float Apatch = max(A1, max(A2, max(A3, A4))) * 4.0f; + + /* solve for scaling factor */ + float Atri = params.dicing_rate * params.dicing_rate * 0.5f; + float Ntris = Apatch / Atri; + + // XXX does the -sqrt solution matter + // XXX max(D, 0.0) is highly suspicious, need to test cases + // where D goes negative + float N = 0.5f * (Ntris - (sub.edge_u0.T + sub.edge_u1.T + sub.edge_v0.T + sub.edge_v1.T)); + float D = 4.0f * N * Mu * Mv + (Mu + Mv) * (Mu + Mv); + float S = (Mu + Mv + sqrtf(max(D, 0.0f))) / (2 * Mu * Mv); + + return S; +} + +void QuadDice::add_grid(Subpatch &sub, int Mu, int Mv, int offset) +{ + /* create inner grid */ + float du = 1.0f / (float)Mu; + float dv = 1.0f / (float)Mv; + + for (int j = 1; j < Mv; j++) { + for (int i = 1; i < Mu; i++) { + float u = i * du; + float v = j * dv; + + set_vert(sub, offset + (i - 1) + (j - 1) * (Mu - 1), u, v); + + if (i < Mu - 1 && j < Mv - 1) { + int i1 = offset + (i - 1) + (j - 1) * (Mu - 1); + int i2 = offset + i + (j - 1) * (Mu - 1); + int i3 = offset + i + j * (Mu - 1); + int i4 = offset + (i - 1) + j * (Mu - 1); + + add_triangle(sub.patch, i1, i2, i3); + add_triangle(sub.patch, i1, i3, i4); + } + } + } +} + +void QuadDice::dice(Subpatch &sub) +{ + /* compute inner grid size with scale factor */ + int Mu = max(sub.edge_u0.T, sub.edge_u1.T); + int Mv = max(sub.edge_v0.T, sub.edge_v1.T); + +#if 0 /* Doesn't work very well, especially at grazing angles. */ + float S = scale_factor(sub, ef, Mu, Mv); +#else + float S = 1.0f; +#endif + + Mu = max((int)ceilf(S * Mu), 2); // XXX handle 0 & 1? + Mv = max((int)ceilf(S * Mv), 2); // XXX handle 0 & 1? + + /* inner grid */ + add_grid(sub, Mu, Mv, sub.inner_grid_vert_offset); + + /* sides */ + set_side(sub, 0); + set_side(sub, 1); + set_side(sub, 2); + set_side(sub, 3); + + stitch_triangles(sub, 0); + stitch_triangles(sub, 1); + stitch_triangles(sub, 2); + stitch_triangles(sub, 3); +} + +CCL_NAMESPACE_END diff --git a/intern/cycles/subd/dice.h b/intern/cycles/subd/dice.h new file mode 100644 index 00000000000..7510aae775c --- /dev/null +++ b/intern/cycles/subd/dice.h @@ -0,0 +1,103 @@ +/* + * Copyright 2011-2013 Blender Foundation + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +#ifndef __SUBD_DICE_H__ +#define __SUBD_DICE_H__ + +/* DX11 like EdgeDice implementation, with different tessellation factors for + * each edge for watertight tessellation, with subpatch remapping to work with + * DiagSplit. For more algorithm details, see the DiagSplit paper or the + * ARB_tessellation_shader OpenGL extension, Section 2.X.2. */ + +#include "util/types.h" +#include "util/vector.h" + +#include "subd/subpatch.h" + +CCL_NAMESPACE_BEGIN + +class Camera; +class Mesh; +class Patch; + +struct SubdParams { + Mesh *mesh; + bool ptex; + + int test_steps; + int split_threshold; + float dicing_rate; + int max_level; + Camera *camera; + Transform objecttoworld; + + SubdParams(Mesh *mesh_, bool ptex_ = false) + { + mesh = mesh_; + ptex = ptex_; + + test_steps = 3; + split_threshold = 1; + dicing_rate = 1.0f; + max_level = 12; + camera = NULL; + } +}; + +/* EdgeDice Base */ + +class EdgeDice { + public: + SubdParams params; + float3 *mesh_P; + float3 *mesh_N; + size_t vert_offset; + size_t tri_offset; + + explicit EdgeDice(const SubdParams ¶ms); + + void reserve(int num_verts, int num_triangles); + + void set_vert(Patch *patch, int index, float2 uv); + void add_triangle(Patch *patch, int v0, int v1, int v2); + + void stitch_triangles(Subpatch &sub, int edge); +}; + +/* Quad EdgeDice */ + +class QuadDice : public EdgeDice { + public: + explicit QuadDice(const SubdParams ¶ms); + + float3 eval_projected(Subpatch &sub, float u, float v); + + float2 map_uv(Subpatch &sub, float u, float v); + void set_vert(Subpatch &sub, int index, float u, float v); + + void add_grid(Subpatch &sub, int Mu, int Mv, int offset); + + void set_side(Subpatch &sub, int edge); + + float quad_area(const float3 &a, const float3 &b, const float3 &c, const float3 &d); + float scale_factor(Subpatch &sub, int Mu, int Mv); + + void dice(Subpatch &sub); +}; + +CCL_NAMESPACE_END + +#endif /* __SUBD_DICE_H__ */ diff --git a/intern/cycles/subd/patch.cpp b/intern/cycles/subd/patch.cpp new file mode 100644 index 00000000000..4d73f334c1b --- /dev/null +++ b/intern/cycles/subd/patch.cpp @@ -0,0 +1,121 @@ +/* + * Copyright 2011-2013 Blender Foundation + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +/* Parts adapted from code in the public domain in NVidia Mesh Tools. */ + +#include "scene/mesh.h" + +#include "subd/patch.h" + +#include "util/math.h" +#include "util/types.h" + +CCL_NAMESPACE_BEGIN + +/* De Casteljau Evaluation */ + +static void decasteljau_cubic(float3 *P, float3 *dt, float t, const float3 cp[4]) +{ + float3 d0 = cp[0] + t * (cp[1] - cp[0]); + float3 d1 = cp[1] + t * (cp[2] - cp[1]); + float3 d2 = cp[2] + t * (cp[3] - cp[2]); + + d0 += t * (d1 - d0); + d1 += t * (d2 - d1); + + *P = d0 + t * (d1 - d0); + if (dt) + *dt = d1 - d0; +} + +static void decasteljau_bicubic( + float3 *P, float3 *du, float3 *dv, const float3 cp[16], float u, float v) +{ + float3 ucp[4], utn[4]; + + /* interpolate over u */ + decasteljau_cubic(ucp + 0, utn + 0, u, cp); + decasteljau_cubic(ucp + 1, utn + 1, u, cp + 4); + decasteljau_cubic(ucp + 2, utn + 2, u, cp + 8); + decasteljau_cubic(ucp + 3, utn + 3, u, cp + 12); + + /* interpolate over v */ + decasteljau_cubic(P, dv, v, ucp); + if (du) + decasteljau_cubic(du, NULL, v, utn); +} + +/* Linear Quad Patch */ + +void LinearQuadPatch::eval(float3 *P, float3 *dPdu, float3 *dPdv, float3 *N, float u, float v) +{ + float3 d0 = interp(hull[0], hull[1], u); + float3 d1 = interp(hull[2], hull[3], u); + + *P = interp(d0, d1, v); + + if (dPdu && dPdv) { + *dPdu = interp(hull[1] - hull[0], hull[3] - hull[2], v); + *dPdv = interp(hull[2] - hull[0], hull[3] - hull[1], u); + } + + if (N) { + *N = normalize( + interp(interp(normals[0], normals[1], u), interp(normals[2], normals[3], u), v)); + } +} + +BoundBox LinearQuadPatch::bound() +{ + BoundBox bbox = BoundBox::empty; + + for (int i = 0; i < 4; i++) + bbox.grow(hull[i]); + + return bbox; +} + +/* Bicubic Patch */ + +void BicubicPatch::eval(float3 *P, float3 *dPdu, float3 *dPdv, float3 *N, float u, float v) +{ + if (N) { + float3 dPdu_, dPdv_; + decasteljau_bicubic(P, &dPdu_, &dPdv_, hull, u, v); + + if (dPdu && dPdv) { + *dPdu = dPdu_; + *dPdv = dPdv_; + } + + *N = normalize(cross(dPdu_, dPdv_)); + } + else { + decasteljau_bicubic(P, dPdu, dPdv, hull, u, v); + } +} + +BoundBox BicubicPatch::bound() +{ + BoundBox bbox = BoundBox::empty; + + for (int i = 0; i < 16; i++) + bbox.grow(hull[i]); + + return bbox; +} + +CCL_NAMESPACE_END diff --git a/intern/cycles/subd/patch.h b/intern/cycles/subd/patch.h new file mode 100644 index 00000000000..ad4dc1bd8e9 --- /dev/null +++ b/intern/cycles/subd/patch.h @@ -0,0 +1,63 @@ +/* + * Copyright 2011-2013 Blender Foundation + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +#ifndef __SUBD_PATCH_H__ +#define __SUBD_PATCH_H__ + +#include "util/boundbox.h" +#include "util/types.h" + +CCL_NAMESPACE_BEGIN + +class Patch { + public: + Patch() : patch_index(0), shader(0), from_ngon(false) + { + } + + virtual ~Patch() = default; + + virtual void eval(float3 *P, float3 *dPdu, float3 *dPdv, float3 *N, float u, float v) = 0; + + int patch_index; + int shader; + bool from_ngon; +}; + +/* Linear Quad Patch */ + +class LinearQuadPatch : public Patch { + public: + float3 hull[4]; + float3 normals[4]; + + void eval(float3 *P, float3 *dPdu, float3 *dPdv, float3 *N, float u, float v); + BoundBox bound(); +}; + +/* Bicubic Patch */ + +class BicubicPatch : public Patch { + public: + float3 hull[16]; + + void eval(float3 *P, float3 *dPdu, float3 *dPdv, float3 *N, float u, float v); + BoundBox bound(); +}; + +CCL_NAMESPACE_END + +#endif /* __SUBD_PATCH_H__ */ diff --git a/intern/cycles/subd/patch_table.cpp b/intern/cycles/subd/patch_table.cpp new file mode 100644 index 00000000000..d215dfaa1dd --- /dev/null +++ b/intern/cycles/subd/patch_table.cpp @@ -0,0 +1,295 @@ +/* + * Based on code from OpenSubdiv released under this license: + * + * Copyright 2014 DreamWorks Animation LLC. + * + * Licensed under the Apache License, Version 2.0 (the "Apache License") + * with the following modification; you may not use this file except in + * compliance with the Apache License and the following modification to it: + * Section 6. Trademarks. is deleted and replaced with: + * + * 6. Trademarks. This License does not grant permission to use the trade + * names, trademarks, service marks, or product names of the Licensor + * and its affiliates, except as required to comply with Section 4(c) of + * the License and to reproduce the content of the NOTICE file. + * + * You may obtain a copy of the Apache License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the Apache License with the above modification is + * distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY + * KIND, either express or implied. See the Apache License for the specific + * language governing permissions and limitations under the Apache License. + */ + +#include "subd/patch_table.h" +#include "kernel/types.h" + +#include "util/math.h" + +#ifdef WITH_OPENSUBDIV +# include +#endif + +CCL_NAMESPACE_BEGIN + +#ifdef WITH_OPENSUBDIV + +using namespace OpenSubdiv; + +/* functions for building patch maps */ + +struct PatchMapQuadNode { + /* sets all the children to point to the patch of index */ + void set_child(int index) + { + for (int i = 0; i < 4; i++) { + children[i] = index | PATCH_MAP_NODE_IS_SET | PATCH_MAP_NODE_IS_LEAF; + } + } + + /* sets the child in quadrant to point to the node or patch of the given index */ + void set_child(unsigned char quadrant, int index, bool is_leaf = true) + { + assert(quadrant < 4); + children[quadrant] = index | PATCH_MAP_NODE_IS_SET | (is_leaf ? PATCH_MAP_NODE_IS_LEAF : 0); + } + + uint children[4]; +}; + +template static int resolve_quadrant(T &median, T &u, T &v) +{ + int quadrant = -1; + + if (u < median) { + if (v < median) { + quadrant = 0; + } + else { + quadrant = 1; + v -= median; + } + } + else { + if (v < median) { + quadrant = 3; + } + else { + quadrant = 2; + v -= median; + } + u -= median; + } + + return quadrant; +} + +static void build_patch_map(PackedPatchTable &table, + OpenSubdiv::Far::PatchTable *patch_table, + int offset) +{ + int num_faces = 0; + + for (int array = 0; array < table.num_arrays; array++) { + Far::ConstPatchParamArray params = patch_table->GetPatchParams(array); + + for (int j = 0; j < patch_table->GetNumPatches(array); j++) { + num_faces = max(num_faces, (int)params[j].GetFaceId()); + } + } + num_faces++; + + vector quadtree; + quadtree.reserve(num_faces + table.num_patches); + quadtree.resize(num_faces); + + /* adjust offsets to make indices relative to the table */ + int handle_index = -(table.num_patches * PATCH_HANDLE_SIZE); + offset += table.total_size(); + + /* populate the quadtree from the FarPatchArrays sub-patches */ + for (int array = 0; array < table.num_arrays; array++) { + Far::ConstPatchParamArray params = patch_table->GetPatchParams(array); + + for (int i = 0; i < patch_table->GetNumPatches(array); + i++, handle_index += PATCH_HANDLE_SIZE) { + const Far::PatchParam ¶m = params[i]; + unsigned short depth = param.GetDepth(); + + PatchMapQuadNode *node = &quadtree[params[i].GetFaceId()]; + + if (depth == (param.NonQuadRoot() ? 1 : 0)) { + /* special case : regular BSpline face w/ no sub-patches */ + node->set_child(handle_index + offset); + continue; + } + + int u = param.GetU(); + int v = param.GetV(); + int pdepth = param.NonQuadRoot() ? depth - 2 : depth - 1; + int half = 1 << pdepth; + + for (int j = 0; j < depth; j++) { + int delta = half >> 1; + + int quadrant = resolve_quadrant(half, u, v); + assert(quadrant >= 0); + + half = delta; + + if (j == pdepth) { + /* we have reached the depth of the sub-patch : add a leaf */ + assert(!(node->children[quadrant] & PATCH_MAP_NODE_IS_SET)); + node->set_child(quadrant, handle_index + offset, true); + break; + } + else { + /* travel down the child node of the corresponding quadrant */ + if (!(node->children[quadrant] & PATCH_MAP_NODE_IS_SET)) { + /* create a new branch in the quadrant */ + quadtree.push_back(PatchMapQuadNode()); + + int idx = (int)quadtree.size() - 1; + node->set_child(quadrant, idx * 4 + offset, false); + + node = &quadtree[idx]; + } + else { + /* travel down an existing branch */ + uint idx = node->children[quadrant] & PATCH_MAP_NODE_INDEX_MASK; + node = &(quadtree[(idx - offset) / 4]); + } + } + } + } + } + + /* copy into table */ + assert(table.table.size() == table.total_size()); + uint map_offset = table.total_size(); + + table.num_nodes = quadtree.size() * 4; + table.table.resize(table.total_size()); + + uint *data = &table.table[map_offset]; + + for (int i = 0; i < quadtree.size(); i++) { + for (int j = 0; j < 4; j++) { + assert(quadtree[i].children[j] & PATCH_MAP_NODE_IS_SET); + *(data++) = quadtree[i].children[j]; + } + } +} + +#endif + +/* packed patch table functions */ + +size_t PackedPatchTable::total_size() +{ + return num_arrays * PATCH_ARRAY_SIZE + num_indices + + num_patches * (PATCH_PARAM_SIZE + PATCH_HANDLE_SIZE) + num_nodes * PATCH_NODE_SIZE; +} + +void PackedPatchTable::pack(Far::PatchTable *patch_table, int offset) +{ + num_arrays = 0; + num_patches = 0; + num_indices = 0; + num_nodes = 0; + +#ifdef WITH_OPENSUBDIV + num_arrays = patch_table->GetNumPatchArrays(); + + for (int i = 0; i < num_arrays; i++) { + int patches = patch_table->GetNumPatches(i); + int num_control = patch_table->GetPatchArrayDescriptor(i).GetNumControlVertices(); + + num_patches += patches; + num_indices += patches * num_control; + } + + table.resize(total_size()); + uint *data = table.data(); + + uint *array = data; + uint *index = array + num_arrays * PATCH_ARRAY_SIZE; + uint *param = index + num_indices; + uint *handle = param + num_patches * PATCH_PARAM_SIZE; + + uint current_param = 0; + + for (int i = 0; i < num_arrays; i++) { + *(array++) = patch_table->GetPatchArrayDescriptor(i).GetType(); + *(array++) = patch_table->GetNumPatches(i); + *(array++) = (index - data) + offset; + *(array++) = (param - data) + offset; + + Far::ConstIndexArray indices = patch_table->GetPatchArrayVertices(i); + + for (int j = 0; j < indices.size(); j++) { + *(index++) = indices[j]; + } + + const Far::PatchParamTable ¶m_table = patch_table->GetPatchParamTable(); + + int num_control = patch_table->GetPatchArrayDescriptor(i).GetNumControlVertices(); + int patches = patch_table->GetNumPatches(i); + + for (int j = 0; j < patches; j++, current_param++) { + *(param++) = param_table[current_param].field0; + *(param++) = param_table[current_param].field1; + + *(handle++) = (array - data) - PATCH_ARRAY_SIZE + offset; + *(handle++) = (param - data) - PATCH_PARAM_SIZE + offset; + *(handle++) = j * num_control; + } + } + + build_patch_map(*this, patch_table, offset); +#else + (void)patch_table; + (void)offset; +#endif +} + +void PackedPatchTable::copy_adjusting_offsets(uint *dest, int doffset) +{ + uint *src = table.data(); + + /* arrays */ + for (int i = 0; i < num_arrays; i++) { + *(dest++) = *(src++); + *(dest++) = *(src++); + *(dest++) = *(src++) + doffset; + *(dest++) = *(src++) + doffset; + } + + /* indices */ + for (int i = 0; i < num_indices; i++) { + *(dest++) = *(src++); + } + + /* params */ + for (int i = 0; i < num_patches; i++) { + *(dest++) = *(src++); + *(dest++) = *(src++); + } + + /* handles */ + for (int i = 0; i < num_patches; i++) { + *(dest++) = *(src++) + doffset; + *(dest++) = *(src++) + doffset; + *(dest++) = *(src++); + } + + /* nodes */ + for (int i = 0; i < num_nodes; i++) { + *(dest++) = *(src++) + doffset; + } +} + +CCL_NAMESPACE_END diff --git a/intern/cycles/subd/patch_table.h b/intern/cycles/subd/patch_table.h new file mode 100644 index 00000000000..b5fd5923f31 --- /dev/null +++ b/intern/cycles/subd/patch_table.h @@ -0,0 +1,64 @@ +/* + * Copyright 2011-2016 Blender Foundation + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +#ifndef __SUBD_PATCH_TABLE_H__ +#define __SUBD_PATCH_TABLE_H__ + +#include "util/array.h" +#include "util/types.h" + +#ifdef WITH_OPENSUBDIV +# ifdef _MSC_VER +# include "iso646.h" +# endif + +# include +#endif + +CCL_NAMESPACE_BEGIN + +#ifdef WITH_OPENSUBDIV +using namespace OpenSubdiv; +#else +/* forward declare for when OpenSubdiv is unavailable */ +namespace Far { +struct PatchTable; +} +#endif + +#define PATCH_ARRAY_SIZE 4 +#define PATCH_PARAM_SIZE 2 +#define PATCH_HANDLE_SIZE 3 +#define PATCH_NODE_SIZE 1 + +struct PackedPatchTable { + array table; + + size_t num_arrays; + size_t num_indices; + size_t num_patches; + size_t num_nodes; + + /* calculated size from num_* members */ + size_t total_size(); + + void pack(Far::PatchTable *patch_table, int offset = 0); + void copy_adjusting_offsets(uint *dest, int doffset); +}; + +CCL_NAMESPACE_END + +#endif /* __SUBD_PATCH_TABLE_H__ */ diff --git a/intern/cycles/subd/split.cpp b/intern/cycles/subd/split.cpp new file mode 100644 index 00000000000..2b29f3a5a78 --- /dev/null +++ b/intern/cycles/subd/split.cpp @@ -0,0 +1,748 @@ +/* + * Copyright 2011-2013 Blender Foundation + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +#include "scene/camera.h" +#include "scene/mesh.h" + +#include "subd/dice.h" +#include "subd/patch.h" +#include "subd/split.h" + +#include "util/algorithm.h" +#include "util/foreach.h" +#include "util/hash.h" +#include "util/math.h" +#include "util/types.h" + +CCL_NAMESPACE_BEGIN + +/* DiagSplit */ + +#define DSPLIT_NON_UNIFORM -1 +#define STITCH_NGON_CENTER_VERT_INDEX_OFFSET 0x60000000 +#define STITCH_NGON_SPLIT_EDGE_CENTER_VERT_TAG (0x60000000 - 1) + +DiagSplit::DiagSplit(const SubdParams ¶ms_) : params(params_) +{ +} + +float3 DiagSplit::to_world(Patch *patch, float2 uv) +{ + float3 P; + + patch->eval(&P, NULL, NULL, NULL, uv.x, uv.y); + if (params.camera) + P = transform_point(¶ms.objecttoworld, P); + + return P; +} + +static void order_float2(float2 &a, float2 &b) +{ + if (b.x < a.x || b.y < a.y) { + swap(a, b); + } +} + +int DiagSplit::T(Patch *patch, float2 Pstart, float2 Pend, bool recursive_resolve) +{ + order_float2(Pstart, Pend); /* May not be necessary, but better to be safe. */ + + float Lsum = 0.0f; + float Lmax = 0.0f; + + float3 Plast = to_world(patch, Pstart); + + for (int i = 1; i < params.test_steps; i++) { + float t = i / (float)(params.test_steps - 1); + + float3 P = to_world(patch, Pstart + t * (Pend - Pstart)); + + float L; + + if (!params.camera) { + L = len(P - Plast); + } + else { + Camera *cam = params.camera; + + float pixel_width = cam->world_to_raster_size((P + Plast) * 0.5f); + L = len(P - Plast) / pixel_width; + } + + Lsum += L; + Lmax = max(L, Lmax); + + Plast = P; + } + + int tmin = (int)ceilf(Lsum / params.dicing_rate); + int tmax = (int)ceilf((params.test_steps - 1) * Lmax / + params.dicing_rate); // XXX paper says N instead of N-1, seems wrong? + int res = max(tmax, 1); + + if (tmax - tmin > params.split_threshold) { + if (!recursive_resolve) { + res = DSPLIT_NON_UNIFORM; + } + else { + float2 P = (Pstart + Pend) * 0.5f; + res = T(patch, Pstart, P, true) + T(patch, P, Pend, true); + } + } + + limit_edge_factor(res, patch, Pstart, Pend); + return res; +} + +void DiagSplit::partition_edge( + Patch *patch, float2 *P, int *t0, int *t1, float2 Pstart, float2 Pend, int t) +{ + if (t == DSPLIT_NON_UNIFORM) { + *P = (Pstart + Pend) * 0.5f; + *t0 = T(patch, Pstart, *P); + *t1 = T(patch, *P, Pend); + } + else { + assert(t >= 2); /* Need at least two segments to partition into. */ + + int I = (int)floorf((float)t * 0.5f); + *P = interp(Pstart, Pend, I / (float)t); + *t0 = I; + *t1 = t - I; + } +} + +void DiagSplit::limit_edge_factor(int &T, Patch *patch, float2 Pstart, float2 Pend) +{ + int max_t = 1 << params.max_level; + int max_t_for_edge = int(max_t * len(Pstart - Pend)); + + if (patch->from_ngon) { + max_t_for_edge >>= 1; /* Initial split of ngon causes edges to extend half the distance. */ + } + + T = (max_t_for_edge <= 1) ? 1 : min(T, max_t_for_edge); + + assert(T >= 1 || T == DSPLIT_NON_UNIFORM); +} + +void DiagSplit::resolve_edge_factors(Subpatch &sub) +{ + /* Resolve DSPLIT_NON_UNIFORM to actual T value if splitting is no longer possible. */ + if (sub.edge_u0.T == 1 && sub.edge_u1.T == DSPLIT_NON_UNIFORM) { + sub.edge_u1.T = T(sub.patch, sub.c01, sub.c11, true); + } + if (sub.edge_u1.T == 1 && sub.edge_u0.T == DSPLIT_NON_UNIFORM) { + sub.edge_u0.T = T(sub.patch, sub.c00, sub.c10, true); + } + if (sub.edge_v0.T == 1 && sub.edge_v1.T == DSPLIT_NON_UNIFORM) { + sub.edge_v1.T = T(sub.patch, sub.c11, sub.c10, true); + } + if (sub.edge_v1.T == 1 && sub.edge_v0.T == DSPLIT_NON_UNIFORM) { + sub.edge_v0.T = T(sub.patch, sub.c01, sub.c00, true); + } +} + +void DiagSplit::split(Subpatch &sub, int depth) +{ + if (depth > 32) { + /* We should never get here, but just in case end recursion safely. */ + assert(!"diagsplit recursion limit reached"); + + sub.edge_u0.T = 1; + sub.edge_u1.T = 1; + sub.edge_v0.T = 1; + sub.edge_v1.T = 1; + + subpatches.push_back(sub); + return; + } + + bool split_u = (sub.edge_u0.T == DSPLIT_NON_UNIFORM || sub.edge_u1.T == DSPLIT_NON_UNIFORM); + bool split_v = (sub.edge_v0.T == DSPLIT_NON_UNIFORM || sub.edge_v1.T == DSPLIT_NON_UNIFORM); + + /* Split subpatches such that the ratio of T for opposite edges doesn't + * exceed 1.5, this reduces over tessellation for some patches + */ + /* clang-format off */ + if (min(sub.edge_u0.T, sub.edge_u1.T) > 8 && /* Must be uniform and preferably greater than 8 to split. */ + min(sub.edge_v0.T, sub.edge_v1.T) >= 2 && /* Must be uniform and at least 2 to split. */ + max(sub.edge_u0.T, sub.edge_u1.T) / min(sub.edge_u0.T, sub.edge_u1.T) > 1.5f) + { + split_v = true; + } + if (min(sub.edge_v0.T, sub.edge_v1.T) > 8 && + min(sub.edge_u0.T, sub.edge_u1.T) >= 2 && + max(sub.edge_v0.T, sub.edge_v1.T) / min(sub.edge_v0.T, sub.edge_v1.T) > 1.5f) + { + split_u = true; + } + /* clang-format on */ + + /* Alternate axis. */ + if (split_u && split_v) { + split_u = depth % 2; + } + + if (!split_u && !split_v) { + /* Add the unsplit subpatch. */ + subpatches.push_back(sub); + Subpatch &subpatch = subpatches[subpatches.size() - 1]; + + /* Update T values and offsets. */ + for (int i = 0; i < 4; i++) { + Subpatch::edge_t &edge = subpatch.edges[i]; + + edge.offset = edge.edge->T; + edge.edge->T += edge.T; + } + } + else { + /* Copy into new subpatches. */ + Subpatch sub_a = sub; + Subpatch sub_b = sub; + + /* Pointers to various subpatch elements. */ + Subpatch::edge_t *sub_across_0, *sub_across_1; + Subpatch::edge_t *sub_a_across_0, *sub_a_across_1; + Subpatch::edge_t *sub_b_across_0, *sub_b_across_1; + + Subpatch::edge_t *sub_a_split, *sub_b_split; + + float2 *Pa, *Pb, *Pc, *Pd; + + /* Set pointers based on split axis. */ + if (split_u) { + sub_across_0 = &sub.edge_u0; + sub_across_1 = &sub.edge_u1; + sub_a_across_0 = &sub_a.edge_u0; + sub_a_across_1 = &sub_a.edge_u1; + sub_b_across_0 = &sub_b.edge_u0; + sub_b_across_1 = &sub_b.edge_u1; + + sub_a_split = &sub_a.edge_v1; + sub_b_split = &sub_b.edge_v0; + + Pa = &sub_a.c11; + Pb = &sub_a.c10; + Pc = &sub_b.c01; + Pd = &sub_b.c00; + } + else { + sub_across_0 = &sub.edge_v0; + sub_across_1 = &sub.edge_v1; + sub_a_across_0 = &sub_a.edge_v0; + sub_a_across_1 = &sub_a.edge_v1; + sub_b_across_0 = &sub_b.edge_v0; + sub_b_across_1 = &sub_b.edge_v1; + + sub_a_split = &sub_a.edge_u0; + sub_b_split = &sub_b.edge_u1; + + Pa = &sub_a.c10; + Pb = &sub_a.c00; + Pc = &sub_b.c11; + Pd = &sub_b.c01; + } + + /* Partition edges */ + float2 P0, P1; + + partition_edge( + sub.patch, &P0, &sub_a_across_0->T, &sub_b_across_0->T, *Pd, *Pb, sub_across_0->T); + partition_edge( + sub.patch, &P1, &sub_a_across_1->T, &sub_b_across_1->T, *Pc, *Pa, sub_across_1->T); + + /* Split */ + *Pa = P1; + *Pb = P0; + + *Pc = P1; + *Pd = P0; + + int tsplit = T(sub.patch, P0, P1); + + if (depth == -2 && tsplit == 1) { + tsplit = 2; /* Ensure we can always split at depth -1. */ + } + + sub_a_split->T = tsplit; + sub_b_split->T = tsplit; + + resolve_edge_factors(sub_a); + resolve_edge_factors(sub_b); + + /* Create new edge */ + Edge &edge = *alloc_edge(); + + sub_a_split->edge = &edge; + sub_b_split->edge = &edge; + + sub_a_split->offset = 0; + sub_b_split->offset = 0; + + sub_a_split->indices_decrease_along_edge = false; + sub_b_split->indices_decrease_along_edge = true; + + sub_a_split->sub_edges_created_in_reverse_order = !split_u; + sub_b_split->sub_edges_created_in_reverse_order = !split_u; + + edge.top_indices_decrease = sub_across_1->sub_edges_created_in_reverse_order; + edge.bottom_indices_decrease = sub_across_0->sub_edges_created_in_reverse_order; + + /* Recurse */ + edge.T = 0; + split(sub_a, depth + 1); + + int edge_t = edge.T; + (void)edge_t; + + edge.top_offset = sub_across_1->edge->T; + edge.bottom_offset = sub_across_0->edge->T; + + edge.T = 0; /* We calculate T twice along each edge. :/ */ + split(sub_b, depth + 1); + + assert(edge.T == edge_t); /* If this fails we will crash at some later point! */ + + edge.top = sub_across_1->edge; + edge.bottom = sub_across_0->edge; + } +} + +int DiagSplit::alloc_verts(int n) +{ + int a = num_alloced_verts; + num_alloced_verts += n; + return a; +} + +Edge *DiagSplit::alloc_edge() +{ + edges.emplace_back(); + return &edges.back(); +} + +void DiagSplit::split_patches(Patch *patches, size_t patches_byte_stride) +{ + int patch_index = 0; + + for (int f = 0; f < params.mesh->get_num_subd_faces(); f++) { + Mesh::SubdFace face = params.mesh->get_subd_face(f); + + Patch *patch = (Patch *)(((char *)patches) + patch_index * patches_byte_stride); + + if (face.is_quad()) { + patch_index++; + + split_quad(face, patch); + } + else { + patch_index += face.num_corners; + + split_ngon(face, patch, patches_byte_stride); + } + } + + params.mesh->vert_to_stitching_key_map.clear(); + params.mesh->vert_stitching_map.clear(); + + post_split(); +} + +static Edge *create_edge_from_corner(DiagSplit *split, + const Mesh *mesh, + const Mesh::SubdFace &face, + int corner, + bool &reversed, + int v0, + int v1) +{ + int a = mesh->get_subd_face_corners()[face.start_corner + mod(corner + 0, face.num_corners)]; + int b = mesh->get_subd_face_corners()[face.start_corner + mod(corner + 1, face.num_corners)]; + + reversed = !(b < a); + + if (b < a) { + swap(a, b); + swap(v0, v1); + } + + Edge *edge = split->alloc_edge(); + + edge->is_stitch_edge = true; + edge->stitch_start_vert_index = a; + edge->stitch_end_vert_index = b; + + edge->start_vert_index = v0; + edge->end_vert_index = v1; + + edge->stitch_edge_key = {a, b}; + + return edge; +} + +void DiagSplit::split_quad(const Mesh::SubdFace &face, Patch *patch) +{ + Subpatch subpatch(patch); + + int v = alloc_verts(4); + + bool v0_reversed, u1_reversed, v1_reversed, u0_reversed; + subpatch.edge_v0.edge = create_edge_from_corner( + this, params.mesh, face, 3, v0_reversed, v + 3, v + 0); + subpatch.edge_u1.edge = create_edge_from_corner( + this, params.mesh, face, 2, u1_reversed, v + 2, v + 3); + subpatch.edge_v1.edge = create_edge_from_corner( + this, params.mesh, face, 1, v1_reversed, v + 1, v + 2); + subpatch.edge_u0.edge = create_edge_from_corner( + this, params.mesh, face, 0, u0_reversed, v + 0, v + 1); + + subpatch.edge_v0.sub_edges_created_in_reverse_order = !v0_reversed; + subpatch.edge_u1.sub_edges_created_in_reverse_order = u1_reversed; + subpatch.edge_v1.sub_edges_created_in_reverse_order = v1_reversed; + subpatch.edge_u0.sub_edges_created_in_reverse_order = !u0_reversed; + + subpatch.edge_v0.indices_decrease_along_edge = v0_reversed; + subpatch.edge_u1.indices_decrease_along_edge = u1_reversed; + subpatch.edge_v1.indices_decrease_along_edge = v1_reversed; + subpatch.edge_u0.indices_decrease_along_edge = u0_reversed; + + /* Forces a split in both axis for quads, needed to match split of ngons into quads. */ + subpatch.edge_u0.T = DSPLIT_NON_UNIFORM; + subpatch.edge_u1.T = DSPLIT_NON_UNIFORM; + subpatch.edge_v0.T = DSPLIT_NON_UNIFORM; + subpatch.edge_v1.T = DSPLIT_NON_UNIFORM; + + split(subpatch, -2); +} + +static Edge *create_split_edge_from_corner(DiagSplit *split, + const Mesh *mesh, + const Mesh::SubdFace &face, + int corner, + int side, + bool &reversed, + int v0, + int v1, + int vc) +{ + Edge *edge = split->alloc_edge(); + + int a = mesh->get_subd_face_corners()[face.start_corner + mod(corner + 0, face.num_corners)]; + int b = mesh->get_subd_face_corners()[face.start_corner + mod(corner + 1, face.num_corners)]; + + if (b < a) { + edge->stitch_edge_key = {b, a}; + } + else { + edge->stitch_edge_key = {a, b}; + } + + reversed = !(b < a); + + if (side == 0) { + a = vc; + } + else { + b = vc; + } + + if (!reversed) { + swap(a, b); + swap(v0, v1); + } + + edge->is_stitch_edge = true; + edge->stitch_start_vert_index = a; + edge->stitch_end_vert_index = b; + + edge->start_vert_index = v0; + edge->end_vert_index = v1; + + return edge; +} + +void DiagSplit::split_ngon(const Mesh::SubdFace &face, Patch *patches, size_t patches_byte_stride) +{ + Edge *prev_edge_u0 = nullptr; + Edge *first_edge_v0 = nullptr; + + for (int corner = 0; corner < face.num_corners; corner++) { + Patch *patch = (Patch *)(((char *)patches) + corner * patches_byte_stride); + + Subpatch subpatch(patch); + + int v = alloc_verts(4); + + /* Setup edges. */ + Edge *edge_u1 = alloc_edge(); + Edge *edge_v1 = alloc_edge(); + + edge_v1->is_stitch_edge = true; + edge_u1->is_stitch_edge = true; + + edge_u1->stitch_start_vert_index = -(face.start_corner + mod(corner + 0, face.num_corners)) - + 1; + edge_u1->stitch_end_vert_index = STITCH_NGON_CENTER_VERT_INDEX_OFFSET + face.ptex_offset; + + edge_u1->start_vert_index = v + 3; + edge_u1->end_vert_index = v + 2; + + edge_u1->stitch_edge_key = {edge_u1->stitch_start_vert_index, edge_u1->stitch_end_vert_index}; + + edge_v1->stitch_start_vert_index = -(face.start_corner + mod(corner + 1, face.num_corners)) - + 1; + edge_v1->stitch_end_vert_index = STITCH_NGON_CENTER_VERT_INDEX_OFFSET + face.ptex_offset; + + edge_v1->start_vert_index = v + 1; + edge_v1->end_vert_index = v + 2; + + edge_v1->stitch_edge_key = {edge_v1->stitch_start_vert_index, edge_v1->stitch_end_vert_index}; + + bool v0_reversed, u0_reversed; + + subpatch.edge_v0.edge = create_split_edge_from_corner(this, + params.mesh, + face, + corner - 1, + 0, + v0_reversed, + v + 3, + v + 0, + STITCH_NGON_SPLIT_EDGE_CENTER_VERT_TAG); + + subpatch.edge_u1.edge = edge_u1; + subpatch.edge_v1.edge = edge_v1; + + subpatch.edge_u0.edge = create_split_edge_from_corner(this, + params.mesh, + face, + corner + 0, + 1, + u0_reversed, + v + 0, + v + 1, + STITCH_NGON_SPLIT_EDGE_CENTER_VERT_TAG); + + subpatch.edge_v0.sub_edges_created_in_reverse_order = !v0_reversed; + subpatch.edge_u1.sub_edges_created_in_reverse_order = false; + subpatch.edge_v1.sub_edges_created_in_reverse_order = true; + subpatch.edge_u0.sub_edges_created_in_reverse_order = !u0_reversed; + + subpatch.edge_v0.indices_decrease_along_edge = v0_reversed; + subpatch.edge_u1.indices_decrease_along_edge = false; + subpatch.edge_v1.indices_decrease_along_edge = true; + subpatch.edge_u0.indices_decrease_along_edge = u0_reversed; + + /* Perform split. */ + { + subpatch.edge_u0.T = T(subpatch.patch, subpatch.c00, subpatch.c10); + subpatch.edge_u1.T = T(subpatch.patch, subpatch.c01, subpatch.c11); + subpatch.edge_v0.T = T(subpatch.patch, subpatch.c00, subpatch.c01); + subpatch.edge_v1.T = T(subpatch.patch, subpatch.c10, subpatch.c11); + + resolve_edge_factors(subpatch); + + split(subpatch, 0); + } + + /* Update offsets after T is known from split. */ + edge_u1->top = subpatch.edge_v0.edge; + edge_u1->stitch_top_offset = edge_u1->top->T * (v0_reversed ? -1 : 1); + edge_v1->top = subpatch.edge_u0.edge; + edge_v1->stitch_top_offset = edge_v1->top->T * (!u0_reversed ? -1 : 1); + + if (corner == 0) { + first_edge_v0 = subpatch.edge_v0.edge; + } + + if (prev_edge_u0) { + if (v0_reversed) { + subpatch.edge_v0.edge->stitch_offset = prev_edge_u0->T; + } + else { + prev_edge_u0->stitch_offset = subpatch.edge_v0.edge->T; + } + + int T = subpatch.edge_v0.edge->T + prev_edge_u0->T; + subpatch.edge_v0.edge->stitch_edge_T = T; + prev_edge_u0->stitch_edge_T = T; + } + + if (corner == face.num_corners - 1) { + if (v0_reversed) { + subpatch.edge_u0.edge->stitch_offset = first_edge_v0->T; + } + else { + first_edge_v0->stitch_offset = subpatch.edge_u0.edge->T; + } + + int T = first_edge_v0->T + subpatch.edge_u0.edge->T; + first_edge_v0->stitch_edge_T = T; + subpatch.edge_u0.edge->stitch_edge_T = T; + } + + prev_edge_u0 = subpatch.edge_u0.edge; + } +} + +void DiagSplit::post_split() +{ + int num_stitch_verts = 0; + + /* All patches are now split, and all T values known. */ + + foreach (Edge &edge, edges) { + if (edge.second_vert_index < 0) { + edge.second_vert_index = alloc_verts(edge.T - 1); + } + + if (edge.is_stitch_edge) { + num_stitch_verts = max(num_stitch_verts, + max(edge.stitch_start_vert_index, edge.stitch_end_vert_index)); + } + } + + num_stitch_verts += 1; + + /* Map of edge key to edge stitching vert offset. */ + struct pair_hasher { + size_t operator()(const pair &k) const + { + return hash_uint2(k.first, k.second); + } + }; + typedef unordered_map, int, pair_hasher> edge_stitch_verts_map_t; + edge_stitch_verts_map_t edge_stitch_verts_map; + + foreach (Edge &edge, edges) { + if (edge.is_stitch_edge) { + if (edge.stitch_edge_T == 0) { + edge.stitch_edge_T = edge.T; + } + + if (edge_stitch_verts_map.find(edge.stitch_edge_key) == edge_stitch_verts_map.end()) { + edge_stitch_verts_map[edge.stitch_edge_key] = num_stitch_verts; + num_stitch_verts += edge.stitch_edge_T - 1; + } + } + } + + /* Set start and end indices for edges generated from a split. */ + foreach (Edge &edge, edges) { + if (edge.start_vert_index < 0) { + /* Fix up offsets. */ + if (edge.top_indices_decrease) { + edge.top_offset = edge.top->T - edge.top_offset; + } + + edge.start_vert_index = edge.top->get_vert_along_edge(edge.top_offset); + } + + if (edge.end_vert_index < 0) { + if (edge.bottom_indices_decrease) { + edge.bottom_offset = edge.bottom->T - edge.bottom_offset; + } + + edge.end_vert_index = edge.bottom->get_vert_along_edge(edge.bottom_offset); + } + } + + int vert_offset = params.mesh->verts.size(); + + /* Add verts to stitching map. */ + foreach (const Edge &edge, edges) { + if (edge.is_stitch_edge) { + int second_stitch_vert_index = edge_stitch_verts_map[edge.stitch_edge_key]; + + for (int i = 0; i <= edge.T; i++) { + /* Get proper stitching key. */ + int key; + + if (i == 0) { + key = edge.stitch_start_vert_index; + } + else if (i == edge.T) { + key = edge.stitch_end_vert_index; + } + else { + key = second_stitch_vert_index + i - 1 + edge.stitch_offset; + } + + if (key == STITCH_NGON_SPLIT_EDGE_CENTER_VERT_TAG) { + if (i == 0) { + key = second_stitch_vert_index - 1 + edge.stitch_offset; + } + else if (i == edge.T) { + key = second_stitch_vert_index - 1 + edge.T; + } + } + else if (key < 0 && edge.top) { /* ngon spoke edge */ + int s = edge_stitch_verts_map[edge.top->stitch_edge_key]; + if (edge.stitch_top_offset >= 0) { + key = s - 1 + edge.stitch_top_offset; + } + else { + key = s - 1 + edge.top->stitch_edge_T + edge.stitch_top_offset; + } + } + + /* Get real vert index. */ + int vert = edge.get_vert_along_edge(i) + vert_offset; + + /* Add to map */ + if (params.mesh->vert_to_stitching_key_map.find(vert) == + params.mesh->vert_to_stitching_key_map.end()) { + params.mesh->vert_to_stitching_key_map[vert] = key; + params.mesh->vert_stitching_map.insert({key, vert}); + } + } + } + } + + /* Dice; TODO(mai): Move this out of split. */ + QuadDice dice(params); + + int num_verts = num_alloced_verts; + int num_triangles = 0; + + for (size_t i = 0; i < subpatches.size(); i++) { + subpatches[i].inner_grid_vert_offset = num_verts; + num_verts += subpatches[i].calc_num_inner_verts(); + num_triangles += subpatches[i].calc_num_triangles(); + } + + dice.reserve(num_verts, num_triangles); + + for (size_t i = 0; i < subpatches.size(); i++) { + Subpatch &sub = subpatches[i]; + + sub.edge_u0.T = max(sub.edge_u0.T, 1); + sub.edge_u1.T = max(sub.edge_u1.T, 1); + sub.edge_v0.T = max(sub.edge_v0.T, 1); + sub.edge_v1.T = max(sub.edge_v1.T, 1); + + dice.dice(sub); + } + + /* Cleanup */ + subpatches.clear(); + edges.clear(); +} + +CCL_NAMESPACE_END diff --git a/intern/cycles/subd/split.h b/intern/cycles/subd/split.h new file mode 100644 index 00000000000..e876f34c419 --- /dev/null +++ b/intern/cycles/subd/split.h @@ -0,0 +1,75 @@ +/* + * Copyright 2011-2013 Blender Foundation + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +#ifndef __SUBD_SPLIT_H__ +#define __SUBD_SPLIT_H__ + +/* DiagSplit: Parallel, Crack-free, Adaptive Tessellation for Micropolygon Rendering + * Splits up patches and determines edge tessellation factors for dicing. Patch + * evaluation at arbitrary points is required for this to work. See the paper + * for more details. */ + +#include "subd/dice.h" +#include "subd/subpatch.h" + +#include "util/deque.h" +#include "util/types.h" +#include "util/vector.h" + +#include + +CCL_NAMESPACE_BEGIN + +class Mesh; +class Patch; + +class DiagSplit { + SubdParams params; + + vector subpatches; + /* `deque` is used so that element pointers remain valid when size is changed. */ + deque edges; + + float3 to_world(Patch *patch, float2 uv); + int T(Patch *patch, float2 Pstart, float2 Pend, bool recursive_resolve = false); + + void limit_edge_factor(int &T, Patch *patch, float2 Pstart, float2 Pend); + void resolve_edge_factors(Subpatch &sub); + + void partition_edge( + Patch *patch, float2 *P, int *t0, int *t1, float2 Pstart, float2 Pend, int t); + + void split(Subpatch &sub, int depth = 0); + + int num_alloced_verts = 0; + int alloc_verts(int n); /* Returns start index of new verts. */ + + public: + Edge *alloc_edge(); + + explicit DiagSplit(const SubdParams ¶ms); + + void split_patches(Patch *patches, size_t patches_byte_stride); + + void split_quad(const Mesh::SubdFace &face, Patch *patch); + void split_ngon(const Mesh::SubdFace &face, Patch *patches, size_t patches_byte_stride); + + void post_split(); +}; + +CCL_NAMESPACE_END + +#endif /* __SUBD_SPLIT_H__ */ diff --git a/intern/cycles/subd/subd_dice.cpp b/intern/cycles/subd/subd_dice.cpp deleted file mode 100644 index a4019a5d639..00000000000 --- a/intern/cycles/subd/subd_dice.cpp +++ /dev/null @@ -1,283 +0,0 @@ -/* - * Copyright 2011-2013 Blender Foundation - * - * Licensed under the Apache License, Version 2.0 (the "License"); - * you may not use this file except in compliance with the License. - * You may obtain a copy of the License at - * - * http://www.apache.org/licenses/LICENSE-2.0 - * - * Unless required by applicable law or agreed to in writing, software - * distributed under the License is distributed on an "AS IS" BASIS, - * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. - * See the License for the specific language governing permissions and - * limitations under the License. - */ - -#include "scene/camera.h" -#include "scene/mesh.h" - -#include "subd/subd_dice.h" -#include "subd/subd_patch.h" - -CCL_NAMESPACE_BEGIN - -/* EdgeDice Base */ - -EdgeDice::EdgeDice(const SubdParams ¶ms_) : params(params_) -{ - mesh_P = NULL; - mesh_N = NULL; - vert_offset = 0; - - params.mesh->attributes.add(ATTR_STD_VERTEX_NORMAL); - - if (params.ptex) { - params.mesh->attributes.add(ATTR_STD_PTEX_UV); - params.mesh->attributes.add(ATTR_STD_PTEX_FACE_ID); - } -} - -void EdgeDice::reserve(int num_verts, int num_triangles) -{ - Mesh *mesh = params.mesh; - - vert_offset = mesh->get_verts().size(); - tri_offset = mesh->num_triangles(); - - mesh->resize_mesh(mesh->get_verts().size() + num_verts, mesh->num_triangles()); - mesh->reserve_mesh(mesh->get_verts().size() + num_verts, mesh->num_triangles() + num_triangles); - - Attribute *attr_vN = mesh->attributes.add(ATTR_STD_VERTEX_NORMAL); - - mesh_P = mesh->verts.data() + vert_offset; - mesh_N = attr_vN->data_float3() + vert_offset; - - params.mesh->num_subd_verts += num_verts; -} - -void EdgeDice::set_vert(Patch *patch, int index, float2 uv) -{ - float3 P, N; - - patch->eval(&P, NULL, NULL, &N, uv.x, uv.y); - - assert(index < params.mesh->verts.size()); - - mesh_P[index] = P; - mesh_N[index] = N; - params.mesh->vert_patch_uv[index + vert_offset] = make_float2(uv.x, uv.y); -} - -void EdgeDice::add_triangle(Patch *patch, int v0, int v1, int v2) -{ - Mesh *mesh = params.mesh; - - mesh->add_triangle(v0 + vert_offset, v1 + vert_offset, v2 + vert_offset, patch->shader, true); - params.mesh->triangle_patch[params.mesh->num_triangles() - 1] = patch->patch_index; - - tri_offset++; -} - -void EdgeDice::stitch_triangles(Subpatch &sub, int edge) -{ - int Mu = max(sub.edge_u0.T, sub.edge_u1.T); - int Mv = max(sub.edge_v0.T, sub.edge_v1.T); - Mu = max(Mu, 2); - Mv = max(Mv, 2); - - int outer_T = sub.edges[edge].T; - int inner_T = ((edge % 2) == 0) ? Mv - 2 : Mu - 2; - - if (inner_T < 0 || outer_T < 0) - return; // XXX avoid crashes for Mu or Mv == 1, missing polygons - - /* stitch together two arrays of verts with triangles. at each step, - * we compare using the next verts on both sides, to find the split - * direction with the smallest diagonal, and use that in order to keep - * the triangle shape reasonable. */ - for (size_t i = 0, j = 0; i < inner_T || j < outer_T;) { - int v0, v1, v2; - - v0 = sub.get_vert_along_grid_edge(edge, i); - v1 = sub.get_vert_along_edge(edge, j); - - if (j == outer_T) { - v2 = sub.get_vert_along_grid_edge(edge, ++i); - } - else if (i == inner_T) { - v2 = sub.get_vert_along_edge(edge, ++j); - } - else { - /* length of diagonals */ - float len1 = len_squared(mesh_P[sub.get_vert_along_grid_edge(edge, i)] - - mesh_P[sub.get_vert_along_edge(edge, j + 1)]); - float len2 = len_squared(mesh_P[sub.get_vert_along_edge(edge, j)] - - mesh_P[sub.get_vert_along_grid_edge(edge, i + 1)]); - - /* use smallest diagonal */ - if (len1 < len2) - v2 = sub.get_vert_along_edge(edge, ++j); - else - v2 = sub.get_vert_along_grid_edge(edge, ++i); - } - - add_triangle(sub.patch, v1, v0, v2); - } -} - -/* QuadDice */ - -QuadDice::QuadDice(const SubdParams ¶ms_) : EdgeDice(params_) -{ -} - -float2 QuadDice::map_uv(Subpatch &sub, float u, float v) -{ - /* map UV from subpatch to patch parametric coordinates */ - float2 d0 = interp(sub.c00, sub.c01, v); - float2 d1 = interp(sub.c10, sub.c11, v); - return interp(d0, d1, u); -} - -float3 QuadDice::eval_projected(Subpatch &sub, float u, float v) -{ - float2 uv = map_uv(sub, u, v); - float3 P; - - sub.patch->eval(&P, NULL, NULL, NULL, uv.x, uv.y); - if (params.camera) - P = transform_perspective(¶ms.camera->worldtoraster, P); - - return P; -} - -void QuadDice::set_vert(Subpatch &sub, int index, float u, float v) -{ - EdgeDice::set_vert(sub.patch, index, map_uv(sub, u, v)); -} - -void QuadDice::set_side(Subpatch &sub, int edge) -{ - int t = sub.edges[edge].T; - - /* set verts on the edge of the patch */ - for (int i = 0; i < t; i++) { - float f = i / (float)t; - - float u, v; - switch (edge) { - case 0: - u = 0; - v = f; - break; - case 1: - u = f; - v = 1; - break; - case 2: - u = 1; - v = 1.0f - f; - break; - case 3: - default: - u = 1.0f - f; - v = 0; - break; - } - - set_vert(sub, sub.get_vert_along_edge(edge, i), u, v); - } -} - -float QuadDice::quad_area(const float3 &a, const float3 &b, const float3 &c, const float3 &d) -{ - return triangle_area(a, b, d) + triangle_area(a, d, c); -} - -float QuadDice::scale_factor(Subpatch &sub, int Mu, int Mv) -{ - /* estimate area as 4x largest of 4 quads */ - float3 P[3][3]; - - for (int i = 0; i < 3; i++) - for (int j = 0; j < 3; j++) - P[i][j] = eval_projected(sub, i * 0.5f, j * 0.5f); - - float A1 = quad_area(P[0][0], P[1][0], P[0][1], P[1][1]); - float A2 = quad_area(P[1][0], P[2][0], P[1][1], P[2][1]); - float A3 = quad_area(P[0][1], P[1][1], P[0][2], P[1][2]); - float A4 = quad_area(P[1][1], P[2][1], P[1][2], P[2][2]); - float Apatch = max(A1, max(A2, max(A3, A4))) * 4.0f; - - /* solve for scaling factor */ - float Atri = params.dicing_rate * params.dicing_rate * 0.5f; - float Ntris = Apatch / Atri; - - // XXX does the -sqrt solution matter - // XXX max(D, 0.0) is highly suspicious, need to test cases - // where D goes negative - float N = 0.5f * (Ntris - (sub.edge_u0.T + sub.edge_u1.T + sub.edge_v0.T + sub.edge_v1.T)); - float D = 4.0f * N * Mu * Mv + (Mu + Mv) * (Mu + Mv); - float S = (Mu + Mv + sqrtf(max(D, 0.0f))) / (2 * Mu * Mv); - - return S; -} - -void QuadDice::add_grid(Subpatch &sub, int Mu, int Mv, int offset) -{ - /* create inner grid */ - float du = 1.0f / (float)Mu; - float dv = 1.0f / (float)Mv; - - for (int j = 1; j < Mv; j++) { - for (int i = 1; i < Mu; i++) { - float u = i * du; - float v = j * dv; - - set_vert(sub, offset + (i - 1) + (j - 1) * (Mu - 1), u, v); - - if (i < Mu - 1 && j < Mv - 1) { - int i1 = offset + (i - 1) + (j - 1) * (Mu - 1); - int i2 = offset + i + (j - 1) * (Mu - 1); - int i3 = offset + i + j * (Mu - 1); - int i4 = offset + (i - 1) + j * (Mu - 1); - - add_triangle(sub.patch, i1, i2, i3); - add_triangle(sub.patch, i1, i3, i4); - } - } - } -} - -void QuadDice::dice(Subpatch &sub) -{ - /* compute inner grid size with scale factor */ - int Mu = max(sub.edge_u0.T, sub.edge_u1.T); - int Mv = max(sub.edge_v0.T, sub.edge_v1.T); - -#if 0 /* Doesn't work very well, especially at grazing angles. */ - float S = scale_factor(sub, ef, Mu, Mv); -#else - float S = 1.0f; -#endif - - Mu = max((int)ceilf(S * Mu), 2); // XXX handle 0 & 1? - Mv = max((int)ceilf(S * Mv), 2); // XXX handle 0 & 1? - - /* inner grid */ - add_grid(sub, Mu, Mv, sub.inner_grid_vert_offset); - - /* sides */ - set_side(sub, 0); - set_side(sub, 1); - set_side(sub, 2); - set_side(sub, 3); - - stitch_triangles(sub, 0); - stitch_triangles(sub, 1); - stitch_triangles(sub, 2); - stitch_triangles(sub, 3); -} - -CCL_NAMESPACE_END diff --git a/intern/cycles/subd/subd_dice.h b/intern/cycles/subd/subd_dice.h deleted file mode 100644 index ee63403d40c..00000000000 --- a/intern/cycles/subd/subd_dice.h +++ /dev/null @@ -1,103 +0,0 @@ -/* - * Copyright 2011-2013 Blender Foundation - * - * Licensed under the Apache License, Version 2.0 (the "License"); - * you may not use this file except in compliance with the License. - * You may obtain a copy of the License at - * - * http://www.apache.org/licenses/LICENSE-2.0 - * - * Unless required by applicable law or agreed to in writing, software - * distributed under the License is distributed on an "AS IS" BASIS, - * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. - * See the License for the specific language governing permissions and - * limitations under the License. - */ - -#ifndef __SUBD_DICE_H__ -#define __SUBD_DICE_H__ - -/* DX11 like EdgeDice implementation, with different tessellation factors for - * each edge for watertight tessellation, with subpatch remapping to work with - * DiagSplit. For more algorithm details, see the DiagSplit paper or the - * ARB_tessellation_shader OpenGL extension, Section 2.X.2. */ - -#include "util/util_types.h" -#include "util/util_vector.h" - -#include "subd/subd_subpatch.h" - -CCL_NAMESPACE_BEGIN - -class Camera; -class Mesh; -class Patch; - -struct SubdParams { - Mesh *mesh; - bool ptex; - - int test_steps; - int split_threshold; - float dicing_rate; - int max_level; - Camera *camera; - Transform objecttoworld; - - SubdParams(Mesh *mesh_, bool ptex_ = false) - { - mesh = mesh_; - ptex = ptex_; - - test_steps = 3; - split_threshold = 1; - dicing_rate = 1.0f; - max_level = 12; - camera = NULL; - } -}; - -/* EdgeDice Base */ - -class EdgeDice { - public: - SubdParams params; - float3 *mesh_P; - float3 *mesh_N; - size_t vert_offset; - size_t tri_offset; - - explicit EdgeDice(const SubdParams ¶ms); - - void reserve(int num_verts, int num_triangles); - - void set_vert(Patch *patch, int index, float2 uv); - void add_triangle(Patch *patch, int v0, int v1, int v2); - - void stitch_triangles(Subpatch &sub, int edge); -}; - -/* Quad EdgeDice */ - -class QuadDice : public EdgeDice { - public: - explicit QuadDice(const SubdParams ¶ms); - - float3 eval_projected(Subpatch &sub, float u, float v); - - float2 map_uv(Subpatch &sub, float u, float v); - void set_vert(Subpatch &sub, int index, float u, float v); - - void add_grid(Subpatch &sub, int Mu, int Mv, int offset); - - void set_side(Subpatch &sub, int edge); - - float quad_area(const float3 &a, const float3 &b, const float3 &c, const float3 &d); - float scale_factor(Subpatch &sub, int Mu, int Mv); - - void dice(Subpatch &sub); -}; - -CCL_NAMESPACE_END - -#endif /* __SUBD_DICE_H__ */ diff --git a/intern/cycles/subd/subd_patch.cpp b/intern/cycles/subd/subd_patch.cpp deleted file mode 100644 index 23b3e6d5136..00000000000 --- a/intern/cycles/subd/subd_patch.cpp +++ /dev/null @@ -1,121 +0,0 @@ -/* - * Copyright 2011-2013 Blender Foundation - * - * Licensed under the Apache License, Version 2.0 (the "License"); - * you may not use this file except in compliance with the License. - * You may obtain a copy of the License at - * - * http://www.apache.org/licenses/LICENSE-2.0 - * - * Unless required by applicable law or agreed to in writing, software - * distributed under the License is distributed on an "AS IS" BASIS, - * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. - * See the License for the specific language governing permissions and - * limitations under the License. - */ - -/* Parts adapted from code in the public domain in NVidia Mesh Tools. */ - -#include "scene/mesh.h" - -#include "subd/subd_patch.h" - -#include "util/util_math.h" -#include "util/util_types.h" - -CCL_NAMESPACE_BEGIN - -/* De Casteljau Evaluation */ - -static void decasteljau_cubic(float3 *P, float3 *dt, float t, const float3 cp[4]) -{ - float3 d0 = cp[0] + t * (cp[1] - cp[0]); - float3 d1 = cp[1] + t * (cp[2] - cp[1]); - float3 d2 = cp[2] + t * (cp[3] - cp[2]); - - d0 += t * (d1 - d0); - d1 += t * (d2 - d1); - - *P = d0 + t * (d1 - d0); - if (dt) - *dt = d1 - d0; -} - -static void decasteljau_bicubic( - float3 *P, float3 *du, float3 *dv, const float3 cp[16], float u, float v) -{ - float3 ucp[4], utn[4]; - - /* interpolate over u */ - decasteljau_cubic(ucp + 0, utn + 0, u, cp); - decasteljau_cubic(ucp + 1, utn + 1, u, cp + 4); - decasteljau_cubic(ucp + 2, utn + 2, u, cp + 8); - decasteljau_cubic(ucp + 3, utn + 3, u, cp + 12); - - /* interpolate over v */ - decasteljau_cubic(P, dv, v, ucp); - if (du) - decasteljau_cubic(du, NULL, v, utn); -} - -/* Linear Quad Patch */ - -void LinearQuadPatch::eval(float3 *P, float3 *dPdu, float3 *dPdv, float3 *N, float u, float v) -{ - float3 d0 = interp(hull[0], hull[1], u); - float3 d1 = interp(hull[2], hull[3], u); - - *P = interp(d0, d1, v); - - if (dPdu && dPdv) { - *dPdu = interp(hull[1] - hull[0], hull[3] - hull[2], v); - *dPdv = interp(hull[2] - hull[0], hull[3] - hull[1], u); - } - - if (N) { - *N = normalize( - interp(interp(normals[0], normals[1], u), interp(normals[2], normals[3], u), v)); - } -} - -BoundBox LinearQuadPatch::bound() -{ - BoundBox bbox = BoundBox::empty; - - for (int i = 0; i < 4; i++) - bbox.grow(hull[i]); - - return bbox; -} - -/* Bicubic Patch */ - -void BicubicPatch::eval(float3 *P, float3 *dPdu, float3 *dPdv, float3 *N, float u, float v) -{ - if (N) { - float3 dPdu_, dPdv_; - decasteljau_bicubic(P, &dPdu_, &dPdv_, hull, u, v); - - if (dPdu && dPdv) { - *dPdu = dPdu_; - *dPdv = dPdv_; - } - - *N = normalize(cross(dPdu_, dPdv_)); - } - else { - decasteljau_bicubic(P, dPdu, dPdv, hull, u, v); - } -} - -BoundBox BicubicPatch::bound() -{ - BoundBox bbox = BoundBox::empty; - - for (int i = 0; i < 16; i++) - bbox.grow(hull[i]); - - return bbox; -} - -CCL_NAMESPACE_END diff --git a/intern/cycles/subd/subd_patch.h b/intern/cycles/subd/subd_patch.h deleted file mode 100644 index 8fe423bc94d..00000000000 --- a/intern/cycles/subd/subd_patch.h +++ /dev/null @@ -1,63 +0,0 @@ -/* - * Copyright 2011-2013 Blender Foundation - * - * Licensed under the Apache License, Version 2.0 (the "License"); - * you may not use this file except in compliance with the License. - * You may obtain a copy of the License at - * - * http://www.apache.org/licenses/LICENSE-2.0 - * - * Unless required by applicable law or agreed to in writing, software - * distributed under the License is distributed on an "AS IS" BASIS, - * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. - * See the License for the specific language governing permissions and - * limitations under the License. - */ - -#ifndef __SUBD_PATCH_H__ -#define __SUBD_PATCH_H__ - -#include "util/util_boundbox.h" -#include "util/util_types.h" - -CCL_NAMESPACE_BEGIN - -class Patch { - public: - Patch() : patch_index(0), shader(0), from_ngon(false) - { - } - - virtual ~Patch() = default; - - virtual void eval(float3 *P, float3 *dPdu, float3 *dPdv, float3 *N, float u, float v) = 0; - - int patch_index; - int shader; - bool from_ngon; -}; - -/* Linear Quad Patch */ - -class LinearQuadPatch : public Patch { - public: - float3 hull[4]; - float3 normals[4]; - - void eval(float3 *P, float3 *dPdu, float3 *dPdv, float3 *N, float u, float v); - BoundBox bound(); -}; - -/* Bicubic Patch */ - -class BicubicPatch : public Patch { - public: - float3 hull[16]; - - void eval(float3 *P, float3 *dPdu, float3 *dPdv, float3 *N, float u, float v); - BoundBox bound(); -}; - -CCL_NAMESPACE_END - -#endif /* __SUBD_PATCH_H__ */ diff --git a/intern/cycles/subd/subd_patch_table.cpp b/intern/cycles/subd/subd_patch_table.cpp deleted file mode 100644 index 4e873375725..00000000000 --- a/intern/cycles/subd/subd_patch_table.cpp +++ /dev/null @@ -1,295 +0,0 @@ -/* - * Based on code from OpenSubdiv released under this license: - * - * Copyright 2014 DreamWorks Animation LLC. - * - * Licensed under the Apache License, Version 2.0 (the "Apache License") - * with the following modification; you may not use this file except in - * compliance with the Apache License and the following modification to it: - * Section 6. Trademarks. is deleted and replaced with: - * - * 6. Trademarks. This License does not grant permission to use the trade - * names, trademarks, service marks, or product names of the Licensor - * and its affiliates, except as required to comply with Section 4(c) of - * the License and to reproduce the content of the NOTICE file. - * - * You may obtain a copy of the Apache License at - * - * http://www.apache.org/licenses/LICENSE-2.0 - * - * Unless required by applicable law or agreed to in writing, software - * distributed under the Apache License with the above modification is - * distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY - * KIND, either express or implied. See the Apache License for the specific - * language governing permissions and limitations under the Apache License. - */ - -#include "subd/subd_patch_table.h" -#include "kernel/kernel_types.h" - -#include "util/util_math.h" - -#ifdef WITH_OPENSUBDIV -# include -#endif - -CCL_NAMESPACE_BEGIN - -#ifdef WITH_OPENSUBDIV - -using namespace OpenSubdiv; - -/* functions for building patch maps */ - -struct PatchMapQuadNode { - /* sets all the children to point to the patch of index */ - void set_child(int index) - { - for (int i = 0; i < 4; i++) { - children[i] = index | PATCH_MAP_NODE_IS_SET | PATCH_MAP_NODE_IS_LEAF; - } - } - - /* sets the child in quadrant to point to the node or patch of the given index */ - void set_child(unsigned char quadrant, int index, bool is_leaf = true) - { - assert(quadrant < 4); - children[quadrant] = index | PATCH_MAP_NODE_IS_SET | (is_leaf ? PATCH_MAP_NODE_IS_LEAF : 0); - } - - uint children[4]; -}; - -template static int resolve_quadrant(T &median, T &u, T &v) -{ - int quadrant = -1; - - if (u < median) { - if (v < median) { - quadrant = 0; - } - else { - quadrant = 1; - v -= median; - } - } - else { - if (v < median) { - quadrant = 3; - } - else { - quadrant = 2; - v -= median; - } - u -= median; - } - - return quadrant; -} - -static void build_patch_map(PackedPatchTable &table, - OpenSubdiv::Far::PatchTable *patch_table, - int offset) -{ - int num_faces = 0; - - for (int array = 0; array < table.num_arrays; array++) { - Far::ConstPatchParamArray params = patch_table->GetPatchParams(array); - - for (int j = 0; j < patch_table->GetNumPatches(array); j++) { - num_faces = max(num_faces, (int)params[j].GetFaceId()); - } - } - num_faces++; - - vector quadtree; - quadtree.reserve(num_faces + table.num_patches); - quadtree.resize(num_faces); - - /* adjust offsets to make indices relative to the table */ - int handle_index = -(table.num_patches * PATCH_HANDLE_SIZE); - offset += table.total_size(); - - /* populate the quadtree from the FarPatchArrays sub-patches */ - for (int array = 0; array < table.num_arrays; array++) { - Far::ConstPatchParamArray params = patch_table->GetPatchParams(array); - - for (int i = 0; i < patch_table->GetNumPatches(array); - i++, handle_index += PATCH_HANDLE_SIZE) { - const Far::PatchParam ¶m = params[i]; - unsigned short depth = param.GetDepth(); - - PatchMapQuadNode *node = &quadtree[params[i].GetFaceId()]; - - if (depth == (param.NonQuadRoot() ? 1 : 0)) { - /* special case : regular BSpline face w/ no sub-patches */ - node->set_child(handle_index + offset); - continue; - } - - int u = param.GetU(); - int v = param.GetV(); - int pdepth = param.NonQuadRoot() ? depth - 2 : depth - 1; - int half = 1 << pdepth; - - for (int j = 0; j < depth; j++) { - int delta = half >> 1; - - int quadrant = resolve_quadrant(half, u, v); - assert(quadrant >= 0); - - half = delta; - - if (j == pdepth) { - /* we have reached the depth of the sub-patch : add a leaf */ - assert(!(node->children[quadrant] & PATCH_MAP_NODE_IS_SET)); - node->set_child(quadrant, handle_index + offset, true); - break; - } - else { - /* travel down the child node of the corresponding quadrant */ - if (!(node->children[quadrant] & PATCH_MAP_NODE_IS_SET)) { - /* create a new branch in the quadrant */ - quadtree.push_back(PatchMapQuadNode()); - - int idx = (int)quadtree.size() - 1; - node->set_child(quadrant, idx * 4 + offset, false); - - node = &quadtree[idx]; - } - else { - /* travel down an existing branch */ - uint idx = node->children[quadrant] & PATCH_MAP_NODE_INDEX_MASK; - node = &(quadtree[(idx - offset) / 4]); - } - } - } - } - } - - /* copy into table */ - assert(table.table.size() == table.total_size()); - uint map_offset = table.total_size(); - - table.num_nodes = quadtree.size() * 4; - table.table.resize(table.total_size()); - - uint *data = &table.table[map_offset]; - - for (int i = 0; i < quadtree.size(); i++) { - for (int j = 0; j < 4; j++) { - assert(quadtree[i].children[j] & PATCH_MAP_NODE_IS_SET); - *(data++) = quadtree[i].children[j]; - } - } -} - -#endif - -/* packed patch table functions */ - -size_t PackedPatchTable::total_size() -{ - return num_arrays * PATCH_ARRAY_SIZE + num_indices + - num_patches * (PATCH_PARAM_SIZE + PATCH_HANDLE_SIZE) + num_nodes * PATCH_NODE_SIZE; -} - -void PackedPatchTable::pack(Far::PatchTable *patch_table, int offset) -{ - num_arrays = 0; - num_patches = 0; - num_indices = 0; - num_nodes = 0; - -#ifdef WITH_OPENSUBDIV - num_arrays = patch_table->GetNumPatchArrays(); - - for (int i = 0; i < num_arrays; i++) { - int patches = patch_table->GetNumPatches(i); - int num_control = patch_table->GetPatchArrayDescriptor(i).GetNumControlVertices(); - - num_patches += patches; - num_indices += patches * num_control; - } - - table.resize(total_size()); - uint *data = table.data(); - - uint *array = data; - uint *index = array + num_arrays * PATCH_ARRAY_SIZE; - uint *param = index + num_indices; - uint *handle = param + num_patches * PATCH_PARAM_SIZE; - - uint current_param = 0; - - for (int i = 0; i < num_arrays; i++) { - *(array++) = patch_table->GetPatchArrayDescriptor(i).GetType(); - *(array++) = patch_table->GetNumPatches(i); - *(array++) = (index - data) + offset; - *(array++) = (param - data) + offset; - - Far::ConstIndexArray indices = patch_table->GetPatchArrayVertices(i); - - for (int j = 0; j < indices.size(); j++) { - *(index++) = indices[j]; - } - - const Far::PatchParamTable ¶m_table = patch_table->GetPatchParamTable(); - - int num_control = patch_table->GetPatchArrayDescriptor(i).GetNumControlVertices(); - int patches = patch_table->GetNumPatches(i); - - for (int j = 0; j < patches; j++, current_param++) { - *(param++) = param_table[current_param].field0; - *(param++) = param_table[current_param].field1; - - *(handle++) = (array - data) - PATCH_ARRAY_SIZE + offset; - *(handle++) = (param - data) - PATCH_PARAM_SIZE + offset; - *(handle++) = j * num_control; - } - } - - build_patch_map(*this, patch_table, offset); -#else - (void)patch_table; - (void)offset; -#endif -} - -void PackedPatchTable::copy_adjusting_offsets(uint *dest, int doffset) -{ - uint *src = table.data(); - - /* arrays */ - for (int i = 0; i < num_arrays; i++) { - *(dest++) = *(src++); - *(dest++) = *(src++); - *(dest++) = *(src++) + doffset; - *(dest++) = *(src++) + doffset; - } - - /* indices */ - for (int i = 0; i < num_indices; i++) { - *(dest++) = *(src++); - } - - /* params */ - for (int i = 0; i < num_patches; i++) { - *(dest++) = *(src++); - *(dest++) = *(src++); - } - - /* handles */ - for (int i = 0; i < num_patches; i++) { - *(dest++) = *(src++) + doffset; - *(dest++) = *(src++) + doffset; - *(dest++) = *(src++); - } - - /* nodes */ - for (int i = 0; i < num_nodes; i++) { - *(dest++) = *(src++) + doffset; - } -} - -CCL_NAMESPACE_END diff --git a/intern/cycles/subd/subd_patch_table.h b/intern/cycles/subd/subd_patch_table.h deleted file mode 100644 index 118d410f8f0..00000000000 --- a/intern/cycles/subd/subd_patch_table.h +++ /dev/null @@ -1,64 +0,0 @@ -/* - * Copyright 2011-2016 Blender Foundation - * - * Licensed under the Apache License, Version 2.0 (the "License"); - * you may not use this file except in compliance with the License. - * You may obtain a copy of the License at - * - * http://www.apache.org/licenses/LICENSE-2.0 - * - * Unless required by applicable law or agreed to in writing, software - * distributed under the License is distributed on an "AS IS" BASIS, - * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. - * See the License for the specific language governing permissions and - * limitations under the License. - */ - -#ifndef __SUBD_PATCH_TABLE_H__ -#define __SUBD_PATCH_TABLE_H__ - -#include "util/util_array.h" -#include "util/util_types.h" - -#ifdef WITH_OPENSUBDIV -# ifdef _MSC_VER -# include "iso646.h" -# endif - -# include -#endif - -CCL_NAMESPACE_BEGIN - -#ifdef WITH_OPENSUBDIV -using namespace OpenSubdiv; -#else -/* forward declare for when OpenSubdiv is unavailable */ -namespace Far { -struct PatchTable; -} -#endif - -#define PATCH_ARRAY_SIZE 4 -#define PATCH_PARAM_SIZE 2 -#define PATCH_HANDLE_SIZE 3 -#define PATCH_NODE_SIZE 1 - -struct PackedPatchTable { - array table; - - size_t num_arrays; - size_t num_indices; - size_t num_patches; - size_t num_nodes; - - /* calculated size from num_* members */ - size_t total_size(); - - void pack(Far::PatchTable *patch_table, int offset = 0); - void copy_adjusting_offsets(uint *dest, int doffset); -}; - -CCL_NAMESPACE_END - -#endif /* __SUBD_PATCH_TABLE_H__ */ diff --git a/intern/cycles/subd/subd_split.cpp b/intern/cycles/subd/subd_split.cpp deleted file mode 100644 index 6b352ab02c3..00000000000 --- a/intern/cycles/subd/subd_split.cpp +++ /dev/null @@ -1,748 +0,0 @@ -/* - * Copyright 2011-2013 Blender Foundation - * - * Licensed under the Apache License, Version 2.0 (the "License"); - * you may not use this file except in compliance with the License. - * You may obtain a copy of the License at - * - * http://www.apache.org/licenses/LICENSE-2.0 - * - * Unless required by applicable law or agreed to in writing, software - * distributed under the License is distributed on an "AS IS" BASIS, - * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. - * See the License for the specific language governing permissions and - * limitations under the License. - */ - -#include "scene/camera.h" -#include "scene/mesh.h" - -#include "subd/subd_dice.h" -#include "subd/subd_patch.h" -#include "subd/subd_split.h" - -#include "util/util_algorithm.h" -#include "util/util_foreach.h" -#include "util/util_hash.h" -#include "util/util_math.h" -#include "util/util_types.h" - -CCL_NAMESPACE_BEGIN - -/* DiagSplit */ - -#define DSPLIT_NON_UNIFORM -1 -#define STITCH_NGON_CENTER_VERT_INDEX_OFFSET 0x60000000 -#define STITCH_NGON_SPLIT_EDGE_CENTER_VERT_TAG (0x60000000 - 1) - -DiagSplit::DiagSplit(const SubdParams ¶ms_) : params(params_) -{ -} - -float3 DiagSplit::to_world(Patch *patch, float2 uv) -{ - float3 P; - - patch->eval(&P, NULL, NULL, NULL, uv.x, uv.y); - if (params.camera) - P = transform_point(¶ms.objecttoworld, P); - - return P; -} - -static void order_float2(float2 &a, float2 &b) -{ - if (b.x < a.x || b.y < a.y) { - swap(a, b); - } -} - -int DiagSplit::T(Patch *patch, float2 Pstart, float2 Pend, bool recursive_resolve) -{ - order_float2(Pstart, Pend); /* May not be necessary, but better to be safe. */ - - float Lsum = 0.0f; - float Lmax = 0.0f; - - float3 Plast = to_world(patch, Pstart); - - for (int i = 1; i < params.test_steps; i++) { - float t = i / (float)(params.test_steps - 1); - - float3 P = to_world(patch, Pstart + t * (Pend - Pstart)); - - float L; - - if (!params.camera) { - L = len(P - Plast); - } - else { - Camera *cam = params.camera; - - float pixel_width = cam->world_to_raster_size((P + Plast) * 0.5f); - L = len(P - Plast) / pixel_width; - } - - Lsum += L; - Lmax = max(L, Lmax); - - Plast = P; - } - - int tmin = (int)ceilf(Lsum / params.dicing_rate); - int tmax = (int)ceilf((params.test_steps - 1) * Lmax / - params.dicing_rate); // XXX paper says N instead of N-1, seems wrong? - int res = max(tmax, 1); - - if (tmax - tmin > params.split_threshold) { - if (!recursive_resolve) { - res = DSPLIT_NON_UNIFORM; - } - else { - float2 P = (Pstart + Pend) * 0.5f; - res = T(patch, Pstart, P, true) + T(patch, P, Pend, true); - } - } - - limit_edge_factor(res, patch, Pstart, Pend); - return res; -} - -void DiagSplit::partition_edge( - Patch *patch, float2 *P, int *t0, int *t1, float2 Pstart, float2 Pend, int t) -{ - if (t == DSPLIT_NON_UNIFORM) { - *P = (Pstart + Pend) * 0.5f; - *t0 = T(patch, Pstart, *P); - *t1 = T(patch, *P, Pend); - } - else { - assert(t >= 2); /* Need at least two segments to partition into. */ - - int I = (int)floorf((float)t * 0.5f); - *P = interp(Pstart, Pend, I / (float)t); - *t0 = I; - *t1 = t - I; - } -} - -void DiagSplit::limit_edge_factor(int &T, Patch *patch, float2 Pstart, float2 Pend) -{ - int max_t = 1 << params.max_level; - int max_t_for_edge = int(max_t * len(Pstart - Pend)); - - if (patch->from_ngon) { - max_t_for_edge >>= 1; /* Initial split of ngon causes edges to extend half the distance. */ - } - - T = (max_t_for_edge <= 1) ? 1 : min(T, max_t_for_edge); - - assert(T >= 1 || T == DSPLIT_NON_UNIFORM); -} - -void DiagSplit::resolve_edge_factors(Subpatch &sub) -{ - /* Resolve DSPLIT_NON_UNIFORM to actual T value if splitting is no longer possible. */ - if (sub.edge_u0.T == 1 && sub.edge_u1.T == DSPLIT_NON_UNIFORM) { - sub.edge_u1.T = T(sub.patch, sub.c01, sub.c11, true); - } - if (sub.edge_u1.T == 1 && sub.edge_u0.T == DSPLIT_NON_UNIFORM) { - sub.edge_u0.T = T(sub.patch, sub.c00, sub.c10, true); - } - if (sub.edge_v0.T == 1 && sub.edge_v1.T == DSPLIT_NON_UNIFORM) { - sub.edge_v1.T = T(sub.patch, sub.c11, sub.c10, true); - } - if (sub.edge_v1.T == 1 && sub.edge_v0.T == DSPLIT_NON_UNIFORM) { - sub.edge_v0.T = T(sub.patch, sub.c01, sub.c00, true); - } -} - -void DiagSplit::split(Subpatch &sub, int depth) -{ - if (depth > 32) { - /* We should never get here, but just in case end recursion safely. */ - assert(!"diagsplit recursion limit reached"); - - sub.edge_u0.T = 1; - sub.edge_u1.T = 1; - sub.edge_v0.T = 1; - sub.edge_v1.T = 1; - - subpatches.push_back(sub); - return; - } - - bool split_u = (sub.edge_u0.T == DSPLIT_NON_UNIFORM || sub.edge_u1.T == DSPLIT_NON_UNIFORM); - bool split_v = (sub.edge_v0.T == DSPLIT_NON_UNIFORM || sub.edge_v1.T == DSPLIT_NON_UNIFORM); - - /* Split subpatches such that the ratio of T for opposite edges doesn't - * exceed 1.5, this reduces over tessellation for some patches - */ - /* clang-format off */ - if (min(sub.edge_u0.T, sub.edge_u1.T) > 8 && /* Must be uniform and preferably greater than 8 to split. */ - min(sub.edge_v0.T, sub.edge_v1.T) >= 2 && /* Must be uniform and at least 2 to split. */ - max(sub.edge_u0.T, sub.edge_u1.T) / min(sub.edge_u0.T, sub.edge_u1.T) > 1.5f) - { - split_v = true; - } - if (min(sub.edge_v0.T, sub.edge_v1.T) > 8 && - min(sub.edge_u0.T, sub.edge_u1.T) >= 2 && - max(sub.edge_v0.T, sub.edge_v1.T) / min(sub.edge_v0.T, sub.edge_v1.T) > 1.5f) - { - split_u = true; - } - /* clang-format on */ - - /* Alternate axis. */ - if (split_u && split_v) { - split_u = depth % 2; - } - - if (!split_u && !split_v) { - /* Add the unsplit subpatch. */ - subpatches.push_back(sub); - Subpatch &subpatch = subpatches[subpatches.size() - 1]; - - /* Update T values and offsets. */ - for (int i = 0; i < 4; i++) { - Subpatch::edge_t &edge = subpatch.edges[i]; - - edge.offset = edge.edge->T; - edge.edge->T += edge.T; - } - } - else { - /* Copy into new subpatches. */ - Subpatch sub_a = sub; - Subpatch sub_b = sub; - - /* Pointers to various subpatch elements. */ - Subpatch::edge_t *sub_across_0, *sub_across_1; - Subpatch::edge_t *sub_a_across_0, *sub_a_across_1; - Subpatch::edge_t *sub_b_across_0, *sub_b_across_1; - - Subpatch::edge_t *sub_a_split, *sub_b_split; - - float2 *Pa, *Pb, *Pc, *Pd; - - /* Set pointers based on split axis. */ - if (split_u) { - sub_across_0 = &sub.edge_u0; - sub_across_1 = &sub.edge_u1; - sub_a_across_0 = &sub_a.edge_u0; - sub_a_across_1 = &sub_a.edge_u1; - sub_b_across_0 = &sub_b.edge_u0; - sub_b_across_1 = &sub_b.edge_u1; - - sub_a_split = &sub_a.edge_v1; - sub_b_split = &sub_b.edge_v0; - - Pa = &sub_a.c11; - Pb = &sub_a.c10; - Pc = &sub_b.c01; - Pd = &sub_b.c00; - } - else { - sub_across_0 = &sub.edge_v0; - sub_across_1 = &sub.edge_v1; - sub_a_across_0 = &sub_a.edge_v0; - sub_a_across_1 = &sub_a.edge_v1; - sub_b_across_0 = &sub_b.edge_v0; - sub_b_across_1 = &sub_b.edge_v1; - - sub_a_split = &sub_a.edge_u0; - sub_b_split = &sub_b.edge_u1; - - Pa = &sub_a.c10; - Pb = &sub_a.c00; - Pc = &sub_b.c11; - Pd = &sub_b.c01; - } - - /* Partition edges */ - float2 P0, P1; - - partition_edge( - sub.patch, &P0, &sub_a_across_0->T, &sub_b_across_0->T, *Pd, *Pb, sub_across_0->T); - partition_edge( - sub.patch, &P1, &sub_a_across_1->T, &sub_b_across_1->T, *Pc, *Pa, sub_across_1->T); - - /* Split */ - *Pa = P1; - *Pb = P0; - - *Pc = P1; - *Pd = P0; - - int tsplit = T(sub.patch, P0, P1); - - if (depth == -2 && tsplit == 1) { - tsplit = 2; /* Ensure we can always split at depth -1. */ - } - - sub_a_split->T = tsplit; - sub_b_split->T = tsplit; - - resolve_edge_factors(sub_a); - resolve_edge_factors(sub_b); - - /* Create new edge */ - Edge &edge = *alloc_edge(); - - sub_a_split->edge = &edge; - sub_b_split->edge = &edge; - - sub_a_split->offset = 0; - sub_b_split->offset = 0; - - sub_a_split->indices_decrease_along_edge = false; - sub_b_split->indices_decrease_along_edge = true; - - sub_a_split->sub_edges_created_in_reverse_order = !split_u; - sub_b_split->sub_edges_created_in_reverse_order = !split_u; - - edge.top_indices_decrease = sub_across_1->sub_edges_created_in_reverse_order; - edge.bottom_indices_decrease = sub_across_0->sub_edges_created_in_reverse_order; - - /* Recurse */ - edge.T = 0; - split(sub_a, depth + 1); - - int edge_t = edge.T; - (void)edge_t; - - edge.top_offset = sub_across_1->edge->T; - edge.bottom_offset = sub_across_0->edge->T; - - edge.T = 0; /* We calculate T twice along each edge. :/ */ - split(sub_b, depth + 1); - - assert(edge.T == edge_t); /* If this fails we will crash at some later point! */ - - edge.top = sub_across_1->edge; - edge.bottom = sub_across_0->edge; - } -} - -int DiagSplit::alloc_verts(int n) -{ - int a = num_alloced_verts; - num_alloced_verts += n; - return a; -} - -Edge *DiagSplit::alloc_edge() -{ - edges.emplace_back(); - return &edges.back(); -} - -void DiagSplit::split_patches(Patch *patches, size_t patches_byte_stride) -{ - int patch_index = 0; - - for (int f = 0; f < params.mesh->get_num_subd_faces(); f++) { - Mesh::SubdFace face = params.mesh->get_subd_face(f); - - Patch *patch = (Patch *)(((char *)patches) + patch_index * patches_byte_stride); - - if (face.is_quad()) { - patch_index++; - - split_quad(face, patch); - } - else { - patch_index += face.num_corners; - - split_ngon(face, patch, patches_byte_stride); - } - } - - params.mesh->vert_to_stitching_key_map.clear(); - params.mesh->vert_stitching_map.clear(); - - post_split(); -} - -static Edge *create_edge_from_corner(DiagSplit *split, - const Mesh *mesh, - const Mesh::SubdFace &face, - int corner, - bool &reversed, - int v0, - int v1) -{ - int a = mesh->get_subd_face_corners()[face.start_corner + mod(corner + 0, face.num_corners)]; - int b = mesh->get_subd_face_corners()[face.start_corner + mod(corner + 1, face.num_corners)]; - - reversed = !(b < a); - - if (b < a) { - swap(a, b); - swap(v0, v1); - } - - Edge *edge = split->alloc_edge(); - - edge->is_stitch_edge = true; - edge->stitch_start_vert_index = a; - edge->stitch_end_vert_index = b; - - edge->start_vert_index = v0; - edge->end_vert_index = v1; - - edge->stitch_edge_key = {a, b}; - - return edge; -} - -void DiagSplit::split_quad(const Mesh::SubdFace &face, Patch *patch) -{ - Subpatch subpatch(patch); - - int v = alloc_verts(4); - - bool v0_reversed, u1_reversed, v1_reversed, u0_reversed; - subpatch.edge_v0.edge = create_edge_from_corner( - this, params.mesh, face, 3, v0_reversed, v + 3, v + 0); - subpatch.edge_u1.edge = create_edge_from_corner( - this, params.mesh, face, 2, u1_reversed, v + 2, v + 3); - subpatch.edge_v1.edge = create_edge_from_corner( - this, params.mesh, face, 1, v1_reversed, v + 1, v + 2); - subpatch.edge_u0.edge = create_edge_from_corner( - this, params.mesh, face, 0, u0_reversed, v + 0, v + 1); - - subpatch.edge_v0.sub_edges_created_in_reverse_order = !v0_reversed; - subpatch.edge_u1.sub_edges_created_in_reverse_order = u1_reversed; - subpatch.edge_v1.sub_edges_created_in_reverse_order = v1_reversed; - subpatch.edge_u0.sub_edges_created_in_reverse_order = !u0_reversed; - - subpatch.edge_v0.indices_decrease_along_edge = v0_reversed; - subpatch.edge_u1.indices_decrease_along_edge = u1_reversed; - subpatch.edge_v1.indices_decrease_along_edge = v1_reversed; - subpatch.edge_u0.indices_decrease_along_edge = u0_reversed; - - /* Forces a split in both axis for quads, needed to match split of ngons into quads. */ - subpatch.edge_u0.T = DSPLIT_NON_UNIFORM; - subpatch.edge_u1.T = DSPLIT_NON_UNIFORM; - subpatch.edge_v0.T = DSPLIT_NON_UNIFORM; - subpatch.edge_v1.T = DSPLIT_NON_UNIFORM; - - split(subpatch, -2); -} - -static Edge *create_split_edge_from_corner(DiagSplit *split, - const Mesh *mesh, - const Mesh::SubdFace &face, - int corner, - int side, - bool &reversed, - int v0, - int v1, - int vc) -{ - Edge *edge = split->alloc_edge(); - - int a = mesh->get_subd_face_corners()[face.start_corner + mod(corner + 0, face.num_corners)]; - int b = mesh->get_subd_face_corners()[face.start_corner + mod(corner + 1, face.num_corners)]; - - if (b < a) { - edge->stitch_edge_key = {b, a}; - } - else { - edge->stitch_edge_key = {a, b}; - } - - reversed = !(b < a); - - if (side == 0) { - a = vc; - } - else { - b = vc; - } - - if (!reversed) { - swap(a, b); - swap(v0, v1); - } - - edge->is_stitch_edge = true; - edge->stitch_start_vert_index = a; - edge->stitch_end_vert_index = b; - - edge->start_vert_index = v0; - edge->end_vert_index = v1; - - return edge; -} - -void DiagSplit::split_ngon(const Mesh::SubdFace &face, Patch *patches, size_t patches_byte_stride) -{ - Edge *prev_edge_u0 = nullptr; - Edge *first_edge_v0 = nullptr; - - for (int corner = 0; corner < face.num_corners; corner++) { - Patch *patch = (Patch *)(((char *)patches) + corner * patches_byte_stride); - - Subpatch subpatch(patch); - - int v = alloc_verts(4); - - /* Setup edges. */ - Edge *edge_u1 = alloc_edge(); - Edge *edge_v1 = alloc_edge(); - - edge_v1->is_stitch_edge = true; - edge_u1->is_stitch_edge = true; - - edge_u1->stitch_start_vert_index = -(face.start_corner + mod(corner + 0, face.num_corners)) - - 1; - edge_u1->stitch_end_vert_index = STITCH_NGON_CENTER_VERT_INDEX_OFFSET + face.ptex_offset; - - edge_u1->start_vert_index = v + 3; - edge_u1->end_vert_index = v + 2; - - edge_u1->stitch_edge_key = {edge_u1->stitch_start_vert_index, edge_u1->stitch_end_vert_index}; - - edge_v1->stitch_start_vert_index = -(face.start_corner + mod(corner + 1, face.num_corners)) - - 1; - edge_v1->stitch_end_vert_index = STITCH_NGON_CENTER_VERT_INDEX_OFFSET + face.ptex_offset; - - edge_v1->start_vert_index = v + 1; - edge_v1->end_vert_index = v + 2; - - edge_v1->stitch_edge_key = {edge_v1->stitch_start_vert_index, edge_v1->stitch_end_vert_index}; - - bool v0_reversed, u0_reversed; - - subpatch.edge_v0.edge = create_split_edge_from_corner(this, - params.mesh, - face, - corner - 1, - 0, - v0_reversed, - v + 3, - v + 0, - STITCH_NGON_SPLIT_EDGE_CENTER_VERT_TAG); - - subpatch.edge_u1.edge = edge_u1; - subpatch.edge_v1.edge = edge_v1; - - subpatch.edge_u0.edge = create_split_edge_from_corner(this, - params.mesh, - face, - corner + 0, - 1, - u0_reversed, - v + 0, - v + 1, - STITCH_NGON_SPLIT_EDGE_CENTER_VERT_TAG); - - subpatch.edge_v0.sub_edges_created_in_reverse_order = !v0_reversed; - subpatch.edge_u1.sub_edges_created_in_reverse_order = false; - subpatch.edge_v1.sub_edges_created_in_reverse_order = true; - subpatch.edge_u0.sub_edges_created_in_reverse_order = !u0_reversed; - - subpatch.edge_v0.indices_decrease_along_edge = v0_reversed; - subpatch.edge_u1.indices_decrease_along_edge = false; - subpatch.edge_v1.indices_decrease_along_edge = true; - subpatch.edge_u0.indices_decrease_along_edge = u0_reversed; - - /* Perform split. */ - { - subpatch.edge_u0.T = T(subpatch.patch, subpatch.c00, subpatch.c10); - subpatch.edge_u1.T = T(subpatch.patch, subpatch.c01, subpatch.c11); - subpatch.edge_v0.T = T(subpatch.patch, subpatch.c00, subpatch.c01); - subpatch.edge_v1.T = T(subpatch.patch, subpatch.c10, subpatch.c11); - - resolve_edge_factors(subpatch); - - split(subpatch, 0); - } - - /* Update offsets after T is known from split. */ - edge_u1->top = subpatch.edge_v0.edge; - edge_u1->stitch_top_offset = edge_u1->top->T * (v0_reversed ? -1 : 1); - edge_v1->top = subpatch.edge_u0.edge; - edge_v1->stitch_top_offset = edge_v1->top->T * (!u0_reversed ? -1 : 1); - - if (corner == 0) { - first_edge_v0 = subpatch.edge_v0.edge; - } - - if (prev_edge_u0) { - if (v0_reversed) { - subpatch.edge_v0.edge->stitch_offset = prev_edge_u0->T; - } - else { - prev_edge_u0->stitch_offset = subpatch.edge_v0.edge->T; - } - - int T = subpatch.edge_v0.edge->T + prev_edge_u0->T; - subpatch.edge_v0.edge->stitch_edge_T = T; - prev_edge_u0->stitch_edge_T = T; - } - - if (corner == face.num_corners - 1) { - if (v0_reversed) { - subpatch.edge_u0.edge->stitch_offset = first_edge_v0->T; - } - else { - first_edge_v0->stitch_offset = subpatch.edge_u0.edge->T; - } - - int T = first_edge_v0->T + subpatch.edge_u0.edge->T; - first_edge_v0->stitch_edge_T = T; - subpatch.edge_u0.edge->stitch_edge_T = T; - } - - prev_edge_u0 = subpatch.edge_u0.edge; - } -} - -void DiagSplit::post_split() -{ - int num_stitch_verts = 0; - - /* All patches are now split, and all T values known. */ - - foreach (Edge &edge, edges) { - if (edge.second_vert_index < 0) { - edge.second_vert_index = alloc_verts(edge.T - 1); - } - - if (edge.is_stitch_edge) { - num_stitch_verts = max(num_stitch_verts, - max(edge.stitch_start_vert_index, edge.stitch_end_vert_index)); - } - } - - num_stitch_verts += 1; - - /* Map of edge key to edge stitching vert offset. */ - struct pair_hasher { - size_t operator()(const pair &k) const - { - return hash_uint2(k.first, k.second); - } - }; - typedef unordered_map, int, pair_hasher> edge_stitch_verts_map_t; - edge_stitch_verts_map_t edge_stitch_verts_map; - - foreach (Edge &edge, edges) { - if (edge.is_stitch_edge) { - if (edge.stitch_edge_T == 0) { - edge.stitch_edge_T = edge.T; - } - - if (edge_stitch_verts_map.find(edge.stitch_edge_key) == edge_stitch_verts_map.end()) { - edge_stitch_verts_map[edge.stitch_edge_key] = num_stitch_verts; - num_stitch_verts += edge.stitch_edge_T - 1; - } - } - } - - /* Set start and end indices for edges generated from a split. */ - foreach (Edge &edge, edges) { - if (edge.start_vert_index < 0) { - /* Fix up offsets. */ - if (edge.top_indices_decrease) { - edge.top_offset = edge.top->T - edge.top_offset; - } - - edge.start_vert_index = edge.top->get_vert_along_edge(edge.top_offset); - } - - if (edge.end_vert_index < 0) { - if (edge.bottom_indices_decrease) { - edge.bottom_offset = edge.bottom->T - edge.bottom_offset; - } - - edge.end_vert_index = edge.bottom->get_vert_along_edge(edge.bottom_offset); - } - } - - int vert_offset = params.mesh->verts.size(); - - /* Add verts to stitching map. */ - foreach (const Edge &edge, edges) { - if (edge.is_stitch_edge) { - int second_stitch_vert_index = edge_stitch_verts_map[edge.stitch_edge_key]; - - for (int i = 0; i <= edge.T; i++) { - /* Get proper stitching key. */ - int key; - - if (i == 0) { - key = edge.stitch_start_vert_index; - } - else if (i == edge.T) { - key = edge.stitch_end_vert_index; - } - else { - key = second_stitch_vert_index + i - 1 + edge.stitch_offset; - } - - if (key == STITCH_NGON_SPLIT_EDGE_CENTER_VERT_TAG) { - if (i == 0) { - key = second_stitch_vert_index - 1 + edge.stitch_offset; - } - else if (i == edge.T) { - key = second_stitch_vert_index - 1 + edge.T; - } - } - else if (key < 0 && edge.top) { /* ngon spoke edge */ - int s = edge_stitch_verts_map[edge.top->stitch_edge_key]; - if (edge.stitch_top_offset >= 0) { - key = s - 1 + edge.stitch_top_offset; - } - else { - key = s - 1 + edge.top->stitch_edge_T + edge.stitch_top_offset; - } - } - - /* Get real vert index. */ - int vert = edge.get_vert_along_edge(i) + vert_offset; - - /* Add to map */ - if (params.mesh->vert_to_stitching_key_map.find(vert) == - params.mesh->vert_to_stitching_key_map.end()) { - params.mesh->vert_to_stitching_key_map[vert] = key; - params.mesh->vert_stitching_map.insert({key, vert}); - } - } - } - } - - /* Dice; TODO(mai): Move this out of split. */ - QuadDice dice(params); - - int num_verts = num_alloced_verts; - int num_triangles = 0; - - for (size_t i = 0; i < subpatches.size(); i++) { - subpatches[i].inner_grid_vert_offset = num_verts; - num_verts += subpatches[i].calc_num_inner_verts(); - num_triangles += subpatches[i].calc_num_triangles(); - } - - dice.reserve(num_verts, num_triangles); - - for (size_t i = 0; i < subpatches.size(); i++) { - Subpatch &sub = subpatches[i]; - - sub.edge_u0.T = max(sub.edge_u0.T, 1); - sub.edge_u1.T = max(sub.edge_u1.T, 1); - sub.edge_v0.T = max(sub.edge_v0.T, 1); - sub.edge_v1.T = max(sub.edge_v1.T, 1); - - dice.dice(sub); - } - - /* Cleanup */ - subpatches.clear(); - edges.clear(); -} - -CCL_NAMESPACE_END diff --git a/intern/cycles/subd/subd_split.h b/intern/cycles/subd/subd_split.h deleted file mode 100644 index 7416b2fbbf8..00000000000 --- a/intern/cycles/subd/subd_split.h +++ /dev/null @@ -1,75 +0,0 @@ -/* - * Copyright 2011-2013 Blender Foundation - * - * Licensed under the Apache License, Version 2.0 (the "License"); - * you may not use this file except in compliance with the License. - * You may obtain a copy of the License at - * - * http://www.apache.org/licenses/LICENSE-2.0 - * - * Unless required by applicable law or agreed to in writing, software - * distributed under the License is distributed on an "AS IS" BASIS, - * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. - * See the License for the specific language governing permissions and - * limitations under the License. - */ - -#ifndef __SUBD_SPLIT_H__ -#define __SUBD_SPLIT_H__ - -/* DiagSplit: Parallel, Crack-free, Adaptive Tessellation for Micropolygon Rendering - * Splits up patches and determines edge tessellation factors for dicing. Patch - * evaluation at arbitrary points is required for this to work. See the paper - * for more details. */ - -#include "subd/subd_dice.h" -#include "subd/subd_subpatch.h" - -#include "util/util_deque.h" -#include "util/util_types.h" -#include "util/util_vector.h" - -#include - -CCL_NAMESPACE_BEGIN - -class Mesh; -class Patch; - -class DiagSplit { - SubdParams params; - - vector subpatches; - /* `deque` is used so that element pointers remain valid when size is changed. */ - deque edges; - - float3 to_world(Patch *patch, float2 uv); - int T(Patch *patch, float2 Pstart, float2 Pend, bool recursive_resolve = false); - - void limit_edge_factor(int &T, Patch *patch, float2 Pstart, float2 Pend); - void resolve_edge_factors(Subpatch &sub); - - void partition_edge( - Patch *patch, float2 *P, int *t0, int *t1, float2 Pstart, float2 Pend, int t); - - void split(Subpatch &sub, int depth = 0); - - int num_alloced_verts = 0; - int alloc_verts(int n); /* Returns start index of new verts. */ - - public: - Edge *alloc_edge(); - - explicit DiagSplit(const SubdParams ¶ms); - - void split_patches(Patch *patches, size_t patches_byte_stride); - - void split_quad(const Mesh::SubdFace &face, Patch *patch); - void split_ngon(const Mesh::SubdFace &face, Patch *patches, size_t patches_byte_stride); - - void post_split(); -}; - -CCL_NAMESPACE_END - -#endif /* __SUBD_SPLIT_H__ */ diff --git a/intern/cycles/subd/subd_subpatch.h b/intern/cycles/subd/subd_subpatch.h deleted file mode 100644 index cdaa310916a..00000000000 --- a/intern/cycles/subd/subd_subpatch.h +++ /dev/null @@ -1,219 +0,0 @@ -/* - * Copyright 2011-2018 Blender Foundation - * - * Licensed under the Apache License, Version 2.0 (the "License"); - * you may not use this file except in compliance with the License. - * You may obtain a copy of the License at - * - * http://www.apache.org/licenses/LICENSE-2.0 - * - * Unless required by applicable law or agreed to in writing, software - * distributed under the License is distributed on an "AS IS" BASIS, - * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. - * See the License for the specific language governing permissions and - * limitations under the License. - */ - -#ifndef __SUBD_SUBPATCH_H__ -#define __SUBD_SUBPATCH_H__ - -#include "util/util_map.h" -#include "util/util_types.h" - -CCL_NAMESPACE_BEGIN - -/* Subpatch */ - -class Subpatch { - public: - class Patch *patch; /* Patch this is a subpatch of. */ - int inner_grid_vert_offset; - - struct edge_t { - int T; - int offset; /* Offset along main edge, interpretation depends on the two flags below. */ - - bool indices_decrease_along_edge; - bool sub_edges_created_in_reverse_order; - - struct Edge *edge; - - int get_vert_along_edge(int n) const; - }; - - /* - * eu1 - * c01 --------- c11 - * | | - * ev0 | | ev1 - * | | - * c00 --------- c10 - * eu0 - */ - - union { - float2 corners[4]; /* UV within patch, clockwise starting from uv (0, 0) towards (0, 1) etc. */ - struct { - float2 c00, c01, c11, c10; - }; - }; - - union { - edge_t - edges[4]; /* Edges of this subpatch, each edge starts at the corner of the same index. */ - struct { - edge_t edge_v0, edge_u1, edge_v1, edge_u0; - }; - }; - - explicit Subpatch(Patch *patch = nullptr) - : patch(patch), - c00(zero_float2()), - c01(make_float2(0.0f, 1.0f)), - c11(one_float2()), - c10(make_float2(1.0f, 0.0f)) - { - } - - Subpatch(Patch *patch, float2 c00, float2 c01, float2 c11, float2 c10) - : patch(patch), c00(c00), c01(c01), c11(c11), c10(c10) - { - } - - int calc_num_inner_verts() const - { - int Mu = max(edge_u0.T, edge_u1.T); - int Mv = max(edge_v0.T, edge_v1.T); - Mu = max(Mu, 2); - Mv = max(Mv, 2); - return (Mu - 1) * (Mv - 1); - } - - int calc_num_triangles() const - { - int Mu = max(edge_u0.T, edge_u1.T); - int Mv = max(edge_v0.T, edge_v1.T); - Mu = max(Mu, 2); - Mv = max(Mv, 2); - - int inner_triangles = (Mu - 2) * (Mv - 2) * 2; - int edge_triangles = edge_u0.T + edge_u1.T + edge_v0.T + edge_v1.T + (Mu - 2) * 2 + - (Mv - 2) * 2; - - return inner_triangles + edge_triangles; - } - - int get_vert_along_edge(int e, int n) const; - - int get_vert_along_grid_edge(int edge, int n) const - { - int Mu = max(edge_u0.T, edge_u1.T); - int Mv = max(edge_v0.T, edge_v1.T); - Mu = max(Mu, 2); - Mv = max(Mv, 2); - - switch (edge) { - case 0: - return inner_grid_vert_offset + n * (Mu - 1); - case 1: - return inner_grid_vert_offset + (Mu - 1) * (Mv - 2) + n; - case 2: - return inner_grid_vert_offset + ((Mu - 1) * (Mv - 1) - 1) - n * (Mu - 1); - case 3: - return inner_grid_vert_offset + (Mu - 2) - n; - } - - return -1; - } -}; - -struct Edge { - /* Number of segments the edge will be diced into, see DiagSplit paper. */ - int T; - - /* top is edge adjacent to start, bottom is adjacent to end. */ - Edge *top, *bottom; - - int top_offset, bottom_offset; - bool top_indices_decrease, bottom_indices_decrease; - - int start_vert_index; - int end_vert_index; - - /* Index of the second vert from this edges corner along the edge towards the next corner. */ - int second_vert_index; - - /* Vertices on edge are to be stitched. */ - bool is_stitch_edge; - - /* Key to match this edge with others to be stitched with. - * The ints in the pair are ordered stitching indices */ - pair stitch_edge_key; - - /* Full T along edge (may be larger than T for edges split from ngon edges) */ - int stitch_edge_T; - int stitch_offset; - int stitch_top_offset; - int stitch_start_vert_index; - int stitch_end_vert_index; - - Edge() - : T(0), - top(nullptr), - bottom(nullptr), - top_offset(-1), - bottom_offset(-1), - top_indices_decrease(false), - bottom_indices_decrease(false), - start_vert_index(-1), - end_vert_index(-1), - second_vert_index(-1), - is_stitch_edge(false), - stitch_edge_T(0), - stitch_offset(0) - { - } - - int get_vert_along_edge(int n) const - { - assert(n >= 0 && n <= T); - - if (n == 0) { - return start_vert_index; - } - else if (n == T) { - return end_vert_index; - } - - return second_vert_index + n - 1; - } -}; - -inline int Subpatch::edge_t::get_vert_along_edge(int n) const -{ - assert(n >= 0 && n <= T); - - if (!indices_decrease_along_edge && !sub_edges_created_in_reverse_order) { - n = offset + n; - } - else if (!indices_decrease_along_edge && sub_edges_created_in_reverse_order) { - n = edge->T - offset - T + n; - } - else if (indices_decrease_along_edge && !sub_edges_created_in_reverse_order) { - n = offset + T - n; - } - else if (indices_decrease_along_edge && sub_edges_created_in_reverse_order) { - n = edge->T - offset - n; - } - - return edge->get_vert_along_edge(n); -} - -inline int Subpatch::get_vert_along_edge(int edge, int n) const -{ - return edges[edge].get_vert_along_edge(n); -} - -CCL_NAMESPACE_END - -#endif /* __SUBD_SUBPATCH_H__ */ diff --git a/intern/cycles/subd/subpatch.h b/intern/cycles/subd/subpatch.h new file mode 100644 index 00000000000..0ba8ed88aa8 --- /dev/null +++ b/intern/cycles/subd/subpatch.h @@ -0,0 +1,219 @@ +/* + * Copyright 2011-2018 Blender Foundation + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +#ifndef __SUBD_SUBPATCH_H__ +#define __SUBD_SUBPATCH_H__ + +#include "util/map.h" +#include "util/types.h" + +CCL_NAMESPACE_BEGIN + +/* Subpatch */ + +class Subpatch { + public: + class Patch *patch; /* Patch this is a subpatch of. */ + int inner_grid_vert_offset; + + struct edge_t { + int T; + int offset; /* Offset along main edge, interpretation depends on the two flags below. */ + + bool indices_decrease_along_edge; + bool sub_edges_created_in_reverse_order; + + struct Edge *edge; + + int get_vert_along_edge(int n) const; + }; + + /* + * eu1 + * c01 --------- c11 + * | | + * ev0 | | ev1 + * | | + * c00 --------- c10 + * eu0 + */ + + union { + float2 corners[4]; /* UV within patch, clockwise starting from uv (0, 0) towards (0, 1) etc. */ + struct { + float2 c00, c01, c11, c10; + }; + }; + + union { + edge_t + edges[4]; /* Edges of this subpatch, each edge starts at the corner of the same index. */ + struct { + edge_t edge_v0, edge_u1, edge_v1, edge_u0; + }; + }; + + explicit Subpatch(Patch *patch = nullptr) + : patch(patch), + c00(zero_float2()), + c01(make_float2(0.0f, 1.0f)), + c11(one_float2()), + c10(make_float2(1.0f, 0.0f)) + { + } + + Subpatch(Patch *patch, float2 c00, float2 c01, float2 c11, float2 c10) + : patch(patch), c00(c00), c01(c01), c11(c11), c10(c10) + { + } + + int calc_num_inner_verts() const + { + int Mu = max(edge_u0.T, edge_u1.T); + int Mv = max(edge_v0.T, edge_v1.T); + Mu = max(Mu, 2); + Mv = max(Mv, 2); + return (Mu - 1) * (Mv - 1); + } + + int calc_num_triangles() const + { + int Mu = max(edge_u0.T, edge_u1.T); + int Mv = max(edge_v0.T, edge_v1.T); + Mu = max(Mu, 2); + Mv = max(Mv, 2); + + int inner_triangles = (Mu - 2) * (Mv - 2) * 2; + int edge_triangles = edge_u0.T + edge_u1.T + edge_v0.T + edge_v1.T + (Mu - 2) * 2 + + (Mv - 2) * 2; + + return inner_triangles + edge_triangles; + } + + int get_vert_along_edge(int e, int n) const; + + int get_vert_along_grid_edge(int edge, int n) const + { + int Mu = max(edge_u0.T, edge_u1.T); + int Mv = max(edge_v0.T, edge_v1.T); + Mu = max(Mu, 2); + Mv = max(Mv, 2); + + switch (edge) { + case 0: + return inner_grid_vert_offset + n * (Mu - 1); + case 1: + return inner_grid_vert_offset + (Mu - 1) * (Mv - 2) + n; + case 2: + return inner_grid_vert_offset + ((Mu - 1) * (Mv - 1) - 1) - n * (Mu - 1); + case 3: + return inner_grid_vert_offset + (Mu - 2) - n; + } + + return -1; + } +}; + +struct Edge { + /* Number of segments the edge will be diced into, see DiagSplit paper. */ + int T; + + /* top is edge adjacent to start, bottom is adjacent to end. */ + Edge *top, *bottom; + + int top_offset, bottom_offset; + bool top_indices_decrease, bottom_indices_decrease; + + int start_vert_index; + int end_vert_index; + + /* Index of the second vert from this edges corner along the edge towards the next corner. */ + int second_vert_index; + + /* Vertices on edge are to be stitched. */ + bool is_stitch_edge; + + /* Key to match this edge with others to be stitched with. + * The ints in the pair are ordered stitching indices */ + pair stitch_edge_key; + + /* Full T along edge (may be larger than T for edges split from ngon edges) */ + int stitch_edge_T; + int stitch_offset; + int stitch_top_offset; + int stitch_start_vert_index; + int stitch_end_vert_index; + + Edge() + : T(0), + top(nullptr), + bottom(nullptr), + top_offset(-1), + bottom_offset(-1), + top_indices_decrease(false), + bottom_indices_decrease(false), + start_vert_index(-1), + end_vert_index(-1), + second_vert_index(-1), + is_stitch_edge(false), + stitch_edge_T(0), + stitch_offset(0) + { + } + + int get_vert_along_edge(int n) const + { + assert(n >= 0 && n <= T); + + if (n == 0) { + return start_vert_index; + } + else if (n == T) { + return end_vert_index; + } + + return second_vert_index + n - 1; + } +}; + +inline int Subpatch::edge_t::get_vert_along_edge(int n) const +{ + assert(n >= 0 && n <= T); + + if (!indices_decrease_along_edge && !sub_edges_created_in_reverse_order) { + n = offset + n; + } + else if (!indices_decrease_along_edge && sub_edges_created_in_reverse_order) { + n = edge->T - offset - T + n; + } + else if (indices_decrease_along_edge && !sub_edges_created_in_reverse_order) { + n = offset + T - n; + } + else if (indices_decrease_along_edge && sub_edges_created_in_reverse_order) { + n = edge->T - offset - n; + } + + return edge->get_vert_along_edge(n); +} + +inline int Subpatch::get_vert_along_edge(int edge, int n) const +{ + return edges[edge].get_vert_along_edge(n); +} + +CCL_NAMESPACE_END + +#endif /* __SUBD_SUBPATCH_H__ */ -- cgit v1.2.3