Skip to main content

Questions tagged [octree]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
1 vote
1 answer
77 views

Octree as struct not class

I was wondering (as I could not find any implementation online), if anyone here would have an idea of how to create an octree as a struct and not a class. The problem is that Octrees are usually ...
L Chougrani's user avatar
1 vote
0 answers
27 views

What would be a good way to interface a voxel octree to commit multiple changes at once?

I am creating a voxel game that uses octrees for storage. The implementation details are not super relevant, but the entire octree is ordered and contiguous in memory and each branch can be merged and ...
CPlus's user avatar
  • 143
0 votes
1 answer
178 views

How can I handle voxels that require extra data in my octree?

I am using octrees as an efficient way to store voxel data in a voxel game. The details of my octree implementation can be found here, but in a nutshell, each node is 16 bits, and the most significant ...
CPlus's user avatar
  • 143
0 votes
0 answers
89 views

Octree build time crashes page for complex mesh

Using the standard three.js FPS example of octree implementation with a more advanced mesh, crashes the page on load. My first idea is to write a few functions to save the octee data to a file, then ...
B''H Bi'ezras -- Boruch Hashem's user avatar
1 vote
0 answers
143 views

What is the fastest way to insert and move a rectangle object into a linear octree?

So I have build a linear (basically an array) octree containing rectangular objects (like bounding boxes). Every node has an unique index, all child indexes (if present) and parent node index (if not ...
Janis Taranda's user avatar
1 vote
0 answers
234 views

How to use transvoxel cell cache with octree structure?

I have been implementing Transvoxel in to my Marching Cubes project in c++. The Transvoxel documentation and available code examples feature cell vertex reuse (caching) via indices. The main benefits ...
trshmanx's user avatar
  • 171
3 votes
3 answers
1k views

How to read a sparse Octree sequentially, like a 3D array?

Is it possible to read a sparse Octree like a regular 3D grid: for(z) for(y) for(x) ...and still benefit from skipping large empty areas? I need this for a ...
trshmanx's user avatar
  • 171
0 votes
0 answers
254 views

Can inserting/removing one point in a quadtree or octree cause multiple splits/collapses?

I was reading Robert Nystrom's Game Programming Patterns website and, in the section about spatial partitioning, particularly in the section on quadtrees, he mentions: Objects can be added ...
Carmo's user avatar
  • 157
0 votes
0 answers
691 views

How to calculate ray unit grid intersections?

P is ray origin, D direction. How do I calculate tx, ty(s)? This is for octree raycast. The primary goal is to get 1st intersection voxel (v) then second (v") and so on.
Janis Taranda's user avatar
0 votes
0 answers
268 views

How to raycast octree for closest leaf node?

So I need to raycast a octree for closest leaf node as efficient as possible. I will be doing it on compute shader (hlsl), but I think it doesn't matter because first I need to understand the approach ...
Janis Taranda's user avatar
0 votes
1 answer
370 views

How to construct a octree density from SDF for MC

It very clear how it works with a regular grid. 3 inner loops - x, y, z over some size. The smaller the cells, so will be the mesh more detailed. But how about octree. I know i can stich different ...
trshmanx's user avatar
  • 171
0 votes
0 answers
269 views

Octree LOD without traversing the entire tree

I am working on a voxel engine that uses a huge Hashed Linear Octree that reconfigures when you move. Each octree leaf is a voxel. The world is procedurally generated using 2D Perlin noise. The octree ...
Amit Assaraf's user avatar
0 votes
1 answer
276 views

Octree Terrain Destruction and LODs

Meet my octree world: My end goal is to have this world destructible, and I am having an issue warping my head around how this can be done when you have LOD. The basic principle of LOD (as I ...
Amit Assaraf's user avatar
0 votes
0 answers
443 views

Benefit of storing chunks as Octree leafs vs single block as Octree leaf

I saw many voxel game developers opt for a strategy that involves using an octree whose leaf nodes include a 16x16x16 (or 32^3 or 64^3) chunk instead of having leafs represent a single voxel. What is ...
Amit Assaraf's user avatar
1 vote
0 answers
306 views

Fast Occlusion Discovery in 3D Point Cloud

I am trying to find occluded objects given a view point at x,y,z in the scene. For instance in the example below all the points constructing trees should be ...
fhm's user avatar
  • 11
1 vote
1 answer
2k views

Using octrees as LOD system

I am using an octree to define my 3D voxel world. And I want to use octree subdivision as a LoD system. This means, subdivide close to the player, but far away nodes un-subdivided. But it occurs to me ...
Bram's user avatar
  • 3,729
0 votes
0 answers
237 views

Too many neighbors when pathfinding in Sparse Voxel Octree

Imagine we have upto 9 or so layers (that is depth), and due to some big colliding platform in the level, one of the empty nodes close to the root have all much smaller nodes as neighbors at one of ...
Acey's user avatar
  • 11
0 votes
0 answers
71 views

Best option to narrow a known set of triangles?

I am building collision detection and response in a custom engine. This routine happens between the moving player, and static entities on the map. In the first phase, the broad phase I am moving the ...
kevzettler's user avatar
1 vote
0 answers
37 views

How to track/identify amorphous blobs in 2D or 3D space

In doing HTML/DOM work, you are working with concrete nodes which you can visibly touch and have a defined shape and boundary. What I'm wondering though is like with a cloud like structure, or like a ...
Lance's user avatar
  • 177
1 vote
0 answers
74 views

How can I save a local player modification into a procedurally generated terrain density octree?

So I have recently been researching how to implement DC for procedural terrain. I originally planned to use a 3D grid that just stated if the point is solid or not. I have noticed that most other ...
Drok_'s user avatar
  • 11
1 vote
0 answers
66 views

Modern way of getting points within a distance?

I'm making a game engine, and some components may want to interact with others based on distance. Currently, the component registers an update listener which runs on a loop, then it checks the ...
evilpudding's user avatar
0 votes
2 answers
243 views

Need help with simple octree implementation

Hello I'm trying to implement an octree, but when I query the centre positions they all return zero, but these should be offset from zero. Here is my code: ...
cee012's user avatar
  • 3
1 vote
0 answers
35 views

Calling update oct-function (only if changed)

Issue: How is the best way to update my units position on the oct-tree, I'm struggling with the logic, specifically when It changes oct, tree, I want it to pop itself of its previous oct-tree, and it ...
RNewell122's user avatar
1 vote
1 answer
136 views

Setting up an "Oct-Tree"

Instead of spam the same hard question like my previous one that Is difficult to get a minimum verifiable example for, I have decided to rework my path-finding and I can fix a lot of my issues with an ...
RNewell122's user avatar
1 vote
0 answers
691 views

Simple Stupid Funnel Algorithm (SSFA) for 3D Navigation

tl;dr I need an algorithm similar to SSFA except for portals with 4 vertices (or n vertices if an algorithm like that exists). I'm working on a game that requires pathfinding in 3 dimensions. By this ...
Andriy Dzikh's user avatar
4 votes
0 answers
306 views

How do I test my Octree implementation?

I decided to use an Octree subdivision in my game. After implementing it, I do some research (a few tests and comparisons) and came up with several questions about. The main question: How to test my ...
GreenTheGreen's user avatar
1 vote
0 answers
464 views

How to convert an octree to a 3D array

I have an octree that I'm planning to use for 3D pathfinding. My plan was to break down the world such that all the leaf nodes of the tree would be of equal dimensions that would create a nice grid ...
user1265215's user avatar
1 vote
0 answers
867 views

Does anyone have a example of Dual Contouring in C#?

I'm trying to develop a method of creating terrain using Perlin. I've followed plenty of the Minecraft tutorials, and got them to function. I've done some playing around with MarchingSquares, but I'm ...
Alexander Meyers's user avatar
3 votes
1 answer
2k views

General Octree question: What do you actually store?

Ok, So I'm experimenting with various terrain generation methods, primarily in Unity, but i'll admit to not use all its features because I started learning about Game Dev in XNA YEARS ago. So, I made ...
Alexander Meyers's user avatar
0 votes
2 answers
437 views

Drawbacks to an Octree and Quadtree hybrid?

I've implemented an octree to divide 3D space that contains several objects. I've noticed in certain octree nodes I could use more refinement in some axis, but splitting the node into 8 children is a ...
FerranMG's user avatar
0 votes
1 answer
2k views

How can I correctly instantiate an octree in UE4?

I tried to create a simple Octree like this: (I looked at the FMeshTriOctree source code since no question in answers.unrealengine.com helped me) ...
arthur.sw's user avatar
  • 291
2 votes
1 answer
501 views

Simplyfing/dissolving octree to simple boxes by adjacent octants with similar traits

I am looking forward to create a navigation volume to be utilized by AI actors. The approach I am trying to tackle here is to first generate an octree and associate with respectable flags/data (type, ...
tomsseisums's user avatar
  • 3,366
9 votes
1 answer
3k views

Building an Octree for terrain generation

I've previously implemented marching cubes/tetrahedra to render an IsoSurface. It worked (YouTube), but the performance was dire as I never got around to implementing variable Level of Detail based on ...
Basic's user avatar
  • 1,278
5 votes
1 answer
2k views

Is Frustum culling still needed today?

I'm reading about efficient Frustum culling algorithms. I found an article about a smart method that first use the Frustum AABB (Axis Aligned Bounding Box) to eliminate most of the scene before check ...
Hatoru Hansou's user avatar
3 votes
2 answers
1k views

How can I calculate an octree node's depth from its location code?

The article Advanced Octrees 2: node representations states: The AABB (axis-aligned bounding box) of the node can be stored explicitly as before, or it can be computed from the node’s tree depth ...
gnzlbg's user avatar
  • 131
0 votes
0 answers
825 views

Octree Frustrum Culling

times came when i had to implement some culling into my engine. I started by reading some stuff and so far so good. I managed to create an octree which can effectivly divide my geometry's vertices (...
user2742982's user avatar
2 votes
0 answers
2k views

How do I implement a sparse voxel octree?

I've been working on a voxel engine and I want to implement sparse voxel storage. As I understand it, it works a bit differently from a regular octree and has some neat performance increasing "tricks"....
Russoul's user avatar
  • 282
4 votes
0 answers
967 views

How to convert an octree to a polygon mesh?

So if I have dynamic voxel terrain data stored in an octree representation what would be the best way to go about converting the octree to a polygon mesh which I can render with OpenGL? A lot of ...
Edward J Brown's user avatar
1 vote
1 answer
899 views

How can I store point voxel terrain in octrees

I am writing a voxel engine in LWJGL3 - binding for OpenGL 4 for JVM. Recently I implemented an octree storage of cubic voxels. In my implementation each leaf node of an octree has one voxel, voxels ...
Russoul's user avatar
  • 282
1 vote
0 answers
71 views

How to move octree data correctly from parent to child?

This is my first question, so apologies if it is a repeat, I have had a look at the other questions and I still can't seem to find an answer to this. So I am making a recursive octree in OpenGL. So ...
101_son's user avatar
  • 66
0 votes
1 answer
3k views

Should I use octree or quadtree for my spacial data structures? [closed]

I would like to know the advantages and disadvantages of using octree or quadtree for spacial data structures? In a 3d gaming setting would you ever need more than 4 children nodes? Does it take ...
Andrew Wilson's user avatar
2 votes
0 answers
2k views

Binary Space Partitioning of 3d Triangle Mesh (for finding nearest points)

I'm writing a Binary Space Partitioning (BSP) tree for the purpose of optimizing finding the nearest point on the surface of a 3d triangle mesh with respect to another point. I'm currently following a ...
Erik's user avatar
  • 21
0 votes
1 answer
331 views

How can I split up a large model into an octree codewise?

For collision detection, I am attempting to split up a large model into an octree. If we take this black thing thing to be the ship (104,000 vertices): Then I would like to split up the faces I ...
joehot200's user avatar
  • 733
2 votes
0 answers
774 views

Actual use of sparse voxel octrees in a game engine

Looking for different ways to speed up my simple voxel system reducing the number of voxels and generated triangles, I stumbled upon these sparse voxel octrees. Now, I read a lot about it: how do they ...
edornd's user avatar
  • 121
0 votes
2 answers
2k views

Implicit Functions and extracting an isosurface

I recently discovered a paper on Dual Marching Cubes which produces a much reduced poly count to other methods like Dual Contouring and Marching Cubes, however a recurring theme when reading these ...
Mark A. Ropper's user avatar
3 votes
1 answer
3k views

Marching cubes over an octree dual - how?

In Dual Marching Cubes the dual of an octree is tessellated via the standard marching cubes method. But the classical marching cubes algorithm operates only on cubes with eight vertices (it uses signs ...
GameDevEnthusiast's user avatar
4 votes
1 answer
583 views

Determine wheter an octree node needs to be continue

For collision detection (moving vs. non-moving) in my current project, I decided to implement an octree approach after the preselection. The only collision detection I'm currently using is a AABB-vs.-...
s3lph's user avatar
  • 143
3 votes
1 answer
642 views

Dynamic Quad/Oct Trees

I've recently discovered the power of Quadtrees and Octrees and their role in culling/LOD applications, however I've been pondering on the implementations for a Dynamic Quad/Oct Tree. Such tree would ...
KKlouzal's user avatar
  • 252
10 votes
1 answer
7k views

How to efficiently render a large terrain mesh?

Recently I've been stuck on a problem thinking about the best way to generate a terrain into my game. In another projects I normally used heightmaps, so all the core-work was based on the engine used, ...
Karl Marny's user avatar
1 vote
1 answer
240 views

How to create more vertexes from within a shader in OpenGL?

when rendering voxels in octrees, the only information necessary is the current octree-level, -position and colour/texture. But one has to send eight vertices to the rendering pipeline in order to ...
yogo1212's user avatar