how to store triangles in an octree

Question

1.00/5 (1 vote)

See more:

I am doing High Speed Data Calculation project for a CFD software.For this I have constructed an octree and pupulated it with particles.For collision detection,for each particle ,I have already calculated its neighbouring particles.For this purpose I have first calculated in which octree cube the particle lies and found out all the particles that lie in the neighbouring 26 cubes.This handles particle-particle collision. Now I have a task to handle particle-mesh collision and My mesh is triangle based. For the purpose I need to store the triangle in an octree and for each particle in an octree cube, I have to find out which triangles are lying in the neighbouring 26 cubes.And finding in which octree cube the triangle lies seems a difficult task since a single triangle can lie in more than one cube. so we need to check multiple points along its edges and its face to find out in exacltly which cube it lies. And one can never be sure how many such points along the edge and in the face of the triangle be taken for the purpose of checking since the size of the octree cube and triangle itself can be variable.
So Please help me out in this.what are the standard procedures generally followed for storing a triangle in an octree and finding its location(i.e.in which octree cube it lies)?

Posted 23-Nov-13 20:43pm

pramithas dhakal

Updated 10-Feb-19 3:37am

v3

Add a Solution

Comments

OriginalGriff 24-Nov-13 5:09am

From that? No, probably not.
This is not a good question - we cannot work out from that little what you are trying to do.
Remember that we can't see your screen, access your HDD, or read your mind.
Use the "Improve question" widget to edit your question and provide better information.

pramithas dhakal 24-Nov-13 21:47pm

I am doing High Speed Data Calculation project for a CFD software.For this I have constructed an octree and pupulated it with particles.For collision detection,for each particle ,I have already calculated its neighbouring particles.For this purpose I have first calculated in which octree cube the particle lies and found out all the particles that lie in the neighbouring 26 cubes.This handles particle-particle collision. Now I have a task to handle particle-mesh collision and My mesh is triangle based. For the purpose I need to store the triangle in an octree and for each particle in an octree cube, I have to find out which triangles are lying in the neighbouring 26 cubes.And finding in which octree cube the triangle lies seems a difficult task since a single triangle can lie in more than one cube. so we need to check multiple points along its edges and its face to find out in exacltly which cube it lies. And one can never be sure how many such points along the edge and in the face of the triangle be taken for the purpose of checking since the size of the octree cube and tringle itself can be variable.
So Please help me out in this.what are the standard procedures generally followed for storing a triangle in an octree and finding its location(i.e.in which octree cube it lies)?

Sergey Alexandrovich Kryukov 24-Nov-13 12:30pm

If you provide sufficient detail and explain your problems, you may get help, as such problems are relatively simple.
http://whathaveyoutried.com so far?
—SA

pramithas dhakal 24-Nov-13 21:47pm

I am doing High Speed Data Calculation project for a CFD software.For this I have constructed an octree and pupulated it with particles.For collision detection,for each particle ,I have already calculated its neighbouring particles.For this purpose I have first calculated in which octree cube the particle lies and found out all the particles that lie in the neighbouring 26 cubes.This handles particle-particle collision. Now I have a task to handle particle-mesh collision and My mesh is triangle based. For the purpose I need to store the triangle in an octree and for each particle in an octree cube, I have to find out which triangles are lying in the neighbouring 26 cubes.And finding in which octree cube the triangle lies seems a difficult task since a single triangle can lie in more than one cube. so we need to check multiple points along its edges and its face to find out in exacltly which cube it lies. And one can never be sure how many such points along the edge and in the face of the triangle be taken for the purpose of checking since the size of the octree cube and tringle itself can be variable.
So Please help me out in this.what are the standard procedures generally followed for storing a triangle in an octree and finding its location(i.e.in which octree cube it lies)?

Stefan_Lang 25-Nov-13 6:36am

You mention collision detection, implying moving objects. There's no point in storing moving objects in an octree, since the calculations necessary for that would have to be repeated incessantly!

Therefore your question doesn't make sense: either the points are moving and storing them in an octree was an error from the start, or the mesh is moving, in which case storing that in an octree is impractical.

1 solution

Add a Solution

Add your solution here

Treat my content as plain text, not as HTML

Preview 0

…

Existing Members

Sign in to your account

...or Join us

Download, Vote, Comment, Publish.

Your Email
Password
Forgot your password?

Your Email
This email is in use. Do you need your password?
Optional Password

I have read and agree to the Terms of Service and Privacy Policy
Please subscribe me to the CodeProject newsletters

When answering a question please:

Read the question carefully.
Understand that English isn't everyone's first language so be lenient of bad spelling and grammar.
If a question is poorly phrased then either ask for clarification, ignore it, or edit the question and fix the problem. Insults are not welcome.
Don't tell someone to read the manual. Chances are they have and don't get it. Provide an answer or move on to the next question.

Let's work to help developers, not make them feel stupid.

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

tugrulGtx · Answer 1 · 2019-02-10T03:37:00

Why are you using both a uniform grid (I understand this from your "26 neighbor ..") and an octree at the same for same task (collision detection)?

You could have a broad octree for broadphase collisions (particle - mesh). Then in each broad octree node that is filled, have a sub-octree to hold its triangles (particle - triangle).

First check if collision is made with "mesh object" and if it collides, then check which triangle is that by the sub octree.

Since number of mesh << number of triangles, the first octree would be small enough to be able to re-build at each frame. Then in each sub-octree, you can simply "transform" the coordinates instead of re-building it. Did mesh rotate? Then rotate octree, don't rebuild it. I assumed meshes are static. For static meshes, also you can cache index arrays to access nodes at 1 step instead of log2(n) steps. If meshes are dynamic(and also particles are dynamic I assume), then have a look at "loose octree". These have above normal volumes per node hence it needs less frequent updates.