[vtkusers] [Fwd: Re: Doubt about vtk hash implementation...]

[Renato N. Elias]

Hi David,

I was expecting some index computed from the polygon point ID's itself. 
For example, let's consider the edge extraction from a triangle mesh 
formed by 2 triangles:

T1: 1-2-3 (edges 1-2, 2-3, 3-1)
T2: 3-2-4 (edges 3-2, 2-4, 4-3)

These edges can be extracted using a hash table which would take pairs 
of points ID's and compute a corresponding and "unique" index, so:

For the first triangle:
int index = HashFunction(1,2); // index for 1st edge
int index = HashFunction(2,3); // index for 2nd edge
int index = HashFunction(1,3); // index for 3rd edge

For the second:
int index = HashFunction(2,3); // index for *2nd* edge
int index = HashFunction(2,4); // index for 4th
int index = HashFunction(3,4); // index for 5th

the main difference between this approach and VTK's is that VTK does not 
actually *compute* an index. It searches for data already inserted in 
the table and places new data in free positions. Is it also considered a 
hash table?

Renato.

David Cole wrote:
> line 1452:
>   // Look for existing quad in the hash;
>   end = this->QuadHash + a;
>
> "a" is used as the starting location of the search. A brute force 
> search would start at 0 and look at every element up to "a" as well. 
> This is the best case sort of hash table where you are happily able to 
> use the input *as* the hash index...
>
>
> Does that make it clearer?
> David
>
>
> On Wed, Apr 30, 2008 at 9:51 AM, Renato N. Elias 
> <rnelias at nacad.ufrj.br <mailto:rnelias at nacad.ufrj.br>> wrote:
>
>     Hi folks,
>
>     I was trying to understand a VTK algorithm inside
>     vtkDataSetSurfaceFilter class. In this class, there's a method
>     called InsertQuadInHash (line 1418). My doubt is that after
>     studying the code, I was not able to find where the hash index is
>     being computed. From my knowledge, a hash table is made of indexes
>     which are computed using some sort of hash function but this
>     algorithm seems to be only a brute force search inside a linked
>     list. What am I missing?
>
>     thanks for any clarification
>
>     Renato.
>     _______________________________________________
>     This is the private VTK discussion list.
>     Please keep messages on-topic. Check the FAQ at:
>     http://www.vtk.org/Wiki/VTK_FAQ
>     Follow this link to subscribe/unsubscribe:
>     http://www.vtk.org/mailman/listinfo/vtkusers
>
>