代写CISC/CMPE 330、program代做、代写Python，Java，C/C++程序设计

日期：2020-10-11 11:27

Computational Geometry

Assignment for CISC/CMPE 330

1) Intersect-Two-Lines

x Compute the approximate (symbolic) intersection of two lines, with a suitable error metric.

Define each line by fix point P and direction vector v. Use the standard line equation.

x Input: (P1, v1), (P2, v2)

x Output: symbolic intersection point, error

x Testing: Sketch up on paper at least three test cases with easy-to-see solutions (a.k.a. groundtruth).

Include intersecting, non-intersecting and parallel lines. Examine if your program

produces the expected output.

(2) Intersect-Line-and-Plane

x Compute the intersection of and plane. The plane is given by a point (A) and its normal vector

(n). The line is given by a fix (P) and the direction vector (v).

x Input: (A, n), (P, v)

x Output: intersection point

x Testing: Sketch up on paper at least three test cases, including a parallel line and plane. Examine

if your program produces the expected output.

(3) Intersect-Line-and-Ellipsoid

x Compute the intersection of a line and the canonical ellipsoid with half-axes lengths a, b, c. The

line is given by a fix (P) and the direction vector (v). Use the standard equations for line and

ellipsoid, derive the 2nd degree polynomial, and find the roots.

x Input: (P, v), (a, b, c)

x Output: number of intersections, intersection point(s)

x Testing: Sketch up on paper at least three test cases with easy-to-see solutions (a.k.a. groundtruth),

for 0,1, and 2 intersection points. Examine if your program produces the expected output.

(4) Intersect-Sphere-and-Cylinder

x Compute the number of intersection points (0, 1 infinite) between a sphere and an infinite

cylinder. The sphere is given by its center (C) and radius (R). The cylinder is given by its radius

(r), a point on its central axis (P) and the direction vector of its central axis (v). Explain your

approach in comment or on paper.

x Input: (C, R), (r, P, v)

x Output: number of intersections (0, 1, infinite)

x Testing: Sketch up on paper at least three test cases with easy-to-see solutions (a.k.a. groundtruth).

Examine if your program produces the expected output.

5) Reconstruct-Sphere

x Reconstruct the best fitting sphere from a set of points. Explain your approach in comments. The

sphere will be defined by center point (C) and radius (R).

x Input: [points-in]

x Output: C, R

Page 2 of 4

x Testing: Generate points on a general sphere (other than the canonical unit sphere), use 20x20

surface patches, reconstruct, and examine the result.

(6) Generate-Random-Unit-Vector

x Generate a unit vector in random direction in 2D or in 3D.

x Input: 2 or 3 (for the dimension)

x Output: vector

x Testing: Create the following two ground-truth tests: run the function several times for 2D and

3D, and plot resulting points on the canonical unit circle and unit sphere, respectively, and

inspect the results.

(7) Generate-Orthonormal-Frame

x Compute an orthonormal frame from three points (A, B, C). Define the frame by a centre (Oe)

and three base vectors (e1, e2, e3). Place center in the center or gravity.

x Input: (A, B, C)

x Output: Oe, (e1, e2, e3)

x TESTING: Sketch up on paper at least three sufficiently general test cases, with easy-to-see

solutions (a.k.a. ground-truth). One example should be collinear (A, B, C). Examine if your

program produces the expected output.

(8) Rotation-About-Frame-Axis

x Generate a transformation matrix to rotate a point about one of the (x,y,z) frame axes by a given

rotation angle. For future convenience, return the rotation in both 3x3 and 4x4 formats.

x Input: axis, angle

x Output: Rotation matrix (3x3), Homogeneous rotation matrix (4x4)

x TESTING: Sketch up on paper at least 3 sufficiently general test cases, with easy-to-see

solutions (a.k.a. ground-truth), including each axis. Examine if your program produces the

expected output.

(9) Frame-Transformation-to-Home

