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.

https://www.researchgate.net/publica...ation-at-a.png

Another possible problematic scenario could be Crowd Simulation or Boids (Flocking Behaviour by Craig Reynolds)

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
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
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
' 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.

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:
```

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

..... thinking

Originally Posted by Elroy
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```
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.

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.

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.

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)

Originally Posted by Elroy
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 )

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

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
.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)

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.

Originally Posted by reexre
...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.

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

Originally Posted by Schmidt
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)

#### 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