LDraw.org Discussion Forums
T-Junctions re-visited - Printable Version

+- LDraw.org Discussion Forums (https://forums.ldraw.org)
+-- Forum: Models and Parts (https://forums.ldraw.org/forum-18.html)
+--- Forum: Parts Authoring (https://forums.ldraw.org/forum-19.html)
+--- Thread: T-Junctions re-visited (/thread-8595.html)

Pages: 1 2 3 4 5 6 7 8 9


T-Junctions re-visited - Travis Cobbs - 2013-03-12

The recent activity regarding automatic calculation of surface normals in order to produce smooth rendering in other programs (similar to how LDView has behaved for a long time, but via a different, better algorithm) has made me investigate places where LDView's current smoothing is failing, and this has led to this post, a revisit to the subject of T-Junctions.

The point is that, while I never thought about it before, T-Junctions prevent smooth shading from working. If you don't know what T-Junctions are, please see this article. I just updated that article to point out that T-Junctions on curved surfaces prevent smoothing algorithms from working on those surfaces.

Since, as far as I know, this has never been mentioned before, I don't think parts authors in the past have had any particular impetus to go to the significant extra work needed to avoid T-Junctions on curved surfaces. However, given that they prevent just about any reasonable smoothing algorithm from functioning, I think they should be avoided more strongly.

If someone can come up with a simple smoothing algorithm that works with T-Junctions, I will gladly stand corrected, but any such algorithm would also require per-pixel lighting in order to work with T-Junctions, and I think even with per-pixel lighting, the algorithm would end up being downright nasty.

The only alternative I can think of is to detect the T-Junctions during file loading, and automatically split the geometry involved. That doesn't seem very easy either, though. Does anyone know of a good, fast algorithm to do this? If so, we could potentially recommend that in all LDraw renderers, and remove the recommendation against T-Junctions in parts entirely.


Re: T-Junctions re-visited - Tim Gould - 2013-03-12

Hi Travis,

I'm not sure what the hardest stage is, but if one computes all valid edges (on triangles or quads), then one can efficiently check if points lie within lines as follows:
Code:
# O (N_Edges N_Points)
for I,J in Edges
  for K in Points
    DIJ=Dist(P(I),P(J))
    DIK=Dist(P(I),P(K))
    DJK=Dist(P(I),P(K))
    if (abs(DIJ-(DIK+DJK))<TOL)
      # K is on the line between I & J
      PushLineTrio(I,J;K)
    endif
  endfor
endfor

After that, one needs to split all tris and quads that have a point K in the line trios.
Code:
# O(N_LineTrios log(N_LineTrios))
SortLineTriosBy(I,J)
# O(N_LineTrios)
foreach I,J in LineTrios # Count on I,J first to split along a line
  if (NumberLineTriosWith(I,J) is 1)
    SplitIJAtKTri/Quad # For quads there are two options here, perhaps split into three tris here rather than trying to choose
  else
    SplitIJAtMultipleKTri/Quad # Hard
  endif
endfor

Code:
routine SplitIJatKTri(I,J;K)
foreach Tri with I,J as an edge # This is slow but won't be called very often
  NewTri(I,K,Tri.L)
  NewTri(J,K,Tri.L)
  DeleteTri(I,J,Tri.L)
endfor

routine SplitIJatMultipleKTri(I,J;KS)
foreach Tri with I,J as an edge # This is slow but won't be called very often
  NewTri(I,KS(1),Tri.L)
  for IK in 1..(NKS-1)
    NewTri(KS(IK),KS(IK+1),Tri.L)
  endfor
  NewTri(KS(NKS),J,Tri.L)
  DeleteTri(I,J,Tri.L)
endfor

routine SplitIJatKQuad(I,J;K)
# Quad has I,J,L,M going around
foreach Quad with I,J as an edge # This is slow but won't be called very often
  NewTri(I,K,Tri.M)
  NewTri(J,K,Tri.L)
  NewTri(K,Tri.L,Tri.M)
  DeleteQuad(I,J,Quad.L,Quad.M)
endfor

What this does may not deal with well is quads with splits on multiple edges. That could perhaps be checked for if results from the above suck.

Tim


Re: T-Junctions re-visited - Ben Supnik - 2013-03-12

Hi Guys,

If I may jump on the "T junctions are evil" bandwagon:

- If you have a smooth surface, you probably don't have lines covering the edges. But with a T junction, the GPU may leave a 'crack' in the texturing of the surface. So T junctions are a general modeling no-no for this reason even when smoothing isn't considered.

- In order for the lighting to match at the T point, you have to ensure that the calculated normal of the vertex touching the triangle midpoint is the same interpolated normal from the two edges. This pretty much goes against what a smoothing algorithm is trying to do (calculate a normal based on the incident faces).

Even if we can band-aid around T junctions for smoothing, I do not think we should: there exists a way to author the part to fix this (subdivide the 'long' triangle or quad into two triangles or quads at the T point) that will result in un-cracked, smoothly shaded meshes.

I think it would be more productive for developers to write tools to detect and/or repair parts that have T junctions than to code around it in smoothing code; in the later case we endure the development cost for every LDraw app going forward, the performance cost of the more complex algorithm, and the lighting artifacts of having to pick weird normals at every T junction to avoid discontinuities.

I apologize for sounding like a broken record/big fat jerk, but... :-)

...the rules for mesh construction for 3-d graphics and games are already solved for the rest of the 3-d modeling world...we should match the graphics industry's rules for "water tight" meshes; the result will be better visual results and better performance.

Cheers
Ben


Re: T-Junctions re-visited - Roland Melkert - 2013-03-12

There t-junctions are a big party spoiler indeed, Tim's detection code could probably be done fast enough on small parts, but on the bigger ones it could take ages, also on most parts it isn't even needed.

Instead of brute forcing everything, we should only apply this on problem parts like the minifig heads (by means of a meta hint). This would keep loading times acceptable even on lesser hardware.

I posted an example on using a meta in this message:

[url=http://forums.ldraw.org/showthread.php?tid=8597&pid=8597#pid8597][/url]

The same meta could be used to indicate the need of t-junction removal.


Re: T-Junctions re-visited - Roland Melkert - 2013-03-12

I agree, but there is the small issue of editing over 5000 parts Smile

So if we could do 'simple' real time fixing, instead of waiting on the library to catch up, it's the preferred way of doing things at the moment. We could always get rid of the real-time correcting once the library does catch up.


Re: T-Junctions re-visited - Ben Supnik - 2013-03-12

Hi Roland,

I seem to keep running into "but we can't edit 5000 parts". :-(

My concern about simple real-time fixing is that having these algorithms alive in code is a very different proposition from having their results saved to a file. If we decide the algorithm does a bad job, revising _all_ apps is nearly impossible. But re-processing library files is possible.

The library is big, but it's not homogenous: some parts are way more important than others in terms of frequency of use, and some won't even need processing.

Are there specific authoring tools that I could write that would make the parts library more accessible? For example, we could write code to detect T junctions, or even code to detect T junctions that probably _should_ have been smooth shaded, or even code that only subdivides those T junctions that affect smooth shading. (The goal with this is minimal editing of the parts while solving the maximum smoothing problems.)

I am not afraid to write big complex slow algo code to solve these things -- I just hate to see it in BrickSmith's part loader. :-(

cheers
Ben


Re: T-Junctions re-visited - Roland Melkert - 2013-03-12

Thing is large changes have to go through the reviewing process, which is currently a bottle neck even for new parts.

Chris Dee is currently the only one who can 'sneak' stuff through without rereviewing, so maybe if you write a very smart t-junction removal script he could apply it to the whole library and roll it out in the next release if he finds the results acceptable.


Re: T-Junctions re-visited - Ben Supnik - 2013-03-12

Hi Roland,

That is sort of my idea - apply the review and quality control to the tool - carefully check some of its output, design it to create sane output, and then use it to batch-apply to parts. I feel bad asking part authors to manually do such tedious work!

cheers
ben


Re: T-Junctions re-visited - Allen Smith - 2013-03-12

The "have to go through the reviewing process" bit is a purely artificial requirement. It exists because some people are afraid that subverting a very complicated, very slow review process will somehow damage the quality of the part library. In individual instances, I'm sure the concern is well-founded. But on the whole, I feel the policy has demonstrably had the exact opposite effect. Simple problems which could have been algorithmically corrected remain enshrined (bow-tie quads, for example). Authors create parts, then don't even bother submitting them to the Part Tracker because it's a waste of their time. Contributors fade away. New ideas are almost invariably dead on arrival.

I would like to see, at the very least, an expansion of admin power on the part tracker and a recognition that some changes can be made in bulk without individual review of every single line.

Reflexively shooting down an idea like this is just unhealthy. We should be fixing this administrative problem before talking about software client workarounds.

Allen


Re: T-Junctions re-visited - Michael Heidemann - 2013-03-13

I like this idea very much. If we would have code that can fix the T-junction I am very interesting in integrating that code into DATHeader.

Regarding the bulk change of files in the library (I like that idea), I think we need to address this change in the !History line due to our license.