BASIC

Author Topic: Simple check of distance from simple 3D Box to 3D point.  (Read 7388 times)

Offline nabz32

  • Community Developer
  • Dr. Type
  • ******
  • Posts: 307
    • View Profile
Edit2: This code is for non rotated boxes only, which are aligned to the Worlds X Z and Y coordinates.
And have only 90 degree corners.

Edit:
Kanonet has done a nice optimized code of my brute force attempt,
so I am pinning his post here for people who need
that code:

Dam, instead of going to sleep you guys made me do this:
Code: GLBasic [Select]
FUNCTION DistanceBoxPoint#: cX# , cY# , cZ# , bXL# , bXR# , bYD# , bYU# , bZF# , bZB#
        cX = IIF( cX<bXL, cX-bXL, IIF( cX>bXR, cX-bXR, 0 ) )
        cY = IIF( cY<bYD, cY-bYD, IIF( cY>bYU, cY-bYU, 0 ) )
        cZ = IIF( cZ<bZF, cZ-bZF, IIF( cZ>bZB, cZ-bZB, 0 ) )
        RETURN cX * cX + cY * cY + cZ * cZ
ENDFUNCTION
Same interface as your function and should give the same results, while having obvious advantages. I love the fun of finding algorithms.  :booze:

My brute force attempt was like this:

Code: GLBasic [Select]
// cX = 3DPointX , cY = 3DPointY , cZ = 3DPointZ
// bXL (box left side, the smallest x coordinate of the box ) , bXR ( box right side, the greatest x coordinate of the box)
// bYD (box bottom side, the smallest y coordinate of the box ) , bYU ( box top side, the greatest y coordinate of the box)
// bZF (box front side, the smallest t coordinate of the box ) , bZB ( box back side, the greatest z coordinate of the box)
FUNCTION DistanceBoxPoint#: cX# , cY# , cZ# , bXL# , bXR# , bYD# , bYU# , bZF# , bZB#
        LOCAL dist# , dist1# , dist2#
        LOCAL distX# , distY# , distZ#
        LOCAL boxYU# , boxYD# , boxXL# , boxXR# , checkX# , checkY#
        distX = 0 ; distY = 0 ; distZ = 0
        FOR i2 = 0 TO 2
                IF i2 = 0 // x and z
                        checkX = cX ; checkY = cZ
                        boxYU = bZB ; boxYD = bZF ; boxXR = bXR ; boxXL = bXL
                ENDIF
                IF i2 = 1 // x and y
                        checkX = cX ; checkY = cY
                        boxYU = bYU ; boxYD = bYD ; boxXR = bXR ; boxXL = bXL
                ENDIF
                IF i2 = 2 // z and y
                        checkX = cZ ; checkY = cY
                        boxYU = bYU ; boxYD = bYD ; boxXR = bZB ; boxXL = bZF
                ENDIF
                dist1 = 0 ; dist2 = 0
                IF checkX < boxXL AND checkY > boxYU // Left top area
                        dist1 = checkX - boxXL ; dist2 = checkY - boxYU
                ENDIF
                IF checkX >= boxXL AND checkX <= boxXR AND checkY > boxYU // top area
                        dist1 = 0 ; dist2 = checkY - boxYU
                ENDIF
                IF checkX > boxXR AND checkY > boxYU // Right top area
                        dist1 = checkX - boxXR ; dist2 = checkY - boxYU
                ENDIF
                IF checkY >= boxYD AND checkY <= boxYU AND checkX > boxXR // right area
                        dist1 = checkX - boxXR ; dist2 = 0
                ENDIF
                IF checkX > boxXR AND checkY < boxYD // Right down area
                        dist1 = checkX - boxXR ; dist2 = checkY - boxYD
                ENDIF
                IF checkX >= boxXL AND checkX <= boxXR AND checkY < boxYD // down area
                        dist1 = 0 ; dist2 = checkY - boxYD
                ENDIF
                IF checkX < boxXL AND checkY < boxYD // Left down area
                        dist1 = checkX - boxXL ; dist2 = checkY - boxYD
                ENDIF
                IF checkY >= boxYD AND checkY <= boxYU AND checkX < boxXL // left area
                        dist1 = checkX - boxXL ; dist2 = 0
                ENDIF
                IF dist1 <> 0
                        IF i2 = 0 ; distX = dist1 * dist1 ; ENDIF
                        IF i2 = 1 ; distX = dist1 * dist1 ; ENDIF
                        IF i2 = 2 ; distZ = dist1 * dist1 ; ENDIF
                ENDIF
                IF dist2 <> 0
                        IF i2 = 0 ; distZ = dist2 * dist2 ; ENDIF
                        IF i2 = 1 ; distY = dist2 * dist2 ; ENDIF
                        IF i2 = 2 ; distY = dist2 * dist2 ; ENDIF              
                ENDIF
        NEXT
        dist = ( distX + distY + distZ )
        // return an not square rooted 3D distance ( if you want the real distance you have to use sqr() on the value this
        // function returns )
        RETURN dist
