|
|
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.
Post a reply to this message
|
|