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.