KiCad PCB EDA Suite
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 <mrluzeiro@ua.pt>
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 #include <wx/debug.h>
32 
33 
34 #define BVH_RANGED_TRAVERSAL
35 //#define BVH_PARTITION_TRAVERSAL
36 
37 
38 #define MAX_TODOS 64
39 
40 
41 struct StackNode
42 {
43  int cell;
44  unsigned int ia; // Index to the first alive ray
45 };
46 
47 
48 static inline unsigned int getFirstHit( const RAYPACKET& aRayPacket, const BBOX_3D& aBBox,
49  unsigned int ia, HITINFO_PACKET* aHitInfoPacket )
50 {
51  float hitT;
52 
53  if( aBBox.Intersect( aRayPacket.m_ray[ia], &hitT )
54  && ( hitT < aHitInfoPacket[ia].m_HitInfo.m_tHit ) )
55  return ia;
56 
57  if( !aRayPacket.m_Frustum.Intersect( aBBox ) )
59 
60  for( unsigned int i = ia + 1; i < RAYPACKET_RAYS_PER_PACKET; ++i )
61  {
62  if( aBBox.Intersect( aRayPacket.m_ray[i], &hitT )
63  && ( hitT < aHitInfoPacket[i].m_HitInfo.m_tHit ) )
64  return i;
65  }
66 
68 }
69 
70 
71 #ifdef BVH_RANGED_TRAVERSAL
72 
73 static inline unsigned int getLastHit( const RAYPACKET& aRayPacket, const BBOX_3D& aBBox,
74  unsigned int ia, HITINFO_PACKET* aHitInfoPacket )
75 {
76  for( unsigned int ie = (RAYPACKET_RAYS_PER_PACKET - 1); ie > ia; --ie )
77  {
78  float hitT;
79 
80  if( aBBox.Intersect( aRayPacket.m_ray[ie], &hitT )
81  && ( hitT < aHitInfoPacket[ie].m_HitInfo.m_tHit ) )
82  return ie + 1;
83  }
84 
85  return ia + 1;
86 }
87 
88 
89 // "Large Ray Packets for Real-time Whitted Ray Tracing"
90 // http://cseweb.ucsd.edu/~ravir/whitted.pdf
91 
92 // Ranged Traversal
93 bool BVH_PBRT::Intersect( const RAYPACKET& aRayPacket, HITINFO_PACKET* aHitInfoPacket ) const
94 {
95  if( m_nodes == nullptr )
96  return false;
97 
98  if( &m_nodes[0] == nullptr )
99  return false;
100 
101  bool anyHit = false;
102  int todoOffset = 0, nodeNum = 0;
103  StackNode todo[MAX_TODOS];
104 
105  unsigned int ia = 0;
106 
107  while( true )
108  {
109  const LinearBVHNode *curCell = &m_nodes[nodeNum];
110 
111  ia = getFirstHit( aRayPacket, curCell->bounds, ia, aHitInfoPacket );
112 
113  if( ia < RAYPACKET_RAYS_PER_PACKET )
114  {
115  if( curCell->nPrimitives == 0 )
116  {
117  StackNode& node = todo[todoOffset++];
118  node.cell = curCell->secondChildOffset;
119  node.ia = ia;
120  nodeNum = nodeNum + 1;
121  continue;
122  }
123  else
124  {
125  const unsigned int ie = getLastHit( aRayPacket, curCell->bounds, ia,
126  aHitInfoPacket );
127 
128  for( int j = 0; j < curCell->nPrimitives; ++j )
129  {
130  const OBJECT_3D* obj = m_primitives[curCell->primitivesOffset + j];
131 
132  if( aRayPacket.m_Frustum.Intersect( obj->GetBBox() ) )
133  {
134  for( unsigned int i = ia; i < ie; ++i )
135  {
136  const bool hit = obj->Intersect( aRayPacket.m_ray[i],
137  aHitInfoPacket[i].m_HitInfo );
138 
139  if( hit )
140  {
141  anyHit |= hit;
142  aHitInfoPacket[i].m_hitresult |= hit;
143  aHitInfoPacket[i].m_HitInfo.m_acc_node_info = nodeNum;
144  }
145  }
146  }
147  }
148  }
149  }
150 
151  if( todoOffset == 0 )
152  break;
153 
154  const StackNode& node = todo[--todoOffset];
155 
156  nodeNum = node.cell;
157  ia = node.ia;
158  }
159 
160  return anyHit;
161 
162 }
163 #endif
164 
165 
166 // "Ray Tracing Deformable Scenes Using Dynamic Bounding Volume Hierarchies"
167 // http://www.cs.cmu.edu/afs/cs/academic/class/15869-f11/www/readings/wald07_packetbvh.pdf
168 
169 #ifdef BVH_PARTITION_TRAVERSAL
170 
171 static inline unsigned int getLastHit( const RAYPACKET& aRayPacket, const BBOX_3D& aBBox,
172  unsigned int ia, const unsigned int* aRayIndex,
173  HITINFO_PACKET* aHitInfoPacket )
174 {
175  for( unsigned int ie = (RAYPACKET_RAYS_PER_PACKET - 1); ie > ia; --ie )
176  {
177  float hitT;
178 
179  if( aBBox.Intersect( aRayPacket.m_ray[ aRayIndex[ie] ], &hitT )
180  && ( hitT < aHitInfoPacket[ aRayIndex[ie] ].m_HitInfo.m_tHit ) )
181  return ie + 1;
182  }
183 
184  return ia + 1;
185 }
186 
187 
188 static inline unsigned int partRays( const RAYPACKET& aRayPacket, const BBOX_3D& aBBox,
189  unsigned int ia, unsigned int* aRayIndex,
190  HITINFO_PACKET* aHitInfoPacket )
191 {
192 
193  if( !aRayPacket.m_Frustum.Intersect( aBBox ) )
195 
196  unsigned int ie = 0;
197 
198  for( unsigned int i = 0; i < ia; ++i )
199  {
200  float hitT;
201 
202  if( aBBox.Intersect( aRayPacket.m_ray[ aRayIndex[i] ], &hitT )
203  && ( hitT < aHitInfoPacket[ aRayIndex[i] ].m_HitInfo.m_tHit ) )
204  std::swap( aRayIndex[ie++], aRayIndex[i] );
205  }
206 
207  return ie;
208 }
209 
210 
211 bool BVH_PBRT::Intersect( const RAYPACKET& aRayPacket, HITINFO_PACKET* aHitInfoPacket ) const
212 {
213  bool anyHit = false;
214  int todoOffset = 0, nodeNum = 0;
215  StackNode todo[MAX_TODOS];
216 
217  unsigned int I[RAYPACKET_RAYS_PER_PACKET];
218 
219  memcpy( I, m_I, RAYPACKET_RAYS_PER_PACKET * sizeof( unsigned int ) );
220 
221  unsigned int ia = 0;
222 
223  while( true )
224  {
225  const LinearBVHNode *curCell = &m_nodes[nodeNum];
226 
227  ia = partRays( aRayPacket, curCell->bounds, ia, I, aHitInfoPacket );
228 
229  if( ia < RAYPACKET_RAYS_PER_PACKET )
230  {
231  if( curCell->nPrimitives == 0 )
232  {
233  StackNode& node = todo[todoOffset++];
234  node.cell = curCell->secondChildOffset;
235  node.ia = ia;
236  nodeNum = nodeNum + 1;
237  continue;
238  }
239  else
240  {
241  unsigned int ie = getLastHit( aRayPacket, curCell->bounds, ia, I,
242  aHitInfoPacket );
243 
244  for( int j = 0; j < curCell->nPrimitives; ++j )
245  {
246  const OBJECT_3D* obj = m_primitives[curCell->primitivesOffset + j];
247 
248  if( aRayPacket.m_Frustum.Intersect( obj->GetBBox() ) )
249  {
250  for( unsigned int i = 0; i < ie; ++i )
251  {
252  unsigned int idx = I[i];
253 
254  bool hit = obj->Intersect( aRayPacket.m_ray[idx],
255  aHitInfoPacket[idx].m_HitInfo );
256 
257  if( hit )
258  {
259  anyHit |= hit;
260  aHitInfoPacket[idx].m_hitresult |= hit;
261  aHitInfoPacket[idx].m_HitInfo.m_acc_node_info = nodeNum;
262  }
263  }
264  }
265  }
266  }
267  }
268 
269  if( todoOffset == 0 )
270  break;
271 
272  const StackNode& node = todo[--todoOffset];
273 
274  nodeNum = node.cell;
275  ia = node.ia;
276  }
277 
278  return anyHit;
279 }
280 #endif
static unsigned int getFirstHit(const RAYPACKET &aRayPacket, const BBOX_3D &aBBox, unsigned int ia, HITINFO_PACKET *aHitInfoPacket)
RAY m_ray[RAYPACKET_RAYS_PER_PACKET]
Definition: raypacket.h:59
int primitivesOffset
leaf
Definition: bvh_pbrt.h:90
CONST_VECTOR_OBJECT m_primitives
Definition: bvh_pbrt.h:144
unsigned int ia
uint16_t nPrimitives
0 -> interior node
Definition: bvh_pbrt.h:95
virtual bool Intersect(const RAY &aRay, HITINFO &aHitInfo) const =0
Manage a bounding box defined by two SFVEC3F min max points.
Definition: bbox_3d.h:41
bool Intersect(const RAY &aRay, float *t) const
Definition: bbox_3d_ray.cpp:46
This BVH implementation is based on the source code implementation from the book "Physically Based Re...
float m_tHit
( 4) distance
Definition: hitinfo.h:43
static unsigned int getLastHit(const RAYPACKET &aRayPacket, const BBOX_3D &aBBox, unsigned int ia, HITINFO_PACKET *aHitInfoPacket)
bool Intersect(const BBOX_3D &aBBox) const
Intersect aBBox with this frustum.
Definition: frustum.cpp:62
#define I(x, y, z)
Definition: md5_hash.cpp:18
HITINFO m_HitInfo
Definition: hitinfo.h:63
FRUSTUM m_Frustum
Definition: raypacket.h:58
#define RAYPACKET_RAYS_PER_PACKET
Definition: raypacket.h:40
unsigned int m_acc_node_info
( 4) The acc stores here the node that it hits
Definition: hitinfo.h:47
bool Intersect(const RAY &aRay, HITINFO &aHitInfo) const override
Definition: bvh_pbrt.cpp:1066
const BBOX_3D & GetBBox() const
Definition: object_3d.h:92
int secondChildOffset
interior
Definition: bvh_pbrt.h:91
bool m_hitresult
Definition: hitinfo.h:62
#define MAX_TODOS
unsigned int m_I[RAYPACKET_RAYS_PER_PACKET]
Definition: bvh_pbrt.h:150
LinearBVHNode * m_nodes
Definition: bvh_pbrt.h:145
BBOX_3D bounds
Definition: bvh_pbrt.h:85