Category Archive: 3D Geometry

Orthonormalize a Rotation Matrix

If you use a 3×3 R matrix to store the result of the multiplication of a series of rotation transformations, it could be the case that sometimes you end up with a matrix that is not orthonormal (i.e. det(R) != 1 and R.inv(R) != eye). In such cases, you need to re-orthonormalize the rotation matrix, …

Continue reading »

Computing the Distance Between a 3D Point and a Plücker Line

In order to solve an optimization problem with the goal of reducing the distance between a bunch of 3D points and lines, I was looking for the correct way of finding the distance between 3D points and a Plucker line representation. The Plucker line  passing through two lines  and  is defined as (for more details refer …

Continue reading »

CGAL Point in Polyhedron Algorithm

The “point in polygon” or “point in polyhedron” is a classic computer graphics problem. The goal is to determine whether a given point is inside a polygon (in 2D) or a polyhedron (in 3D). One solution to the problem is shooting a ray originating from the said point to an arbitrary direction and determine the number …

Continue reading »

3D Line Fitting in 5 Easy Steps with SVD

Least squares fit is used for 2D line fitting. In 3D space, the line is called 3D Orthogonal Distance Regression (ODR) line. The line can be easily found in 3D using SVD (singular value decomposition). Assuming that we have a bunch of 3D points (x0, y0, z0) to (xn, yn, zn), the algorithm (in MATLAB) is as follows: …

Continue reading »

Intersection of a Ray and a Line Segment in 3D

This page contains methods for performing various intersection tests. Although it does not have an entry for ray vs. line segment intersection, I tried the suggested ray vs. ray intersection test (page 782 of Real-Time Rendering 3rd Edition) and it did not work in my case. I looked around quite a bit and based on an …

Continue reading »