dcsimg
Page 2 of 2 FirstFirst 12
Results 41 to 49 of 49

Thread: [VB6] QuadTree

  1. #41

    Thread Starter
    Hyperactive Member
    Join Date
    Sep 2010
    Location
    Italy
    Posts
    335

    Re: [VB6] QuadTree

    Sorry if I insist, but I still think that "one and only one" collision-event detection per colliding Pair, (I mean "at least one and no more than one" collision-event detection per colliding Pair) is a must.

    If Olaf's approach works anyway (without catching ALL collsion pairs in a single time [single all particels query]) in a 2D physic engine, it doesen't mean that it will works well in other scenarios.
    I think 2D physic engine is a kind of "Special Case", since particels are not agglomerating. (They are instantly pushed away from their radius of influenece)

    But in other scenarios like SPH (Smoothed Particles Hydrodynamics) (used to simulate fluids) where particles are very close each other, and their Action/influence Radius is large. I'm pretty sure that the resulting simulation behaviour will be weird.
    Name:  The-method-of-approximation-of-field-variables-in-the-SPH-The-approximation-at-a.jpg
Views: 117
Size:  32.5 KB
    https://www.researchgate.net/publica...ation-at-a.png

    Another possible problematic scenario could be Crowd Simulation or Boids (Flocking Behaviour by Craig Reynolds)
    Name:  boid.jpg
