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 Melkert543March 08, 2013 12:41PM
Re: Question about edges Philippe Hurbain238March 08, 2013 11:07PM
Re: Question about edges Roland Melkert245March 09, 2013 11:11AM
Re: Question about edges Philippe Hurbain231March 09, 2013 11:25AM
Re: Question about edges Roland Melkert248March 09, 2013 12:23PM
Re: Question about edges Ben Supnik235March 09, 2013 08:18PM
Re: Question about edges Philippe Hurbain240March 09, 2013 10:53PM
Re: Question about edges Roland Melkert284March 10, 2013 11:35AM
Re: Question about edges Philippe Hurbain258March 10, 2013 12:00PM
Re: Question about edges Ben Supnik253March 10, 2013 04:11PM
Re: Question about edges Roland Melkert265March 10, 2013 04:32PM
Re: Question about edges Ben Supnik263March 10, 2013 07:31PM
Re: Question about edges Travis Cobbs246March 10, 2013 10:19PM
Re: Question about edges Ben Supnik236March 10, 2013 11:20PM
Re: Question about edges Tim Gould302March 10, 2013 11:40PM
Re: Question about edges Ben Supnik240March 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 Gould259March 11, 2013 04:57PM
Re: Question about edges Roland Melkert223March 11, 2013 06:02PM
Re: Question about edges Tim Gould235March 11, 2013 06:24PM
Re: Question about edges Travis Cobbs248March 11, 2013 10:12PM
Re: Question about edges Tim Gould258March 11, 2013 02:07PM
Re: Question about edges Ben Supnik284March 22, 2013 03:33PM
Re: Question about edges Tim Gould275March 22, 2013 03:44PM
Re: Question about edges Ben Supnik279March 22, 2013 04:48PM
Re: Question about edges Philippe Hurbain329March 23, 2013 01:49AM
Re: Question about edges Travis Cobbs229March 11, 2013 11:20AM
Re: Question about edges Roland Melkert250March 11, 2013 01:50PM
Re: Question about edges Roland Melkert214March 12, 2013 11:15AM
Re: Question about edges Ben Supnik233March 12, 2013 11:24AM
Re: Question about edges Roland Melkert219March 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