Questions tagged [data-structure]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
16 votes
1 answer
13k views

Difference between BVH and Octree/K-d trees

So I'm currently reading up on acceleration data structures and so far I've heard there are 2 main schemes. Object Subdivision and Spatial Subdivision. The Bounding Volume Hierarchy belongs to the ...
gallickgunner's user avatar
12 votes
1 answer
5k views

What is the benefit of using Half Edge over Winged Edge?

For mesh representation, what is the benefit of using Half Edge over Winged Edge data structure? I understand both mesh representations, the only difference is that half edge uses directional edge ...
Bla...'s user avatar
  • 481
10 votes
0 answers
166 views

How to describe the bi-directional links for the Weiler-Atherton algorithm?

My postscript interpreter currently implements the Hodgeman-Sutherland clipping algorithm but this is limited to simpler shapes and doesn't have a provision for utilizing various winding-number rules. ...
luser droog's user avatar
  • 1,363
9 votes
2 answers
3k views

Why are oct trees so much more common than hash tables?

When reading papers I commonly find Oct tree implementations of geometry representations to sort the data. However whenever I think about the problem hash tables seem better overall. Hash tables have ...
Makogan's user avatar
  • 1,696
8 votes
1 answer
5k views

What is the definition of a Half Edge?

I ran into half-edges as part of the result of a Delaunay Triangulation library, but can't find an actual definition of what one is. I understand vertices, edges and faces, but can't find a concrete ...
Mark A. Ropper's user avatar
8 votes
1 answer
1k views

The meaning of early ray termination and front-to-back traversal in ray tracing

I'm new to computer graphics. These days I've been trying to understand how ray tracing using an acceleration data structure works. I came across the term "early ray termination" several times, I ...
S.E.K.'s user avatar
  • 141
5 votes
1 answer
763 views

Why sending data from gpu to cpu is slower than cpu to gpu?

Why sending data from gpu to cpu is slower than cpu to gpu? I heard the relation is similar to network situation, in detail, the upload is slower than download. However, I could not understand the ...
shashack's user avatar
  • 523
5 votes
2 answers
2k views

Is it possible to store the plain buffer data in gltf files?

The GL Transmission Format comes along with a JSON styled main file which basicly describes the scene and binary files which contain the buffers. I'm currently writing a WebGL library and I need to ...
q9f's user avatar
  • 703
4 votes
2 answers
4k views

Are there any gltf example datasets available? [closed]

I'm currently researching my options on effeciently exchanging data for a webgl application. I understand the gltf format is still being drafted but I need some example data to understand whether this ...
q9f's user avatar
  • 703
4 votes
2 answers
2k views

How to generate binary gltf array buffers?

I'm looking for any way which enables me to quickly generate gltf files including the conversion of plain array buffers (vertex, index, color, etc.) into binary (bgltf, glb, bin) files. I'm asking ...
q9f's user avatar
  • 703
4 votes
1 answer
563 views

Which provides better intuition: THREE.Geometry or THREE.BufferGeometry?

THREE.js recently dropped support for THREE.Geometry in favor of exclusively THREE.BufferGeometry. I'm trying to decide which paradigm to teach in my computer graphics course to best provide students ...
TomKern's user avatar
  • 251
4 votes
1 answer
577 views

Data structure and algorithm for clipping triangulation with leaf nodes of an octree

I have an application in which I am using an octree to store a volume mesh of axis-aligned bounding boxes (AABBs). Given a water-tight manifold triangle mesh, I need to: find if an AABB is ...
gnzlbg's user avatar
  • 141
3 votes
3 answers
233 views

Dealing with wasted space when using SIMD on CPU for vector maths

I've been getting interested in SIMD programming on CPU using SSE recently, but I'm a complete noob on the subject. I found this article describing how to make an efficient float3 type using the ...
russ's user avatar
  • 2,392
3 votes
2 answers
185 views

Smart half edge iteration?

In my HE implementation, half edges are stored in an array. When I iterate over the edges, I color all the HE black, and when I do an operation on an edge (e.g edge splitting) I mark both the current ...
Makogan's user avatar
  • 1,696
3 votes
1 answer
474 views

Compute shader textures compared 2D float4 arrays

I am wondering is there a difference in performance between using floating point textures as my 2D float4 array vs just passing in 2D float4 arrays? 2D float arrays eliminate the need to do texture ...
wduk's user avatar
  • 177
3 votes
0 answers
123 views

What techniques are used to build ray intersection acceleration structures on the GPU?

