in reply to RFC: Implementation of a QuadTree and worries of a lone programmer

Just some BS'ing...brainstorming or bullsh*ting...take your pick. :-)

I'm not sure what the Quad tree is used for, and whether you really need it, but as far as overlooking something, I would wonder if it is the fastest way to get your lists. Might not it be faster to make AoA's (arrays of arrays), and loop thru them with Inline-C, finding all $states==1, then extracting the $x,$y,$z.

I'm just mentioning it, because if your grid gets larger, and you are doing 3d stuff, you will need speed. Perl is relatively slow doing recursive math calculations.

I'm not really a human, but I play one on earth Remember How Lucky You Are
  • Comment on Re: Implementation of a QuadTree and worries of a lone programmer

Replies are listed 'Best First'.
Re^2: Implementation of a QuadTree and worries of a lone programmer
by Xenofur (Monk) on Nov 07, 2008 at 18:45 UTC
    What it'll be used for is this: I want to make use of OpenGL occlusion routines to determine which parts of the world can be skipped in drawing. For that i need to create a rough shape around the parts that would be drawn, keeping it cheap enough to actually make a difference. That shape is created by taking all units that would contain something and drawing shapes around them.

    I could go the naive way and draw one cube per unit and call it a day. However that would be rather slow and i'd prefer to draw a rectangular shape that encompasses as many units as possible.

    To give an example on practice, with a map such as this: 
      0   4   8   12 15
 00111000000000000
  1111000000000000
  1111000000000000
  1111000000000000
 40000000000000000
  0000000000000000
  0000000000000000
  0000000000000000
 80000000000000000
  0000000000000000
  0000000000000000
  0000000000000000
120000000000000000
  0000000000000000
  0000000000000000
150000000000000000

    [download]
    , the result would be: 0:3:2:3|2:3:0:1|0:1:1:1|1:1:0:0|. This would be 4 shapes as opposed to the 15 shapes needed if i were drawing this naively.

    I'm not sure at all what you mean in your example in the first place. But my guts tell me that you kinda missed the point. Also, i have no idea about how to use inline-c.

    Edit: I should also note, the grid won't get bigger. At least not in my application. 16x16 is the limit on the data i have. I merely made it work for general cases in case others might find it useful and because i found it easier to work that way.
[reply]
[d/l]
[select]

      I don't understand your notation there "0:3:2:3|2:3:0:1|0:1:1:1|1:1:0:0|", but can't you draw the area with 1's as two objects one large tall one and one small tall one? (1,0)-(3,3) and (0,1)-(0,3) or of course you could split it the other way (0,1)->(3,3) and (1,0)->(3,0).


      ___________
      Eric Hodges
[reply]
        The notation comes from this:
        $rectangles .= "$child->{XMIN}:$child->{XMAX}:$child->{YMIN}:$child->{YMAX}|";

        As for it being condensable into two rectangles: Yes, i am aware of that. Just haven't gotten around to implementing that last bit of optimization. :)

        Reason for that being that i was only made aware of a decently fast way to do it an hour ago.
[reply]

In Section Meditations