Programming – Page 2 – Form Follows Energy

2008/04/122016/09/19

[webpage]Graphics Gems Repository

컴퓨터 그래픽 분야에서 광범위하게 사용되는 핵심적인 알고리즘과 그를 구현하는 코드가 공개된 사이트.
Graphics Gems 시리즈 책에 실려있는 모든 코드가 고스란히 정리되고 공개되어 있다.
해석프로그램인 SolarView에서 사용한 알고리즘 중 일부는 여기에서 제공한 것을 번역 또는 변환해서 사용하였다.

주소 : http://tog.acm.org/GraphicsGems/
내용 :
2D Geometry
2D Rendering
3D Geometry
3D Rendering
C Utilities
Curves and Surfaces
Frame Buffer Techniques
Image Processing
Matrix Techniques
Modeling and Transformations
Numerical and Programming Techniques
Radiosity
Ray Tracing

이 책은 알고리즘, 프로그램, 그래픽 프로그래머들에 필요한 수학적인 기술들을 담고 있다. 즉, 그래픽 프로그래머들이 프로그램을 작성할 때 도움을
주고자 만들어졌다. 이 책에 있는 기사들은 연구 논문이 아니며, 저널에 실린 것들과 컨퍼런스에서 나온 결과를 담고 있다. 수록된 내용들과
소스코드는 현재까지 모든 게임과 그래픽 전 분야에 걸쳐서 핵심적으로 사용되고 있는 것들이다. (교보문고 설명문 인용)

2008/04/102015/11/12

[webpage]Computational Geometry Algorithms Library

위치 : http://www.cgal.org/
내용 :
전산기하학에 필요한 알고리즘을 공개한 사이트. 아래는 사이트 내의 설명임
The goal of the CGAL Open Source Project is to provide
easy access to efficient and reliable geometric algorithms
in the form of a C++ library.
CGAL is used in various areas needing geometric computation, such as:
computer graphics, scientific visualization, computer aided design and
modeling, geographic information systems, molecular biology, medical imaging,
robotics and motion planning, mesh generation, numerical methods.

The Computational Geometry Algorithms Library
(CGAL), offers data
structures and algorithms like

triangulations (2D constrained triangulations and Delaunay triangulations in 2D and 3D),

Voronoi diagrams (for 2D and 3D points, 2D additively weighted Voronoi diagrams, and
segment Voronoi diagrams),

Boolean operations on polygons and
polyhedra,

arrangements of curves and their applications (2D and 3D envelopes, Minkowski sums),

mesh generation (2D Delaunay mesh generation and 3D surface mesh generation, skin surfaces),

geometry processing (surface mesh simplification,
subdivision and parameterization, as well as estimation of local differential properties,
and approximation of ridges and umbilics),
alpha shapes,

convex hull algorithms (in 2D, 3D and dD),

operations on polygons (straight skeleton and offset polygon),

search structures (kd trees for nearest neighbor search, and range and segment trees),

interpolation (natural neighbor interpolation and placement of streamlines),

shape analysis, fitting, and distances (smallest enclosing sphere of points or spheres, smallest enclosing ellipsoid of points,
principal component analysis), and

kinetic data structures.

2008/03/31

[webpage]Comp.Graphics.Algorithms Frequently Asked Questions

유즈넷 Comp.Graphics.Algorithms에서 자주묻는질문(FAQ)를 정리해놓은 사이트

0. General Information

0.01:
Charter of comp.graphics.algorithms
0.02:
Are the postings to comp.graphics.algorithms archived?
0.03:
How can I get this FAQ?
0.04:
What are some must-have books on graphics algorithms?
0.05:
Are there any online references?
0.06:
Are there other graphics related FAQs?
0.07:
Where is all the source?

1. 2D Computations:
Points, Segments, Circles, Etc.

