1// Copyright 2009-2021 Intel Corporation
2// SPDX-License-Identifier: Apache-2.0
3
4#pragma once
5
6#include "geometry.h"
7#include "buffer.h"
8#include "../subdiv/half_edge.h"
9#include "../subdiv/tessellation_cache.h"
10#include "../subdiv/catmullclark_coefficients.h"
11#include "../subdiv/patch.h"
12#include "../../common/algorithms/parallel_map.h"
13#include "../../common/algorithms/parallel_set.h"
14
15namespace embree
16{
17 class SubdivMesh : public Geometry
18 {
19 ALIGNED_CLASS_(16);
20 public:
21
22 typedef HalfEdge::Edge Edge;
23
24 /*! type of this geometry */
25 static const Geometry::GTypeMask geom_type = Geometry::MTY_SUBDIV_MESH;
26
27 /*! structure used to sort half edges using radix sort by their key */
28 struct KeyHalfEdge
29 {
30 KeyHalfEdge() {}
31
32 KeyHalfEdge (uint64_t key, HalfEdge* edge)
33 : key(key), edge(edge) {}
34
35 __forceinline operator uint64_t() const {
36 return key;
37 }
38
39 friend __forceinline bool operator<(const KeyHalfEdge& e0, const KeyHalfEdge& e1) {
40 return e0.key < e1.key;
41 }
42
43 public:
44 uint64_t key;
45 HalfEdge* edge;
46 };
47
48 public:
49
50 /*! subdiv mesh construction */
51 SubdivMesh(Device* device);
52
53 public:
54 void setMask (unsigned mask);
55 void setSubdivisionMode (unsigned int topologyID, RTCSubdivisionMode mode);
56 void setVertexAttributeTopology(unsigned int vertexAttribID, unsigned int topologyID);
57 void setNumTimeSteps (unsigned int numTimeSteps);
58 void setVertexAttributeCount (unsigned int N);
59 void setTopologyCount (unsigned int N);
60 void setBuffer(RTCBufferType type, unsigned int slot, RTCFormat format, const Ref<Buffer>& buffer, size_t offset, size_t stride, unsigned int num);
61 void* getBuffer(RTCBufferType type, unsigned int slot);
62 void updateBuffer(RTCBufferType type, unsigned int slot);
63 void setTessellationRate(float N);
64 bool verify();
65 void commit();
66 void addElementsToCount (GeometryCounts & counts) const;
67 void setDisplacementFunction (RTCDisplacementFunctionN func);
68 unsigned int getFirstHalfEdge(unsigned int faceID);
69 unsigned int getFace(unsigned int edgeID);
70 unsigned int getNextHalfEdge(unsigned int edgeID);
71 unsigned int getPreviousHalfEdge(unsigned int edgeID);
72 unsigned int getOppositeHalfEdge(unsigned int topologyID, unsigned int edgeID);
73
74 public:
75
76 /*! return the number of faces */
77 size_t numFaces() const {
78 return faceVertices.size();
79 }
80
81 /*! return the number of edges */
82 size_t numEdges() const {
83 return topology[0].vertexIndices.size();
84 }
85
86 /*! return the number of vertices */
87 size_t numVertices() const {
88 return vertices[0].size();
89 }
90
91 /*! calculates the bounds of the i'th subdivision patch at the j'th timestep */
92 __forceinline BBox3fa bounds(size_t i, size_t j = 0) const {
93 return topology[0].getHalfEdge(i)->bounds(vertices[j]);
94 }
95
96 /*! check if the i'th primitive is valid */
97 __forceinline bool valid(size_t i) const {
98 return topology[0].valid(i) && !invalidFace(i);
99 }
100
101 /*! check if the i'th primitive is valid for the j'th time range */
102 __forceinline bool valid(size_t i, size_t j) const {
103 return topology[0].valid(i) && !invalidFace(i,j);
104 }
105
106 /*! prints some statistics */
107 void printStatistics();
108
109 /*! initializes the half edge data structure */
110 void initializeHalfEdgeStructures ();
111
112 public:
113
114 /*! returns the vertex buffer for some time step */
115 __forceinline const BufferView<Vec3fa>& getVertexBuffer( const size_t t = 0 ) const {
116 return vertices[t];
117 }
118
119 /* returns tessellation level of edge */
120 __forceinline float getEdgeLevel(const size_t i) const
121 {
122 if (levels) return clamp(levels[i],1.0f,4096.0f); // FIXME: do we want to limit edge level?
123 else return clamp(tessellationRate,1.0f,4096.0f); // FIXME: do we want to limit edge level?
124 }
125
126 public:
127 RTCDisplacementFunctionN displFunc; //!< displacement function
128
129 /*! all buffers in this section are provided by the application */
130 public:
131
132 /*! the topology contains all data that may differ when
133 * interpolating different user data buffers */
134 struct Topology
135 {
136 public:
137
138 /*! Default topology construction */
139 Topology () : halfEdges(nullptr,0) {}
140
141 /*! Topology initialization */
142 Topology (SubdivMesh* mesh);
143
144 /*! make the class movable */
145 public:
146 Topology (Topology&& other) // FIXME: this is only required to workaround compilation issues under Windows
147 : mesh(std::move(other.mesh)),
148 vertexIndices(std::move(other.vertexIndices)),
149 subdiv_mode(std::move(other.subdiv_mode)),
150 halfEdges(std::move(other.halfEdges)),
151 halfEdges0(std::move(other.halfEdges0)),
152 halfEdges1(std::move(other.halfEdges1)) {}
153
154 Topology& operator= (Topology&& other) // FIXME: this is only required to workaround compilation issues under Windows
155 {
156 mesh = std::move(other.mesh);
157 vertexIndices = std::move(other.vertexIndices);
158 subdiv_mode = std::move(other.subdiv_mode);
159 halfEdges = std::move(other.halfEdges);
160 halfEdges0 = std::move(other.halfEdges0);
161 halfEdges1 = std::move(other.halfEdges1);
162 return *this;
163 }
164
165 public:
166 /*! check if the i'th primitive is valid in this topology */
167 __forceinline bool valid(size_t i) const
168 {
169 if (unlikely(subdiv_mode == RTC_SUBDIVISION_MODE_NO_BOUNDARY)) {
170 if (getHalfEdge(i)->faceHasBorder()) return false;
171 }
172 return true;
173 }
174
175 /*! updates the interpolation mode for the topology */
176 void setSubdivisionMode (RTCSubdivisionMode mode);
177
178 /*! marks all buffers as modified */
179 void update ();
180
181 /*! verifies index array */
182 bool verify (size_t numVertices);
183
184 /*! initializes the half edge data structure */
185 void initializeHalfEdgeStructures ();
186
187 private:
188
189 /*! recalculates the half edges */
190 void calculateHalfEdges();
191
192 /*! updates half edges when recalculation is not necessary */
193 void updateHalfEdges();
194
195 /*! user input data */
196 public:
197
198 SubdivMesh* mesh;
199
200 /*! indices of the vertices composing each face */
201 BufferView<unsigned int> vertexIndices;
202
203 /*! subdiv interpolation mode */
204 RTCSubdivisionMode subdiv_mode;
205
206 /*! generated data */
207 public:
208
209 /*! returns the start half edge for face f */
210 __forceinline const HalfEdge* getHalfEdge ( const size_t f ) const {
211 return &halfEdges[mesh->faceStartEdge[f]];
212 }
213
214 /*! Half edge structure, generated by initHalfEdgeStructures */
215 mvector<HalfEdge> halfEdges;
216
217 /*! the following data is only required during construction of the
218 * half edge structure and can be cleared for static scenes */
219 private:
220
221 /*! two arrays used to sort the half edges */
222 std::vector<KeyHalfEdge> halfEdges0;
223 std::vector<KeyHalfEdge> halfEdges1;
224 };
225
226 /*! returns the start half edge for topology t and face f */
227 __forceinline const HalfEdge* getHalfEdge ( const size_t t , const size_t f ) const {
228 return topology[t].getHalfEdge(f);
229 }
230
231 /*! buffer containing the number of vertices for each face */
232 BufferView<unsigned int> faceVertices;
233
234 /*! array of topologies */
235 vector<Topology> topology;
236
237 /*! vertex buffer (one buffer for each time step) */
238 vector<BufferView<Vec3fa>> vertices;
239
240 /*! user data buffers */
241 vector<RawBufferView> vertexAttribs;
242
243 /*! edge crease buffer containing edges (pairs of vertices) that carry edge crease weights */
244 BufferView<Edge> edge_creases;
245
246 /*! edge crease weights for each edge of the edge_creases buffer */
247 BufferView<float> edge_crease_weights;
248
249 /*! vertex crease buffer containing all vertices that carry vertex crease weights */
250 BufferView<unsigned int> vertex_creases;
251
252 /*! vertex crease weights for each vertex of the vertex_creases buffer */
253 BufferView<float> vertex_crease_weights;
254
255 /*! subdivision level for each half edge of the vertexIndices buffer */
256 BufferView<float> levels;
257 float tessellationRate; // constant rate that is used when levels is not set
258
259 /*! buffer that marks specific faces as holes */
260 BufferView<unsigned> holes;
261
262 /*! all data in this section is generated by initializeHalfEdgeStructures function */
263 private:
264
265 /*! number of half edges used by faces */
266 size_t numHalfEdges;
267
268 /*! fast lookup table to find the first half edge for some face */
269 mvector<uint32_t> faceStartEdge;
270
271 /*! fast lookup table to find the face for some half edge */
272 mvector<uint32_t> halfEdgeFace;
273
274 /*! set with all holes */
275 parallel_set<uint32_t> holeSet;
276
277 /*! fast lookup table to detect invalid faces */
278 mvector<char> invalid_face;
279
280 /*! test if face i is invalid in timestep j */
281 __forceinline char& invalidFace(size_t i, size_t j = 0) { return invalid_face[i*numTimeSteps+j]; }
282 __forceinline const char& invalidFace(size_t i, size_t j = 0) const { return invalid_face[i*numTimeSteps+j]; }
283
284 /*! interpolation cache */
285 public:
286 static __forceinline size_t numInterpolationSlots4(size_t stride) { return (stride+15)/16; }
287 static __forceinline size_t numInterpolationSlots8(size_t stride) { return (stride+31)/32; }
288 static __forceinline size_t interpolationSlot(size_t prim, size_t slot, size_t stride) {
289 const size_t slots = numInterpolationSlots4(stride);
290 assert(slot < slots);
291 return slots*prim+slot;
292 }
293 std::vector<std::vector<SharedLazyTessellationCache::CacheEntry>> vertex_buffer_tags;
294 std::vector<std::vector<SharedLazyTessellationCache::CacheEntry>> vertex_attrib_buffer_tags;
295 std::vector<Patch3fa::Ref> patch_eval_trees;
296
297 /*! the following data is only required during construction of the
298 * half edge structure and can be cleared for static scenes */
299 private:
300
301 /*! map with all vertex creases */
302 parallel_map<uint32_t,float> vertexCreaseMap;
303
304 /*! map with all edge creases */
305 parallel_map<uint64_t,float> edgeCreaseMap;
306
307 protected:
308
309 /*! counts number of geometry commits */
310 size_t commitCounter;
311 };
312
313 namespace isa
314 {
315 struct SubdivMeshISA : public SubdivMesh
316 {
317 SubdivMeshISA (Device* device)
318 : SubdivMesh(device) {}
319
320 void interpolate(const RTCInterpolateArguments* const args);
321 void interpolateN(const RTCInterpolateNArguments* const args);
322 };
323 }
324
325 DECLARE_ISA_FUNCTION(SubdivMesh*, createSubdivMesh, Device*);
326};
327