## Spatial partitioning?

Member
Posts: 281
Joined: 2009.04
Post: #1
What is the best method of spatially organising large groups of triangles? I would use octrees or X-Z quadtrees but I can't seem to find a triangle-square or triangle-cube intersection test.

Another of my questions is how to organise this: I tried to port my C code to C++ by copy-pasting all code (C++ is a subset of C after all?) and using Vector but this doesn't work. I tried to use C with memcpying but I find this hard to visualise.

~ Bring a Pen ~
Sage
Posts: 1,487
Joined: 2002.09
Post: #2
#1) Sorry, but no easy answer for this one. Are the triangles mostly the same size? A spatial hash or grid would work best here and are very easy to implement. Quadtrees work well for stuff that isn't quite 3 dimensions like heightmapped terrain. Octrees work well in general for 3D. BSP trees work very good as well, but only for certain types of triangle sets with good splits.

#2) Triangle to box intersection is easy. Use the Separating Axis Theorem. http://www.metanetsoftware.com/technique/tutorialA.html That tutorial is for 2D, but the idea is the same. The box has three axes, and the triangle one. If they overlap on all 4 axes, then they are intersecting.

#3) Other way around, but not quite. C is mostly a subset of C++, it just depends on which variant of C you are talking about. C99 code is not very C++ friendly and will need fixes for features unsupported in C++.

Scott Lembcke - Howling Moon Software
Author of Chipmunk Physics - A fast and simple rigid body physics library in C.
Member
Posts: 281
Joined: 2009.04
Post: #3
Well, the triangles are mostly the same size, but BSP trees would not need me to create custom BSP nodes for each object? I think a grid is a good idea and I will read the site linked.

I think I'm using C99 (don't even know :S) but my code is pretty straightforward: I'm not using any complex string functions or memcpy (bar the example mentioned, and sprintf).

Thanks for the reply anyway though. What do you think is the best way to organise a dynamic list of triangles in a spatial hash?

~ Bring a Pen ~
Sage
Posts: 1,487
Joined: 2002.09
Post: #4
Dynamic list? Meaning the triangles are moving? That adds another interesting dimension. I figured you meant static triangles. Do you have rigid objects where the triangles don't move in relation to each other? Depending on how many triangles there are per object you probably want to create a fixed spatial index for each object and then collide the spatial indexes against each other. Tree structures work well for this, grids do not.

Scott Lembcke - Howling Moon Software
Author of Chipmunk Physics - A fast and simple rigid body physics library in C.
Member
Posts: 281
Joined: 2009.04
Post: #5
Sorry if I was misleading; I meant a 'dynamic list' as a dynamic array: I can't count the triangles before I create the list of triangles so I will have to change the size of the array. That's why I'm using memcpy.

~ Bring a Pen ~
Sage
Posts: 1,487
Joined: 2002.09
Post: #6
How you load/store the triangles is irrelevant. For some spatial indexes you will need the all the triangles to measure the size of the world and such (most trees, grids, etc), while some do not (spatial partitioning, incremental trees).

The question you are asking is pretty much equivalent to "Which car should I buy?". There are a lot of different types of spatial indexes, and it really depends on what you want to use it for. You can either do a lot of reading about spatial indexes, or just get a car like all your friends have. For 3D, your best and simplest bets are an oct tree or a spatial hash. If it's relatively 2D like terrain or a one story building, a grid or an quad tree might be sufficient and simpler. Those are the Honda Civics and Toyota Camrys of the spatial indexing world I think. They are simple and sufficient even if not always the most optimal.

Scott Lembcke - Howling Moon Software
Author of Chipmunk Physics - A fast and simple rigid body physics library in C.
Member
Posts: 281
Joined: 2009.04
Post: #7
Quote:How you load/store the triangles is irrelevant.

That's part of the question. C or C++? Examples?

Considering I decide to use a 3D grid to store the triangles, which is the best method of storing these? Arrays? Creating a text file and writing the triangles positions, then reading the text file into memory at runtime and storing the triangles into arrays?

~ Bring a Pen ~
Sage
Posts: 1,487
Joined: 2002.09
Post: #8
Using a 3D array might be abad idea due to the amount of memory you would need to allocate. For 3D I'd use a spatial hash, but depending on what resolution you need a grid could work too and would be simpler to implement.

I'm not quite sure what you are getting at about storing the triangles. Presumably you are drawing them, why not just stick to the same format that you are passing to OpenGL? As for storing them on disk, how are you creating the models to begin with? If you are creating it as an .obj file, there isn't really a need to convert it to some custom format.

Scott Lembcke - Howling Moon Software
Author of Chipmunk Physics - A fast and simple rigid body physics library in C.
Member
Posts: 281
Joined: 2009.04
Post: #9
I am passing the triangles to OpenGL normally (from a set of arrays preloaded at start time from an OBJ). I am using the partitioning for character physics but It's too slow to check every triangle so I want to partition them.

~ Bring a Pen ~