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
³Generate-Orthonormal-FUaPe´ URXWiQe, computed the body frame an arbitrary pose ³Y´ (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 ³displaced´ 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 ³Err´. 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 ³WUackiQg 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