5 ms·

Ray-Strips: A Compact Mesh Representation for Interactive Ray Tracing (2007) [pdf]

114 points by all2 8y ago

tntn 8y ago
(2007)
- all2 8y ago
  Fixed.
all2 8y ago
The important bits can be found at the end of the paper; > 6.2 Analysis and Limitations > The results above show that Ray-Strips are an efficient representation for our tested complex benchmarks. In practice, the memory improvements gained from using Ray-Strips are highly dependent on finding sufficiently long triangle strips to build the hierarchy on. Obviously, this makes our approach unsuitable for models without any mesh connectivity (e.g. without any shared vertices). In that case, the Ray-Strip representation shown in Section 4 becomes an indexed triangle list with a standard BVH (just with the addition on the 2-byte header storing the triangle count) and performance gains are lost. However, the memory overhead added is only very small.Therefore, it is unlikely that there will be a significant performance loss compared to using an indexed triangle list to start with. > Our current implementation uses the stripification library Stripe[0], which was designed for rasterization and unlike many newer approaches works on general meshes without limitations on the input. Since the computed strips can be sub-optimal for ray tracing,it should be quite possible to further improve the performance of our approaches by designing a stripification algorithm that chooses strips based on ray tracing criteria. > As presented in Section 3 and 4, our system uses a BVH with axis-aligned bounding boxes as the high-level hierarchy, but is important to note that in principle any acceleration structure can be used for the Ray-Strips. We find that a BVH usually provides a reasonable compromise between rendering speed, flexibility and ease of use. It is also easily updateable so that dynamic scenes can be handled efficiently. If maximum performance for a static scene is desired, a kd-tree may be a better choice and might reduce the memory footprint slightly. Note that Ray-Strips can be updated in the same manner as BVHs, but have the limitation that mesh connectivity cannot change in the animation, e.g. objects cannot “break”. [0] I can't find this anywhere on the internet. Here is the DOI for the IEEE paper cited (which does not mention this library), DOI: 10.1109/VISUAL.1996.568125
- deleted 8y ago
  [deleted]
- carterschonwald 8y ago
  heres a random search result that is code that cites that paper for its own strip generation https://github.com/zeux/meshoptimizer/blob/master/src/stripifier.cpp https://github.com/zeux/meshoptimizer/blob/master/src/stripi... source: went to https://sci-hub.tw/10.1109/VISUAL.1996.568125 https://sci-hub.tw/10.1109/VISUAL.1996.568125 then searched one of the author names + github paper title and authors are Optimizing Triangle Strips for Fast Rendering Francine Evans Steven Skiena Amitabh Varshney
geuszb 8y ago
This was 2007. Is this used in production these days? If not, what else is used instead?
- gmueckl 8y ago
  Most systems that I am aware of use a plain BVH. Memory requirements for the acceleration structure are not that much of a concern in most cases. Memory hogs typically are (in descending order) volumetric data (smoke/fire/...), textures and only then geometry. And because a BVH leaf node typically contains a few triangles, the BVH itself is always smaller than the geometry data.
srib 8y ago
I wonder if any of this is implemented in OpenVDB[0]? [0] https://www.openvdb.org/ https://www.openvdb.org/
- gmueckl 8y ago
  No, OpenVDB solves the completely unrelated problem of keeping huge volume data sets in memory for efficient monte carlo sampling. This ray strip paper deals with tiangulated surface meshes, which are completely unrelated data structures in an unrelated domain (2d surfaces embedded in a 2d domain versus a discretely, regularly sampled 3d function).
aphextim 8y ago
A little bit off topic but I recently saw something regarding a Ray-tracing engine built inside of the game Factorio. Check it out here - https://www.youtube.com/watch?v=7lVAFcDX4eM https://www.youtube.com/watch?v=7lVAFcDX4eM
- pixelpoet 8y ago
  The Factorio guys are just down the road from us at Corona Renderer (a top ray tracing engine) in Prague, I guess we should hang out and talk ray tracing sometime :)