ENDFUNCTION
 
« Last Edit: 2015-Aug-22 by nabz32 »

Offline Hemlos

  • To boldy go where no pixel has gone before!
  • Global Moderator
  • Prof. Inline
  • *******
  • Posts: 1634
  • Particle Hawk
    • View Profile
why not a simple point to point magnitude?
would be much less to calculate
Volume_of_Earth(km^3) = 4/3*3.14*POW(6371.392896,3)

Offline nabz32

  • Community Developer
  • Dr. Type
  • ******
  • Posts: 307
    • View Profile
when you got large objects that are not segmented into more objects you won´t get an accurate
distance when checking the distance from point to point.
This function basically does the point to point
calculation but selects the most fitting points on the surface of the box for the calculation
( the ones that would give you the shortest distance to the box )
« Last Edit: 2015-Aug-21 by nabz32 »

Offline Hemlos

  • To boldy go where no pixel has gone before!
  • Global Moderator
  • Prof. Inline
  • *******
  • Posts: 1634
  • Particle Hawk
    • View Profile
i see what youre saying...

Its a big algorithm....are you doing a mag test to the actual 3d object vertice, or to the really the closest position on the box faces?

edit: I reread what you said...ok to the face.

very cool dude, there might be a quicker way though.
Im interested because im programming a 3d game too, ill let you know if i come up with something more efficient.
« Last Edit: 2015-Aug-21 by Hemlos »
Volume_of_Earth(km^3) = 4/3*3.14*POW(6371.392896,3)

Offline nabz32

  • Community Developer
  • Dr. Type
  • ******
  • Posts: 307
    • View Profile
it is a really easy one,

take this picture:

^
 |   a|b|c
 y ------
     d|e|f
    ------
     g|h|i
    x-->
e represents the box
it checks if the coordinate is within one of the surrounding areas ( a , b , c , d , f , g , h , i ).
I.e. when its in d the shortest distance would be just the x difference to the left side of e
If the point is in i the shortest distance would always be calculated to the bottom right corner point of e
( in the code these are the cases where the distance is calculated using an x and y part )
When it is inside e the distance is zero and no multiplication is done at all.

It simply uses different coordinate Systems each time it does this,
in the example the box is viewed in an X Y coordinate system
the Algorythm will also look at the box using an X Z Coordinate System and an Z Y Coordinate System.

It could be that the algorythm uses one more iteration than it actually needs in some cases.

And it would be better to check the cases using the GLBASIC SELECT method. :)

But I think it is far more efficient than splitting the box surface into single points and calculate the distance to the points,
when you use large objects in relation to your collision size,
because you need more and more points when your object gets larger.

I use it in my game to calculate the distance to the camera point position on some larger objects to avoid
this object from fading out to early and I had no noteable framerate drop with this on the pandora when tested with 50 Objects
which used this every frame, in my test case.


« Last Edit: 2015-Aug-21 by nabz32 »

Offline Hemlos

  • To boldy go where no pixel has gone before!
  • Global Moderator
  • Prof. Inline
  • *******
  • Posts: 1634
  • Particle Hawk
    • View Profile
Quote
fading out to early

it might be even more efficient to simply create an imaginary boundary, and add half the width of the box.
obviously you would need to adjust this boundary according to your 3d delta changing....but i dont think youll be doing this too much?
even if you did adjust the delta alot...you could just leave the render boundary at its max size.

This could be reduced to 3 comparisions(and one division for the box width) with no itterations.
Your way is more precise, but your delta cant be changed can it?
« Last Edit: 2015-Aug-21 by Hemlos »
Volume_of_Earth(km^3) = 4/3*3.14*POW(6371.392896,3)

Offline nabz32

  • Community Developer
  • Dr. Type
  • ******
  • Posts: 307
    • View Profile
I am sorry, what do you mean with 3D delta ?
Rotation of the camera / boxes?
This could only be done in my code if you rotate the box so that its not rotated anymore together with the point you
want to check the distance from, before you run the coordinates through the function.
But this would need a lot of Cos, Sin and Tan calculations when its done often.

I need this precission in some cases to make the fading look better in general.
I also use it when a bomb explodes, Blocks check this way if they are inside the Blast radius,
used on a grid with many independent blocks makes the impact look circular.

I only have used the point to point / point inside box calculations before in my game, except for the round collision routine
which does a little more math by calculating the intersection Points of two circles and chosing the right one of those.
Of course the point to point aproach is far more efficient and should be used whenever it is possible to ease the CPUs life.

