1// Copyright 2009-2021 Intel Corporation
2// SPDX-License-Identifier: Apache-2.0
3
4#pragma once
5
6#include "../common/default.h"
7
8namespace embree
9{
10 struct __aligned(16) GridRange
11 {
12 unsigned int u_start;
13 unsigned int u_end;
14 unsigned int v_start;
15 unsigned int v_end;
16
17 __forceinline GridRange() {}
18
19 __forceinline GridRange(unsigned int u_start, unsigned int u_end, unsigned int v_start, unsigned int v_end)
20 : u_start(u_start), u_end(u_end), v_start(v_start), v_end(v_end) {}
21
22 __forceinline unsigned int width() const {
23 return u_end-u_start+1;
24 }
25
26 __forceinline unsigned int height() const {
27 return v_end-v_start+1;
28 }
29
30 __forceinline bool hasLeafSize() const
31 {
32 const unsigned int u_size = u_end-u_start+1;
33 const unsigned int v_size = v_end-v_start+1;
34 assert(u_size >= 1);
35 assert(v_size >= 1);
36 return u_size <= 3 && v_size <= 3;
37 }
38
39 static __forceinline unsigned int split(unsigned int start,unsigned int end)
40 {
41 const unsigned int center = (start+end)/2;
42 assert (center > start);
43 assert (center < end);
44 return center;
45 }
46
47 __forceinline void split(GridRange& r0, GridRange& r1) const
48 {
49 assert( hasLeafSize() == false );
50 const unsigned int u_size = u_end-u_start+1;
51 const unsigned int v_size = v_end-v_start+1;
52 r0 = *this;
53 r1 = *this;
54
55 if (u_size >= v_size)
56 {
57 const unsigned int u_mid = split(u_start,u_end);
58 r0.u_end = u_mid;
59 r1.u_start = u_mid;
60 }
61 else
62 {
63 const unsigned int v_mid = split(v_start,v_end);
64 r0.v_end = v_mid;
65 r1.v_start = v_mid;
66 }
67 }
68
69 __forceinline unsigned int splitIntoSubRanges(GridRange r[4]) const
70 {
71 assert( !hasLeafSize() );
72 unsigned int children = 0;
73 GridRange first,second;
74 split(first,second);
75
76 if (first.hasLeafSize()) {
77 r[0] = first;
78 children++;
79 }
80 else {
81 first.split(r[0],r[1]);
82 children += 2;
83 }
84
85 if (second.hasLeafSize()) {
86 r[children] = second;
87 children++;
88 }
89 else {
90 second.split(r[children+0],r[children+1]);
91 children += 2;
92 }
93 return children;
94 }
95 };
96}
97