1.01:
How do I rotate a 2D point?
1.02:
How do I find the distance from a point to a line?
1.03:
How do I find intersections of 2 2D line segments?
1.04:
How do I generate a circle through three points?
1.05:
How can the smallest circle enclosing a set of points be
found?
1.06:
Where can I find graph layout algorithms?

2. 2D Polygon
Computations

2.01:
How do I find the area of a polygon?
2.02:
How can the centroid of a polygon be computed?
2.03:
How do I find if a point lies within a polygon?
2.04:
How do I find the intersection of two convex polygons?
2.05:
How do I do a hidden surface test (backface culling) with
2d points?
2.06:
How do I find a single point inside a simple polygon?
2.07:
How do I find the orientation of a simple polygon?

3. 2D Image/Pixel
Computations

3.01:
How do I rotate a bitmap?
3.02:
How do I display a 24 bit image in 8 bits?
3.03:
How do I fill the area of an arbitrary shape?
3.04:
How do I find the ‘edges’ in a bitmap?
3.05:
How do I enlarge/sharpen/fuzz a bitmap?
3.06:
How do I map a texture on to a shape?
3.07:
How do I detect a ‘corner’ in a collection of points?
3.08:
Where do I get source to display (raster font format)?
3.09:
What is morphing/how is it done?
3.10:
How do I quickly draw a filled triangle?
3.11:
D Noise functions and turbulence in Solid texturing.
3.12:
How do I generate realistic sythetic textures?
3.13:
How do I convert between color models (RGB, HLS, CMYK,
CIE etc)?
3.14:
How is “GIF” pronounced?

4. Curve Computations

4.01:
How do I generate a bezier curve that is parallel to
another bezier?
4.02:
How do I split a bezier at a specific value for t?
4.03:
How do I find a t value at a specific point on a bezier?
4.04:
How do I fit a bezier curve to a circle?

5. 3D computations

5.01:
How do I rotate a 3D point?
5.02:
What is ARCBALL and where is the source?
5.03:
How do I clip a polygon against a rectangle?
5.04:
How do I clip a polygon against another polygon?
5.05:
How do I find the intersection of a line and a plane?
5.06:
How do I determine the intersection between a ray and a
polygon?
5.07:
How do I determine the intersection between a ray and a
sphere?
5.08:
How do I find the intersection of a ray and a bezier
surface?
5.09:
How do I ray trace caustics?
5.10:
What is the marching cubes algorithm?
5.11:
What is the status of the patent on the “marching
cubes” algorithm?
5.12:
How do I do a hidden surface test (backface culling) with
3d points?
5.13:
Where can I find algorithms for 3D collision detection?
5.14:
How do I perform basic viewing in 3d?
5.15:
How do I optimize a 3D polygon mesh?
5.16:
How can I perform volume rendering?
5.17:
Where can I get the spline description of the famous
teapot etc.?
5.18:
How can the distance between two lines in space be
computed?
5.19:
How can I compute the volume of a polyhedron?
5.20:
How can I decompose a polyhedron into convex pieces?
5.21:
How can the circumsphere of a tetrahedron be computed?
5.22:
How do I determine if two triangles in 3D intersect?

6. Geometric Structures
and Mathematics

6.01:
Where can I get source for Voronoi/Delaunay
triangulation?
6.02:
Where do I get source for convex hull?
6.03:
Where do I get source for halfspace intersection?
6.04:
What are barycentric coordinates?
6.05:
How do I generate a random point inside a triangle?
6.06:
How do I evenly distribute N points on (tesselate) a
sphere?
6.07:
What are coordinates for the vertices of an icosohedron?
6.08:
How do I generate random points on the surface of a
sphere?
6.09:
What are Plücker coordinates?

7. Contributors

7.01:
How can you contribute to this FAQ?
7.02:
Contributors. Who made this all possible.

2008/02/222015/12/12

DXF를 읽어오는 모듈을 정리

과거 동적배열로 된 변수들을 Generic.List와 Generic.Dictionary로 변경하였다. 파일 읽는 시간이 놀랍게 줄었다.
리스트와 딕셔너리도 마치 동적배열처럼 사용할 수 있다.

