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 
15 namespace 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     {
KeyHalfEdgeKeyHalfEdge30       KeyHalfEdge() {}
31 
KeyHalfEdgeKeyHalfEdge32       KeyHalfEdge (uint64_t key, HalfEdge* edge)
33       : key(key), edge(edge) {}
34 
uint64_tKeyHalfEdge35       __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 */
numFaces()77     size_t numFaces() const {
78       return faceVertices.size();
79     }
80 
81     /*! return the number of edges */
numEdges()82     size_t numEdges() const {
83       return topology[0].vertexIndices.size();
84     }
85 
86     /*! return the number of vertices */
numVertices()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 */
valid(size_t i)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 */
valid(size_t i,size_t j)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 */
getEdgeLevel(const size_t i)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 */
TopologyTopology139       Topology () : halfEdges(nullptr,0) {}
140 
141       /*! Topology initialization */
142       Topology (SubdivMesh* mesh);
143 
144       /*! make the class movable */
145     public:
TopologyTopology146       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 */
validTopology167       __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 */
getHalfEdgeTopology210       __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 */
getHalfEdge(const size_t t,const size_t 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:
numInterpolationSlots4(size_t stride)286     static __forceinline size_t numInterpolationSlots4(size_t stride) { return (stride+15)/16; }
numInterpolationSlots8(size_t stride)287     static __forceinline size_t numInterpolationSlots8(size_t stride) { return (stride+31)/32; }
interpolationSlot(size_t prim,size_t slot,size_t stride)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     {
SubdivMeshISASubdivMeshISA317       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