Get connected Triangles
Get connected Triangles
Get connected Triangles
Get connected Triangles
Get connected Triangles
Get connected Triangles Get connected Triangles Get connected Triangles Get connected Triangles Get connected Triangles Get connected Triangles Get connected Triangles Get connected Triangles
Get connected Triangles Get connected Triangles
Get connected Triangles
Go Back  Xtreme Visual Basic Talk > > > > Get connected Triangles


Reply
 
Thread Tools Display Modes
  #1  
Old 07-11-2006, 05:50 AM
RcSepp RcSepp is offline
Regular
 
Join Date: Oct 2004
Posts: 55
Question Get connected Triangles


Hi again

My current problem is about getting a group of all connected triangles in a vertex buffer.

I tried to build myself a cycle to get all connected triangles manually, but after two days optimizing my code I'm still at calculating about 100 vertices per second (For an object with 100000 vertices I need nearly 17 minutes).

My vertexbuffer contains a trianglelist.

I already saw programs, that do this in under a half of a second and these programs also worked with trianglelist (not trianglestrips or -fans).

How do they do this??? Is there any function from direct3d itself, that does it?

Please help me finding a faster solution
Reply With Quote
  #2  
Old 07-16-2006, 06:33 AM
Iceplug's Avatar
IceplugGet connected Triangles Iceplug is offline
MetaCenturion

Retired Moderator
* Guru *
 
Join Date: Aug 2001
Location: Iowa, USA
Posts: 16,583
Default

Show me how you are initializing your vertex buffer and drawing it?
__________________

Iceplug, USN
Quadrill 1 Quadrill 2 (full) Quadrill 3 JumpCross .NET Website is ALIVE! - DL Platform Tour for VB.NET! Posting Guidelines Hint: Specify your location in your user cp profile if you want compassion!
Reply With Quote
  #3  
Old 07-16-2006, 07:20 PM
Rockoon's Avatar
Rockoon Rockoon is offline
Joseph Koss

* Guru *
 
Join Date: Aug 2003
Location: Unfashionable End
Posts: 3,615
Default

Access the vertex buffer once, copying the vertex coordinates into a native array.
Reply With Quote
  #4  
Old 07-19-2006, 05:07 AM
RcSepp RcSepp is offline
Regular
 
Join Date: Oct 2004
Posts: 55
Cool

Thank you for replaying

I have already copyed the vertex buffer into a native array.

I now have found a way to solve my problem pretty fast. The only problem is that it uses meshes, so I can't use this for big vertex buffers (maximum 65534 faces)

Here is what I do:

1.Create a temporary mesh with my vertexbuffer (I use PositionOnly for speed reasons)
Code:
Dim TempMesh As New Mesh(TargetBufferVertexCount / 3, TargetBufferVertexCount, MeshFlags.Managed, VertexFormats.Position, d3dDevice)

                    Dim gs As GraphicsStream = TempMesh.VertexBuffer.Lock(0, 0, LockFlags.None)
                    For i As Long = 0 To TargetBufferVertexCount - 1
                        gs.Write(New CustomVertex.PositionOnly(TargetVerts(i).Position))
                    Next
2.Build a simple index buffer with index1=1, index2=2, ....
Code:
Dim indices(TargetBufferVertexCount) As Long
                    For i As Long = 0 To TargetBufferVertexCount - 1
                        indices(i) = i
                    Next
                    Dim ib As IndexBuffer = TempMesh.IndexBuffer
                    ib.SetData(indices, 0, LockFlags.None)
3.Calculate the adjacency (the neighbors for each face)
Code:
Dim Adjacency(TargetBufferVertexCount * 9) As Integer
                    TempMesh.GenerateAdjacency(0, Adjacency)
4. Dispose the mesh

5.Make a function that gets all neighbours and calls itself again for every new neighbour
Code:
GetNeighbours(0, Adjacency, SelectedTriangles)
0 is the triangle to start
Adjacency is the adjacency array
SelectedTriangles is the array we want to fill with all connected triangles

Here is the body of the function:
Code:
Private Sub GetNeighbours(ByVal TriangleIndex As Integer, ByVal Adjacency() As Integer, ByVal SelectedTriangles As ArrayList)
        Dim Triangle As Integer = Adjacency(TriangleIndex * 3)
        If Not SelectedTriangles.Contains(Triangle) Then
            SelectedTriangles.Add(Triangle)
            GetNeighbours(Triangle, Adjacency, SelectedTriangles)
        End If
        Triangle = Adjacency(TriangleIndex * 3 + 1)
        If Not SelectedTriangles.Contains(Triangle) Then
            SelectedTriangles.Add(Triangle)
            GetNeighbours(Triangle, Adjacency, SelectedTriangles)
        End If
        Triangle = Adjacency(TriangleIndex * 3 + 2)
        If Not SelectedTriangles.Contains(Triangle) Then
            SelectedTriangles.Add(Triangle)
            GetNeighbours(Triangle, Adjacency, SelectedTriangles)
        End If
    End Sub
This function checks each of the three neighbour-triangles if they have already been added. If not, the function is repeated for this neighbour.

Everyone can use this code at own will, but if you can still speed it up, please post your ideas. I would be happy about it.
Reply With Quote
  #5  
Old 07-19-2006, 01:17 PM
Rockoon's Avatar
Rockoon Rockoon is offline
Joseph Koss

* Guru *
 
Join Date: Aug 2003
Location: Unfashionable End
Posts: 3,615
Default

Ok then the next step (for the do-it-yourselfer) is a hash table so as to eliminate the expensive searches for equal vertices.
Reply With Quote
  #6  
Old 07-20-2006, 08:56 AM
RcSepp RcSepp is offline
Regular
 
Join Date: Oct 2004
Posts: 55
Default

hash table?
Sounds awesome! I can't wait to try that.
Reply With Quote
  #7  
Old 07-20-2006, 08:53 PM
Rockoon's Avatar
Rockoon Rockoon is offline
Joseph Koss

* Guru *
 
Join Date: Aug 2003
Location: Unfashionable End
Posts: 3,615
Default

Yeah, the basic gist of it would be that you have a set of vertices representing your "working set" of connected triangles. These would be stored in a hash table to facilitate fast lookups. You might as well go overboard on the size of the hash table since it doesnt sound like ram will ever be an issue (its only 100,000 vertices after all)
Reply With Quote
Reply


Currently Active Users Viewing This Thread: 1 (0 members and 1 guests)
 
Thread Tools
Display Modes

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is Off
HTML code is Off

Forum Jump

Advertisement:





Free Publications
The ASP.NET 2.0 Anthology
101 Essential Tips, Tricks & Hacks - Free 156 Page Preview. Learn the most practical features and best approaches for ASP.NET.
subscribe
Programmers Heaven C# School Book -Free 338 Page eBook
The Programmers Heaven C# School book covers the .NET framework and the C# language.
subscribe
Build Your Own ASP.NET 3.5 Web Site Using C# & VB, 3rd Edition - Free 219 Page Preview!
This comprehensive step-by-step guide will help get your database-driven ASP.NET web site up and running in no time..
subscribe
Get connected Triangles
Get connected Triangles
Get connected Triangles Get connected Triangles
Get connected Triangles
Get connected Triangles
Get connected Triangles Get connected Triangles Get connected Triangles Get connected Triangles Get connected Triangles Get connected Triangles Get connected Triangles
Get connected Triangles
Get connected Triangles
 
Get connected Triangles
Get connected Triangles
 
-->