Views: 116
Size:  12.0 KB
    http://www.red3d.com/cwr/boids/
    http://www.trsp.net/teaching/lifemod/clase1/boid.png

    So in spite it works on 2D physic engine, I strongly doubt it will work in these kind of scenarios.
    For this, IMO, a QuadTree implementation without "one and only one" collision-event detection per colliding Pair, to me is still incomplete.

    That said, I think that to implement it in Olaf code is not so hard to do.

    I have not tested them, anyway these are my 2 ideas:

    1)
    Code:
    For i = 0 To UBound(Particles)
        Set P = Particles(i)
         '  If Not P.HighLight Then 
          QTree.QueryRectangle P.x, P.y, P.r + MaxRadius, P.r + MaxRadius
          For j = 0 To QTree.FoundPoints_Count - 1
              Set OtherP = QTree.FoundPoints_UserObj(j)
              If   ObjPtr(P) < ObjPtr(OtherP) then
                 If P.Intersects(OtherP) Then
                    Debug.Print ObjPtr(P), ObjPtr(OtherP)
                    If Not P.HighLight Then P.HighLight = True: P.Render CC
                    If Not OtherP.HighLight Then OtherP.HighLight = True: OtherP.Render CC
                 End If
              End If
          Next
          If Not P.HighLight Then P.Render CC
      ' End If 
    Next
    2)
    Code:
    For i = 0 To UBound(Particles)
        Set P = Particles(i)
         '  If Not P.HighLight Then 
          QTree.QueryRectangle P.x, P.y, P.r + MaxRadius, P.r + MaxRadius
          For j = 0 To QTree.FoundPoints_Count - 1
              Set OtherP = QTree.FoundPoints_UserObj(j)
              If Not P Is OtherP  and Not OtherP.ALREADYCHECKEDALL Then 
                 If P.Intersects(OtherP) Then
                    Debug.Print ObjPtr(P), ObjPtr(OtherP)
                    If Not P.HighLight Then P.HighLight = True: P.Render CC
                    If Not OtherP.HighLight Then OtherP.HighLight = True: OtherP.Render CC
                 End If
              End If
          Next
          If Not P.HighLight Then P.Render CC
       P.ALREADYCHECKEDALL = True
      ' End If 
    Next

    Sorry but nobody will remove from my mind that "one and only one collision-event detection per colliding Pair" is a must.
    Last edited by reexre; Sep 9th, 2018 at 12:06 PM.

  2. #42
    PowerPoster Elroy's Avatar
    Join Date
    Jun 2014
    Location
    Near Nashville TN
    Posts
    4,613

    Re: [VB6] QuadTree

    Geez, I was hoping to just move past all of this. But there are apparently some people who just refuse to let go of the drama and move on. So...

    Referring to the original code in OP (and I haven't checked to see if it changed, as I've got it from it was originally posted).

    IMHO, the following is just an awful practice, even for an example:

    Code:
    
    Private Sub Form_Unload(Cancel As Integer)
    
    
        End
    
    End Sub
    
    

    It just promotes this bad behavior, and should aways be done in a more elegant way. Reexre, if you care to, look at any of my postings in this thread for a much better way to deal with this.


    And...

    Code:
    
    Friend Sub Setup(x1 As Double, y1 As Double, x2 As Double, y2 As Double, Capac As Long)
    
        If Capac Then
            With Boundary
                .x1 = x1
                .y1 = y1
                .x2 = x2
                .y2 = y2
            End With
            Capacity = Capac
    
    
            ReDim pX(Capacity)
            ReDim pY(Capacity)
            ReDim pIDX(Capacity)
        End If
    
    

    We'll notice that pX, pY, and pIDX are dimensioned with the Capacity variable. However, as done, all three of these will have ZERO as their lower dimension. Therefore, best case, you'll be wasting an array element for each of them (and along with the wasted associated memory). In the videos, Matthew treats all variables as ZERO for the lower bound. Therefore, it would seem that these should be...

    Code:
    
            ReDim pX(Capacity - 1)
            ReDim pY(Capacity - 1)
            ReDim pIDX(Capacity - 1)
    
    

    Or, maybe you're just treating Capacity incorrectly and always including an extra element from what the caller wanted. Or, maybe it's an outright bug causing larger problems. I don't have RC5 and I didn't research further to sort it out. I simply saw this, and started to get leery about the quality of the code.


    And then, if we view the video posted in OP, and listen to around 12:45 into it, you'll see where Matthew talks about a circle geometry object. And then, he goes on to explain why that's the optimal object to use to speed up the use of the QuadTree in this situation. And Reexre, this is something you totally skipped. Now, having gotten into all of this some more, I'll admit that a rectangle would also work. However, since this entire discussion is about optimization, this circle geometry object is probably something we shouldn't overlook. And, if you bother to look at any of the code I posted, you'll find that I developed that circle geometry object.


    Therefore, yet again, I'll apologize. I'm sorry you've taken this the wrong way. However, with these problems and omissions, I did make the statement that your OP code wasn't ready for prime time. That wasn't meant to be a personal slight, just a comment about your code.

    ((( And I can't help but feel all of the "personal" digs at me are more to do with my refusal to adopt and support RC5, than the actual issues of this thread. )))


    As things progressed, I made commitments to write what I saw as the complete example of what Matthew was attempting to illustrate. Furthermore, I committed to optimizing it for the VB6 language. In addition, I committed to expanding it to the OctoTree (3D) situation. And I feel that I met all of those commitments in posts above.

    Again, I'm sorry that you've taken my critiques so personally. They weren't meant that way. My sole purpose was to provide improvements as well as alternatives that are entirely open-source and have no third-party dependencies. And, even though it seems like I've been wandering around in a mine field, I do feel that that's all I've done.

    Best Regards,
    Elroy
    Last edited by Elroy; Sep 14th, 2018 at 04:50 PM.
    Any software I post in these forums written by me is provided “AS IS” without warranty of any kind, expressed or implied, and permission is hereby granted, free of charge and without restriction, to any person obtaining a copy. Please understand that I’ve been programming since the mid-1970s and still have some of that code. My contemporary VB6 project is approaching 1,000 modules. In addition, I have a “VB6 random code folder” that is overflowing. I’ve been at this long enough to truly not know with absolute certainty from whence every single line of my code has come, with much of it coming from programmers under my employ who signed intellectual property transfers. I have not deliberately attempted to remove any licenses and/or attributions from any software. If someone finds that I have inadvertently done so, I sincerely apologize, and, upon notice and reasonable proof, will re-attach those licenses and/or attributions. To all, peace and happiness.

  3. #43

    Thread Starter
    Hyperactive Member
    Join Date
    Sep 2010
    Location
    Italy
    Posts
    335

    Re: [VB6] QuadTree

    ..... thinking
    Last edited by reexre; Sep 14th, 2018 at 06:57 PM.

  4. #44

    Thread Starter
    Hyperactive Member
    Join Date
    Sep 2010
    Location
    Italy
    Posts
    335

    Re: [VB6] QuadTree

    Quote Originally Posted by Elroy View Post
    And then, if we view the video posted in OP, and listen to around 12:45 into it, you'll see where Matthew talks about a circle geometry object. And then, he goes on to explain why that's the optimal object to use to speed up the use of the QuadTree in this situation. And Reexre, this is something you totally skipped.
    What do you mean ?

    Version 1 ( never changed )


    Code:
     diam2 = (R * 2) ^ 2
        ...
        ...
            For I = 1 To tNP - 1
                Q.Query x(I) - R * 2, y(I) - R * 2, _
                        x(I) + R * 2, y(I) + R * 2, rX(), rY(), rIDX(), True
                For J = 1 To UBound(rX)
                    If rIDX(J) > I Then
                        PairsChecked = PairsChecked + 1
                        dx = x(I) - rX(J)
                        dy = y(I) - rY(J)
                          If dx * dx + dy * dy < diam2 Then 
                            CollisionsFound = CollisionsFound + 1
                            With vbDrawCC
                                .Arc x(I), y(I), R
                                .Arc rX(J), rY(J), R
                                .Fill
                            End With
                        End If
                    End If
                Next
            Next
    version 2.1 ( diffrent radius)
    Code:
            For I = 1 To NPoints - 1
                Q.QuerySquare X(I), Y(I), (MaxR + R(I)), rX(), rY(), rIDX()
                For J = 1 To UBound(rX)
                    If rIDX(J) > I Then
                        I2 = rIDX(J)
                        PairsChecked = PairsChecked + 1
                        DX = X(I) - rX(J)
                        DY = Y(I) - rY(J)
                        minD = R(I) + R(I2)
                        If (DX * DX + DY * DY) < (minD * minD) Then
                            CollisionsFound = CollisionsFound + 1
                            With vbDrawCC
                                .Arc X(I), Y(I), R(I)
                                .Arc rX(J), rY(J), R(I2)
                                .Fill
                            End With
                        End If
                    End If
                Next
            Next

    What's the problem ?
    Because I've done it outside of class cQuadTree.cls class ?


    Do you think a QueryCircle SUB like:

    Code:
    Friend Sub QueryCircle(cx As Double, _
                           cy As Double, _
                           R As Double, _
                           rpX() As Double, rpY() As Double, rpIDX() As Long)
    
        FoundUpperBound = DefaultFoundUpperBound
        ReDim rpX(FoundUpperBound)
        ReDim rpY(FoundUpperBound)
        ReDim rpIDX(FoundUpperBound)
    
        foundCount = 0
    
        pvQueryCircle cx, cy, R, rpX(), rpY(), rpIDX(), foundCount, FoundUpperBound
    
        ReDim Preserve rpX(foundCount)
        ReDim Preserve rpY(foundCount)
        ReDim Preserve rpIDX(foundCount)
    
    End Sub
    Friend Sub pvQueryCircle(cx As Double, _
                             cy As Double, _
                             R As Double, _
                             rpX() As Double, rpY() As Double, rpIDX() As Long, foundCount As Long, FoundUpperBound As Long)
    
    
        Dim I       As Long
        Dim rX1     As Double: rX1 = cx - R
        Dim ry1     As Double: ry1 = cy - R
        Dim rX2     As Double: rX2 = cx + R
        Dim ry2     As Double: ry2 = cy + R
    
        Dim dx      As Double
        Dim dy      As Double
                
         Dim RSq     As Double
         RSq = R * R 
    
        If Not (BBOverlap(rX1, ry1, _
                          rX2, ry2, _
                          Boundary.x1, Boundary.y1, _
                          Boundary.x2, Boundary.y2)) Then Exit Sub
    
        For I = 1 To mNP
             
            dx = pX(I) - cx
            dy = pY(I) - cy
            If (dx * dx + dy * dy) < RSq Then 
                foundCount = foundCount + 1
                If foundCount > FoundUpperBound Then
                    FoundUpperBound = foundCount * 2
                    ReDim Preserve rpX(FoundUpperBound)
                    ReDim Preserve rpY(FoundUpperBound)
                    ReDim Preserve rpIDX(FoundUpperBound)
                End If
    
                rpX(foundCount) = pX(I)
                rpY(foundCount) = pY(I)
                rpIDX(foundCount) = pIDX(I)
    
            End If
        Next
    
        If Divided Then
            ChildNW.pvQueryCircle cx, cy, R, rpX(), rpY(), rpIDX(), foundCount, FoundUpperBound
            ChildNE.pvQueryCircle cx, cy, R, rpX(), rpY(), rpIDX(), foundCount, FoundUpperBound
            ChildSW.pvQueryCircle cx, cy, R, rpX(), rpY(), rpIDX(), foundCount, FoundUpperBound
            ChildSE.pvQueryCircle cx, cy, R, rpX(), rpY(), rpIDX(), foundCount, FoundUpperBound
        End If
    
    End Sub
    Would it makes a big difference ?
    From what I understand, you consider a lack that my code does not have a QueryCircle subrutine.
    Instead of complaining you could have wrote it for me.
    Anyway here it is QueryCircle. (above) hooray

    From my point of view it is absolutely not a lack.
    I put the video just to say what was my source of inspiration. not that I wanted to do it the same way.

    Quadtree ...
    Damn me.
    Such a simple thing to do.
    Who knows what I had in mind when it occurred to me to share the code and think that someone could have been "really" interested in using it ...
    I should have known that the goal is the challenge, nobody cares about practical use.
    What a fool !

    I will try not to make this kind of mistake again.
    Last edited by reexre; Sep 14th, 2018 at 08:39 PM.

  5. #45

    Thread Starter
    Hyperactive Member
    Join Date
    Sep 2010
    Location
    Italy
    Posts
    335

    Re: [VB6] QuadTree

    Now I think I understand your point of view better and I hope that the misunderstanding between us is over.

    You have been very focused on the video.
    while I do not. I had only put it to cite the source of inspiration, but not to say that I would have done the same.

    Quote Originally Posted by Elroy
    I did make the statement that your OP code wasn't ready for prime time. That wasn't meant to be a personal slight, just a comment about your code.
    For my above statement I turn upset when you continuosily assert my code is incomplete. I think is quite normal.
    To you "Complete" means like the one of the video.
    To me "Complete" means it is working.
    ...I put the video just to cite the inspiration. (I'll never do it again!)
    Mine is completely working from the beginning , and moreover it includes from the beginning the "Issues of Pairs" solution. (One and only One collision detection per Colliding Pair)


    Quote Originally Posted by Elroy View Post
    I don't have RC5 and I didn't research further to sort it out. I simply saw this, and started to get leery about the quality of the code.
    ...
    ((( And I can't help but feel all of the "personal" digs at me are more to do with my refusal to adopt and support RC5, than the actual issues of this thread. )))
    My code uses RC5 only for rendering ... so, with small changes it can be used in any scenario of rendering technique.
    To me is not a problem if you prefer not to use it.


    I hope the misunderstanding is over, and that we move on
    ( I think we will ..... Until you will say again that my code Version1 of post #1 is incomplete and unready for for prime time.
    hahahaha )
    Last edited by reexre; Sep 15th, 2018 at 06:24 AM.

  6. #46
    PowerPoster Elroy's Avatar
    Join Date
    Jun 2014
    Location
    Near Nashville TN
    Posts
    4,613

    Re: [VB6] QuadTree

    By the way, I agree with you that there's only one collision between any two dots. In my code examples, I changed it so that no rendering was done until everything was checked. And then, prior to rendering, if I found a collision, I changed the color of BOTH dots. Then, I used color as a flag to see if that dot needed to be checked for collisions. That way, I circumvented the checking for about half my dots (because they were already "found" when the opposing dot's collision was found). ((( I didn't upload any of this, as it hardly took anything to implement. I will upload it if someone requests. )))

    Whether or not I used the QuadTree, checking the color (as a flag) before searching sped up the framerate by a good additional 20% (if not more).

    And these ideas (two dots but only one collision) also apply to the 3D situation just as they apply to the 2D situation.

    Take Care,
    Elroy
    Any software I post in these forums written by me is provided “AS IS” without warranty of any kind, expressed or implied, and permission is hereby granted, free of charge and without restriction, to any person obtaining a copy. Please understand that I’ve been programming since the mid-1970s and still have some of that code. My contemporary VB6 project is approaching 1,000 modules. In addition, I have a “VB6 random code folder” that is overflowing. I’ve been at this long enough to truly not know with absolute certainty from whence every single line of my code has come, with much of it coming from programmers under my employ who signed intellectual property transfers. I have not deliberately attempted to remove any licenses and/or attributions from any software. If someone finds that I have inadvertently done so, I sincerely apologize, and, upon notice and reasonable proof, will re-attach those licenses and/or attributions. To all, peace and happiness.

  7. #47

    Thread Starter
    Hyperactive Member
    Join Date
    Sep 2010
    Location
    Italy
    Posts
    335

    Re: [VB6] QuadTree

    I made a test about speed
    To me it results that using QueryCircle compared to QuerySquare the speed is pratically the same.

    QueryCircle is nicer because it give us all points within the radius of a given point.
    (PairsChecked == CollisionsFound)

    However, it is preferable only when the radii are identical.

    Code:
        'with QueryCIRCLE
            For I = 1 To NPoints - 1
                Q.QueryCircle X(I), Y(I), R2, rX(), rY(), rIDX()
                For J = 1 To UBound(rX)
                    If rIDX(J) > I Then
                        PairsChecked = PairsChecked + 1
                        '           DX = X(I) - rX(J)
                        '           DY = Y(I) - rY(J)
                        '           If DX * DX + DY * DY < diam2 Then
                        CollisionsFound = CollisionsFound + 1
                        With vbDrawCC
                            .Arc X(I), Y(I), RADIUS
                            .Arc rX(J), rY(J), RADIUS
                            .Fill
                        End With
                    End If
                    '                End If
                Next
            Next

    When you have different radii it is practically useless.
    Since the radius of QueryCircle must be Ri + RMAX and after obtaining Query results you need to make another distance check. (Ri+Rj)
    (I mean:
    Inside QueryCircle there's DX and DY computation. [to check if points are within Ri + RMAX distance]
    And after obtaining the resulting points you have to compute again DX DY [To check if they are within (Ri+Rj) distance])

    (I'm talking about how it is implemented in my code)





    About Pairs:

    Quote Originally Posted by Elroy
    if I found a collision, I changed the color of BOTH dots. Then, I used color as a flag to see if that dot needed to be checked for collisions.
    Try not to do the same think that Olaf did.
    This way you will encounter same problem

    Suppose we have 3 particles of the same radius arranged in a circle at the same distance, so that they are in the shape of a triangle.
    Suppose that they touch each other
    The pairs are A-B, A-C and B-C.

    If you use color as a flag. What happen ?

    - Look "A". The color light is not ON, so check the neighbors
    .............Find B, Then Turn ON A and B
    ............Find C, Then Switch ON A and C
    - Go on, but there's nothing to check on because you've already turned ON B and C

    So you only found 2 pairs: A-B and A-C
    missing B-C pair
    (and this is not good if our intention is to implement a QuadTree for generic scenarios. As I've already said , we have to detect ALL pairs , and do it only one time for each of them)

    My code has not this kind of problem, because I check
    1 with 2 to N___________( A with B and C )
    2 with 3 to N___________( B with C )
    3 with 4 to N
    N-1 with N

    Here you can find my approach to a solution about same problem in Olaf's code.
    Last edited by reexre; Sep 15th, 2018 at 04:20 PM.

  8. #48
    PowerPoster
    Join Date
    Jun 2013
    Posts
    3,794

    Re: [VB6] QuadTree

    Quote Originally Posted by reexre View Post
    ...and this is not good if our intention is to implement a QuadTree for generic scenarios.

    The QuadTree is one thing - the other thing is, in what scenario you use the QuadTree -
    and no, there is no "generic scenario" whilst using a QuadTree.

    I've explained this in #26 over here already: http://www.vbforums.com/showthread.p...=1#post5318293
    but I'll include a copy of what I wrote, to continue the discussion in this place, if you want...

    -----------------------------
    It's because "the pairing-issue" is not really "resolvable" in a satisfying way for all possible usage-scenarios of a QuadTree.

    The QuadTree-algo which you introduced in your CodeBank-entry is a (relatively simple) - and *generic* thing.
    (which I tried to make more clear, by deliberately "isolating it" in its own ActiveX-Dll).
    It can be used in a whole lot of different scenarios, to get a list of Points for a certain "area of interest" fast
    (ideally a Rectangle of interest, to keep things speedy) - but that's it already QuadTree-wise.

    Now, the "pairing-stuff" is "UserCode-stuff" (not QuadTree-related really), which is basically in 3 categories (in any given "area of interest"):
    1) pairings, which are satisfactional as long as they cover only "all UserObjects once"
    2) pairings, which consider "all pairs" of UserObjects, but allow only "a single directional-pairing"
    3) pairings, which consider "all pairs" of UserObjects, but allow "both possible directional-pairings"

    Category 1) being a sub-set of 2) - which itself is a sub-set of 3)

    It entirely depends on the scenario, which "pairing-type" you choose.

    E.g. the initial example (where an existing overlapping was simply highlighted) was using category 3) in the beginning,
    but was later changed, to work in "category-mode 1)" (for a bit more speed)

    The "solid-body"-physics-scenario you've posted later, was using category 2),
    whereas my take at the same "solid-body"-scenario was using 1), which usually produces less pairings than 2) in each iteration,
    but behaves basically the same as yours (since overlapping in a solid-body simulation is resolved fast - and the exception, not the rule).

    So, both 1) and 2) can be used in a solid-body-simulation - 2) with more precision - 1) with a bit more speed, but less precision per cycle -
    only 3) has to be ruled out in that scenario entirely (to not try to resolve an overlapping collision for the same pair twice).

    But of course there are a whole lot of scenarios (as e.g. in "crowd-simulation", which you brought up),
    where even 3) will entirely make sense.

    E.g. if you consider 3 persons A,B and C - which are (Point-wise) returned by a fast QuadTree-Query "within an area of interest" (as e.g. their "visual-range")...

    Each of these 3 persons could (depending on their psyche or "mental state") behave in different ways "in a panic".
    So, in an implementation you will have different routines (depending on an assumed "mental state"),
    how each of the persons will react "in relation to the two others" -
    and thus category 3) "pairings without considering order" are useful there:
    - Viewpoint of person A (pairings being A->B, A->C) might react to B and C (with regards to a new movement-vector) differently than
    - Viewpoint of person B (pairings being B->A, B->C) ... or
    - Viewpoint of person C (pairings being C->A, C->B)

    So there is no "single type of pairing-category which is useful everywhere".

    Olaf

  9. #49

    Thread Starter
    Hyperactive Member
    Join Date
    Sep 2010
    Location
    Italy
    Posts
    335

    Re: [VB6] QuadTree

    Quote Originally Posted by Schmidt View Post
    So there is no "single type of pairing-category which is useful everywhere".
    I understand what you mean and I agree that QuadTree is something general.
    I think it is my deformation because I often do / did programs that had to do with interaction between objects.

    About Physic engine sceneario you not conviced me so much.
    I understood that the case of multiple collisions per object in the same time is very rare. And that the collision not detected, in case, will be detected anyway in the next step.
    But I do not like it conceptually. and I'm not so sure there's any gain in speed.

    Your example of 3) to me do not make a lot sense, because once you detect A-B it is useless to detect again B-A.
    For example you detect A-B and you check if B is in FOV (field of view) of A. In that case A execute something.
    Already having this pair, then you check if A is in FOV of B and in that case B execute something.
    So bidirectional case 3) to me do not make a lot of sense, but someone could like it. (Detecting twice the pairs needed)

    The case I mentioned (SPH) is the one that most from the idea of how method 2) is indispensable.
    And in my opinion the one that best suits all situations.

    So to me. Personally method 2 (the one I've always talked about) is the best and should be the one to choose by default.
    However I agree that everyone can use the methods of "pairs detection" they prefer. (perhaps slipping more easly into some error of lack or redundancy)

    Last edited by reexre; Sep 16th, 2018 at 06:00 PM.

Page 2 of 2 FirstFirst 12

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  



Featured


Click Here to Expand Forum to Full Width