LinesSpherePlanesTriangles/직선·구·평면·삼각형

Geometric Primitives

What’s a Geometric Primitive
A geometric primitive is a simple geometric object, among which we will include the:

• Ray
• Line
• Plane
• Sphere
• Polygon

Representation Forms
There are three basic ways to represent a geometric primitive

• Implicit form
  • a Boolean function f(x,y,z)
  • x²+y²+z² = 1
• Parametric form
  • Express x, y, z as functions of another parameter or parameters) that vary between certain limits.
  • x(t) = cos 2πt
  • y(t) = sin 2πt
  • As t varies through 0 ≤ t ≤ 1,
• “Straightforward” form
  • Nonmathematical; no equations.
  • “A unit sphere centered at the origin.”

Different forms for different uses.

Degrees of Freedom

• Degrees of freedom: the minimum number of “pieces of information” which are required to describe the entity unambiguously.
• For each geometric primitive, some representation forms use more numbers than others.
• Usually due to a redundancy that could be eliminated by assuming the appropriate constraint, such as a vector having unit length.

---

LINES AND RAYS

Lines and Rays
Classical definitions:

• A line extends infinitely in two directions.
• A line segment is a finite portion of a line that has two endpoints.
• A ray is half of a line that has an origin and extends infinitely in one direction.

Computer graphics definition:

• A ray is a directed line segment.

The Importance of Being Ray

• A ray will have an origin and an endpoint.
• A ray defines a position, a finite length, and (unless it has zero length) a direction.
• A ray also defines a line and a line segment (containing it).
• Rays are important in computational geometry and computer graphics.

Two Points Rep. of Rays
Give the two points that are the ray origin and the ray endpoint: porg and pend.

Parametric Rep. of Rays
Three equations in t:
x(t) = x0 + t Δx
y(t) = y0 + t Δy
z(t) = z0 + t Δz

The parameter t is restricted to 0 ≤ t ≤ 1.

Vector Notation
Alternatively, use vector notation:
p(t) = p0 + td

where:
p(t) = [ x(t) y(t) z(t) ]
p0 = [ x0 y0 z0 ]
d = [ Δx Δy Δz ]

Let d be a unit vector.
Vary t in the range [0, l], where l is the length of the ray.
p(0) = p0 is the origin point.
p(l) = p0 + ld is the end point.
d is the ray’s direction.

Lines in 2D
Implicit representation of a line:
ax + by = d
Some people prefer the longer:
ax + by + d = 0

Vector notation: let n = [ a b ], p = [ x y ] and use dot product:
p·n = d

Special Case of the Line

• Make n a unit vector (scale d appropriately.)
• Then d is the signed distance from the origin to the line measured perpendicular to the line (parallel to n).
• By signed distance, we mean that d is positive if the line is on the side of the origin that the normal points towards.
• As d increases, the line moves in the direction of n.

Variation of the Line

• Give a point q that is on the line, rather than the distance to the origin.
• Any point will do.
• The direction of the line is described using a normal to the line n, as before.

Slope-Intercept Form
y = mx + b
m is the slope of the line, expressed as a ratio of rise over run:

• For every rise unit that we move up,
• we move run units to the right.

b is the y-intercept

• Substituting x = 0 shows that the line crosses the y-axis at y = b.

The slope of a horizontal line is zero.
A vertical line has infinite slope and cannot be represented in slope-intercept form since the implicit form of a vertical line is x = k.

Yet Another Form

• One final way to define a line is as the perpendicular bisector of two points q and r.
• In fact, this is one of the earliest definitions of a line: the set of all points equidistant from two given points.

Some Line Conversions
Two points => parametric form
p0 = porg
d = pend – porg

Parametric form => two points
porg = p0
pend = p0 + d

Parametric ray => Implicit ray
a = dy
b = –dx
d = porgxdy – porgydx
ax + by = d

Two points Parametric form Implicit form

Some Line Conversions
Implicit form => slope-intercept form:
m = –a/b , b = d/b

y = mx + b
ax + by = d
Implicit form Slope-intercept form

Implicit form => normal and distance form:
p·n = d

a normal and a point q on line => normal and distance form
n = n
distance = n · q

---

SPHERES AND CIRCLES

Circles and Spheres

• A sphere is the set of all points that are a given distance from a given point.
• The distance from the center of the sphere to a point is known as the radius of the sphere.
• The straightforward representation of a sphere is its center c and radius r.

Implicit Representation
The implicit form of a sphere with center c and radius r is the set of points p such that:
|| p – c || = r.

