# Finding Triangle Neighbours

This topic is 3794 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

Hi, I am working with the marching cubes algorithm at the moment and need to smooth the mesh afterwards. In order to do so I need to know the neighbours of each triangle and I need to compute vertex indices of the triangulated volume chunk Some options: 1) I could propagate the vertex & triangle indices from left to right when traversing the volume from left to right and the rest of the vertices are found with a map(std::map) this approach requires a lot of tree traversion, something I would like to avoid. 2) Another option would be a hash map. 3) split the triangulation into small chunks, generate the vertex indices and triangle relationships and combine the chunks later on I would be very glad if you had some suggestions that would help me to develop a more efficient algorithm to achieve the mention aim thx in advance

##### Share on other sites
So you are referring to the map and hash_map as a way of finding the index of a vertex which has already been added? That is fine, but you can get closer to constant time by using a 3D lookup table the same size as your chunks. Clear the values in the lookup table to -1. Now, each time you generate a vertex you can set the corresponding position in the lookup table to be it's index. Actually it can be/better/simpler than I described, but ask for more details if you want to go this route.

Otherwise, I assume you need to smooth the mesh because you are working with binary data? Have you though about smoothing the volume (with a low pass filter) before running the MC algorithm? This should mean the mesh you get is already pretty smooth.

Also check out the project in my signature. It uses marching cubes for the geometry generation.

##### Share on other sites
Smoothing the volume is not an option unfortunatly.

I implemented it with a std::map< ivertex3, uint>
where ivertex3 is
int x,y,z; and a operator<

MC returns ivertex3 and I do a lookup then ...

with a 32*32*255 volume filled with heightmap data it takes around 128 ms on my 3 years old AMD Winchester.

Your idea with the 3d volume sounds interesting and pretty straight forward, I ll give it a try.

I ll also implement a hash map.

luckily I have several frames(1-4) to triangulate and smooth it

But I think with the 3d volume approach I could get below the 100 ms

I ll post the results, so stay tuned

##### Share on other sites
I just implemented the lookup table and the results are disappointing

std::map<ivertex4,uint>:
repeated 20x:
~67-68 ms
repeated 1x:
~ 124 ms

3d lookup:
repeated 20x:
~60-67 ms
repeated 1x:
~ 128 ms

The 20x iterations perform better because of the increase cache coherence and memory mapping

However I will probably face the case that modifications to the volume happend rather seldom, so I had to examine both approaches on a multi core cpu to judge which one performs best.

I think further optimization should concentrate on minimizing the dimension of the volume the MC works on.
e.g.: tracking modifications to determine the min & max values of the chunk, since I am working with heightmaps, most terrain chunks' bounding boxes will be very flat.

If you have further ideas please let me know

##### Share on other sites
Hi

so I finished the triangulation now.

The result:
Vertices: 4990
Triangles: 9525

Time to Triangulate and to build the Triangle Neighbour structure
72 ms 3D-Lookup
250 ms std::map

Now its time to optimize this further, to get below 60 ms
One way to go might be multithreading, 3 threads moving the data onto a stack or a ring buffer and another threads builds the triangle structure

maybe one can subdivide the steps and combine the results in the end

CPU:
processor : 0
vendor_id : AuthenticAMD
cpu family : 15
model : 31
model name : AMD Athlon(tm) 64 Processor 3000+
stepping : 0
cpu MHz : 1005.165
cache size : 512 KB
fpu : yes
fpu_exception : yes
cpuid level : 1
wp : yes
flags : fpu vme de pse tsc msr pae mce cx8 apic sep mtrr pge mca cmov pat pse36 clflush mmx fxsr sse sse2 syscall nx mmxext fxsr_opt lm 3dnowext 3dnow lahf_lm
bogomips : 2012.45
TLB size : 1024 4K pages
clflush size : 64
cache_alignment : 64
address sizes : 40 bits physical, 48 bits virtual
power management: ts fid vid ttp

##### Share on other sites
Right, sorry, I'm not getting much time to post...

Some more thoughts:

Regarding the 3D lookup table I should point out that you don't need your table to be as big as the volume (I just described it that way to may it easier to understand). Assuming you process your slices in order, you know for example that the first slice will never share a vertex with the third one. So actually, you only need to keep two 3D lookup slices at a time. This cuts down on your memory usage a lot.

Secondly, you might want to consider breaking you volume down into chunks. Firstly this allows to you use even less memory for your 3D lookup slices, and secondly it means you can process different chunks on different threads in parallel. The only catchis it means you will have duplicate vertices where the mesh for one chuck joins the mesh for another. Think about whether this will cuse a problem for you smoothing algorithm.

There's also stuff you can do to optimise the basic algorithm. For example a naive algorithm will visit a cell and look at the eight corner voxels. It will then more onto an adjacent cell and again look at the eight corner voxels *even though four of them are the same as for the previous cell*. A smart implementation should optimise for this kind of thing.

Lastly, just in case I can convince you to smooth the volume instead of the mesh, remember that you don't have to actually *create* a smoothed volume. Instead you can simply smooth each voxel as you use it. Each time you retrieve a voxel you average it with its neighbours - this lets you have a smoothed volume without any memory overhead...

Hope that helps!

##### Share on other sites
Following your tips I could cut down the time it takes to
54-56 ms

I also consider to half the volume size to be triangulated at once
in the final terrain triangulation, this would result in
17 ms that is realtime triangulation at 50 fps.

I can easily avoid cracks at the boundery if I only smooth boundery edges along the boundery axis and I don t have to update too many triangle meshes for the physics engine

What it left to be implemented is to use only two slices for the lookup table, this hopefully makes some room in the L1 cache for the rest of the volume data.

Currently the triangulation pipeline looks as follows

MC->TriangleStorage->BuildVertexIndices->BuildTriangleNeighborhood

I consider breaking this up into
MC->TriangleStorage->BuildVertexIndices
and then seperately
BuildTriangleNeighborhood

This should reduce page trashing in the memory management unit a little I think

stay tuned :)

P.S.: Forgot to mention, I rearranged some of the slopes and I count the number of free edges for each triangle before I test it against the next one
maybe I could put that count into a seperate array

##### Share on other sites
So I finally found the bug in my edge collapse algorithm.

You need to find all triangles touching the vertices of the edge to be collapsed.
This is usually done by extracting a triangle fan in CW and CCW direction on the right and left side of respectively

I just forgot to check whether this fan is closed, otherwise the search diverges

The edgecollapse of ~4000 triangles takes only 1-2 ms

Now I just need to pick some random triangles and compare their crease angles and collapse their shared edges accordingly

The triangulation algorithm takes only 51 ms now, thats 3 ms less although its pretty much optimized already.
The speedup came from replacing the index calculation with a const int lookuptable, although I am already compiling with highest optimization enabled

1. 1
2. 2
Rutin
16
3. 3
4. 4
5. 5

• 13
• 26
• 10
• 11
• 9
• ### Forum Statistics

• Total Topics
633722
• Total Posts
3013546
×