CMPE 330代做、Java，c/c++编程代写

日期：2023-10-07 07:38

Computational Geometry

Assignment for CISC/CMPE 330

1) Intersect-Two-Lines

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

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

• Output: symbolic intersection point, error

• 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

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

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

• Output: intersection point

• 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

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

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

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

• 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

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

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

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

• 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

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

• Input: [points-in]

• Output: C, R

Page 2 of 4

• 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

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

• Input: 2 or 3 (for the dimension)

• Output: vector

• 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

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

• Input: (A, B, C)

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

• 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

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

• Input: axis, angle

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

• 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

Let’s assume that you want to track a cancer target in a rigid body (like the head) in the

canonical home Oh(0,0,0) h1(1,0,0) h2(0,1,0) h3(0,0,1). You observe the rigid body in an

arbitrary pose (call it v pose) and you have already computed its body frame in this pose (v

frame) defined by Ov centre and the v1,v2,v2 base vectors.

• Your task is to compute the transformation that takes the perspective from v frame to home.

• Input: (Ov, v1, v2, v3)  centre and 3 base vectors in v frame

• Output: Frame transformation  4x4 homogeneous matrix

• 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-Registration-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 (just to get a hang of it :-)

The clinical problem: We are about to purchase a

new position tracking device that localizes small

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

beacons as fiducial markers for tracking a patient’s

head during neurosurgery. We want to integrate the

tracker in a neuro-navigation system for localizing

intracranial hemorrhage, like the white blood clot

shown in the CT image (Fig 1, left). For treatment,

we will drill a small burr hole through the cranium,

enter a thin tube through which we evacuate the

hemorrhage (Fig 1, right). The hemorrhage is often

superficial, like in the figure. In such cases, the

critical element of the surgery is proper placement

of the burr hole, identified in the CT image. The

required surgical targeting accuracy for drilling burr

hole is often rather lenient; in the case shown in the

figure, it is about 5.0 mm. But intracranial hemorrhage is an emergency procedure, the clot must be

evacuated quickly, otherwise the danger of neurological deficit starts skyrocketing. Often there is no time

to transfer the patient to a proper operating room or there is no operating room available, and we need to

perform the procedure at bedside.

In the neuro-navigation system, we will place 3 markers on the patient’s head prior to CT imaging. We

will localize these markers in the CT image space during surgical planning and we will again localize the

markers again during surgery, from which we compute the planned location of the burr hole for drilling.

(Refer to the slide deck: Math Primer, Part 3: Frame Transformations, slide on “Rigid body registration.

Use case: mapping a target from pre-op imaging space to surgical navigation space.)

In a bedside setup, however, we want to use a lightweight and inexpensive tracker. Such a device will be

much less accurate than a high-end tracking device that we typically use in a fully qualified operating

room. This cheap tracking system may have substantial error in localizing the fiducial markers. This error,

which is called Fiducial Localization Error (FLE), causes the target (i.e. the burr hole) to be inaccurately

localized during surgery.

Objective: We must determine the minimum requited accuracy of the new tracking system. In other words,

we need to determine the maximum affordable fiducial localization error (FLE) without compromising

the required surgical targeting accuracy.

Simulated ground-truth setup: First, we will design a simplified representation of the surgical scene. It

needs to be mathematically and practically sufficiently general, yet simple enough for us to sketch it up

on paper. Let us place the tracker in the canonical home, (0,0,0) aligned with the home base (ref. Homer

in his armchair.) Let us model the patient’s head as a sphere of 100 mm radius, placed in (0,0,-300), with

the top of the head in the positive z direction. Let us place 3 markers on the head in A(100,0,-300),

B(-50,86.6,-300), C(-50,-86.6,-300).

Fig 1: Left: A superficial intracranial hemorrhage

(white blood clot) in computed tomography (CT)

imaging and the location of the planned burr hole.

Right: Removal of intracranial hemorrhage in the

operating room.

Page 4 of 4

Target selection: For target registration error, the position of a target point relative to the fiducial markers

matters a great deal. Your first task is to determine the most error-prone target location in the head. Since

we always want to account for the worst case, we will further examine only the most error-prone target

