Computational Geometry Assignment for CISC/CMPE 330
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. ground-
truth). 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. ground-
truth), 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. ground-
truth). 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 1 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 transformation4x4 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 2 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 3 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 yourfindings, and make a well-reasoned recommendation for the neurosurgeon for the tracking system.
Page 4 of 4
|
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
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.