Expanding this, if p = [ x y z ]:
(x – cx)² + (y – cy)² = r² (2D circle)
(x – cx)² + (y – cy)² + (z – cz)² = r² (3D sphere)

Some Measurements
For both circles and spheres,

• diameter D : D = 2r
• circumference C : C = 2πr = πD

The area of a circle is :
A = πr²

The surface area S and volume V of a sphere are:
S = 4πr²
V = 4πr³/3

Bounding Sphere

• A bounding sphere is often used in collision detection for fast rejection because the equations for intersection with a sphere are simple.
• Rotating a sphere does not change its shape, and so a bounding sphere can be used for an object regardless of the orientation of the object.

For collision detection, p is inside the sphere if:
|| p – c || ≤ r.

Bounding Sphere computation:

• find c
• For all points, compute distance to c
• The maximum value is r

Bounding Boxes

Types of Bounding Box

• Like spheres, bounding boxes are also used in collision detection.
• AABB: axially aligned bounding box. sides aligned with world axes
• OABB: object aligned bounding box. sides aligned with object axes
• Axially aligned bounding boxes are simpler to create and use.

Points In AABB
The points (x y z) inside an AABB satisfy:
xmin ≤ x ≤ xmax
ymin ≤ y ≤ ymax
zmin ≤ z ≤ zmax

Two special corner points are:
pmin = [xmin ymin zmin]
pmax = [xmax ymax zmax]

The center point c is given by:
c = (pmin+ pmax)/2

AABB Size & Radius
The size vector s is the vector from pmin to pmax and contains the width, height, and length of the box:
s = pmax – pmin

The radius vector r is the vector from the center to pmax:
r = pmax – c = s/2

Defining an AABB

• To unambiguously define an AABB requires only two of the five vectors pmin, pmax, c, s, and r.
• Other than the pair s, r, any pair may be used.
• Some representation forms are more useful in particular situations than others.
• A good idea to represent a bounding box using pmin, pmax, since in practice these are needed far more frequently that c, s, and r.
• Of course, computing any of these three from pmin, pmax is very fast.

AABBs vs Spheres

• Computing the optimal AABB for a set of points is easy and takes linear time.
• Computing the optimal bounding sphere is a much more difficult problem.
• For many objects that arise in practice, AABBs usually provide a “tighter” bounding volume, and thus better trivial rejection.

Which is Best?
Of course, for some objects, the bounding sphere is better.
In the worst case, AABB volume will be just under twice the sphere volume.
However, when a sphere is bad, it can be really bad.

Transforming an AABB
When you transform an object, its AABB changes.

1. Can re-compute a new AABB from the transformed object. => This is slow.
2. Faster to transform the AABB itself. => But the transformed AABB may not be an AABB.

• So, transform the AABB,
• and compute a new AABB from the transformed box.
  => There are some small but significant optimizations for computing the new AABB.

Downside of transforming the AABB
Transforming an AABB may give you a larger AABB than recomputing the AABB from the object

Exercise
Five points v1 = (7, 11,−5), v2 = (2, 3, 8), v3 = (−3, 3, 1), v4 = (−5,−7, 0), v5 = (6, 3, 4).
(a) Find pmin and pmax of the AABB.
(b) List the eight vertices of the AABB.
(c) Find the center point c and size vector s of the AABB.

---

Planes

Planes

• A plane in 3D is the set of points equidistant from two points.
• A plane is perfectly flat, has no thickness, and extends infinitely.
• Planes are very common tools in video games.
• The implicit form of a plane is given by all points p = (x, y, z) that satisfy the plane equation:

ax + by + cz = d
p·n = d
where n = [a, b, c].

• We often consider a plane to have a front and a back side.
• The front of the plane is the side that n points away from.

Plane from 3 Points

• Three non-collinear points p1, p2, p3 can define a unique plane
• To compute n and d for a Plane Passing Thru 3 Pts
  • In a left-handed coordinate system, we assume that p1, p2, p3 are listed in clockwise order when viewed from the front side of the plane.

e3 = p2 – p1
e1 = p3 – p2
n = e3 x e1
d = p1·n

Distance from Point to Plane

• Imagine a plane and a point q that is not in the plane.
• There exists a point p that lies in the plane and is the closest point in the plane to q.
• Clearly, the vector from p to q is perpendicular to the plane, and thus is of the form an for some scalar a.
• If the plane normal n is a unit vector, then the distance from p to q (and thus the distance from q to the plane) is simply a.

p + an = q
(p + an) · n = q · n
p · n + (an)·n = q · n
d + a = q · n
a = q · n – d

