KiCad PCB EDA Suite
Loading...
Searching...
No Matches
bvh_packet_traversal.cpp
Go to the documentation of this file.
1/*
2 * This program source code file is part of KiCad, a free EDA CAD application.
3 *
4 * Copyright (C) 2015-2016 Mario Luzeiro <[email protected]>
5 * Copyright (C) 2015-2020 KiCad Developers, see AUTHORS.txt for contributors.
6 *
7 * This program is free software; you can redistribute it and/or
8 * modify it under the terms of the GNU General Public License
9 * as published by the Free Software Foundation; either version 2
10 * of the License, or (at your option) any later version.
11 *
12 * This program is distributed in the hope that it will be useful,
13 * but WITHOUT ANY WARRANTY; without even the implied warranty of
14 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 * GNU General Public License for more details.
16 *
17 * You should have received a copy of the GNU General Public License
18 * along with this program; if not, you may find one here:
19 * http://www.gnu.org/licenses/old-licenses/gpl-2.0.html
20 * or you may search the http://www.gnu.org website for the version 2 license,
21 * or you may write to the Free Software Foundation, Inc.,
22 * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA
23 */
24
30#include "bvh_pbrt.h"
31
32
33#define BVH_RANGED_TRAVERSAL
34//#define BVH_PARTITION_TRAVERSAL
35
36
37#define MAX_TODOS 64
38
39
41{
42 int cell;
43 unsigned int ia; // Index to the first alive ray
44};
45
46
47static inline unsigned int getFirstHit( const RAYPACKET& aRayPacket, const BBOX_3D& aBBox,
48 unsigned int ia, HITINFO_PACKET* aHitInfoPacket )
49{
50 float hitT;
51
52 if( aBBox.Intersect( aRayPacket.m_ray[ia], &hitT )
53 && ( hitT < aHitInfoPacket[ia].m_HitInfo.m_tHit ) )
54 return ia;
55
56 if( !aRayPacket.m_Frustum.Intersect( aBBox ) )
58
59 for( unsigned int i = ia + 1; i < RAYPACKET_RAYS_PER_PACKET; ++i )
60 {
61 if( aBBox.Intersect( aRayPacket.m_ray[i], &hitT )
62 && ( hitT < aHitInfoPacket[i].m_HitInfo.m_tHit ) )
63 return i;
64 }
65
67}
68
69
70#ifdef BVH_RANGED_TRAVERSAL
71
72static inline unsigned int getLastHit( const RAYPACKET& aRayPacket, const BBOX_3D& aBBox,
73 unsigned int ia, HITINFO_PACKET* aHitInfoPacket )
74{
75 for( unsigned int ie = (RAYPACKET_RAYS_PER_PACKET - 1); ie > ia; --ie )
76 {
77 float hitT;
78
79 if( aBBox.Intersect( aRayPacket.m_ray[ie], &hitT )
80 && ( hitT < aHitInfoPacket[ie].m_HitInfo.m_tHit ) )
81 return ie + 1;
82 }
83
84 return ia + 1;
85}
86
87
88// "Large Ray Packets for Real-time Whitted Ray Tracing"
89// http://cseweb.ucsd.edu/~ravir/whitted.pdf
90
91// Ranged Traversal
92bool BVH_PBRT::Intersect( const RAYPACKET& aRayPacket, HITINFO_PACKET* aHitInfoPacket ) const
93{
94 if( m_nodes == nullptr )
95 return false;
96
97 if( &m_nodes[0] == nullptr )
98 return false;
99
100 bool anyHit = false;
101 int todoOffset = 0, nodeNum = 0;
102 StackNode todo[MAX_TODOS];
103
104 unsigned int ia = 0;
105
106 while( true )
107 {
108 const LinearBVHNode *curCell = &m_nodes[nodeNum];
109
110 ia = getFirstHit( aRayPacket, curCell->bounds, ia, aHitInfoPacket );
111
113 {
114 if( curCell->nPrimitives == 0 )
115 {
116 StackNode& node = todo[todoOffset++];
117 node.cell = curCell->secondChildOffset;
118 node.ia = ia;
119 nodeNum = nodeNum + 1;
120 continue;
121 }
122 else
123 {
124 const unsigned int ie = getLastHit( aRayPacket, curCell->bounds, ia,
125 aHitInfoPacket );
126
127 for( int j = 0; j < curCell->nPrimitives; ++j )
128 {
129 const OBJECT_3D* obj = m_primitives[curCell->primitivesOffset + j];
130
131 if( aRayPacket.m_Frustum.Intersect( obj->GetBBox() ) )
132 {
133 for( unsigned int i = ia; i < ie; ++i )
134 {
135 const bool hit = obj->Intersect( aRayPacket.m_ray[i],
136 aHitInfoPacket[i].m_HitInfo );
137
138 if( hit )
139 {
140 anyHit |= hit;
141 aHitInfoPacket[i].m_hitresult |= hit;
142 aHitInfoPacket[i].m_HitInfo.m_acc_node_info = nodeNum;
143 }
144 }
145 }
146 }
147 }
148 }
149
150 if( todoOffset == 0 )
151 break;
152
153 const StackNode& node = todo[--todoOffset];
154
155 nodeNum = node.cell;
156 ia = node.ia;
157 }
158
159 return anyHit;
160
161}
162#endif
163
164
165// "Ray Tracing Deformable Scenes Using Dynamic Bounding Volume Hierarchies"
166// http://www.cs.cmu.edu/afs/cs/academic/class/15869-f11/www/readings/wald07_packetbvh.pdf
167
168#ifdef BVH_PARTITION_TRAVERSAL
169
170static inline unsigned int getLastHit( const RAYPACKET& aRayPacket, const BBOX_3D& aBBox,
171 unsigned int ia, const unsigned int* aRayIndex,
172 HITINFO_PACKET* aHitInfoPacket )
173{
174 for( unsigned int ie = (RAYPACKET_RAYS_PER_PACKET - 1); ie > ia; --ie )
175 {
176 float hitT;
177
178 if( aBBox.Intersect( aRayPacket.m_ray[ aRayIndex[ie] ], &hitT )
179 && ( hitT < aHitInfoPacket[ aRayIndex[ie] ].m_HitInfo.m_tHit ) )
180 return ie + 1;
181 }
182
183 return ia + 1;
184}
185
186
187static inline unsigned int partRays( const RAYPACKET& aRayPacket, const BBOX_3D& aBBox,
188 unsigned int ia, unsigned int* aRayIndex,
189 HITINFO_PACKET* aHitInfoPacket )
190{
191
192 if( !aRayPacket.m_Frustum.Intersect( aBBox ) )
194
195 unsigned int ie = 0;
196
197 for( unsigned int i = 0; i < ia; ++i )
198 {
199 float hitT;
200
201 if( aBBox.Intersect( aRayPacket.m_ray[ aRayIndex[i] ], &hitT )
202 && ( hitT < aHitInfoPacket[ aRayIndex[i] ].m_HitInfo.m_tHit ) )
203 std::swap( aRayIndex[ie++], aRayIndex[i] );
204 }
205
206 return ie;
207}
208
209
210bool BVH_PBRT::Intersect( const RAYPACKET& aRayPacket, HITINFO_PACKET* aHitInfoPacket ) const
211{
212 bool anyHit = false;
213 int todoOffset = 0, nodeNum = 0;
214 StackNode todo[MAX_TODOS];
215
216 unsigned int I[RAYPACKET_RAYS_PER_PACKET];
217
218 memcpy( I, m_I, RAYPACKET_RAYS_PER_PACKET * sizeof( unsigned int ) );
219
220 unsigned int ia = 0;
221
222 while( true )
223 {
224 const LinearBVHNode *curCell = &m_nodes[nodeNum];
225
226 ia = partRays( aRayPacket, curCell->bounds, ia, I, aHitInfoPacket );
227
229 {
230 if( curCell->nPrimitives == 0 )
231 {
232 StackNode& node = todo[todoOffset++];
233 node.cell = curCell->secondChildOffset;
234 node.ia = ia;
235 nodeNum = nodeNum + 1;
236 continue;
237 }
238 else
239 {
240 unsigned int ie = getLastHit( aRayPacket, curCell->bounds, ia, I,
241 aHitInfoPacket );
242
243 for( int j = 0; j < curCell->nPrimitives; ++j )
244 {
245 const OBJECT_3D* obj = m_primitives[curCell->primitivesOffset + j];
246
247 if( aRayPacket.m_Frustum.Intersect( obj->GetBBox() ) )
248 {
249 for( unsigned int i = 0; i < ie; ++i )
250 {
251 unsigned int idx = I[i];
252
253 bool hit = obj->Intersect( aRayPacket.m_ray[idx],
254 aHitInfoPacket[idx].m_HitInfo );
255
256 if( hit )
257 {
258 anyHit |= hit;
259 aHitInfoPacket[idx].m_hitresult |= hit;
260 aHitInfoPacket[idx].m_HitInfo.m_acc_node_info = nodeNum;
261 }
262 }
263 }
264 }
265 }
266 }
267
268 if( todoOffset == 0 )
269 break;
270
271 const StackNode& node = todo[--todoOffset];
272
273 nodeNum = node.cell;
274 ia = node.ia;
275 }
276
277 return anyHit;
278}
279#endif
#define MAX_TODOS
static unsigned int getLastHit(const RAYPACKET &aRayPacket, const BBOX_3D &aBBox, unsigned int ia, HITINFO_PACKET *aHitInfoPacket)
static unsigned int getFirstHit(const RAYPACKET &aRayPacket, const BBOX_3D &aBBox, unsigned int ia, HITINFO_PACKET *aHitInfoPacket)
This BVH implementation is based on the source code implementation from the book "Physically Based Re...
LinearBVHNode * m_nodes
Definition: bvh_pbrt.h:145
unsigned int m_I[RAYPACKET_RAYS_PER_PACKET]
Definition: bvh_pbrt.h:150
bool Intersect(const RAY &aRay, HITINFO &aHitInfo) const override
Definition: bvh_pbrt.cpp:1066
CONST_VECTOR_OBJECT m_primitives
Definition: bvh_pbrt.h:144
virtual bool Intersect(const RAY &aRay, HITINFO &aHitInfo) const =0
const BBOX_3D & GetBBox() const
Definition: object_3d.h:92
#define I(x, y, z)
Definition: md5_hash.cpp:18
#define RAYPACKET_RAYS_PER_PACKET
Definition: raypacket.h:35
Manage a bounding box defined by two SFVEC3F min max points.
Definition: bbox_3d.h:43
bool Intersect(const RAY &aRay, float *t) const
Definition: bbox_3d_ray.cpp:46
bool Intersect(const BBOX_3D &aBBox) const
Intersect aBBox with this frustum.
Definition: frustum.cpp:58
bool m_hitresult
Definition: hitinfo.h:57
HITINFO m_HitInfo
Definition: hitinfo.h:58
unsigned int m_acc_node_info
( 4) The acc stores here the node that it hits
Definition: hitinfo.h:42
float m_tHit
( 4) distance
Definition: hitinfo.h:38
int secondChildOffset
interior
Definition: bvh_pbrt.h:91
BBOX_3D bounds
Definition: bvh_pbrt.h:85
uint16_t nPrimitives
0 -> interior node
Definition: bvh_pbrt.h:95
int primitivesOffset
leaf
Definition: bvh_pbrt.h:90
RAY m_ray[RAYPACKET_RAYS_PER_PACKET]
Definition: raypacket.h:54
FRUSTUM m_Frustum
Definition: raypacket.h:53
unsigned int ia