What improvements and alternatives have been developed since HLBVH was introduced in the 2010 paper HLBVH: Hierarcihcal LBVH Construction for Real-Time Ray Tracing of Dynamic Geometry by J. Pantaleoni ...
user avatar
2 votes
1 answer
135 views

Creating glsl library

I have different functions for example normalmapping which I use all the time... Now I thought about making a small glsl library. My problem: I don't want to have all functions within the same "...
Thomas's user avatar
  • 1,245
2 votes
1 answer
1k views

Why is pixel 0,0 at the top left of some formats and bottom left of others?

It seems that every image format (jpeg, png, tiff, bmp, jp2000...) doesn't place their origin at the same corner. Do you know where I could find some info about this differences? I can only say that ...
Sandburg's user avatar
  • 123
2 votes
1 answer
256 views

Dynamic array approach for GPU buffers

On CPU dynamic arrays are often used to store data of dynamic size, and often implemented by doubling the size when the array is full and copying the data over. The data structure has amortized O(1) ...
Lenny White's user avatar
2 votes
1 answer
459 views

is a scene graph actually a tree?

All "scene graphs" I've seen in practice are actually trees, but I have some vague memories about somebody saying a while ago that sometimes they can actually be graphs (technically, trees are already ...
Mei Zhang's user avatar
  • 121
1 vote
2 answers
319 views

How to assign a texture to a single entry of a texture array?

The C++ psuedo code to transmit the idea of what I want to do would be: Texture_array tarr = Texture_array(6); tarr[0] = texture; Which I am attempting to do as ...
Makogan's user avatar
  • 1,696
1 vote
1 answer
491 views

Which coding strategies exist to handle opengl texture size limit?

I recently hit the roof for maximum texture size for my opengl implementation (GL_MAX_TEXTURE_SIZE contains $3379$) when I wanted to create a texture for a 4k resolution video frame ($3840 \times 2160$...
mathreadler's user avatar
1 vote
1 answer
3k views

How do you load multiple textures into an array texture with OpenGL?

I have been reading the OpenGL documentation but it is not clear to me how to achieve the following. Say we have an array of strings. Each string in the array is a valid relative path to an image ...
Makogan's user avatar
  • 1,696
1 vote
2 answers
683 views

Efficiently transferring only needed parts of the vertex data to the GPU (C++/OpenGL)

I have a situation, where I have an array of vertices on the CPU side, for which, besides rendering-relevant data, like their position, I have a lot of other data at each vertex. All vertex data is ...
user avatar
1 vote
0 answers
95 views

What other geometry processing data structures are there?

I essentially know of 2 geometry processing data structures. one is the half edge (which has some really nice properties, but can't represent non manifold meshes nor tet meshes). The other is an ...
Makogan's user avatar
  • 1,696
1 vote
0 answers
20 views

How to handle object drawables?

Currently the graphics API I am using is Vulkan, but I am trying to find a general enough way to represent the following. In graphics, drawing can be generalized as: Get vertex buffers and send them ...
Makogan's user avatar
  • 1,696
1 vote
0 answers
60 views

Help with efficient quadtree vertices indexing to avoid redundancy

I am creating a quad tree from ground zero, because I am going to collapse it from bottom up I am refining it with a certain LoD level. I am using glm for mathematics and opengl for rendering. ...
richard_ba's user avatar
1 vote
0 answers
40 views

Proper design of data structure to store wavefront file information?

Currently I have a naive Mesh data structure to store wavefront files. This data has 3 buffers for the vertices, normals and UVs. It works well to the point I can render the sponza scene, despite ...
Makogan's user avatar
  • 1,696
1 vote
0 answers
111 views

How to pass *struct*ured data from libGDX to openGL shader?

I know about the standard methods to pass floats, ints, or vectors. However, I'm curious whether there is an elegant way to pass data from libGDX Java code directly into a shader struct. I'm looking ...
wehnsdaefflae's user avatar
0 votes
1 answer
179 views

Data structure of IFC-files

I know OBJ-files essentially are one or more lists of n-tuples containing information about the location of vertices, texture and normals. However, I am not sure how this is structured in an IFC-file. ...
Avatrin's user avatar
  • 113
-1 votes
1 answer
335 views

How to modify a part of VBO data without Compute Shader or OpenCL?

After binding the data to the vertex buffer object as follows, how to modify the buffer data? (Each subdata size is 3$*$ data size (three elements per index) ...
shashack's user avatar
  • 523