GAME DEV: tools programming
Marco Tarini
Parte 1:
Parte 1:
Parte 1:
Parte 1: tri-meshes
M a r c o T a r i n i ‧ [ G A M E - D E V ] ‧ V e r o n a ‧ 2 0 1 3
Tipi di mesh
• Mesh superficiali
– Mesh di triangoli (o tri-mesh, o simpliciali) – Mesh di quadrilateri (o quad-mesh)
– Mesh miste (quad e tri)
• Spesso, mesh prevalemtemente di quads (quad-dominant )
– Mesh di poligoni
• Mesh volumetriche
– Mesh tetraedrali (o simpliciali 3D)
– Mesh exaedrali (“di cubi”)
M a r c o T a r i n i ‧ [ G A M E - D E V ] ‧ V e r o n a ‧ 2 0 1 3
Mesh di triangoli
• discretizzazione lineare a tratti
di una superfice continua (un “2 manifold”) immersa in R 3
• Componenti:
1. geometria
• i vertici, ciascuno con pos (x,y,z)
• un campionamento della superficie!
2. connettività
• come sono connessi i vertici
• (es.: in una tri-mesh, i triangoli) 3. attributi
• es: colore, materiali, normali, UV, temperatura
M a r c o T a r i n i ‧ [ G A M E - D E V ] ‧ V e r o n a ‧ 2 0 1 3
Mesh triangolare (o mesh simpliciale)
• Un insieme di triangoli adiacenti
facce
vertici
spigoli
(o edges)
Mesh: intro
• GPU friendly
• Risoluzione (potenzialmente) adattiva
• “Complessità” = numero facce
M a r c o T a r i n i ‧ [ G A M E - D E V ] ‧ V e r o n a ‧ 2 0 1 3
Mesh: cenni storici
• Da sempre, il dataset cardine della C.G.
• Costante aumento complessità
• Tecnologie base di creazione:
– anni ’80: parametric surfaces (NURBS, splines) GSM / isosuperfici,
CAD
– anni ’90: scansione /acquisizione;
superfici di suddivisione;
semplificazione automatica;
– anni ’00: on-card geometry amplification;
computer vision – anni ’10: reverse engineering
(semiregular quads)
M a r c o T a r i n i ‧ [ G A M E - D E V ] ‧ V e r o n a ‧ 2 0 1 3
Simplicial Meshes: complessità crescente
70.000 △
1994
M a r c o T a r i n i ‧ [ G A M E - D E V ] ‧ V e r o n a ‧ 2 0 1 3
Simplicial Meshes: complessità crescente
1.200.000 △
1997
M a r c o T a r i n i ‧ [ G A M E - D E V ] ‧ V e r o n a ‧ 2 0 1 3
Simplicial Meshes: complessità crescente
2.000.000.000 △
2002
M a r c o T a r i n i ‧ [ G A M E - D E V ] ‧ V e r o n a ‧ 2 0 1 3
M a r c o T a r i n i ‧ C o m p u t e r G r a p h i c s ‧ 2 0 1 2 / 1 3 ‧ U n i v e r s i t à d e l l ’ I n s u b r i a
Ma… in ambiente games
• LOW POLY MODELLING!
Low Poly modelling
M a r c o T a r i n i ‧ [ G A M E - D E V ] ‧ V e r o n a ‧ 2 0 1 3
pixel art
: (high-res) mesh
(high res) images
= :
low-poly models
M a r c o T a r i n i ‧ [ G A M E - D E V ] ‧ V e r o n a ‧ 2 0 1 3
Metal Slug (1996, Nazca Copr), on Neo Geo (SNK) Solomons’s key
(1986, Temco) on Z80
reminder:
per tutti gli ‘80,
il principale asset asset asset asset dei games é consistito in
sprites/tiles sprites/tiles sprites/tiles
sprites/tiles in pixel art pixel art pixel art ... pixel art
M a r c o T a r i n i ‧ C o m p u t e r G r a p h i c s ‧ 2 0 1 2 / 1 3 ‧ U n i v e r s i t à d e l l ’ I n s u b r i a by Phillip Heckinger (3D modeller)
Low-poly modelling
Mesh editing: applicativi generici
• 3D Studio Max (autodesk) , Maya (alias) , Cinema4D (maxon)
– generici, potenti, completi
• Blender
– idem, ma open-source e freeware (simile a: Gimp VS. Adobe Photoshop per 2D images)
• MeshLab
– open-source, grande collezione algoritmi di geometry processing …
• AutoCAD (autodesk), SolidWorks (SolidThinking)
– per CAD
• ZBrush (pixologic) , Mudbox (autodesk)
– scultura virtuale, specializzato in ritocco manuale dettagli hi-freq, bumpmapping, normalmaps…
• Wings3D
– open-source, piccolo, specializzato in low-poly editing, subdivision surfaces
• [Rhinoceros]
– parametric surfaces (NURBS)
• Sculptris
– Metafora scultura
• FragMotion
– specializzato per mesh animate
• …
• + moltissimi strumenti per contesti specifici
– (editing di umani, di interni architetturali, di paesaggi, o editor specifici per game-engines, etc...) M a r c o T a r i n i ‧ [ G A M E - D E V ] ‧ V e r o n a ‧ 2 0 1 3
Mesh editing: librerie
• VCG-Lib (CNR, it)
– Vision and Computer Graphic Lib
• OpenMesh (RWTH, de)
• CGAL (~INRIA, fr)
– Computational Geometry Algorithms Library
– tutte e tre: C++, open-suorce.
M a r c o T a r i n i ‧ [ G A M E - D E V ] ‧ V e r o n a ‧ 2 0 1 3
Argomento molto vasto
• Un buon manuale:
M a r c o T a r i n i ‧ [ G A M E - D E V ] ‧ V e r o n a ‧ 2 0 1 3
M a r c o T a r i n i ‧ [ G A M E - D E V ] ‧ V e r o n a ‧ 2 0 1 3
Formati files per mesh …
(da xkcd.com) xkcd.com) xkcd.com) xkcd.com)
M a r c o T a r i n i ‧ [ G A M E - D E V ] ‧ V e r o n a ‧ 2 0 1 3
Formati files per mesh
(una Torre di Babele!)
• 3DS -
3D Studio Max file format• OBJ –
Another file format for 3D objects• MA, MB –
Maya file formats• 3DX –
Rinoceros file format• BLEND –
Blender file format• DAE –
COLLADACOLLADA file format (Khornos)COLLADACOLLADA• FBX –
Autodesk interchange file format• X –
Direct X object• SMD –
good for animations (by Valve)• MD3 –
quake 3 vertex animations• DEM -
Digital Elevation Models• DXF –
(exchange format, Autodesk's AutoCAD)• FIG -
Used by REND386/AVRIL• FLT -
MulitGen Inc.'s OpenFlight format• HDF -
Hierarchical Data Format• IGES -
Initial Graphics Exchange Specification• IV -
Open Inventor File Format Info• LWO, LWB & LWS
- Lightwave 3D file formats• MAZ -
Used by Division's dVS/dVISE• MGF -
Materials and Geometry Format• MSDL -
Manchester Scene Description Language• 3DML –
by Flatland inc.• C4D –
Cinema 4D file format• SLDPTR –
SolidWork "part"• WINGS –
Wings3D object• NFF -
Used by Sense8's WorldToolKit• SKP –
Google sketch up• KMZ –
Google Earth model• OFF -
A general 3D mesh Object File Format• OOGL -
Object Oriented Graphics Library• PLG -
Used by REND386/AVRIL• POV –
“persistence of vision” ray-tracer• QD3D -
Apple's QuickDraw 3D Metafile format• TDDD -
for Imagine & Turbo Silver ray-tracers• NFF & ENFF -
(Extended) Neutral File Format• VIZ -
Used by Division's dVS/dVISE• VRML, VRML97 -
Virtual Reality Modeling Language (RIP)• X3D –
tentato successore di VRML• PLY –
introdotto by Cyberware – tipic. dati range scan• DICOM
–Dalla casa omonima – tipic. dati CAT scan• Renderman
–per l'omonimo visualizzatore• RWX
–RenderWare Object• Z3D –
ZModeler File format• etc, etc, etc...
M a r c o T a r i n i ‧ [ G A M E - D E V ] ‧ V e r o n a ‧ 2 0 1 3
Come definisco una triangle mesh?
• Una tri-mesh è un insieme di triangoli adiacenti
• Strutture dati?
• Modo diretto:
– un vettore di triangoli
– e per ogni triangolo tre vertici – e per ogni vertice tre coordinate
• Ma: replicazione dati
– poco efficiente in spazio – oneroso fare updates
M a r c o T a r i n i ‧ [ G A M E - D E V ] ‧ V e r o n a ‧ 2 0 1 3
cubo.ply
Esempio di file format : formato PLY
• Esempio:
ply
format ascii 1.0
comment proprio un cubetto element vertex 8
property float x property float y property float z element face 12
property list uchar int vertex_indices end_header
<dati...>
M a r c o T a r i n i ‧ [ G A M E - D E V ] ‧ V e r o n a ‧ 2 0 1 3
LetteraL.off
Esempio di file format : formato OFF
• Esempio:
1 5 1 0 5 1 4 3 2 1 0 4 5 4 3 0 4 6 7 8 9 4 6 9 10 11 4 0 1 7 6 4 1 2 8 7 4 2 3 9 8 4 3 4 10 9 4 4 5 11 10 4 5 0 6 11 OFF
12 10 40 0 0 0 3 0 0 3 1 0 1 1 0 1 5 0 0 5 0 0 0 1 3 0 1 3 1 1 1 1 1
# vertici
# facce # edges
x,y,z 2ndo vert
prima faccia:
4 vertici:
con indici 3, 2, 1 e 0 indice 0
indice 3 indice 2 indice 1
M a r c o T a r i n i ‧ [ G A M E - D E V ] ‧ V e r o n a ‧ 2 0 1 3
Esempio di file format : formato PLY
• E' un formato digitale per mesh superficiali
• Può essere in binario, o in ASCII (testo) – binario: più compatto e veloce da leggere
– ascii: direttamente leggibile con un editore di testo
• In ogni caso, comincia con un header in ASCII
M a r c o T a r i n i ‧ [ G A M E - D E V ] ‧ V e r o n a ‧ 2 0 1 3
E gli attributi?
• Tipicamente definiti:
– per vertice
• un attributo nella struttura di ogni vertice
– per faccia
• un attributo nella struttura di ogni faccia
– per wedge (vertice di faccia)
• tre attributi nella struttura di ogni faccia (caso più generico!)
– per edge (raro)
• Attributi più comuni:
– colore
– coordinate texture – normali...
M a r c o T a r i n i ‧ [ G A M E - D E V ] ‧ V e r o n a ‧ 2 0 1 3
Caratteristiche della connettività di una mesh
• Orientabile, non orientabile
– è possibile assegnare un orientamento ad ogni faccia coerentemente?
– orientabile = normali coerenti!
1
3 2 1
3 2
senso opposto, edge coerente A
B C
D
M a r c o T a r i n i ‧ [ G A M E - D E V ] ‧ V e r o n a ‧ 2 0 1 3
Mesh: strutture dati
• Strutture basate su half half----edges half half edges edges edges
V3 V4
V1
V5
V2
M a r c o T a r i n i ‧ [ G A M E - D E V ] ‧ V e r o n a ‧ 2 0 1 3
Mesh: task comuni
• Data una mesh:
– magari appena caricata
• trovare il AABB
(axis aligned bounding box)
– utile ad esempio per translare e scalare l'oggetto opportunamente – come si fa?
• (si itera sui vertici:
trovare il max e il min
di tutte le x, le y e le z)
M a r c o T a r i n i ‧ [ G A M E - D E V ] ‧ V e r o n a ‧ 2 0 1 3
Mesh: task comuni
• Data una mesh:
– magari appena caricata
• trovare le normali per faccia
• trovare le normali per vertice – come si fa?
– che struttura serve?
• (FV? VF?)
BASTA LA FV!
1 azzerare tutte le norm x vertice 2 iterare su ogni faccia:
- trovare normale x faccia (normalizzata)
- aggiungerla a normale dei tre vertici incidenti (FV) 3 iterare su ogni vertice:
normalizzare normale x vertice
M a r c o T a r i n i ‧ [ G A M E - D E V ] ‧ V e r o n a ‧ 2 0 1 3
Mesh: altri task
• Parametrizzazione
– assegnare una coppia di coordinate texture ad ogni wedge
– ci sono seams
• replicare i vertici
• oppure, memorizzale le text coord per wedge
u
v
M a r c o T a r i n i ‧ C o m p u t e r G r a p h i c s ‧ 2 0 1 2 / 1 3 ‧ U n i v e r s i t à d e l l ’ I n s u b r i a
Task: “u-v mapping” di una mesh (“u-v” == “s-t”)
• Assegnare una coppia di coordinate texutres ad ogni vertice della mesh
– In preprocessing
s t
s t
M a r c o T a r i n i ‧ C o m p u t e r G r a p h i c s ‧ 2 0 1 2 / 1 3 ‧ U n i v e r s i t à d e l l ’ I n s u b r i a
Problema difficile: “u-v mapping” (“u-v” == “s-t”)
fatto a mano,
oppure automatizzato
M a r c o T a r i n i ‧ [ G A M E - D E V ] ‧ V e r o n a ‧ 2 0 1 3
Mesh: altri task
automaticamente
mesh semplificata 2K triangles mesh originale
500K triangoli
• Semplificazione automatica
• parametri:
– un errore massimo
– o un numero di facce obiettivo
M a r c o T a r i n i ‧ [ G A M E - D E V ] ‧ V e r o n a ‧ 2 0 1 3
Semplificazione automatica
p e r f o r m a n c e
q u a l i t y
M a r c o T a r i n i ‧ [ G A M E - D E V ] ‧ V e r o n a ‧ 2 0 1 3
Semplificazione automatica
LOD 1 LOD 2 LOD 3 LOD 4
Una piramide di Livelli di Dettaglio
usare quando visto da vicino
usare quando visto da lontano
M a r c o T a r i n i ‧ [ G A M E - D E V ] ‧ V e r o n a ‧ 2 0 1 3
Semplificazione automatica
• Molte tecniche diverse
– Adattive oppure no
• usare piu' triangoli dove c'e' bisogno (es non nelle zone cmq piatte)
• oppure no
– Errore massimo introdotto:
• misurato e/o limitato
• oppure no
– Topologia:
• mantenuta
• oppure no
– Streaming
• Possibile
• Oppure no
– ...
M a r c o T a r i n i ‧ [ G A M E - D E V ] ‧ V e r o n a ‧ 2 0 1 3
Detail preservation
(o "texture for geometry")
• Idea:
– semplificare una mesh – sintetizzare una tessitura
– per ripristinare il dettaglio perso durante la semplificazione
M a r c o T a r i n i ‧ [ G A M E - D E V ] ‧ V e r o n a ‧ 2 0 1 3
500mila triangoli
2mila triangoli
semplificazione automatica
sempre duemila triangoli, ma con texture mapping
rendering
TESSITURA fatta apposta (es. BumpMap) detail
recover
M a r c o T a r i n i ‧ [ G A M E - D E V ] ‧ V e r o n a ‧ 2 0 1 3
simplificato
2K triangles
originale
500K triangles
semplificato ma con tessitura
2K triangles
Mesh: task tipici nella game industry
• Semplificazione automatica
– LOD construction
• Light baking
– Precomputazione Luce
– Tipico esempio: Ambient Occlusion
• U-V mapping
– parametrizzazione
• Texturing
– creazione tessiture
• Rigging / Animation
– linear blend skinning
M a r c o T a r i n i ‧ [ G A M E - D E V ] ‧ V e r o n a ‧ 2 0 1 3
