Welcome! Log In Create A New Profile

Advanced
Re: Question about edges
March 10, 2013 11:40PM
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
Question about edges Roland Melkert542March 08, 2013 12:41PM
Re: Question about edges Philippe Hurbain237March 08, 2013 11:07PM
Re: Question about edges Roland Melkert243March 09, 2013 11:11AM
Re: Question about edges Philippe Hurbain227March 09, 2013 11:25AM
Re: Question about edges Roland Melkert247March 09, 2013 12:23PM
Re: Question about edges Ben Supnik235March 09, 2013 08:18PM
Re: Question about edges Philippe Hurbain238March 09, 2013 10:53PM
Re: Question about edges Roland Melkert282March 10, 2013 11:35AM
Re: Question about edges Philippe Hurbain256March 10, 2013 12:00PM
Re: Question about edges Ben Supnik253March 10, 2013 04:11PM
Re: Question about edges Roland Melkert264March 10, 2013 04:32PM
Re: Question about edges Ben Supnik261March 10, 2013 07:31PM
Re: Question about edges Travis Cobbs242March 10, 2013 10:19PM
Re: Question about edges Ben Supnik234March 10, 2013 11:20PM
Re: Question about edges Tim Gould300March 10, 2013 11:40PM
Re: Question about edges Ben Supnik238March 11, 2013 11:52AM
Re: Question about edges Roland Melkert236March 11, 2013 01:31PM
Re: Question about edges Tim Gould244March 11, 2013 01:58PM
Re: Question about edges Roland Melkert234March 11, 2013 04:48PM
Re: Question about edges Tim Gould255March 11, 2013 04:57PM
Re: Question about edges Roland Melkert217March 11, 2013 06:02PM
Re: Question about edges Tim Gould234March 11, 2013 06:24PM
Re: Question about edges Travis Cobbs247March 11, 2013 10:12PM
Re: Question about edges Tim Gould257March 11, 2013 02:07PM
Re: Question about edges Ben Supnik282March 22, 2013 03:33PM
Re: Question about edges Tim Gould272March 22, 2013 03:44PM
Re: Question about edges Ben Supnik277March 22, 2013 04:48PM
Re: Question about edges Philippe Hurbain327March 23, 2013 01:49AM
Re: Question about edges Travis Cobbs228March 11, 2013 11:20AM
Re: Question about edges Roland Melkert248March 11, 2013 01:50PM
Re: Question about edges Roland Melkert213March 12, 2013 11:15AM
Re: Question about edges Ben Supnik233March 12, 2013 11:24AM
Re: Question about edges Roland Melkert215March 12, 2013 11:37AM
Re: Question about edges Travis Cobbs216March 09, 2013 10:57PM



Sorry, only registered users may post in this forum.

Click here to login