x You want to track a rigid body in the canonical home. Previously, you have attached 3 markers

to the body, measured the position of these markers in your canonical frame, and using your

3Generate-Orthonormal-FUaPe′ URXWiQe, computed the body frame an arbitrary pose 3Y′ (you

computed the Ov, centre and v1,v2,v2 base vectors pose v.)

x Now, must compute the transformation that takes body from pose v to home.

x Input: (Oe, e1, e2, e3) ? centre and 3 base vectors for e and v frames

x Output: Frame transformation ? 4x4 homogeneous matrix

x TESTING: Sketch up on paper 6 ground truth test cases: 2 with pure translation, 2 with pure

rotation, 2 with both some translation and rotation.) In each test case, make a sketch of the

ground-truth and explain how you constructed the transformations. Run the program and

examine if it correctly reproduces the ground-truth.

Page 3 of 4

(10) Target-Tracking-Error-Simulation

Preamble: Simulation is fundamental tool for surgical navigation performance analysis, and it will pop

up in your assignments, repeatedly. Here, you are helped with a step-by-step explanation of the design

and execution of a surgical navigation simulation and analysis problem (to get a hang of it :-)

The clinical problem: We got a brand-new position

tracking device that localizes small electromagnetic

beacons in 3D space. We intend to use three of these

beacons as markers for tracking a SaWieQW?V head

during neurosurgery. We want to integrate the

tracker in an existing neuro-navigation system for

localizing intracranial hemorrhage, like the white

blood clot shown in the CT image (Fig 1). We will

drill a small burr hole through the cranium, enter a

thin tube, and evacuate the hemorrhage (Fig 2). The

required targeting accuracy is rather lenient, about

4.0 mm. But it is an emergency procedure, and often

there is no time to transfer the patient to a proper

operating room, in which case the procedure is done

at the bedside. In such a setup, the head is not rigidly

fixed, and it tends to move excessively during the

craniotomy. All said, for this application, localizing

and tracking the target anatomy is necessary, but

because the target is relatively large, the tracking

does not have to be very accurate ± at least not for

hitting the hemorrhage, but it is equally important to

minimize neurological deficit caused by damage to

the healthy parts of the brain on our way to the target. Now, we must determine if our brand-new tracker

can do the job.

The technical problem: Our new tracking system has some jitter error: each time we localize a marker, it

appears to be somewhat randomly 3displaced′ from its true position, even if the marker is motionless.

Characterization of the Error: We have measured the marker localization error many-many times and

analyzed it statistically. Let us say, we have found the error to be a vector of random direction and of a

magnitude not larger than some 3Err′. Let us say, we do not know the true distribution of this error, so we

must assume the worst case and overestimate the error - because we want our simulation to be stricter than

reality, for we must not never pass a faulty system to clinical use. To overestimate the error, we will

simulate it as a vector of random direction and of a fixed magnitude Err.

Objective: We must determine if we can tolerate the marker localization error without compromising the

required clinical target tracking accuracy.

Ground-truth setup: We must design a simplified geometrical representation of the scene. It needs to be

mathematically and practically sufficiently general for studying the issue at hand (jitter error, in this case),

but simple enough for us to see through the entire process on a piece of paper. In this case, a sphere of

100 mm radius will suffice to model the head.

Fig 1: Examples of Intracranial hemorrhage (white

blood clot) in computed tomography (CT) imaging.

Fig 2: Removal of intracranial hemorrhage: schematics

(left) and actual view in the operating room.

Page 4 of 4

As we are not aware of any dependency of the jitter error on the actual location of the beacons, we are

free to choose the most convenient places for the head, markers, and tracker: we will place head and

tracker both in (0,0,0). In real life, this would mean that the tracker (i.e. HRPeU?V aUPchaiU) is inside the

SaWieQW?V head, bXW in terms of mathematics this is completely irrelevant :-)

In placing the three markers on the head, we will again choose the most convenient locations: A(100,0,0),