Intersection of ray and plane
q = p0 + td
q·n = (p0+td)·n = f
p0·n + t d·n = f
t = (f – p0·n)/(d·n)
Therefore, q = p0 + (f – p0·n)/(d·n) d

n = [a,b,c]
ax+by+cz=f

Exercise
The three vertices of a triangle in clockwise order are (6, 10,−2), (3,−1, 17), (−9, 8, 0).
(a) Find the equation of the plane containing this triangle.
(b) Determine whether the point (3, 4, 5) is in front or back of the plane.
(c) Find the distance from the point (3, 4, 5) to the plane.

---

TRIANGLES

Basic Properties of a Triangle

• A triangle is defined by listing three vertices.
• In a left-handed coordinate system, we list the points in clockwise order when viewed from the front side of the triangle; v1, v2, v3.
• A triangle lies in a plane, and the equation of this plane (the normal n and distance to origin d) is important in a number of applications.

Let li denote the length of ei for i = 1, 2, 3.

Area of a Triangle
The area of a triangle of base b and perpendicular height (also called altitude) h is given by
A = bh/2.

• If the altitude is not known, then Heron's formula can be used, which requires only the lengths of the three sides.
• Let s equal one half the perimeter (also known as the semiperimeter).
• Then the area A is given by:

Area from Point Coordinates 1

• Let's tackle this problem in 2D.
• For each edge of the triangle, compute the signed area of the trapezoid
• By signed area, we mean that the area is positive if the edge points from left to right, and negative otherwise.
• There will always be at least one positive edge and at least one negative edge. A vertical edge has zero area.

Given two edge vectors from the triangle, e1 and e2, the area of the triangle is given by:
A = ||e1 x e2||/2.

Area from Point Coordinates 2
The formulas for the areas under each edge are:

Barycentric Space

• Even though we certainly use triangles in 3D, the surface of a triangle lies in a plane and is inherently a 2D object.
• A coordinate space that is related to the surface of the triangle? => Barycentric space
• Any point in the plane of the triangle can be expressed as weighted average of the vertices.
• Many practical problems that arise when making video games, such as interpolation and intersection, can be solved using barycentric coordinates.

Parametric Expression of Line
p(t) = p0 + td, 0 ≤ t ≤ 1
If we express p in terms of p0 and p1:
p(t) = (1 – t)p0 + t p1
Thus, p is (1 – t, t) along the line defined by p0 and p1.

Barycentric Coordinates
Barycentric coordinates (b1, b2, b3) correspond to the point b1v1 + b2v2 + b3v3.

Observations

• The triangle vertices in barycentric space: (1,0,0) to v1, (0,1,0) to v2, and (0,0,1) to v3.
• All points on the side opposite a vertex → a zero barycentric coordinate corresponding to that vertex
• Any point in the plane → if inside the triangle, barycentric coordinates are between 0 and 1.
• If outside, at least one coordinate is negative.

Applications of Barycentric Coordinates 1

• Parameters (or computed) per vertex: texture coordinates, surface normals, colors, lighting values, etc.
• To determine the interpolated value at an arbitrary location within the triangle.

Applications of Barycentric Coordinates 2

• Ray-triangle Intersection testing
  1. Find intersection of ray with plane containing the triangle
  2. Determine if the intersection point is inside or outside the triangle
• If all barycentric coordinates are positive → inside the triangle.

Barycentric from Cartesian Coords

• Given Cartesian coordinates of v1, v2, v3 and point p, find b1, b2, b3.
• Barycentric coordinates (b1, b2, b3) correspond to b1v1+ b2v2 + b3v3.
• This gives 3 equations in 3 unknowns.
• Solving yields the barycentric coordinates.

Area Relationships

• Denominator: twice area of the triangle.
• Numerator: twice the area of sub-triangle Ti.
• bi = A(Ti)/A(T) for i = 1,2,3.
• Applies even if p is outside the triangle.
• If vertices are collinear, no barycentric coordinates.

---

한국어

 

기하학적 기본 요소 (Geometric Primitives)

기하학적 기본 요소란 단순한 기하학적 객체를 의미하며, 여기에 포함되는 것은 다음과 같습니다.

• 광선(Ray)
• 직선(Line)
• 평면(Plane)
• 구(Sphere)
• 다각형(Polygon)

표현 방식
기하학적 기본 요소를 표현하는 방법은 세 가지가 있습니다.

• 암시적(Implicit) 표현
  • 불리언 함수 f(x,y,z)
  • 예: x²+y²+z² = 1
