LDraw.org Discussion Forums

Full Version: Question about edges
You're currently viewing a stripped down version of our content. View the full version with proper formatting.
Pages: 1 2 3 4
Hi Roland,

I think the artifacts in the minifig-heads pic are induced by bugs and not by the limits of crease-angles, because there appears to be flat-shading errors at very low angles (e.g. nearly smooth sides). But it is also possible that the meshes aren't manifold or contain tiny cracks that throw your code off.

Could you post a screenshot of parts 6085.dat with the crease-angle smoothing? If I understand, it may look weirdly rounded due to the soft angles.

Also, how are you handling BFC? Does your algorithm assume BFC or cope with the case where the winding order of adjacent triangles is opposite (thus inducing opposite normals)?

cheers
Ben
This one?

[Image: smoothTest6085.png]

It looks fine even though it isn't bfc, but because all it's subparts are make it a non issue I think.

At the moment I assume a perfect library, so I handle it like everything is bfc Smile. I figured the angle stay more or less the same (because of the smallest angle result of dot products) and re normalizing will take care of most other problems resulting from non bfc meshes. I realize this isn't optimal but this is just an experimental implementation, so much room for improvement.

Low angle stuff is in deed a problem at the moment (using a whopping 60 degree threshold at the moment), but the nice thing is the edge lines will fix most of that problem (due to they optical illusion/misdirection they supply). Take a look at the slope bricks in the 5580 model for example.

I'm also hoping per pixel lighting will fix things even more by removing, the some times, weirdly shaped hot spots.
Hi Roland,

Yep - exactly what I expected with 6085: - a rounder-than-real life shading. :-)

I think you may find per pixel lighting makes the lighting effect _worse_...particularly if you use per pixel lighting for what it's really good for: shininess. (The problem with per-vertex lighting is that the fall-off from specular hilights is very steep, so the hilight tends to be contained entirely within one triangle. Once you have that 'sharp' hilight, the induced roundness will make lighting that really looks...well...round.) I hadn't noticed the error on the slope bricks because they look nice for the roundness of the lighting.

I just coded a smoothing algorithm (which, having not run it yet, I must assume works perfectly :-), but it takes the opposite approach: it uses only lines, rather than only angle, to do smoothing/creasing. I'll post some pics once I have it integrated, which may not be for a few days.

Having gone through the coding exercise, I think I can state a 'wish list' of assumptions about the library for a smoothing algorithm:

1. The bit-wise locations of all colocated vertices match exactly - that is, no floating point jitters between vertices that should touch.
2. All faces that form a smooth edge share the (bitwise) same coordinate values and the (bitwise) same transform stack. (In other words, if you want two sub-parts to mesh smoothly, they must be transformed in the same way.)
3. All parts are BFC valid. (Because of this, two adjacent faces will have edges going in opposite directions along the triangle.)
4. Any lines used to indicate a crease have a start and end point that (bitwise) matches the location of the corners of the triangle edge that they crease. (The line does not have to go in any particular direction, as it will always match one of the two triangle faces.)

This wish list allows apps that smooth meshes to avoid any epsilon math checks, computational geometry tests, etc. Smoothing behavior is (theoretically) predictable:
- every exactly manifold edge that doesn't have a manifold line is smooth.
- every exactly manifold edge that has a manifold line is creased.
- non-manifold edges are crease (or rather, aren't eligible for smoothing because they aren't even considered to be connected).

Cheers
Ben
Unfortunately, geting bit-wise floating point exactness is incompatible with using primitives (or even, to a certain extent, subfiles). Much of the time, curved primitives meet other curved primitives, but sometimes they have to meet part-level geometry, and when they do, the floating point values won't match. (Note: parts aren't allowed to use a bunch of floating point digits when specifying geometry). Also, even when primitives meet up with each other, they're only likely to have the same bit-wise floating point value if both primitives have the same transformation matrix. Otherwise, it's quite likely that round-off will result in slightly different values.
Hi Travis,

I smacked into that wall pretty hard with my own smoothing code tonight - 3963.dat uses a mix of hand-positioned faces and sub-part line rings to build the nozzles and the result is inexact vertices. The problem can be resolved in code by (1) also using a crease angle to catch the case where we 'lost' our line or (2) snapping the geometry to a grid.

Is there a minimum precision to the library (e.g. 1/16th of an LDU or something) that would allow programs to quantize part positions to catch such floating point problems without breaking small details? Or is there a minimum tolerance that library parts are checked to?

Cheers
Ben
While I realise bitwise matching is quickest, three subtractions, three squares, an addition, an absolute and a less than is hardly that much slower (the minimum needed for a distance comparison) for a quadratic scaling operation like comparison. And you can easily save work here too. As a scientific programmer of many years, I've learned the hard way that it's sometimes too easy to get caught up trying to save CPU in the easy bits, when there's other much better places to save it.

And you should never, ever, ever rely on floating point bitwise matches. The moment you add, subtract, multiply or divide you will inevitably run into errors. This even applies if you quantise, as 1/16+1e-15 and 1/16-1e-15 are only 2e-15 apart, but appear in different quanta. Furthermore you need to choose an integer that is large enough to cover the whole range, which would have to be at least 32bytes to be safe (since 16 bytes at a 1/16 bucket gives a range of -2048 to 2048).

Pseudo-code for efficient matching of points

Code:
# Calculate tolerance squared
TOL2=TOL*TOL
# Precompute distance squared for every vertex P(i) - O(N)
for i from 1 to noPoints
  P(i).r2=P(i).x*P(i).x+P(i).y*P(i).y+P(i).z*P(i).z
