THEORY OF THREE DIMENSIONAL COMPUTER GRAPHICS
CONTENTS 1 INFORMATION THEORY BASICS 1 1 1 ENTROPY 1 1 2 RELATIVE ENTROPY AND MUTUAL INFORMATION 6 1 3 INEQUALITIES 8 1 3 1 JENSEN S INEQUALITY 8 1 3 2 LOG SUM INEQUALITY 9 1 3 3 JENSEN SHANNON INEQUALITY 9 1 3 4 DATA PROCESSING INEQUALITY 10 1 4 ENTROPY RATE 10 1 5 ENTROPY AND CODING 12 1 6 CONTINUOUS CHANNEL 13 1 7 INFORMATION BOTTLENECK METHOD 15 1 8 F DIVERGENCES 16 1 9 GENERALIZED ENTROPIES 17 2 SCENE COMPLEXITY AND RE NEMENT CRITERIA FOR RADIOSITY 19 2 1 BACKGROUND 19 2 1 1 RADIOSITY METHOD 19 2 1 2 FORM FACTOR COMPUTATION 22 2 1 3 SCENE RANDOM WALK 24 2 2 SCENE INFORMATION CHANNEL 25 2 2 1 BASIC DE NITIONS 25 2 2 2 FROM VISIBILITY TO RADIOSITY 28 2 3 SCENE COMPLEXITY 30 2 3 1 CONTINUOUS SCENE VISIBILITY MUTUAL INFORMATION 31 2 3 2 COMPUTATION OF SCENE VISIBILITY COMPLEXITY 32 2 3 3 COMPLEXITY AND DISCRETISATION 33 2 4 RE NEMENT CRITERION BASED ON MUTUAL INFORMATION 38 2 4 1 LOSS OF INFORMATION TRANSFER DUE TO DISCRETISATION 38 2 4 2 MUTUAL INFORMATION BASED ORACLE FOR HIERARCHICAL RADIOSITY 39 2 5 RE NEMENT CRITERIA BASED ON F DIVERGENCES 41 3 SHAPE DESCRIPTORS 47 3 1 BACKGROUND 47 3 2 INNER SHAPE COMPLEXITY 48 3 2 1 COMPLEXITY MEASURE 48 3 2 2 INNER 3D SHAPE COMPLEXITY RESULTS 50 3 2 3 INNER 2D SHAPE COMPLEXITY RESULTS 52 3 3 OUTER SHAPE COMPLEXITY 53 4 RE NEMENT CRITERIA FOR RAY TRACING 57 4 1 BACKGROUND 57 4 2 PIXEL QUALITY 59 4 2 1 PIXEL COLOR ENTROPY 59 4 2 2 PIXEL GEOMETRY ENTROPY 61 4 3 PIXEL CONTRAST 62 4 3 1 PIXEL COLOR CONTRAST 62 4 3 2 PIXEL GEOMETRY CONTRAST 64 4 3 3 PIXEL COLOR GEOMETRY CONTRAST 65 4 4 ENTROPY BASED SUPERSAMPLING 66 4 4 1 ALGORITHM 66 4 4 2 RESULTS 67 4 5 ENTROPY BASED ADAPTIVE SAMPLING 67 4 5 1 ADAPTIVE SAMPLING 67 4 5 2 ALGORITHM 70 4 5 3 IMPLEMENTATION 72 4 5 4 RESULTS 73 4 6 F DIVERGENCES IN ADAPTIVE SAMPLING FOR RAY TRACING 76 4 6 1 ALGORITHM 76 4 6 2 RESULTS 78 5 VIEWPOINT SELECTION AND MESH SALIENCY 83 5 1 BACKGROUND 83 5 2 VIEWPOINT CHANNEL 84 5 2 1 VIEWPOINT ENTROPY AND MUTUAL INFORMATION 84 5 2 2 RESULTS 88 5 3 VIEWPOINT SIMILARITY AND STABILITY 89 5 4 BEST VIEW SELECTION AND OBJECT EXPLORATION 93 5 4 1 SELECTION OF N BEST VIEWS 93 5 4 2 OBJECT EXPLORATION 94 5 5 VIEW BASED POLYGONAL INFORMATION AND SALIENCY 96 5 5 1 VIEW BASED POLYGONAL INFORMATION 97 5 5 2 VIEW BASED MESH SALIENCY 98 5 6 IMPORTANCE DRIVEN VIEWPOINT SELECTION 100 6 VIEW SELECTION IN SCIENTI C VISUALIZATION 105 6 1 ADAPTATION FROM POLYGONS TO VOLUMES 106 6 1 1 ISOSURFACES 106 6 1 2 VOLUMETRIC DATA 107 6 2 INTEGRATION OF DOMAIN SEMANTICS 109 6 2 1 VISUALIZATION OF MOLECULAR STRUCTURES 109 6 2 2 GUIDED NAVIGATION IN DATA SEMANTICS 111 7 VIEWPOINT BASED GEOMETRY SIMPLI CATION 117 7 1 BACKGROUND 117 7 2 VIEWPOINT BASED ERROR METRIC 118 7 2 1 ANALYSIS 119 7 3 SIMPLI CATION ALGORITHM 121 7 4 EXPERIMENTS 123 7 4 1 VIEWPOINT ENTROPY 124 7 4 2 VIEWPOINT MUTUAL INFORMATION 124 7 4 3 VIEWPOINT KULLBACK LEIBLER DISTANCE 127 SUMMARY 133 C H A P T E R 1 INFORMATION THEORY BASICS IN 1948 CLAUDE SHANNON PUBLISHED A PAPER ENTITLED A MATHEMATICAL THEORY OF COMMUNICA TION 113 WHICH MARKS THE BEGINNING OF INFORMATION THEORY IN THIS PAPER SHANNON DE NED MEASURES SUCH AS ENTROPY AND MUTUAL INFORMATION1 AND INTRODUCED THE FUNDAMENTAL LAWS OF DATA COMPRESSION AND TRANSMISSION INFORMATION THEORY DEALS WITH THE TRANSMISSION STORAGE AND PRO CESSING OF INFORMATION AND IS USED IN ELDS SUCH AS PHYSICS COMPUTER SCIENCE MATHEMATICS STATISTICS ECONOMICS BIOLOGY LINGUISTICS NEUROLOGY LEARNING IMAGE PROCESSING AND COMPUTER GRAPHICS IN INFORMATION THEORY INFORMATION IS SIMPLY THE OUTCOME OF A SELECTION AMONG A NITE NUMBER OF POSSIBILITIES AND AN INFORMATION SOURCE IS MODELED AS A RANDOM VARIABLE OR A RANDOM PROCESS THE CLASSICAL MEASURE OF INFORMATION SHANNON ENTROPY EXPRESSES THE INFORMATION CONTENT OR THE UNCERTAINTY OF A SINGLE RANDOM VARIABLE IT IS ALSO A MEASURE OF THE DISPERSION OR DIVERSITY OF A PROBABILITY DISTRIBUTION OF OBSERVED EVENTS FOR TWO RANDOM VARIABLES THEIR MUTUAL INFORMATION IS A MEASURE OF THE DEPENDENCE BETWEEN THEM MUTUAL INFORMATION PLAYS AN IMPORTANT ROLE IN THE STUDY OF A COMMUNICATION CHANNEL A SYSTEM IN WHICH THE OUTPUT DEPENDS PROBABILISTICALLY ON ITS INPUT 25 139 146 THIS CHAPTER PRESENTS SHANNON S INFORMATION MEASURES ENTROPY CONDITIONAL ENTROPY AND MU TUAL INFORMATION AND THEIR MOST BASIC PROPERTIES THE INFORMATION BOTTLENECK METHOD F DIVERGENCES AND GENERALIZED ENTROPIES ARE ALSO INTRODUCED GOOD REFERENCES OF INFORMATION THEORY ARE THE BOOKS BY COVER AND THOMAS 25 AND YEUNG 146 1 1 ENTROPY AFTER REPRESENTING A DISCRETE INFORMATION SOURCE AS A RANDOM PROCESS SHANNON ASKS HIMSELF CAN WE DE NE A QUANTITY WHICH WILL MEASURE IN SOME SENSE HOW MUCH INFORMATION IS PRODUCED BY SUCH A PROCESS OR BETTER AT WHAT RATE INFORMATION IS PRODUCED 113 IN HIS ANSWER SHANNON SUPPOSES THAT WE HAVE A SET OF POSSIBLE EVENTS WHOSE PROBABILITIES OF OCCURRENCE ARE P1 P2 PN AND ASKS FOR THE POSSIBILITY OF NDING A MEASURE DENOTED BY H P1 P2 PN OF HOW MUCH CHOICE IS INVOLVED IN THE SELECTION OF THE EVENT OR OF HOW UNCERTAIN WE ARE OF THE OUTCOME IF THIS UNCERTAINTY MEASURE EXISTS SHANNON CONSIDERS REASONABLE TO REQUIRE OF IT THE FOLLOWING PROPERTIES 1 H WOULD BE CONTINUOUS IN THE PI 1IN SHANNON S PAPER THE MUTUAL INFORMATION IS CALLED RATE OF TRANSMISSION