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 Melkert510March 08, 2013 12:41PM
Re: Question about edges Philippe Hurbain228March 08, 2013 11:07PM
Re: Question about edges Roland Melkert229March 09, 2013 11:11AM
Re: Question about edges Philippe Hurbain215March 09, 2013 11:25AM
Re: Question about edges Roland Melkert237March 09, 2013 12:23PM
Re: Question about edges Ben Supnik222March 09, 2013 08:18PM
Re: Question about edges Philippe Hurbain226March 09, 2013 10:53PM
Re: Question about edges Roland Melkert271March 10, 2013 11:35AM
Re: Question about edges Philippe Hurbain242March 10, 2013 12:00PM
Re: Question about edges Ben Supnik238March 10, 2013 04:11PM
Re: Question about edges Roland Melkert250March 10, 2013 04:32PM
Re: Question about edges Ben Supnik244March 10, 2013 07:31PM
Re: Question about edges Travis Cobbs233March 10, 2013 10:19PM
Re: Question about edges Ben Supnik223March 10, 2013 11:20PM
Re: Question about edges Tim Gould286March 10, 2013 11:40PM
Re: Question about edges Ben Supnik231March 11, 2013 11:52AM
Re: Question about edges Roland Melkert224March 11, 2013 01:31PM
Re: Question about edges Tim Gould232March 11, 2013 01:58PM
Re: Question about edges Roland Melkert224March 11, 2013 04:48PM
Re: Question about edges Tim Gould247March 11, 2013 04:57PM
Re: Question about edges Roland Melkert209March 11, 2013 06:02PM
Re: Question about edges Tim Gould222March 11, 2013 06:24PM
Re: Question about edges Travis Cobbs238March 11, 2013 10:12PM
Re: Question about edges Tim Gould246March 11, 2013 02:07PM
Re: Question about edges Ben Supnik270March 22, 2013 03:33PM
Re: Question about edges Tim Gould258March 22, 2013 03:44PM
Re: Question about edges Ben Supnik258March 22, 2013 04:48PM
Re: Question about edges Philippe Hurbain304March 23, 2013 01:49AM
Re: Question about edges Travis Cobbs221March 11, 2013 11:20AM
Re: Question about edges Roland Melkert238March 11, 2013 01:50PM
Re: Question about edges Roland Melkert205March 12, 2013 11:15AM
Re: Question about edges Ben Supnik219March 12, 2013 11:24AM
Re: Question about edges Roland Melkert208March 12, 2013 11:37AM
Re: Question about edges Travis Cobbs205March 09, 2013 10:57PM



Sorry, only registered users may post in this forum.

Click here to login