'옛날 코드
Dim DXFEntities() As SV_DXFEntity
ReDim Preserve DXFEntities(k)
DXFEntities(k) = New SV_DXFEntity

'옛날 코드

Dim DXFEntities() As SV_DXFEntity

ReDim Preserve DXFEntities(k)

DXFEntities(k) = New SV_DXFEntity

'개체 클래스
Public Class SV_DXFEntity
Private m_Type As String '자료명
Private m_CodeValue As Generic.Dictionary(Of Integer, String)
'
Public Sub New()
m_CodeValue = New Generic.Dictionary(Of Integer, String)
End Sub
Default Public Property CodeValue(ByVal groupCode As Integer) As String
Get
Return m_CodeValue(groupCode)
End Get
Set(ByVal value As String)
m_CodeValue(groupCode) = value
End Set
End Property
Public Property Type() As String
Get
Return m_Type
End Get
Set(ByVal value As String)
m_Type = value
End Set
End Property
Public Sub Add(ByVal myCode As Integer, ByVal myValue As String)
If m_CodeValue.ContainsKey(myCode) Then Exit Sub
m_CodeValue.Add(myCode, myValue)
End Sub

End Class

'개체 클래스

Public Class SV_DXFEntity

Private m_Type As String '자료명

Private m_CodeValue As Generic.Dictionary(Of Integer, String)

Public Sub New()

m_CodeValue = New Generic.Dictionary(Of Integer, String)

End Sub

Default Public Property CodeValue(ByVal groupCode As Integer) As String

Get

Return m_CodeValue(groupCode)

End Get

Set(ByVal value As String)

m_CodeValue(groupCode) = value

End Set

End Property

Public Property Type() As String

Get

Return m_Type

End Get

Set(ByVal value As String)

m_Type = value

End Set

End Property

Public Sub Add(ByVal myCode As Integer, ByVal myValue As String)

If m_CodeValue.ContainsKey(myCode) Then Exit Sub

m_CodeValue.Add(myCode, myValue)

End Sub

End Class

'엔티티를 원소로하는 리스트 선언
Dim DXFEntities As Generic.List(Of SV_DXFEntity)

1 2	'엔티티를 원소로하는 리스트 선언 Dim DXFEntities As Generic.List(Of SV_DXFEntity)

2008/02/18

Structure와 Class

선택사항을 저장하는 구조체를 만들었는데, 원본 구조체의 값이 변경되지 않았다. 구조체를 전달할 때, ByRef를 사용했음에도 불구하고 원본 값이 변경되지 않았다. 그래서 클래스로 변경하니 원본의 값이 변경되었다.
구조체를 사용해서 인자를 전달하면, 원본에는 아무런 변화가 없다.

2008/01/112021/01/06

연산자 Mod를 재발견

For문 등에서 배열을 계산하다보면, 인덱스의 범위를 넘어가는 경우가 생긴다. 이때 Mod[footnote]c/c++에서는 %연산자를 이용한다.[/footnote]를 사용하면 편리하다.