B(-50, 0, 86.6), C(-50, 0, -86.6). By doing so, we not only defined the body frame in a known groundtruth

pose within the observation home frame, but we also made the body frame and home frame coincide.

Setup cannot be made more convenient than this, while maintaining complete mathematical generality!

Target Selection: As you remember from our class, for target tracking accuracy, the position of a target

relative to the body frame matters a great deal. Your first task is to determine the best Pb (least errorprone)

and worst Pw (most error prone) target locations of the head. Explain your reasoning. (2pts)

Now, we are ready to start observing our targets in the stationary head with our jittery tracker. In each

observation, we will transform the target between the observed body frame and the true body frame. We

must compute the Target Registration Error (TRE) as the displacement between the true target position

and the observed target position.

Scene Plot: Make a clear drawing or a 3D plot of the scene, with all details (home frame, body frame,

head, markers, error vectors, targets, labels, TRE, etc. in ground truth position and observed position (2pts)

We will siPXOaWe Whe 3WUackiQg QRiVe′ aV UaQdRP YecWRU Rf a giYeQ PagQiWXde Err. Starting from no error

(Err=0), we will gradually increase Err by a small dErr increment (0.5mm is appropriate in this case) until

reaching some Errmax when we expect target registration to fail comprehensively. As a starter, we can try

Errmax=10mm and go higher if we you need to.

Your next task is to develop the simulation program, per below:

Simulation Program (8pts)

x START observing the markers. Displace the markers, each by a different random jitter noise vector

of magnitude Err.

x Transform the targets from home to body frame, using the error-ridden marker positions.

x For each target, compute the Target Registration Error (TRE) as the displacement between the

ground-truth and the transformed target positions.

x Determine if your target tracking accuracy fails to meet the clinical requirement.

x Repeat from START: keep observing the markers for a statistically large-enough number of times,

but without drowning your laptop. Our simulation at hand is not computationally expensive, you

can easily run it some hundreds of times. For each target (best and worst), compute the failure rate

(FR) as number of failures (NF) over the number of observations (N).

x Increment the magnitude of the noise vector (Err) and continue from START or exit if Err reached

the Errmax limit. (Note that if Err =0, then there is no error and all TRE-s must be 0, else you have

a bug.)

Analysis (2pts)

Your final task is to analyze the results. For each target (best and worst), plot the failure rate as a function

of Err. Inspect the plot, explain your findings, and make a well-reasoned recommendation for the

neurosurgeon regarding safety of the system in the given surgical procedure.

1) Intersect-Two-Lines

Program: algorithm / formula 4

Program: handle exception 1

Program: error metric 2

Test (program and paper) 3

Total 10

2) Intersect-Line-and-Plane

Program 7

Test (program and paper) 3

Total 10

3) Intersect-Line-and-Ellipsoid

Paper: Derive polynomial 3

Program: check determinant 1

Program: find roots 3

Test (program and paper) 3

Total 10

4) Intersect-Sphere-and-Cylinder

Explain method 3

Program algorithm/formula 4

Test (program and paper) 3

Total 10

5) Reconstruct-Sphere

Program: Reconstruction 5

Test (program and paper) 2

Total 7

6) Generate-Random-Unit-Vector

Explain method 4

Program 4

Test (program and paper) 2

Total 10

(7) Generate-Orthonormal-Frame

Program: Centre 2

Program: Bases 3

Program: Normalization 2

Test (program and paper) 3

Total 10

(8) Rotate-About-Frame-Axis

Program: x 2

Program: y 2

Program: z 2

Test (program and paper) 3

Total 9

9) Rigid-Body-Transform

Program: frames 1

Program: Translation 1

Program: Rotation 1

Program: Homogeneous transform 1

Test (program and paper) 6

Total 10

10) Target-Tracking-Error-Simulation

Target points 2

Scene plot 2

Program 8

Analysis 2

Total 14

TOTAL 100