-
Notifications
You must be signed in to change notification settings - Fork 1
/
binsearch.cg
54 lines (45 loc) · 1.23 KB
/
binsearch.cg
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
////////////////////////////////////////////////////////////////////
//
// $Id: binsearch.cg 2021/06/05 12:10:04 kanai Exp $
//
// Copyright (c) 2021 Takashi Kanai
// Released under the MIT license
//
////////////////////////////////////////////////////////////////////
#ifndef _BINSEARCH_CG
#define _BINSEARCH_CG 1
// #define LOGN 5 // valid if n_kt < 32 (2^{5})
#define LOGN 6 // valid if n_kt < 64 (2^{6})
//
// finding a knot span i for a parameter t ( t_{i} <= t < t_{i+1} )
// by a binary search algorithm
//
int binarySearch( float t,
float fid,
float deg,
uniform samplerRECT sortlist )
{
// fetch the number of knot vector
float4 a = texRECT( sortlist, float2(0, fid) );
float m = a.y - 1;
float t0 = f1texRECT( sortlist, float2(m - deg, fid) );
int flag = 0;
if ( abs(t-t0) < 1.0e-05 ) flag = 1;
int low = deg;
int high = m - deg;
int mid = (low+high)/2;
for ( int i = 0; i < LOGN; i++ )
{
float ts = f1texRECT( sortlist, float2(mid, fid) );
float te = f1texRECT( sortlist, float2(mid+1,fid) );
if ( t < ts || t >= te )
{
if ( t < ts ) high = mid;
else low = mid;
mid = (low+high)/2;
}
}
if ( flag == 1 ) mid = m - (deg+1);
return mid;
}
#endif // _BINSEARCH_CG