Book a Demo!
CoCalc Logo Icon
StoreFeaturesDocsShareSupportNewsAboutPoliciesSign UpSign In
godotengine
GitHub Repository: godotengine/godot
 Path: blob/master/thirdparty/embree/kernels/subdiv/catmullrom_curve.h
9913 views
1
// Copyright 2009-2021 Intel Corporation

2
// SPDX-License-Identifier: Apache-2.0

3


4
#pragma once

5


6
#include "../common/default.h"

7
#include "bezier_curve.h"

8
#include "../common/scene_curves.h"

9


10
/*

11


12
  Implements Catmul Rom curves with control points p0, p1, p2, p3. At

13
  t=0 the curve goes through p1, with tangent (p2-p0)/2, and for t=1

14
  the curve goes through p2 with tangent (p3-p2)/2.

15


16
 */

17


18
namespace embree

19
{

20
  class CatmullRomBasis

21
  {

22
  public:

23


24
    template<typename T>

25
      static __forceinline Vec4<T> eval(const T& u) 

26
    {

27
      const T t  = u;

28
      const T s  = T(1.0f) - u;

29
      const T n0 = - t * s * s;

30
      const T n1 = 2.0f + t * t * (3.0f * t - 5.0f);

31
      const T n2 = 2.0f + s * s * (3.0f * s - 5.0f);

32
      const T n3 = - s * t * t;

33
      return T(0.5f) * Vec4<T>(n0, n1, n2, n3);

34
    }

35
    

36
    template<typename T>

37
      static __forceinline Vec4<T>  derivative(const T& u)

38
    {

39
      const T t  =  u;

40
      const T s  =  1.0f - u;

41
      const T n0 =  - s * s + 2.0f * s * t;

42
      const T n1 =  2.0f * t * (3.0f * t - 5.0f) + 3.0f * t * t;

43
      const T n2 =  2.0f * s * (3.0f * t + 2.0f) - 3.0f * s * s;

44
      const T n3 = -2.0f * s * t + t * t;

45
      return T(0.5f) * Vec4<T>(n0, n1, n2, n3);

46
    }

47


48
    template<typename T>

49
      static __forceinline Vec4<T>  derivative2(const T& u)

50
    {

51
      const T t  =  u;

52
      const T n0 = -3.0f * t + 2.0f;

53
      const T n1 =  9.0f * t - 5.0f;

54
      const T n2 = -9.0f * t + 4.0f;

55
      const T n3 =  3.0f * t - 1.0f;

56
      return Vec4<T>(n0, n1, n2, n3);

57
    }

58
  };

59
  

60
  struct PrecomputedCatmullRomBasis

61
  {

62
    enum { N = 16 };

63
  public:

64
    PrecomputedCatmullRomBasis() {}

65
    PrecomputedCatmullRomBasis(int shift);

66


67
    /* basis for bspline evaluation */

68
  public:

69
    float c0[N+1][N+1];

70
    float c1[N+1][N+1];

71
    float c2[N+1][N+1];

72
    float c3[N+1][N+1];

73
    

74
    /* basis for bspline derivative evaluation */

75
  public:

76
    float d0[N+1][N+1];

77
    float d1[N+1][N+1];

78
    float d2[N+1][N+1];

79
    float d3[N+1][N+1];

80
  };

81
  extern PrecomputedCatmullRomBasis catmullrom_basis0;

82
  extern PrecomputedCatmullRomBasis catmullrom_basis1;

83


84
  template<typename Vertex>

85
    struct CatmullRomCurveT

86
    {

87
      Vertex v0,v1,v2,v3;

88
      

89
      __forceinline CatmullRomCurveT() {}

90
      

91
      __forceinline CatmullRomCurveT(const Vertex& v0, const Vertex& v1, const Vertex& v2, const Vertex& v3)

92
        : v0(v0), v1(v1), v2(v2), v3(v3) {}

93


94
      __forceinline Vertex begin() const {

95
        return v1;

96
      }

97


98
      __forceinline Vertex end() const {

99
        return v2;

100
      }

101


102
      __forceinline Vertex center() const {

103
        return 0.5f*(v0+v1);

104
      }

105


106
      __forceinline BBox<Vertex> bounds() const {

107
        return merge(BBox<Vertex>(v0),BBox<Vertex>(v1),BBox<Vertex>(v2),BBox<Vertex>(v3));

108
      }

109


110
      __forceinline friend CatmullRomCurveT operator -( const CatmullRomCurveT& a, const Vertex& b ) {

111
        return CatmullRomCurveT(a.v0-b,a.v1-b,a.v2-b,a.v3-b);

112
      }

113


114
      __forceinline CatmullRomCurveT<Vec3ff> xfm_pr(const LinearSpace3fa& space, const Vec3fa& p) const

115
      {

116
        const Vec3ff q0(xfmVector(space,v0-p), v0.w);

117
        const Vec3ff q1(xfmVector(space,v1-p), v1.w);

118
        const Vec3ff q2(xfmVector(space,v2-p), v2.w);

119
        const Vec3ff q3(xfmVector(space,v3-p), v3.w);

120
        return CatmullRomCurveT<Vec3ff>(q0,q1,q2,q3);

121
      }

122
      

123
      __forceinline Vertex eval(const float t) const 

124
      {

125
        const Vec4<float> b = CatmullRomBasis::eval(t);

126
        return madd(b.x,v0,madd(b.y,v1,madd(b.z,v2,b.w*v3)));

127
      }

128
      

129
      __forceinline Vertex eval_du(const float t) const

130
      {

131
        const Vec4<float> b = CatmullRomBasis::derivative(t);

132
        return madd(b.x,v0,madd(b.y,v1,madd(b.z,v2,b.w*v3)));

133
      }

134
      

135
      __forceinline Vertex eval_dudu(const float t) const 

136
      {

137
        const Vec4<float> b = CatmullRomBasis::derivative2(t);

138
        return madd(b.x,v0,madd(b.y,v1,madd(b.z,v2,b.w*v3)));

139
      }

140


141
      __forceinline void eval(const float t, Vertex& p, Vertex& dp) const

142
      {

143
        p = eval(t);

144
        dp = eval_du(t);

145
      }

146
      

147
      __forceinline void eval(const float t, Vertex& p, Vertex& dp, Vertex& ddp) const

148
      {

149
        p = eval(t);

150
        dp = eval_du(t);

151
        ddp = eval_dudu(t);

152
      }

153


154
      template<int M>

155
      __forceinline Vec4vf<M> veval(const vfloat<M>& t) const 

156
      {

157
        const Vec4vf<M> b = CatmullRomBasis::eval(t);

158
        return madd(b.x, Vec4vf<M>(v0), madd(b.y, Vec4vf<M>(v1), madd(b.z, Vec4vf<M>(v2), b.w * Vec4vf<M>(v3))));

159
      }

160


161
      template<int M>

162
      __forceinline Vec4vf<M> veval_du(const vfloat<M>& t) const 

163
      {

164
        const Vec4vf<M> b = CatmullRomBasis::derivative(t);

165
        return madd(b.x, Vec4vf<M>(v0), madd(b.y, Vec4vf<M>(v1), madd(b.z, Vec4vf<M>(v2), b.w * Vec4vf<M>(v3))));

166
      }

167


168
      template<int M>

169
      __forceinline Vec4vf<M> veval_dudu(const vfloat<M>& t) const 

170
      {

171
        const Vec4vf<M> b = CatmullRomBasis::derivative2(t);

172
        return madd(b.x, Vec4vf<M>(v0), madd(b.y, Vec4vf<M>(v1), madd(b.z, Vec4vf<M>(v2), b.w * Vec4vf<M>(v3))));

173
      }

174


175
      template<int M>

176
      __forceinline void veval(const vfloat<M>& t, Vec4vf<M>& p, Vec4vf<M>& dp) const

177
      {

178
        p = veval<M>(t);

179
        dp = veval_du<M>(t);

180
      }

181
      

182
      template<int M>

183
      __forceinline Vec4vf<M> eval0(const int ofs, const int size) const

184
      {

185
        assert(size <= PrecomputedCatmullRomBasis::N);

186
        assert(ofs <= size);

187
        return madd(vfloat<M>::loadu(&catmullrom_basis0.c0[size][ofs]), Vec4vf<M>(v0),

188
                    madd(vfloat<M>::loadu(&catmullrom_basis0.c1[size][ofs]), Vec4vf<M>(v1),

189
                         madd(vfloat<M>::loadu(&catmullrom_basis0.c2[size][ofs]), Vec4vf<M>(v2),

190
                              vfloat<M>::loadu(&catmullrom_basis0.c3[size][ofs]) * Vec4vf<M>(v3))));

191
      }

192
      

193
      template<int M>

194
      __forceinline Vec4vf<M> eval1(const int ofs, const int size) const

195
      {

196
        assert(size <= PrecomputedCatmullRomBasis::N);

197
        assert(ofs <= size);

198
        return madd(vfloat<M>::loadu(&catmullrom_basis1.c0[size][ofs]), Vec4vf<M>(v0), 

199
                    madd(vfloat<M>::loadu(&catmullrom_basis1.c1[size][ofs]), Vec4vf<M>(v1),

200
                         madd(vfloat<M>::loadu(&catmullrom_basis1.c2[size][ofs]), Vec4vf<M>(v2),

201
                              vfloat<M>::loadu(&catmullrom_basis1.c3[size][ofs]) * Vec4vf<M>(v3))));

202
      }

203
      

204
      template<int M>

205
      __forceinline Vec4vf<M> derivative0(const int ofs, const int size) const

206
      {

207
        assert(size <= PrecomputedCatmullRomBasis::N);

208
        assert(ofs <= size);

209
        return madd(vfloat<M>::loadu(&catmullrom_basis0.d0[size][ofs]), Vec4vf<M>(v0),

210
                    madd(vfloat<M>::loadu(&catmullrom_basis0.d1[size][ofs]), Vec4vf<M>(v1),

211
                         madd(vfloat<M>::loadu(&catmullrom_basis0.d2[size][ofs]), Vec4vf<M>(v2),

212
                              vfloat<M>::loadu(&catmullrom_basis0.d3[size][ofs]) * Vec4vf<M>(v3))));

213
      }

214
      

215
      template<int M>

216
      __forceinline Vec4vf<M> derivative1(const int ofs, const int size) const

217
      {

218
        assert(size <= PrecomputedCatmullRomBasis::N);

219
        assert(ofs <= size);

220
        return madd(vfloat<M>::loadu(&catmullrom_basis1.d0[size][ofs]), Vec4vf<M>(v0),

221
                    madd(vfloat<M>::loadu(&catmullrom_basis1.d1[size][ofs]), Vec4vf<M>(v1),

222
                         madd(vfloat<M>::loadu(&catmullrom_basis1.d2[size][ofs]), Vec4vf<M>(v2),

223
                              vfloat<M>::loadu(&catmullrom_basis1.d3[size][ofs]) * Vec4vf<M>(v3))));

224
      }

225
      

226
      /* calculates bounds of catmull-rom curve geometry */

227
      __forceinline BBox3fa accurateRoundBounds() const

228
      {

229
        const int N = 7;

230
        const float scale = 1.0f/(3.0f*(N-1));

231
        Vec4vfx pl(pos_inf), pu(neg_inf);

232
        for (int i=0; i<=N; i+=VSIZEX)

233
        {

234
          vintx vi = vintx(i)+vintx(step);

235
          vboolx valid = vi <= vintx(N);

236
          const Vec4vfx p  = eval0<VSIZEX>(i,N);

237
          const Vec4vfx dp = derivative0<VSIZEX>(i,N);

238
          const Vec4vfx pm = p-Vec4vfx(scale)*select(vi!=vintx(0),dp,Vec4vfx(zero));

239
          const Vec4vfx pp = p+Vec4vfx(scale)*select(vi!=vintx(N),dp,Vec4vfx(zero));

240
          pl = select(valid,min(pl,p,pm,pp),pl); // FIXME: use masked min

241
          pu = select(valid,max(pu,p,pm,pp),pu); // FIXME: use masked min

242
        }

243
        const Vec3fa lower(reduce_min(pl.x),reduce_min(pl.y),reduce_min(pl.z));

244
        const Vec3fa upper(reduce_max(pu.x),reduce_max(pu.y),reduce_max(pu.z));

245
        const float r_min = reduce_min(pl.w);

246
        const float r_max = reduce_max(pu.w);

247
        const Vec3fa upper_r = Vec3fa(max(abs(r_min),abs(r_max)));

248
        return enlarge(BBox3fa(lower,upper),upper_r);

249
      }

250
      

251
      /* calculates bounds when tessellated into N line segments */

252
      __forceinline BBox3fa accurateFlatBounds(int N) const

253
      {

254
        if (likely(N == 4))

255
        {

256
          const Vec4vf4 pi = eval0<4>(0,4);

257
          const Vec3fa lower(reduce_min(pi.x),reduce_min(pi.y),reduce_min(pi.z));

258
          const Vec3fa upper(reduce_max(pi.x),reduce_max(pi.y),reduce_max(pi.z));

259
          const Vec3fa upper_r = Vec3fa(reduce_max(abs(pi.w)));

260
          const Vec3ff pe = end();

261
          return enlarge(BBox3fa(min(lower,pe),max(upper,pe)),max(upper_r,Vec3fa(abs(pe.w))));

262
        } 

263
        else

264
        {

265
          Vec3vfx pl(pos_inf), pu(neg_inf); vfloatx ru(0.0f);

266
          for (int i=0; i<=N; i+=VSIZEX)

267
          {

268
            vboolx valid = vintx(i)+vintx(step) <= vintx(N);

269
            const Vec4vfx pi = eval0<VSIZEX>(i,N);

270
            

271
            pl.x = select(valid,min(pl.x,pi.x),pl.x); // FIXME: use masked min

272
            pl.y = select(valid,min(pl.y,pi.y),pl.y); 

273
            pl.z = select(valid,min(pl.z,pi.z),pl.z); 

274
            

275
            pu.x = select(valid,max(pu.x,pi.x),pu.x); // FIXME: use masked min

276
            pu.y = select(valid,max(pu.y,pi.y),pu.y); 

277
            pu.z = select(valid,max(pu.z,pi.z),pu.z); 

278
            

279
            ru = select(valid,max(ru,abs(pi.w)),ru); 

280
          }

281
          const Vec3fa lower(reduce_min(pl.x),reduce_min(pl.y),reduce_min(pl.z));

282
          const Vec3fa upper(reduce_max(pu.x),reduce_max(pu.y),reduce_max(pu.z));

283
          const Vec3fa upper_r(reduce_max(ru));

284
          return enlarge(BBox3fa(lower,upper),upper_r);

285
        }

286
      }

287
      

288
      friend __forceinline embree_ostream operator<<(embree_ostream cout, const CatmullRomCurveT& curve) {

289
        return cout << "CatmullRomCurve { v0 = " << curve.v0 << ", v1 = " << curve.v1 << ", v2 = " << curve.v2 << ", v3 = " << curve.v3 << " }";

290
      }

291
    };

292


293
  template<typename Vertex>

294
    __forceinline void convert(const CatmullRomCurveT<Vertex>& icurve, BezierCurveT<Vertex>& ocurve)

295
  {

296
    const Vertex v0 = icurve.v1;

297
    const Vertex v1 = icurve.v1+(icurve.v2-icurve.v0)*(1.0f/6.0f);

298
    const Vertex v2 = icurve.v2+(icurve.v1-icurve.v3)*(1.0f/6.0f);

299
    const Vertex v3 = icurve.v2;

300
    ocurve = BezierCurveT<Vertex>(v0,v1,v2,v3);

301
  }

302


303
  template<typename CurveGeometry>

304
  __forceinline CatmullRomCurveT<Vec3ff> enlargeRadiusToMinWidth(const RayQueryContext* context, const CurveGeometry* geom, const Vec3fa& ray_org, const CatmullRomCurveT<Vec3ff>& curve)

305
  {

306
    return CatmullRomCurveT<Vec3ff>(enlargeRadiusToMinWidth(context,geom,ray_org,curve.v0),

307
                                    enlargeRadiusToMinWidth(context,geom,ray_org,curve.v1),

308
                                    enlargeRadiusToMinWidth(context,geom,ray_org,curve.v2),

309
                                    enlargeRadiusToMinWidth(context,geom,ray_org,curve.v3));

310
  }

311
  

312
  typedef CatmullRomCurveT<Vec3fa> CatmullRomCurve3fa;

313
}

314


315


316