1// Copyright 2009-2021 Intel Corporation
2// SPDX-License-Identifier: Apache-2.0
3
4#pragma once
5
6#include "catmullclark_patch.h"
7#include "bilinear_patch.h"
8#include "bspline_patch.h"
9#include "bezier_patch.h"
10#include "gregory_patch.h"
11#include "tessellation_cache.h"
12
13#if 1
14#define PATCH_DEBUG_SUBDIVISION(ptr,x,y,z)
15#else
16#define PATCH_DEBUG_SUBDIVISION(ptr,x,y,z) \
17 { \
18 size_t hex = (size_t)ptr; \
19 for (size_t i=0; i<4; i++) hex = hex ^ (hex >> 8); \
20 const float c = (float)(((hex >> 0) ^ (hex >> 4) ^ (hex >> 8) ^ (hex >> 12) ^ (hex >> 16))&0xf)/15.0f; \
21 if (P) *P = Vertex(0.5f+0.5f*x,0.5f+0.5f*y,0.5f+0.5f*z,0.0f); \
22 }
23#endif
24
25#define PATCH_MAX_CACHE_DEPTH 2
26//#define PATCH_MIN_RESOLUTION 1 // FIXME: not yet completely implemented
27#define PATCH_MAX_EVAL_DEPTH_IRREGULAR 10 // maximum evaluation depth at irregular vertices (has to be larger or equal than PATCH_MAX_CACHE_DEPTH)
28#define PATCH_MAX_EVAL_DEPTH_CREASE 10 // maximum evaluation depth at crease features (has to be larger or equal than PATCH_MAX_CACHE_DEPTH)
29#define PATCH_USE_GREGORY 1 // 0 = no gregory, 1 = fill, 2 = as early as possible
30
31#if PATCH_USE_GREGORY==2
32#define PATCH_USE_BEZIER_PATCH 1 // enable use of bezier instead of b-spline patches
33#else
34#define PATCH_USE_BEZIER_PATCH 0 // enable use of bezier instead of b-spline patches
35#endif
36
37#if PATCH_USE_BEZIER_PATCH
38# define RegularPatch BezierPatch
39# define RegularPatchT BezierPatchT<Vertex,Vertex_t>
40#else
41# define RegularPatch BSplinePatch
42# define RegularPatchT BSplinePatchT<Vertex,Vertex_t>
43#endif
44
45#if PATCH_USE_GREGORY
46#define IrregularFillPatch GregoryPatch
47#define IrregularFillPatchT GregoryPatchT<Vertex,Vertex_t>
48#else
49#define IrregularFillPatch BilinearPatch
50#define IrregularFillPatchT BilinearPatchT<Vertex,Vertex_t>
51#endif
52
53namespace embree
54{
55 template<typename Vertex, typename Vertex_t = Vertex>
56 struct __aligned(64) PatchT
57 {
58 public:
59
60 typedef GeneralCatmullClarkPatchT<Vertex,Vertex_t> GeneralCatmullClarkPatch;
61 typedef CatmullClarkPatchT<Vertex,Vertex_t> CatmullClarkPatch;
62 typedef CatmullClark1RingT<Vertex,Vertex_t> CatmullClarkRing;
63 typedef BezierCurveT<Vertex> BezierCurve;
64
65 enum Type {
66 INVALID_PATCH = 0,
67 BILINEAR_PATCH = 1,
68 BSPLINE_PATCH = 2,
69 BEZIER_PATCH = 3,
70 GREGORY_PATCH = 4,
71 SUBDIVIDED_GENERAL_PATCH = 7,
72 SUBDIVIDED_QUAD_PATCH = 8,
73 EVAL_PATCH = 9,
74 };
75
76 struct Ref
77 {
78 __forceinline Ref(void* p = nullptr)
79 : ptr((size_t)p) {}
80
81 __forceinline operator bool() const { return ptr != 0; }
82 __forceinline operator size_t() const { return ptr; }
83
84 __forceinline Ref (Type ty, void* in)
85 : ptr(((size_t)in)+ty) { assert((((size_t)in) & 0xF) == 0); }
86
87 __forceinline Type type () const { return (Type)(ptr & 0xF); }
88 __forceinline void* object() const { return (void*) (ptr & ~0xF); }
89
90 size_t ptr;
91 };
92
93 struct EvalPatch
94 {
95 /* creates EvalPatch from a CatmullClarkPatch */
96 template<typename Allocator>
97 __noinline static Ref create(const Allocator& alloc, const CatmullClarkPatch& patch)
98 {
99 size_t ofs = 0, bytes = patch.bytes();
100 void* ptr = alloc(bytes);
101 patch.serialize(ptr,ofs);
102 assert(ofs == bytes);
103 return Ref(EVAL_PATCH, ptr);
104 }
105 };
106
107 struct BilinearPatch
108 {
109 /* creates BilinearPatch from a CatmullClarkPatch */
110 template<typename Allocator>
111 __noinline static Ref create(const Allocator& alloc, const CatmullClarkPatch& patch,
112 const BezierCurve* border0, const BezierCurve* border1, const BezierCurve* border2, const BezierCurve* border3) {
113 return Ref(BILINEAR_PATCH, new (alloc(sizeof(BilinearPatch))) BilinearPatch(patch));
114 }
115
116 __forceinline BilinearPatch (const CatmullClarkPatch& patch)
117 : patch(patch) {}
118
119 /* creates BilinearPatch from 4 vertices */
120 template<typename Allocator>
121 __noinline static Ref create(const Allocator& alloc, const HalfEdge* edge, const char* vertices, size_t stride) {
122 return Ref(BILINEAR_PATCH, new (alloc(sizeof(BilinearPatch))) BilinearPatch(edge,vertices,stride));
123 }
124
125 __forceinline BilinearPatch (const HalfEdge* edge, const char* vertices, size_t stride)
126 : patch(edge,vertices,stride) {}
127
128 public:
129 BilinearPatchT<Vertex,Vertex_t> patch;
130 };
131
132 struct BSplinePatch
133 {
134 /* creates BSplinePatch from a half edge */
135 template<typename Allocator>
136 __noinline static Ref create(const Allocator& alloc, const HalfEdge* edge, const char* vertices, size_t stride) {
137 return Ref(BSPLINE_PATCH, new (alloc(sizeof(BSplinePatch))) BSplinePatch(edge,vertices,stride));
138 }
139
140 __forceinline BSplinePatch (const HalfEdge* edge, const char* vertices, size_t stride)
141 : patch(edge,vertices,stride) {}
142
143 /* creates BSplinePatch from a CatmullClarkPatch */
144 template<typename Allocator>
145 __noinline static Ref create(const Allocator& alloc, const CatmullClarkPatch& patch,
146 const BezierCurve* border0, const BezierCurve* border1, const BezierCurve* border2, const BezierCurve* border3) {
147 return Ref(BSPLINE_PATCH, new (alloc(sizeof(BSplinePatch))) BSplinePatch(patch,border0,border1,border2,border3));
148 }
149
150 __forceinline BSplinePatch (const CatmullClarkPatch& patch, const BezierCurve* border0, const BezierCurve* border1, const BezierCurve* border2, const BezierCurve* border3)
151 : patch(patch,border0,border1,border2,border3) {}
152
153 public:
154 BSplinePatchT<Vertex,Vertex_t> patch;
155 };
156
157 struct BezierPatch
158 {
159 /* creates BezierPatch from a half edge */
160 template<typename Allocator>
161 __noinline static Ref create(const Allocator& alloc, const HalfEdge* edge, const char* vertices, size_t stride) {
162 return Ref(BEZIER_PATCH, new (alloc(sizeof(BezierPatch))) BezierPatch(edge,vertices,stride));
163 }
164
165 __forceinline BezierPatch (const HalfEdge* edge, const char* vertices, size_t stride)
166 : patch(edge,vertices,stride) {}
167
168 /* creates Bezier from a CatmullClarkPatch */
169 template<typename Allocator>
170 __noinline static Ref create(const Allocator& alloc, const CatmullClarkPatch& patch,
171 const BezierCurve* border0, const BezierCurve* border1, const BezierCurve* border2, const BezierCurve* border3) {
172 return Ref(BEZIER_PATCH, new (alloc(sizeof(BezierPatch))) BezierPatch(patch,border0,border1,border2,border3));
173 }
174
175 __forceinline BezierPatch (const CatmullClarkPatch& patch, const BezierCurve* border0, const BezierCurve* border1, const BezierCurve* border2, const BezierCurve* border3)
176 : patch(patch,border0,border1,border2,border3) {}
177
178 public:
179 BezierPatchT<Vertex,Vertex_t> patch;
180 };
181
182 struct GregoryPatch
183 {
184 /* creates GregoryPatch from half edge */
185 template<typename Allocator>
186 __noinline static Ref create(const Allocator& alloc, const HalfEdge* edge, const char* vertices, size_t stride) {
187 return Ref(GREGORY_PATCH, new (alloc(sizeof(GregoryPatch))) GregoryPatch(edge,vertices,stride));
188 }
189
190 __forceinline GregoryPatch (const HalfEdge* edge, const char* vertices, size_t stride)
191 : patch(CatmullClarkPatch(edge,vertices,stride)) {}
192
193 /* creates GregoryPatch from CatmullClarkPatch */
194 template<typename Allocator>
195 __noinline static Ref create(const Allocator& alloc, const CatmullClarkPatch& patch,
196 const BezierCurve* border0, const BezierCurve* border1, const BezierCurve* border2, const BezierCurve* border3) {
197 return Ref(GREGORY_PATCH, new (alloc(sizeof(GregoryPatch))) GregoryPatch(patch,border0,border1,border2,border3));
198 }
199
200 __forceinline GregoryPatch (const CatmullClarkPatch& patch, const BezierCurve* border0, const BezierCurve* border1, const BezierCurve* border2, const BezierCurve* border3)
201 : patch(patch,border0,border1,border2,border3) {}
202
203 public:
204 GregoryPatchT<Vertex,Vertex_t> patch;
205 };
206
207 struct SubdividedQuadPatch
208 {
209 template<typename Allocator>
210 __noinline static Ref create(const Allocator& alloc, Ref children[4]) {
211 return Ref(SUBDIVIDED_QUAD_PATCH, new (alloc(sizeof(SubdividedQuadPatch))) SubdividedQuadPatch(children));
212 }
213
214 __forceinline SubdividedQuadPatch(Ref children[4]) {
215 for (size_t i=0; i<4; i++) child[i] = children[i];
216 }
217
218 public:
219 Ref child[4];
220 };
221
222 struct SubdividedGeneralPatch
223 {
224 template<typename Allocator>
225 __noinline static Ref create(const Allocator& alloc, Ref* children, const unsigned N) {
226 return Ref(SUBDIVIDED_GENERAL_PATCH, new (alloc(sizeof(SubdividedGeneralPatch))) SubdividedGeneralPatch(children,N));
227 }
228
229 __forceinline SubdividedGeneralPatch(Ref* children, const unsigned N) : N(N) {
230 for (unsigned i=0; i<N; i++) child[i] = children[i];
231 }
232
233 unsigned N;
234 Ref child[MAX_PATCH_VALENCE];
235 };
236
237 /*! Default constructor. */
238 __forceinline PatchT () {}
239
240 template<typename Allocator>
241 __noinline static Ref create(const Allocator& alloc, const HalfEdge* edge, const char* vertices, size_t stride)
242 {
243 if (PATCH_MAX_CACHE_DEPTH == 0)
244 return nullptr;
245
246 Ref child(0);
247 switch (edge->patch_type) {
248 case HalfEdge::BILINEAR_PATCH: child = BilinearPatch::create(alloc,edge,vertices,stride); break;
249 case HalfEdge::REGULAR_QUAD_PATCH: child = RegularPatch::create(alloc,edge,vertices,stride); break;
250#if PATCH_USE_GREGORY == 2
251 case HalfEdge::IRREGULAR_QUAD_PATCH: child = GregoryPatch::create(alloc,edge,vertices,stride); break;
252#endif
253 default: {
254 GeneralCatmullClarkPatch patch(edge,vertices,stride);
255 child = PatchT::create(alloc,patch,edge,vertices,stride,0);
256 }
257 }
258 return child;
259 }
260
261 template<typename Allocator>
262 __noinline static Ref create(const Allocator& alloc, GeneralCatmullClarkPatch& patch, const HalfEdge* edge, const char* vertices, size_t stride, size_t depth)
263 {
264 /* convert into standard quad patch if possible */
265 if (likely(patch.isQuadPatch()))
266 {
267 CatmullClarkPatch qpatch; patch.init(qpatch);
268 return PatchT::create(alloc,qpatch,edge,vertices,stride,depth);
269 }
270
271 /* do only cache up to some depth */
272 if (depth >= PATCH_MAX_CACHE_DEPTH)
273 return nullptr;
274
275 /* subdivide patch */
276 unsigned N;
277 array_t<CatmullClarkPatch,GeneralCatmullClarkPatch::SIZE> patches;
278 patch.subdivide(patches,N);
279
280 if (N == 4)
281 {
282 Ref child[4];
283#if PATCH_USE_GREGORY == 2
284 BezierCurve borders[GeneralCatmullClarkPatch::SIZE]; patch.getLimitBorder(borders);
285 BezierCurve border0l,border0r; borders[0].subdivide(border0l,border0r);
286 BezierCurve border1l,border1r; borders[1].subdivide(border1l,border1r);
287 BezierCurve border2l,border2r; borders[2].subdivide(border2l,border2r);
288 BezierCurve border3l,border3r; borders[3].subdivide(border3l,border3r);
289 GeneralCatmullClarkPatch::fix_quad_ring_order(patches);
290 child[0] = PatchT::create(alloc,patches[0],edge,vertices,stride,depth+1,&border0l,nullptr,nullptr,&border3r);
291 child[1] = PatchT::create(alloc,patches[1],edge,vertices,stride,depth+1,&border0r,&border1l,nullptr,nullptr);
292 child[2] = PatchT::create(alloc,patches[2],edge,vertices,stride,depth+1,nullptr,&border1r,&border2l,nullptr);
293 child[3] = PatchT::create(alloc,patches[3],edge,vertices,stride,depth+1,nullptr,nullptr,&border2r,&border3l);
294#else
295 GeneralCatmullClarkPatch::fix_quad_ring_order(patches);
296 for (size_t i=0; i<4; i++)
297 child[i] = PatchT::create(alloc,patches[i],edge,vertices,stride,depth+1);
298#endif
299 return SubdividedQuadPatch::create(alloc,child);
300 }
301 else
302 {
303 assert(N<MAX_PATCH_VALENCE);
304 Ref child[MAX_PATCH_VALENCE];
305
306#if PATCH_USE_GREGORY == 2
307 BezierCurve borders[GeneralCatmullClarkPatch::SIZE];
308 patch.getLimitBorder(borders);
309
310 for (size_t i0=0; i0<N; i0++) {
311 const size_t i2 = i0==0 ? N-1 : i0-1;
312 BezierCurve border0l,border0r; borders[i0].subdivide(border0l,border0r);
313 BezierCurve border2l,border2r; borders[i2].subdivide(border2l,border2r);
314 child[i0] = PatchT::create(alloc,patches[i0],edge,vertices,stride,depth+1, &border0l, nullptr, nullptr, &border2r);
315 }
316#else
317 for (size_t i=0; i<N; i++)
318 child[i] = PatchT::create(alloc,patches[i],edge,vertices,stride,depth+1);
319#endif
320 return SubdividedGeneralPatch::create(alloc,child,N);
321 }
322
323 return nullptr;
324 }
325
326 static __forceinline bool final(const CatmullClarkPatch& patch, const typename CatmullClarkRing::Type type, size_t depth)
327 {
328 const size_t max_eval_depth = (type & CatmullClarkRing::TYPE_CREASES) ? PATCH_MAX_EVAL_DEPTH_CREASE : PATCH_MAX_EVAL_DEPTH_IRREGULAR;
329//#if PATCH_MIN_RESOLUTION
330// return patch.isFinalResolution(PATCH_MIN_RESOLUTION) || depth>=max_eval_depth;
331//#else
332 return depth>=max_eval_depth;
333//#endif
334 }
335
336 template<typename Allocator>
337 __noinline static Ref create(const Allocator& alloc, CatmullClarkPatch& patch, const HalfEdge* edge, const char* vertices, size_t stride, size_t depth,
338 const BezierCurve* border0 = nullptr, const BezierCurve* border1 = nullptr, const BezierCurve* border2 = nullptr, const BezierCurve* border3 = nullptr)
339 {
340 const typename CatmullClarkPatch::Type ty = patch.type();
341 if (unlikely(final(patch,ty,depth))) {
342 if (ty & CatmullClarkRing::TYPE_REGULAR) return RegularPatch::create(alloc,patch,border0,border1,border2,border3);
343 else return IrregularFillPatch::create(alloc,patch,border0,border1,border2,border3);
344 }
345 else if (ty & CatmullClarkRing::TYPE_REGULAR_CREASES) {
346 assert(depth > 0); return RegularPatch::create(alloc,patch,border0,border1,border2,border3);
347 }
348#if PATCH_USE_GREGORY == 2
349 else if (ty & CatmullClarkRing::TYPE_GREGORY_CREASES) {
350 assert(depth > 0); return GregoryPatch::create(alloc,patch,border0,border1,border2,border3);
351 }
352#endif
353 else if (depth >= PATCH_MAX_CACHE_DEPTH) {
354 return EvalPatch::create(alloc,patch);
355 }
356
357 else
358 {
359 Ref child[4];
360 array_t<CatmullClarkPatch,4> patches;
361 patch.subdivide(patches);
362
363 for (size_t i=0; i<4; i++)
364 child[i] = PatchT::create(alloc,patches[i],edge,vertices,stride,depth+1);
365 return SubdividedQuadPatch::create(alloc,child);
366 }
367 }
368 };
369
370 typedef PatchT<Vec3fa,Vec3fa_t> Patch3fa;
371}
372