1// Copyright 2009-2021 Intel Corporation
2// SPDX-License-Identifier: Apache-2.0
3
4#pragma once
5
6#include "catmullclark_coefficients.h"
7
8namespace embree
9{
10 class __aligned(32) HalfEdge
11 {
12 friend class SubdivMesh;
13 public:
14
15 enum PatchType : char {
16 BILINEAR_PATCH = 0, //!< a bilinear patch
17 REGULAR_QUAD_PATCH = 1, //!< a regular quad patch can be represented as a B-Spline
18 IRREGULAR_QUAD_PATCH = 2, //!< an irregular quad patch can be represented as a Gregory patch
19 COMPLEX_PATCH = 3 //!< these patches need subdivision and cannot be processed by the above fast code paths
20 };
21
22 enum VertexType : char {
23 REGULAR_VERTEX = 0, //!< regular vertex
24 NON_MANIFOLD_EDGE_VERTEX = 1, //!< vertex of a non-manifold edge
25 };
26
27 __forceinline friend PatchType max( const PatchType& ty0, const PatchType& ty1) {
28 return (PatchType) max((int)ty0,(int)ty1);
29 }
30
31 struct Edge
32 {
33 /*! edge constructor */
34 __forceinline Edge(const uint32_t v0, const uint32_t v1)
35 : v0(v0), v1(v1) {}
36
37 /*! create an 64 bit identifier that is unique for the not oriented edge */
38 __forceinline operator uint64_t() const
39 {
40 uint32_t p0 = v0, p1 = v1;
41 if (p0<p1) std::swap(p0,p1);
42 return (((uint64_t)p0) << 32) | (uint64_t)p1;
43 }
44
45 public:
46 uint32_t v0,v1; //!< start and end vertex of the edge
47 };
48
49 HalfEdge ()
50 : vtx_index(-1), next_half_edge_ofs(0), prev_half_edge_ofs(0), opposite_half_edge_ofs(0), edge_crease_weight(0),
51 vertex_crease_weight(0), edge_level(0), patch_type(COMPLEX_PATCH), vertex_type(REGULAR_VERTEX)
52 {
53 static_assert(sizeof(HalfEdge) == 32, "invalid half edge size");
54 }
55
56 __forceinline bool hasOpposite() const { return opposite_half_edge_ofs != 0; }
57 __forceinline void setOpposite(HalfEdge* opposite) { opposite_half_edge_ofs = int(opposite-this); }
58
59 __forceinline HalfEdge* next() { assert( next_half_edge_ofs != 0 ); return &this[next_half_edge_ofs]; }
60 __forceinline const HalfEdge* next() const { assert( next_half_edge_ofs != 0 ); return &this[next_half_edge_ofs]; }
61
62 __forceinline HalfEdge* prev() { assert( prev_half_edge_ofs != 0 ); return &this[prev_half_edge_ofs]; }
63 __forceinline const HalfEdge* prev() const { assert( prev_half_edge_ofs != 0 ); return &this[prev_half_edge_ofs]; }
64
65 __forceinline HalfEdge* opposite() { assert( opposite_half_edge_ofs != 0 ); return &this[opposite_half_edge_ofs]; }
66 __forceinline const HalfEdge* opposite() const { assert( opposite_half_edge_ofs != 0 ); return &this[opposite_half_edge_ofs]; }
67
68 __forceinline HalfEdge* rotate() { return opposite()->next(); }
69 __forceinline const HalfEdge* rotate() const { return opposite()->next(); }
70
71 __forceinline unsigned int getStartVertexIndex() const { return vtx_index; }
72 __forceinline unsigned int getEndVertexIndex () const { return next()->vtx_index; }
73 __forceinline Edge getEdge () const { return Edge(getStartVertexIndex(),getEndVertexIndex()); }
74
75
76 /*! tests if the start vertex of the edge is regular */
77 __forceinline PatchType vertexType() const
78 {
79 const HalfEdge* p = this;
80 size_t face_valence = 0;
81 bool hasBorder = false;
82
83 do
84 {
85 /* we need subdivision to handle edge creases */
86 if (p->hasOpposite() && p->edge_crease_weight > 0.0f)
87 return COMPLEX_PATCH;
88
89 face_valence++;
90
91 /* test for quad */
92 const HalfEdge* pp = p;
93 pp = pp->next(); if (pp == p) return COMPLEX_PATCH;
94 pp = pp->next(); if (pp == p) return COMPLEX_PATCH;
95 pp = pp->next(); if (pp == p) return COMPLEX_PATCH;
96 pp = pp->next(); if (pp != p) return COMPLEX_PATCH;
97
98 /* continue with next face */
99 p = p->prev();
100 if (likely(p->hasOpposite()))
101 p = p->opposite();
102
103 /* if there is no opposite go the long way to the other side of the border */
104 else
105 {
106 face_valence++;
107 hasBorder = true;
108 p = this;
109 while (p->hasOpposite())
110 p = p->rotate();
111 }
112 } while (p != this);
113
114 /* calculate vertex type */
115 if (face_valence == 2 && hasBorder) {
116 if (vertex_crease_weight == 0.0f ) return REGULAR_QUAD_PATCH;
117 else if (vertex_crease_weight == float(inf)) return REGULAR_QUAD_PATCH;
118 else return COMPLEX_PATCH;
119 }
120 else if (vertex_crease_weight != 0.0f) return COMPLEX_PATCH;
121 else if (face_valence == 3 && hasBorder) return REGULAR_QUAD_PATCH;
122 else if (face_valence == 4 && !hasBorder) return REGULAR_QUAD_PATCH;
123 else return IRREGULAR_QUAD_PATCH;
124 }
125
126 /*! tests if this edge is part of a bilinear patch */
127 __forceinline bool bilinearVertex() const {
128 return vertex_crease_weight == float(inf) && edge_crease_weight == float(inf);
129 }
130
131 /*! calculates the type of the patch */
132 __forceinline PatchType patchType() const
133 {
134 const HalfEdge* p = this;
135 PatchType ret = REGULAR_QUAD_PATCH;
136 bool bilinear = true;
137
138 ret = max(ret,p->vertexType());
139 bilinear &= p->bilinearVertex();
140 if ((p = p->next()) == this) return COMPLEX_PATCH;
141
142 ret = max(ret,p->vertexType());
143 bilinear &= p->bilinearVertex();
144 if ((p = p->next()) == this) return COMPLEX_PATCH;
145
146 ret = max(ret,p->vertexType());
147 bilinear &= p->bilinearVertex();
148 if ((p = p->next()) == this) return COMPLEX_PATCH;
149
150 ret = max(ret,p->vertexType());
151 bilinear &= p->bilinearVertex();
152 if ((p = p->next()) != this) return COMPLEX_PATCH;
153
154 if (bilinear) return BILINEAR_PATCH;
155 return ret;
156 }
157
158 /*! tests if the face is a regular b-spline face */
159 __forceinline bool isRegularFace() const {
160 return patch_type == REGULAR_QUAD_PATCH;
161 }
162
163 /*! tests if the face can be diced (using bspline or gregory patch) */
164 __forceinline bool isGregoryFace() const {
165 return patch_type == IRREGULAR_QUAD_PATCH || patch_type == REGULAR_QUAD_PATCH;
166 }
167
168 /*! tests if the base vertex of this half edge is a corner vertex */
169 __forceinline bool isCorner() const {
170 return !hasOpposite() && !prev()->hasOpposite();
171 }
172
173 /*! tests if the vertex is attached to any border */
174 __forceinline bool vertexHasBorder() const
175 {
176 const HalfEdge* p = this;
177 do {
178 if (!p->hasOpposite()) return true;
179 p = p->rotate();
180 } while (p != this);
181 return false;
182 }
183
184 /*! tests if the face this half edge belongs to has some border */
185 __forceinline bool faceHasBorder() const
186 {
187 const HalfEdge* p = this;
188 do {
189 if (p->vertexHasBorder() && (p->vertex_type != HalfEdge::NON_MANIFOLD_EDGE_VERTEX)) return true;
190 p = p->next();
191 } while (p != this);
192 return false;
193 }
194
195 /*! calculates conservative bounds of a catmull clark subdivision face */
196 __forceinline BBox3fa bounds(const BufferView<Vec3fa>& vertices) const
197 {
198 BBox3fa bounds = this->get1RingBounds(vertices);
199 for (const HalfEdge* p=this->next(); p!=this; p=p->next())
200 bounds.extend(p->get1RingBounds(vertices));
201 return bounds;
202 }
203
204 /*! tests if this is a valid patch */
205 __forceinline bool valid(const BufferView<Vec3fa>& vertices) const
206 {
207 size_t N = 1;
208 if (!this->validRing(vertices)) return false;
209 for (const HalfEdge* p=this->next(); p!=this; p=p->next(), N++) {
210 if (!p->validRing(vertices)) return false;
211 }
212 return N >= 3 && N <= MAX_PATCH_VALENCE;
213 }
214
215 /*! counts number of polygon edges */
216 __forceinline unsigned int numEdges() const
217 {
218 unsigned int N = 1;
219 for (const HalfEdge* p=this->next(); p!=this; p=p->next(), N++);
220 return N;
221 }
222
223 /*! calculates face and edge valence */
224 __forceinline void calculateFaceValenceAndEdgeValence(size_t& faceValence, size_t& edgeValence) const
225 {
226 faceValence = 0;
227 edgeValence = 0;
228
229 const HalfEdge* p = this;
230 do
231 {
232 /* calculate bounds of current face */
233 unsigned int numEdges = p->numEdges();
234 assert(numEdges >= 3);
235 edgeValence += numEdges-2;
236
237 faceValence++;
238 p = p->prev();
239
240 /* continue with next face */
241 if (likely(p->hasOpposite()))
242 p = p->opposite();
243
244 /* if there is no opposite go the long way to the other side of the border */
245 else {
246 faceValence++;
247 edgeValence++;
248 p = this;
249 while (p->hasOpposite())
250 p = p->opposite()->next();
251 }
252
253 } while (p != this);
254 }
255
256 /*! stream output */
257 friend __forceinline std::ostream &operator<<(std::ostream &o, const HalfEdge &h)
258 {
259 return o << "{ " <<
260 "vertex = " << h.vtx_index << ", " << //" -> " << h.next()->vtx_index << ", " <<
261 "prev = " << h.prev_half_edge_ofs << ", " <<
262 "next = " << h.next_half_edge_ofs << ", " <<
263 "opposite = " << h.opposite_half_edge_ofs << ", " <<
264 "edge_crease = " << h.edge_crease_weight << ", " <<
265 "vertex_crease = " << h.vertex_crease_weight << ", " <<
266 //"edge_level = " << h.edge_level <<
267 " }";
268 }
269
270 private:
271
272 /*! calculates the bounds of the face associated with the half-edge */
273 __forceinline BBox3fa getFaceBounds(const BufferView<Vec3fa>& vertices) const
274 {
275 BBox3fa b = vertices[getStartVertexIndex()];
276 for (const HalfEdge* p = next(); p!=this; p=p->next()) {
277 b.extend(vertices[p->getStartVertexIndex()]);
278 }
279 return b;
280 }
281
282 /*! calculates the bounds of the 1-ring associated with the vertex of the half-edge */
283 __forceinline BBox3fa get1RingBounds(const BufferView<Vec3fa>& vertices) const
284 {
285 BBox3fa bounds = empty;
286 const HalfEdge* p = this;
287 do
288 {
289 /* calculate bounds of current face */
290 bounds.extend(p->getFaceBounds(vertices));
291 p = p->prev();
292
293 /* continue with next face */
294 if (likely(p->hasOpposite()))
295 p = p->opposite();
296
297 /* if there is no opposite go the long way to the other side of the border */
298 else {
299 p = this;
300 while (p->hasOpposite())
301 p = p->opposite()->next();
302 }
303
304 } while (p != this);
305
306 return bounds;
307 }
308
309 /*! tests if this is a valid face */
310 __forceinline bool validFace(const BufferView<Vec3fa>& vertices, size_t& N) const
311 {
312 const Vec3fa v = vertices[getStartVertexIndex()];
313 if (!isvalid(v)) return false;
314 size_t n = 1;
315 for (const HalfEdge* p = next(); p!=this; p=p->next(), n++) {
316 const Vec3fa v = vertices[p->getStartVertexIndex()];
317 if (!isvalid(v)) return false;
318 }
319 N += n-2;
320 return n >= 3 && n <= MAX_PATCH_VALENCE;
321 }
322
323 /*! tests if this is a valid ring */
324 __forceinline bool validRing(const BufferView<Vec3fa>& vertices) const
325 {
326 size_t faceValence = 0;
327 size_t edgeValence = 0;
328
329 const HalfEdge* p = this;
330 do
331 {
332 /* calculate bounds of current face */
333 if (!p->validFace(vertices,edgeValence))
334 return false;
335
336 faceValence++;
337 p = p->prev();
338
339 /* continue with next face */
340 if (likely(p->hasOpposite()))
341 p = p->opposite();
342
343 /* if there is no opposite go the long way to the other side of the border */
344 else {
345 faceValence++;
346 edgeValence++;
347 p = this;
348 while (p->hasOpposite())
349 p = p->opposite()->next();
350 }
351
352 } while (p != this);
353
354 return faceValence <= MAX_RING_FACE_VALENCE && edgeValence <= MAX_RING_EDGE_VALENCE;
355 }
356
357 private:
358 unsigned int vtx_index; //!< index of edge start vertex
359 int next_half_edge_ofs; //!< relative offset to next half edge of face
360 int prev_half_edge_ofs; //!< relative offset to previous half edge of face
361 int opposite_half_edge_ofs; //!< relative offset to opposite half edge
362
363 public:
364 float edge_crease_weight; //!< crease weight attached to edge
365 float vertex_crease_weight; //!< crease weight attached to start vertex
366 float edge_level; //!< subdivision factor for edge
367 PatchType patch_type; //!< stores type of subdiv patch
368 VertexType vertex_type; //!< stores type of the start vertex
369 char align[2];
370 };
371}
372