melling 8y ago
More raytracing resources: https://github.com/melling/ComputerGraphics/blob/master/ray_tracing.md https://github.com/melling/ComputerGraphics/blob/master/ray_...
Derek_MK 8y ago
A sort of ELI5 on this for those that may not be familiar with any of this: Ray tracing algorithms require checking to see if a ray will intersect with objects in a scene. This takes a LOT of time, and if you want this to be interactive ray tracing (e.g. in a game, where you need a frame drawn in a very short time), you have to find ways to reduce the number of objects you're comparing the ray against. A lot of the time this includes culling algorithms, which essentially give you very quick ways to say that a number of objects have literally no way of being intersected by a ray, so you can ignore them. There's also things like bounding volume hierarchies (BVHs), which says things like, if a ray doesn't intersect with a given massive invisible cube that contains objects, then it can't possibly intersect things contained in that cube. This is a bit different of a solution. If I'm understanding it right, this involves simplifying the representation of the objects themselves, so that something that was once a lot of triangles to be checked individually, can now be checked as one object. This means that a) you don't have to check for as many intersections, and b) it uses a lot less memory.
- hughes 8y ago
  It still sounds a lot like BVHs. Maybe I need to read it more carefully, but I can't tell the difference.
  - corysama 8y ago
    AFAICT, they use whatever BVH you want above the individual mesh level. Then, within the mesh, they use a kd-tree with 2 parallel, overlapping half-spaces at each node. The triangles are stored as a bunch of triangle strips in a linear array. Each node of the kd-tree refers to span of the triangle strips. The spans hierarchically get smaller the further down the tree you go, but technically you can run through a linear array of triangles for any node. They stop subdividing at 4 triangles because SIMD. Did I miss anything? Looks like the primary speed up is due to memory footprint reduction --especially because the largest model is big enough in the "standard BVH" that it hits swap during rendering. Not sure what their "standard BVH" representation is that's 6X larger than triangle strips.
- Jasper_ 8y ago

114 points by all2 8y ago

tntn 8y ago

(2007)

all2 8y ago
Fixed.

all2 8y ago

The important bits can be found at the end of the paper; > 6.2 Analysis and Limitations > The results above show that Ray-Strips are an efficient representation for our tested complex benchmarks. In practice, the memory improvements gained from using Ray-Strips are highly dependent on finding sufficiently long triangle strips to build the hierarchy on. Obviously, this makes our approach unsuitable for models without any mesh connectivity (e.g. without any shared vertices). In that case, the Ray-Strip representation shown in Section 4 becomes an indexed triangle list with a standard BVH (just with the addition on the 2-byte header storing the triangle count) and performance gains are lost. However, the memory overhead added is only very small.Therefore, it is unlikely that there will be a significant performance loss compared to using an indexed triangle list to start with. > Our current implementation uses the stripification library Stripe[0], which was designed for rasterization and unlike many newer approaches works on general meshes without limitations on the input. Since the computed strips can be sub-optimal for ray tracing,it should be quite possible to further improve the performance of our approaches by designing a stripification algorithm that chooses strips based on ray tracing criteria. > As presented in Section 3 and 4, our system uses a BVH with axis-aligned bounding boxes as the high-level hierarchy, but is important to note that in principle any acceleration structure can be used for the Ray-Strips. We find that a BVH usually provides a reasonable compromise between rendering speed, flexibility and ease of use. It is also easily updateable so that dynamic scenes can be handled efficiently. If maximum performance for a static scene is desired, a kd-tree may be a better choice and might reduce the memory footprint slightly. Note that Ray-Strips can be updated in the same manner as BVHs, but have the limitation that mesh connectivity cannot change in the animation, e.g. objects cannot “break”. [0] I can't find this anywhere on the internet. Here is the DOI for the IEEE paper cited (which does not mention this library), DOI: 10.1109/VISUAL.1996.568125

