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