end
# Compare points - O(N^2)
for i from 1 to noPoints
  for j from (i+1) to noPoints
    # Check that points are close enough in the sphere - one abs, one <
    if abs(P(i).r2-P(j).r2)<TOL2
      # Now check their distance apart (squared) - 8 FLOPS, one <
      if (P(i).r2+P(j).r2-2*(P(i).x*P(j).x+P(i).y*P(j).y+P(i).z*P(j).z))<TOL2
        # Points are the same to TOL
        SetPointsSame(i,j)
      endif
    endif
  endfor
endfor
The Numeric Precision and Format section of the File Format Restrictions for the Official Library specifies that parts and non-scalable primitives are not allowed to use more than 3 decimal places, and scalable primitives aren't allowed to use more than 4 decimal places. It's worth noting, however, that just because that level or precision is allowed, it doesn't mean that relying on it will work.
Hi Tim,

My hope for 'bitwise sameness' isn't so that we can use fast bit comparisons - it is so that we can have transitivity of equal points. I think your code, by pre-processing, may do that; what does "SetPointsSame" do?

For example, if 3 vertices A, B, and C are near each other so that the distance from A to B is < TOL and the distance from B to C is < TOL but the distance from A to C is > TOL, are all three points the same? If not, do we say that A == B and B == C but A != C? :-)

My smoothing algorithm assumes transitivity of equality for point locations, so a fuzzy match has to be transitive too. As an experiment, I implemented a simple and stupid grid-snap, which does result in transitive behavior - in the case above, if A, B, and C all snap together, then A == B == C. If the snap separates B and C but keeps A and B together then A == B, A != C, B != C and things are still sane.

As an aside, OpenGL (maybe D3D too??) has some pretty specific rules about invariance, water tight meshes, and cracks; if the part library has bit-wise exact transform data and point locations then there will be no mesh cracks, but if that isn't true then I think there could be rendering artifacts..that's why I thought there might be some hope of having bitwise comparable data.* :-) The case that hosed me was a line and triangle not having the same bitwise definitions, which isn't surprising; no one needs watertight rendering between a tri and a line.

cheers
Ben

* For X-Plane we basically require bit-wise exact vertices to get manifold rendering in our model files, because the graphics cards require it...but the output is coming from 3-d modeling programs that more or less do this for free. Thus we ensure the same mathematical function is applied on the same input bits, so while we don't know what the floating point output is, we know it's the same every time.
I've been using the next piece of code for years to do 'fast' duplicate point detection in my renderers.

Code:
kX=(int)floor(v.x*appDef_decCntMul);
kY=(int)floor(v.y*appDef_decCntMul);
kZ=(int)floor(v.z*appDef_decCntMul);
v.x=(GLfloat)kX/appDef_decCntMul;
v.y=(GLfloat)kY/appDef_decCntMul;
v.z=(GLfloat)kZ/appDef_decCntMul;

v.x etc is still float but it's contents should now be bit wise comparable while using 4 decimal precision on all part level transformed coordinates.

I also stuff this in a hash list to speed up look ups.

This has worked pretty well for years (reducing vertex count by ~60% when only using positional data)
Ben Supnik Wrote:Yep - exactly what I expected with 6085: - a rounder-than-real life shading. :-)

Yes but I kinda expected that using a 60 degree threshold. Although this part seems to be very round indeed, I didn't realize it because I never seen this part in real life or use it in modelling etc Smile

When I lower the threshold to 30 degree (6085 becomes square then) it messes up (much more often used) parts like the antenna or loudspeaker. So in the end I rather have these 'rare' parts rendering wrong.


Ben Supnik Wrote:I think you may find per pixel lighting makes the lighting effect _worse_...particularly if you use per pixel lighting for what it's really good for: shininess. (The problem with per-vertex lighting is that the fall-off from specular hilights is very steep, so the hilight tends to be contained entirely within one triangle. Once you have that 'sharp' hilight, the induced roundness will make lighting that really looks...well...round.) I hadn't noticed the error on the slope bricks because they look nice for the roundness of the lighting.

It's probably better to first get the smoothing thing to work at an acceptable level before I start playing with my own lighting model then.


Ben Supnik Wrote:Having gone through the coding exercise, I think I can state a 'wish list' of assumptions about the library for a smoothing algorithm:

1. The bit-wise locations of all colocated vertices match exactly - that is, no floating point jitters between vertices that should touch.
2. All faces that form a smooth edge share the (bitwise) same coordinate values and the (bitwise) same transform stack. (In other words, if you want two sub-parts to mesh smoothly, they must be transformed in the same way.)
3. All parts are BFC valid. (Because of this, two adjacent faces will have edges going in opposite directions along the triangle.)
4. Any lines used to indicate a crease have a start and end point that (bitwise) matches the location of the corners of the triangle edge that they crease. (The line does not have to go in any particular direction, as it will always match one of the two triangle faces.)

Like Travis wrote I don't think 1 and 4 are realistic demands, not only from a technical point but it won't be fair to the part authors/reviewers they already have enough to nit pick over I think Smile

3 Is a very realistic demand, and the current library is well on it's way on this. So maybe if some parts smooth weirdly the first helping hand thing part authors can do would be to make the part in question bfc.

4 Is pretty much the point I start the thread for (excluding the bitwise part), I'm not sure how many part will smooth weird when assuming this while it isn't the case. Depending on the amount of parts I might be fixable quite easily for some of the advanced part authors.

I'm going to implement a very rough version of the number 4 base edge handling in my code next weekend or so, maybe this in combination whit 60 degree approach will result in e.g 99% correct smoothing. I could then compile a list of 'problem' parts, that would benefit the most from bfc/nr 4 corrections.

Or maybe someone else has ideas for a completely different approach?
Pages: 1 2 3 4