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 Melkert449March 08, 2013 12:41PM
Re: Question about edges Philippe Hurbain198March 08, 2013 11:07PM
Re: Question about edges Roland Melkert189March 09, 2013 11:11AM
Re: Question about edges Philippe Hurbain173March 09, 2013 11:25AM
Re: Question about edges Roland Melkert198March 09, 2013 12:23PM
Re: Question about edges Ben Supnik192March 09, 2013 08:18PM
Re: Question about edges Philippe Hurbain196March 09, 2013 10:53PM
Re: Question about edges Roland Melkert227March 10, 2013 11:35AM
Re: Question about edges Philippe Hurbain200March 10, 2013 12:00PM
Re: Question about edges Ben Supnik204March 10, 2013 04:11PM
Re: Question about edges Roland Melkert211March 10, 2013 04:32PM
Re: Question about edges Ben Supnik201March 10, 2013 07:31PM
Re: Question about edges Travis Cobbs193March 10, 2013 10:19PM
Re: Question about edges Ben Supnik184March 10, 2013 11:20PM
Re: Question about edges Tim Gould244March 10, 2013 11:40PM
Re: Question about edges Ben Supnik203March 11, 2013 11:52AM
Re: Question about edges Roland Melkert197March 11, 2013 01:31PM
Re: Question about edges Tim Gould202March 11, 2013 01:58PM
Re: Question about edges Roland Melkert197March 11, 2013 04:48PM
Re: Question about edges Tim Gould214March 11, 2013 04:57PM
Re: Question about edges Roland Melkert176March 11, 2013 06:02PM
Re: Question about edges Tim Gould189March 11, 2013 06:24PM
Re: Question about edges Travis Cobbs210March 11, 2013 10:12PM
Re: Question about edges Tim Gould212March 11, 2013 02:07PM
Re: Question about edges Ben Supnik227March 22, 2013 03:33PM
Re: Question about edges Tim Gould218March 22, 2013 03:44PM
Re: Question about edges Ben Supnik207March 22, 2013 04:48PM
Re: Question about edges Philippe Hurbain264March 23, 2013 01:49AM
Re: Question about edges Travis Cobbs191March 11, 2013 11:20AM
Re: Question about edges Roland Melkert207March 11, 2013 01:50PM
Re: Question about edges Roland Melkert176March 12, 2013 11:15AM
Re: Question about edges Ben Supnik193March 12, 2013 11:24AM
Re: Question about edges Roland Melkert179March 12, 2013 11:37AM
Re: Question about edges Travis Cobbs177March 09, 2013 10:57PM



Sorry, only registered users may post in this forum.

Click here to login