(출처 : http://local.wasp.uwa.edu.au/~pbourke/geometry/polyarea/)

'다각형면적구하기[vbnet]
Type tPoint
  X As Double
  Y As Double
End Type

Function PolygonArea(N As Integer, Points() As tPoint) As Double
  Dim i As Integer, j As Integer
  Dim area As Double
  area = 0
  For i = 0 To N - 1
    j = (i + 1) Mod N
    area = area + Points(i).X * Points(j).Y - Points(j).X * Points(i).Y
  Next i
  PolygonArea = area / 2
End Function

'다각형면적구하기[vbnet]

Type tPoint

X As Double

Y As Double

End Type

Function PolygonArea(N As Integer, Points() As tPoint) As Double

Dim i As Integer, j As Integer

Dim area As Double

area = 0

For i = 0 To N - 1

j = (i + 1) Mod N

area = area + Points(i).X * Points(j).Y - Points(j).X * Points(i).Y

Next i

PolygonArea = area / 2

End Function

2008/01/112021/01/06

형변환 연산자

점은 위치 벡터로 해석할 수 있다. 곧 점과 벡터는 서로 밀접한 관련이 있다. 표현되는 형식도 비슷하다. 이를 코드에서 어떻게 표현할 것인가가 문제였다. 형변환 연산자를 정의하므로 해결할 수 있었다.
형변환 연산자를 정의해 놓으면, 자동으로 형을 변환하여 계산하게 된다. 이야호!
아래의 내용은 점을 벡터로 확대변환을 하는 것이다. 이로써 인자를 벡터로 받는 곳에 그냥 점을 넘겨줘도 자동으로 형이 변환된다.

Public Shared Widening Operator CType(ByVal p As Point3D) As Vector3D
Return New Vector3D(p.X, p.Y, p.Z)
End Operator

Public Shared Widening Operator CType(ByVal p As Point3D) As Vector3D

Return New Vector3D(p.X, p.Y, p.Z)

End Operator

변환 프로시저에서 Widening 외에 Public Shared도 지정해야 한다.
확대 변환은 런타임에 항상 성공하며 데이터 손실이 없다. Single을 Double로 변환하거나 Char를 String으로 변환하거나 파생된 형식을 해당 기본 형식으로 변환하는 예를 들 수 있다. 파생된 형식에는 기본 형식의 모든 멤버가 포함되어 기본 형식의 인스턴스가 되므로 파생된 형식을 해당 기본 형식으로 변환하는 것은 확대 변환이다.
Option Strict가 On으로 설정되어 있는 경우에도 사용하는 코드에서 확대 변환에 대해 CType을 사용할 필요가 없다.

2008/01/07

부울 변수의 변환

Visual Basic에서 숫자 데이터 형식 값을 Boolean으로 변환하는 경우 0은 False가 되고 다른 모든 값은 True가 된다. Visual Basic에서 Boolean 값을 숫자 값으로 변환하는 경우 False는 0이 되고 True는 -1이 된다. 반면에 C/C++ 또는 Java는 True값을 1로 하기에 바로 수식 계산에 이용할 수 있다. 다른 언어의 이와 같은 코드를 바로 옮기면 오류가 발생할 수 있다.

2007/11/142021/01/06

연산자 중복정의(operator overload)

VB2005는 VB2003과 달리 연산자 중복정의를 할 수 있다. 다음은 행렬계산에서 곱셈(*)에 대한 연산자 중복정의를 한 코드이다.

Public Shared Operator *(ByVal mA As Matrix3D, ByVal mB As Matrix3D) As Matrix3D
    Dim i, j As Short
    Dim mC As Matrix3D = New Matrix3D
    For i = 0 To 3
        For j = 0 To 3
          mC.Data(i, j) = (mA.Data(i,0)*mB.Data(0,j))+(mA.Data(i,1)*mB.Data(1,j)) _
                        + (mA.Data(i,2)*mB.Data(2,j))+(mA.Data(i,3)*mB.Data(3,j))
        Next j
    Next i
    Return mC
End Operator

Public Shared Operator *(ByVal mA As Matrix3D, ByVal p1 As Point3D) As Point3D
  Dim p2 As Point3D = New Point3D()
  p2.X=(mA.Data(0,0)*p1.X)+(mA.Data(0,1)*p1.Y)+(mA.Data(0,2)*p1.Z)+(mA.Data(0,3)*1)
  p2.Y=(mA.Data(1,0)*p1.X)+(mA.Data(1,1)*p1.Y)+(mA.Data(1,2)*p1.Z)+(mA.Data(1,3)*1)
  p2.Z=(mA.Data(2,0)*p1.X)+(mA.Data(2,1)*p1.Y)+(mA.Data(2,2)*p1.Z)+(mA.Data(2,3)*1)
  Return p2
End Operator

Public Shared Operator *(ByVal mA As Matrix3D, ByVal mB As Matrix3D) As Matrix3D

Dim i, j As Short

Dim mC As Matrix3D = New Matrix3D

For i = 0 To 3

For j = 0 To 3

mC.Data(i, j) = (mA.Data(i,0)*mB.Data(0,j))+(mA.Data(i,1)*mB.Data(1,j)) _

+ (mA.Data(i,2)*mB.Data(2,j))+(mA.Data(i,3)*mB.Data(3,j))

Next j

Next i

Return mC

End Operator

Public Shared Operator *(ByVal mA As Matrix3D, ByVal p1 As Point3D) As Point3D

Dim p2 As Point3D = New Point3D()

p2.X=(mA.Data(0,0)*p1.X)+(mA.Data(0,1)*p1.Y)+(mA.Data(0,2)*p1.Z)+(mA.Data(0,3)*1)

p2.Y=(mA.Data(1,0)*p1.X)+(mA.Data(1,1)*p1.Y)+(mA.Data(1,2)*p1.Z)+(mA.Data(1,3)*1)

p2.Z=(mA.Data(2,0)*p1.X)+(mA.Data(2,1)*p1.Y)+(mA.Data(2,2)*p1.Z)+(mA.Data(2,3)*1)

Return p2

End Operator

2007/11/132015/12/12

이벤트 핸들러 로직을 공유하기

풀다운메뉴와 툴바의 메뉴는 형식이 다른 콘트롤이나, 동일한 기능을 하는 다른 콘트롤이다. 즉, 이 콘트롤들의 대표적인 이벤트인 클릭(click)을 통해서 동일한 일을 하게 된다. 이럴 때 클릭에 대한 이벤트를 공유한다. 과거 VB6에서는 콘트롤배열(control arrays)이란 개념으로 수행했으나, 이제는 컨트롤의 이벤트 메소드의 Handles문을 통하여 구현할 수 있다.

다음의 경우는 풀다운메뉴를 클릭했을 때(mnuWaldram.Click)와 툴바메뉴를 클릭했을 때(WaldramToolStripButton.Click)에 대한 이벤트 핸들러를 공유한 것이다.

Private Sub mnuWaldram_Click(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles mnuWaldram.Click, WaldramToolStripButton.Click
mnuWaldram.Checked = Not mnuWaldram.Checked
WaldramToolStripButton.Checked = mnuWaldram.Checked
My.Settings.WaldramChecked = mnuWaldram.Checked
End Sub

Private Sub mnuWaldram_Click(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles mnuWaldram.Click, WaldramToolStripButton.Click

mnuWaldram.Checked = Not mnuWaldram.Checked

WaldramToolStripButton.Checked = mnuWaldram.Checked

My.Settings.WaldramChecked = mnuWaldram.Checked

End Sub

Tag: Programming

[webpage]Graphics Gems Repository

[webpage]Computational Geometry Algorithms Library

[webpage]Comp.Graphics.Algorithms Frequently Asked Questions

Table of
Contents

0. General Information

1. 2D Computations:
Points, Segments, Circles, Etc.

2. 2D Polygon
Computations

3. 2D Image/Pixel
Computations

4. Curve Computations

4.01:
How do I generate a bezier curve that is parallel to
another bezier?
4.02:
How do I split a bezier at a specific value for t?
4.03:
How do I find a t value at a specific point on a bezier?
4.04:
How do I fit a bezier curve to a circle?

5. 3D computations

6. Geometric Structures
and Mathematics

7. Contributors

7.01:
How can you contribute to this FAQ?
7.02:
Contributors. Who made this all possible.

DXF를 읽어오는 모듈을 정리

Structure와 Class

연산자 Mod를 재발견

형변환 연산자

부울 변수의 변환

연산자 중복정의(operator overload)

이벤트 핸들러 로직을 공유하기