2023.01.13 TIL: LeetCode 2246, Visibility Buffer Rendering with Material Graph

Highfence·2023년 1월 13일
0

TIL

목록 보기
2/2

LeetCode 2246

오늘도 한 문제를 풀었다. LeetCode에서 처음 풀어보는 Hard 단계 문제였는데, 아마도 Hard중에서는 그렇게 어려운 편은 아니었을 것 같다.
https://leetcode.com/problems/longest-path-with-different-adjacent-characters/

이것도 Tree관련 순회 문제인데, 풀고 나서 다른 사람의 코드를 보니 필요없는 코드들이 꽤 많다는 것을 확인했다.



   public class LongestPathNode
   {
       public int LongestPathAsRoot;
       public int LongestPathAsChild;
       public char Label;
       public List<int> Childs;
   }

   public int LongestPath(int[] parent, string s)
   {
       var nodes = Enumerable.Range(0, parent.Length).Select(i => new LongestPathNode
       {
           LongestPathAsRoot = 0,
           LongestPathAsChild = 0,
           Label = s[i],
           Childs = new()
       }).ToList();

       for (var i = 1; i < parent.Length; ++i)
       {
           var parentIndex = parent[i];
           var node = nodes[parentIndex];

           node.Childs.Add(i);
       }
       
       CalculateLongestPath(nodes[0], nodes);
       return nodes.Max(node => node.LongestPathAsRoot);
   }

   public void CalculateLongestPath(LongestPathNode currentNode, List<LongestPathNode> nodes)
   {
       var longestPathOfChild = 0;
       var secondLongestPathOfChild = 0;

       foreach (var childIndex in currentNode.Childs)
       {
           var childNode = nodes[childIndex];
           CalculateLongestPath(childNode, nodes);

           if (childNode.Label == currentNode.Label)
           {
               continue;
           }

           if (childNode.LongestPathAsChild > longestPathOfChild)
           {
               secondLongestPathOfChild = longestPathOfChild;
               longestPathOfChild = childNode.LongestPathAsChild;
           }
           else if (childNode.LongestPathAsChild > secondLongestPathOfChild)
           {
               secondLongestPathOfChild = childNode.LongestPathAsChild;
           }
       }

       currentNode.LongestPathAsRoot = longestPathOfChild + secondLongestPathOfChild + 1;
       currentNode.LongestPathAsChild = longestPathOfChild + 1;
   }

Visibility Buffer Rendering with Material Graph

http://filmicworlds.com/blog/visibility-buffer-rendering-with-material-graphs/
오늘 위 글을 마저 좀 봤다.

Visibilty Rendering이 포워드, 디퍼드 렌더링에 비해서 갖는 우위점은 Triangle이 Pixel 대비 점점 작아질 수록, 2x2 Quad로 실행되는 Pixel Shader에서 이 Quad를 여러 삼각형이 차지하게 되고, 그 경우 Quad Utilization이 낮아지면서 Pixel Shader와 Material, Lighting Shading이 강력하게 바인딩이 되어있는 포워드, 디퍼드 렌더링은 상대적으로 손해를 보는데, Visibility Rendering은 그렇지 않아 고정 비용을 감당 가능하다면 이 점에서 이득을 본다는 것이다.

좋은 글이라고 느꼈고, 만약 따로 이 글에 대해서 글을 쓰게 된다면 번역 이상의 수준으로 뭔가를 써내려갈 수 있을지? 싶다.

오늘은 끝. 내일부터는 주말이다.

profile
Game, Graphics engineer

0개의 댓글