Point matching Re: Question about edges

[Tim Gould]

I'm going to split this off as a new thread since the old one is unwieldy...

When we develop a list of points (via check and snap), there will be (hopefully only a few) remaining points that have not been snapped to each other and remain with only _one_ tri or quad accessing them. We can exploit this as these points must be:

• Part of a t-junction
  
• A point that has not been snapped properly
  
• An edge point (but this should be illegal in an LDraw part)
  

There is absolutely no other reason for a point not the be shared amongst at least two tris/quads. We can store the number of facet prims accessing the point via a simple count on the list of points.

So here's the deal:

Code:

SnapPoints

foreach Point not in TwoTris/Quads
  # Check if the point is part of a t-junciton
  If CheckForTJunction then  SplitTJunction

  # Check for nearby points with a larger (eg. 0.05) tolerance
  DoNearbyCheck(TOLBIG)
  SnapToPoints
endfor

If, at the end of this code, there are points that are still not shared then the part can probably be flagged as bad.

Tim

[Philippe Hurbain]

An edge point (but this should be illegal in an LDraw part)

Could be a point inside interpenetrating surfaces.

[Tim Gould]

Hmmm. I'm not exactly sure what you mean. But trust you completely to have thought of something I've missed

Do you have an example?

Tim

[Michael Heidemann]

That is exactly the way Gapfinder is working (http://ldraw.heidemann.org/index.php?page=gapfinder) (except of snapping before).

[Michael Heidemann]

Not a partnumber at the moment, but there are many parts that uses primitives (mostly curved) that builds the shape, but not truncated as needed (as that would eliminate the build in smoothing for that primitives) and the egdeline is just generated by isecalc. The remaining part of the primitive just pokes into the inside of the part and is never visible except at parts that can also occur as transparent. Therefore at those parts this technic should be avoided.

[Tim Gould]

Thanks, gotcha. I've even done that myself and it is of course allowable in parts.

Tim

[Ben Supnik]

Hi Guys,

Tim, I'm not sure I understand the algo: are you saying that you can optimize the number of T junction searches by ignoring already-shared points? I think this would not be the case when two properly-shared meshes are connected to each other without proper T-junction removal.

Or did I misunderstand the intent here?

For Michael and Philippe's case, I've been assuming that I will not try to fix T junctions that cannot participate in smoothing because they are not coplanar with a surface, on an edge, or the angle of the two surfaces in question is larger than the global crease angle.

In terms of permformance, I think that only finding T's "on a line" will give a good speed-up if a spatial index is used; I'll post back when I have this running. Finding interpenetration would be much slower (you have to query 'everywhere') but isn't necessary for smoothing.

cheers
Ben

[Roland Melkert]

Do you mean parts like 32495.dat?

These are giving me sleepless nights at the moment Smoothing trips over them, and doing T-Junction fixes makes it even worse because it's actually trying to join the individual segments, at places where polygon edges happen to almost toch one of the 'grid' indexed vertices.

This also happens on e.g. 1x1 round plates. But with them it isn't noticeable.

[Roland Melkert]

In terms of permformance, I think that only finding T's "on a line" will give a good speed-up if a spatial index is used

Fixing only stuff on edges won't work, take for example the standard grin minifig head, it's whole face is edgeless and this is exactly the place that needs to be tj-fixed.

On the other hand I have nearly perfect TJ-Fixing running at the moment but the smoothing results on detailed curved surfaces are still a mess. I'm going to fix the non bfc awareness today, but I doubt it will help much (judging from the bfc-ed minifg heads).

[Michael Heidemann]

Yes, that is a good example

[Ben Supnik]

Sorry, "on a line" is totally wrong -- "on a triangle edge" is the right term - that is, you only have to search the subset of lines formed by two points that are already connected by a triangle, and you only have to search them if smoothing against that triangle is a possibility, if you're willing to leave 'creased' T's in place.

[Ben Supnik]

Hi Roland,

I'm hoping to let part authors 'fix' 32495.dat and not try to smooth it myself. :-) :-)

But for the 1x1 round plate, I'm not sure what the problem is from a smoothing perspective. It has T's but none of them occur over smooth regions. Or did I miss something subtle going on with the part?

Cheers
Ben

[Roland Melkert]

There is no problem with those parts, but I'm TJ-Fixing the entire universe at the moment

So it finds the stud bottom edge touching the triangle edges making up the top of the (stud less) plate.

Also I don't know if you have your TJ stuff running yet but I'm running into a triangulation problem under certain circumstances. For example this:

Code:

C x-----x B
  |     |
D x     |
  |     |
E x     |
  |     |
F x-----x A

Code:

C x-----x B
  |    /|
D x   / |
  |  /  |
E x /   |
  |/    |
F x-----x A

Where c d e and f all lie on a line and thus no visible triangles are added. All goes fine when the winding is the other way around, but it happens fairly often. So yet another exception to add to the ever increasing list of things to improve.

For a quick fix I added a additional center point and added triangles to all others from that, but it's overkill for most of the splits. So now I'm searching for a efficient triangulation function that's best suited for the LDraw poly's.

[Roland Melkert]

I've fixed the above problem, and finished a usable version of TJ-Fixing in LDCad.

But I must say it's very dissapointing, many parts are actually looking worse. Like 32495.dat Only a handfull of parts look (slightly) better then when only basic smoothing is enabled.

In the end I'm thinking it's just not worth all the effort (loading times). Especially when you take in account it's bloating most parts up in vertex count with no visual change what so ever.

So I'm heavily leaning towards #ifdef'ing it all out for now, leaving the tj mass correction stuff to the part authors and or mass correction scripts.

[Ben Supnik]

Hi Roland,

I only got triangle detection working - subdivision will have to wait for another free weekend. Given the assumption that the input polygon is convex, and assuming we know all splits up front (e.g. gather first, split later) I think I can fix the triangulation issue by 'cutting off' the sharpest corner and recursing, although the resulting triangulation may look a bit silly. I think I'll have to change from equal weight to angle weight to get the normals to not be highly distorted.

But I know what you mean re: diminishing results..the big wins are up front in smoothing most well-made simple parts. And when you look at how well a textured mini-fig head works vs. a face that is built out of triangles, it makes the whole effort seem a bit pyrrhic.

cheers
ben

[Roland Melkert]

How do you mean angle based averaging? Wouldn't that cancel out the smoothing.

Here are my results, so far:



One thing I'm thinking about is splitting (all) triangles evenly so you get a better spread wireframe grid, hopefully resulting in better normals. But I'm not sure if I'm going to try that anytime soon.

[Ben Supnik]

Hi Roland,

My speculation is that the relative weight of each face normal considered at a vertex V should be proportional to the angle of the triangle at V. So....

Code:

A---B---E
|  /|  /|
| / | / |
|/  |/  |
C---D---F

For the smoothing of vertex B (which is a blend of the normals of ABC, SPAM CONTENT, and BED) we would give ABC and SPAM CONTENT a weight of "45" each, and a weight of BED "90" - that is, BED's normal acts as much as ABC and SPAM CONTENT's combined.

cheers
Ben

[Roland Melkert]

that is, BED's normal acts as much as ABC and SPAM CONTENT's combined.

I'm kinda doing this already I only average the unique normals at a certain vertex. So I would be using only bed and abc in your example.This because the uneven weighting was visible in all quad based primitives.

But this made me think, maybe I need to play with the threshold of those uniqueness tests.

[Ben Supnik]

Hi Roland,

I was able to hack in weighting and I can confirm: if you use all incident smooth vertices but weight them by their angle span, you get correct normals for triangulated primitives - that is, the specular hilite on a stud will not be 'skewed' on the diagonal if you triangulate quads.

cheers
ben

[Roland Melkert]

Great, I'll have to try that too then.

It will be slower though, having to calculate all the edges (again, might buffer them from the tjtests) and do full 0..360 deg angle (dot and cross operations instead simple acos dot ) determination on them.

And all this just when I was thinking to leave smoothing as it is, and to pick up the 'normal' activities for LDCad 1.2 this weekend.

[Ben Supnik]

Hi Roland,

Hrm - I get the angle -almost- for free...my vertices and faces are linked in the internal data structure, so the weighting cost is the cost of:
- calculating the normalized vector to the adjacent points on the polygon (the vertex "object" can be found by ptrs easily)
- calculating the dot product of those vectors
- applying acos to get a radian angle weight.

I don't need to normalize - after all, the angles going into the vertex may not sum up to 360 or 2pi. I just use the relative weights and renormalize the normal at the end, something I would have had to do anyway.

Adding the weighting coefficient only slowed smoothing by 5% - that's a pretty light cost to pay to get the specular hilights looking right when a face is/must be triangulated. :-)

cheers
Ben

[Roland Melkert]

I just realized I was over thinking it, you won't need 360 degree information (the main reason being triangles can't have >180 deg angles )

So it would have about the same impact you described in my code too.

[Roland Melkert]

Well i did a quick test, and I'm getting little to no visual change (compared to averaging unique normals) with or without TJ-Fixing enabled.

Could it be this only effects/helps per pixel lighting like you are using ?

[Ben Supnik]

Yes - that's very possible. In fact, to _really_ see the importance of angle-weighting, I needed to turn on not just per pixel lighting but per-pixel _specularity_, which really increases the sensitivity of your normal vectors.