Offline Hemlos

  • To boldy go where no pixel has gone before!
  • Global Moderator
  • Prof. Inline
  • *******
  • Posts: 1634
  • Particle Hawk
    • View Profile
delta of the camera apature....the zoom of the camera i guess you can call it

To find a rendering area, you can get the cosine and set a rendering zone value, which is from the center of your screen to the last things being rendered on the sides.
Use the furthest away object from camera that will be rendered, use that distance, and half the delta of the camera to get the cosine.
Add half the size of your largest object, and youll have a distance across your screen of how far it should go from there to be rendered.

this is one calculation at the start of your game, and no further calcs will be needed other than comparing the distance of any object using thier mid points.

edit:
thank you for these ideas..im going to write an alogirthm tonight that handles this...its something i havent implemented into my game yet.
« Last Edit: 2015-Aug-21 by Hemlos »
Volume_of_Earth(km^3) = 4/3*3.14*POW(6371.392896,3)

Offline kanonet

  • Administrator
  • Prof. Inline
  • *******
  • Posts: 1142
    • View Profile
    • My GLBasic code archiv
Dam, instead of going to sleep you guys made me do this:
Code: GLBasic [Select]
FUNCTION DistanceBoxPoint#: cX# , cY# , cZ# , bXL# , bXR# , bYD# , bYU# , bZF# , bZB#
        cX = IIF( cX<bXL, cX-bXL, IIF( cX>bXR, cX-bXR, 0 ) )
        cY = IIF( cY<bYD, cY-bYD, IIF( cY>bYU, cY-bYU, 0 ) )
        cZ = IIF( cZ<bZF, cZ-bZF, IIF( cZ>bZB, cZ-bZB, 0 ) )
        RETURN cX * cX + cY * cY + cZ * cZ
ENDFUNCTION
Same interface as your function and should give the same results, while having obvious advantages. I love the fun of finding algorithms.  :booze:
Lenovo Thinkpad T430u: Intel i5-3317U, 8GB DDR3, NVidia GeForce 620M, Micron RealSSD C400 @Win7 x64

Offline Hemlos

  • To boldy go where no pixel has gone before!
  • Global Moderator
  • Prof. Inline
  • *******
  • Posts: 1634
  • Particle Hawk
    • View Profile
hmm cool command thanks, didnt even see that
Volume_of_Earth(km^3) = 4/3*3.14*POW(6371.392896,3)

Offline kanonet

  • Administrator
  • Prof. Inline
  • *******
  • Posts: 1142
    • View Profile
    • My GLBasic code archiv
IIF is just the GLBasic version of the C++ ternary/conditional operator '?' and has been around since release of V12. I think when ever possible it should be preferred over IF, but of cause I could have also written that distance function with IF instead of IIF.
Lenovo Thinkpad T430u: Intel i5-3317U, 8GB DDR3, NVidia GeForce 620M, Micron RealSSD C400 @Win7 x64

Offline erico

  • Community Developer
  • Prof. Inline
  • ******
  • Posts: 4209
    • View Profile
    • Portfolio
Dam, instead of going to sleep you guys made me do this:
...

What?! Are you guys waking Kanonet up?!? :D  :P

Offline nabz32

  • Community Developer
  • Dr. Type
  • ******
  • Posts: 307
    • View Profile
wow nice work Kanonet, didn´t know about the IIF command beforehand.

Seeing this code now makes it obvious, that you can just
calculate the x distance by only comparing x and the z distance by only comparing z etc.

Thank you very much. :nw:

Edit: As expected, it returns the same values, as my brute force attempt did, thx again.
« Last Edit: 2015-Aug-21 by nabz32 »

Offline Hemlos

  • To boldy go where no pixel has gone before!
  • Global Moderator
  • Prof. Inline
  • *******
  • Posts: 1634
  • Particle Hawk
    • View Profile
What?! Are you guys waking Kanonet up?!? :D  :P

pffft, IKR! If you whisper 3d, he is all over it like flies on ....
I am glad for this, thank you kanonet, you make a great difference around here.
Volume_of_Earth(km^3) = 4/3*3.14*POW(6371.392896,3)

Offline kanonet

  • Administrator
  • Prof. Inline
  • *******
  • Posts: 1142
    • View Profile
    • My GLBasic code archiv
Actually when someone writes that he found an effective algorithm all I see is "here is your challenge, try to beat me!" lol

nabz32 since you edited your 1st post, you should still mention the limitation of this, like that it is only for a non-rotated box (=aligned to world-axes), with all edges 90°. A more general version would be complex.
Lenovo Thinkpad T430u: Intel i5-3317U, 8GB DDR3, NVidia GeForce 620M, Micron RealSSD C400 @Win7 x64