• 매개변수(Parametric) 표현
  • x, y, z를 일정 범위에서 변하는 매개변수의 함수로 표현
  • x(t) = cos 2πt
  • y(t) = sin 2πt
  • 여기서 0 ≤ t ≤ 1
• 직관적(Straightforward) 표현
  • 비수학적이고 방정식이 없는 방식
  • 예: “원점에 중심을 둔 단위 구”

각 표현 방식은 활용 목적에 따라 다르게 사용됩니다.

자유도(Degrees of Freedom)

• 자유도란 어떤 대상을 명확하게 설명하는 데 필요한 최소한의 정보 조각을 의미합니다.
• 기하학적 기본 요소마다 표현 방식에 따라 필요한 수치가 더 많을 수도 있습니다.
• 보통 불필요한 중복 때문인데, 예를 들어 벡터의 길이를 1로 정하면 불필요한 정보를 줄일 수 있습니다.

---

직선과 광선

직선과 광선의 정의

• 직선(Line)은 양쪽으로 무한히 뻗어 있는 선입니다.
• 선분(Line segment)은 두 개의 끝점을 가진 직선의 유한 부분입니다.
• 광선(Ray)은 한쪽 끝에서 시작해 한 방향으로 무한히 뻗는 선입니다.

컴퓨터 그래픽스에서의 정의

• 광선은 방향성을 가진 선분입니다.

광선의 중요성

• 광선은 시작점과 끝점을 가집니다.
• 광선은 위치, 유한한 길이, 그리고 (길이가 0이 아닌 경우) 방향을 정의합니다.
• 광선은 직선과 그를 포함하는 선분 또한 정의합니다.
• 광선은 계산 기하학 및 컴퓨터 그래픽스에서 매우 중요합니다.

광선의 두 점 표현

• 광선의 시작점(porg)과 끝점(pend)을 지정하여 표현할 수 있습니다.

광선의 매개변수 표현
x(t) = x0 + t Δx
y(t) = y0 + t Δy
z(t) = z0 + t Δz

여기서 t는 0 ≤ t ≤ 1 범위로 제한됩니다.

벡터 표기법
벡터로는 다음과 같이 표현됩니다.
p(t) = p0 + td

여기서,
p(t) = [ x(t) y(t) z(t) ]
p0 = [ x0 y0 z0 ]
d = [ Δx Δy Δz ]

d가 단위 벡터라고 하면, t를 [0, l] 범위에서 변화시킬 수 있습니다.
p(0) = p0 는 시작점,
p(l) = p0 + ld 는 끝점이 됩니다.
d는 광선의 방향입니다.

2차원 직선
직선의 암시적 표현은 다음과 같습니다.
ax + by = d
또는 ax + by + d = 0

벡터 표기법으로는, n = [a b], p = [x y]라 하면 내적을 이용해:
p·n = d

특수한 직선의 경우

• n을 단위 벡터로 만들면, d는 원점에서 직선까지의 수직 거리(법선 방향)입니다.
• 부호 있는 거리(signed distance)로 정의하며, d가 양수일 경우 직선은 원점에서 법선 방향 쪽에 위치합니다.
• d가 커질수록 직선은 n의 방향으로 이동합니다.

직선의 다른 표현

• 원점에서의 거리 대신 직선 위 한 점 q를 주어도 됩니다.
• 직선의 방향은 법선 벡터 n으로 표현됩니다.

기울기-절편(Slope-Intercept) 형태
y = mx + b

• m은 기울기 (rise/run)
• b는 y절편

수평선의 기울기는 0이며, 수직선은 기울기가 무한대여서 slope-intercept 형태로 표현할 수 없습니다.

또 다른 정의

• 직선은 두 점 q, r의 수직 이등분선으로 정의할 수도 있습니다.
• 이는 “두 점에서 동일한 거리에 있는 모든 점의 집합”이라는 고전적 정의입니다.

직선의 변환

• 두 점으로부터 → 매개변수 형태
• 매개변수 형태 → 두 점
• 매개변수 광선 → 암시적 광선
• 암시적 → 기울기-절편
• 암시적 → 법선-거리 형태

---

구와 원

구와 원의 정의

• 구는 한 점에서 일정한 거리에 있는 모든 점의 집합입니다.
• 중심에서 한 점까지의 거리를 반지름(radius)이라고 합니다.
• 구의 간단한 표현은 중심 c와 반지름 r입니다.

암시적 표현
구의 암시적 방정식은:
|| p – c || = r