deleted 8y ago
[deleted]
carterschonwald 8y ago
heres a random search result that is code that cites that paper for its own strip generation https://github.com/zeux/meshoptimizer/blob/master/src/stripifier.cpp https://github.com/zeux/meshoptimizer/blob/master/src/stripi... source: went to https://sci-hub.tw/10.1109/VISUAL.1996.568125 https://sci-hub.tw/10.1109/VISUAL.1996.568125 then searched one of the author names + github paper title and authors are Optimizing Triangle Strips for Fast Rendering Francine Evans Steven Skiena Amitabh Varshney

geuszb 8y ago

This was 2007. Is this used in production these days? If not, what else is used instead?

gmueckl 8y ago
Most systems that I am aware of use a plain BVH. Memory requirements for the acceleration structure are not that much of a concern in most cases. Memory hogs typically are (in descending order) volumetric data (smoke/fire/...), textures and only then geometry. And because a BVH leaf node typically contains a few triangles, the BVH itself is always smaller than the geometry data.

srib 8y ago

I wonder if any of this is implemented in OpenVDB[0]? [0] https://www.openvdb.org/ https://www.openvdb.org/

gmueckl 8y ago
No, OpenVDB solves the completely unrelated problem of keeping huge volume data sets in memory for efficient monte carlo sampling. This ray strip paper deals with tiangulated surface meshes, which are completely unrelated data structures in an unrelated domain (2d surfaces embedded in a 2d domain versus a discretely, regularly sampled 3d function).

aphextim 8y ago

A little bit off topic but I recently saw something regarding a Ray-tracing engine built inside of the game Factorio. Check it out here - https://www.youtube.com/watch?v=7lVAFcDX4eM https://www.youtube.com/watch?v=7lVAFcDX4eM

pixelpoet 8y ago
The Factorio guys are just down the road from us at Corona Renderer (a top ray tracing engine) in Prague, I guess we should hang out and talk ray tracing sometime :)

melling 8y ago

More raytracing resources: https://github.com/melling/ComputerGraphics/blob/master/ray_tracing.md https://github.com/melling/ComputerGraphics/blob/master/ray_...

Derek_MK 8y ago

A sort of ELI5 on this for those that may not be familiar with any of this: Ray tracing algorithms require checking to see if a ray will intersect with objects in a scene. This takes a LOT of time, and if you want this to be interactive ray tracing (e.g. in a game, where you need a frame drawn in a very short time), you have to find ways to reduce the number of objects you're comparing the ray against. A lot of the time this includes culling algorithms, which essentially give you very quick ways to say that a number of objects have literally no way of being intersected by a ray, so you can ignore them. There's also things like bounding volume hierarchies (BVHs), which says things like, if a ray doesn't intersect with a given massive invisible cube that contains objects, then it can't possibly intersect things contained in that cube. This is a bit different of a solution. If I'm understanding it right, this involves simplifying the representation of the objects themselves, so that something that was once a lot of triangles to be checked individually, can now be checked as one object. This means that a) you don't have to check for as many intersections, and b) it uses a lot less memory.

hughes 8y ago
It still sounds a lot like BVHs. Maybe I need to read it more carefully, but I can't tell the difference.
- corysama 8y ago
  AFAICT, they use whatever BVH you want above the individual mesh level. Then, within the mesh, they use a kd-tree with 2 parallel, overlapping half-spaces at each node. The triangles are stored as a bunch of triangle strips in a linear array. Each node of the kd-tree refers to span of the triangle strips. The spans hierarchically get smaller the further down the tree you go, but technically you can run through a linear array of triangles for any node. They stop subdividing at 4 triangles because SIMD. Did I miss anything? Looks like the primary speed up is due to memory footprint reduction --especially because the largest model is big enough in the "standard BVH" that it hits swap during rendering. Not sure what their "standard BVH" representation is that's 6X larger than triangle strips.
Jasper_ 8y ago