March 10, 2013 11:40PM Website Administrator Steering Committee Member LDraw Part Author/Reviewer Registered: 3 years agoPosts: 1,111
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

```# 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
```

Edited 6 time(s). Last edit at 2013-03-10 11:49PM by Tim Gould.
SubjectAuthorViewsPosted
Roland Melkert578March 08, 2013 12:41PM
Philippe Hurbain258March 08, 2013 11:07PM
Roland Melkert263March 09, 2013 11:11AM
Philippe Hurbain247March 09, 2013 11:25AM
Roland Melkert263March 09, 2013 12:23PM
Ben Supnik246March 09, 2013 08:18PM
Philippe Hurbain252March 09, 2013 10:53PM
Roland Melkert304March 10, 2013 11:35AM
Philippe Hurbain274March 10, 2013 12:00PM
Ben Supnik267March 10, 2013 04:11PM
Roland Melkert280March 10, 2013 04:32PM
Ben Supnik281March 10, 2013 07:31PM
Travis Cobbs258March 10, 2013 10:19PM
Ben Supnik251March 10, 2013 11:20PM
Tim Gould329March 10, 2013 11:40PM
Ben Supnik255March 11, 2013 11:52AM
Roland Melkert254March 11, 2013 01:31PM
Tim Gould260March 11, 2013 01:58PM
Roland Melkert250March 11, 2013 04:48PM
Tim Gould278March 11, 2013 04:57PM
Roland Melkert236March 11, 2013 06:02PM
Tim Gould257March 11, 2013 06:24PM
Travis Cobbs262March 11, 2013 10:12PM
Tim Gould270March 11, 2013 02:07PM
Ben Supnik301March 22, 2013 03:33PM
Tim Gould285March 22, 2013 03:44PM
Ben Supnik295March 22, 2013 04:48PM
Philippe Hurbain349March 23, 2013 01:49AM
Travis Cobbs244March 11, 2013 11:20AM
Roland Melkert267March 11, 2013 01:50PM
Roland Melkert229March 12, 2013 11:15AM
Ben Supnik245March 12, 2013 11:24AM
Roland Melkert232March 12, 2013 11:37AM
Travis Cobbs228March 09, 2013 10:57PM

Sorry, only registered users may post in this forum.