location. Explain your reasoning. Make a sketch of the surgical scene (2 pts).

Now, we are ready to start localizing this target point (Pt) with our inaccurate jittery tracker and analyze

the resulting targeting error.

We will define the Target Registration Error (TRE) as the difference between two observations of the

patient’s head and Pt target point within: the ideal error-free ground-truth observation and an inaccurate

error-ridden observation. (Refer to the slide deck: Math Primer, Part 3: Frame Transformations, slide on

“Rigid body registration. Use case: Inaccurate jittery tracker”.)

Develop a MATLAB program for the following:

Ground-truth observation: Compute the error-free ground-truth observation of the Pt target. Use the

library functions that you have just developed. Check the correctness of your result in the sketch you made

earlier. (3 pts)

Simulated observations (6 pts)

The second observation of the Pt target will carry some simulated error. Let us assume that we do not

know the true distribution of the fiducial localization error (FLE). Alas, we must assume the worst case

and over-estimate the error - because we want our simulation to be stricter than reality, for we must never

pass a faulty system to clinical use. To overestimate fiducial localization error (FLE), we will simulate it

as vector of random direction of a given magnitude FLE. Starting from zero error (FLE=0), we will

gradually increase FLE by a small deltaFLE increment, such as 0.5 mm. We will keep increasing FLE,

until the target registration error (TRE) becomes solidly larger than the allotted TREmax, which is 5.0

mm in our case.

• Start observing the ABC fiducial markers. Displace the ABC markers, each by a different random

vector of FLE magnitude. Compute the erroneous observation of Pt, using the library functions

that you have just developed. Keep observing the ABC markers for a statistically large-enough

number of times, typically N>20. (This simulation is not computationally expensive, so you can

easily run it higher.) In each run, compute the TRE.

o If TRE is above TREmax, quit the simulation, you failed the clinical requirement.

o Otherwise continue, finish off your cycle.

• Increment the magnitude of FLE by deltaFLE and continue the simulation.

Analysis (3 pts)

Your final task is to analyze the results. Plot TREs as a function of FLE. Inspect the plot, explain your

findings, and make a well-reasoned recommendation for the neurosurgeon for the tracking system.

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) Frame-Transformation-to-Home

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, sketch 2

Ground-truth observation 3

Simulated observations 6

Analysis 3

Total 14

TOTAL 100

Page 1 of 1

General Instructions for CISC/CMPE 330 assignments

• Always explain how you solve a problem. Use drawings, math formulas, text, block

diagram, pseudo code - anything that you find them appropriate to convey your

ideas. I must know that you understand what you are doing, and I must be able to

follow your reasoning. Depending on the quality and depth of your reasoning and

discussion or results you may pick (or lose) lots of points.

• Write proper header and richly comment your code. Cleary identify the input and

output. There is no such thing as too much comment. Good style and neatness will

earn you valuable points. The lack of these will cause reduction.

• Consider the validity (or deformity) of the input data, incomplete testing will lead to

deduction of marks.

• Test each module, construct several test cases with known ground-truth answer.

• Write testing m file(s) for each module or problem.

• Capture the output, to show that your program does what it is supposed to do.

Make plots and tables when requested or when they make sense. Add explanation

text as you see it useful.

• Do not use exponential number format. Use decimal digits sensibly and consider

what is precision is practical for the given problem. Generally, resolution finer than

0.1 millimeter is not practically achievable in such a surgical navigation system, so

this should be your limit. Use decimal floating-point format in your outputs.

• Create MATLAB functions for recurring tasks

• Submit the m files and the captured output file, as well as any drawing, or

supplemental information you feel relevant.

• Using source control, such as a private github repository, is recommended but not

required.

• Submit all in one zip file named LastName_FistName_AsnX_CISC330.zip

• Put all .m files in the same folder

• Always include a main.m that calls all other files with proper. Do not require

entering parameters from the command line.

• Always include a PDF report answering all questions and providing the required

analysis of the results, as well as for any drawing, writing, image, etc. that you find

appropriate but does not fit in code comments. (No long essays are needed, and

all questions can be answered in a couple of sentences.

• If you include images, limit the size. No need for high-resolution images.