p = [x y z]라 하면,
2D 원: (x – cx)² + (y – cy)² = r²
3D 구: (x – cx)² + (y – cy)² + (z – cz)² = r²

측정 값

• 지름 D = 2r
• 원둘레 C = 2πr = πD
• 원의 넓이 A = πr²
• 구의 표면적 S = 4πr²
• 구의 부피 V = 4πr³/3

경계 구 (Bounding Sphere)

• 충돌 감지에서 빠른 연산을 위해 자주 사용됩니다.
• 구는 회전에 영향을 받지 않으므로, 어떤 물체든 방향과 관계없이 경계 구로 표현할 수 있습니다.
• 판정: || p – c || ≤ r 이면 내부에 있음.

경계 박스 (Bounding Box)

• AABB: 축 정렬 경계 박스 (축과 평행)
• OABB: 객체 정렬 경계 박스 (객체 좌표축과 정렬)
• AABB가 더 단순하고 많이 쓰임.

AABB의 특징

• 점 (x,y,z)가 xmin ≤ x ≤ xmax, ymin ≤ y ≤ ymax, zmin ≤ z ≤ zmax 범위를 만족하면 내부에 있음.
• pmin, pmax로 정의 가능.
• 중심 c = (pmin + pmax)/2
• 크기 벡터 s = pmax – pmin
• 반지름 벡터 r = s/2

AABB vs 구

• 최적 AABB는 선형 시간에 구할 수 있음.
• 최적 구는 더 어렵고 계산량이 많음.
• 실제로는 AABB가 더 타이트하게 감쌀 때가 많음.

변환 시 AABB

• 객체를 변환하면 AABB도 변합니다.
• 재계산하거나 변환된 박스를 다시 감싸는 새로운 AABB를 만들어야 함.
• 단, 변환 후 다시 만드는 경우 더 큰 박스가 될 수 있습니다.

연습문제
v1 = (7, 11, −5), v2 = (2, 3, 8), v3 = (−3, 3, 1), v4 = (−5, −7, 0), v5 = (6, 3, 4).
(a) AABB의 pmin, pmax를 구하라.
(b) 꼭짓점 8개를 나열하라.
(c) 중심점 c와 크기 벡터 s를 구하라.

---

평면 (Planes)

• 평면은 3D에서 두 점에서 같은 거리에 있는 점들의 집합입니다.
• 완전히 평평하고 두께가 없으며 무한히 확장됩니다.
• 게임 그래픽에서 자주 사용됩니다.

평면의 암시적 표현
ax + by + cz = d
p·n = d
여기서 n = [a b c]

평면에는 앞(front)과 뒤(back) 개념이 있으며, 법선 n이 향하는 쪽이 앞입니다.

세 점으로 정의하는 평면
서로 일직선이 아닌 세 점 p1, p2, p3는 유일한 평면을 정의합니다.
n = (p2 – p1) × (p3 – p2)
d = p1 · n

점과 평면 사이 거리
q가 평면 위에 없다고 할 때, q와 평면 사이의 최단 거리는 q·n – d 입니다.

광선과 평면의 교차
q = p0 + td
t = (f – p0·n) / (d·n)
q = p0 + (f – p0·n)/(d·n) d

연습문제
삼각형 꼭짓점: (6,10,−2), (3,−1,17), (−9,8,0)
(a) 평면 방정식을 구하라.
(b) 점 (3,4,5)가 앞/뒤 어디에 있는가?
(c) 점 (3,4,5)와 평면의 거리를 구하라.

---

삼각형 (Triangles)

• 삼각형은 세 점을 나열해 정의합니다.
• 좌표계 기준 시계방향으로 나열: v1, v2, v3
• 삼각형은 평면 위에 있으며, 그 평면의 법선과 원점까지의 거리가 중요합니다.

삼각형 넓이

• 밑변 b, 높이 h → A = bh/2
• 높이를 모를 경우, 헤론 공식 사용 가능:
  s = 둘레/2
  A = √(s(s – a)(s – b)(s – c))

벡터로 구하는 넓이
A = || e1 × e2 || / 2

Barycentric 좌표

• 삼각형 평면상의 한 점은 세 꼭짓점의 가중 평균으로 표현할 수 있습니다.
• 좌표 (b1,b2,b3) → 점 = b1v1 + b2v2 + b3v3
• 삼각형 내부라면 0 ≤ bi ≤ 1
• 외부라면 하나 이상이 음수

활용

• 보간 (색, 텍스처 좌표, 법선 등)
• 광선-삼각형 교차 검사

면적 기반 해석
bi = A(Ti) / A(T)

---