On 2/27/2018 6:57 AM, clipka wrote:
> Am 27.02.2018 um 02:26 schrieb Bald Eagle:
>> Mike Horvath <mik### [at] gmailcom> wrote:
>>> I have a three coordinates.
>>>
>>> // bounding box
>>> L3ModelBBoxMin = <-1280,-428,-960>
>>> L3ModelBBoxMax = <1280,0,-160>
>>>
>>> // camera location
>>> L3Location = <2413.395250,-1636.367750,-2657.726250>
>>>
>>>
>>> How do I determine the corner of the bounding box that is nearest the
>>> camera? Thanks.
>>>
>>>
>>> Mike
>>
>> Define the corners you want to test, and calculate the vlength between the
>> corners and the camera location.   Then use min().
> 
> That approach requires 8 vector differences, 8 invocations of vlength
> (which is a comparatively expensive operation as it needs to compute a
> square root), and an 8-parameter invocations of min(), for a total of 24
> operations (8 of which are computationally expensive).
> 
> An alternative exists that requires 2 vector differences, 2
> coordinate-wise vector multiplications, 3 two-parameter invocations of
> min(), 1 sum of three vectors, and 1 square root, for a total of just 9
> operations (only 1 of which is computationally expensive).
> 
> 
> The basic approach exploits the fact that the bounding box is
> axis-aligned, and goes as follows:
> 
> (1) For each axis, compute the absolute distance between the camera and
> both the nearest and the farthest side of the bounding box.
> 
> (2) For each axis, compute the smaller of the two absolute distances.
> 
> (3) Compute the length of the vector given by the three smallest
> absolute distances.
> 
> 
> Naively, this would be:
> 
> (1)
>      #declare DistAX = abs(L3ModelBBoxMin.x - L3Location.x);
>      #declare DistAY = abs(L3ModelBBoxMin.y - L3Location.y);
>      #declare DistAZ = abs(L3ModelBBoxMin.z - L3Location.z);
>      #declare DistBX = abs(L3ModelBBoxMax.x - L3Location.x);
>      #declare DistBY = abs(L3ModelBBoxMax.y - L3Location.y);
>      #declare DistBZ = abs(L3ModelBBoxMax.z - L3Location.z);
> (2)
>      #declare DistX = min(DistAX,DistBX);
>      #declare DistY = min(DistAY,DistBY);
>      #declare DistZ = min(DistAZ,DistBZ);
> (3)
>      #declare Dist = vlength(<DistX,DistY,DistZ>);
> 
> Even in this straightforward form the algorithm has just 16 operations,
> only one of which is is a computationally expensive vlength operation.
> 
> 
> Better yet, this algorithm provides room for further optimization.
> 
> The first step may be a bit counter-intuitive, as we'll re-write step
> (3) using more primitive operations:
> 
> (3a)
>      #declare SqrDistX = DistX*DistX;
>      #declare SqrDistY = DistY*DistY;
>      #declare SqrDistZ = DistZ*DistZ;
> (3b)
>      #declare SqrDist = SqrDistX+SqrDistY+SqrDistZ;
>      #declare Dist = sqrt(SqrDist);
> 
> Now note that since DistX, DistY and DistZ are positive values, it
> doesn't matter whether we compute the smaller of each of them before or
> after squaring, allowing us to re-arrange steps (2) and (3a) as follows:
> 
> (3a)
>      #declare SqrDistAX = DistAX*DistAX;
>      #declare SqrDistAY = DistAY*DistAY;
>      #declare SqrDistAZ = DistAZ*DistAZ;
>      #declare SqrDistBX = DistBX*DistBX;
>      #declare SqrDistBY = DistBY*DistBY;
>      #declare SqrDistBZ = DistBZ*DistBZ;
> (2)
>      #declare SqrDistX = min(SqrDistAX,SqrDistBX);
>      #declare SqrDistY = min(SqrDistAY,SqrDistBY);
>      #declare SqrDistZ = min(SqrDistAZ,SqrDistBZ);
> 
> Now note that a distance squared is always positive no matter the sign
> of the input values, so it doesn't matter whether we compute the
> absolute in step (1), allowing us to rewrite it as follows:
> 
> (1)
>      #declare DistAX = L3ModelBBoxMin.x - L3Location.x;
>      #declare DistAY = L3ModelBBoxMin.y - L3Location.y;
>      #declare DistAZ = L3ModelBBoxMin.z - L3Location.z;
>      #declare DistBX = L3ModelBBoxMax.x - L3Location.x;
>      #declare DistBY = L3ModelBBoxMax.y - L3Location.y;
>      #declare DistBZ = L3ModelBBoxMax.z - L3Location.z;
> 
> 
> Now note that since steps (1) and (3a) are effectively coordinate-wise
> operations for which corresponding vector operations are available, we
> can yet again rewrite the code one last time, leaving us with the
> following compact form:
> 
> (1)
>      #declare DistA = L3ModelBBoxMin - L3Location;
>      #declare DistB = L3ModelBBoxMax - L3Location;
> (3a)
>      #declare SqrDistA = DistA*DistA;
>      #declare SqrDistB = DistB*DistB;
> (2)
>      #declare SqrDistX = min(SqrDistA.x,SqrDistB.x);
>      #declare SqrDistY = min(SqrDistA.y,SqrDistB.y);
>      #declare SqrDistZ = min(SqrDistA.z,SqrDistB.z);
> (3b)
>      #declare SqrDist = SqrDistX+SqrDistY+SqrDistZ;
>      #declare Dist = sqrt(SqrDist);
> 
> As you can see, this leaves us with just 9 operations (or 10 if you are
> nitpicky and count the three-vector sum as 2 two-vector sums), and the
> only computationally expensive one is 1 square root.
> 


Thanks, Christoph.



Mike

Post a reply to this message

clipka <ano### [at] anonymousorg> wrote:

>
> Technically you can't just overwrite a single coordinate of a vector.
> You'll have to overwrite the entire vector; any coordinate you want to
> stay the same will have to be explicitly taken from the vector's old value.
>

Something I didn't know. Thanks for the tip (and for your analysis of vlength
etc. eleswhere.)

Post a reply to this message