Part of the Khronos Group
OpenGL.org

The Industry's Foundation for High Performance Graphics

from games to virtual reality, mobile phones to supercomputers

Results 1 to 1 of 1

Thread: Fast Adjacent Triangle Identification

  1. #1
    Junior Member Newbie
    Join Date
    May 2016
    Posts
    2

    Fast Adjacent Triangle Identification

    Identifying adjacent triangles:

    One approach is to loop over each vertex and to compare it with all the other vertices. This can be optimized a bit:
    - A triangle may at most have 3 adjacent triangles
    - All adjacent vertices will be after the current vertex (Because the previous vertices already found the current vertex!)

    But, it will still be a quadratic time algorithm, which can be quite slow.



    A linear time algorithm:
    We will use keys to quickly find adjacent vertices. (Input: vertex, Output: an array of triangles that share the vertex)

    1) Create an object that can have keys and values
    Make sure that a single key can store multiple values/an array.

    2) For each vertex, store it in your object as a key and store the vertex' triangle as the value. (Linear time)

    Code :
    object adjacencyInfo;
    foreach(vertex in mesh){
      if(adjacencyInfo.HasKey(vertex){
        //If the keys is already present, just add the triangle to the key
        adjacencyInfo["vertex"].Add(vertex.triangle);
      }else{
        //Otherwise, we will have to create the key and add the triangle
        adjacencyInfo["vertex"] = vertex.triangle;
      }
    }

    3) Now you can simply loop over each vertex and look it up in the object (Also linear time)

    Code :
    foreach(vertex in mesh){
       adjacencyInfo["vertex"] //All adjacent vertices
    }



    For finding a triangle with a common edge, a slightly modified algorithm can be used: http://stackoverflow.com/a/34848669/3492994
    Last edited by stefnotch; 05-07-2016 at 07:21 AM. Reason: Added a link

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •