smoothing algorithm without quads

[Nicola]

I'm upgrading my webgl renderer program Brigl to work with the latest version of Three.js (the 3d engine i use).
I've found a bitter suprise: they deprecated the Quad primitive (Face4). Now the whole library only deals with triangles (Face3).
I relied to quads for my smoothing algorithm, and everything broke

So my algorithm worked like this: if two faces have a conditional line on the common edge, that means the faces should be smoothed. Smoothing means averaging all normals (per-vertex face normals) at each end of the conditional lines.

I've adjusted for the Face4 removal in the simplest way: by adding two Face3 composing the quad. But now it happends that if i have two quad connected by a condline, only two of the four triangles are affected, the other two staying unsmoothed, effectively creating a zigzag pattern. You can see it here:



Do you have any idea on how i could correct this issue? I tried to keep track of triangle pairs forming quads, but i couldn't manage to restore a working solution.
Eventually i could move all smoothing code to BEFORE generating the 3d mesh, that is while still working with plain ldraw objects (quads and tri), but it looks like an huge amount of work..

[Ben Supnik]

Hi Nicola,

There was a lengthy discussion of smoothing a while ago on the forums:

http://forums.ldraw.org/showthread.php?tid=8595,8688

...I ended up implementing smoothing in BrickSmith based on the discussion. So a few things:

1. Does your original code handle smoothing of rounded surfaces made of triangles too or only quads? The algorithm that I ended up using uses triangles, and thus decomposing the quads is not a problem.

2. The Bricksmith mesh smoother is a straight cross-platform pure C API, and it translates lines, tris and quads into indexed GL meshes - I think you could probably just use it under BrickSmith's open source license.

http://sourceforge.net/p/bricksmith/code...shSmooth.h
http://sourceforge.net/p/bricksmith/code...shSmooth.c

3. For modifying your code to handle this case, I think there are two things you _must_ do:

- You must be prepared to smooth a vertex by an _arbitrary_ number of incident triangles - in other words, think of all triangles touching vertex V as a fan - every one of them may contribute to smoothing, and there can easily be more than 4 - there will be 6 in the case of quads (because of the necessary split) or more for other LDraw shapes.

- When you find all incident triangles, you must weight the averaging of the normals by the _angle_ of the triangle at vertex V. If you do not do this, the direction of the normal will be biased and you will get a smooth mesh, but a smooth mesh whose lighting appears to run at an angle along the split line of the quads.

Finally, just a quick note: the BrickSmith code matches LDView in that it smoothes any edge that is not sharp and does not have a line - it does not require conditional lines to induce smoothing. My thinking on this was: you can easily create a renderer that looks good without rendering conditional lines at all if you are doing 3-d shaded solid drawing. So I wanted to build a smoothing algorithm that would not require conditional lines since they were already unnecessary for the rest of BrickSmith.

I've been meaning to write up a document based on the discussion - people covered fixing the loss of precision due to rotation matrices, detecting and repairing T junctions, etc.

Cheers
Ben

[Nicola]

Hi Nicola,

There was a lengthy discussion of smoothing a while ago on the forums:

http://forums.ldraw.org/showthread.php?tid=8595,8688

Thanks, i'll read it asap!

1. Does your original code handle smoothing of rounded surfaces made of triangles too or only quads? The algorithm that I ended up using uses triangles, and thus decomposing the quads is not a problem.

It smoothed both, as long as they have conditional lines attached.

2. The Bricksmith mesh smoother is a straight cross-platform pure C API, and it translates lines, tris and quads into indexed GL meshes - I think you could probably just use it under BrickSmith's open source license.

http://sourceforge.net/p/bricksmith/code...shSmooth.h
http://sourceforge.net/p/bricksmith/code...shSmooth.c

Unfortunately i'm working in javascript and i don't think there's a sane way to include c code. That's very interesting anyway, thanks!

3. For modifying your code to handle this case, I think there are two things you _must_ do:

- You must be prepared to smooth a vertex by an _arbitrary_ number of incident triangles - in other words, think of all triangles touching vertex V as a fan - every one of them may contribute to smoothing, and there can easily be more than 4 - there will be 6 in the case of quads (because of the necessary split) or more for other LDraw shapes.

- When you find all incident triangles, you must weight the averaging of the normals by the _angle_ of the triangle at vertex V. If you do not do this, the direction of the normal will be biased and you will get a smooth mesh, but a smooth mesh whose lighting appears to run at an angle along the split line of the quads.

Finally, just a quick note: the BrickSmith code matches LDView in that it smoothes any edge that is not sharp and does not have a line - it does not require conditional lines to induce smoothing. My thinking on this was: you can easily create a renderer that looks good without rendering conditional lines at all if you are doing 3-d shaded solid drawing. So I wanted to build a smoothing algorithm that would not require conditional lines since they were already unnecessary for the rest of BrickSmith.

I've been meaning to write up a document based on the discussion - people covered fixing the loss of precision due to rotation matrices, detecting and repairing T junctions, etc.

Cheers
Ben

Ok i think i got the main idea. So your algorithm completely ignore conditional lines? If so i think you're basing on some theresold angle to decide whethere to smooth or not, am i right? Or you're using some other tecnique?

[Ben Supnik]

Oops - sorry - yeah, that C code pretty useless from Javascript. :-)

The algorithm that Travis and I use smooths every seam (connection between two polygons) that are both:

- Not too sharp of an angle and
- Do not have a line primitive on the seam.

So both lines and sharp angles break the smoothing.

Two last performance notes:

- the C code depends on using index structures to do the searching for common edges. If the "triangle soup" was not indexed, this step would be O(N^2), which would be way too slow for parts like base plates and some of the more complex animals.

- In order for the index to work, vertices that have near-exact coordinates are snapped to get exact coordinates. This has two advantages: once the coordinates are snapped, comparisons don't require floating point math (and buckets of identical vertices can be indexed together) and it also helps prevent cracking and gaps in the mesh that would otherwise be introduced by imperfect matrix transforms.

cheers
Ben

[Roland Melkert]

Can't you just keep track of the triangle pairs that used to be quads and sync their normals when needed?

[Steffen]

anway it should be not too difficult to translate the C code to JavaScript...